Constrained stochastic gradient descent for large-scale least squares problem

Yang Mu; Wei Ding; Tianyi Zhou; Dacheng Tao

doi:10.1145/2487575.2487635

Constrained stochastic gradient descent for large-scale least squares problem

Yang Mu
, Wei Ding
, Tianyi Zhou
, Dacheng Tao

Computer Science

University of Massachusetts Boston
University of Technology Sydney

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

Abstract

The least squares problem is one of the most important regression problems in statistics, machine learning and data mining. In this paper, we present the Constrained Stochastic Gradient Descent (CSGD) algorithm to solve the largescale least squares problem. CSGD improves the Stochastic Gradient Descent (SGD) by imposing a provable constraint that the linear regression line passes through the mean point of all the data points. It results in the best regret bound O(log T), and fastest convergence speed among all first order approaches. Empirical studies justify the effectiveness of CSGD by comparing it with SGD and other state-of-Theart approaches. An example is also given to show how to use CSGD to optimize SGD based least squares problems to achieve a better performance.

Original language	English
Title of host publication	KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Editors	Rajesh Parekh, Jingrui He, Dhillon S. Inderjit, Paul Bradley, Yehuda Koren, Rayid Ghani, Ted E. Senator, Robert L. Grossman, Ramasamy Uthurusamy
Publisher	Association for Computing Machinery
Pages	883-891
Number of pages	9
ISBN (Electronic)	9781450321747
DOIs	https://doi.org/10.1145/2487575.2487635
State	Published - Aug 11 2013
Event	19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 - Chicago, United States Duration: Aug 11 2013 → Aug 14 2013

Publication series

Name	Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Volume	Part F128815

Conference

Conference	19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013
Country/Territory	United States
City	Chicago
Period	8/11/13 → 8/14/13

ASJC Scopus Subject Areas

Software
Information Systems

Keywords

Large-scale least squares
Online learning
Stochastic optimization

Access to Document

10.1145/2487575.2487635

Cite this

Mu, Y., Ding, W., Zhou, T., & Tao, D. (2013). Constrained stochastic gradient descent for large-scale least squares problem. In R. Parekh, J. He, D. S. Inderjit, P. Bradley, Y. Koren, R. Ghani, T. E. Senator, R. L. Grossman, & R. Uthurusamy (Eds.), KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 883-891). Article 2487635 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F128815). Association for Computing Machinery. https://doi.org/10.1145/2487575.2487635

Constrained stochastic gradient descent for large-scale least squares problem. / Mu, Yang; Ding, Wei; Zhou, Tianyi et al.
KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ed. / Rajesh Parekh; Jingrui He; Dhillon S. Inderjit; Paul Bradley; Yehuda Koren; Rayid Ghani; Ted E. Senator; Robert L. Grossman; Ramasamy Uthurusamy. Association for Computing Machinery, 2013. p. 883-891 2487635 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F128815).

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

Mu, Y, Ding, W, Zhou, T & Tao, D 2013, Constrained stochastic gradient descent for large-scale least squares problem. in R Parekh, J He, DS Inderjit, P Bradley, Y Koren, R Ghani, TE Senator, RL Grossman & R Uthurusamy (eds), KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining., 2487635, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, vol. Part F128815, Association for Computing Machinery, pp. 883-891, 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, United States, 8/11/13. https://doi.org/10.1145/2487575.2487635

Mu Y, Ding W, Zhou T, Tao D. Constrained stochastic gradient descent for large-scale least squares problem. In Parekh R, He J, Inderjit DS, Bradley P, Koren Y, Ghani R, Senator TE, Grossman RL, Uthurusamy R, editors, KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery. 2013. p. 883-891. 2487635. (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining). doi: 10.1145/2487575.2487635

Mu, Yang ; Ding, Wei ; Zhou, Tianyi et al. / Constrained stochastic gradient descent for large-scale least squares problem. KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. editor / Rajesh Parekh ; Jingrui He ; Dhillon S. Inderjit ; Paul Bradley ; Yehuda Koren ; Rayid Ghani ; Ted E. Senator ; Robert L. Grossman ; Ramasamy Uthurusamy. Association for Computing Machinery, 2013. pp. 883-891 (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{acb559e9e07d427b8da2a9e1e3d8975c,

title = "Constrained stochastic gradient descent for large-scale least squares problem",

abstract = "The least squares problem is one of the most important regression problems in statistics, machine learning and data mining. In this paper, we present the Constrained Stochastic Gradient Descent (CSGD) algorithm to solve the largescale least squares problem. CSGD improves the Stochastic Gradient Descent (SGD) by imposing a provable constraint that the linear regression line passes through the mean point of all the data points. It results in the best regret bound O(log T), and fastest convergence speed among all first order approaches. Empirical studies justify the effectiveness of CSGD by comparing it with SGD and other state-of-Theart approaches. An example is also given to show how to use CSGD to optimize SGD based least squares problems to achieve a better performance.",

keywords = "Large-scale least squares, Online learning, Stochastic optimization",

author = "Yang Mu and Wei Ding and Tianyi Zhou and Dacheng Tao",

note = "Publisher Copyright: Copyright {\textcopyright} 2013 ACM.; 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 ; Conference date: 11-08-2013 Through 14-08-2013",

year = "2013",

month = aug,

day = "11",

doi = "10.1145/2487575.2487635",

language = "English",

series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

publisher = "Association for Computing Machinery",

pages = "883--891",

editor = "Rajesh Parekh and Jingrui He and Inderjit, \{Dhillon S.\} and Paul Bradley and Yehuda Koren and Rayid Ghani and Senator, \{Ted E.\} and Grossman, \{Robert L.\} and Ramasamy Uthurusamy",

booktitle = "KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

}

TY - GEN

T1 - Constrained stochastic gradient descent for large-scale least squares problem

AU - Mu, Yang

AU - Ding, Wei

AU - Zhou, Tianyi

AU - Tao, Dacheng

PY - 2013/8/11

Y1 - 2013/8/11

N2 - The least squares problem is one of the most important regression problems in statistics, machine learning and data mining. In this paper, we present the Constrained Stochastic Gradient Descent (CSGD) algorithm to solve the largescale least squares problem. CSGD improves the Stochastic Gradient Descent (SGD) by imposing a provable constraint that the linear regression line passes through the mean point of all the data points. It results in the best regret bound O(log T), and fastest convergence speed among all first order approaches. Empirical studies justify the effectiveness of CSGD by comparing it with SGD and other state-of-Theart approaches. An example is also given to show how to use CSGD to optimize SGD based least squares problems to achieve a better performance.

AB - The least squares problem is one of the most important regression problems in statistics, machine learning and data mining. In this paper, we present the Constrained Stochastic Gradient Descent (CSGD) algorithm to solve the largescale least squares problem. CSGD improves the Stochastic Gradient Descent (SGD) by imposing a provable constraint that the linear regression line passes through the mean point of all the data points. It results in the best regret bound O(log T), and fastest convergence speed among all first order approaches. Empirical studies justify the effectiveness of CSGD by comparing it with SGD and other state-of-Theart approaches. An example is also given to show how to use CSGD to optimize SGD based least squares problems to achieve a better performance.

KW - Large-scale least squares

KW - Online learning

KW - Stochastic optimization

UR - https://www.scopus.com/pages/publications/84988412002

UR - https://www.scopus.com/pages/publications/84988412002#tab=citedBy

U2 - 10.1145/2487575.2487635

DO - 10.1145/2487575.2487635

M3 - Conference contribution

AN - SCOPUS:84988412002

T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 883

EP - 891

BT - KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

A2 - Parekh, Rajesh

A2 - He, Jingrui

A2 - Inderjit, Dhillon S.

A2 - Bradley, Paul

A2 - Koren, Yehuda

A2 - Ghani, Rayid

A2 - Senator, Ted E.

A2 - Grossman, Robert L.

A2 - Uthurusamy, Ramasamy

PB - Association for Computing Machinery

T2 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013

Y2 - 11 August 2013 through 14 August 2013

ER -

Constrained stochastic gradient descent for large-scale least squares problem

Abstract

Publication series

Conference

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this