Abstract: We emphasize the importance of variance reduction in stochastic methods and propose a probabilistic interpretation as a way to store information about past gradients. The resulting algorithm is very similar to the momentum method, with the difference that the weight over past gradients depends on the distance moved in parameter space rather than the number of steps.
Introduction
This paper offers a fresh probabilistic perspective on one of the most fundamental challenges in machine learning: making stochastic optimization both fast and stable. The authors propose a "Bayesian" approach to variance reduction in online optimization. By weighting past gradients based on the distance moved in parameter space—rather than just the time elapsed—the algorithm automatically transitions from aggressive searching to stable averaging, allowing for convergence even with a fixed stepsize.
The Challenge of Online Variance Reduction
Stochastic Gradient Descent (SGD) is the workhorse of modern AI, but it has a major flaw: noise. Because SGD estimates the "true" gradient using only a small batch of data, the updates are high-variance. To prevent the model from jumping around endlessly, practitioners usually have to "decay" the learning rate over time, and tuning these decay schedules is a notorious headache.
While variance reduction techniques (like SAG or SVRG) exist, they typically require a finite, static dataset that can be passed over multiple times. In an online setting—where data arrives in a continuous stream and the model never sees the same point twice—reducing variance is much harder. The authors aim to bridge this gap, creating an online optimizer that can converge without a complex learning rate schedule.
A Probabilistic Approach to Momentum
The core idea is to treat the "true" gradient as a hidden variable that the optimizer is trying to track.
- Probabilistic Tracking: Instead of relying solely on the current noisy gradient, the authors maintain a Gaussian posterior (an estimate with uncertainty) of the true gradient.
- Distance-Based Decay: Traditional momentum methods (like Adam or RMSProp) use an exponential moving average of past gradients based on time (number of steps). This paper argues that time is a poor proxy for how "stale" a gradient is. Instead, they update their gradient estimate based on the distance moved in parameter space.
- The Hessian Link: To know how much a gradient changes when the model moves, one needs to know the curvature (the Hessian). The authors use an upper bound ($L$) and a lower bound ($\mu$) on the Hessian to "spread" the uncertainty of their gradient estimate whenever the model takes a step.
Essentially, if the model moves a long distance, old gradients are discarded as unreliable. If the model barely moves, old gradients are kept and averaged with new ones to beat down the noise. This allows the algorithm to naturally behave like pure SGD early in training (when steps are large) and automatically shift toward "gradient averaging" as it nears an optimum (when steps become tiny).
Key Results
The paper serves as a theoretical proof-of-concept, utilizing synthetic linear regression and logistic regression to validate the probabilistic framework.
The primary result is qualitative but significant: in the provided experiments, the proposed "Bayes optimizer" continues to converge toward the global minimum with a fixed stepsize, whereas standard SGD and momentum methods hit a "noise floor" and plateau.
As shown in the experimental plots, while SGD and momentum stop improving once the gradient noise matches the stepsize, the variance-reducing nature of the Bayes approach allows it to keep refining the solution. It effectively "cleans" the gradient signal as it goes, allowing the variance of the updates to converge to zero at a rate of $1/t$.
Limitations and Future Work
The authors are transparent about several hurdles that remain for practical, large-scale application:
- Hyperparameter Knowledge: The current version requires knowing the smoothness constant ($L$) and the gradient covariance beforehand. In real-world deep learning, these are rarely known and change throughout training.
- Computational Overhead: Maintaining and updating a covariance matrix adds computational cost compared to the extreme simplicity of standard SGD.
- Lack of Convergence Proof: While empirical results are promising, the paper lacks a formal mathematical proof of the convergence rate.
- Scaling to Deep Learning: The experiments are limited to convex problems. Testing this on high-dimensional, non-convex landscapes (like neural networks) remains an open challenge.
Summary updated