
There are two practical ways to choose the parameter sequence \(\lbrace \beta _{1t}\rbrace \) : (1) \(\beta _{1t}=\beta _1\cdot \lambda ^{t-1}\)  where \(\beta _1,\lambda \in (0,1)\)  and (2) \(\beta _{1t}=1/t\) . In both settings, \(\sum _{t=1}^{N}\beta _{1t}^2=\mathcal {O}(1)\)  and \(\sum _{t=1}^{N}\beta _{1t}=\widetilde{\mathcal {O}}(1)\) . Therefore, we can conclude from Theorem REF  that:
\(\mathbb {E}\Vert V(z)\Vert _2^2\leqslant \mathcal {O}(d/N)+\mathcal {O}(1/N)\cdot \sum _{t=1}^{N}1/M_t\)  holds after regarding \(D,G,\delta ,\eta \)  as constants.

When the batch sizes \(M_k\)  are constant, let \(M_k=\Theta (1/\varepsilon ^2)\) . To guarantee \(\mathbb {E}\Vert V(z)\Vert _2^2\leqslant \varepsilon ^2\) , the total number of iterations should be \(N=\mathcal {O}(d\varepsilon ^{-2})\)  and the total complexity is \(\sum _{k=0}^{N}M_k=\mathcal {O}(d\varepsilon ^{-4})\) . When the batch sizes \(M_k\)  are increasing, let \(M_k=k+1\) . To guarantee \(\mathbb {E}\Vert V(z)\Vert _2^2\leqslant \varepsilon ^2\) , the total number of iterations should be \(N=\widetilde{\mathcal {O}}(d\varepsilon ^{-2})\)  and the total complexity is \(\sum _{k=0}^{N}M_k=\widetilde{\mathcal {O}}(d^2\varepsilon ^{-4})\) . Obviously, using constant batch sizes obtains a better total complexity.

In the deterministic setting, the first-order oracle directly outputs the accurate gradient \(V(z;\xi )=V(z)\) , which means \(\sigma =0\) . Theorem REF  leads to \(\mathbb {E}\Vert V(z)\Vert _2^2\leqslant \mathcal {O}(d/N)\) . To guarantee \(\mathbb {E}\Vert V(z)\Vert _2^2\leqslant \varepsilon ^2\) , the total number of iterations should be \(N=\mathcal {O}(d\varepsilon ^{-2})\) .

In the AMSGrad-EG algorithm, the momentum term is a technical difficulty on the convergence proof. Proofs in the past works always use the MVI condition or convex condition like
\(\langle V(z_k), z_k-z^*\rangle \leqslant 0~\Rightarrow \langle g_k, z_k-z^*\rangle \lessapprox 0\)  to control the gradient norms. However, if we replace \(g_k\)  with the momentum term \(m_k\) , the inequality above will no longer hold, and then we have to find another way to control the upper bound of gradient norms. It's also worth mentioned that our proof can't be extended to Optimistic Adam (OAdam) since we need to guarantee that \(H_1\preceq H_2\preceq \ldots \)  in our proof. Actually, Adam may not even converge in convex case [1]}.

Comparison with OAdaGrad: [2]} proposes the Optimistic AdaGrad (OAdaGrad) algorithm and gives a convergence analysis on under Assumption REF , REF  and Bounded Cumulative Gradient Assumption (which assumes the existence of a constant \(0\leqslant \delta \leqslant 1/2\)  such that the cumulative gradients are bounded as \(\Vert \hat{g}_{1:k,i}\Vert _2\leqslant \delta k^{\alpha }\)  for all \(k\) ). Under these assumptions, they conclude that:
\(\frac{1}{N}\sum _{k=1}^{N}\mathbb {E}\Vert V(z_k)\Vert _{H_{k-1}^{-1}}^{2}\leqslant \mathcal {O}(1/N^{1-\alpha }).\) 
On one hand, notice that \(\frac{1}{N}\sum _{k=1}^{N}\mathbb {E}\Vert V(z_k)\Vert _{H_{k-1}^{-1}}^2\)  is the average of the norms of \(V(z_k)\) . However, the norm keeps changing. Since \(H_{k-1}^{-1}\)  keeps decreasing and may limit to 0 as \(k\rightarrow \infty \) , its unclear what is the real convergence rate in terms of the size of the gradient. It would be more convincing if we can upper bound the average of constant norms like \(\frac{1}{N}\sum _{k=1}^{N}\mathbb {E}\Vert V(z_k)\Vert _2^2\) . On the other hand, the Bounded Cumulative Assumption though widely used in related papers [3]}, [1]}, [5]}, is actually a very strong assumption: Under this assumption, it holds that \(\Vert \hat{g}_{1:k, i}\Vert _2\leqslant \delta k^{\alpha }\) , which naturally leads to:
\(\frac{1}{N}\sum _{k=1}^{N}\mathbb {E}\Vert V(z_k)\Vert _2^2\leqslant \frac{1}{N}\sum _{k=1}^{N}\mathbb {E}\Vert \hat{g}_k\Vert _2^2\leqslant \mathcal {O}\left(\frac{d}{N^{1-2\alpha }}\right).\) 
It causes a possible circularity about the argument. In this paper, we successfully overcome these two shortcomings.

