  The {\L}ojasiewicz inequality shows that sharpness bounds on the minimum of
convex optimization problems hold almost generically. Sharpness directly
controls the performance of restart schemes, as observed by Nemirovsky and
Nesterov (1985). The constants quantifying these sharpness bounds are of course
unobservable, but we show that optimal restart strategies are robust, in the
sense that, in some important cases, finding the best restart scheme only
requires a log scale grid search. Overall then, restart schemes generically
accelerate accelerated first-order methods.
