Survey schemes for stochastic gradient descent with applications to\n M-estimation

Stéphan Clémençon, Patrice Bertail, Emilie Chautru, Guillaume PapaarXiv 2015 · DOI · arXiv

TL;DR

This paper introduces Horvitz-Thompson Gradient Descent (HTGD), a method that replaces uniform mini-batch sampling in Stochastic Gradient Descent (SGD) with "smart" survey sampling. By using auxiliary information to assign higher inclusion probabilities to more informative data points, the authors prove that one can significantly reduce the asymptotic variance of the model—meaning better accuracy in fewer iterations—without increasing computational complexity.

What Problem Does This Paper Address?

In the "Big Data" era, datasets are often too massive to compute statistics over the entire sample. The standard workaround is Stochastic Gradient Descent (SGD), which updates model parameters using a small, randomly selected "mini-batch" of data at each step.

However, standard SGD typically uses uniform sampling, treating every data point as equally important. This is inefficient. In many real-world scenarios, we have "auxiliary information"—extra variables or cheaper-to-compute features—that could tell us which data points are likely to provide a more useful gradient update. The challenge addressed here is how to formally incorporate these "unequal inclusion probabilities" into the SGD framework while maintaining theoretical guarantees like consistency and convergence.

Methods

The authors bridge the gap between Survey Sampling Theory and Machine Learning by introducing the Horvitz-Thompson (HT) estimator into the gradient descent loop.

  1. The HT Gradient Estimator: Instead of a simple average of gradients in a mini-batch, the algorithm weights each sampled gradient by the inverse of its inclusion probability ($\pi_i$). This ensures the stochastic gradient remains an unbiased estimate of the true "full data" gradient.
  2. HTGD Algorithm: At each iteration $t$, the algorithm:
  3. Draws a sample $S_t$ based on a sampling design (like a Poisson scheme).
  4. Calculates inclusion probabilities $\pi_i(\theta)$ for the current model state.
  5. Updates the model using the weighted HT gradient.
  6. Optimal Sampling Design: The paper derives the "optimal" inclusion probabilities. Theoretically, to minimize the variance of the error, you should sample points with a probability proportional to the norm of their (transformed) gradient.
  7. Poisson Schemes: While the theory applies generally, the authors focus on Poisson sampling (where each point is included independently) as a practical, parallelizable way to implement the method.

Datasets

The paper focuses on theoretical proofs and validates them using controlled numerical experiments rather than standard large-scale benchmarks (like ImageNet).

  • Linear Logistic Regression Model: A toy numerical model with $d=11$ parameters and a population size of $N=5000$. It uses 10 independent input variables to test how HTGD handles binary classification compared to standard mini-batch SGD.
  • Semi-parametric Symmetric Model: A location parameter estimation problem ($N=1000$) where the underlying density is a balanced mixture of two Gaussians. This tests the algorithm's ability to handle multimodal distributions where simple means or medians fail.

Key Insights and Ideas

  • Variance Reduction via Importance: The core "aha" moment is that you don't need to know the exact gradient to improve sampling. Even if your auxiliary information is only correlated with the true gradient's importance, you still get a win in terms of asymptotic accuracy.
  • The Cost-Benefit Tradeoff: The authors acknowledge that calculating inclusion probabilities adds "latency." However, they show that if the auxiliary information is "cheap" (e.g., a low-dimensional subset of features), the gain in accuracy per iteration far outweighs the small computational overhead.
  • Theoretical Rigor: The paper provides a formal Central Limit Theorem (CLT) for HTGD. It shows that the error follows a non-central chi-square distribution and provides a Lyapunov equation to calculate the specific asymptotic covariance matrix.
  • Robustness: HTGD is shown to be more robust to "data randomness" than standard SGD because the sampling phase actively selects the most informative observations for the descent.

Key Results

  • Asymptotic Superiority: Proposition 2 proves that as long as the inclusion probabilities are positively correlated with the optimal weights, HTGD will always have a lower Hilbert-Schmidt norm of its asymptotic covariance compared to uniform sampling.
  • Logistic Regression Performance: In simulations, HTGD reached a higher level of precision in fewer steps than both standard mini-batch SGD and full Gradient Descent (when normalized for computation time).
  • Symmetric Model Accuracy: In the location parameter test, HTGD achieved a standard deviation (S.D.) of 0.16, significantly outperforming standard SGD (0.22) and basic GD (0.45) for a fixed computational budget.

Limitations and Future Work

  • Dependence on Auxiliary Info: The effectiveness of HTGD relies entirely on the quality of the auxiliary variables ($W_i$). If the auxiliary info is poorly correlated with the gradient, the benefits diminish.
  • Stability Conditions: The authors note that the "stability condition" required for convergence can be difficult to check in practice. They suggest using "projected" versions of the algorithm to guarantee stability.
  • Computational Latency: While the complexity is $O(N)$, the per-step overhead of calculating weights and drawing non-uniform samples might be a bottleneck in extremely high-throughput systems unless carefully parallelized.
  • Future Directions: The authors suggest exploring more complex sampling designs beyond the Poisson scheme and investigating how to adaptively learn the link functions for inclusion probabilities during the training process.

Summary updated

Abstract

In certain situations that shall be undoubtedly more and more common in the\nBig Data era, the datasets available are so massive that computing statistics\nover the full sample is hardly feasible, if not unfeasible. A natural approach\nin this context consists in using survey schemes and substituting the "full\ndata" statistics with their counterparts based on the resulting random samples,\nof manageable size. It is the main purpose of this paper to investigate the\nimpact of survey sampling with unequal inclusion probabilities on stochastic\ngradient descent-based M-estimation methods in large-scale statistical and\nmachine-learning problems. Precisely, we prove that, in presence of some a\npriori information, one may significantly increase asymptotic accuracy when\nchoosing appropriate first order inclusion probabilities, without affecting\ncomplexity. These striking results are described here by limit theorems and are\nalso illustrated by numerical experiments.\n
BibTeX
@misc{clemencon2015survey,
  author = {Stéphan Clémençon and Patrice Bertail and Emilie Chautru and Guillaume Papa},
  title = {{Survey schemes for stochastic gradient descent with applications to\textbackslash\{\}n M-estimation}},
  year = {2015},
  eprint = {1501.02218},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.02218},
}
Figure