Stochastic Gradient Descent with Biased but Consistent Gradient Estimators

Jie Chen, Ronny LussarXiv 2018 · arXiv

Abstract

Standard Stochastic Gradient Descent (SGD) theory relies on unbiased gradient estimators. However, in domains like graph-based learning, computing unbiased gradients is often computationally prohibitive due to data interdependencies. This paper establishes a theoretical foundation for using consistent estimators—which may be biased but converge to the true gradient as sample size increases. We prove that consistent estimators achieve the same convergence rates as unbiased ones across strongly convex, convex, and nonconvex objectives. Empirical evaluations on Graph Convolutional Networks (GCNs) across multiple benchmarks validate these theoretical findings, demonstrating significant efficiency gains without sacrificing accuracy.

Introduction

In classical supervised learning, training examples are typically assumed to be independent and identically distributed (iid). This assumption simplifies the creation of an unbiased gradient estimate by sampling a single random instance. However, in graph-based learning, such as with Graph Convolutional Networks (GCNs), nodes are interconnected. Calculating an unbiased gradient for a single node requires aggregating information from its neighborhood, which can lead to a "neighbor explosion." In highly connected graphs, computing an unbiased gradient for one node can become as computationally expensive as processing the entire graph ($O(n)$).

Practitioners frequently circumvent this by sampling a fixed number of neighbors, resulting in a biased but consistent estimator. Despite its empirical success, a rigorous theoretical framework guaranteeing convergence under these conditions was previously lacking.

Methodology

The authors bridge the gap between empirical practice and theoretical necessity by formalizing the properties of consistent estimators and deriving convergence proofs.

Defining Consistency and Tail Bounds

A "consistent" estimator is defined as one that converges to the true value in probability as the sample size $N$ increases. Crucially, the authors assume the estimator follows an exponential tail bound, meaning the probability of a large estimation error decays exponentially with sample size. This assumption was empirically verified for GCN architectures.

Convergence Analysis

The paper provides new convergence proofs for three primary optimization scenarios:

  • Strongly Convex Objectives: Achieving $O(1/T)$ convergence.
  • Convex Objectives: Achieving $O(1/\sqrt{T})$ convergence.
  • Nonconvex Objectives: Achieving $O(1/\sqrt{T})$ convergence for the gradient norm.

Furthermore, an integral transform approach is used to generalize GCN layers from finite graphs to infinite domains, providing a cleaner theoretical justification for why layer-wise sampling yields consistent estimators.

Experimental Results

The theoretical framework was validated using three datasets: Mixture (synthetic Gaussian clusters), Cora (citation network), and Pubmed (large-scale citation network).

Training loss curves for Mixture, Cora, and Pubmed datasets comparing consistent and unbiased estimators.

Key Findings

  • Theoretical Parity: Convergence rates for consistent estimators match those of unbiased SGD, proving that the inherent bias in neighbor sampling does not fundamentally impede the learning process.
  • Computational Efficiency: On the Pubmed dataset, a 1-layer GCN using a consistent estimator (sample size 400) was approximately 11x faster per epoch than its unbiased counterpart (0.199s vs. 2.24s) while maintaining comparable test accuracy.
  • Regularization Effects: In some instances, consistent estimators outperformed unbiased ones. For example, on the Cora dataset, a sample size of 400 achieved higher test accuracy than full unbiased SGD, suggesting that sampling may introduce a beneficial regularizing effect.

Discussion and Conclusion

The distinction between unbiasedness and consistency is central to this work. While an estimator can be unbiased yet inconsistent, or consistent yet biased, this research shows that consistency is sufficient for stable optimization trajectories. Unlike standard SGD results that bound expected error, this analysis provides probabilistic bounds, which are more appropriate for consistent estimators.

Limitations and Future Work

The theory requires "sufficiently large" sample sizes and specific step sizes, which currently remain hyperparameters that must be tuned empirically. Additionally, while exponential tail bounds hold for GCNs, their applicability to other complex architectures remains an open question. Future research may focus on developing variance reduction techniques specifically designed for consistent estimators in graph learning.

Summary updated

Abstract

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.
BibTeX
@misc{chen2018stochastic,
  author = {Jie Chen and Ronny Luss},
  title = {{Stochastic Gradient Descent with Biased but Consistent Gradient Estimators}},
  year = {2018},
  eprint = {1807.11880},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.11880},
}
Figure