# Stochastic Gradient Descent with Biased but Consistent Gradient Estimators

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2018.

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

- [Accelerating Training and Inference of Graph Neural Networks with Fast Sampling and Pipelining](https://mlsanity.com/paper/2110.08450/) (2021)
- [Privacy Amplification for Federated Learning via User Sampling and Wireless Aggregation](https://mlsanity.com/paper/2103.01953/) (2021)
- [Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching](https://mlsanity.com/paper/2305.03152/) (2023)
- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [Graph Neural Preconditioners for Iterative Solutions of Sparse Linear Systems](https://mlsanity.com/paper/2406.00809/) (2024)
- [Generative Modelling of Stochastic Actions with Arbitrary Constraints in Reinforcement Learning](https://mlsanity.com/paper/2311.15341/) (2023)
- [Pseudo-Spherical Contrastive Divergence](https://mlsanity.com/paper/2111.00780/) (2021)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction](https://mlsanity.com/paper/2103.02696/) (2021)
- [f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimization](https://mlsanity.com/paper/2312.03259/) (2023)
- [Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits](https://mlsanity.com/paper/2111.10461/) (2021)
- [Behind the Myth of Exploration in Policy Gradients](https://mlsanity.com/paper/2402.00162/) (2024)
- [Regularization for Adversarial Robust Learning](https://mlsanity.com/paper/2408.09672/) (2024)
- [Unifying back-propagation and forward-forward algorithms through model predictive control](https://mlsanity.com/paper/2409.19561/) (2024)
- [A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization](https://mlsanity.com/paper/2102.09893/) (2021)
- [The Sharpe predictor for fairness in machine learning](https://mlsanity.com/paper/2108.06415/) (2021)
- [Learning from time-dependent streaming data with online stochastic algorithms](https://mlsanity.com/paper/2205.12549/) (2022)
- [Neighborhood Sampling Does Not Learn the Same Graph Neural Network](https://mlsanity.com/paper/2509.22868/) (2025)

## Abstract (arXiv)

Stochastic gradient descent (SGD), which dates back to the 1950s, is one of the most popular and effective approaches for performing stochastic optimization. Research on SGD resurged recently in machine learning for optimizing convex loss functions and training nonconvex deep neural networks. The theory assumes that one can easily compute an unbiased gradient estimator, which is usually the case due to the sample average nature of empirical risk minimization. There exist, however, many scenarios (e.g., graphs) where an unbiased estimator may be as expensive to compute as the full gradient because training examples are interconnected. Recently, Chen et al. (2018) proposed using a consistent gradient estimator as an economic alternative. Encouraged by empirical success, we show, in a general setting, that consistent estimators result in the same convergence behavior as do unbiased ones. Our analysis covers strongly convex, convex, and nonconvex objectives. We verify the results with illustrative experiments on synthetic and real-world data. This work opens several new research directions, including the development of more efficient SGD updates with consistent estimators and the design of efficient training algorithms for large-scale graphs.