In the standard textbook theory of Stochastic Gradient Descent (SGD), there is one golden rule: your gradient estimate must be unbiased. Mathematically, this means that while any single mini-batch gradient might be noisy, its expected value must exactly equal the true gradient of the objective function ($\mathbb{E}[g] = \nabla f$).
For decades, this assumption was the bedrock of convergence proofs. However, as machine learning has scaled to massive distributed systems and complex reinforcement learning environments, this "unbiasedness dogma" has become a bottleneck. Recent research has revealed that not only can we tolerate bias, but intentionally introducing it can often lead to faster, more stable convergence.
The Practical Necessity of Bias
In modern large-scale learning, we rarely have the luxury of unbiased gradients. Bias creeps in from three primary sources:
- Communication Compression: In distributed training, workers often compress their gradients (e.g., via sparsification or quantization) to save bandwidth. As Jeremy Bernstein and colleagues noted in their work on SIGNSGD, extreme compression schemes are inherently biased but necessary for scaling.
- Intractable Distributions: In tasks like training Energy-Based Models or solving combinatorial constraints, we cannot sample the true gradient efficiently. Algorithms like XOR-SGD use biased hashing-based sampling because unbiased Markov Chain Monte Carlo (MCMC) is too slow to be practical.
- Algorithmic Structure: Many reinforcement learning and online EM algorithms rely on "consistent" estimators—those that converge to the truth as sample size increases but remain biased in the finite-time regime. Belhal Karimi and Eric Moulines have shown that these biased stochastic approximation schemes still possess strong non-asymptotic convergence guarantees.
The Bias-Variance Tradeoff
Why would a biased estimator ever be better than an unbiased one? The answer lies in the Mean Squared Error (MSE) of the gradient estimate. The MSE is the sum of the variance and the square of the bias: $$\text{MSE} = \text{Variance} + \text{Bias}^2$$
Derek Driggs and Jingwei Liang demonstrated in On the Bias-Variance Tradeoff in Stochastic Gradient Methods that by allowing a small amount of bias, we can often drastically reduce the variance. In many non-convex landscapes, a high-variance unbiased gradient is like a compass that spins wildly; a low-variance biased gradient is like a compass that points slightly to the west of North—it still gets you to the pole, and it does so without the erratic wandering.
This principle is the engine behind MARINA, a state-of-the-art algorithm for distributed non-convex optimization. Developed by Eduard Gorbunov and Peter Richtárik, MARINA uses a biased gradient estimator based on compressed differences. This structured bias provides tighter variance bounds than previous unbiased methods like DIANA, leading to significantly faster convergence in communication-constrained environments.
Taming the Zoo of Biased Algorithms
Until recently, the theory for biased SGD was fragmented. Every new biased algorithm required a bespoke proof. Researchers have recently moved toward a "Grand Unified Theory" to handle what they call the "zoo" of biased methods.
In A Guide Through the Zoo of Biased SGD, Igor Sokolov and co-authors introduced the Biased ABC framework. This framework replaces the strict unbiasedness requirement with a set of weaker, parametric assumptions that bound the bias and variance relative to the true gradient.
Similarly, Eduard Gorbunov has worked to bridge the gap between disparate methods like variance reduction, quantization, and coordinate descent. His unified analysis of SGD-type methods shows that many seemingly different algorithms are actually just different ways of navigating the same bias-variance tradeoff.
Why It Works: Consistency and Misalignment
The intuition for why these methods converge despite the "error" in their gradients comes down to two concepts: consistency and misalignment correction.
- Consistency: As shown by Jie Chen in Stochastic Gradient Descent with Biased but Consistent Gradient Estimators, if the bias vanishes as the sample size increases or as the algorithm approaches the optimum, the trajectory remains stable.
- Momentum as a Buffer: Standard tricks like momentum are surprisingly effective at "correcting" bias. Aditya Bhaskara and colleagues proved in Descent with Misaligned Gradients that momentum can theoretically justify the use of gradients that are merely correlated with the true direction, effectively smoothing out the systematic errors (misalignment) over time.
By relaxing the requirement for unbiasedness, researchers have unlocked a new class of algorithms—like XOR-PGD for constrained optimization and S-Local-SVRG for federated learning—that are more efficient, more scalable, and better suited for the messy reality of modern data.