PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Regression and Lasso

Huan Xu, Constantine Caramanis, Shie Mannor

arXiv:0811.1790v1cs.ITcs.LG

TL;DR

The paper asks how Lasso’s sparsity relates to robustness, consistency, and stability. It recasts Lasso as robust regression, extends the formulation through uncertainty sets, and analyzes these properties directly. The results connect regularization to noise protection, explain sparsity geometrically, re-prove consistency, and establish a sparsity–stability trade-off.

  • Problem

    Existing work recognizes Lasso’s sparsity, but the paper investigates its robustness interpretation and the relationships among sparsity, consistency, and algorithmic stability.

  • Method

    The paper formulates robust regression with feature-wise and coupled uncertainty sets, relates the formulation to kernel density estimation, and analyzes sparsity, consistency, and stability.

  • Results

    Lasso is recovered as robust regression, robustness explains sparsity and supports a consistency proof, and a no-free-lunch theorem shows that sparsity and algorithmic stability contradict each other.

  • Takeaways & Limitations

    Robustness provides a physical basis for selecting regularizers and designing convex Lasso generalizations, while sparse regression requires trading off algorithmic stability.

Abstract

from arXiv · show

Lasso, or $\ell^1$ regularized least squares, has been explored extensively for its remarkable sparsity properties. It is shown in this paper that the solution to Lasso, in addition to its sparsity, has robustness properties: it is the solution to a robust optimization problem. This has two important consequences. First, robustness provides a connection of the regularizer to a physical property, namely, protection from noise. This allows a principled selection of the regularizer, and in particular, generalizations of Lasso that also yield convex optimization problems are obtained by considering different uncertainty sets. Secondly, robustness can itself be used as an avenue to exploring different properties of the solution. In particular, it is shown that robustness of the solution explains why the solution is sparse. The analysis as well as the specific results obtained differ from standard sparsity results, providing different geometric intuition. Furthermore, it is shown that the robust optimization formulation is related to kernel density estimation, and based on this approach, a proof that Lasso is consistent is given using robustness directly. Finally, a theorem saying that sparsity and algorithmic stability contradict each other, and hence Lasso is not stable, is presented.

I. INTRODUCTION

The paper interprets Lasso as robust least-squares regression under feature-wise uncertainty, connecting its regularization to protection from noise. It develops convex generalizations, robustness-based sparsity analysis, consistency results, and a stability trade-off.

  • Lasso is the solution to a robust optimization problem, giving its ℓ1 regularizer an interpretation as protection against feature noise.
  • IV. SPARSITY: Robustness explains sparsity geometrically: a coefficient is nonzero when its feature remains relevant under all allowable perturbations, extending beyond squared loss.
  • A. Formulation: Different uncertainty sets generalize Lasso to other convex regularization schemes and can mitigate conservativeness or encode feature coupling.
  • The paper relates Lasso to kernel density estimation and uses robustness to re-prove consistency, while establishing that sparsity and algorithmic stability cannot both be achieved.
  • A. Formulation: Feature-wise uncoupled norm-bounded disturbances yield an easily solvable robust regression problem equivalent to ℓ1-regularized regression.

B. Uncertainty Set Construction

The paper constructs uncertainty sets that translate robust regression into convex, Lasso-like regularized regression, supporting arbitrary loss norms, coupled disturbances, and flexible disturbance models.

  • Uncertainty-set selection: Uncertainty sets can be selected using chance constraints when disturbance distributions or partial moment information are available.The paper discusses exact distributions and first- and second-moment information as bases for requiring constraints to hold with a specified probability.
  • Uncertainty-set selection: Distribution-based feature uncertainty sets can be constructed by line search and bisection, while moment-based sets use probability bounds.The moment-based procedure relies on a tight first-two-moment bound and a multivariate generalization of Markov’s inequality.
  • Computational tractability: The moment-bound optimization is a semidefinite program solvable in polynomial time and remains valid when the estimated second moment is only an upper bound.This preserves probability guarantees even when variance information is imprecise.
  • Generalizations: The robust formulation generalizes in two directions: arbitrary norm losses and coupled uncertainty sets.Coupled sets allow feature disturbances to satisfy joint convex conditions, reducing conservativeness and enabling additional solution properties.
  • Convex reformulations: Under suitable relative-interior assumptions, robust regression is equivalent to a regularized regression problem whose objective is convex and whose subgradient can be efficiently evaluated.The resulting framework includes symmetric-norm and polytope uncertainty sets, with polytope sets preserving linearity and broad modeling power.
  • Examples: Specific uncertainty sets model cardinality-constrained feature corruption or produce elastic-net-like combinations of ℓ2 and ℓ1 regularization.The elastic-net-like formulation arises when columns and rows of the data matrix can be perturbed independently.

IV. SPARSITY

The paper explains Lasso sparsity through robustness: coefficients can vanish when allowable feature perturbations make corresponding features irrelevant, yielding geometric sparsity conditions.

  • Robustness-based sparsity: The sparsity analysis does not assume a generative model and instead studies conditions under which a feature receives zero weight.This complements statistical approaches that assume observations arise from sparse feature combinations.
  • Geometric conditions: The robustness argument supplies geometric intuition distinct from standard sparsity proofs and establishes a connection between uncertainty properties and sparsity.The paper notes that related incoherence-based results exist, but emphasizes the novelty of deriving them through robustness.
  • Support conditions: A robust solution supported on I exists when a perturbation of features outside I makes those features irrelevant to the robust regression problem.Theorem 5 formalizes this support-preservation condition for feature-wise uncoupled uncertainty sets.
  • Generative interpretation: In a generative model using features in I, Lasso assigns zero weight to feature j outside I when an allowable perturbation can make that feature irrelevant.The result is presented as an interpretation of the robustness theorem rather than as an assumption needed for establishing it.
  • Geometric conditions: For ℓ2 loss, nearly orthogonal features receive zero weight under an incoherence-type condition.Theorem 6 imposes a bound on inner products between unit vectors in the span of selected features and the remaining features.

V. DENSITY ESTIMATION AND CONSISTENCY

The paper rederives Lasso’s asymptotic consistency by viewing robust optimization as a maximum-error problem over probability measures that includes a kernel density estimator.

  • The consistency proof represents the robust optimization formulation as the maximum error over a class of probability measures containing a kernel density estimator.

A. Robust Optimization, Worst-case Expected Utility and Kernel Density Estimator

This section connects robust regression with worst-case expected utility and kernel density estimation, while emphasizing that the key equivalence holds for arbitrary observed samples without distributional assumptions.

  • Robust optimization and expected utility: The analysis first establishes an equivalence between robust optimization and worst-case expected utility over a class of probability measures.
  • Robust optimization and expected utility: For Lasso, the robust regression loss over training data equals the worst-case expected generalization error for a fixed x.
  • Sample-based interpretation: The distribution class is built from hyper-rectangle disturbance sets centered on observed targets and residual-related quantities, with bounded column disturbances.
  • Sample-based interpretation: The equality is non-probabilistic and holds for arbitrary A and b, without assuming independent samples or a particular generating distribution.The associated distribution class is defined from the observed samples and bounded disturbance sets.
  • Kernel density estimation: A kernel density estimator uses iid samples, a kernel function, and bandwidth sequence conditions under which it converges in L1 to the target density.

B. Consistency of Lasso

The paper rederives Lasso consistency through distributional robustness: the robust formulation contains a kernel density estimator, whose convergence supports consistency under stated conditions.

  • Under bounded-support sampling, cn ↓ 0, and lim n→∞ n(cn)^(m+1) = ∞, consistency follows if the solution norms remain bounded.The bounded-norm condition appears in the stated theorem.
  • The consistency theorem is well known, but the robustness-based proof applies to a wider range of algorithms than techniques based on VC dimension or stability.The paper specifically notes that Lasso is not stable, motivating the alternative proof route.
  • The robust formulation can be viewed as maximum error over a class of probability measures containing a kernel density estimator.This representation is the basis for the consistency proof.
  • Lasso consistency is proved using the L1 convergence property of the kernel density estimator.The paper presents this as a robustness-based proof rather than relying on standard consistency techniques.
  • The paper also removes the bounded-solution-norm assumption in a later result, while emphasizing the proof technique rather than a changed conclusion.The alternative argument uses a bound growing with 1/cn.

VI. STABILITY

The paper defines uniform stability through the loss change caused by removing one training sample and shows that Lasso’s stability can be as poor as the trivial bound.

  • The paper concludes that sparsity and non-trivial algorithmic stability cannot be achieved simultaneously by an algorithm satisfying the stated sparsity condition.This broader conclusion is developed from the Lasso result.
  • Uniform stability requires the loss difference between training on S and on S\i to be uniformly bounded by βm.The definition ranges over every training set, removed sample, and evaluation point.
  • Lasso’s stability is much worse than that of ℓ2-regularized regression and is described as being as bad as possible.The comparison is made against Tikhonov-regularized regression, whose stability scales as 1/m.
  • The uniform stability bound of Lasso is lower bounded by the trivial bound when the number of features is halved.This is stated as the main stability theorem before its construction-based proof.
  • The proof constructs a sample set where the full-sample solution has zero test cost, while the leave-one-out solution incurs the trivial-bound cost.The construction uses alternative optimal solutions supported on different feature blocks.

VII. CONCLUSION

The conclusion frames feature-perturbation robustness as an interpretation and extension of Lasso, then uses that interpretation to study consistency, sparsity, and the tradeoff with stability.

  • Feature-wise perturbations in least-square robust regression yield weighted ℓ1-regularized regression when disturbances across features are uncorrelated.This provides the robustness interpretation of Lasso.
  • Coupled disturbances produce tractable robust regression problems that generalize Lasso to a wider class of regularization schemes.The uncertainty structure can therefore encode additional regularization forms.
  • The paper investigates Lasso sparsity and consistency through its robustness interpretation.The conclusion presents these as consequences of the robust formulation.
  • Sparsity and algorithmic stability are incompatible in the paper’s no-free-lunch theorem, so regression design must trade off these properties.The conclusion treats both properties as desirable but jointly unattainable under the theorem’s scope.
  • The robust optimization perspective supplies motivation for selecting existing regularization parameters and designing new regularization schemes.The paper positions robustness as both an interpretation and a design principle.

APPENDIX A PROOF OF THEOREM 2

The appendix proves the equivalence between a robust regression problem and a regularized regression problem by evaluating the worst-case feature disturbance through convex duality.

  • A quadratic expectation argument uses trace terms and ellipsoid-containment conditions to establish the auxiliary bound needed by the theorem.The proof invokes the S-Procedure to certify the containment condition.
  • The theorem states that the robust regression problem is equivalent to a regularized regression problem.This equivalence is the appendix’s central result.
  • The proof represents the disturbance uncertainty set using feature-wise constraints and a convex set of allowable magnitudes.The displayed uncertainty set separates feature disturbances while coupling their magnitudes through c ∈ Z.
  • For a fixed solution x*, the worst-case disturbance term becomes maximization of |x*|⊤c over the uncertainty set.This converts the robust contribution into a linear optimization problem in c.
  • Slater’s condition ensures zero duality gap for the resulting convex minimization, enabling the regularized reformulation.The proof then substitutes the dual expression back into the robust objective.

APPENDIX C PROOF OF PROPOSITION 1

The proof establishes Proposition 1 by first proving an auxiliary lemma and then applying it to ϵ-optimal points and their empirical distribution.

  • Lemma 2: The proof begins by establishing Lemma 2 for a function f and a Borel set Z.The lemma is then used as an intermediate step toward Proposition 1.
  • Lemma 2: An ϵ-optimal solution is used to construct a probability measure concentrated on that solution.This measure assigns mass 1 to the selected point and satisfies µ′(Z) = 1.
  • Lemma 2: The proof derives bounds for arbitrary probability measures supported on Z using the constructed function and the ϵ-optimality relation.The argument uses f(x) ≤ ˆf(x) + ǫ and lets ǫ become arbitrarily small.
  • Lemma 2: Combining the preceding inequalities proves Lemma 2 and completes its role in the proposition’s proof.The proof explicitly concludes the lemma after combining equations (15) and (16).
  • Proposition 1: For Proposition 1, ϵ-optimal solutions are selected for each set Zi, and their empirical distribution is shown to belong to Pn.The proposition then follows by combining the constructed function, Equation (18), and the fact that ǫ can approach zero.

APPENDIX D PROOF OF COROLLARY 3

The appendix proves Corollary 3 by identifying the right-hand side of Equation (20) with the robust formulation and applying Proposition 1.

  • Statement: Corollary 3 states an equation for any x ∈ Rm given b ∈ Rn and A ∈ Rn×m.The displayed equation itself is not included in the supplied passage.
  • Construction: The uncertainty set used in the construction is represented through intervals [bi − σi, bi + σi] within Pn(A, ∆, b, σ).The supplied definition is truncated after the product notation.
  • Proof: The proof evaluates the right-hand side of Equation (20) and relates the left-hand side to the robust formulation.These are the two intermediate identifications used in the argument.
  • Proof: Applying Proposition 1 yields the claimed result and completes the proof of the corollary.The appendix explicitly concludes that this application proves the corollary.
Loading 0811.1790v1…