Timezone: »

Implicit Regularization of Accelerated Methods in Hilbert Spaces
Nicolò Pagliana · Lorenzo Rosasco

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #231

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.

Author Information

Nicolò Pagliana (Università degli studi di Genova (DIMA))
Lorenzo Rosasco (University of Genova- MIT - IIT)

More from the Same Authors