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).
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