Stochastic Gradient Descent (SGD) is the workhorse of modern machine learning, especially for massive datasets. Instead of calculating a gradient over the entire dataset—which is computationally expensive—SGD estimates the gradient using a small "mini-batch."
However, these estimates are inherently "noisy." If the variance of this noise is high, the optimization algorithm spends a lot of time bouncing around instead of heading straight for the optimum. While increasing the mini-batch size reduces noise, it also increases the computational cost per step, defeating the purpose of using stochastic methods. This paper introduces a general framework to speed up Stochastic Gradient (SG) optimization by reducing this gradient variance, allowing for faster convergence and the use of larger learning rates without sacrificing stability.
The Control Variate Framework
The authors propose a general remedy using a classical statistical technique called control variates. The core idea is to augment the noisy gradient $g_d(w)$ with a second term $h_d(w)$ that is highly correlated with it. The new, "improved" gradient is formulated as:
$$\tilde{g}_d(w) = g_d(w) - A^T(h_d(w) - \mathbb{E}[h_d(w)])$$
For this approach to be effective, two conditions must be met:
- High Correlation: The proxy $h_d(w)$ must closely track the noise in the original gradient.
- Easy Expectation: The average value $\mathbb{E}[h_d(w)]$ must be inexpensive to compute, often pre-computed or derived from simple data moments.
The intuition is simple: you don't need to know the true gradient to reduce noise. You just need a proxy that moves in the same direction as the noise. Low-order moments (like mean and variance) act as a rough sketch of the data distribution. Because these don't change during training, they provide a stable "anchor" to correct the fluctuating stochastic gradients.
The paper demonstrates how to construct these control variates for two distinct problems:
- Logistic Regression (Convex): Using a first-order Taylor expansion of the sigmoid function. The resulting control variate's expectation depends only on the mean and variance of the input features, which can be calculated once prior to training.
- Latent Dirichlet Allocation (Non-convex): In the context of Stochastic Variational Inference (SVI), the authors approximate iterative local updates with a fixed-step version, forming a control variate based on second-order moments of word frequencies in the corpus.
Key Results
The authors evaluated their approach on several well-known benchmarks, including the covtype dataset for Logistic Regression and massive text corpora (Nature, New York Times, Wikipedia) for LDA.
High variance usually forces practitioners to use tiny learning rates to prevent the model from diverging. By significantly reducing variance, this method allows for much larger learning rates (e.g., $\rho_t = 1.0$), leading to a much faster "take-off" during training.
- Faster Convergence: In Logistic Regression, the variance-reduced version reached the optimum much faster than standard SGD. With a learning rate of 1.0, the variance-reduced method converged rapidly, whereas standard SGD was too unstable to perform well at that same rate.
- Higher Accuracy: For LDA, the proposed method consistently achieved better held-out log-likelihood (a measure of generalization) across all three massive datasets compared to standard SVI.
- High Correlation: Empirical tests showed the Pearson correlation between the control variates and the noisy gradients was consistently high (above 0.96), proving the Taylor-expansion-based proxies effectively captured the noise.
Limitations and Future Directions
While the framework is general, a primary limitation is that the specific control variate ($h_d$) must be manually derived for each new type of model. Additionally, there is a slight computational overhead per iteration to calculate the control variate, though this is generally outweighed by the massive gains in convergence speed.
Future work may explore integrating this variance reduction technique with second-order methods (like Newton's method). Because variance reduction provides a "cleaner" look at the local geometry of the loss function, it could make complex optimization techniques much more viable in a stochastic setting.
Summary updated