Variance-Reduced Methods for Machine Learning

Robert M. Gower; Mark Schmidt; Francis Bach; Peter Richtarik

doi:10.1109/JPROC.2020.3028013

Variance-Reduced Methods for Machine Learning

Robert M. Gower, Mark Schmidt, Francis Bach, Peter Richtarik

Research output: Contribution to journal › Article › peer-review

66 Scopus citations

Abstract

Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last eight years have seen an exciting new development: Variance reduction for stochastic optimization methods. These variance-reduced (VR) methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory and practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at nonexpert readers. We focus mainly on the convex setting and leave pointers to readers interested in extensions for minimizing nonconvex functions.

Original language	English (US)
Pages (from-to)	1968-1983
Number of pages	16
Journal	Proceedings of the IEEE
Volume	108
Issue number	11
DOIs	https://doi.org/10.1109/JPROC.2020.3028013
State	Published - Oct 16 2020

Bibliographical note

KAUST Repository Item: Exported on 2020-11-16
Acknowledgements: The authors would like to thank Quanquan Gu, Julien Mairal, Tong Zhang, and Lin Xiao for valuable suggestions and comments on an earlier draft of this article. In particular, Quanquan’s recommendations for the nonconvex section improved the organization of our Section IV-G.

Access to Document

10.1109/JPROC.2020.3028013

Cite this

@article{7e08f7bdedf042a4b0efc72b9addd577,

title = "Variance-Reduced Methods for Machine Learning",

abstract = "Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last eight years have seen an exciting new development: Variance reduction for stochastic optimization methods. These variance-reduced (VR) methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory and practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at nonexpert readers. We focus mainly on the convex setting and leave pointers to readers interested in extensions for minimizing nonconvex functions.",

author = "Gower, {Robert M.} and Mark Schmidt and Francis Bach and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2020-11-16 Acknowledgements: The authors would like to thank Quanquan Gu, Julien Mairal, Tong Zhang, and Lin Xiao for valuable suggestions and comments on an earlier draft of this article. In particular, Quanquan{\textquoteright}s recommendations for the nonconvex section improved the organization of our Section IV-G.",

year = "2020",

month = oct,

day = "16",

doi = "10.1109/JPROC.2020.3028013",

language = "English (US)",

volume = "108",

pages = "1968--1983",

journal = "Proceedings of the IEEE",

issn = "1558-2256",

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

number = "11",

}

TY - JOUR

T1 - Variance-Reduced Methods for Machine Learning

AU - Gower, Robert M.

AU - Schmidt, Mark

AU - Bach, Francis

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2020-11-16 Acknowledgements: The authors would like to thank Quanquan Gu, Julien Mairal, Tong Zhang, and Lin Xiao for valuable suggestions and comments on an earlier draft of this article. In particular, Quanquan’s recommendations for the nonconvex section improved the organization of our Section IV-G.

PY - 2020/10/16

Y1 - 2020/10/16

N2 - Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last eight years have seen an exciting new development: Variance reduction for stochastic optimization methods. These variance-reduced (VR) methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory and practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at nonexpert readers. We focus mainly on the convex setting and leave pointers to readers interested in extensions for minimizing nonconvex functions.

AB - Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last eight years have seen an exciting new development: Variance reduction for stochastic optimization methods. These variance-reduced (VR) methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory and practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at nonexpert readers. We focus mainly on the convex setting and leave pointers to readers interested in extensions for minimizing nonconvex functions.

UR - http://hdl.handle.net/10754/665943

UR - https://ieeexplore.ieee.org/document/9226504/

UR - http://www.scopus.com/inward/record.url?scp=85095713994&partnerID=8YFLogxK

U2 - 10.1109/JPROC.2020.3028013

DO - 10.1109/JPROC.2020.3028013

M3 - Article

SN - 1558-2256

VL - 108

SP - 1968

EP - 1983

JO - Proceedings of the IEEE

JF - Proceedings of the IEEE

IS - 11

ER -

Variance-Reduced Methods for Machine Learning

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this