Sharpness, Restart, and Acceleration

Vincent Roulet, Alexandre d’Aspremont

SIAM Journal on Optimization · 2020 · 17 citations · 19 references

DOIFull text

Open access

Concepts

Abstract

The Ł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 Nemirovskii and Nesterov [USSR Comput. Math. Math. Phys., 25 (1985), pp. 21--30]. The constants quantifying these sharpness 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.

References

19