Halting Time is Predictable for Large Models: A Universality Property and Average-Case Analysis
Courtney Paquettea b✉, Bart van Merriënboerb, Elliot Paquettea, Fabián Pedregosab
- aDepartment of Mathematics and Statistics, McGill University, Montreal, QC, Canada
- bGoogle Research, Brain Team, Montreal, QC, Canada
- ✉Corresponding author
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
Average-case analysis computes the complexity of an algorithm averaged over all possible inputs. Compared to worst-case analysis, it is more representative of the typical behavior of an algorithm, but remains largely unexplored in optimization. One difficulty is that the analysis can depend on the probability distribution of the inputs to the model. However, we show that this is not the case for a class of large-scale problems trained with first-order methods including random least squares and one-hidden layer neural networks with random weights. In fact, the halting time exhibits a universality property : it is independent of the probability distribution. With this barrier for average-case analysis removed, we provide the first explicit average-case convergence rates showing a tighter complexity not captured by traditional worst-case analysis. Finally, numerical simulations suggest this universality property holds for a more general class of algorithms and problems.
TL;DRThis work provides the first explicit average-case convergence rates showing a tighter complexity not captured by traditional worst-case analysis, and suggests that this universality property holds for a more general class of algorithms and problems. (Semantic Scholar)