  We study the complexity of the entire regularization path for least squares
regression with 1-norm penalty, known as the Lasso. Every regression parameter
in the Lasso changes linearly as a function of the regularization value. The
number of changes is regarded as the Lasso's complexity. Experimental results
using exact path following exhibit polynomial complexity of the Lasso in the
problem size. Alas, the path complexity of the Lasso on artificially designed
regression problems is exponential.
  We use smoothed analysis as a mechanism for bridging the gap between worst
case settings and the de facto low complexity. Our analysis assumes that the
observed data has a tiny amount of intrinsic noise. We then prove that the
Lasso's complexity is polynomial in the problem size. While building upon the
seminal work of Spielman and Teng on smoothed complexity, our analysis is
morally different as it is divorced from specific path following algorithms. We
verify the validity of our analysis in experiments with both worst case
settings and real datasets. The empirical results we obtain closely match our
analysis.
