Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

By Daniel A. Spielman, Shang-Hua Teng. Symposium on the Theory of Computing, 2001

993 citations recorded by the source corpus.

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. Essentially, we study the performance of algorithms under small random perturbations of their inputs. We show that the shadow-vertex simplex algorithm has polynomial smoothed complexity.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/91d5cd8560a1f05654a8e32450ed939e9cd15b57

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

The null space property for sparse recovery from multiple measurement vectors (2011, neutral): “[26]).”
Quantum Computing in the NISQ era and beyond (2018, background): “lly explain. We can anticipate that the same thing will happen with quantum computers. For example, theorists eventually explained why the simplex method for linear programming works well in practice [24], but only long after it had been found to be useful experimentally. A current example is deep l”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, neutral): “, [190] and references therein).”
Learning and Smoothed Analysis (2009, positive): “Motivated by smoothed analysis [13], we define learning C with respect to smoothed product distributions as follows.”
Quantum machine learning: a classical perspective (2017, background): “Furthermore, smoothed analysis [74,75] provides a framework for studying the time performance of an algorithm in the presence of realistic input noise distributions.”
Poisson convergence in the restricted k-partitioning problem (2007, background): “Smoothed Analysis was introduced by Spielman and Teng in [28] and they discuss a perturbation”
Learning Two-layer Neural Networks with Symmetric Inputs (2018, methodology): “We justify these assumptions using the smoothed analysis framework (Spielman and Teng, 2004).”
Training Over-parameterized Deep ResNet Is almost as Easy as Training a Two-layer Network (2019, methodology): “The gradient lower-bound at the initialization is given in [Allen-Zhu et al., 2018b, Section 6.2] via the smoothed analysis [Spielman and Teng, 2004]: with high probability the gradient is lower-bounded, although the worst case it might be 0.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Smooth analysis [45] might also be used for analyzing the effect of such noise, but this is beyond the scope of this paper.”
Limits on fundamental limits to computation (2014, positive): “For some important problems and algorithms, such as the Simplex algorithm for linear programming , few inputs lead to exponential runtime, and minute perturbations reduce runtime to polynomial [80].”
An Update on the Hirsch Conjecture (2009, background): “In [55], Spielman and Teng proved that the expected diameter of a linear program that is perturbed within a parameter σ is polynomial in d , n, and σ−1.”