Timezone: »

Sharpness, Restart and Acceleration
Vincent Roulet · Alexandre d'Aspremont

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #173 #None

The {\L}ojasiewicz inequality shows that H\"olderian error bounds on the minimum of convex optimization problems hold almost generically. Here, we clarify results of \citet{Nemi85} who show that H\"olderian error bounds directly controls the performance of restart schemes. The constants quantifying error bounds are of course unobservable, but we show that optimal restart strategies are robust, and searching for the best scheme only increases the complexity by a logarithmic factor compared to the optimal bound. Overall then, restart schemes generically accelerate accelerated methods.

Author Information

Vincent Roulet (University of Washington)
Alexandre d'Aspremont (CNRS - Ecole Normale Supérieure)

More from the Same Authors