{"id":"arxiv/2611.14282","url":"https://arxiv.org/abs/2611.14282","tags":["math.OC","cs.CC"],"score":0,"title":"From Worst-Case to Smoothed Complexity in Continuous Optimization","domain":"math.OC","source":"arxiv","authors":["Daniel Cortild","Coralia Cartis"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-10","reactions":{}}