Sharpness, Restart, and Acceleration
研究了凸优化问题中尖锐性边界对重启方案性能的影响，发现最优重启策略具有鲁棒性，且搜索最佳方案仅使复杂度增加对数因子，从而重启方案通常能加速已加速的方法。
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.