  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.
