Only Tails Matter: Average-Case Universality and Robustness in the Convex Regime
The recently developed average-case analysis of optimization methods allows a
more fine-grained and representative convergence analysis than usual worst-case
results. In exchange, this analysis requires a more precise hypothesis over the
data generating process, namely assuming knowledge of the expected spectral
distribution (ESD) of the random matrix associated with the problem. This work
shows that the concentration of eigenvalues near the edges of the ESD
determines a problem's asymptotic average complexity. This a priori information
on this concentration is a more grounded assumption than complete knowledge of
the ESD. This approximate concentration is effectively a middle ground between
the coarseness of the worst-case scenario convergence and the restrictive
previous average-case analysis. We also introduce the Generalized Chebyshev
method, asymptotically optimal under a hypothesis on this concentration and
globally optimal when the ESD follows a Beta distribution. We compare its
performance to classical optimization algorithms, such as gradient descent or
Nesterov's scheme, and we show that, in the average-case context, Nesterov's
method is universally nearly optimal asymptotically.