 for this simple case--- \cite{kingma2014adam} normalize the sum above  by $\frac{\beta^{k+1}-1}{\beta -1}$, showing significant benefits in the experimental section. Indeed, such normalization retains all the celebrated geometric properties of momentum (see Introduction), while improving statistical accuracy  ---a crucial feature of SGD. For convenience of the reader, we report below the full Adam algorithm.

 \begin{tcolorbox}
 Initialize $m_0=v_0=0$ and choose initial estimate $x_0$. Let "$\circ$" denote the element-wise product.
 \begin{equation}
 \tag{ADAM}
     \begin{cases} 
      m_{k+1} &= \beta_1 m_k + (1-\beta_1) \nabla f(x_k) \\
      v_{k+1} &= \beta_2 v_k + (1-\beta_2) \nabla f_k^{\circ 2}(x_k) \\
        \hat m_{k+1} &= m_{k+1}/ (1-\beta_1)^{k+1} \\
            \hat v_{k+1} &= v_{k+1}/ (1-\beta_2)^{k+1} \\
                       x_{k+1} &= x_{k} - \eta \frac{\hat m_k}{\sqrt{\hat v_k +\epsilon}} \\
   \end{cases}
   \label{eq:adam}
\end{equation}
 \end{tcolorbox}



In addition, such normalization also performs variance reduction. Indeed, let $\Sigma := \var\left[\nabla f_{i}(x)\right]$ be the gradient covariance, which we assume constant and finite for simplicity. Then,
\begin{align*}
    \var\left[\frac{\beta-1}{\beta^{k+1}-1}\sum_{j=0}^{k} \beta^{k-j} \nabla f_{i_j}(x_j)\right]&= \frac{(\beta-1)^2}{(\beta^{k+1}-1)^2}\sum_{j=0}^{k} \beta^{2(k-j)} \Sigma\\ &= \frac{(\beta-1)^2}{(\beta^{k+1}-1)^2}\frac{\beta^{2(k+1)}-1}{\beta^2-1}\Sigma\\&= \frac{\beta-1}{(\beta^{k+1}-1)}\frac{\beta^{k+1}+1}{\beta+1}\Sigma \preceq \Sigma.\\
\end{align*}

Note that if $k$ increases, the covariance monotonically decreases until reaching the minimum $\frac{1-\beta}{\beta+1}\Sigma$ at infinity. We also note that, in case $\beta = 0$ (Gradient Descent) we have no variance reduction, as expected.

Supported by the empirical success of Adam\cite{kingma2014adam}, we suggest in the main paper to modify the standard Heavy Ball (\ref{HB-SUM}) with constant momentum to match the Adam update:
 \begin{equation}
    x_{k+1} = x_k - \eta \frac{\beta-1}{\beta^{k+1}-1} \sum_{j=0}^{k} \beta^{k-j} \nabla f(x_j).
     \label{HB-sum_modified}
 \end{equation}
 
 Which can be written recursively using 3 variables (see again \cite{kingma2014adam}). Notice that, after a relatively small number of iterations, we converge to the simpler update rule
 $$x_{k+1} = x_k + \beta (x_k-x_{k-1}) - \eta(1-\beta)\nabla f(x_k),$$
 
 which is also the starting point in some recent elaboration on Heavy Ball \cite{ma2018quasi}. 


\section{Time-warping, acceleration and gradient amplification}

\subsection{Counterexample for existence of a solution of \ref{MG-ODE} starting integration at 0}
\label{app:counterexample}
Consider the one dimensional dynamics with gradients always equal to one and ${\mathfrak{m}}(t) = t^3$. The \ref{MG-ODE} (see main paper) reads $\ddot X(t) + \frac{3}{t} \dot X + \frac{3}{t} = 0$. It is easy to realize using a Cauchy-Euler argument that all solutions are of the form $X(t) = \frac{c_1}{t^2} + c_2 - t$. Unfortunately, the constraint $X(0)=x_0$ fixes both the degrees of freedom and fixes $X(t) = x_0-t$, so that we necessarily have $\dot X(0) = -1$.


  \subsection{Variational point of view}
  \label{lagrangian}
Let $X\in{\mathcal C}^1([t_1,t_2],{\mathbb{R}}^d)$ be a curve; the action (see \cite{arnol2013mathematical} for the precise definition) associated with a Lagrangian $\mathcal{L}:{\mathbb{R}}^d\times{\mathbb{R}}^d\times{\mathbb{R}}\to{\mathbb{R}}$ is $\int_{t_1}^{t_2}\mathcal{L}(X(s),\dot X(s), s) ds$. The fundamental result in variational analysis states that the curve $X$ is a stationary point for the action only if it solves the Euler-Lagrange equation $\frac{d}{dt}\partial_{\dot X} \mathcal{L}(X(t),\dot X(t), t) = \partial_{X} \mathcal{L}(X(t),\dot X(t), t)$. We define the \textit{Memory Lagrangian} as
$$\boxed{\mathcal{L}_{\mathfrak{m}}(X,\dot X,t) := \frac{1}{2}{\mathfrak{m}}(t)\|\dot X\|^2-\dot{\mathfrak{m}}(t) f(X)}.$$
It is straightforward to verify that the associated Euler-Lagrange equations give rise to \ref{MG-ODE}. We cannot help but noticing the striking simplicity of this Lagrangian when compared to others arising from momentum methods (see e.g. the Bregman Lagrangian in \cite{wibisono2016variational}). For the sake of delivering other points in this paper, we leave the analysis of  the symmetries of $\mathcal{L}_{\mathfrak{m}}$ to future work.


\subsection{Time-warping of memory: a general correspondence to \ref{HB-ODE}}
\label{time}
Consider the ODE $\boxed{\ddot X(t) + \frac{\dot{\mathfrak{m}}(t)}{{\mathfrak{m}}(t)}\dot X(t) + \frac{\dot{\mathfrak{m}}(t)}{{\mathfrak{m}}(t)}\nabla f(X)=0}$ and the time change $\tau(t)$. 

Let $Y(t) = X(\tau(t))$, following \cite{wibisono2016variational} we have, by the chain rule, 
\begin{equation*}
    \dot Y(t) = \dot X(\tau(t))\dot\tau(t);\ \ \ \ \ \ \ \
    \ddot Y(t) = \dot X(\tau(t))\ddot\tau(t) + (\dot\tau(t))^2\ddot X(\tau(t)).\\
\end{equation*}

Therefore, we have
\begin{equation*}
    \dot X(\tau(t)) = \frac{\dot Y(t)}{\dot\tau(t)};\ \ \ \ \ \ \ \
    \ddot X(\tau(t)) = \frac{\ddot Y(t)}{(\dot\tau(t))^2}-\frac{\ddot \tau(t)}{(\dot\tau(t))^3} \dot Y(t).\\
\end{equation*}

Next, we construct a new ODE for $Y$ using the previous formulas:
$$\frac{1}{(\dot\tau(t))^2}\ddot Y(t) + \left(\frac{\dot{\mathfrak{m}}(\tau(t))}{\dot\tau(t) {\mathfrak{m}}(\tau(t))} - \frac{\ddot \tau(t)}{(\dot\tau(t))^3}\right)\dot Y(t) + \frac{\dot {\mathfrak{m}}(\tau(t))}{{\mathfrak{m}}(\tau(t))}\nabla f(X(\tau(t)));$$

Next, we multiply everything by ${\mathfrak{m}}(\tau(t))/\dot{\mathfrak{m}}(\tau(t))$, in order to eliminate the coefficient in front of the gradient:

$$\frac{{\mathfrak{m}}(\tau(t))}{\dot{\mathfrak{m}}(\tau(t))(\dot\tau(t))^2}\ddot Y(t) + \left(\frac{1}{\dot\tau(t)} - \frac{{\mathfrak{m}}(\tau(t))\ddot \tau(t)}{\dot{\mathfrak{m}}(\tau(t))(\dot\tau(t))^3}\right)\dot Y(t) + \