Timezone: »

 
Poster
Acceleration through spectral density estimation
Fabian Pedregosa · Damien Scieur

Thu Jul 16 06:00 AM -- 06:45 AM & Thu Jul 16 06:00 PM -- 06:45 PM (PDT) @ Virtual
in Poster Session 41 »

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.

Keywords: Algorithms · Convex Optimization · Large Scale Learning and Big Data · Optimization · Optimization - Convex
[ Slides] 

Author Information

Fabian Pedregosa (Google)
Damien Scieur (Samsung - SAIT AI Lab, Montreal)

More from the Same Authors