What is smoothed analysis?
Daniel Spielman won the Rolf Nevanlinna Prize in 2010 “for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing.” In our interview I asked him to explain smoothed analysis.
DS: A lot of my time I spend trying to analyze algorithms, and when we do analysis of algorithms in the theoretical computer science community we like to say things like “this algorithm will always run in less than so much time.” And when you can do that it’s incredibly powerful. You have this great guarantee on your algorithm. But a lot of times you don’t need those kinds of bounds. If your algorithm runs for too long, you just hit Control-C and you go home, or you try a different algorithm.
There are a lot of situations where you have algorithms that usually work, but they don’t always work. And for some of these, the notion of “usually” is so strong that they’re never observed to fail, to take too long. And I wanted to come up with a theoretical explanation for why this could be. So Shang-Hua Teng and I came up with this idea. We focused on the simplex method because it works incredibly well in practice, but there are these bizarre examples where it fails. [NB: The simplex method always “works” in the sense that it terminates with a correct answer. In this interview DS uses “fail” to mean failure to run quickly.] And we tried to look at those to see if we could reason about them and fix it. We were actually trying to improve the simplex method when we started out and we couldn’t do that. But these examples where it fails are so hard to construct. Even the three dimensional examples looked bizarre. And it occurred to us, maybe this means that they actually are bizarre in a well-defined sense.
So we had the idea, maybe if your inputs were not chosen by an adversary trying to mess up your algorithm, maybe your algorithm was actually likely to work. If there’s noise in your inputs, say from measurements, you usually have imprecision in the lower-order bits, some randomness, and maybe that could be used to guarantee the algorithm would work well. What we were able to do for the simplex method — for one variant, I admit not the most used variant — is show that it would run in polynomial time if there was noise in your lower order bits. …
Sort of what it tells you is that bad inputs look like points that lie near some low-dimensional manifold. The way my colleague Shang-Hua Teng put it, if you’re trying to build your example with boxing gloves on, you couldn’t make an example that takes a lot of time. These are very special inputs. People have gone on to show that there are many algorithms that work well in practice that don’t work in the worst case. You can’t prove worst-case analysis of them but you can do smoothed analysis.
JC: So it was known before you did this that the average run time for the simplex method was polynomial …
DS: Yes, there were results showing that if you take completely random input, the run time should be polynomial. People didn’t feel like that explained what was really going on when they were looking at linear programming problems, because “random” seems very special.
JC: Random in what sense?
DS: That was the thing, you needed, say, a random matrix where every entry was an independent Gaussian random variable. Or something like that. So it was random in a very particular sense. We were looking at things that were random in the lower-order bits, not in all bits. Now we appreciate that random matrices are very special objects that have well-defined properties with very high probability. We wanted to show that the bad examples are everywhere sparse, so you’re very unlikely to run into one.
JC: So your analysis is giving you more information about the pathological cases, rather than just saying they happen with low probability.
DS: That’s right. It says that anywhere you look, most cases around there will not be pathological.
One of the things people first asked us when we did this was “Does this mean that you can solve linear programs faster just by perturbing them and solving them?” No it doesn’t, because on these bad instances, if you perturb them a little bit your answer changes a lot. However, people have used these ideas to analyze algorithms in other areas, like solving systems of polynomial equations.