Understanding average-case acceleration for quadratic minimization

Abstract

This thesis develops the average-case analysis of first-order methods on quadratic forms and derive optimal algorithms under the average-case analysis. In order to obtain the average-case optimal method, we adapt the three-term relation of orthogonal polynomial with respect to the expected spectrum of Hessian of objective. The original result considers only the distance from optimal point under the initial distance condition and we expand the choices of optimality measures and initial conditions for a unified analysis. In addition, we analyze the convergence rates for the exponential distribution. Numerical experiments are detailed on diverse optimality measures.