mlsanityData to 7 Oct 2026

Learning to Accelerate by the Methods of Step-size Planning

arXiv 2204.01705 ↗First posted 1 Apr 2022cs.LG cs.AI math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Gradient descent is slow to converge for ill-conditioned problems and non-convex problems. An important technique for acceleration is step-size adaptation. The first part of this paper contains a detailed review of step-size adaptation methods, including Polyak step-size, L4, LossGrad, Adam, IDBD, and Hypergradient descent, and the relation of step-size adaptation to meta-gradient methods. In the second part of this paper, we propose a new class of methods of accelerating gradient descent that have some distinctiveness from existing techniques. The new methods, which we call em step-size planning, use the em update experience to learn an improved way of updating the parameters. The methods organize the experience into K steps away from each other to facilitate planning. From the past experience, our planning algorithm, Csawg, learns a step-size model which is a form of multi-step machine that predicts future updates. We extends Csawg to applying step-size planning multiple steps, which leads to further speedup. We discuss and highlight the projection power of the diagonal-matrix step-size for future large scale applications. We show for a convex problem, our methods can surpass the convergence rate of Nesterov's accelerated gradient, 1 - √μ/L, where μ, L are the strongly convex factor of the loss function F and the Lipschitz constant of F', which is the theoretical limit for the convergence rate of first-order methods. On the well-known non-convex Rosenbrock function, our planning methods achieve zero error below 500 gradient evaluations, while gradient descent takes about 10000 gradient evaluations to reach a 10-3 accuracy. We discuss the connection of step-size planing to planning in reinforcement learning, in particular, Dyna architectures. (This is a shorter abstract than in the paper because of length requirement)

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 44 of its 132 references that are in the map. First posted on arXiv 1 Apr 2022.

Builds on

44 of 132 references.

References · 44

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  4. 2021Convex optimizationcited by 2,479
  5. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  6. 2018On First-Order Meta-Learning Algorithmscited by 1,003
  7. 2020Meta-Learning in Neural Networks: A Surveycited by 944
  8. 2019On the Convergence of Adam and Beyondcited by 834
  9. 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 776
  10. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  11. 2014Convex Optimization: Algorithms and Complexitycited by 569
  12. 2019Meta-Learning with Implicit Gradientscited by 523
32 more
  1. 2018Meta-Learning with Latent Embedding Optimizationcited by 476
  2. 2017Sharp Minima Can Generalize For Deep Netscited by 462
  3. 2019Meta-Learning with Differentiable Convex Optimizationcited by 461
  4. 2015Gradient-based Hyperparameter Optimization through Reversible Learningcited by 357
  5. 2017Deep Reinforcement Learning: An Overviewcited by 327
  6. 2019PyHessian: Neural Networks Through the Lens of the Hessiancited by 291
  7. 2018Meta-Learning: A Surveycited by 254
  8. 2018An Introduction to Deep Reinforcement Learningcited by 201
  9. 2019Meta-Learning Representations for Continual Learningcited by 189
  10. 2019Adaptive Gradient-Based Meta-Learning Methodscited by 183
  11. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  12. 2013Revisiting Natural Gradient for Deep Networkscited by 157
  13. 2016Eigenvalues of the Hessian in Deep Learning: Singularity and Beyondcited by 156
  14. 2018Meta-Gradient Reinforcement Learningcited by 156
  15. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  16. 2019Online Meta-Learningcited by 137
  17. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  18. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  19. 2017Online Learning Rate Adaptation with Hypergradient Descentcited by 117
  20. 2019Meta-Learning without Memorizationcited by 92
  21. 2019Asymmetric Valleys: Beyond Sharp and Flat Local Minimacited by 90
  22. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  23. 2019Discovery of Useful Questions as Auxiliary Taskscited by 45
  24. 2018L4: Practical loss-based stepsize adaptation for deep learningcited by 26
  25. 2013A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problemscited by 25
  26. 2015A geometric alternative to Nesterov's accelerated gradient descentcited by 21
  27. 2020Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Bettingcited by 19
  28. 2014Fast Approximation of Rotations and Hessians matricescited by 8
  29. 2022A History of Meta-gradient: Gradient Methods for Meta-learningcited by 7
  30. 2018TIDBD: Adapting Temporal-difference Step-sizes Through Stochastic Meta-descentcited by 5
  31. 2018Efficient Full-Matrix Adaptive Regularizationcited by 5
  32. 2019LOSSGRAD: automatic learning rate in gradient descentcited by 1

Built on by

Not cited yet.