Random Function Descent
Not on the map. Why?
Abstract (arXiv)
Classical worst-case optimization theory neither explains the success of optimization in machine learning, nor does it help with step size selection. In this paper we demonstrate the viability and advantages of replacing the classical 'convex function' framework with a 'random function' framework. With complexity O(n3d3), where n is the number of steps and d the number of dimensions, Bayesian optimization with gradients has not been viable in large dimension so far. By bridging the gap between Bayesian optimization (i.e. random function optimization theory) and classical optimization we establish viability. Specifically, we use a 'stochastic Taylor approximation' to rediscover gradient descent, which is scalable in high dimension due to O(nd) complexity. This rediscovery yields a specific step size schedule we call Random Function Descent (RFD). The advantage of this random function framework is that RFD is scale invariant and that it provides a theoretical foundation for common step size heuristics such as gradient clipping and gradual learning rate warmup.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 30 of its 81 references that are in the map. First posted on arXiv 2 May 2023.
Builds on
30 of 81 references.
References · 30
- 2014Adam: A Method for Stochastic Optimizationcited by 36,960
- 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
- 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
- 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
- 2019On the Convergence of Adam and Beyondcited by 834
- 2015Cyclical Learning Rates for Training Neural Networkscited by 627
- 2017Deep Neural Networks as Gaussian Processescited by 617
- 2016Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networkscited by 541
- 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
- 2017The Marginal Value of Adaptive Gradient Methods in Machine Learningcited by 248
- 2018A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decaycited by 223
- 2013Bayesian Optimization in a Billion Dimensions via Random Embeddingscited by 178
18 more
- 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
- 2021A Universal Law of Robustness via Isoperimetrycited by 150
- 2020Descending through a Crowded Valley - Benchmarking Deep Learning Optimizerscited by 118
- 2019Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Modelcited by 116
- 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
- 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
- 2017Bayesian Optimization with Gradientscited by 59
- 2018Fashionable Modelling with Fluxcited by 53
- 2020An Ensemble of Simple Convolutional Neural Network Models for MNIST Digit Recognitioncited by 30
- 2018Optimization of the Sherrington-Kirkpatrick Hamiltoniancited by 20
- 2021High-Dimensional Gaussian Process Inference with Derivativescited by 16
- 2021Scaling Gaussian Processes with Derivative Information Using Variational Inferencecited by 15
- 2020Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysiscited by 14
- 2020Optimal Randomized First-Order Methods for Least-Squares Problemscited by 10
- 2020Optimization of Mean-field Spin Glassescited by 9
- 2021Tight Lipschitz Hardness for Optimizing Mean Field Spin Glassescited by 9
- 2022Only Tails Matter: Average-Case Universality and Robustness in the Convex Regimecited by 7
- 2018Backtracking gradient descent method for general C1 functions, with applications to Deep Learningcited by 6
Built on by
Citing papers per year: 2025: 1.
1 paper.