Implicit Regularization of Accelerated Methods in Hilbert Spaces

TitleImplicit Regularization of Accelerated Methods in Hilbert Spaces
Publication TypeConference Proceedings
Year of Publication2019
AuthorsPagliana, N, Rosasco, L
Conference Name Neural Information Processing Systems (NeurIPS 2019)
Date Published11/2019
Conference LocationVancouver, Canada

We study learning properties of accelerated gradient descent methods for linear least-squares in Hilbert spaces. We analyze the implicit regularization properties of Nesterov acceleration and a variant of heavy-ball in terms of corresponding learning error bounds. Our results show that acceleration can provides faster bias decay than gradient descent, but also suffers of a more unstable behavior. As a result acceleration cannot be in general expected to improve learning accuracy with respect to gradient descent, but rather to achieve the same accuracy with reduced computations. Our theoretical results are validated by numerical simulations. Our analysis is based on studying suitable polynomials induced by the accelerated dynamics and combining spectral techniques with concentration inequalities.

Associated Module: 

CBMM Relationship: 

  • CBMM Funded