Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent

Stephan Clemencon; Patrice Bertail; Emilie Chautru

doi:10.1109/BigData.2014.7004208

Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent

Stephan Clemencon, Patrice Bertail, Emilie Chautru

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 sample 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 purpose of this paper to investigate the impact of survey sampling with unequal inclusion probabilities on (stochastic) gradient descent-based M-estimation methods in large-scale statistical-learning problems. We prove that, in presence of some a priori information, one may significantly reduce the number of terms that must be averaged to estimate the gradient at each step with overwhelming probability, while preserving the asymptotic accuracy. These striking results are described here by limit theorems.

Original language	English
Title of host publication	Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014
Editors	Jimmy Lin, Jian Pei, Xiaohua Tony Hu, Wo Chang, Raghunath Nambiar, Charu Aggarwal, Nick Cercone, Vasant Honavar, Jun Huan, Bamshad Mobasher, Saumyadipta Pyne
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	25-30
Number of pages	6
ISBN (Electronic)	9781479956654
DOIs	https://doi.org/10.1109/BigData.2014.7004208
Publication status	Published - 1 Jan 2014
Externally published	Yes
Event	2nd IEEE International Conference on Big Data, Big Data 2014 - Washington, United States Duration: 27 Oct 2014 → 30 Oct 2014

Publication series

Name	Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

Conference

Conference	2nd IEEE International Conference on Big Data, Big Data 2014
Country/Territory	United States
City	Washington
Period	27/10/14 → 30/10/14

Keywords

Horvitz-Thompson estimation
sampling design
statistical learning
stochastic gradient descent
survey

Access to Document

10.1109/BigData.2014.7004208

Cite this

Clemencon, S., Bertail, P., & Chautru, E. (2014). Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent. In J. Lin, J. Pei, X. T. Hu, W. Chang, R. Nambiar, C. Aggarwal, N. Cercone, V. Honavar, J. Huan, B. Mobasher, & S. Pyne (Eds.), Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014 (pp. 25-30). Article 7004208 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2014.7004208

Clemencon, Stephan ; Bertail, Patrice ; Chautru, Emilie. / Scaling up M-estimation via sampling designs : The Horvitz-Thompson stochastic gradient descent. Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. editor / Jimmy Lin ; Jian Pei ; Xiaohua Tony Hu ; Wo Chang ; Raghunath Nambiar ; Charu Aggarwal ; Nick Cercone ; Vasant Honavar ; Jun Huan ; Bamshad Mobasher ; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 25-30 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

@inproceedings{217d385b893c4d23aa87ea6c0c07102f,

title = "Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent",

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 sample 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 purpose of this paper to investigate the impact of survey sampling with unequal inclusion probabilities on (stochastic) gradient descent-based M-estimation methods in large-scale statistical-learning problems. We prove that, in presence of some a priori information, one may significantly reduce the number of terms that must be averaged to estimate the gradient at each step with overwhelming probability, while preserving the asymptotic accuracy. These striking results are described here by limit theorems.",

keywords = "Horvitz-Thompson estimation, sampling design, statistical learning, stochastic gradient descent, survey",

author = "Stephan Clemencon and Patrice Bertail and Emilie Chautru",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2nd IEEE International Conference on Big Data, Big Data 2014 ; Conference date: 27-10-2014 Through 30-10-2014",

year = "2014",

month = jan,

day = "1",

doi = "10.1109/BigData.2014.7004208",

language = "English",

series = "Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "25--30",

editor = "Jimmy Lin and Jian Pei and Hu, \{Xiaohua Tony\} and Wo Chang and Raghunath Nambiar and Charu Aggarwal and Nick Cercone and Vasant Honavar and Jun Huan and Bamshad Mobasher and Saumyadipta Pyne",

booktitle = "Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014",

}

Clemencon, S, Bertail, P & Chautru, E 2014, Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent. in J Lin, J Pei, XT Hu, W Chang, R Nambiar, C Aggarwal, N Cercone, V Honavar, J Huan, B Mobasher & S Pyne (eds), Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014., 7004208, Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014, Institute of Electrical and Electronics Engineers Inc., pp. 25-30, 2nd IEEE International Conference on Big Data, Big Data 2014, Washington, United States, 27/10/14. https://doi.org/10.1109/BigData.2014.7004208

Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent. / Clemencon, Stephan; Bertail, Patrice; Chautru, Emilie.
Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. ed. / Jimmy Lin; Jian Pei; Xiaohua Tony Hu; Wo Chang; Raghunath Nambiar; Charu Aggarwal; Nick Cercone; Vasant Honavar; Jun Huan; Bamshad Mobasher; Saumyadipta Pyne. Institute of Electrical and Electronics Engineers Inc., 2014. p. 25-30 7004208 (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Scaling up M-estimation via sampling designs

T2 - 2nd IEEE International Conference on Big Data, Big Data 2014

AU - Clemencon, Stephan

AU - Bertail, Patrice

AU - Chautru, Emilie

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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 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 purpose of this paper to investigate the impact of survey sampling with unequal inclusion probabilities on (stochastic) gradient descent-based M-estimation methods in large-scale statistical-learning problems. We prove that, in presence of some a priori information, one may significantly reduce the number of terms that must be averaged to estimate the gradient at each step with overwhelming probability, while preserving the asymptotic accuracy. These striking results are described here by limit theorems.

AB - 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 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 purpose of this paper to investigate the impact of survey sampling with unequal inclusion probabilities on (stochastic) gradient descent-based M-estimation methods in large-scale statistical-learning problems. We prove that, in presence of some a priori information, one may significantly reduce the number of terms that must be averaged to estimate the gradient at each step with overwhelming probability, while preserving the asymptotic accuracy. These striking results are described here by limit theorems.

KW - Horvitz-Thompson estimation

KW - sampling design

KW - statistical learning

KW - stochastic gradient descent

KW - survey

U2 - 10.1109/BigData.2014.7004208

DO - 10.1109/BigData.2014.7004208

M3 - Conference contribution

AN - SCOPUS:84921770482

T3 - Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014

SP - 25

EP - 30

BT - Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014

A2 - Lin, Jimmy

A2 - Pei, Jian

A2 - Hu, Xiaohua Tony

A2 - Chang, Wo

A2 - Nambiar, Raghunath

A2 - Aggarwal, Charu

A2 - Cercone, Nick

A2 - Honavar, Vasant

A2 - Huan, Jun

A2 - Mobasher, Bamshad

A2 - Pyne, Saumyadipta

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 27 October 2014 through 30 October 2014

ER -

Clemencon S, Bertail P, Chautru E. Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent. In Lin J, Pei J, Hu XT, Chang W, Nambiar R, Aggarwal C, Cercone N, Honavar V, Huan J, Mobasher B, Pyne S, editors, Proceedings - 2014 IEEE International Conference on Big Data, Big Data 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 25-30. 7004208. (Proceedings - 2014 IEEE International Conference on Big Data, IEEE Big Data 2014). doi: 10.1109/BigData.2014.7004208

Scaling up M-estimation via sampling designs: The Horvitz-Thompson stochastic gradient descent

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this