Sampling and empirical risk minimization
- 28 November 2016
- journal article
- research article
- Published by Taylor & Francis in Statistics
- Vol. 51 (1) , 30-42
Abstract
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 samples is hardly feasible, if not unfeasible. A natural approach in this context consists in using survey schemes and substituting the ‘full data’ statistics with their counterparts based on the resulting random samples, of manageable size. It is the main purpose of this paper to investigate the impact of survey sampling on statistical learning methods based on empirical risk minimization through the standard binary classification problem, considered here as a ‘case in point’. Precisely, we prove that, in presence of auxiliary information, appropriate use of optimally coupled Poisson survey plans may not affect much the learning rates, while possibly reducing significantly the number of terms that must be averaged to compute the empirical risk functional with overwhelming probability. These striking results are next shown to extend to more general sampling schemes by means of a coupling technique, originally introduced by Hajek [Asymptotic theory of rejective sampling with varying probabilities from a finite population. Ann Math Stat. 1964;35(4):1491–1523].Keywords
This publication has 19 references indexed in Scilit:
- Improved Horvitz–Thompson Estimation of Model Parameters from Two-phase Stratified Samples: Applications in EpidemiologyStatistics in Biosciences, 2009
- A Z‐theorem with Estimated Nuisance Parameters and Correction Note for ‘Weighted Likelihood for Semiparametric Models and Two‐phase Stratified Samples, with Application to Cox Regression’Scandinavian Journal of Statistics, 2008
- Convexity, Classification, and Risk BoundsJournal of the American Statistical Association, 2006
- Theory of Classification: a Survey of Some Recent AdvancesESAIM: Probability and Statistics, 2005
- Concept learning using complexity regularizationIEEE Transactions on Information Theory, 1996
- Calibration Estimators in Survey SamplingJournal of the American Statistical Association, 1992
- Large Sample Theory of Empirical Distributions in Biased Sampling ModelsThe Annals of Statistics, 1988
- On the Convergence of the Horvitz‐Thompson EstimatorAustralian Journal of Statistics, 1982
- Asymptotic Theory of Rejective Sampling with Varying Probabilities from a Finite PopulationThe Annals of Mathematical Statistics, 1964
- A Generalization of Sampling Without Replacement from a Finite UniverseJournal of the American Statistical Association, 1952