PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning-Rate-Free Learning by D-Adaptation

Aaron Defazio, Konstantin Mishchenko

arXiv:2301.07733v5cs.LGcs.AImath.OCstat.ML

TL;DR

When the distance to a solution is unknown, selecting the learning rate can require a hyper-parameter grid search. D-Adaptation maintains a lower bound on that distance within a weighted dual-averaging approach; it achieves asymptotically optimal convergence without extra log factors and matches hand-tuned learning rates across diverse machine-learning problems.

  • Problem

    When D is unknown, AdaGrad-Norm still requires an estimate, and the usual practice is a log-spaced grid search because the method performs poorly when D is estimated incorrectly.

    Source: §1 · p. 2

  • Method

    D-Adaptation modifies the AdaGrad step size for weighted dual averaging and maintains a lower bound on the distance to a solution.

    Source: §2 · p. 2, §1 · p. 2

  • Results

    D-Adaptation achieves the optimal asymptotic convergence rate without extra log factors and matches carefully hand-tuned baseline learning rates across diverse machine-learning problems.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The approach offers parameter-free learning for convex Lipschitz functions and performs well across large, diverse machine-learning problems.

    Source: §8 · p. 18

    The analysis applies only to the restricted setting of convex Lipschitz functions.

    Source: §4.2 · p. 7

Abstract

from arXiv · show

D-Adaptation is an approach to automatically setting the learning rate which asymptotically achieves the optimal rate of convergence for minimizing convex Lipschitz functions, with no back-tracking or line searches, and no additional function value or gradient evaluations per step. Our approach is the first hyper-parameter free method for this class without additional multiplicative log factors in the convergence rate. We present extensive experiments for SGD and Adam variants of our method, where the method automatically matches hand-tuned learning rates across more than a dozen diverse machine learning problems, including large-scale vision and language problems. An open-source implementation is available.

1. Introduction

For unconstrained convex minimization, choosing an effective learning rate depends on unknown problem constants, and the usual practical response when D is unknown is a grid search. The introduction presents D-Adaptation as a way to achieve asymptotically optimal convergence without extra log factors while matching carefully hand-tuned learning rates across diverse machine-learning problems.

1. Introduction

  • Learning-rate choice controls convergence: overly large values can cause oscillation, while small values make progress slow.The learning rate is the main quantity controlling whether and how fast the method converges.Source: §1 · p. 1
  • For the subgradient method, the average iterate converges in function value at an inverse square-root rate, with an optimal fixed step size requiring knowledge of the distance to a solution.The setting is unconstrained convex minimization with a Lipschitz function and a non-empty minimizer set.Source: §1 · p. 1
  • When D is unknown, AdaGrad-Norm still requires an estimate, and the usual practice is a log-spaced grid search because incorrect estimates perform poorly.The fixed-rate guarantee also depends on D and G.Source: §1 · p. 2
  • The method maintains and updates a lower bound on D, which is provably sufficient for asymptotically optimal convergence.The method avoids requiring the exact distance to a solution.Source: §1 · p. 2
  • D-Adaptation matches carefully hand-tuned baseline learning rates across machine-learning problems in computer vision, natural language processing, and recommendation systems, while achieving the optimal asymptotic rate without extra log factors.The introduction reports both the theoretical rate and broad practical performance.Source: §1 · p. 2

2. Algorithm

D-Adaptation modifies weighted dual averaging with a maintained lower bound on the distance to a solution, using empirical quantities to update that bound. It achieves the optimal asymptotic convergence rate; a non-asymptotic guarantee and a gradient-descent variant have additional qualifications.

2. Algorithm

  • The method modifies AdaGrad step sizes for weighted dual averaging and updates a lower bound on D using empirical quantities.It keeps the largest bound seen; the derived bound can be vacuous when the accumulated squared gradients dominate the squared norm of the gradient sum.Source: §2 · pp. 2–3
  • Theorem 1 establishes the optimal asymptotic convergence rate when the initial lower bound d0 is no greater than the distance D to a minimizer.The guarantee applies to convex G-Lipschitz functions with a non-empty set of minimizers.Source: §2 · p. 3
  • The non-asymptotic bound is worse only by a factor of log2(1+D/d0), substantially better than subgradient steps sized proportional to d0, which incur an extra factor of D/d0.Theorem 2 applies to Algorithm 1 run for n ≥ 2 log2(D/d0) iterations with the step size modified.Source: §2 · p. 4

2.1. Why Dual Averaging?

  • The alternative gradient-descent version has an additional logarithmic factor in its asymptotic rate, although its practical performance is very similar.The method also returns a weighted average iterate rather than the last iterate; compatibility with known last-iterate techniques was not explored.Source: §2.1 · p. 4, §2 · p. 4

3. D-Adapted AdaGrad

D-Adapted AdaGrad applies D-Adaptation to coordinate-wise AdaGrad, estimating distance in the ℓ∞ norm. Its asymptotic rate matches AdaGrad up to constant factors without requiring knowledge of that distance.

3. D-Adapted AdaGrad

  • D-Adapted AdaGrad estimates the distance to a solution in the ℓ∞ norm and achieves AdaGrad’s adaptive convergence rate up to constant factors without knowing D∞.The asymptotic result assumes d0 ≤ D∞.Source: §3 · p. 5
  • The same result can be obtained up to higher-order terms without using G∞ in the initialization of a0.Source: §3 · p. 5
  • Figure 1 uses a toy problem to illustrate estimating D over time, with x0 = 1.0 marked in blue and subsequent iterates in purple.The caption identifies the toy objective as f(x) = |x|.Source: Figure 1 · p. 6
  • The algorithm maintains a vector of coordinate-wise denominators, represented in the analysis by a diagonal matrix.Its listed inputs include d0, defaulting to 10⁻⁶, and G∞.Source: §3 · p. 6

4. Discussion

The discussion illustrates D-Adaptation’s distance estimate, compares two estimators, and identifies the analysis’s scope and initialization requirements.

4. Discussion

  • On the toy problem, dk grows toward D, but the theory does not guarantee that it asymptotically approaches D.The example starts d0 at 0.1 while D is 1.0.Source: §4 · p. 6
  • Once dk is large enough, the lower-bound estimate may decrease or become negative; negative estimates appeared in most reported experiments.Source: §4 · p. 7

4.1. Different ways to estimate D

  • The two D-estimation options worked equally well in practice; the hyper-gradient supplies a lower bound on learning-rate magnitude rather than only a too-large-or-too-small signal.Unlike classical hyper-gradient approaches described here, D-Adaptation needs no extra parameter beyond d0 and can accommodate warmup and annealing schedules.Source: §4.1 · p. 7

4.2. Limitations

  • The analysis is restricted to convex Lipschitz functions and does not establish a stochastic guarantee; a stochastic extension may be applicable.The method requires an initial lower bound d0 on D; with float16, very small values may underflow, so 10⁻⁸ to 10⁻⁶ are recommended in practice.Source: §4.2 · p. 7

5. Related Work

The paper positions D-Adaptation among methods for reducing dependence on problem parameters in convex Lipschitz optimization. It contrasts their assumptions, rates, and practical trade-offs with several alternatives.

5. Related Work

  • The authors characterize their method as the first to achieve complete asymptotic independence from problem parameters while retaining the optimal convergence rate.Source: §5 · p. 7

5.1. Polyak step size

  • The Polyak step size attains the optimal rate without extra log factors by requiring knowledge of f*, while estimates of f* can make convergence unstable.A restarting scheme with lower bounds on f* is stated to converge within a multiplicative log factor of the optimal rate.Source: §5.1 · p. 8

5.2. Exact line searches

  • Exact line searches achieve the optimal rate without problem-parameter knowledge, but approximate searches without smoothness assumptions are non-trivial and may add dependencies on problem constants.The cited exact-line-search methods are by Drori and Taylor (2020) and Goujaud et al. (2022).Source: §5.2 · p. 8

5.3. Bisection

  • Bisection on the log-spaced grid reduces dependence on dmax/d0 from log to log log, and estimating dmax can replace it with D.The bisection approach is attributed to Carmon and Hinder (2022).Source: §5.3 · p. 8

5.4. DoG

  • DoG estimates D and establishes learning-rate-free convergence in the stochastic setting, but its rate has additional multiplicative log factors compared with this method.The DoG estimate is not necessarily bounded; the cited work adds denominator dampening, and its result is described as more general because it treats the stochastic setting.Source: §5.4 · pp. 8–9

5.5. Coin-betting

  • Coin-betting methods need knowledge of G but not D; their optimal-regret guarantee is for online optimization, and the cited regret is a sqrt-log-factor worse than with knowledge of D.Online-to-batch conversion yields a function-value rate; asymptotic rates for coin-betting are not currently known.Source: §5.5 · p. 9

5.6. Reward Doubling

  • Reward doubling tracks the sum of xkgk against a threshold based on a pre-specified upper bound on total squared gradients, doubling the step size and resetting the optimizer state when exceeded.In the one-dimensional setting, the cited method obtains rates similar to coin betting.Source: §5.6 · p. 9

6. Machine Learning Applications

The section adapts D-Adaptation to stochastic SGD and Adam, while noting that the theory does not directly support stochastic optimization; optional learning-rate schedules can still be supplied.

6. Machine Learning Applications

  • The SGD and Adam variants address stochastic optimization, although the theory no longer directly supports this setting.They are presented as Algorithms 4 and 5, respectively.Source: §6 · p. 9
  • For SGD, doubling the D bound improves practical performance, while using the initial gradient norm as G works well despite being a crude estimate.The theoretical rate remains valid up to constant factors under a constant step-size multiplier.Source: §6 · p. 9
  • Momentum is implemented through primal averaging, and an optional γ_k sequence can follow the problem’s learning-rate schedule, including warm-up and annealing.The schedule can generally be the same one used without D-Adaptation.Source: §6 · p. 10
  • Adam uses weighted norms and a correction factor for its exponentially averaged state; it adapts quicker than SGD and needs no constant multiplier for d̂.The methods use ḓ option II, which differs in practice only for Adam; SGD’s version is equivalent to option I.Source: §6 · p. 10

7. Experimental Results

Across varied machine-learning benchmarks, D-Adaptation generally matched tuned learning rates, with a reported exception on the vision-transformer task. The experiments used standard schedules and varied models and datasets.

7.1. Convex Problems; 7.2. Convolutional Image Classification

  • On 12 LIBSVM logistic-regression problems, D-Adaptation matched or exceeded grid-search learning rates within 0.5% accuracy, and it matched or exceeded baseline rates on CIFAR10, CIFAR100, and ImageNet 2012.The image-classification experiments used three different architectures.Source: §7.1 · p. 11, §7.2 · p. 11, Figure 2 · p. 12

7.3. LSTM Recurrent Neural Networks; 7.4. Masked Language Modelling

  • For IWSLT14 German-to-English LSTM translation, D-Adaptation achieved comparable baseline performance without learning-rate tuning; for 110M-parameter RoBERTA pretraining on Book-Wiki, it matched baseline test-set perplexity.Source: §7.3 · p. 11, §7.4 · p. 11

7.5. Auto-regressive Language Modelling; 7.6. Object Detection

  • On Book-Wiki autoregressive language modelling, D-Adaptation had only a negligible perplexity difference from baseline; in COCO object detection, increasing weight decay improved test accuracy for both methods.The detection results changed from 42.67 to 42.99 for the baseline and from 41.92 to 43.07 for D-Adaptation.Source: Figure 4 · p. 14, §7.5 · p. 15, §7.6 · p. 15

7.7. Vision Transformers; 7.8. fastMRI

  • D-Adaptation underperformed the baseline on vision transformers, while matching the highly tuned baseline learning rate on the fastMRI reconstruction task.The vision-transformer experiment used a cosine schedule; the authors suggest sensitivity to the initial rate may explain its performance difference.Source: §7.7 · p. 15, §7.8 · p. 15, Figure 5 · p. 16

7.9. Recommendation Systems

  • On the Criteo click-through-rate task, D-Adaptation closely matched the tuned baseline’s performance.The benchmark used the DLRM recommendation model.Source: §7.9 · p. 15, Figure 6 · p. 16

7.10. Sensitivity to d0; 7.11. Observed learning rates

  • Across all 12 convex logistic-regression datasets, outcomes showed no dependence on d0 from 10^-16 to 10^-2; deep-learning adapted rates resembled hand-tuned rates and could lie at the high end of equally good ranges.For CIFAR10, learning rate 2.0 gave equal final test accuracy to the baseline rate of 1.0.Source: §7.10 · p. 17, §7.11 · p. 17, Table 1 · p. 17

7.12. Comparison to other parameter-free methods; 7.7. Vision Transformers

  • D-Adaptation performed comparably to or better than the baseline on every tested problem except the vision-transformer task.The authors note that this task appeared highly sensitive to the initial learning rate, which may explain the difference.Source: §7.7 · p. 15, §7.12 · p. 18

7.12. Comparison to other parameter-free methods

  • COCOB did not match baseline performance on any tested problem, though it came close on MRI; comparison is complicated because COCOB cannot use explicit schedules, including transformer warm-up.The authors identify schedule differences as a possible source of much of the performance gap.Source: §7.12 · p. 18, Table 2 · p. 18

8. Conclusion

The conclusion presents parameter-free learning for convex Lipschitz functions through successively improved lower bounds on distance to solution, alongside strong performance across diverse machine-learning problems. The appendix develops a lower bound on that distance and analyzes the returned average iterate.

8. Conclusion

  • The conclusion presents parameter-free learning for convex Lipschitz functions via successively improved lower bounds on distance to solution, with strong performance across diverse machine-learning problems.The authors describe the lower-bound construction as potentially of independent interest.Source: §8 · p. 18

Appendix A. Core Theory

  • Theorem 7 establishes a lower bound on the initial distance to solution D, the key unknown quantity targeted by the approach.The proof uses bounds on the iterates and gradient error term.Source: Appendix A · pp. 25–26

A.1. Asymptotic analysis

  • The asymptotic analysis bounds the returned average iterate, with its second term decreasing faster in n than its first.The theorem concerns the average iterate returned by Algorithm 1.Source: §A.1 · pp. 27, 29

A.2. Non-asymptotic analysis

The non-asymptotic analysis treats finite runs of Algorithm 1 and gives a separate option for removing the known gradient bound from the step-size numerator.

A.2. Non-asymptotic analysis

  • For n≥2 log2(D/d0), Theorem 2 selects a weighted average iterate; a related bound can remove G² from the numerator with a negligible extra term.The theorem specifies a choice of averaging time t, while the related bound uses the same iterate.Source: §A.2 · pp. 31–32

Appendix B. Gradient Descent Variant

The appendix specializes D-Adaptation to gradient descent and considers both asymptotic and finite-iteration cases. It notes that logarithmic terms in the gradient-descent convergence rate arise from a standard lemma.

Appendix B. Gradient Descent Variant

  • Setting γk=1 specializes earlier D-Adaptation theorems to the gradient descent variant, Algorithm 2.The appendix states corresponding specializations of earlier theorems.Source: Appendix B · p. 32
  • The logarithmic terms in the gradient-descent convergence rate arise from a standard lemma.The appendix identifies the lemma as the source of those terms.Source: Appendix B · p. 32

B.1. Asymptotic case

  • The asymptotic case gives a guarantee for Algorithm 2, following the logic of Theorem 1 and Jensen’s inequality.The proof also applies an earlier lemma for the gradient descent variant.Source: §B.1 · p. 34

B.2. Non-asymptotic case

  • For n≥2 log2(D/d0), the non-asymptotic theorem selects an averaging time t for Algorithm 2.The proof applies Jensen’s inequality and an earlier lemma.Source: §B.2 · pp. 34–35

Appendix C. Coordinate-wise setting

The appendix extends D-Adaptation to coordinate-wise scaling, documents experiment settings, and adds notes on convergence assumptions and a tighter lower bound on distance to solution.

Appendix C. Coordinate-wise setting

  • The coordinate-wise setting defines diagonal scaling matrices and gives an asymptotic theorem for D-Adapted AdaGrad when d0≤D∞.The theorem concerns convex functions with gradient bound G∞ and distance measured in the ℓ∞ norm.Source: Appendix C · pp. 35, 38

Appendix D. Parameter settings

  • This section collects experimental parameters, architectures, and hardware in Tables 3–9; supplied captions identify logistic regression, CIFAR-10, CIFAR-100, ImageNet, and fastMRI experiments.Source: Appendix D · p. 39, Table 3 · p. 40, Table 5 · p. 40

Appendix E. Additional notes

  • An additional note analyzes the learning rate under the condition that the iterates converge in norm to a minimizer.The accompanying argument derives an asymptotic lower bound on dn.Source: Appendix E · p. 43

E.1. A tighter lower bound on D

  • Using Lemma 5, the authors obtain a slightly tighter lower bound on D than the one used in Theorem 7.Source: §E.1 · p. 44

Appendix F. Adam Derivation

Appendix F derives EMA updates for the Adam variant from weighted updates. The derivation uses a scalar analysis with β1 = 0 and describes the elementwise extension.

Appendix F. Adam Derivation

  • The derivation treats quantities as one-dimensional, with the final result applying element-wise, and sets β1 = 0 because that suffices to derive the method.Hatted quantities denote exponential moving averages, except d̂.Source: Appendix F · p. 45
  • The section derives EMA updates from weighted updates.This is the stated goal of the derivation.Source: Appendix F · p. 45
  • The implemented variant normalizes by γk+1, places the Adam denominator in γ rather than the step size, and uses the only arrangement currently supported by the theory.It still uses the non-DA step.Source: Appendix F · p. 45
  • The denominator of γ is chosen to normalize the step, using a recursive exponential moving average of squared gradients.The passage gives the recurrence for v̂k+1.Source: Appendix F · p. 45
Loading 2301.07733v5…