Smoothed Analysis: Why the Simplex Method Beats Its Worst Case

The simplex method for linear programming has been the practical standard for decades while carrying an exponential worst-case bound. The two standard explanations for that gap are both unsatisfying. The worst-case bound is real, and there are inputs that achieve it. An average-case bound would require claiming that practical instances are drawn from some distribution, which is hard to establish for any particular workload and which an adversary is free to violate. Smoothed analysis replaces the distributional assumption with a statement about perturbation: the input may be chosen adversarially, but it is then blurred by noise, and the running time is expressed as a function of the amount of noise rather than as a single number.

The exponential worst case is not hypothetical

Klee and Minty gave a family of linear programs whose geometry defeats a common pivot rule. In dimension d the polytope is a distorted cube with 2d constraints and 2^d vertices, and the rule that pivots to the adjacent vertex with the largest rate of improvement walks through every vertex before reaching the optimum. Neither the vertex count nor the pivot path is an artefact of a large coefficient; the construction scales the distortion by a parameter so that the polytope stays close to an ordinary cube. The exponential behaviour is therefore in the algorithm and the rule, not in a contrived objective.

Three properties of that construction matter for what follows. Its size is exponential in the dimension, so its cost is exponential in the size of the description. Its geometry is degenerate in a specific way: many constraints are nearly parallel, so the path the pivot rule follows is fragile. And the fragility is quantitative. Nudge the coefficient matrix entries by a small amount and the largest-improvement path no longer visits every vertex, because the ordering of the vertices that the construction arranged for that rule depended on the exact coefficients.

That observation is the seed of the whole method: the bad case is not merely rare, it is unstable.

The smoothed model

Smoothed analysis changes the question from “what is the worst-case running time” to “what is the worst-case running time of an adversary who must choose an input with limited precision”. Formally, an adversary selects a linear program with constraint matrix A, right-hand side b, and objective c. The analysis then studies the algorithm on a perturbed instance in which A is replaced by

à = A + (σ·‖A‖)·G

where G is a matrix of independent standard Gaussian entries, ‖A‖ a norm of the original matrix, and σ > 0 the noise parameter. The complexity is measured in expectation over G and then maximised over A, b, and c. The two extremes are instructive. At σ = 0 the perturbation vanishes and the model is the ordinary worst case, so the Klee–Minty program is still admissible. As σ grows, the admissible inputs become a fatter neighbourhood of each adversarial instance, and the adversary’s freedom to concentrate on the degenerate construction disappears.

The claim that results is not a single number but a curve: smoothed complexity as a function of the dimension and of σ. Two properties of that curve are wanted. It should be polynomial in the dimension for each fixed σ, and it should grow as σ decreases so that the worst-case bound is recovered in the limit.

What was proved for the simplex method

Spielman and Teng analysed the shadow-vertex simplex method, a randomised variant whose pivot rule is defined by the projection of the polytope onto a random two-dimensional plane, and showed that its smoothed complexity on perturbed instances is polynomial in the number of constraints, the number of variables, and 1/σ. The argument runs through the condition number of the perturbed polytope: perturbation bounds the condition number of Ã with high probability, and the number of pivots made by the shadow-vertex rule is bounded by a polynomial in the dimension and the condition number. Since the perturbation only increases the set of instances compared with the exact case, the result does not contradict the Klee–Minty example; it explains why an adversary would have to aim at a measure-zero target to produce the exponential path, and why a small error in the coefficients destroys the target.

The reason the noise needs to be Gaussian rather than merely bounded is analytic. The proof needs the perturbed constraint directions to avoid the degenerate configurations that the pivot path depends on, and it needs to bound the probability that a small set of d × d minors is near-singular when the entries are perturbed. Bounded perturbations with the right support give related results, but the tail behaviour of the noise enters the constant in the exponent of 1/σ.

Numbers, precision, and why the parameter is not infinitesimal

The smoothed bound is polynomial in 1/σ, so something has to be said about the size of σ that corresponds to a real problem. If the entries of A come from measurements, σ is the relative measurement error, which is many orders of magnitude above machine precision. If the entries are the output of a floating-point computation, σ cannot be smaller than the precision of the arithmetic: double precision carries about 16 decimal digits, so a computed coefficient has roughly σ ≈ 10^(-16) of unexplained error before any modelling error is counted, and the modelling error is usually far larger.

A bound that is polynomial in the dimension and in 1/σ is therefore not vacuous at realistic precision, because 1/σ enters as a polynomial factor rather than in the exponent of the dimension. A bound with 2^(1/σ) in it would be useless, and the distinction between a polynomial and an exponential dependence on 1/σ is the whole content of the statement.

The perturbation also has to be scaled sensibly. Multiplying by ‖A‖ makes the noise relative to the instance, so a program whose coefficients are all around 10^6 is perturbed by proportional amounts and not by absolute ones. The scaling choice changes the model rather than merely the constants, and the published results fix the scale explicitly for that reason.

import random

def perturb(rows, sigma, scale):
    """Gaussian perturbation of a constraint matrix, entrywise and independent."""
    perturbed = []
    for row in rows:
        perturbed.append([a + random.gauss(0.0, sigma * scale) for a in row])
    return perturbed

A = [[1.0, 1.0], [1.0, -1.0], [-1.0, 0.0]]
for sigma in (1e-3, 1e-8):
    for row in perturb(A, sigma, 1.0):
        print(f'{sigma:.0e}', [round(v, 10) for v in row])

The two runs differ only in σ, and the rounding in the printout decides how much of the deviation is visible rather than whether it is there. A pivot rule that depended on an exact tie between two rows would be defeated at either setting, which is the mechanism the smoothed bound charges for.

Other algorithms, and the limits of the technique

The method is not specific to linear programming. The k-means clustering iteration has a worst-case superpolynomial bound; under Gaussian perturbation of the input points its smoothed complexity is polynomial in the number of points, the dimension, and 1/σ. The perceptron algorithm for linear programming has an exponential worst case and a polynomial smoothed bound, from the same argument about the geometry of perturbed halfspaces. In each case the pattern repeats: an algorithm with a fragile worst case, an adversarial construction that depends on that fragility, a perturbation that removes it, and a parameter that measures the cost of removing it.

Three limitations are worth stating plainly. First, the adversary still chooses the input; only the perturbation is random. An adversary who is allowed to know σ and to choose A after seeing the distribution still cannot force the exponential path, but the model says nothing about an adversary who controls the noise itself, nor about noise drawn from a distribution other than the one analysed. Second, the results are per algorithm and often per pivot rule. Smoothed polynomial bounds for one simplex variant do not transfer to another, and the exponential constructions are also rule-specific, so the two statements have to be matched before either is informative. Third, smoothed analysis bounds expected running time, so it inherits everything that an expectation hides: a per-run guarantee requires a tail bound, and the distinction between expectation and per-operation guarantee is the one drawn in expected, amortized, and average cost.

The technique also does not replace the worst-case bound. σ is a parameter of the model, and taking it to zero returns the original analysis; the smoothed result is a statement about a family of analyses, one for each σ. What it adds is a single curve instead of two unrelated extreme points, which makes the gap between theory and practice a quantitative question rather than a matter of assumption.

Where this sits among the other averaging arguments

Four different averages have now appeared: over a sequence of operations on one structure, over the random choices of an algorithm, over a distribution of inputs, and over a perturbation of an adversarially chosen input. They are not interchangeable, and each buys a different kind of statement. The amortized argument in dynamic arrays gives a bound for every input sequence and no bound on any single operation. A randomised algorithm such as universal hashing gives a per-operation bound for every input chosen without knowledge of the random seed. Average-case analysis asserts something about the caller. Smoothed analysis asserts something about the input’s precision, which is the one quantity that is always available and rarely infinitesimal: any numeric instance carries error, and the smoothed bound prices it.

Whether the bounds hold in a specific setting is also a question about the cost model. A bound that counts pivot steps and a bound that counts floating-point operations on a word RAM differ before any averaging happens, and the model’s treatment of arithmetic is set out in cost models for the word RAM. When a smoothed analysis is quoted, the pivot count and the arithmetic cost model are two separate claims, and both belong in the statement.