从最坏情况到平滑复杂度：连续优化中的平滑分析框架
From Worst-Case to Smoothed Complexity in Continuous Optimization
Daniel Cortild, Coralia Cartis
AI 速读 基于摘要
作者提出一个平滑分析框架，研究经典连续优化算法在任意函数随机扰动下的表现，并给出若干标准方法的平滑复杂度保证。
math.OC · cs.CC
查看原文摘要
Worst-case complexity bounds often fail to reflect the practical performance of optimization algorithms, while average-case complexity heavily relies on the distribution of the input. In this work, we develop a smoothed-analysis framework for classical continuous optimization algorithms by studying their behaviour on random perturbations of arbitrary functions. Our main contribution is to apply methods suited for non-degenerate functions to perturbations of degenerate functions, thereby recovering the faster best-known rates for the non-degenerate class. We derive smoothed complexity guarantees for several standard methods, including (Accelerated) Gradient Descent, Conjugate Gradient, and Newton-type methods, under various settings including nonconvex ones, and show that these bounds can substantially improve upon their worst-case guarantees, bringing them closer to the practical behaviour of the respective methods.