A new regret analysis for Adam-type algorithms

Introduction

One of the most popular optimization algorithms for training neural networks is Adam (Kingma & Ba, 2014), which is a variant of the general class of Adagrad-type algorithms (Duchi et al., 2011). The main novelty of Adam is to apply an exponential moving average (EMA) to gradient estimate (first-order) and to element-wise square-of-gradients (second-order), with parameters $\beta_{1}$ and $\beta_{2}$, respectively.

In practice, constant $\beta_{1}$ and $\beta_{2}$ values are used (the default parameters in PyTorch and Tensorflow, for example, are $\beta_{1}=0.9$ and $\beta_{2}=0.999$). However, the regret analysis in Kingma & Ba (2014) requires $\beta_{1}\to 0$ with a linear rate, causing a clear discrepancy between theory and practice.

Recently, it has been shown by Reddi et al. (2018) that the analysis of Adam contained a technical issue. After this discovery, many variants of Adam were proposed with optimal regret guarantees (Reddi et al., 2018; Chen & Gu, 2018; Huang et al., 2019). Unfortunately, in all these analyses, the requirement of $\beta_{1}\to 0$ is inherited and is needed to derive the optimal $\mathcal{O}(\sqrt{T})$ regret. In contrast, methods that are shown to exhibit favorable practical performance continued to use a constant $\beta_{1}$ in the experiments.

One can wonder whether there is an inherent obstacle — in the proposed methods or the setting — which prohibits optimal regret bounds with a constant $\beta_{1}$.

In this work, we show that this specific discrepancy between the theory and practice is indeed an artifact of the previous analyses. We point out the shortcomings responsible for this artifact, and then introduce a new analysis framework that attains optimal regret bounds with constant $\beta_{1}$ at no additional cost (and even comes with better constants in the obtained bounds).

Our contributions. In the convex setting, our technique obtains data-dependent \mathcal{O}\big{(}\sqrt{T}\big{)} regret bounds for AMSGrad and AdamNc (Reddi et al., 2018). Moreover, our technique can also be applied to a strongly convex variant of AdamNc, known as Sadam (Wang et al., 2020), yielding again data-dependent logarithmic regret with constant $\beta_{1}$. To the best of our knowledge, these are the first optimal regret bounds with constant $\beta_{1}$.

Finally, we illustrate the flexibility of our framework by applying it to zeroth-order (bandit) and nonconvex optimization. In the zeroth-order optimization setting, we improve on the current best result which requires $\beta_{1}\sim\frac{1}{t}$, and show that a constant $\beta_{1}$ again suffices. In the non-convex setting, we recover the existing results in the literature, with a simpler proof and slight improvements in the bounds.

2 Preliminaries

and a weighted projection operator onto $\mathcal{X}$

Related work

In the setting of online convex optimization (OCO), Assumption 1.1 is standard (Hazan et al., 2016; Duchi et al., 2011). It allows us to consider nonsmooth stochastic minimization (though we are not limited to this setting), and even allows for adversarial loss functions.

The algorithms AMSGrad and AdamNc were proposed by Reddi et al. (2018) to fix the issue in the original proof of Adam (Kingma & Ba, 2014). However, as the proof template of Reddi et al. (2018) follows very closely the proof of Kingma & Ba (2014), the requirement for $\beta_{1}\to 0$ remains in all the regret guarantees of these algorithms. In particular, as noted by Reddi et al. (2018, Corollary 1, 2), a schedule of $\beta_{1t}=\beta_{1}\lambda^{t-1}$ is needed for obtaining optimal regret. Reddi et al. (2018) also noted that regret bounds of the same order can be obtained by setting $\beta_{1t}=\beta_{1}/t$. On the other hand, in the numerical experiments, a constant value $\beta_{1t}=\beta_{1}$ is used consistent with the huge literature following Kingma & Ba (2014).

Following Reddi et al. (2018), there has been a surge of interest in proposing new variants of Adam with good practical properties; to name a few, Padam by Chen & Gu (2018), Adabound and Amsbound by Luo et al. (2019); Savarese (2019), Nostalgic Adam by Huang et al. (2019). As the regret analyses of these methods follow very closely the analysis of Reddi et al. (2018), the resulting bounds inherited the same shortcomings. In particular, in all these algorithms, to achieve \mathcal{O}\big{(}\sqrt{T}\big{)} regret, one needs either $\beta_{1t}=\beta_{1}\lambda^{t-1}$ or $\beta_{1t}=\frac{\beta_{1}}{t}$. On the other hand, the experimental results reported on these algorithms note that a constant value of $\beta_{1}$ is used in practice in order to obtain better performance.

Similar issues are present in other problem settings. For strongly convex optimization, Wang et al. (2020) proposed the Sadam algorithm as a variant of AdamNc, which exploits strong convexity to obtain \mathcal{O}\big{(}\log T\big{)} regret. Sadam was shown to exhibit favorable practical performance in the experimental results of Wang et al. (2020). However, the same discrepancy exists as with previous Adam variants: a linearly decreasing $\beta_{1t}$ schedule is required in theory but a constant $\beta_{1t}=\beta_{1}$ is used in practice.

One work that tried to address this issue is that of Fang & Klabjan (2019), where the authors focused on OCO with strongly convex loss functions and derived an $\mathcal{O}(\sqrt{T})$ regret bound with a constant value of $\beta_{1}\leq\frac{\mu\alpha}{1+\mu\alpha}$, where $\mu$ is the strong convexity constant and $\alpha$ is the step size that is set as $\alpha_{1}/\sqrt{T}.$ (Fang & Klabjan, 2019, Theorem 2). However, this result is still not satisfactory, since the obtained bound for $\beta_{1}$ is weak: both strong convexity $\mu$ and the step size $\frac{\alpha_{1}}{\sqrt{T}}$ are small. This does not allow for the standard choices of $\beta_{1}\in(0.9,0.99)$.

Moreover, a quick look into the proof of Fang & Klabjan (2019, Theorem 2) reveals that the proof in fact follows the same lines as Reddi et al. (2018) with the difference of using the contribution of strong convexity to get rid of the spurious terms that require $\beta_{1}\to 0$. Therefore, it is not surprising that the theoretical bound for $\beta_{1}$ depends on $\mu$ and $\alpha$ and can only take values close to . Second, in addition to the standard Assumption 1.1, Fang & Klabjan (2019) also assumes strong convexity, which is a quite stringent assumption by itself. In contrast, our approach does not follow the lines of Reddi et al. (2018), but is an alternative way that does not encounter the same roadblocks.

2 Nonconvex world

A related direction to what we have reviewed in the previous subsection is to analyze Adam-type algorithms without convexity assumptions. When convexity is removed, the standard setting in which the algorithms are analyzed, is stochastic optimization with a smooth loss function and no constraints (Chen et al., 2019a; Zhou et al., 2018; Zou et al., 2019). As a result, these algorithms, compared to the convex counterparts, do not perform projections in the update step of $x_{t+1}$ (cf., Algorithm 1).

In addition to smoothness, bounded gradients are assumed, which is also restrictive, as many nonconvex functions do not satisfy this property. Indeed, one can show that it is equivalent to the Lipschitz continuity of the function (not its gradient!). Under these assumptions, the standard results bound the minimum gradient norm across all iterations.

An interesting phenomenon in this line of work is that a constant $\beta_{1}<1$ is permitted for the theoretical results, which may seem like weakening our claims. However, it is worth noting that these results do not imply any guarantee for regret in OCO setting.

Indeed, adding the convexity assumption to the setting of unconstrained, smooth stochastic optimization, would only help obtaining a gradient norm bound in the averaged iterate, rather than the minimum across all iterations. However, this bound does not imply any guarantee in the objective value, unless more stringent Polyak-Lojasiewicz or strong convexity requirements are added in the mix.

Moreover, in the OCO setting that we analyze, loss functions are nonsmooth, and there exists a constraint onto which a projection is performed in the $x_{t+1}$ step (cf., Algorithm 1). Finally, online optimization includes stochastic optimization as a special case. Given the difference of assumptions, the analyses in (Chen et al., 2019a; Zhou et al., 2018; Zou et al., 2019) indeed do not help obtaining any regret guarantee for standard OCO.

A good example demonstrating this difference on the set of assumptions is the work (Chen et al., 2019b). In this paper, a variant of AMSGrad is proposed for zeroth order optimization and it is analyzed in the convex and nonconvex settings. Consistent with the previous literature in both, convergence result for the nonconvex setting allows a constant $\beta_{1}<1$ (Chen et al., 2019b, Theorem 1). However, the result in the convex setting requires a decreasing schedule such that $\beta_{1t}=\frac{\beta_{1}}{t}$ (Chen et al., 2019b, Proposition 4).

As we highlighted above, the analyses in convex/nonconvex settings follow different paths and the results or techniques are not transferrable to each other. Thus, our main aim in this paper is to bridge the gap in the understanding of regret analysis for OCO and propose a new analytic framework. As we see in the sequel, our analysis not only gives the first results in OCO setting, it is also general enough to apply to the abovementioned nonconvex optimization case and recover similar results as the existing ones.

Main results

We start by describing the shortcoming of the previous approaches in (Reddi et al., 2018; Wang et al., 2020) and, then explain the mechanism that allows us to obtain regret bounds with constant $\beta_{1}$. In this subsection, for full generality, we assume that the update for $m_{t}$ is not done with $\beta_{1}$, but with $\beta_{1t}$, as in (Reddi et al., 2018; Kingma & Ba, 2014):

The standard way to analyze Adam-type algorithms is to start by the nonexpansiveness property (3) and to write

Let us analyze the above inequality. Its left-hand side is exactly what we want to bound, since by convexity $R(T)\leq\sum_{t=1}^{T}\langle g_{t},x_{t}-x\rangle$. The last two terms in the right-hand side are easy to analyze, all of them can be bounded in a standard way using just definitions of $\hat{v}_{t}$, $m_{t}$, and $\alpha_{t}$.

What can we do with the term $-\beta_{1t}\langle m_{t-1},x_{t}-x\rangle$? Analysis in (Reddi et al., 2018) bounds it with Young’s inequality

The term $\frac{\beta_{1t}}{2\alpha_{t}}\|x_{t}-x\|^{2}_{\hat{v}_{t}^{1/2}}$ is precisely what leads to the second term in the regret bound in (Reddi et al., 2018, Theorem 4). Since $\alpha_{t}=\frac{\alpha}{\sqrt{t}}$, one must require $\beta_{1t}\to 0$.

Note that the update for $x_{t+1}$ has a projection. This is important, since otherwise a solution must lie in the interior of $\mathcal{X}$, which is not the case in general for problems with a compact domain. However, let us assume for a moment that the update for $x_{t+1}$ does not have any projection. In this simplified setting, applying the following trick will work.

Recall that $x_{t}=x_{t-1}-\alpha_{t-1}\hat{v}_{t-1}^{-1/2}m_{t-1}$, or equivalently $m_{t-1}=\frac{1}{\alpha_{t-1}}\hat{v}_{t-1}^{1/2}(x_{t-1}-x_{t})$. Plugging it into the error term $\langle m_{t-1},x_{t}-x\rangle$ yields

where the second equality follows from the Cosine Law and the first inequality is from $x_{t}-x_{t-1}=-\alpha_{t-1}\hat{v}_{t-1}^{-1/2}m_{t-1}$ and $\hat{v}_{t}^{1/2}/\alpha_{t}\geq\hat{v}_{t-1}^{1/2}/\alpha_{t-1}$. We now compare this bound with the previous one. The term $\alpha_{t-1}\|m_{t-1}\|^{2}_{\hat{v}_{t-1}^{-1/2}}$, as we already observed, is good for summation (cf., Lemma 4). And other two terms are going to cancel after summation over $t$. Hence, it is easy to finish the analysis to conclude $\mathcal{O}(\sqrt{T})$ regret with a fixed $\beta_{1t}=\beta_{1}$.

Unfortunately, the update for $x_{t+1}$ does have a projection, without it the assumption for the domain to be bounded is very restrictive. This prevents us from using the above trick. Its message, however, is that it is feasible to expect a good bound even with a fixed $\beta_{1t}$, and under the same assumptions on the problem setting.

For having a more general technique to handle $\beta_{1}$, we will take a different route in the very beginning — we will analyze the term $\langle g_{t},x_{t}-x\rangle$ in a completely different way, without resorting to any crude inequality as in (Reddi et al., 2018). Basically, this idea can be applied to any framework with a similar update for the moment $m_{t}$.

2 A key lemma

As we understood above, the presence of the projection complicates handling $\langle m_{t-1},x_{t}-x\rangle$. A high level explanation for the cause of the issue is that the standard analysis does not leave much flexibility, since it uses nonexpansiveness in the very beginning.

The main message of Lemma 1 is that the decomposition of $m_{t}$, in the second part of the analysis in Section 3.1 is now done before using nonexpansiveness, therefore there would be no need for using Young’s inequality which is the main shortcoming of the previous analysis.

Upon inspection on the bound, it is now easy to see that the last two terms will telescope. The second term can be shown to be of the order $\alpha_{t}\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$, and as we have seen before, summing this term will give \mathcal{O}\big{(}\sqrt{T}\big{)}. To see that the first term is also benign, a high level explanation is to notice that $m_{t-1}$ is the gradient estimate used in the update $x_{t}=P_{\mathcal{X}}^{\hat{v}_{t-1}^{1/2}}(x_{t-1}-\alpha_{t-1}\hat{v}_{t-1}^{-1/2}m_{t-1})$, therefore it can be analyzed in the classical way. We will now proceed to illustrate the flexibility of the new analysis on three most popular Adam variants that are proven to converge.

3 AMSGrad

AMSGrad is proposed by (Reddi et al., 2018) as a fix to Adam. The algorithm incorporates an extra step to enforce monotonicity of second moment estimator $\hat{v}_{t}$.

The regret bound for this algorithm in (Reddi et al., 2018, Theorem 4, Corollary 1) requires a decreasing $\beta_{1}$ at least at the order of $1/t$ to obtain \mathcal{O}\big{(}\sqrt{T}\big{)} worst case regret. Moreover, it is easy to see that a constant $\beta_{1}$ results in \mathcal{O}\big{(}T\sqrt{T}\big{)} worst case regret in (Reddi et al., 2018, Theorem 4).

We now present the following theorem which shows that the same \mathcal{O}\big{(}\sqrt{T}\big{)} can be obtained by AMSGrad under the same structural assumptions as (Reddi et al., 2018).

Under Assumption 1.1, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$, and $\varepsilon>0$, AMSGrad achieves the regret

We would like to note that our bound for $R(T)$ is also better than the one in (Reddi et al., 2018) in term of constants. We have only two terms in contrast to three in (Reddi et al., 2018) and each of them is strictly smaller than their counterparts in (Reddi et al., 2018). The reason is that we used i) new way of decomposition $\langle g_{t},x_{t}-x\rangle$ as in Lemma 1, ii) wider admissible range for $\beta_{1},\beta_{2}$, iii) more refined estimates for analyzing terms. For example, the standard analysis to estimate $\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$ uses several Cauchy-Schwarz inequalities. We instead give a better bound by applying generalized Hölder inequality (Beckenbach & Bellman, 1961).

Another observation is that having a constant $\beta_{1}$ explicitly improves the last term in the regret bound. If one uses a non-decreasing $\beta_{1}$, instead of constant $\beta_{1}$, then this term will have an additional multiple of $\frac{1}{(1-\beta_{1})^{2}}$. Given that in general one chooses $\beta_{1}$ close to $1$, this factor is significant.

Notice that Theorem 1 requires $\varepsilon>0$ in order to have the weighted projection operator in (2) well-defined. Such a requirement is common in the literature for theoretical analysis, see (Duchi et al., 2011, Theorem 5). In practice, however, one can set $\varepsilon=0$.

We sum $\langle g_{t},x_{t}-x\rangle$ from Lemma 1 over $t$, use $m_{0}=0$ to get

By using the fact that $\hat{v}_{t,i}\geq\hat{v}_{t-1,i}$, and the same estimation as deriving $S_{2}$,

By Hölder and Young’s inequalities, we can bound $S_{3}$ as

Lastly, we see that $\alpha_{t}\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$ is common in all these terms and it is well known that this term is good for summation

Combining the terms gives the final bound. ∎

Finally, if we are interested in the worst case scenario, it is clear that Theorem 1 gives regret $R(T)=\mathcal{O}(\sqrt{\log(T)T})$. A quick look into the calculations yields that if one uses the worst case bound $g_{t,i}\leq G$, then the bound will not include a logarithmic term. However, then the data-dependence of the bound will be lost. It is not clear if one can obtain a data-dependent $\mathcal{O}(\sqrt{T})$ regret bound. In the following corollary, we give a partial answer to this question.

Under Assumption 1.1, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{{\beta_{2}}}<1$, and $\varepsilon>0$, AMSGrad achieves the regret

We remark that even though this bound does not contain a $\log(T)$ term, thus better in the worst-case, its data-dependence is actually worse than the standard bound. Standard bound contains $g_{t,i}^{2}$ whereas bound above contains $|g_{t,i}|$. Therefore, when the values $g_{t,i}$ are very small, the bound with $\log{T}$ can be better. We leave it as an open question to have a $\sqrt{T}$ bound with the same data-dependence as the original bound.

4 AdamNc

Another variant that is proposed by Reddi et al. (2018) as a fix to Adam is AdamNc which features an increasing schedule for $\beta_{2t}$. In particular, one sets $\beta_{2t}=1-\frac{1}{t}$ in

that results in the following expression for $v_{t}$

which is a reminiscent of Adagrad (Duchi et al., 2011). In fact, to ensure that $P_{\mathcal{X}}^{v_{t}^{1/2}}$ is well-defined, one needs to consider the more general update $v_{t}=\frac{1}{t}\left(\varepsilon\mathbf{1}+\sum_{j=1}^{t}g_{j}^{2}\right)$ similar to the previous case with AMSGrad.

AdamNc is analyzed in (Reddi et al., 2018, Theorem 5, Corollary 2) and similar to AMSGrad it has been shown to exhibit \mathcal{O}\big{(}\sqrt{T}\big{)} worst case regret only when $\beta_{1}$ decreases to . We show in the following theorem that the same regret can be obtained with a constant $\beta_{1}$.

Under Assumption 1.1, $\beta_{1}<1$, and $\varepsilon>0$, AdamNc achieves the regret

We skip the proof sketch of this theorem as it will have the same steps as AMSGrad, just different estimation for $\alpha_{t}\|m_{t}\|^{2}_{v_{t}^{-1/2}}$, due to different $v_{t}$.

Compared with the bound from (Reddi et al., 2018, Corollary 2), we see again that constant $\beta_{1}$ not only removes the middle term of (Reddi et al., 2018, Corollary 2) but improves the last term of the bound by a factor of $(1-\beta_{1})^{2}$.

5 Sadam

It is known that Adagrad can obtain logarithmic regret (Duchi et al., 2010), when the loss functions satisfy $\mu$-strong convexity, defined as

$\forall x,y\in\mathcal{X}$ and $g\in\partial f(y)$.

A variant of AdamNc for this setting is proposed in (Wang et al., 2020, Theorem 1) and shown to obtain logarithmic regret, only with the assumption that $\beta_{1}$ decreases linearly to .

Similar to AMSGrad and AdamNc, our new technique applies to Sadam to show logarithmic regret with a constant $\beta_{1}$ under the same assumptions as (Wang et al., 2020).

Let Assumption 1.1 hold and $f_{t}$ be $\mu$-strongly convex, $\forall t$. Then, if $\beta_{1}<1$, $\varepsilon>0$, and $\alpha\geq\frac{G^{2}}{\mu}$, Sadam achieves

Consistent with the standard literature of OGD (Hazan et al., 2007), to obtain the logarithmic regret, first step size $\alpha$ has a lower bound that depends on strong convexity constant $\mu$. Compared with the requirement of (Wang et al., 2020) for $\alpha\geq\frac{G^{2}}{\mu(1-\beta_{1})}$, our requirement is strictly milder as $1-\beta_{1}\leq 1$ and in practice since $\beta_{1}$ is near $1$, it is much milder. We also remark that our bound is again strictly better than (Wang et al., 2020). Consistent with our previous results, we remove a factor of $\frac{1}{(1-\beta_{1})^{2}}$ from the last term of the bound, compared to (Wang et al., 2020, Theorem 1).

We include the proof sketch to highlight how strong convexity helps in the analysis.

We will start the same as proof sketch of Theorem 1 to get

with the definitions of $S_{1}$, $S_{2}$, $S_{3}$ from the proof sketch of Theorem 1.

Now, due to strong convexity, one gets an improved estimate for the left-hand side,

Similar as before, we note the bound for $S_{2}$ as

For $S_{1}$, one does not finish the estimation as before, but keep some terms that will be gotten rid of using strong convexity, and use the same estimation as $S_{2}$ to obtain

As strong convexity gives more flexibility in the analysis, one can select $\alpha_{t}=\frac{\alpha}{t}$, resulting in an improved bound

It is now easy to see that the negative term in (8), when first step size $\alpha$ is selected properly, can be used to remove the first term in the bound of (10).

It only remains to use Hölder inequality on $S_{3}$, combine the estimates and use (11) to get the final bound. ∎

Extensions

In this section, we further demonstrate the applicability of our analytic framework in different settings. First, we focus on the recently proposed zeroth-order version of AMSGrad which required decreasing $\beta_{1}$ in the convex case (Chen et al., 2019b, Proposition 4), and we show that the same guarantees can be obtained with constant $\beta_{1}$. Second, we show how to recover the known guarantees in the nonconvex setting, with small improvements. Finally, we extend our analysis to show that it allows any non-increasing variable $\beta_{1t}$ schedule.

We first recall the setting of (Chen et al., 2019b), where a zeroth order variant of AMSGrad is proposed. The problem is

We note that this stochastic optimization setting corresponds to a special case of general OCO, with independent and identically distributed loss functions $f(x;\xi)$, indexed by $\xi$.

The algorithm ZO-AdaMM (Chen et al., 2019b) is similar to AMSGrad applied with a zeroth order gradient estimator $\hat{g}_{t}$, instead of regular gradient $g_{t}$. The gradient estimator is computed by

where $\xi_{t}$ is the sample selected at iteration $t$, $u$ is a random vector drawn with uniform distribution from the sphere of a unit ball and $\mu$ is a sampling radius – or smoothing – parameter.

The benefit of this gradient estimator is that it is an unbiased estimator of the randomized smoothed version of $f$, i.e.,

Two cases are analyzed by Chen et al. (2019b): convex $f$ and nonconvex $f$. The authors proved guarantees with constant $\beta_{1}$ for nonconvex $f$ (Chen et al., 2019b, Proposition 2). However, surprisingly, their result for convex $f$ requires $\beta_{1t}=\frac{\beta_{1}}{t}$ (Chen et al., 2019b, Proposition 4).

We identify that this discrepancy is due to the fact that their proof follows the same path as the standard regret analysis of Reddi et al. (2018). We give below a simple corollary of our technique showing that the same guarantees for convex $f$ can be obtained with constant $\beta_{1}$.

Assume that $f$ is convex, $L$-smooth, and $L_{c}$-Lipschitz, $\mathcal{X}$ is compact with diameter $D$. Then ZO-AdaMM with $\beta_{1},\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$ achieves

To finish the arguments, one can use standard bounds in zeroth order optimization, as in Chen et al. (2019b). Compared with Chen et al. (2019b, Proposition 4), the same remarks hold as for AMSGrad. Not only our result allows constant $\beta_{1}$, but it also comes with better constants.

2 Nonconvex AMSGrad

In this section, we focus on the nonconvex, unconstrained, smooth, stochastic optimization setting:

We give a different and simpler proof using our new analysis, without defining $z_{t}$. In terms of guarantees, we recover the same rates, with slightly better constants.

Under Section 4.2, $\beta_{1}<1$, $\beta_{2}<1$, and $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$ AMSGrad achieves

Compared with (Chen et al., 2019a, Corollary 3.1), the initial value of $v_{0}=\varepsilon$ only affects one of the terms in our bound, whereas $\frac{1}{\varepsilon}$ appears in all the terms of (Chen et al., 2019a, Corollary 3.1). The reason is that (Chen et al., 2019a) uses $v_{0}\geq\varepsilon$ in many places of the proof, even when it was unnecessary.

Compared with (Zhou et al., 2018, Corollary 3.9), our result allows for bigger values of $\beta_{1}$, since we require $\beta_{1}^{2}\leq\beta_{1}<1$ whereas (Zhou et al., 2018, Corollary 3.9) requires $\beta_{1}\leq\beta_{2}<1$. Moreover, (Zhou et al., 2018, Corollary 3.9) has a constant step size $\alpha=\frac{1}{\sqrt{dT}}$ that requires setting a horizon and becomes very small with large $d$.

Lastly, we have a $\log T$ dependence, whereas (Zhou et al., 2018, Corollary 3.9) does not. However, this is not for free and it stems from the choice of a constant step size $\alpha_{t}=\frac{1}{\sqrt{dT}}$ therein. In fact, it is well known that for online gradient descent analysis, $\log T$ can be shaved when $\alpha_{t}\approx\frac{1}{\sqrt{T}}$. However, in practice using a variable step size is more favorable, since it does not require setting $T$ in advance. Therefore, we choose to work with variable step size and have the $\log T$ term in the bound.

We have focused on the case of constant $\beta_{1}$ throughout our paper, as it is the most popular choice in practice. However, it is possible that in some applications, practitioners might see benefit of using other schedules. For instance, one can decrease $\beta_{1}$ until some threshold and keep it constant afterwards. This is not covered by the previous regret analyses as $\beta_{1}$ needed to decrease to . With our framework however, one can use not only constant $\beta_{1}$, but any schedule as long as it is nonincreasing, and optimal regret bounds will follow.

Due to space constraints, we do not repeat all the proofs with this modification, but illustrate the main change that happens with variable $\beta_{1}$ and show that our proofs will go through. In this section we switch to notation of $\beta_{1t}$ to illustrate time-varying case.

We start from the result of Lemma 1, after summing over $t=1,\ldots,T$

For bounding the terms on the first and third lines of (15), the only place that will change with varying $\beta_{1t}$ in the proof, is that $\alpha_{t}\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$ will have a slightly different estimation, since now $m_{t}=\sum_{j=1}^{t}\prod_{k=1}^{t-j}\beta_{1(t-k+1)}(1-\beta_{1j})g_{j}^{2}$. One can use that $\beta_{1t}\leq\beta_{1}$ to obtain the same bounds, but with $\frac{1}{(1-\beta_{1})^{2}}$ factor multiplying the bounds now. As explained before, this is one thing we lose with varying $\beta_{1t}$ in theory.

Next, we estimate the terms in the second line of (15)

Now, for the last line we use that $\beta_{1t}$ is non-increasing, $\beta_{1t}\leq\beta_{1}$, $\|m_{t}\|_{1}\leq dG$ and $\|x_{t}-x\|_{\infty}\leq D$, to get

Thus upon summation over $t=1$ to $T$, as $m_{0}=0$,

where we let $\beta_{10}=\beta_{11}<1$. Indeed, the contribution of this term will only be constant as $(1-\beta_{1t})\leq 1,\forall t$, $\|m_{t}\|_{\infty}\leq G$, $\|x_{t}-x\|_{\infty}\leq D$.

Note that the estimation of the terms on the first and third lines of (15) are the same, as in the constant $\beta_{1}$ case (up to constants). Also, the contribution of the terms in the second line of (15) with varying $\beta_{1t}$ is a constant. Thus, one can repeat our proofs, with any nonincreasing $\beta_{1t}$ schedule and obtain the same optimal regret bounds, but with slightly worse constants (compared to constant $\beta_{1}$ case).

Acknowledgements

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon $2020$ research and innovation programme (grant agreement no $725594$ - time-data), the Swiss National Science Foundation (SNSF) under grant number $200021\_178865/1$, the Department of the Navy, Office of Naval Research (ONR) under a grant number N62909-17-1-211. PM acknowledges financial support from the French National Research Agency (ANR) under grant ORACLESS (ANR-16-CE33-0004-01) and the COST Action CA16229 “European Network for Game Theory” (GAMENET).

References

Appendix A Proofs

By definition of $m_{t}$, $g_{t}=\frac{1}{1-\beta_{1}}m_{t}-\frac{\beta_{1}}{1-\beta_{1}}m_{t-1}$. Thus, we have

The above lemma is used to obtain a slightly tighter bound for $\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$, compared to the standard analysis.

Under Assumption 1.1, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$, $\hat{v}_{t}$ in AMSGrad, it holds that

From the definition of $m_{t}$ and $v_{t}$, it follows that

where the first inequality follows from the fact that $\hat{v}^{1/2}_{t,i}\geq v^{1/2}_{t,i}$, the second one follows from the generalized Hölder inequality (Lemma 2) for

and the third one follows from the sum of geometric series and the assumption $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$.

We now comment on the possibility of observing many zero gradients in the beginning, causing $v_{t}=0$ until some $t$, which would cause the appearance of the indeterminate form $\frac{0}{0}$ in the upper bound derived above — specifically in the term $\frac{m_{t,i}^{2}}{v_{t,i}^{1/2}}$. For this, we will use the convention $\frac{0}{0}=0$, in which case the above derivations are always well-defined. For this, we argue as follows: recall first that $v_{t,i}=0$ iff $g_{j,i}=0$ for all $j=1,\dots,t$. This being the case, we also get $m_{t,i}=0$, and hence, $\frac{m_{t,i}^{2}}{{v}_{t,i}^{1/2}}=0$. In fact, this was done only for convenience, since $\hat{v}_{t,i}\geq\varepsilon$ and we can always exclude zero terms from $\|m_{t}\|^{2}_{\hat{v}_{t}^{-1/2}}$, before using the first line in the above chain of inequalities. ∎

Under Assumption 1.1, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$, $\hat{v}_{t}$ in AMSGrad, we have

We now restate Theorem 1 for easy navigation and proceed to its proof.

Under Assumption 1.1, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$, and $\varepsilon>0$, AMSGrad achieves the regret

Let $x\in\operatorname*{argmin}_{y\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(y)$. Then by convexity, we immediately have

Hence, our goal is to bound the latter expression. If we sum the inequality from Lemma 1 over $t=1,\dots,T$ and use the fact that $m_{0}=0$, we obtain

We will separately bound each term in the right-hand side of (22) and then combine these bounds together.

$\bullet$ Bound for $\sum_{t=1}^{T}\langle m_{t},x_{t}-x\rangle$.

As $x\in\mathcal{X}$, by the nonexpansiveness property (3), we get

We rearrange and divide both sides of (A.1) by $2\alpha_{t}$ to get

where the last inequality is due to the fact that $\hat{v}_{t,i}\geq\hat{v}_{t-1,i}$, $\frac{1}{\alpha_{t}}\geq\frac{1}{\alpha_{t-1}}$, and the definition of $D$.Note that for $t=1$ we suppose that $\frac{1}{\alpha_{0}}=0$; this makes the above derivation still valid, as $\alpha_{0}$ is not used in the algorithm, and this is only for convenience.

Summing (24) over $t=1,\dots T$ and using that $\frac{1}{2\alpha_{0}}\|x_{1}-x\|^{2}_{\hat{v}_{0}^{1/2}}=0$ yields

$\bullet$ Bound for $\sum_{t=1}^{T}\langle m_{t-1},x_{t-1}-x_{t}\rangle$.

At this point, we could use eq. 21 to obtain a final bound for $\sum_{t=1}^{T}\langle m_{t-1},x_{t-1}-x_{t}\rangle$. However, we postpone it to combine it with the term $\langle m_{T},x_{T}-x\rangle$ in (22) to have a shorter expression.

$\bullet$ Bound for $\langle m_{T},x_{T}-x\rangle$.

We now have all the ingredients required to bound the right-hand side of (22). To that end, after all substitutions and some straightforward algebra, we obtain

where the second inequality follows from the assumption $\frac{2-\beta_{1}}{4}\leq\frac{1}{2}$, $\frac{1+\beta_{1}}{2}\leq 1$, and $\alpha_{T}=\frac{\alpha}{\sqrt{T}}$, and the last follows by Lemma 4. ∎

A.2 Proofs for AdamNc

We first give analogous results to Lemmas 3 and 4, which are mostly standard and simplified thanks to a constant $\beta_{1}$.

Under Assumption 1.1, $\beta_{1}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$ in AdamNc, it holds that

Using the expression (20) for $m_{t}$ and $v_{t,i}=\frac{1}{t}\left(\sum_{j=1}^{t}g_{j,i}^{2}+\varepsilon\right)$, we obtain:In the sequel, the same comments about the indeterminate form $\frac{0}{0}$ apply here as in Lemma 3.

where the first inequality is due to $\varepsilon>0$, second inequality is by Cauchy-Schwarz, the third one by the sum of geometric series, and the final one is by $j\leq t$. ∎

Under Assumption 1.1, $\beta_{1}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$ in AdamNc, it holds that

where the second equality is due to $\alpha_{t}=\frac{\alpha}{\sqrt{t}}$, third equality is by changing the order of summation, first inequality by summation of the geometric series. For the last inequality, we use a standard inequality for numerical sequences, encountered for example in Auer et al. (2002, Lemma 3.5)

We now restate Theorem 2 and present its proof.

Under Assumption 1.1, $\beta_{1}<1$, and $\varepsilon>0$, AdamNc enjoys the regret bound

We will follow the proof structure of Theorem 1. First, we start from (22) which applies to AdamNc as the update of $m_{t}$ is the same as AMSGrad

Then we again bound each term in the right-hand side seperately.

$\bullet$ Bound for $\sum_{t=1}^{T}\langle m_{t},x_{t}-x\rangle$.

We proceed similarly to the derivations in (A.1) and (24), the main change being that we now have $v_{t}$ instead of $\hat{v}_{t}$. We have:

where the last inequality is due to $\frac{v_{t,i}^{1/2}}{\alpha_{t}}\geq\frac{v_{t-1,i}^{1/2}}{\alpha_{t-1}}$, since by definition $v_{t,i}=\frac{1}{t}\left(\sum_{j=1}^{t}g_{j,i}^{2}+\varepsilon\right)$ and $\alpha_{t}=\frac{\alpha}{\sqrt{t}}$.

We now proceed to telescope this inequality, assuming as before that $\frac{1}{\alpha_{0}}=0$. Doing so, we obtain:

$\bullet$ Bounds for $\langle m_{T},x_{T}-x\rangle$ and $\sum_{t=1}^{T}\langle m_{t-1},x_{t-1}-x_{t}\rangle$

These bounds will be similar as in the proof of Theorem 1. Again, the only change in calculations in (26) and (A.1) is that now we have $v_{t}$ instead of $\hat{v}_{t}$

We now combine (33), (34), and (35) in (31), estimate using the same steps in (28), and use the bound for $\sum_{t=1}^{T}\alpha_{t}\|m_{t}\|^{2}_{v_{t}^{-1/2}}$ from Lemma 6 to conclude:

A.3 Proofs for Sadam

Under Assumption 1.1, $\beta_{1}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$, $\hat{v}_{t}$ in Sadam, it holds that

where we used the definitions $\hat{v}_{t,i}=\frac{1}{t}\sum_{k=1}^{t}g_{k,i}^{2}+\frac{\varepsilon}{t}$ and the expression for $m_{t}$ from (20) in the first line. First inequality follows from Cauchy-Schwarz and sum of geometric series; and the last inequality is by $j\leq t$. ∎

Under Assumption 1.1, $\beta_{1}<1$, $\varepsilon>0$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$, $\hat{v}_{t}$ in Sadam, it holds that

where the second equality is by the definition of $\alpha_{t}$ and the third equality is by changing the order of summation. Moreover, first inequality is by the sum of geometric series and the last inequality is due to the fact that

for nonnegative $a_{1},\ldots,a_{T}$ and $\varepsilon>0$ – see e.g., Duchi et al. (2010, Lemma 12) and Hazan et al. (2007, Lemma 11). ∎

We now restate Theorem 3 and present its proof.

Let Assumption 1.1 hold and $f_{t}$ be $\mu$-strongly convex, $\forall t$. Then, if $\beta_{1}<1$, $\varepsilon>0$, and $\alpha\geq\frac{G^{2}}{\mu}$, Sadam achieves

Let $x=\operatorname*{argmin}_{y\in\mathcal{X}}\sum_{t=1}^{T}f_{t}(y)$. In Theorem 1 we used convexity only once: going from $R(T)$ to $\sum_{t=1}^{T}\langle g_{t},x_{t}-x\rangle$. Instead, strong convexity gives us $f_{t}(x)\geq f_{t}(x_{t})+\langle g_{t},x-x_{t}\rangle+\frac{\mu}{2}\|x_{t}-x\|^{2}$, which combined for all $t$ yields

We want to estimate $\sum_{t=1}^{T}\langle g_{t},x_{t}-x\rangle$. Similarly to (22), we have

$\bullet$ Bound for $\sum_{t=1}^{T}\langle m_{t},x_{t}-x\rangle$.

We proceed similarly to (A.1) and (24). The only change is that now we have $\hat{v}_{t}$ instead of $\hat{v}_{t}^{1/2}$

We sum the above inequality and use the fact that $\frac{1}{\alpha_{0}}\|x_{1}-x\|^{2}_{\hat{v}_{0}}=0$ to obtain

$\bullet$ Bound for $\sum_{t=1}^{T}\langle m_{t-1},x_{t-1}-x_{t}\rangle$

This bound will be similar to the one we derived for Theorem 1. The main change in the calculations of (26) is that we will have $\hat{v}_{t}$ instead of $\hat{v}_{t}^{1/2}$ for using Hölder’s inequality and nonexpansiveness

We collect these estimations in (42) and (41) to derive

We collect the last two terms and use the assumption on the step size $\alpha\geq\frac{G^{2}}{\mu}$ and the definition $\hat{v}_{t,i}=\frac{1}{t}\sum_{j=1}^{t}g_{j,i}^{2}+\frac{\varepsilon}{t}$ to derive

We finalize by using $\frac{1+\beta_{1}}{2}\leq 1$, Lemma 8 for the last term, and $\|m_{t}\|_{\infty}\leq G$, $\|x_{t}-x\|_{\infty}\leq D$ for the first term

A.4 Proof for Zeroth order Adam

We restate Proposition 1 and provide its proof.

Assume that $f$ is convex, $L$-smooth, and $L_{c}$-Lipschitz, $\mathcal{X}$ is compact with diameter $D$. Then ZO-AdaMM with $\beta_{1},\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$ achieves

We first note that ZO-AdaMM (Chen et al., 2019b) corresponds to using AMSGrad with $\hat{g}_{t}$ as the gradient input, rather than the true gradient $g_{t}$. Therefore, we follow the proof structure of Theorem 1 with $\hat{g}_{t}$ as gradient input (instead of the true gradient $g_{t}$), until (28):

Our claim then follows by applying Jensen’s inequality, after taking expectations in (46). ∎

A.5 Proofs for nonconvex AMSGrad

(Bound for $\sum_{t=1}^{T}\|\alpha_{t}\hat{v}_{t}^{-1/2}m_{t}\|^{2}$). Under Section 4.2, $\beta_{1}<1$, $\beta_{2}<1$, $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$, and the definitions of $\alpha_{t}$, $m_{t}$, $v_{t}$, $\hat{v}_{t}$ in AMSGrad, it holds that

We first note the inequality for positive numbers

which is a consequence of Cauchy-Schwarz inequality.

where the first inequality uses $\hat{v}_{t,i}\geq v_{t,i}$, and the second equality uses the expressions from (20). The second inequality is by (48), and the final one by the sum of geometric series with $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}$. Since $\alpha_{t}^{2}=\frac{\alpha^{2}}{t}$, the final inequality (47) follows. ∎

The reader could notice that all proofs so far were based on Lemma 1. In fact, we can formulate a more general statement, which will be the key in the nonconvex settings.

For convex case, we plugged in $A_{t}=x_{t}-x$, while for the nonconvex case we will use $A_{t}=\alpha_{t}\hat{v}_{t}^{-1/2}\nabla f(x_{t})$. Obviously, its proof relies on the same algebra as in Lemma 1.

We move onto restating Theorem 4 and presenting its proof.

Under Section 4.2, $\beta_{1}<1$, $\beta_{2}<1$, and $\gamma=\frac{\beta_{1}^{2}}{\beta_{2}}<1$ AMSGrad achieves

Let $A_{t}=\alpha_{t}\hat{v}_{t}^{-1/2}\nabla f(x_{t})$ for $t\geq 1$ and $A_{0}=A_{1}$. By summing (50) over $t=1,\dots,T$ and using that $m_{0}=0$, $\langle A_{0},m_{0}\rangle=0$, $\langle A_{1}-A_{0},m_{0}\rangle=0$, we obtain

$\bullet$ Bound for $\langle A_{t},g_{t}\rangle$

To simplify derivations, we set $\alpha_{0}=\alpha=\alpha_{1}$. Now, for the last term in the right-hand side we have

where we used Hölder’s inequality, and $\alpha_{t-1}\hat{v}_{t-1,i}^{-1/2}\geq\alpha_{t}\hat{v}_{t,i}^{-1/2}$ (note that for $t=1$, this is still true, since $\hat{v}_{1}\geq\hat{v}_{0}$ and $\alpha_{0}=\alpha_{1}$). Combining (53) and (52) yields

$\bullet$ Bound for $\langle A_{t}-A_{t+1},m_{t}\rangle$

For the first term we use almost the same inequality as in (53)

For the second term we use smoothness of $f$ and the update rule for $x_{t+1}$

We apply above estimates in (A.5) to derive

$\bullet$ Bound for $\langle A_{t},m_{t}\rangle$

By the update of $x_{t+1}$ and the descent lemma, we have

By Young’s inequality, $x_{T}-x_{T+1}=\alpha_{T}\hat{v}_{T}^{-1/2}m_{T}$, and $\|\nabla f(x_{T})\|_{\infty}\leq G$,

where in the second inequality we used $f(x_{T})\geq f(x_{\star})$, $\alpha_{1}=\alpha$, and $\frac{1+\beta_{1}}{2}\leq 1$ and the final inequality follows from Lemma 9, as $\sum_{t=1}^{T}\|x_{t+1}-x_{t}\|^{2}=\sum_{t=1}^{T}\|\alpha_{t}\hat{v}_{t}^{-1/2}m_{t}\|^{2}$.

Now we analyze the left-hand side of (A.5). Using (54), we deduce

where we used $\alpha_{0}=\alpha$ and $\|\alpha_{T}\hat{v}_{T}^{-1/2}\|_{1}\geq 0$.

Finally, combining (A.5), (A.5), and (A.5), we arrive at

where we used that $\hat{v}_{0,i}^{-1/2}\geq\hat{v}_{1,i}^{-1/2}$.

Thus, by taking the full expectation in (A.5), we deduce

from which the final bound follows immediately. ∎