# Random Function Descent

arXiv: https://arxiv.org/abs/2305.01377 · HTML: https://mlsanity.com/paper/2305.01377/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 81 references that are in the map.
- First posted on arXiv 2 May 2023.

## Builds on (most cited first, 30 of 30)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Cyclical Learning Rates for Training Neural Networks](https://mlsanity.com/paper/1506.01186/) (2015)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks](https://mlsanity.com/paper/1602.07868/) (2016)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decay](https://mlsanity.com/paper/1803.09820/) (2018)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers](https://mlsanity.com/paper/2007.01547/) (2020)
- [Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model](https://mlsanity.com/paper/1907.04164/) (2019)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [Bayesian Optimization with Gradients](https://mlsanity.com/paper/1703.04389/) (2017)
- [Fashionable Modelling with Flux](https://mlsanity.com/paper/1811.01457/) (2018)
- [An Ensemble of Simple Convolutional Neural Network Models for MNIST Digit Recognition](https://mlsanity.com/paper/2008.10400/) (2020)
- [Optimization of the Sherrington-Kirkpatrick Hamiltonian](https://mlsanity.com/paper/1812.10897/) (2018)
- [High-Dimensional Gaussian Process Inference with Derivatives](https://mlsanity.com/paper/2102.07542/) (2021)
- [Scaling Gaussian Processes with Derivative Information Using Variational Inference](https://mlsanity.com/paper/2107.04061/) (2021)
- [Halting Time is Predictable for Large Models: A Universality Property and Average-case Analysis](https://mlsanity.com/paper/2006.04299/) (2020)
- [Optimal Randomized First-Order Methods for Least-Squares Problems](https://mlsanity.com/paper/2002.09488/) (2020)
- [Optimization of Mean-field Spin Glasses](https://mlsanity.com/paper/2001.00904/) (2020)
- [Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses](https://mlsanity.com/paper/2110.07847/) (2021)
- [Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime](https://mlsanity.com/paper/2206.09901/) (2022)
- [Backtracking gradient descent method for general C1 functions, with applications to Deep Learning](https://mlsanity.com/paper/1808.05160/) (2018)

## Built on by (most cited first, 1 of 1)

- [SeeingEye: Agentic Information Flow Unlocks Multimodal Reasoning In Text-only LLMs](https://mlsanity.com/paper/2510.25092/) (2025)

## 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.