Research map / Optimization / Optimizers
Random Function Descent
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Replaces the convex-function worst-case view with a random-function (Gaussian process) view, deriving a scalable gradient-descent variant, Random Function Descent, whose step-size schedule explains clipping and warmup.
Problem
Worst-case convex optimization theory does not explain the success of ML optimization or guide step size selection, and Bayesian optimization with gradients is too expensive (O(n^3 d^3)) in high dimensions.
Approach
Define a first-order stochastic Taylor approximation as the conditional expectation of a Gaussian random cost given the value and gradient at the current point; minimizing it under isotropy yields gradient descent with an explicit covariance-determined step size schedule (RFD) that is scale invariant and costs O(nd).
Key results
- RFD with squared exponential and rational quadratic covariance comes close to step-size-tuned Adam and SGD on MNIST with batch size 1024, while needing no more than about one epoch of tuning samples.
- A-RFD (asymptotic step sizes without warmup) performs significantly worse than the RFD variants that implement warmup-like behavior.
- RFD is scale invariant and its step size schedule has a plateau, providing a theoretical account of gradient clipping and gradual warmup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use A-RFD asymptotic step sizes instead of the full RFD schedule (ablation) | RFD · MNIST, batch size 1024 | validation loss | Hurt |
| Reduce batch size from 1024 to 128 (ablation) | RFD · MNIST | performance | No clear effect |
| Use RFD instead of tuned SGD | RFD · CIFAR-100 | performance | Hurt |
| Use RFD instead of tuned SGD | RFD · Fashion MNIST, batch size 128 | validation loss | No clear effect |
Surprising findings
- Asymptotic learning rates alone (A-RFD) perform significantly worse than RFD, showing that the warmup-like plateau is important.
- On CIFAR-100 the RFD step sizes were too large, and RFD appears slightly too risk-affine compared with tuned SGD.
Limitations
- Relies on isotropic, stationary Gaussian random function assumptions that may be violated in neural networks (e.g. CIFAR-100 step sizes too large).
- Forgetful greedy design ignores momentum-type information and lacks classical improvement guarantees, so convergence proofs are weak.
- Only simple covariance models are used and the implementation of variance estimation is inefficient.
Experimental setup
Datasets: MNIST Fashion MNIST
Benchmarks: MNIST Fashion MNIST
Metrics: validation loss
Baselines: Adam SGD
Builds on: gradient descent Bayesian optimization gradient clipping learning rate warmup Adam
Closest papers by meaning
- The Power of Random Features and the Limits of Distribution-Free Gradient Descent (ICML 2025 · similarity 0.87)
- Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization (ICLR 2024 · similarity 0.87)
- Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Time (NeurIPS 2025 · similarity 0.87)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.87)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.86)
- A Generalization Result for Convergence in Learning-to-Optimize (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.