From Worst-Case to Smoothed Complexity in Continuous Optimization
math.OC, cs.CC
Submitted: 2026-11-10
Updated: 2026-11-10
Code: https://github.com/DanielCortild/Smoothed-Analysis
Terminology
Sources
- Gradient Span Algorithms Make Predictable Progress in High Dimension
- Smoothed Analysis of Online Metric Problems
- Quadratic Objective Perturbation: Curvature-Based Differential Privacy
- Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance
- A remark on the smallest singular value of powers of Gaussian matrices
- Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-\L{}ojasiewicz Condition
- The smallest singular value of a random rectangular matrix
- Non-asymptotic theory of random matrices: extreme singular values
- Moment bounds for condition numbers and singular values of high-dimensional Gaussian random matrices: Applications and limitations
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise