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

¹ Telecom ParisTech LTCI, Université Paris Saclay, 46 Rue Barrault, Paris 75634, France.
² Université Paris Ouest, MODAL’X, 200 Avenue de la République, Nanterre 92000, France.
³ Mines ParisTech, PSL University, Centre de géosciences, 35 Rue Saint Honoré, Fontainebleau 77305, France.

^* Corresponding author: stephan.clemencon@telecom-paristech.fr

Received: 3 January 2018
Accepted: 22 October 2018

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.