From proximal point method to Nesterov's accelerationThis work was done as the author's class project for 6.881  Optimization for Machine Learning at MIT, Spring 2020.

Kwangjun Ahn
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology

The proximal point method (PPM) is a fundamental  method in optimization  that is often used as a building block for  fast optimization algorithms.
In this work, building on a recent work by Defazio [9], we provide  a complete understanding of Nesterov's accelerated gradient method (AGM) by establishing quantitative and analytical connections between PPM and AGM.
The main observation in this paper is that AGM is in fact equal to a simple approximation of PPM, which results in an elementary derivation of the mysterious updates of AGM as well as its step sizes.
This connection also leads to a conceptually simple analysis of AGM based on the standard analysis of PPM.
This view naturally extends to the strongly convex case and also motivates other accelerated methods for practically relevant settings.

§ INTRODUCTION

The proximal point method (PPM) [23, 21, 27] is a fundamental method in optimization which solves the minimization of the cost function $f:\re^d\to \re$ by iteratively solving the  subproblem

\begin{align}
\label{prox}
x_{t+1} \leftarrow \argmin_{x\in \re^d} \left\{ f(x) + \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}
\end{align}

for a step size $\ee_{t+1}>0$, where the norm is chosen as the $\ell_2$ norm.
The motivation of the method is clear: we add a quadratic regularization to make the cost function well conditioned for faster optimization[For instance, when $f$ is nonconvex,  the regularization term can  make each subproblem  (<ref>)  convex, and even when $f$ is convex, the regularization term will serve to increase the strong convexity parameter, which results in faster optimization.
Nevertheless, solving (<ref>) is in general as difficult as solving the original optimization problem, and PPM is largely regarded as a “conceptual” guiding principle for accelerating optimization algorithms [12].

On the other hand, there is another prevalent accelerated method called Nesterov's accelerated gradient method (AGM) [24].
In constrast to PPM, AGM is implementable and has been applied to a myriad of applications, including sparse linear regression [8], compressed sensing [3], the maximum  flow problem [18], and deep neural networks [29].
Nonetheless, in contrast with the clear motivation of PPM, AGM has an obscure driving principle.
In particular, original construction of AGM relies on an ingenious yet abstruse technique called estimate sequence <cit.>, which has motivated researchers to investigate numerous alternative explanations (see Section <ref> for details).

Recently, Defazio [9] established an inspiring connection  between PPM and AGM. The main observation is that  for strongly convex costs, one can derive  a version of AGM from the primal-dual form of PPM with a tweak of geometry.
This observation constitutes an important step toward understanding AGM because PPM is not as difficult to understand.
This inspiring result, nevertheless, leaves open many other important questions.
Most importantly, [9] lacks quantitative explanations as to why AGM achieves the accelerated convergence rates of $O(\nicefrac{1}{T^2})$ for smooth (Definition <ref>) costs and $O(\exp(\nicefrac{-T}{\sqrt{\kappa}}))$ for smooth and strongly convex (Definition <ref>) costs, where $T$ is the number of iterations and $\kappa$ is the condition number of the problem.
Moreover, it is not clear whether such connection can be made without assuming strong convexity and can be extended to other  more general and practical versions of AGM.

In this work, we build a thorough understanding of Nesterov's acceleration from the proximal point method by strengthening the connection made in [9].
The main observation in this paper is that the mysterious updates of AGM can be fully understood by viewing it as a simple approximation of PPM.
In particular, this observation leads to a straightforward derivation of  AGM that does not rely on duality unlike [9].
Moreover, the PPM view of AGM   offers a simple analysis of AGM based on the  standard analysis of PPM [14].
We also demonstrate the generality of our view.
More specifically, our view naturally extends to the strongly convex case and obtains a general[It is general in the sense that it smoothly interpolates between the  strongly convex case and  the non-strongly convex case.] version of AGM <cit.>, and our view also gives rise to the key idea of the method of similar triangles, a version of AGM shown to have simple extensions to practically relevant settings [31, 13, 26].

§ BASELINE: ANALYSIS OF  THE PROXIMAL POINT METHOD

The baseline of our discussion is the following convergence rate of PPM for convex costs  proved  in a seminal paper by Güler [14]  (here $\xs$ denotes a global optimum point, i.e., $\xs \in \argmin_x f(x)$):

\begin{align}
\boxed{\textstyle f(x_{T})- f(\xs) \leq \OO{\big(\sum_{t=1}^{T} \ee_t\big)^{-1}}\quad \text{for any $T\geq 1$.}} \label{conv:prox}
\end{align}

In words, one can achieve an arbitrarily fast convergence rate by choosing step sizes $\ee_t$'s large.
Below, we review  a short Lyapuov function proof of (<ref>), which will serve as a backbone to other analyses.

It turns out that the following Lyapunov function is suitable:

\begin{align}
\boxed{\textstyle \Phi_t:=  \big(\sum_{i=1}^{t} \ee_i \big)\cdot \big(f(x_t)-f(\xs)\big) + \frac{1}{2}\norm{\xs-x_t}^2,}\label{def:lya}
\end{align}

where $\Phi_0:= \frac{1}{2}\norm{\xs-x_0}^2$ and here and below, $\norm{\cdot}$ is the $\ell_2$ norm unless stated otherwise.
Now,  it suffices to show that  $\Phi_t$  is decreasing, i.e., $\Phi_{t+1}\leq \Phi_t$ for all $t\geq 0$.
Indeed, if $\Phi_t$ is decreasing, we have $\Phi_T\leq \Phi_0$ for any $T\geq 1$, which  precisely recovers (<ref>). To that end, we use a standard result:

[Proximal inequality (see e.g. <cit.>)]  For a convex function $\phi:\re^d\to \re$,  let $x_{t+1}$ be the unique minimizer of the following proximal step:

\begin{align}
\textstyle x_{t+1} \leftarrow \min_{x\in \re^d} \left\{\phi(x) +\frac{1}{2}\norm{x-x_t}^2\right\}\,. \label{prox:cond}
\end{align}

Then, for any $u\in \re^d$, $\phi(x_{t+1})-\phi(u) +\frac{1}{2}\norm{u-x_{t+1}}^2 +\frac{1}{2}\norm{ x_{t+1}-x_t}^2  -\frac{1}{2}\norm{u-x_t}^2\leq 0$.

Now Proposition <ref> completes the proof as follows:  First, we apply Proposition <ref> with $\phi=\ee_{t+1} f$ and $u=\xs$ and drop the term $\frac{1}{2}\norm{x_{t+1}-x_t}^2$ to obtain:

\begin{align}
\tag{B1}  \ee_{t+1}\left[f( x_{t+1}) -f( \xs)\right] + \frac{1}{2} \norm{\xs-    x_{t+1}}^2  -\frac{1}{2} \norm{ \xs-x_t}^2\leq  0\,.\label{ineq:1}
\end{align}

Next, from the optimality of $x_{t+1}$ for (<ref>), it readily follows that

\begin{align}
\tag{B2} f(x_{t+1}) - f(x_t) \leq 0\,. \label{ineq:2}
\end{align}

Now,  computing $\eqref{ineq:1}+( \sum_{i=1}^{t} \ee_i )\times $(<ref>) yields $\Phi_{t+1}\leq \Phi_t$, which finishes the proof.

§.§ Our conceptual question

Although the convergence rate (<ref>) seems powerful, it does not have any practical values as PPM is in general not implementable.
Nevertheless, one can ask the following conceptual question:

Can we develop an implementable approximation of PPM for large step sizes $\ee_t$'s?

Perhaps, the most straightforward approximation would be to replace the cost function $f$ in (<ref>) with its lower-order approximations.
We implement this idea in the next section.

§ TWO SIMPLE APPROXIMATIONS OF THE PROXIMAL POINT METHOD

To analyze approximation errors, let us assume that the cost function $f$ is $L$-smooth.

For $L>0$, we say a differentiable function $f:\re^d\to \re$ is  $L$-smooth if  $f(x) \leq f(y) + \inp{\nabla f(y)}{x-y} +\frac{L}{2}\norm{x-y}^2 $ for any $x,y\in\re^d$.

From the convexity and the $L$-smoothness of $f$, we have the following lower and upper  bounds:

\begin{align*}
\textstyle f(y) +\inp{\nabla f(y)}{x-y}    \leq f(x) \leq f(y) +\inp{\nabla f(y)}{x-y}+\frac{L}{2}\norm{x-y}^2\quad \text{for any $x,y\in \re^d$.}
\end{align*}

In this section, we use these bounds to approximate PPM.

§.§ First approach: using first-order approximation

Let us first replace $f$ in the objective (<ref>) with its lower approximation:

\begin{align}
x_{t+1} \leftarrow \argmin_{x} \left\{ f(x_t)+\inp{\nabla f(x_t)}{x-x_t} + \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}\,. \label{gd}
\end{align}

Writing the optimality condition, one quickly notices that (<ref>) actually leads to  gradient descent:

\begin{align}
x_{t+1} =x_t -\ee_{t+1} \nabla f(x_{t})\,.\label{gd:1}
\end{align}

Let us see how well (<ref>) approximates PPM:

We first establish counterparts  of  (<ref>) and (<ref>).
We begin with (<ref>). We first apply Proposition <ref> with $\phi(x)=\ee_{t+1}[f(x_t)+\inp{\nabla f(x_t)}{x-x_t}]$ and $u=\xs$:

\begin{align*}
&\phi(x_{t+1})-\phi(\xs)+ \frac{1}{2} \norm{\xs -x_{t+1}}^2 + \frac{1}{2} \norm{ x_{t+1}-x_t}^2 -\frac{1}{2 } \norm{\xs -x_{t}}^2\leq 0\,.
\end{align*}

Now using convexity and $L$-smoothness, we have $\phi(x)\leq \ee_{t+1} f(x)\leq \phi(x) +\frac{L\ee_{t+1}}{2}\norm{x-x_t}^2$, and hence the above inequality implies the following approximate version of (<ref>):

\begin{align*}
\ee_{t+1} \left[ f(x_{t+1})- f(\xs)\right] + \frac{1}{2} \norm{\xs -x_{t+1}}^2- \frac{1}{2 } \norm{\xs -x_{t}}^2 \leq   \eeo,
\end{align*}

where $\eeo:= (\frac{L\ee_{t+1}}{2}-\frac{1  }{2} )\norm{x_{t+1}-x_t}^2$.
Next, we use the $L$-smoothness of $f$ and the fact $\nabla f(x_t)= -\nicefrac{1}{\ee_{t+1}}(x_{t+1}-x_t)$ (due to (<ref>)), to obtain the following counterpart of (<ref>):

\begin{align*}
f(x_{t+1}) -f(x_t) \leq  \inp{\nabla f(x_t)}{x_{t+1}-x_t} + \frac{L}{2} \norm{x_{t+1}-x_t}^2 =   \eet,
\end{align*}

where $\eet:=( \frac{L}{2}- \frac{1}{\ee_{t+1}}) \norm{x_{t+1}-x_t}^2$.

Now paralleling the proof of (<ref>),  to show that $\Phi_t$ (<ref>) is a valid Lyapunov function, we need to find the step sizes $\ee_t$'s that satisfy the following relation: $\eeo + ( \sum_{i=1}^t \ee_i) \times \eet \leq 0$.
On the other hand, note that both  and  become positive numbers when $\ee_{t+1}>2/L$.
Hence, the admissible choices for $\ee_t$ at each iteration are upper bounded by $2/L$, which together with the PPM convergence rate (<ref>) implies that $O(\nicefrac{1}{\sum_{t=1}^T\ee_t}) =O(\nicefrac{1}{T})$ is the best convergence rate  one can prove.
Indeed, choosing  $\ee_t\equiv 1/L$, then we have $\eeo=0$ and $\eet<0$, obtaining the well-known bound of $f(x_T)-f(\xs) \leq \frac{L\norm{x_0-\xs}^2}{2T} =O(\nicefrac{1}{T})$.

To summarize, the first approach only leads to a disappointing result: the approximation is valid only for the small step size regime of $\ee_t = \OO{1}$.
We empirically verify this fact for a  quadratic cost in Figure <ref>.
As one can see from Figure <ref>, the lower approximation approach (<ref>)  overshoots for large step sizes like  $\ee_t = \Theta(t)$ and quickly steers away from PPM iterates.

$\ee_t\equiv 1/3$.

Iterates comparison between PPM (<ref>), the first approach (<ref>), the second approach (<ref>), and the combined approach (<ref>). For the setting, we choose $f(x,y) = 0.1x^2+y^2$ and   $x_0=(10,10)$.

§.§ Second approach: using smoothness

After seeing the disappointing outcome of the first approach, our second approach is to replace $f$ with  its upper approximation  due to the $L$-smoothness:

\begin{align}
x_{t+1} \leftarrow \argmin_{x} \left\{ f(x_t)+\inp{\nabla f(x_t)}{x-x_t} +\frac{L}{2} \norm{x-x_t}^2+ \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}\,. \label{gd:2-1}
\end{align}

Writing the optimality condition,  (<ref>) actually leads to a conservative update of gradient descent:

\begin{align}
x_{t+1} = x_t -\frac{1}{L+\ee_{t+1}^{-1}} \nabla f(x_{t})\,. \label{gd:2-2}
\end{align}

Note that regardless of how large $\ee_{t+1}$ we choose, the actual update step size in (<ref>) is always upper bounded by $\nicefrac{1}{L}$.
Although this conservative update  prevents the  overshooting phenomenon of the first approach, as we increase $\ee_{t}$, this conservative update becomes too tardy to be a good approximation of PPM; see Figure <ref>.

§ NESTEROV'S ACCELERATION VIA ALTERNATING TWO APPROACHES

In the previous section, we have seen that the two simple approximations of PPM both have limitations.
Nonetheless, observe that their limitations are opposite to each other: while the first approach is too “reckless,” the second approach is too “conservative.”
This observation motivates us to consider a combination of the two approaches which could mitigate each other's limitation.

Let us implement this idea by alternating between the two approximations (<ref>) and (<ref>) of PPM.
The key modification is that for both approximations, we introduce an additional sequence of points $\{y_t\}$ for cost function approximation; i.e., we use the following approximations for the $t$-th iteration:

\begin{align*}
f(y_t) +\inp{\nabla f(y_t)}{x-y_t}    \leq f(x) \leq f(y_t) +\inp{\nabla f(y_t)}{x-y_t}+\frac{L}{2}\norm{x-y_t}^2\,.
\end{align*}

Indeed, this modification is crucial: if we just use approximations at $x_t$, the resulting alternation merely concatenates  (<ref>) and (<ref>) during each iteration, and the two limitations we discussed in Section <ref> will remain in the combined approach.

Having introduced a separate sequence $\{y_t\}$ for cost approximations,  we consider the following alternation  where during each iteration, we update $x_{t}$ with  (<ref>) and $y_{t}$ with (<ref>):
Approximate PPM with alternating two approaches. Given $x_0\in \re^d$, let $y_0=x_0$ and run:

\begin{align}
\label{ppm:a} &{\textstyle x_{t+1} \leftarrow  \argmin_{x } \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} + \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}}, \\
\label{ppm:b}
&{\textstyle y_{t+1}\leftarrow   \argmin_{x} \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} +\frac{L}{2} \norm{x-y_t}^2+ \frac{1}{2\ee_{t+1}} \norm{x-x_{t+1}}^2 \right\} }.
\end{align}

In  Figure <ref>, we empirically verify that (<ref>) indeed gets the best of both worlds: this combined approach successfully approximates PPM even for the regime $\ee_t=\Theta(t)$.
More remarkably, (<ref>) exactly recovers Nesterov's AGM.
More specifically, turning (<ref>) into the equational form by writing the optimality conditions, and introducing an auxiliary iterate $z_{t+1}:= y_t -\nicefrac{1}{L}\nabla f(y_t)$,  we obtain the following ($z_0:=x_0=y_0$):

An equivalent representation of (<ref>):

\begin{align}
& \textstyle y_{t} =\frac{\nicefrac{1}{L}}{ \nicefrac{1}{L}+\ee_t} x_t+\frac{ \ee_t }{  \nicefrac{1}{L}+\ee_t} z_t \,, \label{agm:a}\\
& \textstyle x_{t+1} = x_t -\ee_{t+1} \nabla f(y_{t})\,,\label{agm:b}\\
& \textstyle z_{t+1} = y_{t}-\frac{1}{L}\cdot \nabla f(y_{t})\,. \label{agm:c}
\end{align}

(a1) at (-2,0);
(a2) at (-2,-4.5*0.6);
(a3) at (-2,-4.5);
[label=left: $\boldsymbol{x_t}$] (xt) at (0,0);
[label=right: $\boldsymbol{x_{t+1}}$] (xt1) at (11,0);
[label=left:  $\boldsymbol{z_{t}}$] (zt) at (2,-4.5);
[label=left: $\boldsymbol{y_{t}}$] (yt1) at (2*0.6,-4.5*0.6);
[label=right:   $\boldsymbol{z_{t+1}}$] (zt1) at (6.0,-4.5*0.6);
[->,>=stealth,dotted, line width=1pt,red] (xt) – node[below] $\textcolor{red}{\boldsymbol{-\ee_{t+1} \nabla f(y_{t})}}$ (xt1);
[->,>=stealth, dotted, line width=1pt,red] (yt1) – node[below] $\textcolor{red}{\boldsymbol{-\frac{1}{L}\nabla f(y_{t})}}$ (zt1);

[<->,dotted] (a1) – node[left] $  {\ee_t}$  (a2);
[<->,dotted] (a2) – node[left] $  {\nicefrac{1}{L}}$  (a3);
[dashed] (zt) –   (zt1);
[dashed] (zt1) –   (xt1);
[dashed] (xt) –   (zt);

The  iterates of (<ref>).

Hence, we arrive at AGM without relying on any non-trivial derivations in the literature such as estimate sequence [26] or linear coupling [2].
To summarize, we have demonstrated:

Nesterov's accelerated method is a simple approximation of the proximal point method!

Our derivation  is inspired by the one in the recent work by Defazio <cit.>.
However, unlike the approach in [9], our derivation does not rely on duality, which could be advantageous in the settings where duality fails.

It is often the case in the literature that the interpolation step (<ref>) is written as an abstract form $y_t = \tau_t x_t + (1-\tau_t) z_t$ with a weight parameter $\tau_t>0$ to be chosen [2, 17, 32, 6, 1].
That said, in the previous works, $\tau_t$ is carefully chosen according to the analysis without conveying  much intuition.
One important aspect of our PPM view is that it reveals a close relation between the weight parameter $\tau_t$ and the step size $\ee_t$.
More specifically, $\tau_t$ is chosen so that the ratio of the distances  $\norm{y_t-x_t}:\norm{y_t-z_t}$ is equal to $\ee_t:\nicefrac{1}{L}$ (see Figure <ref>).

§.§ Understanding the accelerated convergence rate

In order to determine $\ee_t$'s in (<ref>),  we revisit the analysis of PPM from Section <ref>.
In turns out that following Section <ref>, one can derive from first principles the following inequalities  using Proposition <ref>  (we defer the derivations to Appendix <ref>):

\begin{align*}
\text{Counterpart of }\eqref{ineq:1}: &\quad\ee_{t+1}(f(z_{t+1})- f(\xs)) + \frac{1}{2} \norm{\xs -x_{t+1}}^2-
\frac{1}{2} \norm{\xs -x_{t}}^2\leq \ffo\quad \text{and}\\
\text{Counterpart of }\eqref{ineq:2}: &\quad  f(z_{t+1}) -f(z_t) \leq \fft\,,
\end{align*}

where $\ffo:=(\frac{\ee_{t+1}^2}{2}-\frac{\ee_{t+1}}{2L}) \norm{\nabla f(y_{t})}^2 + L\ee_t\ee_{t+1}\inp{\nabla f(y_{t})}{ z_{t}-y_t}$ and $\fft:= -\frac{1}{2L} \norm{\nabla f(y_{t})}^2$ $- \inp{\nabla f(y_{t})}{z_{t}-y_t}$.
Hence, we modify the Lyapunov function (<ref>) by replacing  the first $x_t$ with $z_t$:

\begin{align}
\textstyle \Phi_t:= (\sum_{i=1}^{t} \ee_i)\cdot (f(z_t)-f(\xs)) + \frac{1}{2}\norm{\xs-x_t}^2\,. \label{lya2}
\end{align}

Then as before, to prove the validity of the chosen Lyapunov function, it suffices to verify $\ffo + ( \sum_{i=1}^t \ee_i)\cdot \fft \leq 0$, which is equivalent to

\begin{align}
\label{cond:1} \textstyle \frac{1}{2L}\left( L\ee_{t+1}^2 - \sum_{i=1}^{t+1} \ee_i\right)   \norm{\nabla f(y_t)}^2 + \left( L\ee_t\ee_{t+1} - \sum_{i=1}^t \ee_i\right)\inp{\nabla f(y_{t})}{z_{t}-y_t} \leq 0
\end{align}

From (<ref>), it suffices to choose $\{\ee_t\}$ so that
$L\ee_t\ee_{t+1}=\sum_{i=1}^t \ee_i$.
Indeed, with such a choice, the coefficient of the inner product term in (<ref>) becomes zero and the coefficient of the squared norm term becomes $\nicefrac{1}{2L}(L\ee_{t+1}^2 - L\ee_{t+1}\ee_{t+2})\leq 0$ (if $\{\ee_t\}$ is increasing).
Indeed, one can quickly notice that choosing $\ee_{t} =\nicefrac{t}{2L}$ satisfies  the desired relation.
Therefore,  we obtain the well known accelerated convergence rate of $f(z_T)-f(\xs)\leq \frac{2L \norm{x_0-\xs}^2}{T(T+1)}= O(\nicefrac{1}{T^2})$ [24].

§.§ Separating step sizes for flexibility

Since (<ref>) is an approximation of PPM, it is helpful to give (<ref>) more flexibility when we try to extend it to other settings.
In particular, we relax (<ref>) by separating the two step sizes:

Approximate PPM with two separate step sizes $\{\ee_t\}$ and $\{\eep_t\}$. Given $x_0=y_0\in \re^d$,

\begin{align}
\label{ppm2:a} &{\textstyle x_{t+1} \leftarrow  \argmin_{x } \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} + \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}}, \\
\label{ppm2:b}
&{\textstyle y_{t+1}\leftarrow   \argmin_{x} \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} +\frac{L}{2} \norm{x-y_t}^2+ \frac{1}{2\eep_{t+1}} \norm{x-x_{t+1}}^2 \right\} }.
\end{align}

As we shall see in the next subsection, this simple relaxation allows us to recover a well known general version of AGM <cit.>.

§.§ Acceleration for strongly convex costs

Let us  apply our PPM view  to the strongly convex cost case. We begin with the definition:

For $\mu>0$, we say a differentiable function $f:\re^d\to \re$ is  $\mu$-strongly convex if   $f(x) \geq f(y) + \inp{\nabla f(y)}{x-y} +\frac{\mu}{2}\norm{x-y}^2 $ for any $x,y\in\re^d$.

Since $f$ is additionally assumed to be strongly convex, one can strengthen the step (<ref>) by

\begin{align}
\label{ppm:str}
x_{t+1} \leftarrow \argmin_{x\in \re^d} \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} + \frac{\mu}{2}\norm{x-y_t}^2 + \frac{1}{2\ee_{t+1}} \norm{x-x_t}^2 \right\}\,.
\end{align}

Writing the optimality condition of (<ref>), it is straightforward to check that (<ref>) is equivalent to the following form (again, we introduce another auxiliary iterate $w_t$, and let $z_0:=x_0=y_0$):

Approximate PPM  for strongly convex costs:

\begin{align}
& \textstyle y_{t} =\frac{\nicefrac{1}{L}}{  \nicefrac{1}{L}+\eep_t} x_t +\frac{ \eep_t }{   \nicefrac{1}{L}+\eep_t} z_t\,, \label{agm2:a}\\
& \textstyle w_t = \frac{\nicefrac{1}{\mu}}{ \nicefrac{1}{\mu}+\ee_{t+1}}x_t +\frac{\ee_{t+1}}{ \nicefrac{1}{\mu} +\ee_{t+1}}y_t\\
& \textstyle x_{t+1} = w_t- \frac{\nicefrac{1}{\mu}\cdot \ee_{t+1}}{ \nicefrac{1}{\mu}+\ee_{t+1}}\nabla f(y_{t})\,,\label{agm2:b}\\
& \textstyle z_{t+1} = y_{t}-\frac{1}{L}\nabla f(y_{t})\,. \label{agm2:c}
\end{align}

(a1) at (-3,0);
(a2) at (-3,-7*0.7);
(a3) at (-3,-7);

(b1) at (-2.5,0);
(b2) at (-2.5,-7*0.3);
(b3) at (-2.5,-7*0.7);
[label=left: $\boldsymbol{x_t}$] (xt) at (0,0);
[label=right:$\boldsymbol{x_{t+1}}$] (xt1) at (11,0);
[label=left: $\boldsymbol{w_t}$]   (wt) at (1*0.3,-7*0.3);
[label=left:  $\boldsymbol{z_{t}}$] (zt) at (1,-7);
[label=left: $\boldsymbol{y_{t}}$] (yt1) at (1*0.7,-7*0.7);
[label=below: $\boldsymbol{z_{t+1}}$] (zt1) at (1+10*0.3/0.7,-7+7*0.3/0.7);
[->,>=stealth,dotted, line width=1pt,red] (wt) – node[above] $\textcolor{red}{\boldsymbol{-\frac{\ee_{t+1}\cdot \nicefrac{1}{\mu}}{ \ee_{t+1}+\nicefrac{1}{\mu}} \nabla f(y_{t})}}$ (xt1);
[->,>=stealth, dotted, line width=1pt,red] (yt1) – node[above] $\textcolor{red}{\boldsymbol{-\frac{1}{L}\nabla f(y_{t})}}$ (zt1);

[<->,dotted] (a1) – node[left] $  {\eep_t}$  (a2);
[<->,dotted] (a2) – node[left] $  {\nicefrac{1}{L}}$  (a3);
[dashed] (zt) –   (zt1);
[dashed] (zt1) –   (xt1);
[dashed] (xt) –   (zt);

[<->,dotted] (b1) – node[right] $  {\ee_{t+1}}$  (b2);
[<->,dotted] (b2) – node[right] $  {\nicefrac{1}{\mu}}$  (b3);

The  iterates of (<ref>).

Paralleling Remark <ref>, our derivation provides new insights into the choices of the AGM step sizes by expressing them in terms of the PPM step sizes $\ee_t$'s and $\eep_t$'s.
Furthermore, our derivation actually demystifies the mysterious parameter choices made in the Nesterov's book <cit.>.
To see this, let us recall the well known convergence rate of PPM for strongly convex costs due to Rockafellar <cit.>:

\begin{align}
\boxed{\textstyle f(x_{T})- f(\xs) \leq \OO{\prod_{t=1}^{T} (1+\mu\ee_t)^{-1}}\quad \text{for any $T\geq 1$.}} \label{conv:prox:str}
\end{align}

In light of (<ref>), it turns out that  for the approximate PPM (<ref>), choosing the following step sizes

$\ee_t \equiv \ee:= \mu^{-1}\cdot  (\sqrt{\kappa}-1)^{-1}$ and $\eep_t \equiv \eep:= \mu^{-1}\cdot  (\sqrt{\kappa})^{-1}$  (where $\kappa:=\nicefrac{L}{\mu}$)

actually recovers the well known parameters choice <cit.> which leads to the convergence rate of $\OO{(1+\ee \mu)^{-T}}=\OO{(1+\nicefrac{1}{(\sqrt{\kappa}-1)})^{-T}}$. See <cit.> for a simple Lyapunov function proof  of this convergence rate.

Remarkably, (<ref>) also exactly recovers a general version of AGM <cit.> which smoothly interpolates between the strongly convex case and the non-strongly convex case.
To see this, we follow a simple equivalent representation of Nesterov's general step sizes  given in [1].
More specifically, given a sequence $\{\xi_t\}$ of positive numbers defined as per the nonlinear recursion $\frac{\xi_{t+1}(\xi_{t+1}-\kappa^{-1})}{1-\xi_{t+1}}=\xi_t^2$ with an initial value $\xi_0>0$,  choosing $\ee_t=\mu^{-1}\cdot  (\kappa \xi_t-1)^{-1}$  and $\eep_t =  \mu^{-1}\cdot (\kappa \xi_{t+1}-1)^{-1}\cdot  (1-\xi_{t+1})$ exactly recovers the choices in <cit.> which are shown to be equivalent to Nesterov's choices <cit.>.

§ SIMPLE GENERALIZATIONS WITH SIMILAR TRIANGLES

In the previous section, we have demonstrated that Nesterov's method is nothing but an approximation of PPM.
This view point has not only provided  simple derivations of versions of  AGM, but also offered clear explanations of the step sizes. In this section, we demonstrate that these interpretations offered by  PPM  actually lead to a great simplification of Nesterov's AGM in the form of the method of similar triangles [26, 13] which admits simple generalizations to practically relevant settings.

Our starting point is the observations made in the previous section:  (i) from Remark <ref>, we have seen $\norm{y_t-x_t}:\norm{y_t-z_t}=\ee_t:\nicefrac{1}{L}$; (ii) from Section <ref>, we have seen that we need to choose $\ee_t=\Theta(t)$, and hence, $\ee_{t+1}\approx\ee_t \gg 1$.
From these observations, one can readily see that the triangle $\triangle x_tx_{t+1}z_t$ is approximately similar to $\triangle y_tz_{t+1} z_t$.
Therefore, one can simplify AGM by further exploiting this fact: we  modify the updates so that the two triangles are indeed similar:

Similar triangle approximation of PPM:

\begin{align}
& \textstyle y_{t} = \frac{\nicefrac{1}{L}}{ \nicefrac{1}{L}+\ee_t} x_t+\frac{ \ee_t }{ \nicefrac{1}{L}+\ee_t} z_t\,, \label{sim:a}\\
& \textstyle x_{t+1} = x_t -\ee_{t+1} \nabla f(y_{t})\,,\label{sim:b}\\
& \textstyle z_{t+1} = \frac{\nicefrac{1}{L}}{ \nicefrac{1}{L}+\ee_t} x_{t+1}+\frac{ \ee_t }{ \nicefrac{1}{L}+\ee_t } z_t\,. \label{sim:c}
\end{align}

(a1) at (-2,0);
(a2) at (-2,-4.5*0.6);
(a3) at (-2,-4.5);
[label=left: $\boldsymbol{x_t}$] (xt) at (0,0);
[label=right: $\boldsymbol{x_{t+1}}$] (xt1) at (11,0);
[label=left:  $\boldsymbol{z_{t}}$] (zt) at (2,-4.5);
[label=left: $\boldsymbol{y_{t}}$] (yt) at (2*0.6,-4.5*0.6);
[label=right:   $\boldsymbol{z_{t+1}}$] (zt1) at (2+9*0.4,-4.5*0.6);
[->,>=stealth, dotted, line width=0.8pt,red] (xt) – node[below] $\textcolor{red}{\boldsymbol{-\ee_{t+1} \nabla f(y_{t})}}$ (xt1);
[->,>=stealth,dotted, line width=0.8pt,red] (yt) –  (zt1);

[<->,dotted] (a1) – node[left] $  {\ee_t}$  (a2);
[<->,dotted] (a2) – node[left] $  {\nicefrac{1}{L}}$  (a3);
[dashed] (zt) –   (xt1);
[dashed] (xt) –   (zt);
pic[draw=black, fill=gray!10, -, angle eccentricity=1.2, angle radius=0.5cm, line width=1pt]
pic[draw=black, fill=gray!10,  -, angle eccentricity=1.2, angle radius=0.5cm, line width=1pt]
pic[draw=black,  fill=gray!10,-, densely dotted, angle eccentricity=1.2, angle radius=0.3cm, line width=1pt]
pic[draw=black, fill=gray!10, -, densely dotted, angle eccentricity=1.2, angle radius=0.3cm, line width=1pt]

The similar triangle updates (<ref>).

We provide a PPM-based analysis of (<ref>) for a more general setting in Section <ref>.

The updates akin to (<ref>) can be found in <cit.> (note that the step sizes are slightly different).
Our derivation based on the PPM view indeed clarifies why such similar triangles are natural updates to consider.
We also remark that the updates based on similar triangles is useful in developing universal methods for stochastic composite optimizations [13].

An alternative way to approximate PPM with similar triangles is:

Alternative similar triangle approximation:

\begin{align}
& \textstyle y_{t} = \frac{\nicefrac{1}{L}}{ \nicefrac{1}{L}+\ee_t} x_t+\frac{ \ee_t }{ \nicefrac{1}{L}+\ee_t} z_t\,, \label{sim2:a}\\
& \textstyle z_{t+1} = y_t -\frac{1}{L} \nabla f(y_{t})\,,\label{sim2:b}\\
& \textstyle x_{t+1} =z_{t+1} + L\eta_t (z_{t+1}-z_t)\,. \label{sim2:c}
\end{align}

(a1) at (-2,0);
(a2) at (-2,-4.5*0.6);
(a3) at (-2,-4.5);
[label=left: $\boldsymbol{x_t}$] (xt) at (0,0);
[label=right: $\boldsymbol{x_{t+1}}$] (xt1) at (11,0);

(2,-4.5) circle (3pt) node[] ;
[label=left:  $\boldsymbol{z_{t}}$] (zt) at (2,-4.5);

(2*0.6,-4.5*0.6) circle (3pt) node[] ;
[label=left: $\boldsymbol{y_{t}}$] (yt) at (2*0.6,-4.5*0.6);

(2+9*0.4,-4.5*0.6) circle (3pt) node[] ;
[label=below:   $\boldsymbol{z_{t+1}}$] (zt1) at (2+9*0.4,-4.5*0.6);

(2+9*0.6,-4.5*0.4) circle (3pt) node[] ;
[label=above:   $\boldsymbol{y_{t+1}}$] (yt1) at (2+9*0.6,-4.5*0.4);
[->,>=stealth, dotted, line width=0.8pt,red] (xt) – (xt1);
[->,>=stealth,dotted, line width=0.8pt,red] (yt) –
node[above] $\textcolor{red}{\boldsymbol{-\frac{1}{L} \nabla f(y_{t})}}$ (zt1);

[<->,dotted] (a1) – node[left] $  {\ee_t}$  (a2);
[<->,dotted] (a2) – node[left] $  {\nicefrac{1}{L}}$  (a3);
[dashed] (zt) –   (xt1);
[dashed] (xt) –   (zt);
pic[draw=black, fill=gray!10, -, angle eccentricity=1.2, angle radius=0.5cm, line width=1pt]
pic[draw=black, fill=gray!10,  -, angle eccentricity=1.2, angle radius=0.5cm, line width=1pt]
pic[draw=black,  fill=gray!10,-, densely dotted, angle eccentricity=1.2, angle radius=0.3cm, line width=1pt]
pic[draw=black, fill=gray!10, -, densely dotted, angle eccentricity=1.2, angle radius=0.3cm, line width=1pt]

The updates of (<ref>).

In fact, (<ref>) can be equivalently expressed without $\{x_t\}$: at the $t$-iteration, we compute (<ref>) and then update $y_{t+1}$ via $y_{t+1}= z_{t+1} + \frac{L\ee_t}{L\ee_{t+1}+1}(z_{t+1}-z_t)$ (these updates are illustrated with dots in Figure <ref>).
Hence, (<ref>) is equal to the well-known momentum based AGM [24, 8].
Notably, it turns out that our  PPM-based analysis suggests the choice of $\{\ee_t\}$ as per the recursive relation $(L\ee_{t+1}+\frac{1}{2})^2= (L\ee_t+1)^2 +\frac{1}{4}$, which after substitution $L\ee_t+1\leftarrow a_t$ exactly recovers the popular recursive relation $a_{t+1} = \frac{1}{2} (1+\sqrt{1+4a_t^2})$ in [24, 8].
See Appendix <ref> for precise details.

The main advantage of this similar triangles approximation (<ref>) becomes clearer in the constraint  optimization case: when there is a constraint set, the  steps (<ref>) and (<ref>) both become projections steps which could be costly when the constraint set does not admit simple projections.
On the other hand, since (<ref>) only requires a single projection in each iteration, it minimizes such costly computations.

§.§ Extension to  composite costs and general norms

It turns out  (<ref>) admits a simple extension to the practically relevant setting of composite costs and general norms (see e.g.  <cit.>).
More specifically, for a closed convex set $Q\subseteq \re^d$ and a closed[This means that the epigraph of the function is closed. See <cit.>. ] convex function $\Psi:Q\to \re$, consider
\begin{align*}
\textstyle \min_{x\in Q} \fsi(x):= f(x)+\Psi(x) \,,
\end{align*}

where $f:Q\to \re$ is a differentiable convex function which is $L$-smooth with respect to a norm $\norm{\cdot}$ that is not necessarily  the $\ell_2$ norm (i.e., we regard the norm in Definition <ref> to be our chosen norm).
For the general norm case, we use the Bregman divergence for the regularizer[The reason why we need the Bregman divergence in place of the norm squared regularization is because for norms other than the $\ell_2$ norm, $\frac{1}{2}\norm{u-v}^2$ is not strongly convex with respect to the chosen norm. ]:

Given a $1$-strongly convex (w.r.t the chosen norm $\norm{\cdot}$) function $h:Q\to \re \cup \{\infty\}$  that is differentiable on the interior of $Q$, $\breg{h}{u}{v}:=h(u)-h(v)-\inp{\nabla h(v)}{u-v}$ for all $u,v\in Q$.

Under the above setting and assumption, (<ref>) admits a simple generalization:

Similar triangle approximations of PPM for composite costs and general norms:

\begin{align}
&\textstyle y_{t} =\frac{\nicefrac{1}{L}}{\nicefrac{1}{L}+\ee_t } x_t+\frac{ \ee_t }{  \nicefrac{1}{L}+\ee_t } z_t\,, \label{simg:a}\\
&\textstyle x_{t+1} \leftarrow \argmin_{x\in Q} \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t} + \frac{1}{\ee_{t+1}} \breg{h}{x}{x_t} +\Psi(x) \right\}\,,\label{simg:b}\\
& \textstyle z_{t+1} =\frac{\nicefrac{1}{L}}{\nicefrac{1}{L}+\ee_t} x_{t+1}+\frac{ \ee_t }{\nicefrac{1}{L}+ \ee_t } z_t \,. \label{simg:c}
\end{align}

Again, the similar triangle approximation (<ref>) is computationally advantageous in that it only requires a single projection in each iteration. Now we provide a simple PPM-based analysis of (<ref>):

To obtain counterparts of (<ref>) and (<ref>), we now use a generalization of Proposition <ref> to the Bregman divergence (<cit.>).
With such a generalization,  we obtain the following inequality for  $\pss(x):=\ee_{t+1}[f(y_t)+\inp{\nabla f(y_t)}{x-y_t} +\Psi(x)]$:

\begin{align}
\pss(x_{t+1}) -\pss(\xs) +  \breg{h}{\xs}{x_{t+1}}+\breg{h}{x_{t+1}}{x_{t}}-
\breg{h}{\xs}{x_{t}} \leq 0\,, \label{gen:1}
\end{align}

where $\xs\in \argmin_{x\in Q}\fsi(x)$.
Now using (<ref>), one can derive from first principles the following inequalities   (we defer the derivations to Appendix <ref>):

\begin{align*}
\text{Counterpart of }\eqref{ineq:1}: &\quad \ee_{t+1}(\fsi(z_{t+1})- \fsi(\xs) ) + \breg{h}{\xs}{x_{t+1}}-
\breg{h}{\xs}{x_{t}} \leq \ggo \quad \text{and}\\
\text{Counterpart of }\eqref{ineq:2}: &\quad  \fsi(z_{t+1}) -\fsi(z_t) \leq \ggt\,,
\end{align*}

where $\ggo:=  \textstyle-\frac{1}{2}\norm{ x_{t+1}-x_t}^2  +\ee_{t+1}[\frac{L}{2}\norm{z_{t+1}-y_{t}}^2 +\inp{\nabla f(y_{t})}{z_{t+1}-x_{t+1}}   +\Psi(z_{t+1}) -\Psi(x_{t+1})]$ and $\ggt:= \frac{L}{2} \norm{z_{t+1}-y_t}^2 +  \inp{\nabla f(y_{t})}{z_{t+1}-z_t} +\Psi(z_{t+1})-\Psi(z_{t})$.
Similarly to Section <ref>, yet replacing the norm squared term with the Bregman divergence, we choose

\begin{align*}
\textstyle\Phi_t:= (\sum_{i=1}^{t} \ee_i)\cdot (\fsi(z_t)-\fsi(\xs)) +\breg{h}{\xs}{x_t}.
\end{align*}

Then, it suffices to show  $\ggo + ( \sum_{i=1}^t \ee_i)\cdot \ggt \leq 0$.
Using   the facts (i) $z_{t+1}-x_{t+1} = L\ee_t (z_t-z_{t+1})$ and (ii) $\norm{x_{t+1}-x_t}= (L\ee_t+1)\norm{z_{t+1}-y_t}$  (both are immediate consequences of the similar triangles) and rearranging, one can easily check that  $\ggo + ( \sum_{i=1}^t \ee_i)\cdot \ggt$ is equal to

\begin{align}
\textstyle     \frac{1}{2}\left(-(L\ee_t+1)^2 +L \ee_{t+1}+  L\sum_{i=1}^{t}\ee_{i} \right)\norm{z_{t+1}-y_{t}}^2 \label{a1}\\
\textstyle +\left(L\ee_t \ee_{t+1} - \sum_{i=1}^t\ee_i\right)\inp{\nabla f(y_{t})}{z_{t}-z_{t+1}} \label{a2}\\
\textstyle  +\ee_{t+1}[ \Psi(z_{t+1}) -\Psi(x_{t+1}) ] +   \left( \sum_{i=1}^t \ee_i\right)\cdot [\Psi(z_{t+1})-\Psi(z_{t})].
\label{a3}
\end{align}

Now choosing $\ee_t= \nicefrac{t}{2L}$ analogously to Section <ref>, one can easily verify  $\eqref{a1}+\eqref{a2}+\eqref{a3} \leq 0$.
Indeed, for (<ref>), since  $L  \ee_t \ee_{t+1}=\sum_{i=1}^t\ee_i$, the coefficient becomes $\nicefrac{1}{2}(L\ee_t+1)(L\ee_{t+1}-L\ee_t-1)$ which is a negative number since $L\ee_{t+1}-L\ee_t-1=-\nicefrac{1}{2}$;
for (<ref>), the coefficient becomes zero due to the relation $L  \ee_t \ee_{t+1}=\sum_{i=1}^t\ee_i$;
lastly, for (<ref>), we have

\begin{align}
\eqref{a3}=    \ee_{t+1}\left[ (1+L\ee_t) \Psi(z_{t+1}) -\Psi(x_{t+1}) -L\ee_{t}\Psi(z_{t})\right] \leq 0\,,
\end{align}

where the equality is due to the relation $L  \ee_t \ee_{t+1} =\sum_{i=1}^t\ee_i$, and the inequality is due to the update (<ref>) (which can be equivalently written as $(1+L\ee_t) z_{t+1} = x_{t+1}+ L\ee_t z_t$) and the convexity of $\Psi$.
Hence, we obtain the accelerated rate of  $\fsi(z_T)-\fsi(\xs)\leq \frac{4L\breg{h}{\xs}{x_0}}{T(T+1)} = O(\nicefrac{1}{T^2})$.

§ RELATED WORK

Motivated by the obscure scope of Nesterov's estimate sequence technique, there have been a flurry of works on developing alternative approaches to Nesterov's acceleration.
The most contributions are made based on understanding the continuous limit dynamics of Nesterov's AGM [28, 15, 33].
These continuous dynamics approaches have brought about new intuitions about Nesterov's acceleration, and follow-up works have developed analytical techniques for such dynamics [32, 11].
However, these approaches share a limitation that when applying discretization techniques to obtain optimization algorithms, some auxiliary modifications are required to recover/obtain analyzable algorithms.
In contrast, our PPM approach directly yields accelerated methods and does not require additional adjustments.

Another notable contribution is made based on the  linear coupling framework [2].
The main observation is that the two most popular first-order methods, namely gradient descent and mirror descent, have complementary performances, and hence, one can come up with a faster method by linearly coupling  the two methods.
This view indeed offers a general framework of developing fast optimization algorithms; however, for understanding Nesterov's acceleration, this view has less expressive power compared to  our PPM view.
More specifically, it is a priori  not clear why one needs to couple two methods linearly.
Moreover, with the linear coupling view, one cannot interpret the interpolation weight as we did in Remark <ref>.

It is also important to note that  PPM has been given new attention as a building block for designing and analyzing fast optimization methods [12].
To list few instances, PPM has given rise to methods  for weakly convex problems [10], the prox-linear methods for composite optimizations [5, 25, 19], accelerated methods for stochastic optimizations [16], and methods for saddle-point problems [22].
Moreover, using Proposition <ref> (and its generalization to the Bregman divergence) as a unified tool for analyzing  first-order methods has been discussed in [30].

§ CONCLUSION

This work provides a complete understanding of Nesterov's acceleration by making analytical and quantitative connections to the proximal point method.
The key observation is that an alternation of two simple approximations of the PPM exatly recovers Nesterov's AGM.
Through this connection, we are able to explain all the step sizes of AGM in terms of the PPM step sizes, demystifying the mysterious choices made in the literature.
This view naturally extends to the strongly convex case and recovers Nesterov's general accelerated method from his book.
Moreover, our PPM view  motivates a simplification of AGM using similar triangles, which admits a simple PPM-based analysis as well as a simple extension to the general norm and composite optimization case.
For future directions, it would be interesting to connect our PPM view to accelerated stochastic methods
[16, 20] and other accelerated methods, including geometric descent [7].

§ ACKNOWLEDGEMENT
The author thanks Suvrit Sra, Alp Yurtsever and   Jingzhao Zhang  for detailed comments and stimulating discussions, Aaron Defazio for clarifications that help the author develop Section <ref>, and  Heinz Bauschke for constructive suggestions on the presentation of Section <ref> as well as Remark <ref>.

[1]
Kwangjun Ahn and Suvrit Sra.
From Nesterov's estimate sequence to Riemannian acceleration.
arXiv preprint: 2001.08876, 2020.

[2]
Zeyuan Allen-Zhu and Lorenzo Orecchia.
Linear coupling: An ultimate unification of gradient and mirror
In 8th Innovations in Theoretical Computer Science Conference
(ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

[3]
Stephen Becker, Jérôme Bobin, and Emmanuel J Candès.
NESTA: A fast and accurate first-order method for sparse recovery.
SIAM Journal on Imaging Sciences, 4(1):1–39, 2011.

[4]
Heinz H Bauschke and Patrick L Combettes.
Convex analysis and monotone operator theory in Hilbert
spaces, volume 408.
Springer, 2011.

[5]
James V Burke and Michael C Ferris.
A Gauss-Newton method for convex composite optimization.
Mathematical Programming, 71(2):179–194, 1995.

[6]
Nikhil Bansal and Anupam Gupta.
Potential-function proofs for gradient methods.
Theory of Computing, 15(4):1–32, 2019.

[7]
Sébastien Bubeck, Yin Tat Lee, and Mohit Singh.
A geometric alternative to Nesterov's accelerated gradient descent.
arXiv preprint: 1506.08187, 2015.

[8]
Amir Beck and Marc Teboulle.
A fast iterative shrinkage-thresholding algorithm for linear inverse
SIAM journal on imaging sciences, 2(1):183–202, 2009.

[9]
Aaron Defazio.
On the curved geometry of accelerated optimization.
In Advances in Neural Information Processing Systems, pages
1764–1773, 2019.

[10]
Damek Davis and Benjamin Grimmer.
Proximally guided stochastic subgradient method for nonsmooth,
nonconvex problems.
SIAM Journal on Optimization, 29(3):1908–1930, 2019.

[11]
Jelena Diakonikolas and Lorenzo Orecchia.
The approximate duality gap technique: A unified theory of
first-order methods.
SIAM Journal on Optimization, 29(1):660–689, 2019.

[12]
Dmitriy Drusvyatskiy.
The proximal point method revisited.
arXiv preprint: 1712.06038, 2017.

[13]
Alexander Vladimirovich Gasnikov and Yu E Nesterov.
Universal method for stochastic composite optimization problems.
Computational Mathematics and Mathematical Physics,
58(1):48–64, 2018.

[14]
Osman Güler.
On the convergence of the proximal point algorithm for convex
SIAM Journal on Control and Optimization, 29(2):403–419, 1991.

[15]
Walid Krichene, Alexandre Bayen, and Peter L Bartlett.
Accelerated mirror descent in continuous and discrete time.
In Advances in Neural Information Processing Systems, pages
2845–2853, 2015.

[16]
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui.
A universal catalyst for first-order optimization.
In Advances in Neural Information Processing Systems, pages
3384–3392, 2015.

[17]
Laurent Lessard, Benjamin Recht, and Andrew Packard.
Analysis and design of optimization algorithms via integral quadratic
SIAM Journal on Optimization, 26(1):57–95, 2016.

[18]
Yin Tat Lee, Satish Rao, and Nikhil Srivastava.
A new approach to computing maximum flows using electrical flows.
In Proceedings of the forty-fifth annual ACM Symposium on Theory
of Computing, pages 755–764, 2013.

[19]
Adrian S Lewis and Stephen J Wright.
A proximal method for composite minimization.
Mathematical Programming, 158(1-2):501–546, 2016.

[20]
Guanghui Lan and Yi Zhou.
An optimal randomized incremental gradient method.
Mathematical programming, 171(1-2):167–215, 2018.

[21]
Bernard Martinet.
Régularisation d’inéquations variationnelles par
approximations successives. rev. française informat.
Recherche Opérationnelle, 4:154–158, 1970.

[22]
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil.
A unified analysis of extra-gradient and optimistic gradient methods
for saddle point problems: proximal point approach.
arXiv preprint: 1901.08511, 2019.

[23]
Jean-Jacques Moreau.
Proximité et dualité dans un espace Hilbertien.
Bulletin de la Société mathématique de France,
93:273–299, 1965.

[24]
Yurii Nesterov.
A method for unconstrained convex minimization problem with the rate
of convergence $O(1/k^{2})$.
In Doklady AN USSR, volume 269, pages 543–547, 1983.

[25]
Yu Nesterov.
Modified Gauss-Newton scheme with worst case guarantees for
global performance.
Optimisation methods and software, 22(3):469–483, 2007.

[26]
Yurii Nesterov.
Lectures on convex optimization, volume 137.
Springer, 2018.

[27]
R Tyrrell Rockafellar.
Monotone operators and the proximal point algorithm.
SIAM journal on control and optimization, 14(5):877–898, 1976.

[28]
Weijie Su, Stephen Boyd, and Emmanuel J Candes.
A differential equation for modeling Nesterov's accelerated
gradient method: theory and insights.
The Journal of Machine Learning Research, 17(1):5312–5354,

[29]
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton.
On the importance of initialization and momentum in deep learning.
In International Conference on Machine Learning, pages
1139–1147, 2013.

[30]
Marc Teboulle.
A simplified view of first order methods for optimization.
Mathematical Programming, 170(1):67–96, 2018.

[31]
Paul Tseng.
On accelerated proximal gradient methods for convex-concave
submitted to SIAM Journal on Optimization, 2008.

[32]
Ashia C Wilson, Benjamin Recht, and Michael I Jordan.
A Lyapunov analysis of momentum methods in optimization.
arXiv preprint: 1611.02635, 2016.

[33]
Andre Wibisono, Ashia C Wilson, and Michael I Jordan.
A variational perspective on accelerated methods in optimization.
Proceedings of the National Academy of Sciences,
113(47):E7351–E7358, 2016.

§ DEFERRED DERIVATIONS FROM SECTION <REF>

Counterpart of  (<ref>). Apply Proposition <ref> with $\phi(x)=\ee_{t+1}[f(y_{t})+\inp{\nabla f(y_{t})}{x-y_{t}}]$ to (<ref>):

\begin{align}
\phi(x_{t+1})-\phi(\xs) +\frac{1}{2}\norm{\xs-x_{t+1}}^2 +\frac{1}{2}\norm{ x_{t+1}-x_t}^2  -\frac{1}{2}\norm{\xs-x_t}^2\leq 0\,. \label{ineq:basic}
\end{align}

Now from the convexity, we have $\phi(\xs) \leq \ee_{t+1} f(\xs)$, and from the $L$-smoothness, we have

\begin{align*}
\phi(x_{t+1})&= \ee_{t+1}[f(y_{t})+\inp{\nabla f(y_{t})}{z_{t+1}-y_{t}}+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}}]\\
&\geq \ee_{t+1} \left[f(z_{t+1}) -\frac{L }{2}\norm{z_{t+1}-y_t}^2+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}} \right]\,.
\end{align*}

Plugging these inequalities back to (<ref>) and rearranging, we obtain the following inequality:

\begin{align}
&\ee_{t+1}[f(z_{t+1})-f(\xs)] +\frac{1}{2}\norm{\xs-x_{t+1}}^2  -\frac{1}{2}\norm{\xs-x_t}^2 \nonumber\\
&\leq-\frac{1}{2}\norm{ x_{t+1}-x_t}^2  +\ee_{t+1}\left[ \frac{L}{2}\norm{z_{t+1}-y_t}^2 +  \inp{\nabla f(y_{t})}{z_{t+1}-x_{t+1}}\right]\,. \label{exp:1}
\end{align}

Now decomposing the inner product term  in (<ref>) into

$\ee_{t+1}\inp{\nabla f(y_{t})}{ z_{t+1}-y_t} +\ee_{t+1}\inp{\nabla f(y_{t})}{ y_t-x_t}+\ee_{t+1}\inp{\nabla f(y_{t})}{ x_t-x_{t+1}}$,

and using $x_{t+1}-x_t=-\ee_{t+1} \nabla f(y_t)$ and $z_{t+1}-y_t=-\nicefrac{1}{L} \nabla f(y_t)$ (which are (<ref>) and (<ref>), respectively),  (<ref>) becomes

\begin{align*}
\left(\frac{\ee_{t+1}^2}{2}-\frac{\ee_{t+1}}{2L}\right) \norm{\nabla f(y_{t})}^2 + \ee_{t+1}\inp{\nabla f(y_{t})}{ y_{t}-x_t}\,.
\end{align*}

Now, using the relation $y_{t}-x_t  =L\ee_t (z_t-y_t)$ (which is  (<ref>)), we obtain $\ffo$.

Counterpart of (<ref>). It readily follows from the $L$-smoothness and the convexity of $f$:

\begin{align*}
f(z_{t+1}) -f(z_t) &= f(z_{t+1}) -f(y_{t})+f(y_{t})-f(z_t)\\ &\leq  \inp{\nabla f(y_{t})}{z_{t+1}-y_t}  +\frac{L}{2} \norm{z_{t+1}-y_t}^2+ \inp{\nabla f(y_{t})}{y_{t}-z_t}\\
&\overset{(a)}{=}   -\frac{1}{2L} \norm{\nabla f(y_{t})}^2+ \inp{\nabla f(y_{t})}{y_{t}-z_t}=\fft,
\end{align*}

where ($a$) is due to $z_{t+1}-y_t=-\nicefrac{1}{L} \nabla f(y_t)$.

§ DEFERRED DERVIATIONS FROM SECTION <REF>

Counterpart of  (<ref>).  From convexity, we have $\pss(\xs) \leq \ee_{t+1} \fsi(\xs)$, and from the $L$-smoothness, we have the following lower bound:

\begin{align*}
\pss(x_{t+1})&= \ee_{t+1}[f(y_{t})+\inp{\nabla f(y_{t})}{z_{t+1}-y_{t}}+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}} +\Psi(x_{t+1})]\\
&\geq \ee_{t+1} \left[\fsi (z_{t+1}) -\frac{L }{2}\norm{z_{t+1}-y_t}^2+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}}  + \Psi(x_{t+1})-\Psi(z_{t+1}) \right]\,.
\end{align*}

Plugging these back to  (<ref>), and using  the bound $- \breg{h}{x_{t+1}}{x_t}\leq -\frac{1}{2}\norm{x_{t+1}-x_t}^2$, we obtain:

\begin{align*}
&\ee_{t+1}(\fsi(z_{t+1})- \fsi(\xs) ) + \breg{h}{\xs}{x_{t+1}}-
\breg{h}{\xs}{x_{t}}\\
&\leq \textstyle-\frac{1}{2}\norm{ x_{t+1}-x_t}^2  +\ee_{t+1}\left[\frac{L}{2}\norm{z_{t+1}-y_{t}}^2 +\inp{\nabla f(y_{t})}{z_{t+1}-x_{t+1}}   +\Psi(z_{t+1}) -\Psi(x_{t+1})\right]\,,
\end{align*}

which is precisely equal to $\ggo$.

Counterpart of  (<ref>). We use $L$-smoothness and the convexity of $f$ to obtain the following:

\begin{align*}
&\fsi(z_{t+1}) -\fsi(z_t) \leq  f(z_{t+1})-f(y_t)+f(y_t)-f(z_t) +\Psi(z_{t+1})-\Psi(z_t)\\
&\leq   \frac{L}{2} \norm{z_{t+1}-y_t}^2 +  \inp{\nabla f(y_{t})}{z_{t+1}-z_t} +\Psi(z_{t+1})-\Psi(z_{t})\,,
\end{align*}

which is precisely equal to $\ggt$.

§ DETAILS FOR REMARK <REF>

We first develop counterparts of (<ref>) and (<ref>):

Counterpart of  (<ref>). By the updates (<ref>), we have $x_{t+1} = x_t -(\ee_t +\frac{1}{L})\nabla f(y_t)$.
Letting $\eep_{t+1} :=\ee_t+\frac{1}{L}$, this relation can be equivalently written as:

\begin{align}
\label{sim2:ppm} \textstyle x_{t+1} \leftarrow \argmin_{x} \left\{ f(y_t)+\inp{\nabla f(y_t)}{x-y_t}  + \frac{1}{2\eep_{t+1}} \norm{x-x_t}^2 \right\}
\end{align}

The rest is similar to Appendix <ref>: we apply Proposition <ref> with $\phi(x)=\eep_{t+1}[f(y_{t})+\inp{\nabla f(y_{t})}{x-y_{t}}]$:

\begin{align}
\phi(x_{t+1})-\phi(\xs) +\frac{1}{2}\norm{\xs-x_{t+1}}^2 +\frac{1}{2}\norm{ x_{t+1}-x_t}^2  -\frac{1}{2}\norm{\xs-x_t}^2\leq 0\,. \label{ineq:basic2}
\end{align}

Now from the convexity, we have $\phi(\xs) \leq \eep_{t+1} f(\xs)$, and from the $L$-smoothness, we have

\begin{align*}
\phi(x_{t+1})&= \eep_{t+1} [f(y_{t})+\inp{\nabla f(y_{t})}{z_{t+1}-y_{t}}+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}}]\\
&\geq \eep_{t+1} \left[f(z_{t+1}) -\frac{L }{2}\norm{z_{t+1}-y_t}^2+\inp{\nabla f(y_{t})}{x_{t+1}-z_{t+1}} \right]\,.
\end{align*}

Plugging these inequalities back to (<ref>) and rearranging, we obtain the following inequality:

\begin{align}
&\eep_{t+1}[f(z_{t+1})-f(\xs)] +\frac{1}{2}\norm{\xs-x_{t+1}}^2  -\frac{1}{2}\norm{\xs-x_t}^2 \nonumber\\
&\leq-\frac{1}{2}\norm{ x_{t+1}-x_t}^2  +\eep_{t+1}\left[ \frac{L}{2}\norm{z_{t+1}-y_t}^2 +  \inp{\nabla f(y_{t})}{z_{t+1}-x_{t+1}}\right] \nonumber\\
&=\frac{1}{2}\left(  -(L\ee_t+1)^2   +L\eep_{t+1}\right)\cdot \norm{z_{t+1}-y_t}^2 +  \eep_{t+1}\cdot \inp{\nabla f(y_{t})}{z_{t+1}-x_{t+1}} =:\hho\,, \label{exp:12}
\end{align}

where the last line follows since $\norm{x_{t+1}-x_t} = (L\ee_t+1)\cdot \norm{z_{t+1}-z_t}$ (see Figure <ref>).

Counterpart of (<ref>). It is identical to  Appendix <ref>: From the $L$-smoothness and the convexity of $f$:

\begin{align*}
f(z_{t+1}) -f(z_t) &= f(z_{t+1}) -f(y_{t})+f(y_{t})-f(z_t)\\ &\leq  \inp{\nabla f(y_{t})}{z_{t+1}-y_t}  +\frac{L}{2} \norm{z_{t+1}-y_t}^2+ \inp{\nabla f(y_{t})}{y_{t}-z_t}\\
&=  \frac{L}{2} \norm{z_{t+1}-y_t}^2+ \inp{\nabla f(y_{t})}{z_{t+1}-z_t}=:\hht\,.
\end{align*}

Having established the counterparts of (<ref>) and (<ref>), following Section <ref>, we choose

\begin{align}
\textstyle \Phi_t:= (\sum_{i=1}^{t} \eep_i)\cdot (f(z_t)-f(\xs)) + \frac{1}{2}\norm{\xs-x_t}^2\,. \label{lya2:2}
\end{align}

To prove the validity of the chosen Lyapunov function, it suffices to verify

\begin{align} \label{suff:2}
\textstyle    \hho + ( \sum_{i=1}^t \eep_i)\cdot \hht \leq 0
\end{align}

which is equivalent to (since $z_{t+1}-x_{t+1} = -L\ee_t (z_{t+1}-z_t) $)

\begin{align}
\label{cond:1:2} \textstyle \frac{1}{2}\left(  -(L\ee_t+1)^2     +\sum_{i=1}^{t+1} L\eep_i \right)\cdot \norm{z_{t+1}-y_t}^2 + \left( L\ee_t\eep_{t+1} - \sum_{i=1}^t \eep_i\right)\inp{\nabla f(y_{t})}{z_{t+
1}-z_t} \leq 0\,.
\end{align}

From (<ref>), it suffices to choose $\{\ee_t\}$ so that $L\ee_t\eep_{t+1}=\sum_{i=1}^t \eep_i$.
Indeed, with such a choice, the coefficient of the inner product term in (<ref>) becomes zero and the coefficient of the squared norm term becomes

\begin{align*}
\textstyle \frac{1}{2}\left(  -(L\ee_t+1)^2     +\sum_{i=1}^{t+1} L\eep_i \right)&= \frac{1}{2}\left(  -(L\ee_t+1)^2     +L\eep_{t+1}+ L\eep_{t+1}\cdot L\ee_t\right) \\
&\textstyle= \frac{1}{2}\left(  -(L\ee_t+1)^2     +L\eep_{t+1} (L\ee_t+1) \right) =0
\end{align*}

since $L\eep_{t+1} = L\ee_t+1$.
Indeed, one can actually simplify the relation $L\ee_t\eep_{t+1}=\sum_{i=1}^t \eep_i$:

\begin{align*}
\textstyle L\ee_{t+1} \cdot (L\ee_{t+1}+1)= L\ee_{t+1}\cdot L\eep_{t+2}=\sum_{i=1}^{t+1} L\eep_i  = L\eep_{t+1} + L\ee_{t}\cdot L\eep_{t+1} = (L\ee_{t}+1)^2\,.
\end{align*}

After rearranging, we obtain the recursive relation:
$(L\ee_{t+1}+\frac{1}{2})^2= (L\ee_t+1)^2 +\frac{1}{4}$, which after the substitution $L\ee_t+1= a_t$ exactly recovers the popular recursive relation $a_{t+1} = \frac{1+\sqrt{1+4a_t^2}}{2}$ in [24, 8].