← 研踪 PaperTrailarXiv:2611.14282 · v1
From Worst-Case to Smoothed Complexity in Continuous Optimization
从最坏情况到平滑复杂度：连续优化中的平滑分析框架
首次提交 2026-11-11 00:23
版本更新 2026-11-11 00:23
雷达观测 2026-11-11 13:07
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-11 00:23 · 最新观测版本
From Worst-Case to Smoothed Complexity in Continuous Optimization
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.
查看此版本解读 →查看此版本原文 ↗