2025/04/05 by Eleon Bach, Sophie Huiberts, Bach, Eleon +1 · 3 voices · 3 citations
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2504.04197
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis. Spielman and Teng (STOC '01) introduced the smoothed analysis framework of algorithm analysis and applied it to the simplex method. Given an arbitrary linear program with d variables and n inequality constraints, Spielman and Teng proved that the simplex method runs in time O(σ-30 d55 n86), where σ> 0 is the standard deviation of Gaussian distributed noise added to the original LP data. Spielman and Teng's result was simplified and strengthened over a series of works, with the current strongest upper bound being O(σ-3/2 d13/4 log(n)7/4) pivot steps due to Huiberts, Lee and Zhang (STOC '23). We prove that there exists a simplex method whose smoothed complexity is upper bounded by O(σ-1/2 d11/4 log(n)7/4) pivot steps. Furthermore, we prove a matching high-probability lower bound of Ω( σ-1/2 d1/2ln(4/σ)-1/4) on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using n = \lfloor (4/σ)d \rfloor inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.