Prodigy: An Expeditiously Adaptive Parameter-Free Learner

Introduction

Optimization is an essential tool in modern machine learning, enabling efficient solutions to large-scale problems that arise in various domains, such as computer vision, natural language processing, and reinforcement learning. One of the key challenges is the selection of appropriate learning rates, which can significantly impact the convergence speed and the quality of the final solution. Learning-rate tuning has been particularly challenging in applications where there are multiple agents that use their own optimizer. For instance, when training Generative Adversarial Networks (GANs) (Goodfellow et al., 2020), there are two neural networks with different architectures. In federated learning, tuning is even more challenging (Khodak et al., 2021), since there might be billions of devices (Kairouz et al., 2021), each optimizing their objective locally. Another example is Neural Architecture Search (NAS) (Zoph and Le, 2017), where the goal is to find the best neural network architecture automatically by training a lot of networks and evaluating them on a validation set. In cases like that, it becomes very expensive to manually tune the learning rate.

In recent years, "parameter-free" adaptive learning rate methods (Orabona and Tommasi, 2017; Cutkosky and Orabona, 2018; Zhang et al., 2022; Carmon and Hinder, 2022; Ivgi et al., 2023) have gained considerable attention due to their ability to automatically adjust learning rates based on the problem structure and data characteristics. Among these, the D-Adaptation method, introduced by (Defazio and Mishchenko, 2023), has emerged as a promising practical approach for learning-rate-free optimization.

D-Adaptation works by maintaining a lower bound on the initial distance to solution $D=\left\|x_{0}-x_{*}\right\|$, for any $x_{*}$ in the solution set of the following problem:

In practice, the lower bound estimated by D-Adaptation increases rapidly during the course of optimization, plateauing to a value close to the true $D$. This $D$ quantity is the key unknown constant needed to set the learning rate for non-smooth optimization methods, forming the numerator of the step size:

and the denominator is based on the Adagrad step size Duchi et al. (2011); Streeter and McMahan (2010); Ward et al. (2019). The Gradient Descent form of D-Adaptation simply plugs in the current lower bound at each step in place of $D$. This simple approach can be applied to estimate the step size in Adam (Kingma and Ba, 2015), which yields state-of-the-art performance across a wide-range of deep learning problems. Defazio and Mishchenko (2023) also show that asymptotically, D-Adaptation is as fast as specifying the step size using the true $D$ (up to small constant factors).

In this paper, we present two novel modifications to the D-Adaptation method that enhance its worst-case non-asymptotic convergence rate. By refining the algorithm’s adaptive learning rate scheme, we achieve improved performance in terms of convergence speed and solution quality. We then conduct extensive experiments that consistently demonstrate that the improved D-Adaptation methods adapt the learning rate much faster than the standard D-Adaptation, leading to enhanced convergence rates and better optimization outcomes.

Prodigy Approach

To understand how we can improve upon D-Adaptation, let us take a closer look at some nuggets in its analysis. In D-adapted Dual Averaging, the gradient at iteration $k$ is scaled with weight $\lambda_{k}$. This leads to the error term

The theory then proceeds to upper bound this sum using the largest of all $\lambda_{k}$’s by using the upper bound $\lambda_{k}\leq\lambda_{n}$. This, however, is quite pessimistic since then $\lambda_{k}$ is set to be $\lambda_{k}=d_{k}$, so $\lambda_{n}$ can be as large as $D$ and $\lambda_{k}$ can be as small as $d_{0}$. Therefore, replacing $\lambda_{k}^{2}$ with $\lambda_{n}^{2}$ can introduce a multiplicative error of $\frac{D^{2}}{d_{0}^{2}}$ in this term.

We take a different approach and instead handle the error term using modified Adagrad-like step sizes. In the Adagrad theory, the error term does not have any $\lambda_{k}^{2}$ factors, which is exactly why Adagrad places $\sqrt{\sum_{i=0}^{k}\|g_{i}\|^{2}}$ in the step-size denominator. The required modification is then obvious: since the error terms are now $d_{i}^{2}\|g_{i}\|^{2}$ instead of $\|g_{i}\|^{2}$, the new adaptive step size should be

for the Gradient Descent algorithm. This way, we can still control the error term of D-Adaptation but the obtained step size is provably larger since $d_{k}$ is non-decreasing. For instance, for Gradient Descent, we have

Having larger step sizes while preserving the main error term is the key reason why the new algorithms converge, as we show below, with a faster rate.

Notice, however, that the methods might still be slow because the denominator in the step size might grow too large over time. To remedy this, we introduce a modification for the Gradient Descent step size by placing an extra weight $\lambda_{k}$ next to the gradients:

In fact, the modified step size might even increase between iterations, whereas the Adagrad step size always decreases. We will show that as long as $\lambda_{k}$ does not grow too quickly, the worst-case convergence rate is almost the same.

To have non-asymptotic theory, we also introduce in our algorithms an extra term $G^{2}$ in the denominator which upper bound the gradient norm. We define it formally in the assumption below.

Algorithm 1 and Algorithm 2 give Gradient Descent and the Dual Averaging variants of our new method. In contrast to Adagrad, they estimate the product of $D$ and $G$ in the denominator, so we call the proposed technique Prodigy. We give the following convergence result for Algorithm 1:

Assume $f$ is convex and $G$-Lipschitz. Given any weights $1\leq\lambda_{0}\leq\dotsb\leq\lambda_{n}$, the functional gap of the average iterate of Algorithm 1 converges as

where $\hat{x}_{n}=\frac{1}{n+1}\sum_{k=0}^{n}\eta_{k}x_{k}$ is the weighted average iterate.

Notice that we have the freedom to choose any non-decreasing sequence $\lambda_{k}$ as long as the right-hand side is decreasing. This allows us to put much more weight on the recent gradients and get more reasonable step sizes. For instance, we can choose $\lambda_{k}=k^{p}$, where $p>0$ and since $\sum_{k=0}^{k}k^{2p}=\mathcal{O}(k^{2p+2})$, it would result in an extra factor of $1+p$ in the numerator due to the log term. The denominator, on the other hand, would increase as well, giving us a trade-off that depends on the values of $d_{k}$’s. We note that weights $\lambda_{k}=k$ have appeared previously in Accelegrad (Levy et al., 2018) and UniXGrad (Kavis et al., 2019), which combine Adagrad step sizes with momentum.

To understand why this improves the convergence rate, consider the following lemma, which we prove in the appendix. The lemma presents an upper bound on the terms related to the $d_{k}$ sequence in the right-hand side of equation 1.

Let $d_{0}\leq d_{1}\leq\dotsb\leq d_{N}$ be positive numbers and assume $N\geq 2\log_{2+}(\frac{d_{N}}{d_{0}})$, where $\log_{2+}(\cdot)=1+\log_{2}(\cdot)$. Then,

In contrast to the bound in Defazio and Mishchenko (2023), we bound $\frac{d_{t+1}}{\sqrt{\sum_{k=0}^{t}d_{k}^{2}}}$ instead of $\frac{d_{t+1}}{\sum_{k=0}^{t}d_{k}}$. This is the reason why the overall guarantee improves by a factor of $\sqrt{\log_{2}(D/d_{0})}$. For instance, if we set $\lambda_{k}=1$ for all $k$ and substitute the bound from Lemma 1, we get the convergence rate

where $t\leq n$ is chosen as the argmin from Lemma 1. Furthermore, for arbitrary increasing positive weights, we get the following guarantee by applying Lemma 1 directly to the bound in Theorem 1:

Even though our theory does not guarantee that it is beneficial to use increasing weights $\lambda_{k}$, this result is, to the best of our knowledge, new for Adagrad-like methods. It allows for a wide range of choices in $\lambda_{k}$. For example, if we set $\lambda_{k}=\beta_{2}^{-k^{p}}$ with $\beta_{2}<1$ and $p<1/3$, then the method is still guaranteed to converge at the rate of $\mathcal{O}\left(\frac{1}{n^{(1-3p)/2}}\right)$. This is of particular interest when we study Adam-like methods, see Section 6 for a discussion.

The logarithmic term $\log(n+1)$ is, however, not necessary and only arises due to the use of Gradient Descent update. The Dual Averaging update, provides a tighter guarantee as given in the next theorem.

Let $f$ be a convex and $G$-Lipschitz function. For Algorithm 2, it holds that:

where $t=\arg\min_{k\leq n}\frac{d_{k+1}}{\sqrt{\sum_{i=0}^{k}d_{i}^{2}}}$ and $\log_{2+}(\cdot)=1+\log_{2}(\cdot)$.

Comparing this with the previous rate, the only difference is the removal of a multiplicative $\log(n+1)$ factor. This improvement, however, is mostly theoretical as Gradient Descent typically performs better in practice than Dual Averaging. We also note that we do not have a convergence result for Algorithm 2 with weights other than $\lambda_{k}=d_{k}^{2}$. This is due to the fact that the DA analysis requires the step size to be monotonically decreasing, so we cannot place an extra weighting factor in the numerator of $\gamma_{k+1}$.

Resetting Approach

Algorithm 3 describes a variant of D-Adaptation where the Dual Averaging process is reset whenever the current $d_{k}$ estimate increases by more than a factor of 2. We call the interval between resetting events an epoch. This resetting process has a number of other effects:

The step-size sequence $\gamma$ is also reset, resulting in larger steps right after the reset.

The convergence of the method is proven with respect to an unweighted average of the iterates, rather than a weighted average.

Since the quantities tracked to compute $\hat{d}$ are also reset, the value of $\hat{d}$ often will increase more rapidly than it can when using the standard D-Adaptation estimate.

This resetting variant has the advantage of being significantly simpler to analyze in the non-asymptotic case than standard D-Adaptation or Prodigy. This makes it well suited to be used as a basis for extensions and modifications of D-Adaptation.

Under the assumption of convex and $G$-Lipschitz $f$, we have for Algorithm 3:

This is the same rate as we established for the Dual Averaging variant of Prodigy, but we return the average of all iterates, rather than an average computed up to some point $t\leq n$, a significant simplification. However, due to the resetting operation, this method is not expected to work as well as Prodigy in practice.

Lower Complexity Bounds for Exponentially Bounded Algorithms

We can obtain an interesting class of algorithms, which contains our two D-Adaptation variants, by restricting the rate of growth.

An optimization algorithm is exponentially bounded if there exists a constant $d_{0}$, so that for any sequence of G-bounded gradients it returns a sequence of iterates such that for all $k$:

D-Adaptation, DoG, Prodigy and D-Adaptation with resetting are exponentially bounded.

A simple lower complexity bound can be established via a simple 1-dimensional resisting oracle. The bound depends on the "scale" of the initial step of the algorithm, which is the size of the initial step from $x_{0}$ to $x_{1}$. This initial step is $g_{0}\cdot d_{0}/\sqrt{G^{2}+\left\|g_{0}\right\|^{2}}$ for D-Adaptation, and can be though of as an algorithm-agnostic measure of $d_{0}$.

Our lower bound allows the resisting oracle to choose a constant $D$ after seeing $x_{1}$, which is a much stronger oracle than required for establishing a lower bound. Ideally, a lower bound could be established where the constant $D$ is fixed but unknown to the algorithm, and the actual distance to solution $\left\|x_{0}-x_{*}\right\|\leq D$ given by the oracle is allowed to depend on the iterate sequence.

The primary consequence of this difference is that our construction only tells us that hard problems exist for $n$ small relative to $D/d_{0}$, of the scale $n<\log(D/d_{0})$. It remains an open problem to show a more general lower bound for larger $n$. This is in a sense a trivial consequence of the exponentially bounded property, but is actually representative of the real behavior of the methods during the early steps of the algorithm, where both $n$ and $d_{k}$ actually are small. Any more general lower bound must cover this case.

Our new D-Adaptation variants are optimal among exponentially bounded algorithms for this complexity class:

Consider any exponentially bounded algorithm for minimizing a convex $G$-Lipschitz function starting from $x_{0}$, which has no knowledge of problem constants G and D. There exists a fixed gradient oracle such that any sequence of $x_{1,\dots},x_{n}$, there exists a convex Lipschitz problem $f$ with $G=1$ and $\left\|x_{0}-x_{*}\right\|\leq D$ for all minimizing points $x_{*}$, consistent with the gradient oracle such that:

Using the simple construction from Theorem 5, we show in Appendix C that the class of exponentially bounded methods (potentially with an exponent other than 2) covers all Gradient Descent approaches that use an estimate of $d_{k}\leq cD$ for some constant c, and use a step size $\gamma_{k}\leq d_{k}/G$ without line-search or other additional queries. So the only way to achieve a $\log\log$ dependence on $d_{0}$ is by using a method that performs some queries that overshoot the standard $D/G$ step size by more than a fixed constant factor. Although using larger step sizes is not problematic for Lipschitz functions, it comes with the risk of causing training divergence when applied to functions whose gradients are only locally bounded by $G$, which is common in machine learning settings.

Lower complexity bounds for the average regret in the more general online learning setting also apply here. They are of the form (Zhang et al., 2022):

where $\epsilon$ is a “user-specificed constant” playing a similar role to $x_{1}$. Bounds on the average regret directly bound function value sub-optimality as

where $\bar{x}=\frac{1}{n+1}\sum_{k=0}^{n}x_{k}$.

Related Work

In this section, we review the major classes of techniques for optimizing convex Lipschitz functions with some level of problem parameter independence.

The Polyak step size Polyak (1987) trades the knowledge of $D$ for $f_{*}$, achieving optimal convergence rate without additional log factors. Stable convergence requires accurate $f_{*}$ estimates. A restarting scheme converges within a multiplicative log factor of the optimal rate Hazan and Kakade (2019). There has been substantial recent research on modifications of the Polyak step size to make it better suited to machine learning tasks (Loizou et al., 2021; Gower et al., 2021; Orvieto et al., 2022) but as of yet they have not seen widespread adoption.

Coin-betting Orabona and Tommasi (2017); McMahan and Orabona (2014); Cutkosky and Orabona (2018); Zhang et al. (2022); Orabona and Pál (2021) is a family of approaches from the online learning setting which are also applicable for convex non-smooth optimization. They work by establishing a relationship by duality between regret minimization and wealth-maximization. Existing approaches for wealth-maximization can then be mapped to algorithms for regret minimization. Coin-betting approaches give convergence rates for an equal-weighted average of the iterates of the form:

Standard D-Adaptation obtains asymptotic rates without the log factor, but was otherwise (theoretically) slower in finite time, as it had a $\log(\cdot)$ rather than a $\sqrt{\log(\cdot)}$ dependence on $D/d_{0}$:

Our two new variants close this gap, giving the same sqrt-log dependence as coin betting.

The DoG method (Ivgi et al., 2023), based on the bisection approach of Carmon and Hinder (2022), is the only other approach that we are aware of that estimates $D$ in an online fashion. DoG estimates $D$ by $\bar{r}_{k}$:

Ivgi et al. (2023) use this quantity as a plug-in estimate for the numerator of the step size, similar to D-Adaptation’s approach. This approach can divergence in theory, but with additional modifications to the step size, the "tamed" T-DoG method is shown to converge. It has a $\log_{+}(D/d_{0})$ dependence on the initial sub-optimally of the D estimate, so our approach improves on this dependence by a $\sqrt{\log_{+}(D/d_{o})}$ factor.

Malitsky and Mishchenko (2020) proposed AdGD, a method for convex optimization that does not require any hyperparameters and has a rate that is at least as good as that of the optimally tuned Gradient Descent. However, AdGD requires the objective to be locally smooth, which hinders its use in many practical problems. Latafat et al. (2023) partially addressed this gap by proposing a proximal extension, but the case of non-smooth differentiable functions has remained unstudied.

Deriving Adam-like Step Sizes

To derive an Adam-like method, which should use exponential moving average for the step size, we want to approximate Adam’s update of the exponential moving average of squared gradients:

where $g_{k}^{2}$ is the coordinate-wise square of the gradient $g_{k}$. We can achieve this using exponential weights, $\lambda_{k}=\beta_{2}^{-k/2}$, which after substituting the definition of $\eta_{k}$ give us the following identity:

The update uses exponential moving average as well, although it is more conservative as it uses $\sqrt{\beta_{2}}$ instead of $\beta_{2}$. Note that there is an extra of $(1-\beta_{2})$ in the update for $v_{k}$, which can be optionally compensated for by using the bias correction discussed by Kingma and Ba (2015). These update rules are summarized in Algorithm 4. This is the main algorithm that we study numerically in the next section.

Experiments

We test our methods on convex logistic regression as well as deep learning problems. The Prodigy method is used as presented in Algorithm 4 in all deep learning experiments.

For the convex setting, we ran a set of classification experiments. For each dataset, we used the multi-margin loss (Weston and Watkins, 1999), a multi-class generalization of the hinge loss. This non-smooth loss results in bounded gradients, which is required by our theory. We perform full-batch rather that stochastic optimization, for two reasons. Firstly, it matches the assumptions of our theory. Secondly, fast learning rate adaptation is more crucial for full-batch optimization than stochastic optimization as fewer total steps will be performed.

We performed 1,000 steps for each dataset, using a randomized $x_{0}$ and plot the results of 10 seeds. We ran both DA and SGD variants of each method. Each plot shows the accuracy of the average iterate for each method. Figure 1 shows that both our proposed algorithms greatly out-perform regular D-Adaptation. Our weighted SGD variant of D-Adaptation is faster consistently across each dataset. Additionally, it adapts faster than the DoG method (Ivgi et al., 2023) on 10 of the 12 problems.

CIFAR10.

For neural network experimentsThe PyTorch code of our optimizer is available at https://github.com/konstmish/prodigy, we consider training on CIFAR10 (Krizhevsky, 2009) with batch size 256, where D-Adapted Adam has a gap of a few percent compared to the standard Adam. We use cosine annealing with initial step size 1 for all Adam-based methods and initial step size $10^{-3}$ for Adam itself. The considered networks are VGG11 (Simonyan and Zisserman, 2014) and ResNet-50 (He et al., 2016)VGG11 and ResNet-50 implementation along with the data loaders were taken from https://github.com/kuangliu/pytorch-cifar. To simplify the experiment, we do not use weight decay, so both networks slightly overfit and do not reach high test accuracy values. All methods were run using same 8 random seeds.

We show the results in Figure 2. As we can see, this gap is closed by Prodigy, which is achieved by the larger estimates of the step size.

For DoG and L-DoG, we compute the polynomial-averaging iterate and then report the best of the average and the last iterate. We average with $\gamma=8$, see (Ivgi et al., 2023) for the details. While DoG produces larger step size estimate than Prodigy (see the right column in Figure 2, this is counterbalanced by the larger denominator in DoG. We also tried to modify DoG to use Adam-like step sizes but our heuristic modification diverged on this problem. We also observed that among DoG and its layer-wise version, L-DoG, there is no clear winner as the former performed better on VGG11 and the latter was better when training ResNet-50.

nanoGPT transformer.

We also train a 6-layer transformer network from nanoGPThttps://github.com/karpathy/nanoGPT on the Shakespeare dataset. For all methods, we use batch size 256, clip the gradients to have norm not exceeding 1 and use float16 numbers. We use AdamW with hyperparameters given in the repository, i.e., $\beta_{2}=0.99$, weight decay $0.1$, stepsize $10^{-3}$, cosine annealing with warmup over 100 steps. The same weight decay value and cosine annealing is used for Prodigy and D-Adapted Adam, except that the latter two methods use stepsize 1. We accumulate minibatches of size 12 into a batch of size 480. We tuned the weight decay for DoG and L-DoG and found the value $10^{-4}$ to work well for this problem. We ran each method with 8 random seeds and report the average as well as one-standard-deviation confidence intervals.

See Figure 3 for the results. In terms of the test loss, all methods are roughly equivalent except that DoG and L-DoG were slower to reach the best value of roughly 1.5. For the train loss, Prodigy was on par with tuned AdamW and slightly better than D-Adapted Adam. Surprisingly, the estimated step size in Prodigy was very consistent across the 8 random seeds.

1 Large-scale Adam experiments

To validate the performance on large-scale practical applications directly against D-Adaptation, we ran the subset of the experiments from Defazio and Mishchenko (2023) that use the Adam optimizer. Methods without coordinate adaptivity are known to underperform on these problems and so we exclude SGD and DoG from these comparisons.

On the smallest problem of LSTM training, Prodigy appears to converge significantly faster in training loss and slightly overfits in test loss compared to the baselines. For RoBERTa (Liu et al., 2019) and GPT (Radford et al., 2019) training on BookWiki, Prodigy matches the performance of the baseline with only negligible differences. For the application problems, DLRM (Naumov et al., 2019) on the Criteo Kaggle Display Advertising dataset, and fastMRI VarNet (Zbontar et al., 2018), Prodigy again closely matches the baselines.

ViT training.

Defazio and Mishchenko (2023) present a negative result for training vision transformer (Dosovitskiy et al., 2021), where D-Adaptation significantly underperforms tuned Adam. We investigated this effect, and we were able to reproduce this gap across a wide range of weight-decay values, although this problem has high run-to-run variance of 1-2% of test accuracy, which makes comparison difficult. Using weight decay 0.05 instead of 0.1 significantly improved performance of each variant, and so we present results for both the baselines and Prodigy at that value. We can see that Prodigy almost closes the gap between tuned Adam and D-Adaptation, giving a test accuracy of 74.63% compared to 75.4% for Adam, and more than 2% higher than D-Adaptation. See Figure 5 for the results.

Conclusion

We have presented two new methods for learning rate adaptation that improve upon the adaptation rate of the state-of-the-art D-Adaptation method. Prodigy, a form of weighted D-Adaptation, was shown to adapt faster than other known methods across a range of experiments. The second method, D-Adaptation with resetting, is shown to achieve the same theoretical rate as Prodigy with a much simpler theory than Prodigy or even D-Adaptation.

References

Appendix A Analysis of Prodigy

As a reminder, we use the notation $\log_{2+}(a)=1+\log_{2}(a)$ to denote the logarithm that is lower bounded by $1$ for any $a\geq 1$.

For any sequence of nonnegative real numbers $a_{0},\dotsc,a_{n}$

For completeness, we prove both statements here. Notice that for any $\alpha\in$, it holds $1-\sqrt{1-\alpha}\leq\alpha\leq 2(1-\sqrt{1-\alpha})$. Substituting $\alpha=\frac{a_{k}}{\sum_{i=0}^{k}a_{i}}$ gives

If we multiply all sides by $\sqrt{\sum_{i=0}^{k}a_{i}}$, the inequality above becomes

Summing over $k=0,\dotsc,n$, we get the stated bound. ∎

For any sequence of nonnegative numbers $a_{0},\dotsc,a_{n}$ and $A>0$, it holds

If $a_{i}=0$ for some $i$, we can simply ignore the corresponding summands, so let us assume that $a_{i}>0$ for all $i$. For any $t>0$ it holds $1/(1+t)\leq\log(1+1/t)$. Substituting $t=S_{k}/a_{k}$, where $S_{k}=A+\sum_{i=0}^{k-1}a_{i}$ for $k>0$ and $S_{0}=A$, we get

Summing this over $k$ from to $n$, we get

This is exactly what we wanted to prove. ∎

A.2 Proof of Lemma 1

Following the proof in Ivgi et al. , we define K=\bigl{\lceil}\log_{2}\bigl{(}\frac{d_{N}}{d_{0}}\bigr{)}\bigr{\rceil} and n=\bigl{\lfloor}\frac{N}{K}\bigr{\rfloor}. Consider a partitioning of the sequence $t\leq N$ into half-open intervals $I_{k}=\left[nk,n(k+1)\right)$ for $k=0$ to $K-1$. We want to show that there is at least one interval such that $d_{k}$ changes by at most a factor of 2 on that interval. We will use proof by contradiction.

Suppose that for all intervals, $d_{nk}<\frac{1}{2}d_{n(k+1)}$. Then $d_{k}$ at least doubles in every interval, and so:

which implies that $d_{N}/d_{0}>2^{K}$ and so $K<\log_{2}\left(d_{N}/d_{0}\right)$ which contradictions our definition K=\bigl{\lceil}\log_{2}\bigl{(}\frac{d_{N}}{d_{0}}\bigr{)}\bigr{\rceil}. Therefore, there exists some $\hat{k}$ such that $d_{n\hat{k}}\geq\frac{1}{2}d_{n(\hat{k}+1)}$. We can now proceed with proving the Lemma by considering the summation over interval $I_{\hat{k}}$ only:

A.3 GD Analysis

Assume that $d_{0}\leq D$. Then, the estimate $d_{k}$ in Algorithm 1 satisfies $d_{k}\leq D$ for all $k$.

By optimality of $f_{*}$, we have $f(x_{k})-f_{*}\geq 0$, so

Collecting the gradients in the first sum together and using Cauchy-Schwarz inequality, we obtain

Using the definition of $\hat{d}_{n+1}$, this is equivalent to $0\leq(D-\hat{d}_{n+1})\|x_{0}-x_{n+1}\|$, which implies $\hat{d}_{n+1}\leq D$. Therefore, since $d_{0}\leq D$, we can show by induction $d_{n+1}\leq D$ as well. ∎

The following inequality holds for the iterates of Algorithm 1:

Let us rewrite $\hat{d}_{n+1}$ in a slightly different manner:

Combining this with the property $\hat{d}_{n+1}\leq d_{n+1}$, we derive

Applying inequality $2\alpha\beta\leq\alpha^{2}+\beta^{2}$ with $\alpha^{2}=2d_{n+1}^{2}$ and $\beta^{2}=\frac{1}{2}\|x_{n+1}-x_{0}\|^{2}$ and plugging-in the bound above, we establish

It remains to divide this inequality by $d_{n+1}$ to get the desired claim. ∎

Assuming the weights $\lambda_{0},\dotsc,\lambda_{n}$ are positive, it holds for the iterates of Algorithm 1:

The lemma follows straightforwardly from Proposition 2 by substituting $a_{k}=\frac{d_{k}^{2}}{d_{n}^{2}}\lambda_{k}^{2}\|g_{k}\|^{2}$ for $k$ from 0 to $n$:

where in the last step we used $\frac{d_{k}^{2}}{d_{n}^{2}}\lambda_{k}^{2}\|g_{k}\|^{2}\leq\lambda_{k}^{2}G^{2}$. ∎

Given any weights $1\leq\lambda_{0}\leq\dotsb\lambda_{n}$, the functional gap of the average iterate of Algorithm 1 converges as

The first steps in the proof follow the same lines as the theory in Defazio and Mishchenko , but we still provide them for completeness.

Firstly, let us continue developing the bound proved in the proof of Lemma 2:

We upper bound the first term with the help of Lemma 3:

Since by Lemma 2, $1\leq\frac{D}{d_{n+1}}$, we can simplify it to

Using the convexity of $f$, we can apply Jensen’s inequality on the iterate $\hat{x}_{n}$ to get

Sum over $k$ from to $n$ and using $\lambda_{i}\leq\lambda_{n}$ gives

Consider Algorithm 1 with $n\geq 2\log_{2}\left(\frac{2D}{d_{0}}\right)$ and define $t=\arg\min_{k\leq n}\frac{d_{k}}{\sqrt{\sum_{i=0}^{k}d_{i}^{2}}}$. If we choose weights $\lambda_{k}=1$, then it holds

Substituting $\lambda_{k}$ in the bound of Theorem 1, we get for any $n$

Using the definition of $t$, the result of Lemma 1 and the property $d_{n}\leq D$, we obtain

Choose any $p\geq 0$ ans set the weights to be $\lambda_{k}=(k+1)^{p}$. Then,

Since the sequence $d_{0},d_{1},\dotsc$ is non-decreasing and upper bounded by $D$, there exists an index $\hat{n}$ such that $d_{k}\leq 2d_{\hat{n}}$ for any $k\geq\hat{n}$. Moreover, we have for $n\geq 2(\hat{n}+1)$

Let us plug this into the bound of Theorem 1 for $n\geq 2(\hat{n}+1)$:

Notice that the bound in Corollary 2 does not depend on $D/d_{0}$. This is only possible asymptotically for a large enough $k$ and a similar bound without weights was presented by Defazio and Mishchenko .

A.4 DA Analysis

When studying Dual Averaging, we need to introduce an extra sequence that lower bounds $\overline{d}_{n}$:

Let us show that $\hat{d}_{n+1}\geq\overline{d}_{n+1}$ by comparing their numerators:

Using the definition of $\overline{d}_{n+1}$, and the property $\overline{d}_{n+1}\leq\hat{d}_{n+1}\leq d_{n+1}$, we derive

Using inequality $2\alpha\beta\leq\alpha^{2}+\beta^{2}$ with $\alpha^{2}=\frac{2d_{n+1}^{2}}{\gamma_{n+1}}$ and $\beta^{2}=\frac{\gamma_{n+1}}{2}\|s_{n+1}\|^{2}$ and then the bound above, we establish

It remains to divide both sides by $d_{n+1}$. ∎

The Dual Averaging algorithm (Algorithm 2) satisfies

Summing inequality $f(x_{k})-f_{*}\leq\langle g_{k},x_{k}-x_{*}\rangle$ with weights $\lambda_{k}$, we get

Using Cauchy-Schwarz on the first product in the right-hand side and then telescoping the second sum, we obtain

where $t=\arg\min_{k\leq n}\frac{d_{k+1}}{\sqrt{\sum_{i=0}^{k}d_{i}^{2}}}$.

Let us sum inequality $\lambda_{k}(f(x_{k})-f_{*})\geq 0$ and then apply Lemma 6:

Clearly, this implies that $\hat{d}_{n+1}\leq D$, and by induction it follows that $d_{n+1}\leq D$ as well. Now let us upper bound the functional values:

We can drop the last two terms since $\gamma_{k}\leq\gamma_{k-1}$:

The first term in the right-hand side is readily bounded by Lemma 5:

Let us now plug-in $\lambda_{k}=d_{k}^{2}$ and bound each gradient norm using $\|g_{k}\|\leq G$:

Thus, we get the following convergence rate:

A.5 Coordinate-wise Prodigy

The gradients are upper bounded coordinate-wise: $\|g_{k}\|_{\infty}\leq G_{\infty}$.

It holds for the iterates of Algorithm 5:

As in the proof of Lemma 5, let us introduce an extra sequence $\overline{d}_{n}$:

The next step is to show that $\hat{d}_{n+1}\geq\overline{d}_{n+1}$ by comparing the numerators:

Using the definition of $\overline{d}_{n+1}$, and the property $\overline{d}_{n+1}\leq\hat{d}_{n+1}\leq d_{n+1}$, we derive

Using inequality $2\alpha\beta\leq\alpha^{2}+\beta^{2}$ with $\alpha^{2}=2d_{n+1}^{2}a_{(n+1)i}$ and $\beta^{2}=\frac{1}{2a_{(n+1)i}}s_{(n+1)i}^{2}$ for $i=1,\dotsc,p$ and then the bound above, we establish

It remains to divide both sides by $d_{n+1}$. ∎

The coordinate-wise version of Prodigy (Algorithm 5) satisfies

where $D_{\infty}=\|x_{0}-x_{*}\|_{\infty}$.

Summing inequality $f(x_{k})-f_{*}\leq\langle g_{k},x_{k}-x_{*}\rangle$ with weights $\lambda_{k}$, we get

Using Hölder’s inequality on the first product in the right-hand side and then telescoping the second sum, we obtain

where $t=\arg\min_{k\leq n}\frac{d_{k+1}}{\sqrt{\sum_{i=0}^{k}d_{i}^{2}}}$.

so we can prove by induction that $d_{n+1}\leq D_{\infty}$. Using the same bounds as before, we get for the average iterate

We now apply Proposition 1, substitute $\lambda_{k}=d_{k}^{2}$, and use $g_{kj}^{2}\leq G_{\infty}^{2}$:

Using Lemma 1, we get the rate for $t=\arg\min_{t^{\prime}\leq n}\frac{d_{t^{\prime}+1}}{\sqrt{\sum_{k=0}^{t^{\prime}}d_{k}^{2}}}$:

Appendix B Analysis of D-Adaptation with Resetting

In Algorithm 3 the $r$ counter tracks the epoch. Let $n_{r}$ represent the number of steps performed in epoch $r$. Let $R\leq\log_{2+}(D/d_{0})$ denote the total number of epochs performed before the algorithm returns, where $D=\left\|x_{0}-x_{*}\right\|$.

Consider the steps within a single epoch, dropping the $r$ index, we have that the norm of $s_{n+1}$ is bounded by:

We start with Lemma 5 from Defazio and Mishchenko , which applies within an epoch in our case since the gamma decreases within epochs:

Note that we have used a slightly tightened version, where $\gamma_{n}$ rather than $\gamma_{n+1}$, appears on the right, which easily follows by not using $\gamma_{n+1}\leq\gamma_{n}$ on the last step of their telescoping.

Using the definition of $\hat{d}_{n+1}$ and the property $\hat{d}_{n+1}\leq 2d$, we have:

Using inequality $2\alpha\beta\leq\alpha^{2}+\beta^{2}$ with $\alpha^{2}=\frac{4d^{2}}{\gamma_{n}}$ and $\beta^{2}=\frac{\gamma_{n}}{4}\|s_{n+1}\|^{2}$ and then the bound above, we establish

It remains to divide this inequality by $d$ to get:

Now plugging in $\gamma_{n}=d/\sqrt{G^{2}+\sum_{k=0}^{n-1}\|g_{k}\|^{2}}$, and using the AdaGradNorm error bound:

Starting from the bound in Defazio and Mishchenko :

Using the AdaGradNorm bound $\frac{1}{2}\sum_{k=0}^{n_{r}}\gamma_{k,r}\left\|g_{k,r}\right\|^{2}\leq D\sqrt{\sum_{k=0}^{n_{r}}\left\|g_{r,k}\right\|^{2}}\leq DG\sqrt{n_{r}+1}$. and further dropping the $-\frac{1}{2}\gamma_{n_{r}+1,r}\left\|s_{n_{r}+1,r}\right\|^{2}$ term gives the result. ∎

Starting from Lemma 10, for epoch $r$ it holds that:

We sum over epochs up to the final epoch $R$:

Jensen’s inequality tells us that for concave $\varphi$:

Applying to our case, we use $\varphi(x)=\sqrt{x}$, $a_{r}=1,$ $\sum_{r=1}^{R}a_{r}=R$, and $x_{r}=n_{r+1}$:

Applying Jensen’s inequality to obtain a bound on the average iterate completes the proof. ∎

Appendix C Lower Complexity Theory

Consider any exponentially bounded algorithm for minimizing a convex $G$-Lipschitz function starting from $x_{0}$, which has no knowledge of problem constants G and D. There exists a fixed gradient oracle such that any sequence of $x_{1,\dots},x_{n}$, there exists a convex Lipschitz problem $f$ with $G=1$ and $\left\|x_{0}-x_{*}\right\|\leq D$ for all minimizing points $x_{*}$, consistent with the gradient oracle such that:

We consider the construction of a 1D oracle for this problem. Our oracle returns $g_{0}=-1$ and $f(x_{k})=-x_{k}$ for all queries. Without loss of generality we assume that $x_{k}>0$ for all $k\geq 1$, and $G=1$.

and thus $D=\left|x_{0}-x_{*}\right|=2^{k+1}x_{1}$. and our construction uses the following function value and gradient sequence

Note that for all query points $x$, the gradient is negative, and only the left arm of the absolute value function is seen by the algorithm, so the function appears linear for all test points. Using this construction, we have:

D-Adaptation, DoG, Prodigy and D-Adaptation with resetting are exponentially bounded.

Consider the $D$ lower bound from D-Adaptation:

Note also that $\gamma_{n+1}\leq\frac{1}{G}$. So:

So the sequence $d_{n}$ is upper bounded by the sequence:

This sequence has the following closed form:

We can prove this by induction. The base case is by definition $a_{1}=a_{0}$. Then

Note that for both the Dual Averaging form and the GD form we have, we have:

It follows that D-Adaptation is exponentially bounded. The same argument applies to the resetting variant since the resetting operation does not increase the rate of accumulation of $d$.

The rest of the argument follows the D-Adaptation case, with:

For DoG, recall the basic DoG step is gradient descent with step sizes:

Suppose that $d_{k}\leq cD$ and $\gamma_{k}\leq d_{k}/G$. then:

Without loss of generality assume that $G=1$. Firstly, note that using the absolute value function as constructed in Theorem 5, it’s clear that there is always exists a function with $D_{k}\leq 2\left\|x_{k}-x_{*}\right\|$ at step $k$ consistent with the sequence of gradients seen so far. Therefore, it must hold that

We prove the result by induction. For the base case, trivially: