On the design-dependent suboptimality of the Lasso

Understand

This paper investigates the effect of the design matrix on the ability (or inability) to estimate a sparse parameter in linear regression.

• More specifically, we characterize the optimal rate of estimation when the smallest singular value of the design matrix is bounded away from zero.
• In addition to this information-theoretic result, we provide and analyze a procedure which is simultaneously statistically optimal and computationally efficient, based on soft thresholding the ordinary least squares estimator.
• Most surprisingly, we show that the Lasso estimator -- despite its widespread adoption for sparse linear regression -- is provably minimax rate-suboptimal when the minimum singular value is small.