Source-linked AI summary
Prodigy: An Expeditiously Adaptive Parameter-Free Learner
Konstantin Mishchenko, Aaron Defazio
TL;DR
Learning-rate selection is difficult because adaptive methods require estimating the distance to the solution, while manual tuning is costly in large-scale settings. Prodigy modifies D-Adaptation to estimate this quantity with weighted updates and improved convergence. Across experiments, it adapts faster than known methods and nearly closes D-Adaptation’s gap to tuned Adam in ViT training.
Problem
Learning-rate tuning is challenging and costly, while the distance D needed to set learning rates is unknown.
Method
Prodigy modifies D-Adaptation by using weighted updates and estimating the product of D and G in the step-size denominator.
Results
Prodigy adapts faster than other known methods across experiments and reaches 74.63% test accuracy versus 75.4% for tuned Adam in ViT training.
Takeaways & Limitations
Prodigy provides a practical learning-rate adaptation method that the authors report as outperforming D-Adaptation across experiments.
Takeaways & Limitations
The convergence theory assumes that the objective is G-Lipschitz, so gradients are bounded by G.
Abstract
from arXiv · showhide
We consider the problem of estimating the learning rate in adaptive methods, such as AdaGrad and Adam. We propose Prodigy, an algorithm that provably estimates the distance to the solution $D$, which is needed to set the learning rate optimally. At its core, Prodigy is a modification of the D-Adaptation method for learning-rate-free learning. It improves upon the convergence rate of D-Adaptation by a factor of $O(\sqrt{\log(D/d_0)})$, where $d_0$ is the initial estimate of $D$. We test Prodigy on 12 common logistic-regression benchmark datasets, VGG11 and ResNet-50 training on CIFAR10, ViT training on Imagenet, LSTM training on IWSLT14, DLRM training on Criteo dataset, VarNet on Knee MRI dataset, as well as RoBERTa and GPT transformer training on BookWiki. Our experimental results show that our approach consistently outperforms D-Adaptation and reaches test accuracy values close to that of hand-tuned Adam.
1 Introduction
Learning-rate selection is difficult and costly in large-scale or multi-agent machine-learning settings. D-Adaptation addresses this by estimating the unknown distance-to-solution quantity needed for learning-rate selection, motivating Prodigy’s modification.
- Motivation: Manual learning-rate tuning becomes especially expensive when many agents, devices, or neural networks optimize separately.The paper highlights GANs, federated learning, and neural architecture search as examples.
- Existing approaches: Parameter-free adaptive methods automatically adjust learning rates from problem structure and data characteristics.D-Adaptation is presented as a promising practical learning-rate-free method.
- D-Adaptation: D-Adaptation estimates the unknown initial distance D to the solution, which is needed to set the learning rate for non-smooth optimization.Its estimate increases rapidly and plateaus near the true D in practice.
- Motivation: Prodigy is introduced as a D-Adaptation modification intended to improve worst-case non-asymptotic convergence and outperform D-Adaptation experimentally.The paper also develops a lower complexity bound for methods whose learning rates grow at most exponentially fast.
2 Prodigy Approach
Prodigy modifies D-Adaptation with weighted AdaGrad-like step sizes that preserve control of the error term while producing provably larger steps. Its theory supports flexible non-decreasing weights and improves convergence guarantees, with distinct guarantees for Gradient Descent and Dual Averaging variants.
- Method: Prodigy modifies AdaGrad-like step sizes to control D-Adaptation’s error term while producing provably larger steps because d_k is non-decreasing.The modification introduces weights next to gradients and replaces the relevant error-term factors with terms involving d_k.
- Method: The algorithms estimate the product of D and G in the denominator, motivating the name Prodigy.The non-asymptotic formulation adds G^2 to the denominator under a G-Lipschitz assumption.
- Weighting: Non-decreasing weights λ_k can emphasize recent gradients, provided the resulting right-hand side decreases.The analysis permits choices such as λ_k = k^p and discusses the resulting numerator-denominator trade-off.
- Theory: The convergence guarantee improves by a factor involving log2(D/d0), while arbitrary increasing weights receive a corresponding bound from Lemma 1.The improvement follows by substituting the lemma’s bound into the theorem’s rate expression.
- Theory: For weights λ_k = β^(-kp^2) with β^2 < 1 and p < 1/3, the method remains guaranteed to converge at the stated rate.The result is highlighted as relevant to Adam-like methods.
- Theory: Dual Averaging removes the multiplicative log(n+1) factor, but the theory provides no convergence result for weights beyond λ_k = d_k^2.This restriction follows because the Dual Averaging analysis requires monotonically decreasing step sizes.
3 Lower Complexity Bounds for Exponentially Bounded Algorithms
The paper studies lower complexity bounds for exponentially bounded, parameter-free optimization methods and shows that Prodigy is optimal within this class. The lower-bound construction is strongest for early iterations, while broader bounds for larger iteration counts remain open.
- Algorithm class: Exponentially bounded algorithms restrict how rapidly their iterates or learning-rate estimates can grow.The paper defines this class using a constant d0 that bounds the growth for every sequence of G-bounded gradients.
- Algorithm class: D-Adaptation, DoG, and Prodigy are all exponentially bounded.
- Limitations: The resisting-oracle construction only proves hard problems for n < log(D/d0), leaving more general lower bounds for larger n open.The paper notes that this early-iteration regime reflects the behavior of the methods when both n and the estimate dk are small.
- Lower bound: Theorem 4 establishes a lower bound for any exponentially bounded algorithm minimizing a convex G-Lipschitz function without knowing G or D.The construction uses a fixed gradient oracle and a convex Lipschitz problem with G = 1 and distance to a minimizer at most D.
- Lower bound: Prodigy is optimal among exponentially bounded algorithms for this complexity class.
- Trade-off: Methods that achieve log log dependence on d0 must overshoot the standard D/G step size by more than a fixed constant factor.Such overshooting can risk divergence when gradients are only locally bounded by G.
4 Related Work
Related work includes parameter-free convex optimization, coin-betting, DoG, Polyak-style methods, and adaptive deep-learning optimizers. The paper positions Prodigy as closing a sqrt-log dependence gap while retaining practical learning-rate adaptation.
- Polyak methods: Polyak step sizes replace knowledge of D with an estimate of f∗, but stable convergence requires accurate f∗ estimates.
- Coin-betting: Coin-betting methods apply online-learning regret ideas to convex nonsmooth optimization through a duality between regret minimization and wealth maximization.
- Adam adaptation: Algorithm 3 gives Prodigy’s Adam version, using adaptive moment updates and a nondecreasing estimate dk.
- Prodigy: Prodigy closes the gap by achieving the same sqrt-log dependence as coin-betting.
- Distance estimation: DoG estimates D online, but its tamed variant has a log+(D/d0) dependence on the initial distance-estimate error.
- Adaptive methods: AdGD matches optimally tuned Gradient Descent rates under local smoothness, while the nonsmooth differentiable case had remained unstudied.
5 Deriving Adam-Like Step Sizes
The Adam-like derivation adapts Prodigy’s distance estimation to exponential moving averages of gradients and squared gradients. The resulting update rules form the Adam version evaluated experimentally.
- Exponential weighting: Prodigy approximates Adam’s exponential moving average of squared gradients using exponential weights λk = β2^-k/2.
- Gradient scaling: The construction computes an exponential moving average of dkgk rather than gk itself.
- Distance estimation: The Adam estimate of D uses the ℓ1 norm of the weighted gradient sum in its denominator.This choice follows the coordinate-wise convergence analysis described in the paper.
- Adam update: The update uses an exponential moving average with √β2, plus an optional bias correction for an extra (1 − β2) factor in vk.
- Adam update: Algorithm 3 combines these update rules into the Adam version studied in the numerical experiments.
6 Experiments
Experiments cover convex classification and multiple deep-learning workloads. Prodigy consistently improves over D-Adaptation and often approaches tuned Adam, including on CIFAR10, transformers, and large-scale application models.
- Logistic regression: Prodigy’s weighted SGD variant outperforms regular D-Adaptation across 12 convex classification datasets and adapts faster than DoG on 10 of 12 problems.Each dataset used 1,000 steps, randomized initialization, and 10 seeds.
- CIFAR10: Prodigy closes D-Adaptation’s CIFAR10 accuracy gap to standard Adam on VGG11 and ResNet-50 by estimating larger step sizes.Figure 2 reports test accuracy, train loss, and step sizes for both networks.
- CIFAR10: DoG estimates larger step sizes than Prodigy on CIFAR10, but its larger denominator counterbalances them.DoG performed better on VGG11, whereas L-DoG performed better on ResNet-50.
- nanoGPT transformer: On nanoGPT Shakespeare training, Prodigy’s train loss was on par with tuned AdamW and slightly better than D-Adapted Adam.All methods had roughly equivalent test loss, while DoG and L-DoG reached their best value more slowly.
- Large-scale Adam experiments: Prodigy closely matches baselines on RoBERTa, GPT, DLRM, and VarNet, while appearing faster on the LSTM training-loss curve.The LSTM experiment also showed slight test-loss overfitting.
- ViT training: 74.63% test accuracy versus 75.4% for Adam was achieved by Prodigy on ViT, more than 2% above D-Adaptation.The comparison used weight decay 0.05 and was affected by 1–2% run-to-run test-accuracy variance.
7 Conclusion
The conclusion presents Prodigy as a faster learning-rate adaptation method than D-Adaptation across experiments. Figure 5 reports Adam-family experiments.
- Prodigy, a weighted form of D-Adaptation, adapts faster than other known methods across a range of experiments.
- The authors state that Prodigy improves the adaptation rate of the state-of-the-art D-Adaptation method.
- Figure 5 contains the Adam-family experiments.
A Analysis of Prodigy
The analysis establishes auxiliary inequalities for nonnegative sequences and uses interval doubling arguments to control the evolving distance estimate. These results support the theoretical analysis of Prodigy.
- For nonnegative sequences, Proposition 1 derives bounds using 1 −√(1 −α) ≤ α ≤ 2(1 −√(1 −α)).
- Proposition 2 bounds a sum involving nonnegative sequence terms through logarithmic increments.
- The interval argument shows that some interval must contain only a factor-of-two change in the distance estimate.
- The proof concludes by restricting the summation to the interval identified by the doubling contradiction.
A.3 GD Analysis
The gradient-descent analysis proves that Prodigy’s estimate remains bounded by the solution distance and derives convergence bounds for weighted iterates. The resulting bound can avoid dependence on D/d0 asymptotically.
- Assuming d0 ≤ D, Algorithm 1 maintains dk ≤ D for every iteration.
- Theorem 5 gives a functional-gap convergence bound for the average iterate under nondecreasing weights 1 ≤ λ0 ≤ ··· ≤ λn.
- Corollary 2 uses polynomial weights λk = (k + 1)^p to derive the stated asymptotic convergence rate.
- The resulting corollary bound does not depend on D/d0, unlike the comparable unweighted bound except asymptotically.
A.4 DA Analysis
The dual-averaging analysis extends Prodigy to coordinate-wise updates, using weighted norms and an ℓ∞ distance measure. It establishes convergence while maintaining an upper-bounded distance estimate.
- Algorithm 4 implements the coordinate-wise dual-averaging version of Prodigy.
- The coordinate-wise analysis uses weighted norms, an ℓ∞ distance term, and corresponding gradient assumptions.
- Lemma 8 states the guarantee satisfied by the coordinate-wise version of Prodigy.
- Theorem 7 states that Algorithm 4 converges with the displayed rate.
- The proof establishes by induction that the coordinate-wise estimate remains bounded by D∞.
B Lower Complexity Theory
The section establishes exponential boundedness for D-Adaptation, DoG, and Prodigy, and presents a lower-complexity construction for algorithms lacking knowledge of G and D. The construction yields logarithmic dependence on the distance ratio in the iteration bound.
- Lower complexity theory: Any exponentially bounded algorithm without knowledge of G and D can encounter a convex G-Lipschitz problem consistent with a fixed gradient oracle.The theorem fixes G = 1 and bounds the distance from the starting point to every minimizer by D.
- Lower complexity construction: A one-dimensional oracle can return only negative gradients, making the objective appear linear at all queried points while retaining distance D = |x0 − x∗| = 2^k+1x1.The construction uses an absolute-value function whose unseen side contains the minimizer.
- Lower complexity construction: log2(D/x1) √n + 1 bounds the resulting iteration dependence in the combined lower-bound argument.The bound follows after combining the intermediate results for the constructed sequence.
- Exponential boundedness: Theorem 9 states that D-Adaptation, DoG, and Prodigy are exponentially bounded.The proof treats D-Adaptation first, then extends the argument to Prodigy and DoG.
- Exponential boundedness: The D-Adaptation proof upper-bounds the sequence d_n through a recursively defined sequence and then extends the argument to Prodigy and DoG.The proof invokes induction, triangle-inequality bounds, and the respective step-size constructions.