Optimal survey schemes for stochastic gradient descent with applications to M-estimation

Stéphan Clémençon, Patrice Bertail, Emilie Chautru, Guillaume PapaESAIM 2018 · DOI

TL;DR

This paper introduces Horvitz-Thompson Gradient Descent (HTGD), a novel approach that supercharges Stochastic Gradient Descent (SGD) by borrowing techniques from survey sampling. By using non-uniform sampling weights based on "auxiliary information," the authors prove you can significantly reduce the variance of gradient estimates, leading to faster and more accurate convergence in large-scale machine learning problems.

What Problem Does This Paper Address?

In the era of Big Data, computing a "full" gradient across millions of data points is often computationally impossible. The standard workaround is Stochastic Gradient Descent (SGD), which estimates the gradient using a small, uniform random subsample (a mini-batch).

However, uniform sampling is "blind"—it treats every data point as equally important. In reality, some points are much more informative for the gradient than others. If we sample a point where the gradient is nearly zero, we’ve wasted computational effort. The challenge addressed here is: How can we use prior or "cheap" information about our data to sample more intelligently, thereby getting a better gradient estimate for the same computational price?

Methods

The authors propose the Horvitz-Thompson Gradient Descent (HTGD) algorithm. The core idea is to replace the standard mini-batch mean with a Horvitz-Thompson estimator, a classic tool from survey statistics used to produce unbiased estimates from non-uniform samples.

Key components include:

  • Unequal Inclusion Probabilities ($\pi_i$): Instead of picking points with probability $1/N$, points are picked with a probability $\pi_i$ that reflects their "importance."
  • The Optimal Scheme: The authors mathematically prove that the optimal sampling probability for each point is proportional to the norm of its gradient.
  • Auxiliary Information: Since we don't know the true gradient (that’s what we’re trying to find!), the authors suggest using a "link function" based on auxiliary variables—cheaper, proxy versions of the data—to set the sampling weights.
  • Theoretical Framework: The paper provides rigorous proofs for the consistency (it converges to the right answer) and asymptotic normality (the error distribution is well-behaved) of the HTGD estimator.

Datasets

The paper validates the theory using two primary simulation frameworks:

  1. Linear Logistic Regression: A toy model with $N=5,000$ samples and $d=10$ dimensions. The "auxiliary information" used for sampling was a low-dimensional marginal vector of the input data.
  2. The Symmetric Model: A location parameter estimation problem using a balanced Gaussian mixture (two Gaussian distributions with means at 4 and -4). This tested the algorithm's ability to handle multimodal distributions where standard means or medians might fail.

Key Insights and Ideas

  • Variance is the Enemy: The primary benefit of HTGD is variance reduction. By sampling "high-impact" points more frequently (and weighting them less in the final sum to maintain unbiasedness), the "noise" in the gradient estimate drops significantly.
  • The "Proxy" Strategy: You don't need the perfect gradient to win. Even a "cheap" approximation of the gradient (using auxiliary info) is enough to create a sampling scheme that outperforms uniform SGD.
  • Asymptotic Optimality: The authors show that their proposed sampling weights are not just a good heuristic; they are the mathematically optimal choice to minimize the limit variance of the estimator.
  • Bridging Two Fields: The paper successfully bridges the gap between Survey Sampling (traditionally used in social sciences/polling) and Stochastic Optimization (the backbone of modern AI).

Key Results

  • Higher Precision: In the logistic regression experiments, HTGD achieved a significantly lower Mean Squared Error (MSE) than standard mini-batch SGD. The "dispersion bands" (uncertainty) for HTGD were much tighter, indicating a more stable path to the solution.
  • Faster Convergence: For the symmetric model, HTGD reached a satisfactory estimate of the location parameter in far fewer iterations than standard SGD.
  • Efficiency: The authors demonstrate that while calculating weights adds a small amount of "latency," the massive gain in statistical accuracy per iteration makes it a net win for large-scale $M$-estimation.

Limitations and Future Work

  • The Cost of Weights: The main limitation is the overhead of calculating $\pi_i$ for all $N$ points at each step. While the authors suggest this is $O(N)$ and parallelizable, it still adds a computational layer that uniform SGD lacks.
  • Dependency on Auxiliary Info: The success of the method relies on having "good" auxiliary information that correlates with the gradient. If the proxy information is unrelated to the target, the benefits of HTGD diminish.
  • Scaling to Deep Learning: While the paper focuses on $M$-estimation (like regression), a natural next step is applying these optimal survey schemes to deep neural networks, where gradient noise is a major bottleneck.
  • Distributed Systems: The authors note that future work should explore how to integrate these sampling principles into massively parallelized "Big Data" infrastructures.

Summary updated

Abstract

Iterative stochastic approximation methods are widely used to solve M -estimation problems, in the context of predictive learning in particular. In certain situations that shall be undoubtedly more and more common in the Big Data era, the datasets available are so massive that computing statistics over the full sample is hardly feasible, if not unfeasible. A natural and popular approach to gradient descent in this context consists in substituting the “full data” statistics with their counterparts based on subsamples picked at random of manageable size. It is the main purpose of this paper to investigate the impact of survey sampling with unequal inclusion probabilities on stochastic gradient descent-based M -estimation methods. Precisely, we prove that, in presence of some a priori information, one may significantly increase statistical accuracy in terms of limit variance, when choosing appropriate first order inclusion probabilities. These results are described by asymptotic theorems and are also supported by illustrative numerical experiments.
BibTeX
@inproceedings{clemencon2018optimal,
  author = {Stéphan Clémençon and Patrice Bertail and Emilie Chautru and Guillaume Papa},
  title = {{Optimal survey schemes for stochastic gradient descent with applications to <i>M</i>-estimation}},
  booktitle = {ESAIM},
  year = {2018},
  doi = {10.1051/ps/2018021},
}
Figure