completing the proof.

##### Proof of Theorem 4.

Notice that

$\displaystyle H\left({\bf w}(t;\theta)\right)$
$\displaystyle=-\sum_{i\in[N]}w_{i}(t;\theta)\log w_{i}(t;\theta)$ (145)
$\displaystyle=-\frac{1}{N}\sum_{i\in[N]}(tf(x_{i};\theta)-\widetilde{\Lambda}(t;\theta))e^{tf(x_{i};\theta)-\widetilde{\Lambda}(t;\theta)}$
(146)
$\displaystyle=\widetilde{\Lambda}(t;\theta)-t\frac{1}{N}\sum_{i\in[N]}f(x_{i};\theta)e^{tf(x_{i};\theta)-\widetilde{\Lambda}(t;\theta)}$
(147)
$\displaystyle=\widetilde{\Lambda}(t;\theta)-tA(\theta)+t\theta^{\top}\mathcal{M}(t;\theta).$
(148)

Thus,

$\displaystyle\nabla_{\theta}H\left({\bf w}(t;\theta)\right)$
$\displaystyle=\nabla_{\theta}\left(\widetilde{\Lambda}(t;\theta)-tA(\theta)+t\theta^{\top}\mathcal{M}(t;\theta)\right)$
(149)
$\displaystyle=t\nabla_{\theta}A(\theta)-t\mathcal{M}(t;\theta)-t\nabla_{\theta}A(\theta)+t\mathcal{M}(t;\theta)-t^{2}\mathcal{V}(t;\theta)\theta$
(150) $\displaystyle=-t^{2}\mathcal{V}(t;\theta)\theta.$ (151)

Hence,

$\displaystyle\frac{\partial}{\partial\tau}H\left({\bf
w}(t;\breve{\theta}(\tau))\right)$
$\displaystyle=\left(\frac{\partial}{\partial\tau}\breve{\theta}(\tau)\right)^{\top}\nabla_{\theta}H\left({\bf
w}(t;\breve{\theta}(\tau))\right)$ (152)
$\displaystyle=\left(\frac{\partial}{\partial\tau}\breve{\theta}(\tau)\right)^{\top}\nabla_{\theta}\left(\widetilde{\Lambda}(t;\theta)-tA(\theta)+t\theta^{\top}\mathcal{M}(t;\theta)\right)$
(153)
$\displaystyle=t^{2}\breve{\theta}^{\top}(\tau)\mathcal{V}(\tau;\breve{\theta}(\tau))\left(\nabla^{2}_{\theta\theta}A(\breve{\theta}(\tau))+\tau\mathcal{V}(\tau;\breve{\theta}(\tau))\right)^{-1}\mathcal{V}(t;\breve{\theta}(\tau))\breve{\theta}(\tau)$
(154)

and

$\displaystyle\left.\frac{\partial}{\partial\tau}H\left({\bf
w}(t;\breve{\theta}(\tau))\right)\right|_{t=\tau}\geq 0,$ (155)

completing the proof.

##  B Connections to Other Objectives (Proofs and Additional Results)

Notice that we have the following simple relation:

######  Lemma 24.

If $a<\widetilde{F}(-\infty)$ then $\widetilde{Q}^{0}(\gamma)=1$. Further, if
$\gamma>\widetilde{F}(+\infty)$ then $\widetilde{Q}^{0}(\gamma)=0$, where
$\widetilde{F}(\cdot)$ is defined in Definition 11, and is reproduced here:

$\displaystyle\widetilde{F}(-\infty)$
$\displaystyle=\lim_{t\to-\infty}\widetilde{R}(t;\breve{\theta}(t))=\min_{\theta}\min_{i\in[N]}f(x_{i};\theta),$
(156) $\displaystyle\widetilde{F}(+\infty)$
$\displaystyle=\lim_{t\to+\infty}\widetilde{R}(t;\breve{\theta}(t))=\min_{\theta}\max_{i\in[N]}f(x_{i};\theta).$
(157)

Next, we present our main result on the connection between the superquantile
method and TERM.

######  Theorem 14.

For all $t\in\mathbb{R},$ and all $\theta$, and all
$\gamma\in(\widetilde{F}(-\infty),\widetilde{F}(+\infty)),$555We define the
RHS at $t=0$ via continuous extension.

$\widetilde{Q}(\gamma;\theta)\leq\overline{Q}(\gamma;t,\theta):=\frac{e^{\widetilde{R}(t;\theta)t}-e^{\widetilde{F}(-\infty)t}}{e^{\gamma
t}-e^{\widetilde{F}(-\infty)t}}.$ (158)

###### Proof.

We have

$\displaystyle\widetilde{Q}(\gamma;\theta)$
$\displaystyle=\frac{\frac{1}{N}\sum_{i\in[N]}e^{(\gamma-\widetilde{F}(-\infty))t\mathbb{I}\left\\{\frac{f(x_{i};\theta)-\widetilde{F}(-\infty)}{\gamma-\widetilde{F}(-\infty)}\geq
1\right\\}}-1}{e^{(\gamma-\widetilde{F}(-\infty))t}-1}$ (159)
$\displaystyle\leq\frac{\frac{1}{N}\sum_{i\in[N]}e^{(f(x_{i};\theta)-\widetilde{F}(-\infty))t}-1}{e^{(\gamma-\widetilde{F}(-\infty))t}-1}$
(160)
$\displaystyle=\frac{e^{\widetilde{R}(t;\theta)t}-e^{\widetilde{F}(-\infty)t}}{e^{\gamma
t}-e^{\widetilde{F}(-\infty)t}},$ (161)

where (159) follows from Lemma 162, (160) follows from Lemma 26, the fact that
$e^{tx}$ is strictly increasing (resp. decreasing) for $t>0$ (resp. $t<0$) and
$(e^{(\gamma-\widetilde{F}(-\infty))t}-1)$ is positive (resp. negative) for
$t>0$ (resp. $t<0$), and (161) follows from definition. ∎

######  Lemma 25.

For all $t\in\mathbb{R},$ and all $\theta$,666We define the RHS at $t=0$ via
continuous extension.

$\widetilde{Q}(\gamma;\theta)=\frac{\frac{1}{N}\sum_{i\in[N]}e^{(\gamma-\widetilde{F}(-\infty))t\mathbb{I}\left\\{f(x_{i};\theta)\geq\gamma\right\\}}-1}{e^{(\gamma-\widetilde{F}(-\infty))t}-1}.$
(162)

###### Proof.

The proof is completed following this identity:

$\displaystyle\frac{1}{N}\sum_{i\in[N]}e^{(\gamma-\widetilde{F}(-\infty))\mathbb{I}\left\\{f(x_{i};\theta)\geq\gamma\right\\}t}=\widetilde{Q}(\gamma;\theta)e^{(\gamma-\widetilde{F}(-\infty))t}+(1-\widetilde{Q}(\gamma;\theta)).$
(163)

∎

######  Lemma 26.

For $x\geq 0$, we have $\mathbb{I}\\{x\geq 1\\}\leq x.$

Recall that optimizing $\widetilde{\text{VaR}}$ is equivalent to optimizing
$\widetilde{Q}$. Next we show how TERM is related to optimizing
$\widetilde{Q}$. Recall that $\widetilde{Q}^{0}(\gamma)$ denotes the optimal
value of $\widetilde{Q}(\gamma;\theta)$ optimized over $\theta.$ Let

$\widetilde{Q}^{1}(\gamma):=\inf_{t\in\mathbb{R}}\left\\{\widetilde{Q}(\gamma;\breve{\theta}(t))\right\\},$
(164)

which denotes the value at risk optimized over the $t$-tilted solutions.

######  Theorem 15.

For all $\gamma\in(\widetilde{F}(-\infty),\widetilde{F}(+\infty)),$ we have

$\widetilde{Q}^{0}(\gamma)\leq\widetilde{Q}^{1}(\gamma)\leq\widetilde{Q}^{2}(\gamma)\leq\widetilde{Q}^{3}(\gamma)=\inf_{t\in\mathbb{R}}\left\\{\overline{Q}(\gamma,t)\right\\},$
(165)

where

$\displaystyle\overline{Q}(\gamma,t)$
$\displaystyle:=\frac{e^{\widetilde{F}(t)t}-e^{\widetilde{F}(-\infty)t}}{e^{\gamma
t}-e^{\widetilde{F}(-\infty)t}},$ (166)
$\displaystyle\widetilde{t}^{3}(\gamma)$
$\displaystyle:=\arg\inf_{t\in\mathbb{R}}\left\\{\overline{Q}(\gamma,t)\right\\},$
(167) $\displaystyle\widetilde{Q}^{2}(\gamma)$
$\displaystyle:=\widetilde{Q}(\gamma;\breve{\theta}(\widetilde{t}^{3}(\gamma))),$
(168) $\displaystyle\widetilde{Q}^{3}(\gamma)$
$\displaystyle:=\overline{Q}(\gamma,\widetilde{t}^{3}(\gamma)).$ (169)

###### Proof.

The only non-trivial step is to show that $Q^{2}(\gamma)\leq Q^{3}(\gamma).$
Following Theorem 158,

$\displaystyle Q^{2}(\gamma)$
$\displaystyle=\widetilde{Q}(\gamma;\breve{\theta}(\widetilde{t}(\gamma))\leq\inf_{t\in\mathbb{R}}\overline{Q}(\gamma;t,\breve{\theta}(t))=Q^{3}(\gamma),$
(170)

which completes the proof. ∎

Theorem 15 motivates us with the following approximation on the solutions of
the superquantile method.

######  Approximation 1.

For all $\gamma\in(\widetilde{F}(-\infty),\widetilde{F}(+\infty)),$

$\widetilde{Q}(\gamma;\theta^{0}(\gamma))=\widetilde{Q}^{0}(\gamma)\approx\widetilde{Q}^{2}(\gamma)=\widetilde{Q}(\gamma;\breve{\theta}(\widetilde{t}(\gamma))),$
(171)

and hence, $\breve{\theta}(\widetilde{t}(\gamma))$ is an approximate solution
to the superquantile optimization problem.

Figure 13: Comparing the solutions of different risks in terms of how well
they solve VaR. For $i\in\\{0,1,2\\}$,
$\widetilde{\text{VaR}}^{i}(1-\alpha):=\min_{\gamma}\\{\gamma|\widetilde{Q}^{i}(\gamma)\leq\alpha\\}$.
$\widetilde{\text{VaR}}^{0}(1-\alpha):=\min_{\gamma}\\{\gamma|\widetilde{Q}^{0}(\gamma)\leq\alpha\\}$
is the optimal $\widetilde{\text{VaR}}(1-\alpha;\theta)$. By definition,
$\widetilde{\text{VaR}}^{2}(1-\alpha)$ is the risk value of
$\widetilde{\text{VaR}}(1-\alpha;\theta)$ with $\theta$ being the solutions of
$\widetilde{\text{TiVaR}}(1-\alpha;\theta)$.
$\widetilde{\text{VaR}}^{\widetilde{\text{CVaR}}}(1-\alpha)$ denotes the value
of $\widetilde{\text{VaR}}(1-\alpha;\theta)$ evaluated at
$\arg\min_{\theta}\widetilde{\text{CVaR}}(1-\alpha;\theta)$, and
$\widetilde{\text{VaR}}^{\widetilde{\text{EVaR}}}(1-\alpha)$ is defined in the
similar way. We see that $\widetilde{\text{VaR}}^{1}(1-\alpha)$ and
$\widetilde{\text{VaR}}^{2}(1-\alpha)$ are close to
$\widetilde{\text{VaR}}^{0}(1-\alpha)$, which indicates VaR with the solutions
obtained from solving $\widetilde{\text{TiVaR}}(1-\alpha;\theta)$ (which is
$\widetilde{\text{VaR}}^{2}(1-\alpha)$) is a tight upper bound of the globally
optimal $\widetilde{\text{VaR}}(1-\alpha;\theta)$.
$\widetilde{\text{VaR}}^{2}(1-\alpha)$ is also tighter than VaR under CVaR or
EVaR solutions when $\alpha$ is not small.

While we have not characterized how tight this approximation is for
$\gamma\in(\widetilde{F}(-\infty),\widetilde{F}(+\infty))$, we believe that
Approximation 1 provides a reasonable solution to the superquantile
optimization problem in general. This is evidenced empirically when the
approximation is evaluated on the toy examples of Figure 1, and compared with
the global solutions of the superquantile method, as shown in Figure 13. As
can be seen, $\widetilde{Q}^{0}(\gamma)\approx\widetilde{Q}^{2}(\gamma)$ as
suggested by Approximation 1. Also, we can see that while the bound in Theorem
15 ($\widetilde{Q}^{3}(\gamma)$) is not tight, the solution that is obtained
from solving it ($\widetilde{Q}^{2}(\gamma)$) results in a good approximation
to the superquantile optimization ($\widetilde{Q}^{0}(\gamma)$).

##### Proof of Theorem 5.

We first prove
$\widetilde{\text{TiVaR}}(1-\alpha;\theta)\leq\widetilde{\text{EVaR}}(1-\alpha;\theta)$.

$\displaystyle\widetilde{\text{EVaR}}(1-\alpha;\theta)-\widetilde{F}(-\infty)$
$\displaystyle=\min_{t\in\mathbb{R}^{+}}\frac{1}{t}\log\left(\frac{\frac{1}{N}\sum_{i\in[N]}e^{tf(x_{i};\theta)}}{\alpha}\right)-\widetilde{F}(-\infty)$
(172)
$\displaystyle=\min_{t\in\mathbb{R}^{+}}\frac{1}{t}\log\left(\frac{e^{(\widetilde{R}(t;\theta)-\widetilde{F}(-\infty))t}}{\alpha}\right)$
(173)
$\displaystyle\geq\min_{t\in\mathbb{R}^{+}}\frac{1}{t}\log\left[\frac{e^{(\widetilde{R}(t;\theta)-\widetilde{F}(-\infty))t}-(1-\alpha)}{\alpha}\right]_{+}$
(174)
$\displaystyle\geq\min_{t\in\mathbb{R}}\frac{1}{t}\log\left[\frac{e^{(\widetilde{R}(t;\theta)-\widetilde{F}(-\infty))t}-(1-\alpha)}{\alpha}\right]_{+}.$
(175)

We next prove
$\widetilde{\text{VaR}}(1-\alpha;\theta)\leq\widetilde{\text{TiVaR}}(1-\alpha;\theta)$.
From Theorem 158, we know that for any $t,\theta$,

$\displaystyle\widetilde{Q}(\gamma;\theta)\leq\min_{t\in\mathbb{R}}\left\\{\frac{e^{\widetilde{R}(t;\theta)t}-e^{-\widetilde{F}(-\infty)t}}{e^{\gamma
t}-e^{\widetilde{F}(-\infty)t}}\right\\}$ (176)

Let $\widetilde{Q}(\gamma;\theta)=\alpha$, and
$\gamma^{*}=\widetilde{\text{VaR}}(1-\alpha;\theta)$. We have
$\min_{t\in\mathbb{R}}\left\\{\frac{e^{\widetilde{R}(t;\theta)t}-e^{-\widetilde{F}(-\infty)t}}{e^{\gamma^{*}t}-e^{\widetilde{F}(-\infty)t}}\right\\}\geq\alpha.$
We also note

$\displaystyle\min_{t\in\mathbb{R}}\left\\{\frac{e^{\widetilde{R}(t;\theta)t}-e^{-\widetilde{F}(-\infty)t}}{e^{\widetilde{\text{TiVaR}}(1-\alpha;\theta)t}-e^{\widetilde{F}(-\infty)t}}\right\\}=\alpha.$
(177)

Hence,

$\displaystyle\widetilde{\text{TiVaR}}(1-\alpha;\theta)\geq\gamma^{*}=\widetilde{\text{VaR}}(1-\alpha;\theta).$
(178)

##### TERM and Entropic Value-at-Risk.

Let $\breve{\theta}_{X}(t)$ be the minimizer of entropic risk
$R_{X}(t;\theta)$:

$\breve{\theta}_{X}(t):=\arg\min_{\theta\in\Theta}R_{X}(t;\theta).$ (179)

Further, let $F_{X}(t)$ be the optimum value of entropic risk, i.e.,

$F_{X}(t):=R_{X}(t;\breve{\theta}_{X}(t)).$ (180)

Our next result will relate EVaR to entropic risk.

######  Lemma 27 (Relations between entropic risk and EVaR).

Assume that for $t\in\mathbb{R}^{+},$ $F_{X}(t)$ is a strongly convex function
of $\frac{1}{t}$ . Further, let

$\displaystyle\breve{t}_{X}(\alpha)\in\arg\min_{t\in\mathbb{R}^{+}}\left\\{F_{X}(t)-\frac{1}{t}\log\alpha\right\\},$
(181)

then

$\displaystyle\arg\min_{\theta}\left\\{\text{EVaR}_{X}(1-\alpha;\theta)\right\\}$
$\displaystyle=\arg\min_{\theta}\left\\{R_{X}(\breve{t}_{X}(\alpha);\theta)\right\\}:=\breve{\theta}_{X}(\breve{t}_{X}(\alpha)),$
(182) $\displaystyle
R_{X}\left(\breve{t}_{X}(\alpha);\breve{\theta}_{X}(\breve{t}_{X}(\alpha))\right)$
$\displaystyle=F_{X}(\breve{t}_{X}(\alpha))\leq\text{EVaR}_{X}\left(1-\alpha;\breve{\theta}_{X}(\breve{t}_{X}(\alpha))\right).$
(183)

###### Proof.

Consider the any minimizer of $R_{X}(\breve{t}_{X}(\alpha),\theta)$, i.e.,

$\displaystyle\breve{\theta}_{X}(\breve{t}_{X}(\alpha))$
$\displaystyle\in\arg\min_{\theta}R_{X}(\breve{t}_{X}(\alpha);\theta),$ (184)

we next prove

$\displaystyle\breve{\theta}_{X}(\breve{t}_{X}(\alpha))\in\arg\min_{\theta}\left(\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\theta)}]-\frac{1}{t}\log\alpha\right)\right).$
(185)

Denote
$\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\theta)}]-\frac{1}{t}\log\alpha\right)$
as $h(\theta;\alpha)$. Let

$\displaystyle\theta_{v}^{*}$
$\displaystyle\in\arg\min_{\theta}h(\theta;\alpha),$ (186)
$\displaystyle{t}_{v}(\theta_{v}^{*})$
$\displaystyle\in\arg\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\theta_{v}^{*})}]-\frac{1}{t}\log\alpha\right).$
(187)

By the definition of $\breve{t}_{X}(\alpha)$ and $\breve{\theta}_{X}(t)$, we
have

$\displaystyle\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{\breve{t}_{X}(\alpha)}\log\alpha$
(188)
$\displaystyle\leq\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\breve{\theta}_{X}({t}_{v}(\theta_{v}^{*})))}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(189)
$\displaystyle\leq\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\theta_{v}^{*})}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha.$
(190)

By the definition of $\theta_{v}^{*}$, $h(\theta_{v}^{*};\alpha)\leq
h(\breve{\theta}_{X}(\breve{t}_{X}(\alpha));\alpha)$, i.e.,

$\displaystyle\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\theta_{v}^{*})}]-\frac{1}{t}\log\alpha\right)$
$\displaystyle\leq\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{t}\log\alpha\right).$
(191)

We have

$\displaystyle\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\theta_{v}^{*})}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(192)
$\displaystyle\leq\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{t}\log\alpha\right)$
(193)
$\displaystyle\leq\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{\breve{t}_{X}(\alpha)}\log\alpha,$
(194)

Hence,
$\breve{\theta}_{X}(\breve{t}_{X}(\alpha))\in\arg\min_{\theta}\left(\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\theta)}]-\frac{1}{t}\log\alpha\right)\right)$.

For the other direction, consider any minimizer of
$\text{EVaR}_{X}(1-\alpha;\theta)$, i.e.,

$\displaystyle\theta_{v}^{*}$
$\displaystyle\in\arg\min_{\theta}h(\theta;\alpha)$ (195)
$\displaystyle{t}_{v}(\theta_{v}^{*})$
$\displaystyle\in\arg\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{f(X;\theta_{v}^{*})}]-\frac{1}{t}\log\alpha\right).$
(196)

We next prove
$\theta_{v}^{*}\in\arg\min_{\theta}\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\theta)}]$.
By the definition of $\breve{\theta}_{X}(t)$ and $\breve{t}_{X}(\alpha)$,

$\displaystyle\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\theta_{v}^{*})}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(197)
$\displaystyle\geq\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;{\breve{\theta}}_{X}({t}_{v}(\theta_{v}^{*}))}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(198)
$\displaystyle\geq\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha))}]-\frac{1}{\breve{t}_{X}(\alpha)}\log\alpha.$
(199)

On the other hand, by the definition of $\theta_{v}^{*}$ and
${t}_{v}(\theta_{v}^{*})$,

$\displaystyle\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\theta_{v}^{*})}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
$\displaystyle\leq\min_{t>0}\left(\frac{1}{t}\log\mathbb{E}[e^{tf(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{t}\log\alpha\right)$
(200)
$\displaystyle\leq\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{\breve{t}_{X}(\alpha)}\log\alpha.$
(201)

Therefore,

$\displaystyle\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{{t}_{v}(\theta_{v}^{*})f(X;\theta_{v}^{*})}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(202)
$\displaystyle=\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\mathbb{E}[e^{t_{v}(\theta_{v}^{*})f(X;\breve{\theta}_{X}({t}_{v}(\theta_{v}^{*}))}]-\frac{1}{{t}_{v}(\theta_{v}^{*})}\log\alpha$
(203)
$\displaystyle=\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))}]-\frac{1}{\breve{t}_{X}(\alpha)}\log\alpha.$
(204)

If

$\displaystyle
s(t):=\frac{1}{t}\log\mathbb{E}[e^{tf(X;\breve{\theta}_{X}(t))}]-\frac{1}{t}\log\alpha$
(205)

has a unique minimizer,

$\displaystyle\breve{t}_{X}(\alpha)={t}_{v}(\theta_{v}^{*}),$ (206)

and

$\displaystyle\theta_{v}^{*}\in\arg\min_{\theta}\frac{1}{\breve{t}_{X}(\alpha)}\log\mathbb{E}[e^{\breve{t}_{X}(\alpha)f(X;\theta)}].$
(207)

Hence, we have proved

$\displaystyle\arg\min_{\theta}\text{EVaR}_{X}(1-\alpha;\theta)=\arg\min_{\theta}R_{X}(\breve{t}_{X}(\alpha);\theta),$
(208)

and

$\displaystyle
R_{X}(\breve{t}_{X}(\alpha);\breve{\theta}_{X}(\breve{t}_{X}(\alpha)))\leq\text{EVaR}_{X}(1-\alpha;\breve{\theta}_{X}(\breve{t}_{X}(\alpha))).$
(209)

∎

The lemma relates the solution and the optimal value of EVaR with those of
entropic risk. We can extend Lemma 27 to the empirical version below.

######  Lemma 28 (Relations between empirical entropic risk and empirical
EVaR).

Assume that $\widetilde{F}(t)$ is a strongly convex function of $\frac{1}{t}.$
For $\alpha\in\\{\frac{k}{N}\\}_{k\in[N]}$, let

$\displaystyle\breve{t}(\alpha)\in\arg\min_{t>0}\left\\{\widetilde{F}(t)-\frac{1}{t}\log\alpha\right\\},$
(210)

then

$\displaystyle\arg\min_{\theta}\widetilde{\text{EVaR}}(1-\alpha;\theta)$
$\displaystyle=\arg\min_{\theta}\widetilde{R}(\breve{t}(\alpha);\theta),$
(211) $\displaystyle\widetilde{F}(\breve{t}(\alpha))$
$\displaystyle\leq\widetilde{\text{EVaR}}(1-\alpha;\breve{\theta}(\breve{t}(\alpha))).$
(212)

##  C Solving TERM (Proofs and Details)

###  C.1 Hierarchical Multi-Objective Tilting

We state the hierarchical multi-objective tilting for a hierarchy of depth
$3.$ While we don’t directly use this form, it is stated to clarify the
experiments in Section 7 where tilting is done at class level and annotator
level, and the sample-level tilt value could be understood to be $0.$

$\displaystyle\widetilde{J}(m,t,\tau;\theta)$
$\displaystyle:=\frac{1}{m}\log\left(\frac{1}{N}\sum_{G\in[GG]}\left(\sum_{g\in[G]}|g|\right)e^{m\widetilde{J}_{G}(\tau;\theta)}\right)$
(213) $\displaystyle\widetilde{J}_{G}(t,\tau;\theta)$
$\displaystyle:=\frac{1}{t}\log\left(\frac{1}{\sum_{g\in[G]}|g|}\sum_{g\in[G]}|g|e^{t\widetilde{R}_{g}(\tau;\theta)}\right)$
(214) $\displaystyle\widetilde{R}_{g}(\tau;\theta)$
$\displaystyle:=\frac{1}{\tau}\log\left(\frac{1}{|g|}\sum_{x\in g}e^{\tau
f(x;\theta)}\right),$ (215)

##### Proof of Lemma 10.

We proceed as follows. First notice that by invoking Lemma 5,

$\displaystyle\nabla_{\theta}\widetilde{J}(t,\tau;\theta)$
$\displaystyle=\sum_{g\in[G]}w_{g}(t,\tau;\theta)\nabla_{\theta}\widetilde{R}_{g}(\tau;\theta)$
(216)

where

$w_{g}(t,\tau;\theta):=\frac{|g|e^{t\widetilde{R}_{g}(\tau;\theta)}}{\sum_{g^{\prime}\in[G]}|g^{\prime}|e^{t\widetilde{R}_{g^{\prime}}(\tau;\theta)}}.$
(217)

where $\widetilde{R}_{g}(\tau;\theta)$ is defined in (77), and is reproduced
here:

$\widetilde{R}_{g}(\tau;\theta):=\frac{1}{\tau}\log\left(\frac{1}{|g|}\sum_{x\in
g}e^{\tau f(x;\theta)}\right).$ (218)

On the other hand, by invoking Lemma 5,

$\nabla_{\theta}\widetilde{R}_{g}(\tau;\theta)=\sum_{x\in
g}w_{g,x}(\tau;\theta)\nabla_{\theta}f(x;\theta)$ (219)

where

$w_{g,x}(\tau;\theta):=\frac{e^{\tau f(x;\theta)}}{\sum_{y\in g}e^{\tau
f(y;\theta)}}.$ (220)

Hence, combining (216) and (219),

$\displaystyle\nabla_{\theta}\widetilde{J}(t,\tau;\theta)$
$\displaystyle=\sum_{g\in[G]}\sum_{x\in
g}w_{g}(t,\tau;\theta)w_{g,x}(\tau;\theta)\nabla_{\theta}f(x;\theta).$ (221)

The proof is completed by algebraic manipulations to show that

$w_{g,x}(t,\tau;\theta)=w_{g}(t,\tau;\theta)w_{g,x}(\tau;\theta).$ (222)

###  C.2 Proofs of Convergence for TERM Solvers

Initialize :
$\theta,{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{t}=\frac{1}{t}\log\left(\frac{1}{N}\sum_{i\in[N]}e^{tf(x_{i};\theta)}\right)$

Input: $t,\alpha,\lambda$

while  _stopping criteria not reached_ do

sample two independent minibatches $B_{1},B_{2}$ uniformly at random from
$[N]$

compute the loss $f(x;\theta)$ and gradient $\nabla_{\theta}f(x;\theta)$ for
all $x\in B_{1}$

$\widetilde{R}_{B,t}\leftarrow\text{$t$-tilted loss~{}\eqref{eq: TERM} on
minibatch $B_{2}$}$

${\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{t}\leftarrow\frac{1}{t}\log\left((1-\lambda)e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{t}}+\lambda
e^{t\widetilde{R}_{B,t}}\right)$

$w_{t,x}\leftarrow
e^{tf(x;\theta)-t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{t}}$

$\theta\leftarrow\theta-\frac{\alpha}{|B_{1}|}\sum_{x\in
B_{1}}w_{t,x}\nabla_{\theta}f(x;\theta)$

end while

Algorithm 5 Stochastic Non-Hierarchical TERM with two mini-batches

To prove our convergence results in Theorem 11, we first prove a lemma below.

######  Lemma 29.

Denote
$k_{t}:=\arg\max_{k}\left(k<\frac{2e}{\mu}+\frac{etLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{\mu
k}\right)$. Let $\lambda=1-\frac{1}{2e}$, and

$\displaystyle\alpha_{k}=\begin{cases}\frac{1}{tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}+1},&\text{if
}k\leq k_{t}\\\ \frac{2e}{\mu k},&\text{otherwise},\end{cases}$ (223)

then for any $k$,

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]\leq
2e,$ (224)

where
$\widetilde{R}_{k}:=\widetilde{R}(t;\theta_{k})=\frac{1}{t}\log\left(\frac{1}{N}\sum_{i\in[N]}e^{tf(x_{i};\theta_{k})}\right)$.

###### Proof.

We have the updating rule

$\displaystyle
e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}}$
$\displaystyle=\lambda
e^{tf(\xi_{k},\theta_{k})}+(1-\lambda)e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set<EMAIL_ADDRESS>(225)

Taking conditional expectation
$\mathbb{E}[\cdot|\theta_{1},\ldots,\theta_{k+1}]$ on both sides of (225)
gives

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k+1}]$
(226)
$\displaystyle=\lambda\mathbb{E}[e^{t(f(\xi_{k};\theta_{k})-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k+1}]+(1-\lambda)\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k+1}]$
(227)
$\displaystyle=\lambda+(1-\lambda)\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}].$
(228)

For any $k$, we have

$\displaystyle\|\theta_{k+1}-\theta_{k}\|=\alpha_{k}\left\|\frac{e^{t\widetilde{R}_{k}}}{e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}}}\nabla\widetilde{R}_{k}\right\|\leq\alpha_{k}e^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B.$
(229)

Therefore,

$\displaystyle|f(x_{i};\theta_{k-1})-f(x_{i};\theta_{k})|\leq
L\|\theta_{k-1}-\theta_{k}\|\leq\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})},$
(230)

and

$\displaystyle
e^{-t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\leq
e^{t(\widetilde{R}_{k}-\widetilde{R}_{k+1})}=\frac{\sum_{i\in[N]}e^{tf(x_{i};\theta_{k})}}{\sum_{i\in[N]}e^{tf(x_{i};\theta_{k+1})}}\leq
e^{t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}},$ (231)
$\displaystyle
e^{-t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k+1})}|\theta_{1},\ldots,\theta_{k+1}]$
(232)
$\displaystyle\leq\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k+1}]$
$\displaystyle\leq
e^{t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k+1})}|\theta_{1},\ldots,\theta_{k+1}].$
(233)

Hence,

$\displaystyle
e^{-t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k+1})}|\theta_{1},\ldots,\theta_{k+1}]$
(234)
$\displaystyle\leq\lambda+(1-\lambda)\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]$
(235) $\displaystyle\leq
e^{t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k+1}-\widetilde{R}_{k+1})}|\theta_{1},\ldots,\theta_{k+1}].$
(236)

(i) When $k\leq k_{t}$, we have

$\displaystyle\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}<1.$
(237)

Hence,

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]$
$\displaystyle\leq
e(\lambda+(1-\lambda)\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k-1}-\widetilde{R}_{k-1})}|\theta_{1},\ldots,\theta_{k-1}])$
(238) $\displaystyle\leq
e+\frac{1}{2}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k-1}-\widetilde{R}_{k-1})}|\theta_{1},\ldots,\theta_{k-1}]$
(239) $\displaystyle\leq\cdots\leq
e\left(2-\frac{1}{2^{k-2}}\right)+\frac{1}{2^{k-1}}\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{1}-\widetilde{R}_{1})}|\theta_{1}]\leq
2e.$ (240)

(ii) When $k>k_{t}$,

$\alpha_{k}=\frac{2e}{\mu
k}<\frac{k}{k+tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}.$ (241)

Similarly, we have

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]$
$\displaystyle\leq
e^{t\alpha_{k}LBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}\left(\lambda+(1-\lambda)\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k-1}-\widetilde{R}_{k-1})}|\theta_{1},\ldots,\theta_{k-1}]\right)$
(242) $\displaystyle\leq\cdots\leq 2e.$ (243)

∎

##### Proof of Theorem 11

Denote the empirical optimal solution $\breve{\theta}(t)$ as $\theta^{*}$.
Denote the tilted stochastic gradient on data $\zeta_{k}$ as $g_{k}$, where

$\displaystyle
g_{k}=\frac{e^{tf(\zeta_{k};\theta_{k})}}{e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}}}\nabla
f(\zeta_{k};\theta_{k})=\frac{e^{t\widetilde{R}_{k}}}{e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}}}\frac{e^{tf(\zeta_{k};\theta_{k})}}{e^{t\widetilde{R}_{k}}}\nabla
f(\zeta_{k};\theta_{k})=\frac{e^{t\widetilde{R}_{k}}}{e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}}}\nabla\widetilde{R}_{k}(\zeta_{k}).$
(244)

Therefore, for any $k\geq 1$,

$\displaystyle\mathbb{E}[\langle\theta_{k}-\theta^{*},g_{k}\rangle]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\langle\theta_{k}-\theta^{*},g_{k}\rangle|\theta_{1},\ldots,\theta_{k}]]$
(245)
$\displaystyle=\mathbb{E}[\langle\theta_{k}-\theta^{*},\mathbb{E}[g_{k}|\theta_{1},\ldots,\theta_{k}]\rangle]$
(246)
$\displaystyle=\mathbb{E}[\langle\theta_{k}-\theta^{*},\mathbb{E}[e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}|\theta_{1},\ldots,\theta_{k}]\mathbb{E}[\nabla\widetilde{R}_{k}(\zeta_{k})|\theta_{1},\ldots,\theta_{k}]\rangle]$
(247)
$\displaystyle\geq\frac{1}{2e}\mathbb{E}[\langle\theta_{k}-\theta^{*},\nabla\widetilde{R}(\theta_{k})\rangle]\quad(\mathbb{E}[e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}|\theta_{1},\ldots,\theta_{k}]\geq
1/\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}])$
(248)
$\displaystyle\geq\frac{\mu}{2e}\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]\quad(\mu\text{-strong
convexity of }\widetilde{R}),$ (249)

where (247) follows from the fact that
$e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}$
and $\nabla\widetilde{R}_{k}(\zeta_{k})$ are independent given
$\\{\theta_{1},\ldots,\theta_{k}\\}$. For $k\geq k_{t}$ with
$\alpha_{k}=\frac{2e}{\mu k}$,

$\displaystyle\mathbb{E}[\|\theta_{k+1}-\theta^{*}\|^{2}]$
$\displaystyle=\mathbb{E}[\|\theta_{k}-\alpha_{k}g_{k}-\theta^{*}\|^{2}]$
(250)
$\displaystyle=\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]-2\alpha_{k}\mathbb{E}[\langle\theta_{k}-\theta^{*},g_{k}\rangle]+\alpha_{k}^{2}\mathbb{E}[\|g_{k}\|^{2}]$
(251)
$\displaystyle\leq\left(1-\frac{\alpha_{k}\mu}{e}\right)\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]+\alpha_{k}^{2}\mathbb{E}[\|e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\|^{2}]$
(252)
$\displaystyle\leq\left(1-\frac{2}{k}\right)\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]+\frac{4e^{2}B^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{\mu^{2}k^{2}}.$
(253)

When $k\leq k_{t}$ with
$\alpha_{k}=\frac{1}{1+tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}$,

$\displaystyle\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]$
$\displaystyle\leq\left(1-\frac{\mu}{e(tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}+1)}\right)\mathbb{E}[\|\theta_{k-1}-\theta^{*}\|^{2}]+\frac{B^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{(1+tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})})^{2}}.$
(254)

We can thus prove

$\displaystyle\mathbb{E}[\|\theta_{k_{t}}-\theta^{*}\|^{2}]\leq\max\left\\{\mathbb{E}[\|\theta_{1}-\theta^{*}\|^{2}],\frac{B^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})+1}}{\mu(1+tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})})}\right\\}$
(256)

Let

$\displaystyle
V_{t}=\max\left\\{k_{t}\mathbb{E}[\|\theta_{k_{t}}-\theta^{*}\|^{2}],\frac{4B^{2}e^{2+2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{\mu^{2}}\right\\}.$
(257)

We next prove for $k\geq k_{t}$,

$\displaystyle\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]\leq\frac{V_{t}}{k}.$
(258)

Suppose $\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]\leq\frac{V_{t}}{k}$. From
(253), we have

$\displaystyle\mathbb{E}[\|\theta_{k+1}-\theta^{*}\|^{2}]$
$\displaystyle\leq\left(1-\frac{2}{k}\right)\mathbb{E}[\|\theta_{k}-\theta^{*}\|^{2}]+\frac{4e^{2}B^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{k^{2}\mu^{2}}$
(259)
$\displaystyle\leq\left(1-\frac{2}{k}\right)\frac{V_{t}}{k}+\frac{V_{t}^{2}}{k^{2}}$
(260) $\displaystyle\leq\frac{V_{t}}{k+1},$ (261)

where $k\geq k_{t}=\left\lceil\frac{e+\sqrt{e^{2}+\mu
tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}+1}}{\mu}\right\rceil$.

##### Proof of Theorem 12.

Assume $\widetilde{R}(t;\theta)$ is non-convex and $\beta$-smooth, we have

$\displaystyle\widetilde{R}_{k+1}-\widetilde{R}_{k}-\langle\nabla\widetilde{R}_{k},\theta_{k+1}-\theta_{k}\rangle\leq\frac{\beta}{2}\|\theta_{k+1}-\theta_{k}\|^{2},$
(262)

where
$\widetilde{R}_{k}:=\widetilde{R}(t;\theta_{k})=\frac{1}{t}\log\left(\frac{1}{N}\sum_{i\in[N]}e^{tf(x_{i};\theta_{k})}\right)$.
Plugging in the updating rule

$\displaystyle\theta_{k+1}-\theta_{k}=-\alpha_{k}\frac{e^{t(\zeta_{k};\theta_{k})}}{e^{t{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}}}\nabla
f(\zeta_{k};\theta_{k})=-\alpha_{k}e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})$
(263)

gives

$\displaystyle\widetilde{R}_{k+1}-\widetilde{R}_{k}+\alpha_{k}\langle\nabla\widetilde{R}_{k},e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\rangle\leq\frac{\beta}{2}\left\|\alpha_{k}e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\right\|^{2}.$
(264)

First, we note

$\displaystyle\left\|\alpha_{k}^{2}e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\right\|^{2}\leq\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}\|\nabla\widetilde{R}_{k}(\zeta_{k})\|^{2}.$
(265)

Take expectation on both sides of (264),

$\displaystyle\mathbb{E}[\widetilde{R}_{k+1}]-\mathbb{E}[\widetilde{R}_{k}]+\alpha_{k}\mathbb{E}[\langle\nabla\widetilde{R}_{k},e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\rangle]\leq\frac{\beta\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B^{2}}{2}.$
(266)

Let

$\displaystyle
k_{t}:=\left\lceil\frac{2(\widetilde{F}_{\max}-\widetilde{F}_{\min})t^{2}L^{2}}{\beta
e^{2}}\right\rceil.$ (267)

For any $k\geq k_{t}$, let

$\displaystyle\alpha_{k}=\frac{\sqrt{2(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{e^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}\sqrt{\beta
B^{2}K}}.$ (268)

For $k<k_{t}$, let

$\displaystyle\alpha_{k}=\frac{1}{tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}+1}.$
(269)

We have for any $k\geq 1$,

$\displaystyle\alpha_{k}tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}\leq
1.$ (270)

Therefore, for any $k\geq 1$,

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]\leq
2e.$ (271)

Thus, for any $k\geq 1$,

$\displaystyle\mathbb{E}[\langle\nabla\widetilde{R}_{k},e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\rangle]$
$\displaystyle=\mathbb{E}[\mathbb{E}[\langle\nabla\widetilde{R}_{k},e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})\rangle|\theta_{1},\ldots,\theta_{k}]]$
(272)
$\displaystyle=\mathbb{E}[\langle\nabla\widetilde{R}_{k},\mathbb{E}[e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}\nabla\widetilde{R}_{k}(\zeta_{k})|\theta_{1},\ldots,\theta_{k}]\rangle]$
(273)
$\displaystyle=\mathbb{E}[\langle\nabla\widetilde{R}_{k},\mathbb{E}[e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}|\theta_{1},\ldots,\theta_{k}]\mathbb{E}[\nabla\widetilde{R}_{k}(\zeta_{k})|\theta_{1},\ldots,\theta_{k}]\rangle]$
(274)
$\displaystyle=\mathbb{E}[\langle\nabla\widetilde{R}_{k},\mathbb{E}[e^{t(\widetilde{R}_{k}-{\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k})}|\theta_{1},\ldots,\theta_{k}]\nabla\widetilde{R}_{k}\rangle]$
(275)
$\displaystyle\geq\frac{1}{2e}\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}].$
(276)

Plug (276) into (266),

$\displaystyle\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}]+\frac{2e}{\alpha_{k}}(\mathbb{E}[\widetilde{R}_{k+1}]-\mathbb{E}[\widetilde{R}_{k}])\leq\beta\alpha_{k}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}eB^{2}.$
(277)

Apply telescope sum from $k_{t}+1$ to $K$ and divide both sides by $K$,

$\displaystyle\frac{1}{K}\sum_{k=k_{t}}^{K}\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}]+\frac{2e(\mathbb{E}[\widetilde{R}_{K+1}]-\mathbb{E}[\widetilde{R}_{k_{t}}])}{\alpha_{k}K}\leq\beta\alpha_{k}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}eB^{2}.$
(278)
$\displaystyle\frac{1}{K}\sum_{k=k_{t}}^{K}\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}]$
$\displaystyle\leq\beta\alpha_{k}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}eB^{2}+\frac{2e(\mathbb{E}[\widetilde{R}_{k_{t}}-\widetilde{R}_{K+1}])}{\alpha_{k}K}$
(279)
$\displaystyle\leq\beta\alpha_{k}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}eB^{2}+\frac{2e(\widetilde{F}_{\max}-\widetilde{F}_{\min})}{\alpha_{k}K}$
(280)

Consider that
$\alpha_{k}=\frac{\sqrt{2(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{e^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}\sqrt{\beta
B^{2}K}}$,

$\displaystyle\frac{1}{K}\sum_{k=k_{t}}^{K}\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}]\leq\sqrt{8}Be^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})+1}\sqrt{\frac{\beta(\widetilde{F}_{\max}-\widetilde{F}_{\min})}{K}}.$
(281)

##### Proof of Theorem 13.

From the assumptions, we have $\widetilde{R}(t;\theta)$ is $\frac{\mu}{2}$-PL,
i.e.,

$\displaystyle\mu(\widetilde{R}(t;\theta)-\widetilde{R}^{*})\leq\|\nabla\widetilde{R}(t;\theta)\|^{2},$
(282)

where $\widetilde{R}^{*}:=\widetilde{R}(t;\breve{\theta}(t))$. Let

$\displaystyle
k_{t}:=\arg\max_{k}\left(k<\frac{4e}{\mu}+\frac{4etLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}}{\mu
k}\right),$ (283)

and

$\displaystyle\alpha_{k}=\begin{cases}\frac{1}{tLBe^{t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}+1},&\text{if
}k\leq k_{t}\\\ \frac{4e}{\mu k},&\text{otherwise}.\end{cases}$ (284)

Similarly, we can prove for any $k\geq 1$,

$\displaystyle\mathbb{E}[e^{t({\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{k}-\widetilde{R}_{k})}|\theta_{1},\ldots,\theta_{k}]\leq
2e.$ (285)

Similarly,

$\displaystyle\mathbb{E}[\widetilde{R}_{k+1}]-\mathbb{E}[\widetilde{R}_{k}]+\frac{\alpha_{k}}{2e}\mathbb{E}[\|\nabla\widetilde{R}_{k}\|^{2}]\leq\frac{\beta\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B^{2}}{2}.$
(286)

Therefore,

$\displaystyle\mathbb{E}[\widetilde{R}_{k+1}]-\mathbb{E}[\widetilde{R}_{k}]+\frac{\alpha_{k}}{2e}\mu\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]$
$\displaystyle\leq\frac{\beta\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B^{2}}{2}$
(287)
$\displaystyle\mathbb{E}[\widetilde{R}_{k+1}-\widetilde{R}^{*}]-\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]+\frac{\alpha_{k}}{2e}\mu\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]$
$\displaystyle\leq\frac{\beta\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B^{2}}{2}$
(288) $\displaystyle\mathbb{E}[\widetilde{R}_{k+1}-\widetilde{R}^{*}]$
$\displaystyle\leq\left(1-\frac{\alpha_{k}}{2e}\mu\right)\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]+\frac{\beta\alpha_{k}^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})}B^{2}}{2}$
(289)

Let $\alpha_{k}=\frac{4e}{\mu k}$, and

$\displaystyle
V_{t}=\max\left\\{k_{t}\mathbb{E}[\widetilde{R}_{k_{t}}-\widetilde{R}^{*}],\frac{8\beta
B^{2}e^{2t(\widetilde{F}_{\max}-\widetilde{F}_{\min})+2}}{\mu^{2}}\right\\}.$
(290)

We next prove $\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]\leq\frac{1}{k}$
($k\geq k_{t}$) by induction. Suppose
$\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]\leq\frac{V_{t}}{k}$, then

$\displaystyle\mathbb{E}[\widetilde{R}_{k+1}-\widetilde{R}^{*}]$
$\displaystyle\leq\left(1-\frac{2}{k}\right)\mathbb{E}[\widetilde{R}_{k}-\widetilde{R}^{*}]+\frac{V_{t}}{k^{2}}$
(291)
$\displaystyle\leq\left(1-\frac{2}{k}\right)\frac{V_{t}}{k}+\frac{V_{t}}{k^{2}}$
(292) $\displaystyle\leq\frac{V_{t}}{k+1}.$ (293)

Figure 14: Convergence of Algorithm 2 using two independent mini-batches to
update
${\mathchoice{\widetilde{\hbox{\set@color$\displaystyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\textstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptstyle\widetilde{R}$}}}{\widetilde{\hbox{\set@color$\scriptscriptstyle\widetilde{R}$}}}}_{t}$
and calculate $e^{tf(x;\theta)}\nabla_{\theta}f(x;\theta)$ and a simpler
variant using only one mini-batch to query
$w_{t,x}\nabla_{\theta}f(x;\theta)$. We plot the optimality gap versus the
number of iterations on the point estimation example (Figure 1 (a)) with batch
size being 1. While Algorithm 2 allows us to get better convergence guarantees
theoretically, we find that these two variants perform similarly empirically.
Table 9: TERM Applications and their corresponding solvers.

Three toy examples (Figure 1) | Algorithm 1
---|---
Robust Regression (Table 1) | Algorithm 1
Robust Classification (Table 3) | Algorithm 2
Low-quality Annotators (Figure 9) | Algorithm 4 ($\tau=0$)
Fair PCA (Figure 10) | Algorithm 3 ($\tau=0$)
Class Imbalance (Figure 12) | Algorithm 4 ($\tau=0$)
Variance Reduction (Table 6) | Algorithm 3 ($\tau=0$)
Hierarchical TERM (Table 7) | Algorithm 3

##  D Additional Experiments and Experimental Details

In Appendix D.1, we provide complete experimental results on the properties or
the use-cases of TERM. Details on how the experiments in Section 7 were
executed are provided in Appendix D.2.

###  D.1 Complete Results

Recall that in Section 2, Interpretation 1 is that TERM can be tuned to re-
weight samples to magnify or suppress the influence of outliers. In Figure 15
below, we visually show this effect by highlighting the samples with the
largest weight for $t\to+\infty$ and $t\to-\infty$ on the logistic regression
example previously described in Figure 1.

(a) Samples with the largest weights as $t\to+\infty$.

(b) Samples with the largest weights as $t\to-\infty$.

Figure 15: For positive values of $t$, TERM focuses on the samples with
relatively large losses (rare instances). When $t\to+\infty$ (left), a few
misclassified samples have the largest weights and are highlighted. On the
other hand, for negative values of $t$, TERM suppresses the effect of the
outliers, and as $t\to-\infty$ (right), samples with the smallest losses hold
the the largest weights.

Next, we provide complete results of applying TERM to a diverse set of
applications.

##### Robust classification.

Recall that in Section 7.1, for classification in the presence of label noise,
we only compare with baselines which do not require clean validation data. In
Table 10 below, we report the complete results of comparing TERM with all
baselines, including MentorNet-DD (Jiang et al., 2018) which needs additional
clean data. In particular, in contrast to the other methods, MentorNet-DD uses
5,000 clean validation images. TERM is competitive with the performance of
MentorNet-DD, even though it does not have access to this clean data.

Table 10: A complete comparison including two MentorNet variants. TERM is able
to match the performance of MentorNet-DD, which needs additional clean labels.

objectives |  test accuracy (CIFAR-10, Inception)
---|---
20% noise | 40% noise | 80% noise
ERM | 0.775 (.004) | 0.719 (.004) | 0.284 (.004)
RandomRect (Ren et al., 2018) | 0.744 (.004) | 0.699 (.005) | 0.384 (.005)
SelfPaced (Kumar et al., 2010) | 0.784 (.004) | 0.733 (.004) | 0.272 (.004)
MentorNet-PD (Jiang et al., 2018) | 0.798 (.004) | 0.731 (.004) | 0.312 (.005)
GCE (Zhang and Sabuncu, 2018) |  0.805 (.004) | 0.750 (.004) | 0.433 (.005)
MentorNet-DD (Jiang et al., 2018) |  0.800 (.004) |  0.763 (.004) |  0.461(.005)
TERM | 0.795 (.004) | 0.768 (.004) | 0.455 (.005)
Genie ERM | 0.828 (.004) | 0.820 (.004) | 0.792 (.004)

To interpret the noise more easily, we provide a toy logistic regression
example with synthetic data here. In Figure 16, we see that TERM with $t=-2$
(blue) can converge to the correct classifier under 20%, 40%, and 80% noise.

Figure 16: Robust classification using synthetic data. On this toy problem, we
show that TERM with negative $t$’s (blue) can be robust to random noisy
samples. The green line corresponds to the solution of the generalized cross
entropy (GCE) baseline (Zhang and Sabuncu, 2018). Note that on this toy
problem, GCE is as good as TERM with negative $t$’s, despite its inferior
performance on the real-world CIFAR10 dataset. Figure 17: TERM achieves higher
test accuracy than the baselines, and can match the performance of Genie ERM
(i.e., training on all the clean data combined).

##### Low-quality annotators.

In Section 7.1.3, we demonstrate that TERM can be used to mitigate the effect
of noisy annotators, and we assume each annotator is either always correct, or
always uniformly assigning random labels. Here, we explore a different and
possibly more practical scenario where there are four noisy annotators who
corrupt 0%, 20%, 40%, and 100% of their data by assigning labels uniformly at
random, and there is one additional adversarial annotator who always assigns
wrong labels. We assume the data points labeled by each annotator do not
overlap, since (Khetan et al., 2018) show that obtaining one label per sample
is optimal for the data collectors under a fixed annotation budget. We compare
TERM with several baselines: (a) training without the data coming from the
adversarial annotator, (b) training without the data coming from the worst two
annotators, and (c) training with all the clean data combined (Genie ERM). The
results are shown in Figure 17. We see that TERM outperforms the strong
baselines of removing one or two noisy annotators, and closely matches the
performance of training with all the available clean data.

###  D.2 Experimental Details

We first describe the datasets and models used in each experiment presented in
Section 7, and then provide a detailed setup including the choices of
hyperparameters. All code and datasets are publicly available at
github.com/litian96/TERM.

####  D.2.1 Datasets and models

In Section 7.1, for regression tasks, we use the drug discovery data extracted
from Diakonikolas et al. (2019) which is originally curated from Olier et al.
(2018) and train linear regression models with different losses. There are
4,085 samples in total with each having 411 features. We randomly split the
dataset into 80% training set, 10% validation set, and 10% testing set. For
mitigating noise on classification tasks, we use the standard CIFAR-10 data
and their standard train/val/test partitions along with a standard inception
network (Szegedy et al., 2016). For experiments regarding mitigating noisy
annotators, we again use the CIFAR-10 data and their standard partitions with
a ResNet20 model. The noise generation procedure is described in Section
7.1.3.

In Section 7.2, for fair PCA experiments, we use the complete Default Credit
data to learn low-dimensional approximations and the loss is computed on the
full training set. We follow the exact data processing steps described in the
work (Samadi et al., 2018) we compare with. There are 30,000 total data points
with 21-dimensional features (after preprocessing). Among them, the high
education group has 24,629 samples and the low education group has 5,371
samples. For meta-learning experiments, one the popular sine wave regression
problem (Finn et al., 2017), we generate 5,000 meta-training and 5,000 meta-
testing tasks. Following Collins et al. (2020), there are 250 hard meta-
training tasks with amplitudes drawn from $[4.95,5]$ and 4,750 easy meta-
training tasks with amplitudes drawn from $[0.01,1]$. The amplitudes of meta-
testing tasks are drawn uniformly from $[0.1,5]$. The phase values are drawn
uniformly from $[0,\pi]$ for all tasks. For class imbalance experiments, we
directly take the unbalanced data extracted from MNIST (LeCun et al., 1998)
used in Ren et al. (2018). When demonstrating the variance reduction of TERM,
we use the HIV-1 dataset (Rögnvaldsson, 2013) as in (Duchi and Namkoong, 2019)
and randomly split it into 80% train, 10% validation, and 10% test set. There
are 6,590 total samples and each has 160 features. We report results based on
five such random partitions of the data. We train logistic regression models
(without any regularization) for this binary classification task for TERM and
the baseline methods. We also investigate the performance of a linear SVM.

In Section 7.3, the HIV-1 data are the same as that in Section 7.2. We also
manually subsample the data to make it more imbalanced, or inject random
noise, as described in Section 7.3. The CIFAR10 dataset used in this section
is a standard benchmark, and we follow the same procedures in Cao et al.
(2021) to generate a noisy and imbalanced variant.

####  D.2.2 Hyperparameters

##### Selecting $t$.

In Section 7.2 where we consider positive $t$’s, we select $t$ from a limited
candidate set of $\\{0.1,1,2,5,10,50,100,200\\}$ on the held-out validation
set. For initial robust regression experiments, RMSE changed by only 0.08 on
average across t; we thus used $t=-2$ for all experiments involving noisy
training samples (Section 7.1 and Section 7.3).

##### Other parameters.

For all experiments, we tune all other hyperparameters (the learning rates,
the regularization parameters, the decision threshold for ERM+, $\rho$ for
(Duchi and Namkoong, 2019), $\alpha$ and $\gamma$ for focal loss (Lin et al.,
2017)) based on a validation set, and select the best one. For experiments
regarding focal loss (Lin et al., 2017), we select the class balancing
parameter ($\alpha$ in the original focal loss paper) from
$\texttt{range}(0.05,0.95,0.05)$ and select the main parameter $\gamma$ from
$\\{0.5,1,2,3,4,5\\}$. We tune $\rho$ in (Duchi and Namkoong, 2019) such that
$\frac{\rho}{n}$ is selected from $\\{0.5,1,2,3,4,5,10\\}$ where $n$ is the
training set size. All regularization parameters including regularization for
linear SVM are selected from $\\{0.0001,0.01,0.1,1,2\\}$. For all experiments
on the baseline methods, we use the default hyperparameters in the original
paper (or the open-sourced code).

We summarize a complete list of main hyperparameter values as follows.

Section 7.1:

  * •

Robust regression. The threshold parameter $\delta$ for Huber loss for all
noisy levels is 1, the corruption parameter $k$ for CRR is: 500 (20% noise),
1000 (40% noise), and 3000 (80% noise); and TERM uses $t=-2$.

  * •

Robust classification. The results are all based on the default
hyperparameters provided by the open-sourced code of MentorNet (Jiang et al.,
2018), if applicable. We tune the $q$ parameter for generalized cross entropy
(GCE) from $\\{0.4,0.8,1.0\\}$ and select a best one for each noise level. For
TERM, we scale $t$ linearly as the number of iterations from 0 to -2 for all
noise levels.

  * •

Low-quality annotators. For all methods, we use the same set of
hyperparameters. The initial step-size is set to 0.1 and decayed to 0.01 at
epoch 50. The batch size is 100.

Section 7.2:

  * •

Fair PCA. We use the default hyperparameters and directly run the public code
of (Samadi et al., 2018) to get the results on the min-max fairness baseline.
We use a learning rate of 0.001 for our gradient-based solver for all target
dimensions.

  * •

Fair meta-learning. We use a fixed learning rate of 0.01 for all methods, and
tune a best learning rate for the task weights for the work of Collins et al.
(2020). Similar as Collins et al. (2020), for all methods, we run one step of
mini-batch SGD for inner optimization.

  * •

Handling class imbalance. We take the open-sourced code of LearnReweight (Ren
et al., 2018) and use the default hyperparameters for the baselines of
LearnReweight, HardMine, and ERM. We implement focal loss, and select
$\alpha=0.05,\gamma=2$.

  * •

Variance reduction. The regularization parameter for linear SVM is 1. $\gamma$
for focal loss is 2. We perform binary search on the decision thresholds for
ERM+ and RobustRegRisk+, and choose 0.26 and 0.49, respectively.

Section 7.3:

  * •

Logistic regression on HIV. We tune the $q$ parameter for GCE based on
validation data. We use $q=0,0,0.7,0.3$ respectively for the four scenarios we
consider. For RobustlyRegRisk, we use $\frac{\rho}{n}=10$ (where $n$ is the
training sample size) and we find that the performance is not sensitive to the
choice of $\rho$. For focal loss, we tune the hyperparameters for best
performance and select $\gamma=2$, $\alpha=$0.5, 0.1, 0.5, and 0.2 for four
scenarios. For HAR, we tune the regularization parameter $\lambda$ via grid
search from $\\{0.1,1,2,5,10\\}$ and select the best one. We use $t=-2$ for
TERM in the presence of noise, and tune the positive $t$’s based on validation
data. In particular, the values of tilts under four cases are: (0, 0.1), (0,
50), (-2, 5), and (-2, 10) for TERMsc and (0.1, 0), (50, 0), (1, -2) and (50,
-2) for TERMca.

  * •

ResNet32 on CIFAR10. We reproduce (and then directly take) the results from
(Cao et al., 2021) for all baseline methods. For hierarchical TERM, we scale
$t$ from 0 to 3 for group-level tilting, and scale $t$ from 0 to -2 for
sample-level tilting within each group. $\lambda$ is set to 0.2. We use the
default hyperparameters (batch size, learning rate, etc) in the open-sourced
code of HAR (Cao et al., 2021) for TERM.

## References

  * Abdelkarim et al. (2020) Sherif Abdelkarim, Panos Achlioptas, Jiaji Huang, Boyang Li, Kenneth Church, and Mohamed Elhoseiny.  Long-tail visual relationship recognition with a visiolinguistic hubless loss.  _arXiv preprint arXiv:2004.00436_ , 2020.
  * Ahmadi-Javid (2012) Amir Ahmadi-Javid.  Entropic value-at-risk: A new coherent risk measure.  _Journal of Optimization Theory and Applications_ , 2012.
  * Alghamdi et al. (2020) Wael Alghamdi, Shahab Asoodeh, Hao Wang, Flavio P Calmon, Dennis Wei, and Karthikeyan Natesan Ramamurthy.  Model projection: Theory and applications to fair machine learning.  In _IEEE International Symposium on Information Theory_ , 2020.
  * Arıkan (1996) Erdal Arıkan.  An inequality on guessing and its application to sequential decoding.  _IEEE Transactions on Information Theory_ , 1996.
  * Artzner (1997) Philippe Artzner.  Thinking coherently.  _Risk_ , 1997.
  * Artzner et al. (1999) Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath.  Coherent measures of risk.  _Mathematical Finance_ , 1999.
  * Baharlouei et al. (2020) Sina Baharlouei, Maher Nouiehed, Ahmad Beirami, and Meisam Razaviyayn.  Rényi fair inference.  _International Conference on Learning Representations_ , 2020.
  * Beirami et al. (2018) Ahmad Beirami, Robert Calderbank, Mark M Christiansen, Ken R Duffy, and Muriel Médard.  A characterization of guesswork on swiftly tilting curves.  _IEEE Transactions on Information Theory_ , 2018.
  * Bennett (1962) George Bennett.  Probability inequalities for the sum of independent random variables.  _Journal of the American Statistical Association_ , 1962.
  * Bhatia et al. (2015) Kush Bhatia, Prateek Jain, and Purushottam Kar.  Robust regression via hard thresholding.  In _Advances in Neural Information Processing Systems_ , 2015.
  * Bhatia et al. (2017) Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar.  Consistent robust regression.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Borkar (2002) Vivek S Borkar.  Q-learning for risk-sensitive control.  _Mathematics of Operations Research_ , 2002.
  * Butler (2007) Ronald W Butler.  _Saddlepoint approximations with applications_.  Cambridge University Press, 2007.
  * Calafiore and El Ghaoui (2014) Giuseppe C Calafiore and Laurent El Ghaoui.  _Optimization Models_.  Cambridge University Press, 2014.
  * Cao et al. (2021) Kaidi Cao, Yining Chen, Junwei Lu, Nikos Arechiga, Adrien Gaidon, and Tengyu Ma.  Heteroskedastic and imbalanced deep learning with adaptive regularization.  In _International Conference on Learning Representations_ , 2021.
  * Chang et al. (2017) Haw-Shiuan Chang, Erik Learned-Miller, and Andrew McCallum.  Active bias: Training more accurate neural networks by emphasizing high variance samples.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Chen and Paschalidis (2020) Ruidi Chen and Ioannis Ch Paschalidis.  Distributionally robust learning.  _Foundations and Trends® in Optimization_ , 2020.
  * Cohen and Shashua (2014) Nadav Cohen and Amnon Shashua.  Simnets: A generalization of convolutional networks.  _arXiv preprint arXiv:1410.0781_ , 2014.
  * Cohen et al. (2016) Nadav Cohen, Or Sharir, and Amnon Shashua.  Deep simnets.  In _Conference on Computer Vision and Pattern Recognition_ , 2016\.
  * Collins et al. (2020) Liam Collins, Aryan Mokhtari, and Sanjay Shakkottai.  Task-robust model-agnostic meta-learning.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Cotter et al. (2019) Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan.  Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals.  _Journal of Machine Learning Research_ , 2019.
  * Cover and Thomas (1991) Thomas M Cover and Joy A Thomas.  Information theory and statistics.  _Elements of Information Theory_ , 1991.
  * Curi et al. (2020) Sebastian Curi, Kfir Y Levy, Stefanie Jegelka, and Andreas Krause.  Adaptive sampling for stochastic risk-averse learning.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Dembo and Zeitouni (2009) A. Dembo and O. Zeitouni.  _Large deviations techniques and applications_.  Springer Science & Business Media, 2009.
  * Diakonikolas et al. (2019) Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart.  Sever: A robust meta-algorithm for stochastic optimization.  In _International Conference on Machine Learning_ , 2019.
  * Donini et al. (2018) Michele Donini, Luca Oneto, Shai Ben-David, John S Shawe-Taylor, and Massimiliano Pontil.  Empirical risk minimization under fairness constraints.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Dua and Graff (2019) D Dua and C Graff.  UCI machine learning repository [http://archive. ics. uci. edu/ml]. https://archive. ics. uci. edu/ml/datasets.  2019\.
  * Duarte and Hu (2004) Marco F Duarte and Yu Hen Hu.  Vehicle classification in distributed sensor networks.  _Journal of Parallel and Distributed Computing_ , 2004.
  * Duchi and Namkoong (2019) John Duchi and Hongseok Namkoong.  Variance-based regularization with convex objectives.  _Journal of Machine Learning Research_ , 2019.
  * Dupuis and Ellis (1997) Paul Dupuis and Richard S Ellis.  _A Weak Convergence Approach to the Theory of Large Deviations_.  1997\.
  * Fan et al. (2017) Yanbo Fan, Siwei Lyu, Yiming Ying, and Baogang Hu.  Learning with average top-k loss.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Finn et al. (2017) Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , 2017.
  * Föllmer and Knispel (2011) Hans Föllmer and Thomas Knispel.  Entropic risk measures: Coherence vs. convexity, model ambiguity and robust large deviations.  _Stochastics and Dynamics_ , 2011.
  * Gallager (1968) Robert G Gallager.  _Information theory and reliable communication_.  Springer, 1968.
  * Gao et al. (2015) Jinyang Gao, HV Jagadish, and Beng Chin Ooi.  Active sampler: Light-weight accelerator for complex data analytics at scale.  _arXiv preprint arXiv:1512.03880_ , 2015.
  * Ge et al. (2015) Rong Ge, Furong Huang, Chi Jin, and Yang Yuan.  Escaping from saddle points—online stochastic gradient for tensor decomposition.  In _Conference on Learning Theory_ , 2015.
  * Ghadimi et al. (2020) Saeed Ghadimi, Andrzej Ruszczynski, and Mengdi Wang.  A single timescale stochastic approximation method for nested stochastic optimization.  _SIAM Journal on Optimization_ , 2020.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  In _Advances in Neural Information Processing Systems_ , 2016.
  * Hashimoto et al. (2018) Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In _International Conference on Machine Learning_ , 2018.
  * Hendrycks et al. (2018) Dan Hendrycks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel.  Using trusted data to train deep networks on labels corrupted by severe noise.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Hoeffding (1994) Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In _The Collected Works of Wassily Hoeffding_. 1994.
  * Holland and Ikeda (2019) Matthew Holland and Kazushi Ikeda.  Better generalization with less data using robust gradient descent.  In _International Conference on Machine Learning_ , 2019.
  * Howard and Matheson (1972) Ronald A Howard and James E Matheson.  Risk-sensitive markov decision processes.  _Management science_ , 1972.
  * Huber (1964) Peter J Huber.  Robust estimation of a location parameter.  _The Annals of Mathematical Statistics_ , 1964.
  * Jiang et al. (2019) Angela H Jiang, Daniel L-K Wong, Giulio Zhou, David G Andersen, Jeffrey Dean, Gregory R Ganger, Gauri Joshi, Michael Kaminksy, Michael Kozuch, Zachary C Lipton, et al.  Accelerating deep learning by focusing on the biggest losers.  _arXiv preprint arXiv:1910.00762_ , 2019.
  * Jiang et al. (2018) Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei.  MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels.  In _International Conference on Machine Learning_ , 2018.
  * Jin et al. (2017) Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan.  How to escape saddle points efficiently.  In _International Conference on Machine Learning_ , 2017.
  * Jin et al. (2020) Chi Jin, Praneeth Netrapalli, and Michael Jordan.  What is local optimality in nonconvex-nonconcave minimax optimization?  In _International Conference on Machine Learning_ , 2020.
  * Jindal et al. (2016) Ishan Jindal, Matthew Nokleby, and Xuewen Chen.  Learning deep networks from noisy labels with dropout regularization.  In _International Conference on Data Mining_ , 2016.
  * Jindal et al. (2019) Ishan Jindal, Daniel Pressel, Brian Lester, and Matthew Nokleby.  An effective label noise model for dnn text classification.  In _Conference of the North American Chapter of the Association for Computational Linguistics_ , 2019.
  * Jorion (1996) Philippe Jorion.  Value at risk: a new benchmark for measuring derivatives risk.  _Irwin Professional Pub_ , 1996.
  * Kamani et al. (2019) Mohammad Mahdi Kamani, Farzin Haddadpour, Rana Forsati, and Mehrdad Mahdavi.  Efficient fair principal component analysis.  _arXiv preprint arXiv:1911.04931_ , 2019.
  * Karimi et al. (2016) Hamed Karimi, Julie Nutini, and Mark Schmidt.  Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 2016.
  * Katharopoulos and Fleuret (2017) Angelos Katharopoulos and François Fleuret.  Biased importance sampling for deep neural network training.  _arXiv preprint arXiv:1706.00043_ , 2017.
  * Khetan et al. (2018) Ashish Khetan, Zachary C Lipton, and Anima Anandkumar.  Learning from noisy singly-labeled data.  In _International Conference on Learning Representations_ , 2018.
  * Kort and Bertsekas (1972) Barry W Kort and Dimitri P Bertsekas.  A new penalty function method for constrained minimization.  In _IEEE Conference on Decision and Control and 11th Symposium on Adaptive Processes_ , 1972.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kumar et al. (2010) M Pawan Kumar, Benjamin Packer, and Daphne Koller.  Self-paced learning for latent variable models.  In _Advances in Neural Information Processing Systems_ , 2010.
  * Laguel et al. (2021) Yassine Laguel, Krishna Pillutla, Jérôme Malick, and Zaid Harchaoui.  A superquantile approach for federated learning with heterogeneous devices.  In _Annual Conference on Information Sciences and Systems_ , 2021\.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 1998.
  * Leqi et al. (2019) Liu Leqi, Adarsh Prasad, and Pradeep K Ravikumar.  On human-aligned risk minimization.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Levy et al. (2020) Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford.  Large-scale methods for distributionally robust optimization.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Li et al. (2020a) Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 2020a.
  * Li et al. (2020b) Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith.  Fair resource allocation in federated learning.  In _International Conference on Learning Representations_ , 2020b.
  * Li et al. (2021) Tian Li, Ahmad Beirami, Maziar Sanjabi, and Virginia Smith.  Tilted empirical risk minimization.  In _International Conference on Learning Representations_ , 2021.
  * Lin et al. (2017) Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In _International Conference on Computer Vision_ , 2017.
  * Lowy and Razaviyayn (2021) Andrew Lowy and Meisam Razaviyayn.  Output perturbation for differentially private convex optimization with improved population loss bounds, runtimes and applications to private adversarial training.  _arXiv preprint arXiv:2102.04704_ , 2021.
  * Malisiewicz et al. (2011) Tomasz Malisiewicz, Abhinav Gupta, and Alexei A Efros.  Ensemble of exemplar-SVMs for object detection and beyond.  In _International Conference on Computer Vision_ , 2011.
  * Mason et al. (1999) Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean.  Boosting algorithms as gradient descent.  In _Advances in Neural Information Processing Systems_ , 1999.
  * Massey (1994) James L Massey.  Guessing and entropy.  In _IEEE International Symposium on Information Theory_ , 1994.
  * Maurer and Pontil (2009) Andreas Maurer and Massimiliano Pontil.  Empirical bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * McMahan et al. (2017) H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _International Conference on Artificial Intelligence and Statistics_ , 2017.
  * Menon et al. (2020) Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar.  Can gradient clipping mitigate label noise?  In _International Conference on Learning Representations_ , 2020.
  * Merhav (2014) Neri Merhav.  List decoding—Random coding exponents and expurgated exponents.  _IEEE Transactions on Information Theory_ , 2014.
  * Mohri et al. (2019) Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh.  Agnostic federated learning.  In _International Conference on Machine Learning_ , 2019.
  * Mukhoty et al. (2019) Bhaskar Mukhoty, Govind Gopakumar, Prateek Jain, and Purushottam Kar.  Globally-convergent iteratively reweighted least squares for robust regression problems.  In _International Conference on Artificial Intelligence and Statistics_ , 2019.
  * Namkoong and Duchi (2017) Hongseok Namkoong and John C Duchi.  Variance-based regularization with convex objectives.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Nouiehed et al. (2019) Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn.  Solving a class of non-convex min-max games using iterative first order methods.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Olier et al. (2018) Ivan Olier, Noureddin Sadawi, G Richard Bickerton, Joaquin Vanschoren, Crina Grosan, Larisa Soldatova, and Ross D King.  Meta-qsar: a large-scale application of meta-learning to drug design and discovery.  _Machine Learning_ , 2018.
  * Ostrovskii et al. (2020) Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn.  Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems.  _arXiv preprint arXiv:2002.07919_ , 2020.
  * Pace and Barry (1997) R Kelley Pace and Ronald Barry.  Sparse spatial autoregressions.  _Statistics & Probability Letters_, 1997.
  * Pee and Royset (2011) EY Pee and Johannes O Royset.  On solving large-scale finite minimax problems using exponential smoothing.  _Journal of Optimization Theory and Applications_ , 2011.
  * Qi et al. (2020a) Qi Qi, Zhishuai Guo, Yi Xu, Rong Jin, and Tianbao Yang.  A practical online method for distributionally deep robust optimization.  _arXiv preprint arXiv:2006.10138_ , 2020a.
  * Qi et al. (2020b) Qi Qi, Yi Xu, Rong Jin, Wotao Yin, and Tianbao Yang.  Attentional biased stochastic gradient for imbalanced classification.  _arXiv preprint arXiv:2012.06951_ , 2020b.
  * Ren et al. (2018) Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun.  Learning to reweight examples for robust deep learning.  In _International Conference on Machine Learning_ , 2018.
  * Rezaei et al. (2020) Ashkan Rezaei, Rizal Fathony, Omid Memarrast, and Brian D Ziebart.  Fairness for robust log loss classification.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2020.
  * Rockafellar and Uryasev (2002) R Tyrrell Rockafellar and Stanislav Uryasev.  Conditional value-at-risk for general loss distributions.  _Journal of Banking & Finance_, 2002.
  * Rockafellar et al. (2000) R Tyrrell Rockafellar, Stanislav Uryasev, et al.  Optimization of conditional value-at-risk.  _Journal of risk_ , 2000.
  * Roh et al. (2020) Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh.  Fr-train: A mutual information-based approach to fair and robust training.  In _International Conference on Machine Learning_ , 2020.
  * Rögnvaldsson (2013) Thorsteinn Rögnvaldsson.  UCI repository of machine learning databases.  _https://archive.ics.uci.edu/ml/datasets/HIV-1+protease+cleavage_ , 2013.
  * Salamatian et al. (2019) Salman Salamatian, Litian Liu, Ahmad Beirami, and Muriel Médard.  Mismatched guesswork.  _arXiv preprint arXiv:1907.00531_ , 2019.
  * Samadi et al. (2018) Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstern, Mohit Singh, and Santosh Vempala.  The price of fair PCA: One extra dimension.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Shapiro et al. (2014) Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyński.  _Lectures on stochastic programming: modeling and theory_.  2014\.
  * Shen and Li (2010) Chunhua Shen and Hanxi Li.  On the dual formulation of boosting algorithms.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2010.
  * Shrivastava et al. (2016) Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick.  Training region-based object detectors with online hard example mining.  In _Conference on Computer Vision and Pattern Recognition_ , 2016\.
  * Shu et al. (2019a) Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng.  Meta-weight-net: Learning an explicit mapping for sample weighting.  In _Advances in Neural Information Processing Systems_ , 2019a.
  * Shu et al. (2019b) Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng.  Meta-weight-net: Learning an explicit mapping for sample weighting.  In _Advances in Neural Information Processing Systems_ , 2019b.
  * Siegmund (1976) David Siegmund.  Importance sampling in the monte carlo study of sequential tests.  _The Annals of Statistics_ , 1976.
  * Sinha et al. (2018) Aman Sinha, Hongseok Namkoong, and John Duchi.  Certifying some distributional robustness with principled adversarial training.  In _International Conference on Learning Representations_ , 2018.
  * Stelmakh et al. (2019) Ivan Stelmakh, Nihar B Shah, and Aarti Singh.  PeerReview4All: Fair and accurate reviewer assignment in peer review.  In _Algorithmic Learning Theory_ , 2019.
  * Sypherd et al. (2019) Tyler Sypherd, Mario Diaz, John Kevin Cava, Gautam Dasarathy, Peter Kairouz, and Lalitha Sankar.  A tunable loss function for robust classification: Calibration, landscape, and generalization.  _arXiv preprint arXiv:1906.02314_ , 2019.
  * Szabo et al. (2021) Attila Szabo, Hadi Jamali-Rad, and Siva-Datta Mannava.  Tilted cross entropy (TCE): Promoting fairness in semantic segmentation.  _arXiv preprint arXiv:2103.14051_ , 2021.
  * Szegedy et al. (2016) Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _Conference on Computer Vision and Pattern Recognition_ , 2016\.
  * Tantipongpipat et al. (2019) Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie H Morgenstern, and Santosh Vempala.  Multi-criteria dimensionality reduction with applications to fairness.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Veit et al. (2017) Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie.  Learning from noisy large-scale datasets with minimal supervision.  In _Conference on Computer Vision and Pattern Recognition_ , 2017\.
  * Volpi et al. (2018) Riccardo Volpi, Hongseok Namkoong, Ozan Sener, John C Duchi, Vittorio Murino, and Silvio Savarese.  Generalizing to unseen domains via adversarial data augmentation.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Wainwright and Jordan (2008) Martin J Wainwright and Michael I Jordan.  Graphical models, exponential families, and variational inference.  _Foundations and Trends® in Machine Learning_ , 2008\.
  * Wainwright et al. (2005) Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky.  A new class of upper bounds on the log partition function.  _IEEE Transactions on Information Theory_ , 2005.
  * Wang et al. (2016a) Mengdi Wang, Ji Liu, and Ethan Fang.  Accelerating stochastic composition optimization.  _Advances in Neural Information Processing Systems_ , 2016a.
  * Wang et al. (2017) Mengdi Wang, Ethan X Fang, and Han Liu.  Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions.  _Mathematical Programming_ , 2017.
  * Wang et al. (2013) Xueqin Wang, Yunlu Jiang, Mian Huang, and Heping Zhang.  Robust variable selection with exponential squared loss.  _Journal of the American Statistical Association_ , 2013.
  * Wang et al. (2016b) Zhiguang Wang, Tim Oates, and James Lo.  Adaptive normalized risk-averting training for deep neural networks.  In _AAAI Conference on Artificial Intelligence_ , 2016b.
  * Weyl (1912) Hermann Weyl.  Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung).  _Mathematische Annalen_ , 1912.
  * Yang et al. (2010) Min Yang, Linli Xu, Martha White, Dale Schuurmans, and Yao-liang Yu.  Relaxed clipping: A global training method for robust regression and classification.  In _Advances in Neural Information Processing Systems_ , 2010.
  * Yeh and Lien (2009) I-Cheng Yeh and Che-hui Lien.  The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.  _Expert Systems with Applications_ , 2009.
  * Yu et al. (2012) Yao-liang Yu, Özlem Aslan, and Dale Schuurmans.  A polynomial-time form of robust regression.  In _Advances in Neural Information Processing Systems_ , 2012.
  * Zafar et al. (2017) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P Gummadi.  Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment.  In _Conference on World Wide Web_ , 2017.
  * Zafar et al. (2019) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P Gummadi.  Fairness constraints: A flexible approach for fair classification.  _Journal of Machine Learning Research_ , 2019.
  * Zhang et al. (2017) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  In _International Conference on Learning Representations_ , 2017.
  * Zhang and Sabuncu (2018) Zhilu Zhang and Mert Sabuncu.  Generalized cross entropy loss for training deep neural networks with noisy labels.  In _Advances in Neural Information Processing Systems_ , 2018.
  * Zhou et al. (2021) Tianyi Zhou, Shengjie Wang, and Jeff Bilmes.  Robust curriculum learning: from clean label detection to noisy label self-correction.  In _International Conference on Learning Representations_ , 2021.