Average-case Acceleration Through Spectral Density Estimation

Abstract

We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian's eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods are momentum-based algorithms, whose hyper-parameters can be estimated without knowledge of the Hessian's smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.

References in corpus (7)

• Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• From Averaging to Acceleration, There is Only a Step-size
• Accelerating Smooth Games by Manipulating Spectral Shapes
• The asymptotic spectrum of the Hessian of DNN throughout training
• Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations

Cited by in corpus (6)

• On the Suboptimality of Negative Momentum for Minimax Optimization
• Hessian Eigenspectra of More Realistic Nonlinear Models
• Beyond Random Matrix Theory for Deep Networks
• SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality
• Average-case Acceleration for Bilinear Games and Normal Matrices
• Universal Average-Case Optimality of Polyak Momentum