The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance

Introduction

Due to its simplicity, an enormous amount of literature, starting by [RM51], has sought to understand convergence guarantees for variants of stochastic gradient descent (SGD):

for minimizing a function $F(\cdot)$ using stochastic gradients $\bm{g}_{t}$ and a step size schedule $\eta_{t}$. When the (non-convex) objective function is smooth (i.e., has $L$-Lipschitz-continuous gradients) and the stochastic gradients are unbiased and have affine varianceWhile the proof of convergence under affine variance is not given explicitly in [GL13], by slightly modifying the step size choice, the analysis given in this work continues to hold with no additional modifications. Indeed, this observation is made explicitly by [BCN18, Theorem 4.8 ]., i.e.,

then it is well-known that SGD with a properly-tuned step size (depending on $L$ and $\sigma_{1}$) converges to a first-order stationary point with error $\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$ after $T$ iterations [GL13, BCN18]. Moreover, [ACDFSW19] showed this rate is tight under these assumptions.

Given these results, it is natural to ask if knowledge of $L$ and $\sigma_{1}$ is necessary to obtain this optimal rate of convergence. Indeed, this has been the motivation for adaptive step size algorithms such as AdaGrad-Norm, where for any parameters $\eta,b_{0}>0$, the step size, $\eta_{t}$, is given by

[WWB19] showed that AdaGrad-Norm enjoys a $\mathcal{O}(\nicefrac{{\log(T)}}{{\sqrt{T}}})$ convergence rate even when neither $L$ nor $\sigma_{0}$ is used to tune the step size-schedule. However, their analysis only holds when $\sigma_{1}=0$ and the gradients are uniformly upper-bounded – an assumption which is violated even by strongly convex functions such as $F(\mathbf{w})=\left\lVert\mathbf{w}\right\rVert^{2}$. In fact, [LO19, Section 4] suggests that, due to the correlation between $\eta_{t}$ and $\bm{g}_{t}$ in the standard AdaGrad-Norm, the assumption that the gradients are uniformly-bounded might be necessary to prove their convergence guarantee. Although some works on similar adaptive SGD algorithms do not require the gradients to be uniformly upper-bounded [LO19, LO20], their analysis only holds when the step-size $\eta_{t}$ is (conditionally) independent of the current stochastic gradient $\bm{g}_{t}$, and require subgaussian noise (a condition which forces $\sigma_{1}=0$). However, disentangling $\eta_{t}$ from $\bm{g}_{t}$ is detrimental to the normalization scheme, rendering these methods crucially dependent on the knowledge of the Lipschitz constant $L$ for determining their step size.

Extending these results from the bounded variance setting ($\sigma_{1}=0$) to the affine variance setting is important. Indeed, results that hold only for the case of bounded variance effectively require that one has noiseless access to gradients when their magnitudes are large (see Remark 1 for more discussion). As opposed to the non-adaptive SGD setting where this extension is immediate (discussed above), in AdaGrad-Norm (and more generally, in adaptive methods), the bias introduced by the correlation between $\eta_{t}$ and $\bm{g}_{t}$ causes this additional variance to be significantly more problematic.

Our analysis must overcome two main challenges: (i) possibly unbounded gradients, and (ii) an additional bias term introduced by affine variance. Prior work avoided or circumvented these challenges via additional assumptions. Our work requires several new insights that we believe may be of independent interest. Furthermore, as we state in Remark 14, these insights are broadly applicable to related adaptive algorithms such as coordinate-wise AdaGrad. We outline these below.

Main Challenge 2: Additional bias from affine variance.

In the affine variance setting, the expected difference in function value between consecutive time steps is bounded as:

Related Work. [GL13] were the first to study the convergence of SGD for opimizing a non-convex, smooth objective function. They proved that a properly-tuned SGD converges to a first-order stationary point at rate $\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$, if the step sizes are chosen as $\eta_{t}=\min\left\{\nicefrac{{1}}{{(1+\sigma_{1}^{2})L}},\nicefrac{{\widetilde{D}}}{{\sigma_{0}\sqrt{T}}}\right\}$ for a constant $\widetilde{D}>0$. Further, [ACDFSW19] proved that the $\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$ rate is unimprovable for any algorithm with only first-order oracle access, assuming the function is non-convex, smooth, and the stochastic gradients are unbiased with bounded variance.

The original AdaGrad algorithm was proposed simultaneously by [DHS11, MS10] whereas [SM10] were the first to consider a variant of AdaGrad referred to as AdaGrad-Norm. [WWB19] analyzed AdaGrad-Norm for minimizing a smooth, non-convex function with uniformly-bounded gradients. They showed that AdaGrad-Norm converges at essentially the same rate as SGD, but without the need to know the smoothness constant (albeit under the restrictive assumption that the gradients are uniformly upper-bounded). In a simultaneous work, [LO19] studied a variant of AdaGrad-Norm where step size $\eta_{t}$ is conditionally independent of the current stochastic gradient $\bm{g}_{t}$, unlike in the standard AdaGrad setting. They provided a similar convergence guarantee without needing a uniform upper-bound on the stochastic gradients, but requiring that the noise have bounded support and additionally requiring knowledge of the smoothness parameter $L$ to tune their step sizes. In a followup work [LO20], the same authors proved high-probability convergence of a class of adaptive algorithms (including their variant of AdaGrad-Norm, as well as coordinate-wise AdaGrad with momentum) under the assumption of subgaussian noise. Note that, like the earlier result, their step sizes needed to be tuned with knowledge of the smoothness parameter, and further needed to be conditionally independent of the current gradient. [KLC22] established high probability results for AdaGrad without knowledge of the smoothness parameter in the bounded variance regime, assuming that the norm of the gradients are uniformly upper-bounded (i.e., the objective function is Lipschitz). They were further able to remove the Lipschitz assumption, but only when in addition to bounded variance, the noise of the stochastic gradients is subgaussian. [GG20] studied the asymptotic convergence of AdaGrad (as well as and RMSProp), where their analysis requires uniform gradient bounds as well as uniform bounds on the $2$nd and $4$th moments of the gradient noise. Very recently, [JXH22] established asymptotic almost-sure convergence of the AdaGrad-Norm iterates to first-order stationary points. Unlike our work, they do not provide rates of convergence, and their focus on asymptotics makes their analysis and results significantly different. [ZSJSL18] studied a weighted version of coordinate-wise AdaGrad with momentum, where they assumed the gradients were uniformly bounded. [DBBU20] later improved upon these results with respect to the dependence on the momentum parameter.

Several recent works have studied the convergence of other adaptive algorithms, all of which are based on the assumption of uniformly-bounded stochastic gradients. For instance, [KLBC19] developed an adaptive, accelerated algorithm that achieves optimal rates in the constrained, convex (smooth and non-smooth) regime, without knowledge of the smoothness or noise parameters. [CLSH18] studied the convergence of a class of Adam-like algorithms (originally introduced by [KB15]). Later, building on the results of [WWB19], [DBBU20] improved on this analysis of Adam with respect to the dependence on the momentum parameter and range of valid hyperparameters. [GXYJY21] provide an alternate analysis of a class of Adam-like algorithms for different momentum parameter scaling. [SMBM21] studied “delayed” versions of Adam (as well as a new algorithm they called AvaGrad), which makes the step sizes $\eta_{t}$ conditionally independent of the current stochastic gradient, $\bm{g}_{t}$.

Preliminaries

(Motivation for Affine Variance) This scaling is important for machine learning applications with feature noise (including missing features) [Ful09, KL20], in robust linear regression [XCM08], and generally whenever the model parameters are multiplicatively perturbed by noise (e.g., a multilayer network, where noise from a previous layer multiplies the parameters in subsequent layers). More broadly, restricting to bounded variance (i.e., assuming $\sigma_{1}^{2}=0$) is equivalent to assuming “noiseless” access to the gradient when the magnitude of the gradient grows (e.g., a strongly convex function); this is because the stochastic gradient is an arbitrarily small perturbation of the true gradient in this regime. Finally, as discussed earlier, the analysis for non adaptive SGD is essentially unaffected by affine variance [BCN18].

Further, we will assume that the function $F(\cdot)$ is $L$-smooth:

A key property of AdaGrad-Norm is that the step-size sequence is tightly controlled:

In fact, variations of this observation have been noted for a number of AdaGrad variants [WWB19, DBBU20]. While simple, it is crucially important to our analysis, since, taken together with Assumption 3, it implies that the gradient at time $t$ scales at most polynomially in $t$.

Consider any times $t_{1}\leq t_{2}\in[T]$ during a run of algorithm (AG-Norm). Then, deterministically,

Moreover, with probability at least $1-\delta$, the following bound also holds

As a consequence of Lemma 2, we derive $\sum_{t\in[T]}\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}=T(\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert+\eta LT)^{2}=\mathcal{O}(T^{3})$ deterministically, and an analogous bound of $\mathcal{O}(T^{2}\log(\nicefrac{{T}}{{\delta}}))$ with probability $1-\delta$. Of course, Lemma 2 only gives a much weaker control over $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}$ than a uniform bound, and has not (to the best of our knowledge) been previously exploited. However loose, this bound nonetheless is one of the key steps to removing the uniform gradient bound, and may be of independent interest (e.g., useful for refining the convergence rates for strongly convex problems).

As mentioned earlier, a key difficulty in analyzing adaptive algorithms is the bias introduced by the correlation between the step size $\eta_{t}$ and the stochastic gradient $\bm{g}_{t}$ at each time $t$. To analyze the convergence of such algorithms, it is useful to introduce the following “decorrelated” step size.

Motivating the Proof

We have discussed the two main challenges in Section 1.1: unbounded gradients and affine variance. Now that we have the required mathematical definitions from Section 2, we discuss these challenges in more detail. Adaptive stochastic gradient methods exhibit two difficulties not present in the non-adaptive regime: (i) Since the step size $\eta_{t}$ depends on the trajectory of stochastic gradients, one must argue about the scaling of these stochastic gradients, and (ii) the step size is correlated with the current gradient, $\bm{g}_{t}$, as well as the past gradients. These manifest themselves as follows: by $L$-smoothness (Assumption 3) and the AdaGrad-Norm algorithm (AG-Norm), we have that

When $\eta_{t}$ and $\bm{g}_{t}$ are conditionally independent, then the inner product term above is mean-zero. As a consequence, as long as the step size $\eta_{t}\leq\nicefrac{{1}}{{L(1+\sigma_{1}^{2})}}$, (5) immediately implies that

Although in the non-adaptive setting, we could simply choose $\eta_{t}=\Omega(\nicefrac{{1}}{{\sqrt{T}}})$, in the adaptive regime it is no longer obvious that such a condition holds. One may observe, however, that by Jensen’s inequality and Definition 3

Affine Variance: Upper-bounding the bias.

The bias term in (3) presents another difficulty in analyzing the rate of convergence in the adaptive setting. Specifically, in the affine variance setting

Main Results

In this section, we sketch out the key ideas that go into deriving a bound on the convergence rate of AdaGrad-Norm to a first order stationary point. Our main result is the following:

With probability at least $1-\delta$, the iterates of (AG-Norm) satisfy:

where $C\propto(1+\sigma_{1})\left(\nicefrac{{F(\mathbf{w}_{1})-F^{*}}}{{\eta}}+b_{0}+\sigma_{0}+(1+\sigma_{1}^{2})\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert+(1+\sigma_{1}^{6})\eta L\right)^{2}+o(\nicefrac{{1}}{{T}})$.We use the notation $x\propto y$ to mean $\beta\cdot y\leq x\leq\alpha\cdot y$ for some absolute constant $\alpha>\beta$ independent of all problem parameters. Moreover, when $\sigma_{1}\leq\nicefrac{{1}}{{8}}$, then with probability at least $1-\delta$,

where $A\propto\nicefrac{{F(\mathbf{w}_{1})-F^{*}}}{{\eta}}+\sigma_{0}+\eta L$, B\propto(1+\sigma_{1}^{\nicefrac{{3}}{{2}}})(b_{0}+\sigma_{0}+\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert+\eta L{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}+\nicefrac{{F(\mathbf{w}_{1})-F^{*}}}{{\eta}})^{2}}, and C^{\prime}\propto{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}(1+\sigma_{1}^{2})(b_{0}+\sigma_{0}+\eta L+\nicefrac{{F(\mathbf{w}_{1})-F^{*}}}{{\eta}})^{2}}.

4 demonstrates two interesting regimes for our guarantee. Namely, (11) shows a $\widetilde{\mathcal{O}}(\nicefrac{{1}}{{\sqrt{T}}})$ convergence rate for any choices of $b_{0},\eta>0$, thus establishing our parameter-free guarantee. However, this bound does not recover the $\nicefrac{{1}}{{T}}$ convergence rate in the “small-noise” regime. Through a minor modification to the proof technique used to obtain (11), we are able to derive (12), which demonstrates that (AG-Norm) recovers an $\widetilde{\mathcal{O}}(\nicefrac{{1}}{{T}})$ rate of convergence when $\sigma_{0},\sigma_{1}=\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$ – the rate obtainable by a well-tuned gradient descent in the noiseless regime up to logarithmic factors. We emphasize that (AG-Norm) does not require a priori knowledge of the smoothness parameter $L$ or the variance parameters $\sigma_{0},\sigma_{1}$ to obtain either of the convergence rates in (11) or (12). Indeed, (AG-Norm) adapts automatically to obtain the faster rate in the “small-noise” regime.

As displayed in (9), the affine variance scaling introduces additional bias that our analysis must handle. Indeed, this bound taken together with (3) implies the following lemma.

Recall the step size proxy of Definition 3 and the notation in Definition 6. With $c_{0}=2\sigma_{0}\eta+\nicefrac{{L\eta^{2}}}{{2}}$, we obtain

Key Idea: Compensating for the “bad” times.

Lemma 7 shows that, even when we focus on the good times, we still must argue about the deviations at bad times to obtain a convergence guarantee. In order to address this problem, we begin by rewriting Lemma 7 by: (i) upper bounding the “bad” times using the (potentially quite large) bound obtained from Lemma 5, and (ii) subtracting some of the “good” deviation terms from both sides to compensate for the bad terms.

In the same setting as Lemma 7, we have that

2 Bounding the Expected Sum of Gradients via Recursive Improvement

Suppose that, for some parameters $x\in$, $y\geq 1$, $h(T)$ a sufficiently large polynomial function of $T$, and sufficiently large constant $c_{2}$,

In particular, as a consequence of Lemma 2,

3 Wrapping up

With these bounds from Lemmas 12 and 13 in place, obtaining the convergence result for (AG-Norm) in 4 is immediate. Indeed, we note that Lemma 12 gives us essentially the same bound as the one obtainable in the uniformly-bounded variance case (10) (modulo the summation over the set $\widetilde{S}$ instead of all times $[T]$). Therefore, we may apply (essentially) the same Hölder’s inequality argument as in [WWB19], replacing their application of the uniform gradient bound with our bound on the expected sum of gradients from Lemma 13, and taking extra care that our summation from Lemma 12 is over a random set $\widetilde{S}$. We give the full proof of this theorem in Appendix F.

While we focus in this paper on the convergence rate of one particular adaptive SGD method, our methods are not overly specialized to AdaGrad-Norm. Indeed, using nearly identical arguments per coordinate, we can obtain similar $\widetilde{\mathcal{O}}(\nicefrac{{1}}{{\sqrt{T}}})$ convergence rates under similar assumptions for coordinate-wise AdaGrad, albeit with an additional polynomial dependence on $d$.

Conclusion

Acknowledgements

This research is supported in part by NSF Grants 1952735, 1934932, 2019844, 2127697, and 2112471, ARO Grant W911NF2110226, AFOSR MURI FA9550-19-1-0005, the Machine Learning Lab (MLL) at UT Austin, and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program.

References

Appendix A Preliminaries

Here, we provide proofs for claims from Section 2, as well as some auxiliary results and notation. We additionally state some definitions that will be useful for proving our results.

For any sequence $\{a_{s}\}_{s=0}^{\infty}$ such that $a_{0}>0$ and $a_{s}\geq 0$ for all $s$,

The base case of $T=0$ holds with equality. Let us now assume that the claim holds at $T$. Then, we have that

where the first inequality holds by the induction hypothesis, and the second because of the fact $x<-\log(1-x)$ (where $\log(\cdot)$ denotes the natural logarithm). ∎

Our analysis will focus on adaptive gradient algorithms with a particularly convenient structure, which we refer to as the Bounded Step-Size Property

We say that an optimization algorithm has $\beta_{1}$-Bounded Step-Sizes if, for any pair of adjacent iterates $(\mathbf{w}_{t},\mathbf{w}_{t+1})$ generated by the algorithm, the following inequality holds deterministically:

Another convenient property of the algorithms we study is what we call the Decay Property:

We say that an optimization algorithm satisfies the $(\beta_{2},b_{0})$-Decay Property if the iterate sequence $\{\mathbf{w}_{t}\}_{t\in[T]}$ satisfies the following inequality deterministically:

We observe that these property is satisfied by a number of interesting adaptive gradient algorithms.

AdaGrad-Norm has $\eta$-Bounded Step-Sizes and $(\eta^{2},b_{0})$-Decay. The first follows since for any time $t\geq 0$,

The second is an immediate consequence of Lemma 15, taking $a_{0}=b_{0}^{2}$ and $a_{s}=\left\lVert\bm{g}_{s}\right\rVert^{2}$ for $s>0$.

Coordinate-wise AdaGrad (with coordinate-dependent step sizes

has $\eta\cdot\sqrt{d}$-Bounded Step-Sizes and $(d\eta^{2},b_{0})$-Decay. The first follows since since $\left|\mathbf{w}_{t+1,i}-\mathbf{w}_{t,i}\right|\leq\eta$ for every coordinate $i\in[d]$. The second follows by applying Lemma 15 to the sum of $|\mathbf{w}_{t+1,i}-\mathbf{w}_{t,i}|^{2}=\eta^{2}\frac{\left(\bm{g}_{t,i}\right)^{2}}{b_{t-1,i}^{2}+\left(\bm{g}_{t,i}\right)^{2}}$ for each coordinate.

We note here that all of the remaining results in this section could be stated in more generality by using Definitions 16 and 17. To showcase our ideas in the simplest manner, we will state everything in the context of the AdaGrad-Norm algorithm (AG-Norm).

By Assumption 3 and 18, we also have the following simple, but quite useful, facts, which give us crude but, crucially, polynomial (in $T$) bound on $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}$:

Consider the AdaGrad-Norm algorithm (AG-Norm) running on an $L$-smooth objective function $F$. Then, for any times $t_{2}\geq t_{1}$,

The proof follows by first applying the triangle inequality and using a telescoping sum to bound

then noting that, for each $s\in[t_{1},t_{2}]$, by Assumptions 3 and 18,

The above bound on $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert$ is quite useful, since it guarantees a polynomial (in $T$) bound for $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert$. However, note that this bound is much more crude than the bound assumed by [WWB19, DBBU20] (where they assumed $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}\leq B<\infty$ for every $t$). It turns out that, on “nice” sample paths, a significantly tighter bound can be derived. Intuitively, these sample paths are those for which the quantity $b_{T}^{2}=b_{0}^{2}+\sum_{t=1}^{T}\left\lVert\bm{g}_{t}\right\rVert^{2}$ is bounded by a polynomial in $T.$

For any time s\in{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\{0\}\cup}[T] and failure probability $\delta\in(0,1]$, we define the following “nice event”:

and take $\mathcal{E}_{s}(\delta)=\emptyset$ for $\delta>1$.

As we will soon see, bounding the quantity $\sum_{t\in[T]}\left\lVert\mathbf{w}_{t+1}-\mathbf{w}_{t}\right\rVert^{2}$ will be crucial in many parts of our analysis. Under the “nice” events from Definition 22, this quantity can be easily controlled:

For any choice of $b_{0}^{2}$, and any sample path, (AG-Norm) satisfies

Further, assuming that the “nice event” (20) ($\mathcal{E}_{s}(\delta)$) is true at time $s\in[T]$, and taking $f(\cdot)$ as in (21),

In particular, since $\mathcal{E}_{0}(1)$ is (trivially) always true, the above implies that

Additionally, when $\mathcal{E}_{T}(\delta)$ (the nice event at time $T$) is true,

We already established (22) in 18. For the remaining inequalities, we may assume without loss of generality that $\delta\leq 1$. Indeed, whenever $\delta>1$, then $\mathcal{E}_{s}(\delta)=\emptyset$ by Definition 22, and thus $\mathcal{E}_{s}(\delta)$ is never true, so all of the claims follow trivially.

To show (23), we note that, on any sample path, by (22) and Jensen’s inequality,

To bound this term above, first observe that, as noted in (3), Assumptions 1 and 2 imply that

Further, when (20) ($\mathcal{E}_{s}(\delta)$) is true at time $s$, we have that, by Lemma 21,

Combining the above bounds, we conclude that

as claimed. Finally, observe that (24) and (25) follow immediately from (23), taking $s=0$ (noting that $\mathcal{E}_{0}(1)$ is true deterministically) and $s=T$, respectively. ∎

With the above construction in place, we are ready to give a slightly stronger bound for $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}$, improving upon Lemma 21 (with high probability) in many interesting regimes.

Consider any time $t\in[T]$ during a run of (AG-Norm) initialized at a starting point $\mathbf{w}_{1}$, and is currently at iterate $\mathbf{w}_{t}$. Then,

and additionally, assuming that $\mathcal{E}_{t}(\delta)$ from Definition 22 is true, and taking $f(\cdot)$ as in (21), then

The proof follows effectively from the same arguments used to prove Lemma 21, only using the improved bound from Lemma 23 in place of Lemma 21. Indeed, using the same decomposition, and applying Cauchy-Schwarz, we have that

where the first inequality follows from the decomposition used in the proof of Lemma 21, the second follows by Cauchy-Schwarz, and the third from Lemma 15.

The second claim follows immediately from the above, combined with Lemma 23. ∎

Appendix B Deriving the Starting Point

Here, we provide the proof for the starting point of our analysis, Lemma 5, from Section 4.

We will begin by using our assumption of $L$-smoothness, along with the definition of the algorithm, to get the bound:

Hence, by taking expectations of our first inequality and adding this mean-zero quantity to the resulting expression, we have that

We will now focus on bounding the second term. Observe that, denoting $a=b_{t-1}^{2}+\left\lVert\bm{g}_{t}\right\rVert^{2}{}$ and $b=b_{t-1}^{2}+(1+\sigma_{1}^{2})\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}{}+\sigma_{0}^{2}$,

Plugging this bound into the above, and taking expectation with respect to the filtration at $t-1$, we have shown that

We will now show that the second and third terms above have the same upper bound. Focus on the second term above, we apply Hölder’s inequality and the affine variance assumption to conclude that

Now, focusing on the third term, by Jensen’s inequality to the concave function $\sqrt{\cdot}$, we know that

which show that the second and third terms have exactly the same upper bound. Combining these expressions and rearranging, we find

Appendix C Most Times are (Typically) Good

Here, we provide proofs regarding properties and consequences of the “good” times (Definition 6) from Section 4.

Recalling the step size proxy of Definition 3 and the notation in Definition 6, we obtain

where $c_{0}=2\sigma_{0}\eta+\nicefrac{{L\eta^{2}}}{{2}}$, and $f(\cdot)$ is the function defined in (21).

Observe that an equivalent condition for a time $t$ to be “good” in the sense of Definition 6 is:

Now, summing the above expression over all times $t\in[T]$, and applying Lemma 23, we find that

Now, by (23) in Lemma 23, we know that, whenever $\mathcal{E}_{s}(\delta)$ is true, then

By (27), we additionally know that, for each time $t_{1}\leq T$,

Appendix D Compensating for “Bad” Time-Steps

Here, we provide proofs for the compensation arguments presented in Section 4

Let us begin by proving that, for any times $t\geq t^{\prime}$,

The claim is trivial when $t^{\prime}=t,$ so we focus on the case when $t^{\prime}<t$. Let us denote $a=b_{t-1}^{2}+(1+\sigma_{1}^{2})\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}+\sigma_{0}^{2}$ and $b=b_{t^{\prime}-1}^{2}+(1+\sigma_{1}^{2})\left\lVert\nabla F(\mathbf{w}_{t^{\prime}})\right\rVert^{2}+\sigma_{0}^{2}$. Then, observe that

Therefore, we can observe that the step sizes are sufficiently close, since

where the last line follows by Lemma 21. We will now use this observation in order to prove the claimed inequality. We will proceed by considering two cases.

In the first case, if $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert>2\eta L(t-t^{\prime})$, then by Lemma 21, $\left\lVert\nabla F(\mathbf{w}_{t^{\prime}})\right\rVert\geq\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert-\eta L(t-t^{\prime})\geq\nicefrac{{1}}{{2}}\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert$. This implies that

In the alternative case, when $\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert\leq 2\eta L(t-t^{\prime})$, then

Now, we will use Lemma 10 to bound the first term above. We will use the trivial bound for the second term: by Definition 3 and Lemma 21, we may bound each term inside of the sum of the second expression above as:

where $c_{1}=\widetilde{c}_{0}+\widetilde{c}_{1}.$

The result follows immediately by combining Lemmas 29 and 27. Note that this result, up to logarithmic factors, takes essentially the same form as in the uniformly-bounded setting (10). ∎

Appendix E Bounding the Expected Sum of Gradients via Recursive Improvement

Here, we provide a proof for the recursive improvement argument presented in Section 4.

Suppose that, for some constants $x\geq 1$ and $y\geq 0$, the following inequality is true:

Then, in fact, the following tighter bound also holds:

In particular, as a consequence of Lemmas 24 and 23,

The proof will proceed in three steps, in which we will invoke the auxiliary Lemmas 32, 33 and 34. It is straightforward to verify that the constant $c_{2}$ specified in this lemma, as well as the choice of $h(T)=T^{2}f(T)$, satisfy the constraints from those lemmas. Thus, we are free to use these results to prove our desired result.

In order to “remove” the indicator from the expectation above, we will need to show that, when $\mathcal{E}_{T}(\delta)$ is false, $\sum_{t\in\widetilde{S}}\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}$ cannot be too large. Recall that we have two main tools to upper bound the size of this sum: Lemma 21, which gives a deterministic upper bound of $\mathcal{O}(T^{3})$, and Lemma 24, which gives a high-probability upper bound of $\widetilde{\mathcal{O}}(T^{2})$. These insights allow us to prove Lemma 33, which tells us that

Step 2: Bounding the “good” terms.

With the indicator removed from the above expression, we are now ready to use Lemma 30 together with (40) and (41) to obtain a bound on the expected size of the gradients at the good times:

where the second inequality follows by upper bounding $4\sqrt{2}\nicefrac{{(F(\mathbf{w}_{1})-F^{*}+c_{1})}}{{\eta}}\leq\nicefrac{{\sqrt{c_{2}}}}{{4}}.$ Hence, by choosing $\gamma_{1}=\max\{\nicefrac{{(4-x)}}{{3}},0\}$ and $\gamma_{2}=\max\{\nicefrac{{2(y-1)}}{{3}},0\}$Note that these choices of $\gamma_{1},\gamma_{2}$ satisfy the requirements of Lemmas 32, 33 and 34. Indeed, $\gamma_{1},\gamma_{2}\geq 0$ by construction. Further, since $x\geq 1$, we have that $\gamma_{1}\leq\nicefrac{{(4-x)}}{{3}}\leq 1$ and, whenever $x\in$, $x+\gamma_{1}=\nicefrac{{(2x+4)}}{{3}}\geq 2$, and when $x>4$, $x+\gamma_{1}=x>4>2$. Finally, $y-\gamma_{2}=\min\{\nicefrac{{(y+2)}}{{3}},y\}\geq 0$ since $y\geq 0$., we conclude that

Step 3: Bounding the “bad” terms.

E.2 Technical Lemmas

We divide the proof in two cases: (1) $\delta>1$, and (2) $\delta\leq 1$. In the first case, the claimed result (45) holds trivially, since $\mathcal{E}_{T}(\delta)=\emptyset$ by definition (see Definition 22), and thus,

Let us assume that $\mathcal{E}_{T}(\delta)$ (the “nice” event from Definition 22) is true. Then, we have that

where the first inequality follows by definition of $\mathcal{E}_{T}(\delta)$ and by the assumed bound (44). The second inequality follows since $1\leq\nicefrac{{1}}{{\delta}}$, and the third since $x\geq 1$ and $\log(h(T))\geq 1$. The final inequality follows by plugging in our choice of $\delta$, and using the fact that $c_{2}\geq b_{0}^{2}+\sigma_{0}^{2}$.

Now, since $b_{t-1}^{2}\leq b_{T}^{2}$, the above inequality implies that

where the first inequality follows since $b_{t-1}^{2}\leq b_{T}^{2}$ and by Lemma 21, and the second since $x+\gamma_{1}\geq 2$ and $c_{2}\geq(1+\sigma_{1}^{2})(\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert+\eta L)^{2}+\sigma_{0}^{2}$.

Now, in order to “remove” the indicator from the expectation, we will need to show that, when $\mathcal{E}_{T}(\delta)$ is false, $\sum_{t\in\widetilde{S}}\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{2}$ cannot be too large. Recall that we have two main tools to upper bound the size of this sum: Lemma 21, which gives a deterministic upper bound of $\mathcal{O}(T^{3})$, and Lemma 24, which gives a high-probability upper bound of $\widetilde{\mathcal{O}}(T^{2})$. To exploit this “lighter” regime of Lemma 24, it will be useful to introduce the following event:

where $\delta=\nicefrac{{(2+\sigma_{1}^{2})\log^{y-\gamma_{2}}(h(T))}}{{T^{\gamma_{1}}}}$ is the same choice as in Lemma 32. By definition, $\mathcal{E}^{\prime}\subset\mathcal{E}_{T}(\delta)^{c}$, so

where in the last inequality, we use the following facts: $\nicefrac{{1}}{{\delta}}=\frac{T^{\gamma_{1}}}{(2+\sigma_{1}^{2})\log^{y-\gamma_{2}}(h(T))}\leq T^{2}$ (chosen in Lemma 32) and $\nicefrac{{f(T)}}{{\delta}}\leq T^{2}f(T)\leq h(T)$ which hold since $\gamma_{1}\leq 2$, $y-\gamma_{2}\geq 0$, and by the initial conditions on $h(T)\geq e$. Now, since $\gamma_{1}\leq 1$ by assumption (which implies that $2-\gamma_{1}\geq 1$), we may simplify the above to conclude that

By our assumption that $c_{2}\geq 16(2+\sigma_{1}^{2})(\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert^{2}+L^{2}\eta^{2})$, the claimed bound is immediate. ∎

Therefore, choosing $\delta=\nicefrac{{1}}{{T^{2}}}$, and assuming that $T^{2}f(T)\leq h(T)$, we conclude that

Appendix F Obtaining the Convergence Rate for AdaGrad-Norm

Here, we provide a proof for the main result of this paper, a proof of convergence for the AdaGrad-Norm algorithm.

With probability at least $1-\delta$, the AdaGrad-Norm algorithm (AG-Norm) for any choice of parameters $\eta,b_{0}^{2}>0$ satisfies:

Furthermore, whenever $\sigma_{1}\leq\nicefrac{{1}}{{8}}$, then with probability at least $1-\delta$, (AG-Norm) also satisfies:

where $c_{0}=2\eta\sigma_{0}+\nicefrac{{L\eta^{2}}}{{2}}$.

We note that the second bound in 35, (35), is particularly interesting in the regime when $\sigma_{0},\sigma_{1}=\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$. Indeed, in this setting, our bound yields a $\widetilde{\mathcal{O}}(\nicefrac{{1}}{{T}})$ convergence rate which one should expect in the noiseless regime.

Focusing now on lower bounding the numerator of (49),

where the lower bound above follows since the average is always larger than the minimum. If it were the case that $\widetilde{S}=[T]$, then, at this point, we would essentially be done with our proof. However, since $\widetilde{S}$ is a random set, we must take some additional care. Because $|\widetilde{S}^{c}|$ is $\mathcal{O}(\log(T))$ in expectation by Lemma 26, this is only a minor technicality. Indeed,

Therefore, collecting the results we have derived so far into a lower bound on the right-hand side of (49), and applying the result of Lemma 30 to upper bound the left-hand side of (49), we have obtained the following upper bound:

where the inequality follows since $\min_{t\in[T]}\left\lVert\nabla F(\mathbf{w}_{t})\right\rVert^{\nicefrac{{4}}{{3}}}\leq\left\lVert\nabla F(\mathbf{w}_{1})\right\rVert^{\nicefrac{{4}}{{3}}}$. The above failure probability can be easily upper bounded via Markov’s inequality:

Hence, by a final application of Markov’s inequality, we obtain, for any $\delta\in(0,1)$,

Solving this quadratic inequality, we conclude that

In particular, this implies by Markov’s inequality that, with probability at least $1-\delta$,

This shows that, in the setting when $\sigma_{0}^{2},\sigma_{1}^{2}=\mathcal{O}(\nicefrac{{1}}{{\sqrt{T}}})$, then we recover a $\widetilde{\mathcal{O}}(\nicefrac{{1}}{{T}})$ convergence rate, as in the noiseless setting. ∎