$\displaystyle=\frac{L_{f}\alpha_{k+1}^{2}}{2A_{k+1}^{2}}\lVert
u^{k+1}-u^{k}\rVert^{2}=\frac{1}{2A_{k+1}}\lVert
u^{k+1}-u^{k}\rVert^{2}\leq\frac{1}{A_{k+1}}D_{h}(u^{k+1},u^{k}).$ (6.2)

Next, we consider the remaining terms in the r.h.s. of (6.1). Substituting
$x^{k+1}$ and using $A_{k+1}=A_{k}+\alpha_{k+1}$, we obtain

$\displaystyle f(y^{k+1})$ $\displaystyle+\langle\nabla
f(y^{k+1}),x^{k+1}-y^{k+1}\rangle+r(x^{k+1})$
$\displaystyle=\left(\frac{\alpha_{k+1}}{A_{k+1}}+\frac{A_{k}}{A_{k+1}}\right)f(y^{k+1})+\langle\nabla
f(y^{k+1}),\frac{\alpha_{k+1}}{A_{k+1}}u^{k+1}+\frac{A_{k}}{A_{k+1}}x^{k}-\left(\frac{\alpha_{k+1}}{A_{k+1}}+\frac{A_{k}}{A_{k+1}}\right)y^{k+1}\rangle$
(6.3)
$\displaystyle+r\left(\frac{\alpha_{k+1}}{A_{k+1}}u^{k+1}+\frac{A_{k}}{A_{k+1}}x^{k}\right)$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),x^{k}-y^{k+1}\rangle+r(x^{k})\right)$ (6.4)
$\displaystyle+\frac{\alpha_{k+1}}{A_{k+1}}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1})\right)$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\left(f(x^{k})+r(x^{k})\right)+\frac{\alpha_{k+1}}{A_{k+1}}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1})\right)$
$\displaystyle=\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{\alpha_{k+1}}{A_{k+1}}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1})\right),$ (6.5)

where in the first inequality used the convexity of $r$, and in the second
inequality we used the convexity of $f$. Now we plug (6.1) and (6.1) into
(6.1) to obtain

$\displaystyle\Psi(x^{k+1})$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{\alpha_{k+1}}{A_{k+1}}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1})\right)+\frac{1}{A_{k+1}}D_{h}(u^{k+1},u^{k})$
$\displaystyle=\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{1}{A_{k+1}}\left[\alpha_{k+1}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1})\right)+D_{h}(u^{k+1},u^{k})\right].$
(6.6)

Given the definition of $u^{k+1}$ as a Prox-Mapping, we can apply (3.17) by
substituting $x^{+}=u^{k+1}$, $x=u^{k}$, $\gamma=\alpha_{k+1}$. In this way,
we obtain, for any $u\in\mathsf{X}$,

$\displaystyle\Psi(x^{k+1})$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{1}{A_{k+1}}\left(\alpha_{k+1}(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u^{k+1}-y^{k+1}\rangle+r(u^{k+1}))+D_{h}(u^{k+1},u^{k})\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:r}}}{{\leq}}\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{1}{A_{k+1}}\left(\alpha_{k+1}(f(y^{k+1})+\langle\nabla
f(y^{k+1}),u-y^{k+1}\rangle+r(u))+D_{h}(u,u^{k})-D_{h}(u,u^{k+1})\right)$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{\alpha_{k+1}}{A_{k+1}}(f(u)+r(u))+\frac{1}{A_{k+1}}D_{h}(u,u^{k})-\frac{1}{A_{k+1}}D_{h}(u,u^{k+1})$
$\displaystyle=\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{\alpha_{k+1}}{A_{k+1}}\Psi(u)+\frac{1}{A_{k+1}}D_{h}(u,u^{k})-\frac{1}{A_{k+1}}D_{h}(u,u^{k+1}),$
(6.7)

where we also used convexity of $f$. Multiplying both sides of the last
inequality by $A_{k+1}$, summing these inequalities from $k=0$ to $k=N-1$, and
using that $A_{N}-A_{0}=\sum_{k=0}^{N-1}\alpha_{k+1}$, we obtain

$\displaystyle A_{N}\Psi(x^{N})\leq
A_{0}\Psi(x^{0})+(A_{N}-A_{0})\Psi(u)+D_{h}(u,u^{0})-D_{h}(u,u^{N}).$ (6.8)

Since $A_{0}=0$, we can choose
$u=x^{\ast}\in\operatorname*{argmin}\\{D_{h}(u,u^{0})|u\in\mathsf{X}^{\ast}\\}\subseteq\mathsf{X}^{\ast}$
and $D_{h}(x^{\ast},u^{N})\geq 0$, so that, for all $N\geq 1$,

$\displaystyle\Psi(x^{N})-\Psi_{\min}(\mathsf{X})$
$\displaystyle\leq\frac{D_{h}(x^{\ast},u^{0})}{A_{N}},\quad
D_{h}(x^{\ast},u^{N})\leq D_{h}(x^{\ast},u^{0}).$ (6.9)

So, we see from the second inequality that the Bregman distance between the
iterates $u^{N}$ and the solution $x^{\ast}$ is non-increasing. Then, from the
inequality $D_{h}(x^{\ast},u^{N})\geq\frac{1}{2}\lVert
x^{\ast}-u^{N}\rVert^{2}$ it follows that $\|x^{\ast}-u^{N}\|$ is bounded for
any $N$, which leads to the existence of a subsequence converging to
$x^{\ast}$ by the continuity of $\Psi$. To obtain the convergence rate in
terms of the objective residual it remains to estimate the sequence $A_{N}$
from below.

We prove by induction that $A_{k}\geq\frac{(k+1)^{2}}{4L_{f}}$. For $k=1$ this
inequality holds as equality since $A_{0}=0$, and, hence,
$A_{1}=\alpha_{1}=\frac{1}{L_{f}}$. Let us prove the induction step. From the
quadratic equation $A_{k}+\alpha_{k+1}=L_{f}\alpha_{k+1}^{2}$, we have

$\displaystyle\alpha_{k+1}=\frac{1}{2L_{f}}+\sqrt{\frac{1}{4L_{f}^{2}}+\frac{A_{k}}{L_{f}}}\geq\frac{1}{2L}+\sqrt{\frac{A_{k}}{L_{f}}}\geq\frac{1}{2L_{f}}+\frac{k+1}{2L_{f}}=\frac{k+2}{2L_{f}}.$
(6.10) $\displaystyle
A_{k+1}=A_{k}+\alpha_{k+1}\geq\frac{(k+1)^{2}}{4L_{f}}+\frac{k+2}{2L_{f}}=\frac{k^{2}+2k+1+2k+4}{4L_{f}}\geq\frac{(k+2)^{2}}{4L_{f}}.$
(6.11)

Thus, combining (6.11) with (6.9), we obtain that the A-BPGM has optimal
convergence rate:

$\displaystyle\Psi(x^{N})-\Psi_{\min}(\mathsf{X})$
$\displaystyle\leq\frac{4L_{f}D_{h}(x^{\ast},u^{0})}{(N+1)^{2}}.$ (6.12)

As it was mentioned above, accelerated gradient method in the form of A-BPGM
can serve as a template meta-algorithm for many accelerated algorithms. The
examples of accelerated methods which have a close form include primal-dual
accelerated methods [174, 202, 207], random coordinate descent and other
randomized algorithms [158, 164, 154], methods for stochastic optimization
[135, 140], methods with inexact oracle [143] and inexact model of the
objective [144, 57]. Moreover, only using this one-projection version it was
possible to obtain accelerated gradient methods with inexact model of the
objective [144], accelerated decentralized distributed algorithms for
stochastic convex optimization [146], and accelerated method for stochastic
optimization with heavy-tailed noise [147]. The key to the last two results is
the proof that the sequence generated by the one-projection accelerated
gradient method is bounded with large probability, which, to our knowledge, is
not possible to prove for other types of accelerated methods applied to
stochastic optimization problems.

####  6.1.1 Linear Convergence

Under additional assumptions, we can use the scheme A-BPGM to obtain a linear
convergence rate, or, in other words, logarithmic in the desired accuracy
complexity bound. One such possible assumption is that $\Psi(x)$ satisfies a
quadratic error bound condition for some $\mu>0$:

$\Psi(x)-\Psi_{\min}(\mathsf{X})\geq\frac{\mu}{2}\|x-x^{\ast}\|^{2}.$ (6.13)

This is a weaker assumption than the assumption that $\Psi(x)$ is
$\mu$-strongly convex with $\mu>0$. For a review of different additional
conditions which allow to obtain linear convergence rate we refer the reader
to [176, 177]. The linear convergence rate can be obtained under quadratic
error bound condition by a widely used restart technique, which dates back to
[23, 178], and was extended in the past 20 years to many settings including
problems with non-quadratic error bound condition [179, 180], stochastic
optimization problems [179, 137, 138, 139, 181], methods with inexact oracle
[138, 139], randomized methods [182, 183], conditional gradient [184, 185],
variational inequalities and saddle-point problems [186, 57], methods for
constrained optimization problems [181].

To apply the restart technique, we make several additional assumptions. First,
without loss of generality, we assume that $0\in\mathsf{X}$,
$0=\arg\min_{x\in\mathsf{X}}h(x)$ and $h(0)=0$. Second, we assume that we are
given a starting point $x^{0}\in\mathsf{X}$ and a number $R_{0}>0$ such that
$\|x^{0}-x^{\ast}\|^{2}\leq R_{0}^{2}$. Finally, we make the assumption that
$h$ is bounded on the unit ball [179] in the following sense. Assume that
$x^{\ast}$ is some fixed point and $x$ is such that $\|x-x^{\ast}\|^{2}\leq
R^{2}$, then

$h\Big{(}\frac{x-x^{\ast}}{R}\Big{)}\leq\frac{\Omega}{2},$ (6.14)

where $\Omega$ is some known number. For example, in the Euclidean setup
$\Omega=1$, and other examples are given in [179, Section 2.3], where
typically $\Omega=O(\ln n)$.

The Restarted Accelerated Bregman Proximal Gradient Method (R-A-BPGM)

Input: $z^{0}\in\operatorname{dom}(r)\cap\mathsf{X}^{\circ}$ such that
$\|z^{0}-x^{\ast}\|^{2}\leq R_{0}^{2}$, $\Omega,L_{f},\mu$.

General step: For $p=0,1,\ldots$ do:

Make $N=\left\lceil 2\sqrt{\frac{\Omega L_{f}}{\mu}}\right\rceil-1$ steps of
A-BPGM with starting point $x^{0}=z^{p}$ and proximal setup given by distance-
generating function $h_{p}(x)=R_{p}^{2}h\left(\frac{x-z^{p}}{R_{p}}\right)$,
where $R_{p}:=R_{p-1}/2=R_{0}\cdot 2^{-p}$.

Set $z^{p+1}=x^{N}$.

We next use the above assumptions to show the accelerated logarithmic
complexity of R-A-BPGM, i.e. that the number of Bregman proximal steps to find
a point $\hat{x}$ such that $f(\hat{x})-f(x^{\ast})\leq\varepsilon$ is
proportional to $\sqrt{L_{f}/\mu}\log_{2}(1/\varepsilon)$ instead of
$(L_{f}/\mu)\log_{2}(1/\varepsilon)$ for the BPGM under the error bound
condition. The idea of the proof is to show by induction that, for all $p\geq
0$, $\|z^{p}-x^{\ast}\|^{2}\leq R_{p}^{2}$. For $p=0$ this holds by the
assumption on $z^{0}$ and $R_{0}$. So, next we prove an induction step from
$p-1$ to $p$. Using the definition of $h_{p-1}$, assumptions about $h$, and
the inductive assumption, we have

$D_{h_{p-1}}(x^{\ast},z^{p-1})\leq
h_{p-1}(x^{\ast})=R_{p-1}^{2}h\Big{(}\frac{z^{p-1}-x^{\ast}}{R_{p-1}}\Big{)}\stackrel{{\scriptstyle\eqref{eq:h_bounded}}}{{\leq}}\frac{\Omega
R_{p-1}^{2}}{2}.$ (6.15)

Thus, applying the error bound condition (6.13), the bound (6.12) and our
choice of the number of steps $N$, we obtain

$\displaystyle\frac{\mu}{2}\|z^{p}-x^{\ast}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:quadr_err_bound}}}{{\leq}}\Psi(z^{p})-\Psi_{\min}(\mathsf{X})=\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\stackrel{{\scriptstyle\eqref{eq:AGD_conv_rate}}}{{\leq}}\frac{L_{f}D_{h_{p-1}}(x^{\ast},z^{p-1})}{(N+1)^{2}}\stackrel{{\scriptstyle\eqref{eq:AGD_SC_Proof_1}}}{{\leq}}\frac{L_{f}\Omega
R_{p-1}^{2}}{2(N+1)^{2}}$ $\displaystyle\leq\frac{\mu
R_{p-1}^{2}}{8}=\frac{\mu R_{p}^{2}}{2}.$

So, we obtain that $\|z^{p}-x^{\ast}\|\leq R_{p}=R_{0}\cdot 2^{-p}$ and
$\Psi(z^{p})-\Psi_{\min}(\mathsf{X})\leq\frac{\mu R_{0}^{2}\cdot 2^{-2p}}{2}$.
To estimate the total number of basic steps of A-BPGM to achieve
$\Psi(z^{p})-\Psi_{\min}(\mathsf{X})\leq\varepsilon$, we need to multiply the
sufficient number of restarts $\hat{p}=\left\lceil\frac{1}{2}\log_{2}\frac{\mu
R_{0}^{2}}{2\varepsilon}\right\rceil$ by the number of A-BPGM steps $N$ in
each restart. This leads to the complexity estimate $O\left(\sqrt{\frac{\Omega
L_{f}}{\mu}}\log_{2}\frac{\mu R_{0}^{2}}{\varepsilon}\right)$ which is optimal
[58, 26] for first-order methods applied to smooth strongly convex
optimization problems.

A possible drawback of the restart scheme is that one has to know an estimate
$R_{0}$ for $\|z^{0}-x^{\ast}\|$. It is possible to avoid this by directly
incorporating the parameter $\mu$ into the steps of A-BPGM, see e.g. [187, 26,
35, 57]. Yet, in this case, a stronger assumption that $\Psi(x)$ is strongly
convex or relatively strongly convex [55] is used. The second drawback of both
approaches: restart technique and direct incorporation of $\mu$ into the
steps, is that they require to know the value of the parameter $\mu$. This is
in contrast to non-accelerated BPGM, which using the same step-size as in the
non-strongly convex case automatically has linear convergence rate and
complexity $O\left({\frac{L_{f}}{\mu}}\log_{2}\frac{\mu
R_{0}^{2}}{\varepsilon}\right)$, see e.g. [56, 57]. Several recipes on how to
restart accelerated methods with only rough estimates of the parameter $\mu$
are proposed in [183].

###  6.2 Smooth minimization of non-smooth functions

An important observation made during the last 20 years of development of
first-order methods for convex programming is that there is a large gap
between the optimal convergence rate for black-box non-smooth optimization
problems, i.e. $O(1/\sqrt{N})$ and the optimal convergence rate for black-box
smooth optimization problems, i.e. $O(1/N^{2})$. For the second observation,
let us make a thought experiment. Assume that we minimize a smooth function by
$N$ steps of A-BPGM, i.e. solve problem (P) with $r=0$. Then in each iteration
we observe first-order information $(f(y^{k+1}),\nabla f(y^{k+1}))$ and can
construct a non-smooth piecewise linear approximation of $f$ as
$g(x)=\max_{k=1,...,N}\\{f(y^{k+1})+\langle\nabla
f(y^{k+1}),x-y^{k+1}\rangle$. If we now make $N$ steps of A-BPGM with the same
starting point to minimize $g(x)$, and choose the appropriate subgradients of
$g(\cdot)$, the steps will be absolutely the same as when we minimized $f(x)$,
and we will be able to minimize a non-smooth function $g$ with much faster
rate $1/N^{2}$ than the lower bound $1/\sqrt{N}$. This leads to an idea of
trying to find a sufficiently wide class of non-smooth functions which can be
efficiently minimized by A-BPGM.

To do this, one needs to look into the black-box and use the structure of a
non-smooth problem to obtain faster convergence rates. The result is known as
_Nesterov’s smoothing technique_ [67], a powerful tool we are about to
describe now.

Consider the model problem (P), with the added assumption that the non-smooth
part admits a Fenchel representation of the form

$r(x)=\max_{w\in\mathsf{W}}\\{\langle{\mathbf{A}}x,w\rangle-\kappa(w)\\}.$
(6.16)

Here, $\mathsf{W}\subseteq\mathsf{E}$ is a compact convex subset of a finite-
dimensional real vector space $\mathsf{E}$, and
$\kappa:\mathsf{W}\to\mathbb{R}$ is a continuous convex function on
$\mathsf{W}$. ${\mathbf{A}}$ is a linear operator from $\mathsf{V}$ to
$\mathsf{E}^{\ast}$. This additional structure of the problem gives rise to a
min-max formulation of (P), given by

$\min_{x\in\mathsf{X}}\max_{w\in\mathsf{W}}\\{f(x)+\langle{\mathbf{A}}x,w\rangle-\kappa(w)\\}.$
(6.17)

The main idea of Nesterov is based on the observation that the function $r$
can be well approximated by a class of smooth convex functions, defined as
follows. Let $h_{w}\in\mathcal{H}_{1}(\mathsf{W})$ with a nonrestrictive
assumptions that $\min_{w\in\mathsf{W}}h_{w}(w)=0$, and for some $\tau>0$,
define the function

$\Psi_{\tau}(x):=f(x)+\max_{w\in\mathsf{W}}\\{\langle{\mathbf{A}}x,w\rangle-\kappa(w)-\tau
h_{w}(w)\\}.$ (6.18)

We denote by $\widehat{w}_{\tau}(x)$ the optimal solution of the maximization
problem for a fixed $x$. The main technical lemma, which leads to the main
result is as follows.

######  Proposition 6.1 ([67]).

The function $\Psi_{\tau}(x)$ is well defined, convex and continuously
differentiable at any $x\in\mathsf{X}$ with $\nabla\Psi_{\tau}(x)=\nabla
f(x)+{\mathbf{A}}^{\ast}\widehat{w}_{\tau}(x)$. Moreover,
$\nabla\Psi_{\tau}(x)$ is Lipschitz continuous with constant
$L_{\tau}=L_{f}+\frac{\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}^{2}}{\tau}$.

Here the adjoint operator ${\mathbf{A}}^{\ast}$ is defined by equality
$\langle{\mathbf{A}}x,w\rangle_{\mathsf{E}}=\langle{\mathbf{A}}^{\ast}w,x\rangle_{\mathsf{V}}$
and the norm of the operator $\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}$ is
defined by
$\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}=\max_{x,w}\\{\langle{\mathbf{A}}x,w\rangle:\|x\|_{\mathsf{V}}=1,\|w\|_{\mathsf{E}}=1\\}$.
Since $\mathsf{W}$ is bounded, $\Psi_{\tau}(x)$ is a uniform approximation for
the function $\Psi$, namely, for all $x\in\mathsf{X}$,

$\Psi_{\tau}(x)\leq\Psi(x)\leq\Psi_{\tau}(x)+\tau D_{\mathsf{W}},$ (6.19)

where $D_{\mathsf{W}}:=\max\\{h_{w}(w)|w\in\mathsf{W}\\}$, assumed to be a
finite number. Then, the idea is to choose $\tau$ sufficiently small and apply
accelerated gradient method to minimize $\Psi_{\tau}(x)$ on $\mathsf{X}$ with
a DGF $h_{x}\in\mathcal{H}_{1}(\mathsf{X})$. Doing this, and assuming that
$D_{\mathsf{X}}=\max\\{h_{x}(u)|u\in\mathsf{X}\\}<\infty$, we can apply the
result (6.12) to $\Psi_{\tau}(x)$ and, using (6.19), to obtain

$\displaystyle 0\leq\Psi(x^{N})-\Psi_{\min}(\mathsf{X})$
$\displaystyle\leq\Psi_{\tau}(x^{N})+\tau
D_{\mathsf{W}}-\Psi_{\tau}(x^{*})\leq\Psi_{\tau}(x^{N})+\tau
D_{\mathsf{W}}-\Psi_{\tau}(x_{\tau}^{*})\leq\tau
D_{\mathsf{W}}+\frac{4L_{\tau}D_{\mathsf{X}}}{(N+1)^{2}}$ $\displaystyle=\tau
D_{\mathsf{W}}+\frac{4\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}^{2}D_{\mathsf{X}}}{\tau(N+1)^{2}}+\frac{4L_{f}D_{\mathsf{X}}}{(N+1)^{2}}.$

Choosing $\tau$ to minimize the r.h.s., i.e.
$\tau=\frac{2\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}}{N+1}\sqrt{\frac{D_{\mathsf{X}}}{D_{\mathsf{W}}}}$,
we obtain

$0\leq\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\frac{4\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}\sqrt{D_{\mathsf{X}}D_{\mathsf{W}}}}{N+1}+\frac{4L_{f}D_{\mathsf{X}}}{(N+1)^{2}}.$
(6.20)

A more careful analysis in the proof of [67, Theorem 3], allows also to obtain
an approximate solution to the conjugate problem

$\max_{w\in\mathsf{W}}\\{\psi(w):=-\kappa(w)+\min_{x\in\mathsf{X}}\left(\langle{\mathbf{A}}x,w\rangle+f(x)\right)\\}.$
(6.21)

In each iteration of A-BPGM, the optimizer needs to calculate
$\nabla\Psi_{\tau}(y^{k+1})$, which requires to calculate
$\widehat{w}_{\tau}(y^{k+1})$. This information is aggregated to obtain the
vector
$\widehat{w}^{N}=\sum_{k=0}^{N-1}\frac{\alpha_{k+1}}{A_{k+1}}\widehat{w}_{\tau}(y^{k+1})$
and is used to obtain the following primal-dual result

$0\leq\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\Psi(x^{N})-\psi(\widehat{w}^{N})\leq\frac{4\|{\mathbf{A}}\|_{\mathsf{V},\mathsf{E}}\sqrt{D_{\mathsf{X}}D_{\mathsf{W}}}}{N+1}+\frac{4L_{f}D_{\mathsf{X}}}{(N+1)^{2}}.$
(6.22)

In both cases using the special structure of the problem it is possible to
obtain convergence rate $O(1/N)$ for non-smooth optimization, which is better
than the lower bound $O(1/\sqrt{N})$ for general non-smooth optimization
problems.

We illustrate the smoothing technique by two examples of piecewise-linear
minimization.

######  Example 6.1 (Uniform fit).

Consider the problem of finding a uniform fit of some signal $b\in\mathsf{E}$,
given linear observations ${\mathbf{A}}x$. where
${\mathbf{A}}:\mathsf{V}\to\mathsf{E}$ is a bounded linear operator. This
problem amount to minimize the non-smooth function
$\lVert{\mathbf{A}}x-b\rVert_{\infty}$. Of course, this problem can be
equivalently formulated as an LP, however in case where the dimensionality of
the parameter vector $x$ is large, such a direct approach could turn out to be
not very practical. Adopting the just introduced smoothing technology, the
representation (6.17) can be obtained using the definition of the dual norm
$\lVert\cdot\rVert_{1}$, i.e.
$\lVert{\mathbf{A}}x-b\rVert_{\infty}=\max_{w:\lVert w\rVert_{1}\leq
1}\langle{\mathbf{A}}x-b,w\rangle$. Yet, a better representation is obtained
using the unit simplex
$\mathsf{W}=\\{w\in\mathbb{R}^{2m}_{+}|\sum_{i=1}^{2m}w_{i}=1\\}$, matrix
$\hat{{\mathbf{A}}}=[{\mathbf{A}};-{\mathbf{A}}]$, and vector
$\hat{b}=[b;-b]$. For the set $\mathsf{W}$, a natural Bregman setup is the
norm $\lVert w\rVert_{\mathsf{E}}=\lVert w\rVert_{1}$ and the Boltzmann-
Shannon entropy $h_{w}(w)=\ln 2m+\sum_{i=1}^{m}w_{i}\ln w_{i}$. This gives

$\Psi_{\tau}(x)=\max_{w\in\mathsf{W}}\\{\langle\hat{{\mathbf{A}}}x-\hat{b},w\rangle-\tau
h_{w}(w)\\}=\tau\ln\left(\frac{1}{2m}\sum_{i=1}^{m}\exp\left(\frac{\langle
a_{i},x\rangle-b_{i}}{\tau}\right)+\exp\left(-\frac{\langle a_{i},x\rangle-
b_{i}}{\tau}\right)\right),$

which is recognized as a softmax function.

######  Example 6.2 ($\ell_{1}$-fit).

In compressed sensing [188, 189, 190] one encounters the problem to minimize
the $\ell_{1}$ norm of the residual vector ${\mathbf{A}}x-b$ over a given
closed convex set $\mathsf{X}$. While it is well-known that this problem can
in principle again be reformulated as an LP, the typical high-dimensionality
of such problems makes this direct approach often not practicable. Adopting
the smoothing technology, it is natural to choose
$\mathsf{W}=\\{w\in\mathbb{R}^{m}|\|w\|_{\infty}\leq 1\\}$ and
$h_{w}(w)=\frac{1}{2}\sum_{i=1}^{m}\|a_{i}\|_{\mathsf{E},\ast}w_{i}^{2}$,
which gives

$\Psi_{\tau}(x)=\max_{w\in\mathsf{W}}\\{\langle{{\mathbf{A}}}x-{b},w\rangle-\tau
h_{w}(w)\\}=\sum_{i=1}^{m}\|a_{i}\|_{x,\ast}\psi_{\tau}\left(\frac{|\langle
a_{i},x\rangle-b_{i}|}{\|a_{i}\|_{\mathsf{E},\ast}}\right),$

where $\psi_{\tau}(t)$ is the Huber function equal to $t^{2}/(2\tau)$ for
$0\leq t\leq\tau$ and $t-\tau/2$ if $t\geq\tau$.

For the particular case of smoothing the absolute value function $|x|$, Figure
2 gives the plot of the original function, its softmax smoothing and Huber
smoothing, both with $\tau=1$. Potentially, other ways of smoothing a non-
smooth function can be applied, see [191] for a general framework.

Figure 2: Absolute value function $|x|$, its softmax smoothing and Huber
smoothing, both with $\tau=1$.

Figure 3: Non-smooth function $f(x)=\max\\{x-1,x/2\\}$, a quadratic function
constructed using the first-order information at the point $x=2$, and a
shifted quadratic function constructed using the first-order information at
the point $x=2$. As one can see, adding a shift allows to obtain an upper
quadratic bound for the objective, which is then minimized to obtain a new
test point.

##### Closing Remarks

Let us make several remarks on the related literature. A close approach is
proposed in [192], where the problem (6.17) is considered directly as a min-
max saddle-point problem. These classes of equilibrium problems are typically
solved via tools from monotone variational inequalities, whose performance is
typically worse than the performance of optimization algorithms. In
particular, contrasting the above rate estimate with the one reported in
[192], one observes that the bound in [192] has a similar to (6.22) structure,
yet with the second term being non-accelerated, i.e. proportional to $1/N$.
This approach was generalized to obtain an accelerated method for a special
class of variational inequalities in [193], where an optimal iteration
complexity $O(L/\sqrt{\varepsilon})$ to reach an $\varepsilon$-close solution
is reported. In the original paper [67], the smoothing parameter is fixed and
requires to know the parameters of the problem in advance. This has been
improved in [194], where an adaptive version of the smoothing techniques is
proposed. This framework was extended in [195, 196, 197, 198] for structured
composite optimization problems in the form (2.7) and a related primal-dual
representation (2.8). A related line of works studies minimization of strongly
convex functions under linear constraints. Similarly to (6.18) the objective
in the Lagrange dual problem has Lipschitz gradient, yet the challenge is that
the feasible set in the dual problem is not bounded. Despite that it is
possible to obtain accelerated primal-dual methods [195, 196, 199, 200, 201,
202, 203, 204, 155, 205, 132, 206]. In particular, this allows to obtain
improved complexity bounds for different types of optimal transport problems
[202, 207, 205, 140, 208, 209, 210, 211, 212].

###  6.3 Universal Accelerated Method

As it was discussed in the previous subsection, there is a gap in the
convergence rate between the class of non-smooth convex optimization problems
and the class of smooth convex optimization problems. In this subsection, we
present a unifying framework [213] for these two classes which allows to
obtain uniformly optimal complexity bounds for both classes by a single method
without the need to know whether the objective is smooth or non-smooth. To do
that, consider the Problem (P) with $f$ which belongs to the class of
functions with Hölder-continuous subgradients, i.e. for some $L_{\nu}>0$ and
$\nu\in[0,1]$ it holds that $\lVert\nabla f(x)-\nabla f(y)\rVert_{*}\leq
L_{\nu}\lVert x-y\rVert^{\nu}$ for all $x,y\in\operatorname{dom}f$. If
$\nu=1$, we recover the $L_{f}$-smoothness condition (2.1). If $\nu=0$ we have
that $f$ has bounded variation of the subgradient, which is essentially
equivalent to the bounded subgradient Assumption 4. The main observation [142,
213] is that this Hölder condition allows to prove an inexact version of the
"descent Lemma" inequality (3.20). More precisely [213, Lemma 2], for any
$x,y\in\operatorname{dom}f$ and any $\delta>0$,

$f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L_{\nu}}{1+\nu}\lVert
y-x\rVert^{1+\nu}\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\lVert
y-x\rVert^{2}+\delta,$ (6.23)

where

$L\geq
L(\delta):=\left(\frac{1-\nu}{1+\nu}\frac{1}{\delta}\right)^{\frac{1-\nu}{1+\nu}}L_{\nu}^{\frac{2}{1+\nu}}$
(6.24)

with the convention that $0^{0}=1$. We illustrate this by Figure 3 where we
plot a quadratic bound in the r.h.s. of (6.23) with $\delta=0$ and a shifted
quadratic bound in the r.h.s. of (6.23) with some $\delta>0$. The first
quadratic bound can not be an upper bound for $f(y)$ for any $L>0$, and the
positive shift allows to construct an upper bound. Thus, it is sufficient to
equip the A-BPGM with a backtracking line-search to obtain a universal method.

The Universal Accelerated Bregman Proximal Gradient Method (U-A-BPGM)

Input: Pick $x^{0}=u^{0}=y^{0}\in\operatorname{dom}(r)\cap\mathsf{X}^{\circ}$,
$\varepsilon>0$, $0<L_{0}<L(\varepsilon/2)$, set $A_{0}=0$

General step: For $k=0,1,\ldots$ do:

Find the smallest integer $i_{k}\geq 0$ such that if one defines
$\alpha_{k+1}$ from quadratic equation
$A_{k}+\alpha_{k+1}=2^{i_{k}-1}L_{k}\alpha_{k+1}^{2}$, sets
$A_{k+1}=A_{k}+\alpha_{k+1}$,

sets $y^{k+1}=\frac{\alpha_{k+1}}{A_{k+1}}u^{k}+\frac{A_{k}}{A_{k+1}}x^{k}$,

sets
$u^{k+1}=\operatorname*{argmin}_{x\in\mathsf{X}}\left\\{\alpha_{k+1}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),x-y^{k+1}\rangle+r(x)\right)+D_{h}(x,u^{k})\right\\},$

sets $x^{k+1}=\frac{\alpha_{k+1}}{A_{k+1}}u^{k+1}+\frac{A_{k}}{A_{k+1}}x^{k}$,

then it holds that $f(x^{k+1})\leq f(y^{k+1})+\langle\nabla
f(y^{k+1}),x^{k+1}-y^{k+1}\rangle+\frac{2^{i_{k}-1}L_{k}}{2}\lVert
x^{k+1}-y^{k+1}\rVert^{2}+\frac{\varepsilon\alpha_{k+1}}{2A_{k+1}}$.

Set $L_{k+1}=2^{i_{k}-1}L_{k}$ and go to the next iterate $k$.

We first observe that for sufficiently large $i_{k}$, $2^{i_{k}-1}L_{k}\geq
L\left(\frac{\varepsilon\alpha_{k+1}}{2A_{k+1}}\right)$, see [213, p.396].
This means that the process of finding $i_{k}$ is finite since the condition
which is checked for each $i_{k}$ is essentially (6.23) with
$\delta=\frac{\varepsilon\alpha_{k+1}}{2A_{k+1}}$. Further, the convergence
proof follows the same steps as the proof of the convergence rate for A-BPGM.
The first thing which is changed is equation (6.1), where now the inexact
descent Lemma is used instead of the exact one. The only difference is that
$L_{f}$ is changed to its local approximation $L_{k+1}$ and add the error term
$\frac{\varepsilon\alpha_{k+1}}{2A_{k+1}}$ appears in the r.h.s. In (6.1) the
new quadratic equation with $L_{k+1}$ is used and the inequality remains the
same. This eventually leads to (6.1) with the only change being an additive
error term $\frac{\varepsilon\alpha_{k+1}}{2A_{k+1}}$ in the r.h.s. Finally,
this leads to the bound

$\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\frac{D_{h}(u^{\ast},u^{0})}{A_{N}}+\frac{\varepsilon}{2}.$

After some algebraic manipulation, Nesterov [213, p.397] obtains an inequality
$A_{N}\geq\frac{N^{\frac{1+3\nu}{1+\nu}}\varepsilon^{\frac{1-\nu}{1+\nu}}}{2^{\frac{2+4\nu}{1+\nu}}L_{\nu}^{\frac{2}{1+\nu}}}$.
Substituting, we obtain

$\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\frac{2^{\frac{2+4\nu}{1+\nu}}D_{h}(u^{\ast},u^{0})L_{\nu}^{\frac{2}{1+\nu}}}{N^{\frac{1+3\nu}{1+\nu}}\varepsilon^{\frac{1-\nu}{1+\nu}}}+\frac{\varepsilon}{2}.$

Since the method does not require to know $\nu$ and $L_{\nu}$, the iteration
complexity to achieve accuracy $\varepsilon$ is

$N=O\left(\inf_{\nu\in[0,1]}\left(\frac{L_{\nu}}{\varepsilon}\right)^{\frac{2}{1+3\nu}}\left(D_{h}(u^{\ast},u^{0})\right)^{\frac{1+\nu}{1+3\nu}}\right).$

It is easy to see that the oracle complexity, i.e. the number of proximal
operations, is approximately the same. Indeed, the number of oracle calls for
each $k$ is $2(i_{k}+1)$. Further, $L_{k+1}=2^{i_{k}-1}L_{k}$, which means
that the total number of the oracle calls up to iteration $N$ is
$\sum_{k=0}^{N-1}2(i_{k}+1)=\sum_{k=0}^{N-1}2(2\log_{2}\frac{L_{k+1}}{L_{k}})=4N+2\log_{2}\frac{L_{N}}{L_{0}}$,
i.e. is, up to a logarithmic term, four times larger than $N$. The obtained
oracle complexity coincides up to a constant factor with the lower bound [58]
for first-order methods applied to minimization of functions with Hölder-
continuous gradients. In the particular case $\nu=0$, we obtain the complexity
$O\left(\frac{L_{0}^{2}D_{h}(u^{\ast},u^{0})}{\varepsilon^{2}}\right)$, which
corresponds to the convergence rate $1/\sqrt{k}$, which is typical for general
non-smooth minimization. In the opposite case of smooth minimization
corresponding to $\nu=1$, we obtain the complexity
$O\left(\sqrt{\frac{L_{1}D_{h}(u^{\ast},u^{0})}{\varepsilon}}\right)$, which
corresponds to the optimal convergence rate $1/k^{2}$. The same idea can be
used to obtain universal version of the BPGM method [213]. One can also use
the strong convexity assumption to obtain faster convergence rate of the U-A-
BPGM either by restarts [180, 145], or by incorporating the strong convexity
parameter in the steps [57]. The same backtracking line-search can be applied
in a much simpler way if one knows that $f$ is $L_{f}$-smooth with some
unknown Lipschitz constant or to achieve acceleration in practice caused by a
pessimistic estimate for $L_{f}$ [54, 196, 200, 202, 214, 215, 203]. The idea
is to use standard exact "descent Lemma" inequality in each step of the
accelerated method.

The idea of universal methods turned out to be very productive and several
extensions has been proposed in the literature including universal primal-dual
method for composite optimization [216], universal primal-dual method [217]
for problems with linear constraints and problems in the form (2.7), universal
method for convex and non-convex optimization [218], a universal primal-dual
hybrid of accelerated gradient method with conjugate gradient method using
additional one-dimensional minimization [132]. Extensions are also known for
first-order methods for variational inequalities and saddle-point problems
[186]. The above-described method is not the only way to obtain adaptive and
universal methods for smooth and non-smooth optimization problems. An
alternative way which uses the norm of the current (sub)gradient to define the
step-size was initiated probably by [219] and became very popular in
stochastic optimization for machine learning after the paper [220]. On this
avenue it was possible to obtain for $\nu\in\\{0,1\\}$ universal accelerated
optimization method [221] and universal methods for variational inequalities
and saddle-point problems [222, 223].

###  6.4 Connection between Accelerated method and Conditional Gradient

In this subsection we describe how a variant of conditional gradient method
can be obtained as a particular case of A-BPGM with inexact Bregman Proximal
step. Since we consider conditional gradient method it is natural to assume
that the set $\mathsf{X}$ is bounded with
$\max_{x,u\in\mathsf{X}}D_{h}(x,u)\leq D_{\mathsf{X}}$. We follow the idea of
[45] where the main observation of is that the Prox-Mapping in A-BPGM can be
calculated inexactly by applying the generalized linear oracle given in
Definition 5.2. The idea is very similar to the idea of the conditional
gradient sliding described in Section 5.3.4 with the difference that here we
implement an approximate Bregman Proximal step using only one step of the
generalized conditional gradient method. The resulting algorithm is listed
below with the only difference with A-BPGM being the change of the Bregman
Proximal step $u^{k+1}=\mathcal{P}_{\alpha_{k+1}r}(u^{k},\alpha_{k+1}\nabla
f(y^{k+1}))$ to the step
$u^{k+1}=\mathcal{L}_{\mathsf{X},\alpha_{k+1}r}(\alpha_{k+1}\nabla
f(y^{k+1}))$ given by generalized linear oracle.

Conditional Gradient Method by A-BPGM with Approximate Bregman Proximal Step

Input: pick $x^{0}=u^{0}=y^{0}\in\operatorname{dom}(r)\cap\mathsf{X}^{\circ}$,
set $A_{0}=0$

General step: For $k=0,1,\ldots$ do:

Find $\alpha_{k+1}$ from quadratic equation
$A_{k}+\alpha_{k+1}=L_{f}\alpha_{k+1}^{2}$. Set $A_{k+1}=A_{k}+\alpha_{k+1}$.

Set $y^{k+1}=\frac{\alpha_{k+1}}{A_{k+1}}u^{k}+\frac{A_{k}}{A_{k+1}}x^{k}$.

Set (Approximate Bregman proximal step by generalized linear oracle)
$u^{k+1}=\operatorname*{argmin}_{x\in\mathsf{X}}\left\\{\alpha_{k+1}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),x-y^{k+1}\rangle+r(x)\right)\right\\}=\mathcal{L}_{\mathsf{X},\alpha_{k+1}r}(\alpha_{k+1}\nabla
f(y^{k+1}))$.

Set $x^{k+1}=\frac{\alpha_{k+1}}{A_{k+1}}u^{k+1}+\frac{A_{k}}{A_{k+1}}x^{k}$.

Since the difference between such conditional gradient method and A-BPGM is in
one simple change of the step for $u^{k+1}$, to obtain the convergence rate of
the former, it is sufficient to track, what changes such approximate Bregman
Proximal step entails in the convergence rate proof for A-BPGM. In other
words, we need to understand what happens with the proof for A-BPGM if the
Bregman Proximal step is made inexactly by applying the generalized linear
oracle. The first important difference is that we need an inexact version of
inequality (3.17), which was used in the convergence proof of A-BPGM and which
the result of the exact Bregman Proximal step. To obtain its inexact version,
let us denote

$\varphi(x)=\alpha_{k+1}\left(f(y^{k+1})+\langle\nabla
f(y^{k+1}),x-y^{k+1}\rangle+r(x)\right).$

Then generalized linear oracle actually minimizes this function on the set
$\mathsf{X}$ to obtain $u^{k+1}$. Thus, by the optimality condition, we have
that there exists $\xi\in\partial\varphi(u^{k+1})$ such that
$\langle\xi,u^{k+1}-x\rangle\leq 0$ for all $x\in\mathsf{X}$. Now we remind
that the Bregman Proximal step in A-BPGM minimizes
$\varphi(x)+D_{h}(x,u^{k})$. These observations allow to estimate the
inexactness of the Bregman Proximal step implemented via generalized linear
oracle. Indeed, for
$u^{k+1}=\mathcal{L}_{\mathsf{X},\alpha_{k+1}r}(\alpha_{k+1}\nabla
f(y^{k+1}))$

$\displaystyle\langle\xi+\nabla h(u^{k+1})-\nabla
h(u^{k}),u^{k+1}-x\rangle\leq\langle\nabla h(u^{k+1})-\nabla
h(u^{k}),u^{k+1}-x\rangle$
$\displaystyle=-D_{h}(x,u^{k})+D_{h}(x,u^{k+1})+D_{h}(u^{k+1},u^{k})\leq
2D_{\mathsf{X}},$ (6.25)

where we used three-point identity in Lemma 3.5. This inequality provides
inexact version of the optimality condition (3.15) in the problem
$\min_{x\in\mathsf{X}}\\{\varphi(x)+D_{h}(x,u^{k})\\}$, i.e. (3.18) with
$\Delta=2D_{\mathsf{X}}$. This in order leads to (3.19) with
$\Delta=2D_{\mathsf{X}}$, which is the desired inexact version of (3.17).

Let us now see, how this affects the convergence rate proof of A-BPGM.
Inequality (3.17) was used in the analysis only in (6.1). This means that the
change of (3.17) to (3.19) with $\Delta=2D_{\mathsf{X}}$ leads to an additive
term $\frac{2D_{\mathsf{X}}}{A_{k+1}}$ in the r.h.s. of (6.1):

$\displaystyle\Psi(x^{k+1})$
$\displaystyle\leq\frac{A_{k}}{A_{k+1}}\Psi(x^{k})+\frac{\alpha_{k+1}}{A_{k+1}}\Psi(u)+\frac{1}{A_{k+1}}D_{h}(u,u^{k})-\frac{1}{A_{k+1}}D_{h}(u,u^{k+1})+\frac{2D_{\mathsf{X}}}{A_{k+1}},\quad
u\in\mathsf{X}.$ (6.26)

Multiplying both sides of the last inequality by $A_{k+1}$, summing these
inequalities from $k=0$ to $k=N-1$, and using that
$A_{N}-A_{0}=\sum_{k=0}^{N-1}\alpha_{k+1}$, we obtain

$\displaystyle A_{N}\Psi(x^{N})\leq
A_{0}\Psi(x^{0})+(A_{N}-A_{0})\Psi(u)+D_{h}(u,u^{0})-D_{h}(u,u^{N})+2ND_{\mathsf{X}}.$
(6.27)

Since $A_{0}=0$, we can choose
$u=x^{\ast}\in\operatorname*{argmin}\\{D_{h}(u,u^{0})|u\in\mathsf{X}^{\ast}\\}$,
so that, for all $N\geq 1$,

$\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\frac{D_{h}(x^{\ast},u^{0})}{A_{N}}+\frac{2ND_{\mathsf{X}}}{A_{N}}\leq\frac{D_{\mathsf{X}}}{A_{N}}+\frac{2ND_{\mathsf{X}}}{A_{N}},$

which, given the lower bound $A_{N}\geq\frac{(N+1)^{2}}{4L_{f}}$ leads to the
final result for the convergence rate of this inexact A-BPGM implemented via
generalized linear oracle:

$\Psi(x^{N})-\Psi_{\min}(\mathsf{X})\leq\frac{4L_{f}D_{\mathsf{X}}}{(N+1)^{2}}+\frac{8L_{f}D_{\mathsf{X}}}{N+1}.$

Thus, we obtain a variant of conditional gradient method with the same
convergence rate $1/N$ as for the standard conditional gradient method. Using
the same approach, but with U-A-BPGM as the basis method, one can obtain a
universal version of conditional gradient method [57] for minimizing
objectives with Hölder-continuous gradient. The bounds in this case a similar
to the ones obtained in a more direct universal method in [108]. Similar
bounds were also recently obtained in [224].

##  7 Conclusion

We close this survey, with a very important fact which Nesterov writes in the
introduction of his important textbook [26]: _in general, optimization
problems are unsolvable._ Convex programming stands out from this general
fact, since it describes a significantly large class of model problems, with
important practical applications, for which general solution techniques have
been developed within the mathematical framework of interior-point techniques.
However, modern optimization problems are large-scale in nature, which renders
these polynomial time methods impractical. First-order methods have become the
gold standard in balancing cheap iterations with low solution accuracy, and
many theoretical and practical advances having been made in the last 20 years.

Despite the fact that convex optimization is approaching the state of being a
primitive similar to linear algebra techniques, we foresee that the
development of first-order methods has not come to a halt yet. In connection
with stochastic inputs, the combination of acceleration techniques with other
performance boosting tricks, like variance reduction, incremental techniques,
as well as distributed optimization, still promises to produce some new
innovations. On the other hand, there is also still much room for improvement
of algorithms for optimization problems which do not admit a prox-friendly
geometry. Distributed optimization, in particular in the context of federated
learning is now a very active area of research, see [225] for a recent review
of federated learning and [226] for a recent review of distributed
optimization. Another important focus in the research in optimization methods
is now on numerical methods for non-convex optimization motivated by training
of deep neural networks, see [227, 228] for a recent review. A number of open
questions remain in the theory of first-order methods for variational
inequalities and saddle-point problems, mainly in the case of variational
inequalities with non-monotone operators. In particular, recently the authors
of [229] observed a connection between extragradient methods for monotone
variational inequalities and accelerated first-order methods. Thus, as we
emphasize in this survey, new connections, that are still continuously being
discovered between different methods and different formulations, can lead to
new understanding and developments in this lively field of first-order
methods.

## Acknowledgements

The authors are grateful to Yu. Nesterov and A. Gasnikov for fruitful
discussions. M. Staudigl thanks the COST Action CA16228 (European Network for
Game Theory), the FMJH Program PGMO and from the support of EDF (Project
"Privacy preserving algorithms for distributed control of energy markets") for
its support.

## References

## References

  * [1] Y. Nesterov, A. Nemirovski, Interior Point Polynomial methods in Convex programming, SIAM Publications, 1994.
  * [2] E. D. Andersen, K. D. Andersen, The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm, Springer US, Boston, MA, 2000, pp. 197–232.
  * [3] J. F. Sturm, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optimization methods and software 11 (1-4) (1999) 625–653.
  * [4] P. Jain, P. Kar, Non-convex optimization for machine learning, Found. Trends Mach. Learn. 10 (3–4) (2017) 142–336.
  * [5] F. E. Curtis, K. Scheinberg, Optimization methods for supervised machine learning: From linear models to deep learning, arXiv preprint arXiv:1706.10207.
  * [6] S. J. Wright, Optimization algorithms for data analysis, The Mathematics of Data 25 (2018) 49.
  * [7] H. Robbins, S. Monro, A stochastic approximation method, The Annals of Mathematical Statistics 22 (3) (1951) 400–407.
  * [8] H. J. Kushner, Approximation and Weak Convergence Methods for Random Processes, The MIT Press, 1984.
  * [9] A. Benveniste, M. Métivier, P. Priouret, Adaptive Algorithms and Stochastic Approximations, Springer, Berlin, 1990.
  * [10] L. Ljung, G. Pflug, H. Walk, Stochastic approximation and optimization of random systems, Vol. 17, Birkhäuser, 2012.
  * [11] M. Benaïm, Recursive algorithms, urn processes, and the chaining number of chain recurrent sets, Ergodic Theory and Dynamical Systems 18 (1998) 53–87.
  * [12] P. Mertikopoulos, M. Staudigl , SIAM Journal on Optimization 28 (1) (2018) 163–197.
  * [13] P. Mertikopoulos, M. Staudigl, Stochastic mirror descent dynamics and their convergence in monotone variational inequalities, Journal of Optimization Theory and Applications 179 (3) (2018) 838–867.
  * [14] J. C. Duchi, F. Ruan, Stochastic methods for composite and weakly convex optimization problems, SIAM Journal on Optimization 28 (4) (2018) 3229–3259.
  * [15] D. Davis, D. Drusvyatskiy, S. Kakade, J. D. Lee, Stochastic subgradient method converges on tame functions, Foundations of Computational Mathematics 20 (1) (2020) 119–154.
  * [16] A. Shapiro, D. Dentcheva, A. Ruszczyński, Lectures on Stochastic Programming, Society for Industrial and Applied Mathematics, 2009.
  * [17] G. C. Pflug, A. Pichler, Multistage stochastic optimization, Springer, 2014.
  * [18] A. Beck, First-Order Methods in Optimization, Society for Industrial and Applied Mathematics, 2017.
  * [19] R. T. Rockafellar, R. J. B. Wets, Variational Analysis, Vol. 317 of A Series of Comprehensive Studies in Mathematics, Springer-Verlag, Berlin, 1998.
  * [20] S. Bubeck, Convex optimization: Algorithms and complexity, Foundations and Trends in Machine Learning 8 (3-4) (2015) 231–357.
  * [21] A. Juditsky, A. Nemirovski, First order methods for nonsmooth convex large-scale optimization, i: General purpose methods, MIT Press. Optimization for Machine Learning, 2011, Ch. 5, pp. 121–148.
  * [22] A. Juditsky, A. Nemirovski, First order methods for nonsmooth convex large-scale optimization, ii: Utilizing problems structure, MIT Press. Optimization for Machine Learning, 2011, Ch. 6, pp. 149–183.
  * [23] Y. Nesterov, A method of solving a convex programming problem with convergence rate $o(1/k^{2})$., Soviet Mathematics Doklady 27 (2) (1983) 372–376.
  * [24] J.-B. Hiriart-Urrut, C. Lemaréchal, Fundamentals of Convex Analysis, Springer, 2001.
  * [25] H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer - CMS Books in Mathematics, 2016.
  * [26] Y. Nesterov, Lectures on Convex Optimization, Vol. 137 of Springer Optimization and Its Applications, Springer International Publishing, 2018.
  * [27] P. Bühlmann, S. van de Geer, Statistics for High-Dimensional Data, Springer Series in Statistics, Springer-Verlag Berlin Heidelberg, 2011.
  * [28] I. Daubechies, M. Defrise, C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Communications on pure and applied mathematics 57 (11) (2004) 1413–1457
  * [29] A. Bruckstein, D. Donoho, M. Elad, From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review 51 (1) (2009) 34–81.
  * [30] A. Juditsky, F. KılınçKarzan, A. Nemirovski, Randomized first order algorithms with applications to $\ell_{1}$-minimization, Mathematical Programming 142 (1) (2013) 269–310.
  * [31] S. Sorin, A First-Course on Zero-Sum Repeated Games, Springer, 2000.
  * [32] P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM Journal on Control and Optimization 29 (1) (1991) 119–138.
  * [33] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, Y. Bengio, Generative adversarial nets, in: Advances in neural information processing systems, 2014, pp. 2672–2680.
  * [34] R. M. Gower, M. Schmidt, F. Bach, P. Richtárik, Variance-reduced methods for machine learning, Proceedings of the IEEE 108 (11) (2020) 1968–1983.
  * [35] G. Lan, First-order and Stochastic Optimization Methods for Machine Learning, Springer, 2020. .
  * [36] D. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
  * [37] J.-J. Moreau, Proximité et dualité dans un espace Hilbertien, Bulletin de la Société mathématique de France 93 (1965) 273–299.
  * [38] A. Beck, N. Guttmann-Beck, FOM –a Matlab toolbox of first-order methods for solving convex optimization problems, Optimization Methods and Software 34 (1) (2019) 172–193.
  * [39] P. L. Combettes, J.-C. Pesquet, Proximal splitting methods in signal processing, Springer, 2011, pp. 185–212.
  * [40] N. Parikh, S. Boyd, Proximal algorithms, Foundations and Trends® in Optimization 1 (3) (2014) 127–239
  * [41] A. Auslender, M. Teboulle, Projected subgradient methods with non-euclidean distances for non-differentiable convex minimization and variational inequalities, Mathematical Programming 120 (1) (2009) 27–48.
  * [42] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970\.
  * [43] M. Teboulle, A simplified view of first order methods for optimization, Mathematical Programming 170 (1) (2018) 67–96.
  * [44] P. L. Combettes, V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Modeling & Simulation 4 (4) (2005) 1168–1200.
  * [45] A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization (Lecture Notes), Personal web-page of A. Nemirovski, 2020.
URL https://www2.isye.gatech.edu/~nemirovs/LMCOLN2020WithSol.pdf

  * [46] A. Beck, M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters 31 (3) (2003) 167–175.
  * [47] A. Juditsky, A. V. Nazin, A. B. Tsybakov, N. Vayatis, Recursive aggregation of estimators by the mirror descent algorithm with averaging, Problems of Information Transmission 41 (4) (2005) 368–384.
  * [48] M. Doljansky, M. Teboulle, An interior proximal algorithm and the exponential multiplier method for semidefinite programming, SIAM Journal on Optimization 9 (1) (1998) 1–13.
  * [49] A. Auslender, M. Teboulle, Interior gradient and proximal methods for convex and conic optimization, SIAM Journal on Optimization 16 (3) (2006) 697–725.
  * [50] B. Cox, A. Juditsky, A. Nemirovski, Dual subgradient algorithms for large-scale nonsmooth learning problems, Mathematical Programming 148 (1) (2014) 143–180.
  * [51] M. Teboulle, Entropic proximal mappings with applications to nonlinear programming, Mathematics of Operations Research 17 (1992) 670–690.
  * [52] G. Chen, M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM Journal on Optimization 3 (3) (1993) 538–543.
  * [53] A. Beck, M. Teboulle, Gradient-based algorithms with applications to signal recovery, in: D. P. Palomar, Y. C. Eldar (Eds.), Convex optimization in signal processing and communications, Cambridge University Press, 2009, pp. 42–88.
  * [54] Y. Nesterov, Gradient methods for minimizing composite functions, Mathematical Programming 140 (1) (2013) 125–161
  * [55] H. Lu, R. Freund, Y. Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM Journal on Optimization 28 (1) (2018) 333–354.
  * [56] F. S. Stonyakin, D. Dvinskikh, P. Dvurechensky, A. Kroshnin, O. Kuznetsova, A. Agafonov, A. Gasnikov, A. Tyurin, C. A. Uribe, D. Pasechnyuk, S. Artamonov, Gradient methods for problems with inexact model of the objective, in: M. Khachay, Y. Kochetov, P. Pardalos (Eds.), Mathematical Optimization Theory and Operations Research, Springer International Publishing, Cham, 2019, pp. 97–114, arXiv:1902.09001.
  * [57] F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, D. Pasechnyuk, S. Artamonov, V. Piskunova, Inexact relative smoothness and strong convexity for optimization and variational inequalities by inexact model, arXiv:2001.09013. WIAS Preprint No. 2709.
  * [58] A. S. Nemirovski, D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley, New York, NY, 1983.
  * [59] J. Duchi, S. Shalev-Shwartz, Y. Singer, A. Tewari, Composite objective mirror descent, in: COLT 2010 - The 23rd Conference on Learning Theory, 2010, pp. 14–26.
  * [60] P. E. Dvurechensky, A. V. Gasnikov, E. A. Nurminski, F. S. Stonyakin, Advances in Low-Memory Subgradient Optimization, Springer International Publishing, Cham, 2020, pp. 19–59, arXiv:1902.01572.
  * [61] H. H. Bauschke, J. Bolte, M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Mathematics of Operations Research 42 (2) (2016) 330–348.
  * [62] S. Boyd, L. Vandenberghe, Convex optimization, Cambridge university press, 2004\.
  * [63] M. J. Todd, Minimum-Volume Ellipsoids, Society for Industrial and Applied Mathematics, 2016.
  * [64] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bulletin of the American Mathematical Society 73 (4) (1967) 591–597.
  * [65] Y. Nesterov, Primal-dual subgradient methods for convex problems, Mathematical Programming 120 (1) (2009) 221–259.
  * [66] L. Xiao, Dual averaging methods for regularized stochastic learning and online optimization, Journal of Machine Learning Research 11 (Oct) (2010) 2543–2596.
  * [67] Y. Nesterov, Smooth minimization of non-smooth functions, Mathematical Programming 103 (1) (2005) 127–152.
  * [68] U. Helmke, J. B. Moore, Optimization and Dynamical Systems, Communications & Control Engineering, Springer Berlin Heidelberg, 1996.
  * [69] F. Alvarez, J. Bolte, O. Brahic, Hessian Riemannian gradient flows in convex programming, SIAM Journal on Control and Optimization 43 (2) (2004) 477–501.
  * [70] H. Attouch, J. Bolte, P. Redont, M. Teboulle, Singular Riemannian barrier methods and gradient-projection dynamical systems for constrained optimization, Optimization 53 (5-6) (2004) 435–454.
  * [71] H. Attouch, M. Teboulle, Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization, Journal of Optimization Theory and Applications 121 (3) (2004) 541–570.
  * [72] J. Bolte, M. Teboulle, Barrier operators and associated gradient-like dynamical systems for constrained minimization problems, SIAM Journal on Control and Optimization 42 (4) (2003) 1266–1292.
  * [73] I. M. Bomze, P. Mertikopoulos, W. Schachinger, M. Staudigl, Hessian barrier algorithms for linearly constrained optimization problems, SIAM Journal on Optimization 29 (3) (2019) 2100–2127.
  * [74] B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics 4 (5) (1964) 1–17.
  * [75] W. Su, S. Boyd, E. J. Candes, A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights, Journal of Machine Learning Research 17 (153) (2016), 1-43
  * [76] A. Wibisono, A. C. Wilson, M. I. Jordan, A variational perspective on accelerated methods in optimization, Proceedings of the National Academy of Sciences 113 (47) (2016) E7351.
  * [77] H. Attouch, Z. Chbani, J. Peypouquet, P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Mathematical Programming 168 (1-2) (2018) 123–175.
  * [78] B. Bah, H. Rauhut, U. Terstiege, M. Westdickenberg, Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers, arXiv preprint arXiv:1910.05505.
  * [79] B. Shi, S. S. Du, W. Su, M. I. Jordan, Acceleration via symplectic discretization of high-resolution differential equations, Advances in Neural Information Processing Systems (2019) 5744–5752.
  * [80] H. Attouch, Z. Chbani, J. Fadili, H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, Mathematical Programming (2020)
  * [81] H. Attouch, P. Redont, A. Soubeyran, A new class of alternating proximal minimization algorithms with costs-to-move, SIAM Journal on Optimization 18 (3) (2007) 1061–1081.
  * [82] H. Attouch, A. Cabot, P. Frankel, J. Peypouquet, Alternating proximal algorithms for linearly constrained variational inequalities: application to domain decomposition for PDE’s, Nonlinear Analysis: Theory, Methods & Applications 74 (18) (2011) 7455–7473.
  * [83] M. J. Feizollahi, S. Ahmed, A. Sun, Exact augmented Lagrangian duality for mixed integer linear programming, Mathematical Programming 161 (1) (2017) 365–387.
  * [84] F. Lin, M. Fardad, M. R. Jovanović, Sparse feedback synthesis via the alternating direction method of multipliers, 2012 American Control Conference (ACC), Montreal, QC, 2012, pp. 4765–4770.
  * [85] X. Yuan, Alternating direction method for covariance selection models, Journal of Scientific Computing 51 (2) (2012) 261–273.
  * [86] J. Yang, Y. Zhang, Alternating direction algorithms for $\backslash$ell_1-problems in compressive sensing, SIAM journal on scientific computing 33 (1) (2011) 250–278.
  * [87] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine learning 3 (1) (2011) 1–122.
  * [88] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM journal on control and optimization 14 (5) (1976) 877–898.
  * [89] R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of operations research 1 (2) (1976) 97–116.
  * [90] R. Shefi, M. Teboulle, Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM Journal on Optimization 24 (1) (2014) 269–297.
  * [91] S. Banert, R. I. Bot, E. R. Csetnek, Fixing and extending some recent results on the ADMM algorithm, arXiv preprint arXiv:1612.05057.
  * [92] A. X. Sun, D. T. Phan, S. Ghosh, Fully decentralized AC optimal power flow algorithms, in: 2013 IEEE Power & Energy Society General Meeting, IEEE, 2013, pp. 1–5.
  * [93] A. Auslender, M. Teboulle, Asymptotic cones and functions in optimization and variational inequalities, Springer Science & Business Media, 2006.
  * [94] D. Gabay, Applications of the method of multipliers to variational inequalities, Vol. 15, Elsevier, 1983, Ch. ix, pp. 299–331.
  * [95] J. Eckstein, D. P. Bertsekas, On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming 55 (1-3) (1992) 293–318.
  * [96] C. Chen, B. He, Y. Ye, X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Mathematical Programming 155 (1-2) (2016) 57–79.
  * [97] A. Chambolle, T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision 40 (1) (2011) 120–145.
  * [98] K. Arrow, L. Hurwicz, H. Uzawa, Studies in linear and non-linear programming., in: H. Chenery, S. Johnson, S. Karlin, T. Marschak, R. Solow (Eds.), Stanford Mathematical Studies in the Social Sciences, vol. II., Stanford University Press, Stanford, 1958.
  * [99] M. Frank, P. Wolfe, et al., An algorithm for quadratic programming, Naval research logistics quarterly 3 (1-2) (1956) 95–110.
  * [100] E. S. Levitin, B. T. Polyak, Constrained minimization methods, USSR Computational mathematics and mathematical physics 6 (5) (1966) 1–50.
  * [101] J. Kuczyński, H. Woźniakowski, Estimating the largest eigenvalue by the power and lanczos algorithms with a random start, SIAM Journal on Matrix Analysis and Applications 13 (4) (1992) 1094–1122.
  * [102] F. Facchinei, J.-s. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems - Volume I and Volume II, Springer Series in Operations Research, 2003.
  * [103] M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization., in: International Conference on Machine Learning, 2013, pp. 427–435.
  * [104] W. Bian, X. Chen, Linearly constrained non-Lipschitz optimization for image restoration, SIAM Journal on Imaging Sciences 8 (4) (2015) 2294–2322.
  * [105] W. Bian, X. Chen, Y. Ye, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization, Mathematical Programming 149 (1) (2015) 301–327.
  * [106] G. Haeser, H. Liu, Y. Ye, Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary , Mathematical Programming 178 (2019), 263–299
  * [107] F. Bach, Duality between subgradient and conditional gradient methods, SIAM Journal on Optimization 25 (1) (2015) 115–129.
  * [108] Y. Nesterov, Complexity bounds for primal-dual methods minimizing the model of objective function, Mathematical Programming 171 (1-2) (2018) 311–330.
  * [109] Y. Nesterov, Dual extrapolation and its applications to solving variational inequalities and related problems, Mathematical Programming 109 (2) (2007) 319–344.
  * [110] J. C. Dunn, Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals, SIAM Journal on Control and Optimization 17 (2) (1979) 187–211.
  * [111] F. Pedregosa, G. Negiar, A. Askari, M. Jaggi, Linearly convergent Frank-Wolfe with backtracking line-search, in: International Conference on Artificial Intelligence and Statistics, PMLR, 2020, pp. 1–10.
  * [112] P. Dvurechensky, P. Ostroukhov, K. Safin, S. Shtern, M. Staudigl, Self-concordant analysis of frank-Wolfe algorithms, in: H. D. III, A. Singh (Eds.), Proceedings of the 37th International Conference on Machine Learning, Vol. 119 of Proceedings of Machine Learning Research, PMLR, Virtual, 2020, pp. 2814–2824.
  * [113] P. Dvurechensky, K. Safin, S. Shtern, M. Staudigl, Generalized self-concordant analysis of Frank-Wolfe algorithms, arXiv:2010.01009.
  * [114] R. M. Freund, P. Grigas, New analysis and results for the Frank–Wolfe method, Mathematical Programming 155 (1-2) (2016) 199–230.
  * [115] G. Odor, Y.-H. Li, A. Yurtsever, Y.-P. Hsieh, Q. Tran-Dinh, M. El Halabi, V. Cevher, Frank-Wolfe works for non-Lipschitz continuous gradient objectives: scalable poisson phase retrieval, in: 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Ieee, 2016, pp. 6230–6234.
  * [116] M. D. Canon, C. D. Cullum, A tight upper bound on the rate of convergence of Frank-Wolfe algorithm, SIAM Journal on Control 6 (4) (1968) 509–516.
  * [117] G. Lan, The complexity of large-scale convex programming under a linear optimization oracle, arXiv preprint arXiv:1309.5550.
  * [118] D. Garber, E. Hazan, Faster rates for the Frank-Wolfe method over strongly-convex sets, in: 32nd International Conference on Machine Learning, ICML 2015, 2015.
  * [119] J. Guélat, P. Marcotte, Some comments on Wolfe’s ‘away step’, Mathematical Programming 35 (1) (1986) 110–119.
  * [120] M. Epelman, R. M. Freund, Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system, Mathematical Programming 88 (3) (2000) 451–485.
  * [121] A. Beck, M. Teboulle, A conditional gradient method with linear rate of convergence for solving convex linear systems, Mathematical Methods of Operations Research 59 (2) (2004) 235–247.
  * [122] P. Wolfe, Convergence theory in nonlinear programming, in: J. Abadie (Ed.), Integer and nonlinear programming, North-Holland, Amsterdam, 1970.
  * [123] S. Lacoste-Julien, M. Jaggi, On the global linear convergence of Frank-Wolfe optimization variants, Advances in neural information processing systems 28 (2015) 496–504.
  * [124] A. Beck, S. Shtern, Linearly convergent away-step conditional gradient for non-strongly convex functions, Mathematical Programming 164 (1-2) (2017) 1–27.
  * [125] S. M. Robinson, Generalized equations and their solutions, part ii: applications to nonlinear programming, in: Optimality and Stability in Mathematical Programming, Springer, 1982, pp. 200–221.
  * [126] S. Damla Ahipasaoglu, P. Sun, M. J. Todd, Linear convergence of a modified frank–wolfe algorithm for computing minimum-volume enclosing ellipsoids, Optimisation Methods and Software 23 (1) (2008) 5–19.
  * [127] C. A. Holloway, An extension of the Frank and Wolfe method of feasible directions, Mathematical Programming 6 (1) (1974) 14–27.
  * [128] B. Von Hohenbalken, Simplicial decomposition in nonlinear programming algorithms, Mathematical Programming 13 (1) (1977) 49–68.
  * [129] D. Garber, E. Hazan, A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization, SIAM Journal on Optimization 26 (3) (2016) 1493–1528.
  * [130] G. Lan, Y. Zhou, Conditional gradient sliding for convex optimization, SIAM Journal on Optimization 26 (2) (2016) 1379–1409.
  * [131] A. Nemirovski, Orth-method for smooth convex optimization, Izvestia AN SSSR, Transl.: Eng. Cybern. Soviet J. Comput. Syst. Sci 2 (1982) 937–947.
  * [132] Y. Nesterov, A. Gasnikov, S. Guminov, P. Dvurechensky, Primal-dual accelerated gradient methods with small-dimensional relaxation oracle, Optimization Methods and Software (2020) 1–28
  * [133] A. Beck, M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences 2 (1) (2009) 183–202.
  * [134] O. Devolder, Stochastic first order methods in smooth convex optimization, CORE Discussion Paper 2011/70.
  * [135] G. Lan, An optimal method for stochastic composite optimization, Mathematical Programming 133 (1) (2012) 365–397
  * [136] S. Ghadimi, G. Lan, Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework, SIAM Journal on Optimization 22 (4) (2012) 1469–1492.
  * [137] S. Ghadimi, G. Lan, Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, ii: Shrinking procedures and optimal algorithms, SIAM Journal on Optimization 23 (4) (2013) 2061–2089.
  * [138] P. Dvurechensky, A. Gasnikov, Stochastic intermediate gradient method for convex problems with stochastic inexact oracle, Journal of Optimization Theory and Applications 171 (1) (2016) 121–145.
  * [139] A. V. Gasnikov, P. E. Dvurechensky, Stochastic intermediate gradient method for convex optimization problems, Doklady Mathematics 93 (2) (2016) 148–151.
  * [140] P. Dvurechensky, D. Dvinskikh, A. Gasnikov, C. A. Uribe, A. Nedić, Decentralize and randomize: Faster algorithm for Wasserstein barycenters, in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems 31, NeurIPS 2018, Curran Associates, Inc., 2018, pp. 10783–10793.
  * [141] A. d’Aspremont, Smooth optimization with approximate gradient, SIAM J. on Optimization 19 (3) (2008) 1171–1183.
  * [142] O. Devolder, F. Glineur, Y. Nesterov, First-order methods of smooth convex optimization with inexact oracle, Mathematical Programming 146 (1) (2014) 37–75.
  * [143] M. Cohen, J. Diakonikolas, L. Orecchia, On acceleration with noise-corrupted gradients, in: J. Dy, A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, PMLR, Stockholmsmässan, Stockholm Sweden, 2018, pp. 1019–1028, arXiv:1805.12591.
  * [144] A. V. Gasnikov, A. I. Tyurin, Fast gradient descent for convex minimization problems with an oracle producing a ($\delta$, L)-model of function at the requested point, Computational Mathematics and Mathematical Physics 59 (7) (2019) 1085–1097.
  * [145] D. Kamzolov, P. Dvurechensky, A. V. Gasnikov, Universal intermediate gradient method for convex problems with inexact oracle, Optimization Methods and Software (2020) 1–28, arXiv:1712.06036.
URL https://doi.org/10.1080/10556788.2019.1711079

  * [146] E. Gorbunov, D. Dvinskikh, A. Gasnikov, Optimal decentralized distributed algorithms for stochastic convex optimization, arXiv:1911.07363.
  * [147] E. Gorbunov, M. Danilova, A. Gasnikov, Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping, in: Proceedings of the 33rd International Conference on Neural Information Processing Systems, NeurIPS 2020, 2020.
  * [148] R. Frostig, R. Ge, S. Kakade, A. Sidford, Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization, in: F. Bach, D. Blei (Eds.), Proceedings of the 32nd International Conference on Machine Learning, Vol. 37 of Proceedings of Machine Learning Research, PMLR, Lille, France, 2015, pp. 2540–2548.
  * [149] H. Lin, J. Mairal, Z. Harchaoui, A universal catalyst for first-order optimization, in: Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS’15, MIT Press, Cambridge, MA, USA, 2015, pp. 3384–3392.
  * [150] Y. Zhang, L. Xiao, Stochastic primal-dual coordinate method for regularized empirical risk minimization, in: F. Bach, D. Blei (Eds.), Proceedings of the 32nd International Conference on Machine Learning, Vol. 37 of Proceedings of Machine Learning Research, PMLR, Lille, France, 2015, pp. 353–361.
  * [151] Z. Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, ACM, New York, NY, USA, 2017, pp. 1200–1205, arXiv:1603.05953.
  * [152] G. Lan, Y. Zhou, An optimal randomized incremental gradient method, Mathematical Programming 171 (2018), 167-215
  * [153] A. Ivanova, A. Gasnikov, P. Dvurechensky, D. Dvinskikh, A. Tyurin, E. Vorontsova, D. Pasechnyuk, Oracle complexity separation in convex optimization, arXiv:2002.02706 WIAS Preprint No. 2711.
  * [154] J. Diakonikolas, L. Orecchia, Alternating randomized block coordinate descent, in: J. Dy, A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, PMLR, Stockholmsmässan, Stockholm Sweden, 2018, pp. 1224–1232.
  * [155] S. Guminov, P. Dvurechensky, N. Tupitsa, A. Gasnikov, Accelerated alternating minimization, accelerated Sinkhorn’s algorithm and accelerated Iterative Bregman Projections, arXiv:1906.03622 WIAS Preprint No. 2695.
  * [156] Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM Journal on Optimization 22 (2) (2012) 341–362.
  * [157] Y. T. Lee, A. Sidford, Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems, in: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS ’13, IEEE Computer Society, Washington, DC, USA, 2013, pp. 147–156.
  * [158] O. Fercoq, P. Richtárik, Accelerated, parallel, and proximal coordinate descent, SIAM Journal on Optimization 25 (4) (2015) 1997–2023.
  * [159] Q. Lin, Z. Lu, L. Xiao, An accelerated proximal coordinate gradient method, in: Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 27, Curran Associates, Inc., 2014, pp. 3059–3067, first appeared in arXiv:1407.1296.
  * [160] Y. Nesterov, S. U. Stich, Efficiency of the accelerated coordinate descent method on structured optimization problems, SIAM Journal on Optimization 27 (1) (2017) 110–123, first presented in May 2015 http://www.mathnet.ru:8080/PresentFiles/11909/7_nesterov.pdf.
  * [161] A. Gasnikov, P. Dvurechensky, I. Usmanova, On accelerated randomized methods, Proceedings of Moscow Institute of Physics and Technology 8 (2) (2016) 67–100, in Russian, first appeared in arXiv:1508.02182.
  * [162] Z. Allen-Zhu, Z. Qu, P. Richtarik, Y. Yuan, Even faster accelerated coordinate descent using non-uniform sampling, in: M. F. Balcan, K. Q. Weinberger (Eds.), Proceedings of The 33rd International Conference on Machine Learning, Vol. 48 of Proceedings of Machine Learning Research, PMLR, New York, New York, USA, 2016, pp. 1110–1119.
  * [163] S. Shalev-Shwartz, T. Zhang, Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization, in: E. P. Xing, T. Jebara (Eds.), Proceedings of the 31st International Conference on Machine Learning, Vol. 32 of Proceedings of Machine Learning Research, PMLR, Bejing, China, 2014, pp. 64–72, first appeared in arXiv:1309.2375.
  * [164] P. Dvurechensky, A. Gasnikov, A. Tiurin, Randomized similar triangles method: A unifying framework for accelerated randomized optimization methods (coordinate descent, directional search, derivative-free method), arXiv:1707.08486.
  * [165] Y. Nesterov, V. Spokoiny, Random gradient-free minimization of convex functions, Found. Comput. Math. 17 (2) (2017) 527–566,
  * [166] E. Gorbunov, P. Dvurechensky, A. Gasnikov, An accelerated method for derivative-free smooth stochastic convex optimization, arXiv:1802.09022.
  * [167] E. A. Vorontsova, A. V. Gasnikov, E. A. Gorbunov, P. E. Dvurechenskii, Accelerated gradient-free optimization methods with a non-euclidean proximal operator, Automation and Remote Control 80 (8) (2019) 1487–1501.
  * [168] E. A. Vorontsova, A. V. Gasnikov, E. A. Gorbunov, Accelerated directional search with non-euclidean prox-structure, Automation and Remote Control 80 (4) (2019) 693–707.
  * [169] P. Dvurechensky, E. Gorbunov, A. Gasnikov, An accelerated directional derivative method for smooth stochastic convex optimization, European Journal of Operational Research 290 (2) (2021) 601–621
  * [170] Y. Nesterov, Accelerating the cubic regularization of newton’s method on convex problems, Mathematical Programming 112 (1) (2008) 159–181.
  * [171] M. Baes, Estimate sequence methods: extensions and approximations, Institute for Operations Research, ETH, Zürich, Switzerland.
  * [172] Y. Nesterov, Implementable tensor methods in unconstrained convex optimization, Mathematical Programming (2019)
  * [173] A. Gasnikov, P. Dvurechensky, E. Gorbunov, E. Vorontsova, D. Selikhanovych, C. A. Uribe, B. Jiang, H. Wang, S. Zhang, S. Bubeck, Q. Jiang, Y. T. Lee, Y. Li, A. Sidford, Near optimal methods for minimizing convex functions with Lipschitz $p$-th derivatives, in: A. Beygelzimer, D. Hsu (Eds.), Proceedings of the Thirty-Second Conference on Learning Theory, Vol. 99 of Proceedings of Machine Learning Research, PMLR, Phoenix, USA, 2019, pp. 1392–1393, arXiv:1809.00382.
  * [174] P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, Tech. rep., MIT (2008).
URL http://www.mit.edu/~dimitrib/PTseng/papers/apgm.pdf

  * [175] A. Gasnikov, Yu. Nesterov, Universal method for stochastic composite optimization problems, Computational Mathematics and Mathematical Physics 58 (1) (2018) 48–64.
  * [176] I. Necoara, Y. Nesterov, F. Glineur, Linear convergence of first order methods for non-strongly convex optimization, Mathematical Programming 175 (1) (2019) 69–107.
  * [177] J. Bolte, T. P. Nguyen, J. Peypouquet, B. W. Suter, From error bounds to the complexity of first-order descent methods for convex functions, Mathematical Programming 165 (2) (2017) 471–507.
  * [178] A. Nemirovskii, Y. Nesterov, Optimal methods of smooth convex minimization, USSR Computational Mathematics and Mathematical Physics 25 (2) (1985) 21 – 30.
  * [179] A. Juditsky, Y. Nesterov, Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization, Stochastic Systems 4 (1) (2014) 44–80.
  * [180] V. Roulet, A. d’Aspremont, Sharpness, restart and acceleration, in: I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (Eds.), Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017, pp. 1119–1129.
  * [181] A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov, Mirror descent and convex optimization problems with non-smooth inequality constraints, in: P. Giselsson, A. Rantzer (Eds.), Large-Scale and Distributed Optimization, Springer International Publishing, 2018, Ch. 8, pp. 181–215, arXiv:1710.06612.
  * [182] Z. Allen-Zhu, E. Hazan, Optimal black-box reductions between optimization objectives, in: D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, R. Garnett (Eds.), Advances in Neural Information Processing Systems, Vol. 29, Curran Associates, Inc., 2016, pp. 1614–1622.
  * [183] O. Fercoq, Z. Qu, Restarting the accelerated coordinate descent method with a rough strong convexity estimate, Computational Optimization and Applications 75 (1) (2020) 63–91.
  * [184] G. Lan, The complexity of large-scale convex programming under a linear optimization oracle, arXiv:1309.5550.
  * [185] T. Kerdreux, A. d’Aspremont, S. Pokutta, Restarting Frank-Wolfe, in: K. Chaudhuri, M. Sugiyama (Eds.), Proceedings of Machine Learning Research, Vol. 89 of Proceedings of Machine Learning Research, PMLR, 2019, pp. 1275–1283.
  * [186] F. Stonyakin, A. Gasnikov, P. Dvurechensky, M. Alkousa, A. Titov, Generalized Mirror Prox for monotone variational inequalities: Universality and inexact oracle, arXiv:1806.05140.
  * [187] O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, Ph.D. thesis (2013), UC Louvain.
  * [188] E. J. Candes, J. Romberg, T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory 52 (2) (2006) 489–509.
  * [189] D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory 52 (4) (2006) 1289–1306.
  * [190] E. Candes, T. Tao, The Dantzig selector: Statistical estimation when $p$ is much larger than $n$, The Annals of Statistics 35 (6) (2007) 2313–2351.
  * [191] A. Beck, M. Teboulle, Smoothing and first order methods: A unified framework, SIAM Journal on Optimization 22 (2) (2012) 557–580.
  * [192] A. Nemirovski, Prox-method with rate of convergence $o(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM Journal on Optimization 15 (1) (2004) 229–251.
  * [193] Y. Chen, G. Lan, Y. Ouyang, Accelerated schemes for a class of variational inequalities, Mathematical Programming 165 (2017), 113–149
  * [194] Y. Nesterov, Excessive gap technique in nonsmooth convex minimization, SIAM Journal on Optimization 16 (1) (2005) 235–249.
  * [195] Q. Tran-Dinh, V. Cevher, Constrained convex minimization via model-based excessive gap, in: Proceedings of the 27th International Conference on Neural Information Processing Systems, NIPS’14, MIT Press, Cambridge, MA, USA, 2014, pp. 721–729.
  * [196] Q. Tran-Dinh, O. Fercoq, V. Cevher, A smooth primal-dual optimization framework for nonsmooth composite convex minimization, SIAM Journal on Optimization 28 (1) (2018) 96–134, arXiv:1507.06243.
  * [197] A. Alacaoglu, Q. Tran Dinh, O. Fercoq, V. Cevher, Smooth primal-dual coordinate descent algorithms for nonsmooth convex optimization, in: I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (Eds.), Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017, pp. 5852–5861.
  * [198] Q. Tran-Dinh, A. Alacaoglu, O. Fercoq, V. Cevher, An adaptive primal-dual framework for nonsmooth convex minimization, Mathematical Programming Computation 12 (3) (2020) 451–491.
  * [199] A. Chernov, P. Dvurechensky, A. Gasnikov, Fast primal-dual gradient method for strongly convex minimization problems with linear constraints, in: Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos (Eds.), Discrete Optimization and Operations Research: 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings, Springer International Publishing, 2016, pp. 391–403.
  * [200] P. Dvurechensky, A. Gasnikov, E. Gasnikova, S. Matsievsky, A. Rodomanov, I. Usik, Primal-dual method for searching equilibrium in hierarchical congestion population games, in: Supplementary Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School (DOOR 2016) Vladivostok, Russia, September 19 - 23, 2016, 2016, pp. 584–595, arXiv:1606.08988.
  * [201] A. S. Anikin, A. V. Gasnikov, P. E. Dvurechensky, A. I. Tyurin, A. V. Chernov, Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints, Computational Mathematics and Mathematical Physics 57 (8) (2017) 1262–1276.
  * [202] P. Dvurechensky, A. Gasnikov, A. Kroshnin, Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm, in: J. Dy, A. Krause (Eds.), Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, 2018, pp. 1367–1376, arXiv:1802.04367.
  * [203] P. Dvurechensky, A. Gasnikov, S. Omelchenko, A. Tiurin, A stable alternative to Sinkhorn’s algorithm for regularized optimal transport, in: A. Kononov, M. Khachay, V. A. Kalyagin, P. Pardalos (Eds.), Mathematical Optimization Theory and Operations Research, Springer International Publishing, Cham, 2020, pp. 406–423.
  * [204] S. V. Guminov, Y. E. Nesterov, P. E. Dvurechensky, A. V. Gasnikov, Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems, Doklady Mathematics 99 (2) (2019) 125–128.
  * [205] A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, C. Uribe, On the complexity of approximating Wasserstein barycenters, in: K. Chaudhuri, R. Salakhutdinov (Eds.), Proceedings of the 36th International Conference on Machine Learning, Vol. 97 of Proceedings of Machine Learning Research, PMLR, Long Beach, California, USA, 2019, pp. 3530–3540, arXiv:1901.08686.
  * [206] A. Ivanova, P. Dvurechensky, A. Gasnikov, D. Kamzolov, Composite optimization for the resource allocation problem, Optimization Methods and Software 0 (0) (2020) 1–35, arXiv:1810.00595.
  * [207] T. Lin, N. Ho, M. Jordan, On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms, in: K. Chaudhuri, R. Salakhutdinov (Eds.), Proceedings of the 36th International Conference on Machine Learning, Vol. 97 of Proceedings of Machine Learning Research, PMLR, Long Beach, California, USA, 2019, pp. 3982–3991.
  * [208] C. A. Uribe, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, A. Nedić, Distributed computation of Wasserstein barycenters over networks, in: 2018 IEEE Conference on Decision and Control (CDC), 2018, pp. 6544–6549, arXiv:1803.02933.
  * [209] T. Lin, N. Ho, M. Cuturi, M. I. Jordan, On the Complexity of Approximating Multimarginal Optimal Transport, arXiv e-printsArXiv:1910.00152.
  * [210] T. Lin, N. Ho, X. Chen, M. Cuturi, M. I. Jordan, Computational Hardness and Fast Algorithm for Fixed-Support Wasserstein Barycenter, arXiv e-prints (2020) arXiv:2002.04783
  * [211] N. Tupitsa, P. Dvurechensky, A. Gasnikov, C. A. Uribe, Multimarginal optimal transport by accelerated alternating minimization, in: 2020 IEEE 59th Conference on Decision and Control (CDC), 2020, (accepted), arXiv:2004.02294.
  * [212] R. Krawtschenko, C. A. Uribe, A. Gasnikov, P. Dvurechensky, Distributed optimization with quantization for computing Wasserstein barycenters, arXiv:2010.14325
  * [213] Y. Nesterov, Universal gradient methods for convex optimization problems, Mathematical Programming 152 (1) (2015) 381–404.
  * [214] Y. Malitsky, T. Pock, A first-order primal-dual algorithm with linesearch, SIAM Journal on Optimization 28 (1) (2018) 411–432.
  * [215] D. Dvinskikh, A. Ogaltsov, A. Gasnikov, P. Dvurechensky, V. Spokoiny, On the line-search gradient methods for stochastic optimization, IFAC-PapersOnLine21th IFAC World Congress, accepted, arXiv:1911.08380.
  * [216] D. R. Baimurzina, A. V. Gasnikov, E. V. Gasnikova, P. E. Dvurechensky, E. I. Ershov, M. B. Kubentaeva, A. A. Lagunovskaya, Universal method of searching for equilibria and stochastic equilibria in transportation networks, Computational Mathematics and Mathematical Physics 59 (1) (2019) 19–33, arXiv:1701.02473.
  * [217] A. Yurtsever, Q. Tran-Dinh, V. Cevher, A universal primal-dual convex optimization framework, in: Proceedings of the 28th International Conference on Neural Information Processing Systems, NIPS’15, MIT Press, Cambridge, MA, USA, 2015, pp. 3150–3158.
  * [218] S. Ghadimi, G. Lan, H. Zhang, Generalized uniformly optimal methods for nonlinear programming, Journal of Scientific Computing 79 (3) (2019) 1854–1881, arXiv:1508.07384.
  * [219] B. T. Polyak, Introduction to Optimization, Optimization Software, 1987.
  * [220] J. Duchi, E. Hazan, Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, Journal of Machine Learning Research 12 (Jul.) (2011) 2121–2159.
  * [221] K. Y. Levy, A. Yurtsever, V. Cevher, Online adaptive methods, universality and acceleration, in: S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, R. Garnett (Eds.), Advances in Neural Information Processing Systems 31, Curran Associates, Inc., 2018, pp. 6500–6509, arXiv:1809.02864.
  * [222] F. Bach, K. Y. Levy, A universal algorithm for variational inequalities adaptive to smoothness and noise, in: A. Beygelzimer, D. Hsu (Eds.), Proceedings of the Thirty-Second Conference on Learning Theory, Vol. 99 of Proceedings of Machine Learning Research, PMLR, Phoenix, USA, 2019, pp. 164–194, arXiv:1902.01637.
  * [223] K. Antonakopoulos, E. V. Belmega, P. Mertikopoulos, Adaptive extra-gradient methods for min-max optimization and games, arXiv:2010.12100.
  * [224] R. Zhao, R. M. Freund, Analysis of the Frank-Wolfe method for logarithmically-homogeneous barriers, with an extension, arXiv:2010.08999.
  * [225] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, Advances and open problems in federated learning, arXiv preprint arXiv:1912.04977.
  * [226] E. Gorbunov, A. Rogozin, A. Beznosikov, D. Dvinskikh, A. Gasnikov, Recent theoretical advances in decentralized distributed convex optimization, arXiv preprint arXiv:2011.13259.
  * [227] R. Sun, Optimization for deep learning: theory and algorithms, arXiv preprint arXiv:1912.08957.
  * [228] M. Danilova, P. Dvurechensky, A. Gasnikov, E. Gorbunov, S. Guminov, D. Kamzolov, I. Shibaev, Recent theoretical advances in non-convex optimization, arXiv:2012.06188.
  * [229] M. B. Cohen, A. Sidford, K. Tian, Relative lipschitzness in extragradient methods and a direct recipe for acceleration, arXiv:2011.06572.

  *[DGF]: distance generating function