Implicit Regularization of Accelerated Methods in Hilbert Spaces

Abstract

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.

References in corpus (7)

• Understanding deep learning requires rethinking generalization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Train faster, generalize better: Stability of stochastic gradient descent
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• Stability and Convergence Trade-off of Iterative Optimization Algorithms

Cited by in corpus (4)

• Learning with Gradient Descent and Weakly Convex Losses
• Iterative regularization for convex regularizers
• Nonparametric Topological Layers in Neural Networks
• Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?