SIAM Journal on Optimization · 2020 · 17 citations · 19 references
ComputingComputer ScienceAlgorithmsOptimizationTheory Of ComputationApproximation AlgorithmsConvex AnalysisConvex OptimizationNumerical AlgorithmsOptimization TheoryRobust OptimizationAccelerated OptimizationRestart
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.
19
Smooth minimization of non-smooth functions
Yu. Nesterov · Mathematical Programming · 2004 · 2.6K citations
Gradient methods for minimizing composite functions
Yu. Nesterov · Mathematical Programming · 2012 · 1.4K citations
Hédy Attouch, Jérôme Bolte, Patrick Redont et al. · Mathematics of Operations Research · 2010 · 1.2K citations · Full text