Implicit Sparse Regularization: The Impact of Depth and Early Stopping

Jiangyuan Li; Thanh V. Nguyen; Chinmay Hegde; Raymond K.W. Wong

Implicit Sparse Regularization: The Impact of Depth and Early Stopping

Jiangyuan Li, Thanh V. Nguyen, Chinmay Hegde, Raymond K.W. Wong

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

Abstract

In this paper, we study the implicit bias of gradient descent for sparse regression. We extend results on regression with quadratic parametrization, which amounts to depth-2 diagonal linear networks, to more general depth-N networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, a phenomenon that we call implicit sparse regularization. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. We characterize the impact of depth and early stopping and show that for a general depth parameter N, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization w₀ and step size η. In particular, we show that increasing depth enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely to take place.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
Editors	Marc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
Publisher	Neural information processing systems foundation
Pages	28298-28309
Number of pages	12
ISBN (Electronic)	9781713845393
State	Published - 2021
Event	35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online Duration: Dec 6 2021 → Dec 14 2021

Publication series

Name	Advances in Neural Information Processing Systems
Volume	34
ISSN (Print)	1049-5258

Conference

Conference	35th Conference on Neural Information Processing Systems, NeurIPS 2021
City	Virtual, Online
Period	12/6/21 → 12/14/21

ASJC Scopus subject areas

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

Li, J., Nguyen, T. V., Hegde, C., & Wong, R. K. W. (2021). Implicit Sparse Regularization: The Impact of Depth and Early Stopping. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021 (pp. 28298-28309). (Advances in Neural Information Processing Systems; Vol. 34). Neural information processing systems foundation.

Implicit Sparse Regularization: The Impact of Depth and Early Stopping. / Li, Jiangyuan; Nguyen, Thanh V.; Hegde, Chinmay et al.
Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. ed. / Marc'Aurelio Ranzato; Alina Beygelzimer; Yann Dauphin; Percy S. Liang; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. p. 28298-28309 (Advances in Neural Information Processing Systems; Vol. 34).

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

Li, J, Nguyen, TV, Hegde, C & Wong, RKW 2021, Implicit Sparse Regularization: The Impact of Depth and Early Stopping. in MA Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Advances in Neural Information Processing Systems, vol. 34, Neural information processing systems foundation, pp. 28298-28309, 35th Conference on Neural Information Processing Systems, NeurIPS 2021, Virtual, Online, 12/6/21.

Li J, Nguyen TV, Hegde C, Wong RKW. Implicit Sparse Regularization: The Impact of Depth and Early Stopping. In Ranzato MA, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, editors, Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. Neural information processing systems foundation. 2021. p. 28298-28309. (Advances in Neural Information Processing Systems).

Li, Jiangyuan ; Nguyen, Thanh V. ; Hegde, Chinmay et al. / Implicit Sparse Regularization : The Impact of Depth and Early Stopping. Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021. editor / Marc'Aurelio Ranzato ; Alina Beygelzimer ; Yann Dauphin ; Percy S. Liang ; Jenn Wortman Vaughan. Neural information processing systems foundation, 2021. pp. 28298-28309 (Advances in Neural Information Processing Systems).

@inproceedings{7b7142b141a844a7bf4ca213134b455b,

title = "Implicit Sparse Regularization: The Impact of Depth and Early Stopping",

abstract = "In this paper, we study the implicit bias of gradient descent for sparse regression. We extend results on regression with quadratic parametrization, which amounts to depth-2 diagonal linear networks, to more general depth-N networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, a phenomenon that we call implicit sparse regularization. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. We characterize the impact of depth and early stopping and show that for a general depth parameter N, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization w0 and step size η. In particular, we show that increasing depth enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely to take place.",

author = "Jiangyuan Li and Nguyen, {Thanh V.} and Chinmay Hegde and Wong, {Raymond K.W.}",

note = "Publisher Copyright: {\textcopyright} 2021 Neural information processing systems foundation. All rights reserved.; 35th Conference on Neural Information Processing Systems, NeurIPS 2021 ; Conference date: 06-12-2021 Through 14-12-2021",

year = "2021",

language = "English (US)",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

pages = "28298--28309",

editor = "Marc'Aurelio Ranzato and Alina Beygelzimer and Yann Dauphin and Liang, {Percy S.} and {Wortman Vaughan}, Jenn",

booktitle = "Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021",

}

TY - GEN

T1 - Implicit Sparse Regularization

T2 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

AU - Li, Jiangyuan

AU - Nguyen, Thanh V.

AU - Hegde, Chinmay

AU - Wong, Raymond K.W.

PY - 2021

Y1 - 2021

N2 - In this paper, we study the implicit bias of gradient descent for sparse regression. We extend results on regression with quadratic parametrization, which amounts to depth-2 diagonal linear networks, to more general depth-N networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, a phenomenon that we call implicit sparse regularization. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. We characterize the impact of depth and early stopping and show that for a general depth parameter N, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization w0 and step size η. In particular, we show that increasing depth enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely to take place.

AB - In this paper, we study the implicit bias of gradient descent for sparse regression. We extend results on regression with quadratic parametrization, which amounts to depth-2 diagonal linear networks, to more general depth-N networks, under more realistic settings of noise and correlated designs. We show that early stopping is crucial for gradient descent to converge to a sparse model, a phenomenon that we call implicit sparse regularization. This result is in sharp contrast to known results for noiseless and uncorrelated-design cases. We characterize the impact of depth and early stopping and show that for a general depth parameter N, gradient descent with early stopping achieves minimax optimal sparse recovery with sufficiently small initialization w0 and step size η. In particular, we show that increasing depth enlarges the scale of working initialization and the early-stopping window so that this implicit sparse regularization effect is more likely to take place.

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

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

M3 - Conference contribution

AN - SCOPUS:85121806745

T3 - Advances in Neural Information Processing Systems

SP - 28298

EP - 28309

BT - Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

A2 - Ranzato, Marc'Aurelio

A2 - Beygelzimer, Alina

A2 - Dauphin, Yann

A2 - Liang, Percy S.

A2 - Wortman Vaughan, Jenn

PB - Neural information processing systems foundation

Y2 - 6 December 2021 through 14 December 2021

ER -

Implicit Sparse Regularization: The Impact of Depth and Early Stopping

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this