PaperlayerView exact revision on arXiv

Source-linked AI summary

Lower bounds on the performance of polynomial-time algorithms for sparse linear regression

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan

arXiv:1402.1918v2math.STcs.CCstat.TH

TL;DR

Prior work leaves open whether the gap in prediction-error guarantees for ℓ1-based methods persists across all polynomial-time estimators. Under the assumption that NP is not contained in P/poly, the paper establishes such a gap for sparse linear regression: for a suitably constructed design, polynomial-time estimators have prediction error that depends inversely on the restricted eigenvalue constant, unlike optimal algorithms.

  • Problem

    Whether the prediction-error gap for ℓ1-based methods persists when considering all polynomial-time estimators, rather than only the Lasso, remains open.

    Source: §1 · pp. 2–3

  • Method

    The paper constructs a family of design matrices and proves a lower bound for every polynomial-time estimator under the assumption that NP is not contained in P/poly.

    Source: §1 · p. 3, §3 · p. 6

  • Results

    For a suitably constructed design, optimal prediction error has no dependence on the restricted eigenvalue constant, while every polynomial-time algorithm's prediction error exhibits an inverse dependence.

    Source: §5 · p. 17

  • Takeaways & Limitations

    The paper establishes a polynomially constrained minimax-rate lower bound relying only on a worst-case complexity assumption.

    Source: §5 · p. 17

    The result is conditional on the assumption that NP is not contained in P/poly.

    Source: §3 · p. 6

Abstract

from arXiv · show

Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.

1 Introduction

This section frames whether the gap between ℓ0-based and ℓ1-based prediction guarantees reflects a limitation of the Lasso or of polynomial-time methods more broadly. It answers that question by showing, under a worst-case complexity assumption, a gap between polynomial-time and optimal sparse-regression prediction performance.

1 Introduction

  • Sparse regression seeks a low-prediction-error estimate of a k-sparse regression vector from a response and a fixed design matrix.The model uses Gaussian observation noise.Source: §1 · pp. 1–2
  • Direct ℓ0-constrained least squares entails considering many supports, motivating polynomial-time ℓ1 relaxations such as the Lasso and basis pursuit.These convex optimization methods can be computed in polynomial time, and have achieved minimax-optimal performance in some cases.Source: §1 · p. 2
  • The ℓ0-based estimator has a uniform prediction guarantee for any fixed design, whereas common ℓ1-based guarantees require a restricted eigenvalue condition.The restricted eigenvalue constant measures design conditioning, even though conditioning need not determine whether a good sparse predictor exists.Source: §1 · pp. 2–3
  • The paper asks whether the Lasso's restricted-eigenvalue-dependent prediction guarantee reflects conservative analysis or a broader limit on polynomial-time estimators.A prior result found a Lasso prediction-error lower bound for a particular 2-sparse case violating the restricted eigenvalue condition.Source: §1 · p. 3
  • Under NP not in P/poly, a family of design matrices makes every polynomial-time estimator incur a prediction-error lower bound, yielding a gap from the optimal ℓ0-based method.The paper contrasts this worst-case complexity assumption with prior results based on average-case complexity.Source: §1 · pp. 1, 3

2 Background and problem set-up

The section sets up sparse linear regression and compares a direct sparse estimator with a thresholded Lasso using prediction error. It explains how restricted eigenvalues qualify the thresholded Lasso’s guarantee.

2 Background and problem set-up

  • The section introduces sparse regression, restricted eigenvalues, and prediction error as the framework for characterizing the ℓ0 estimator and thresholded Lasso.The regression vector is k-sparse, and the estimator is required to return a k-sparse vector.Source: §2 · p. 3, §2.1 · p. 4

2.1 Estimators for sparse linear regression

  • The ℓ0-based estimator has a prediction-error guarantee for any design matrix, with probability at least 1 − 2e^(−c2 k log d).The section uses this estimator as the comparison point for the thresholded Lasso.Source: §2.1 · p. 4
  • The thresholded Lasso is formed by regularized Lasso estimation followed by retaining the k largest coefficients in absolute value.This truncation makes the estimator k-sparse and places it in the family of k-sparse estimators.Source: §2.1 · p. 4

2.2 Restricted eigenvalues and ℓ1-guarantees

  • The restricted eigenvalue condition measures design curvature on a cone that includes vectors whose off-support ℓ1 norm is small relative to their on-support norm.The condition matters for ℓ1-based prediction guarantees, although it is not necessary for small prediction loss itself.Source: §2.2 · pp. 4–5
  • The thresholded Lasso guarantee requires a normalized design with positive restricted eigenvalue constant and holds with probability at least 1 − 2e^(−c4 k log d).Its bound differs from the ℓ0-based guarantee by a 1/γ(X)^2 term, where γ(X) depends on the design matrix.Source: §2.2 · p. 5

3 Main result and its consequences

Under NP ⊄ P/poly, the theorem constructs normalized designs with restricted-eigenvalue control on which polynomial-efficient estimators face an unavoidable prediction-risk penalty, characterizing a gap from the ℓ0 estimator.

3 Main result and its consequences

  • Polynomial-efficient estimators are parameterized by program length b, input-quantization accuracy G, and runtime H as a function of input size.The definition bounds program encoding length, quantization level, and termination time.Source: §3 · p. 6
  • For sufficiently large parameter choices, the theorem supplies a sparsity level and a range of dimensions and sample sizes for which its design and risk bounds hold.The theorem allows any positive b, δ in (0, 1), and polynomial functions F, G, and H.Source: §3 · p. 7
  • The lower bound for polynomial-efficient estimators essentially matches the thresholded Lasso upper bound on the constructed normalized designs with restricted-eigenvalue control.The theorem’s design satisfies the normalization and RE conditions, and δ can be chosen arbitrarily close to zero.Source: §3 · p. 7
  • The theorem characterizes a gap between optimal and polynomial-time algorithms, with polynomial-time risk depending inversely on γ(X) while the ℓ0 estimator does not.The result establishes that the inverse dependence on the RE constant is unavoidable for polynomial-time algorithms.Source: §3 · pp. 6–7
  • The hardness result applies to a design matrix fixed ahead of time and to all polynomial-time algorithms, unlike the earlier adversarial-matrix result.The constructed design also satisfies normalization and RE conditions, allowing the thresholded Lasso upper bound to apply.Source: §3 · p. 7

4 Proof of Theorem 1

The section proves Theorem 1 by establishing worst-case sparse-regression hardness, deriving probabilistic hardness and a design-matrix construction for part (a), and reducing a hard recovery problem to a prediction-error lower bound for part (b).

4.1 An NP-Hard Problem

  • Under Claims 1 and 2, if ∥Mu − v∥2 < 1/2, then exactly m/3 selected 3-sets from C cover S, forming an exact cover.Source: §4.1 · p. 10

4.2 Probabilistic Hardness

  • Assuming A, for any NP-hard problem P, arbitrary polynomial bounds f and g, and positive integer m0, some m > m0 forces every algorithm encoded in f(m) bits and terminating in g(m) time to fail on at least one input with probability greater than 1/2.Source: §4.2 · p. 10

4.3 Proof of part (a)

  • Using M as a building block, the proof constructs a quantized design matrix X and establishes the restricted-eigenvalue and upper-bound conditions required for Theorem 1(a).The construction selects a value of x and a realization of R so that X = ⌊Cx⌋L has the stated properties.Source: §4.3 · p. 12

4.4 Proof of part (b)

  • Section 4.4 begins by denoting the top and bottom halves of X by X↑ and X↓, respectively.Source: §4.4 · p. 13
  • The reduction constructs an intermediate problem P2′ from a hard P1 instance and shows that a P2 estimator solves P2′ with prediction error of the same order.P2′ bridges the additional Gaussian design rows and response noise in the regression model.Source: §4.4 · p. 13
  • A large subset of the constructed estimators outputs sparse solutions with positive probability, supporting the transfer of P1’s recovery hardness to regression prediction error.The proof combines this property with a bound relating P2′’s prediction error to that of an auxiliary solver.Source: §4.4 · pp. 15–16
  • With d bounded by a polynomial in k and α set to δ/8, the proof completes the theorem’s lower-bound argument.The proof chooses parameters to meet the lemma conditions before deriving the lower bound.Source: §4.4 · p. 17

5 Conclusion

Under a standard complexity conjecture, the paper establishes a gap between optimal and polynomial-time prediction error, with the latter depending inversely on the restricted eigenvalue constant for a suitably constructed design. The authors identify this as the first lower bound on the polynomially constrained minimax rate based only on a worst-case complexity conjecture.

5 Conclusion

  • The prediction error of optimal algorithms has no restricted-eigenvalue dependence, whereas polynomial-time algorithms exhibit inverse dependence on that constant for a suitably constructed design.The authors state that this establishes a fundamental gap under a standard complexity conjecture.Source: §5 · p. 17
  • The result is the first lower bound on the polynomially constrained minimax rate of statistical estimation based only on a worst-case complexity conjecture.Source: §5 · p. 17

A Technical lemmas for Theorem 1

The appendix collects proofs of technical lemmas used in the proof of the main theorem.

A Technical lemmas for Theorem 1

A.1 Proof of Lemma 2

The proof shows that a polynomial-time randomized solver for an NP-hard problem would yield polynomial advice and a deterministic polynomial-time solver. It does so by repeating the randomized machine enough times to succeed on every input of a given length with positive probability, then fixing a successful random sequence.

A.1 Proof of Lemma 2

  • Under Assumption A, these conditions certify that the problem belongs to P/poly.The argument handles input lengths at most m0 with a constant-size machine.Source: §A.1 · p. 18
  • Repeating the randomized machine m + 1 times gives a positive probability that it succeeds on every input of length m.Independence gives per-input failure probability 2^(-m-1); a union bound over at most 2^m inputs yields success probability at least 1/2.Source: §A.1 · p. 18
  • A successful random sequence can be fixed as advice, allowing a deterministic machine to simulate the m + 1 executions on every input of length m.The advice contains the machine code and fixed random sequence.Source: §A.1 · p. 18
  • The advice length is O(f(m)+mg(m)) bits and the resulting running time is O(mg(m)).Source: §A.1 · p. 18

A.2 Proof of Lemma 4

Lemma 8 supplies a random matrix Cτ that, with exponentially high probability, satisfies the RE condition and upper bounds. The proof then uses continuity and quantization to obtain a matrix satisfying the stated conditions.

A.2 Proof of Lemma 4

  • With probability at least 1 − c1 exp(−c2n), Cτ satisfies the RE condition with parameter γ and the stated upper bounds.The supplied passages do not specify the upper-bound values.Source: §A.2 · pp. 18–19
  • A realization of Cτ satisfies both normalization and RE conditions, with RE constant at least γ.The proof uses continuity of the RE constant to choose τ′ such that γ(Cτ′) = γ.Source: §A.2 · p. 20
  • Quantizing Cτ′ to precision 2^-L preserves the stated RE condition when L meets the supplied logarithmic lower bound.The quantization approximates each entry to precision 2^-L, and the proof also checks the normalization conditions.Source: §A.2 · p. 20
  • The proof establishes γ(C0) = 0 by using rank(C0) ≤ 3k while C0 has more than 3k nonzero columns.This yields a nonzero (3k + 1)-sparse vector in the null space, which the proof uses with its chosen set S.Source: §A.2 · p. 20

A.3 Proof of Lemma 5

The proof constructs a deterministic solver from a bounded noise realization and argues that its code length and running time are polynomial. It then applies the hardness result to constrain the solver's success probability.

A.3 Proof of Lemma 5

  • The noise vector is modeled as Gaussian, and the proof defines an event in which its infinity norm is at most μ.This event is used in the noise argument.Source: §A.3 · p. 21
  • A bounded deterministic noise vector can be chosen so the resulting solver follows the same remaining steps as the randomized procedure.The passage states that some realization with ∥w0∥∞ ≤ μ has the required property.Source: §A.3 · p. 21
  • The constructed solver has polynomial code length and polynomial running time.The proof bounds the encoding lengths of X, the fixed vectors, and the bounded noise, and states that the response can be constructed in polynomial time.Source: §A.3 · pp. 21–22
  • The proof invokes Lemma 3 to bound the success probability of any polynomial-complexity solver by 1/h(m).It then uses standard tail bounds and a union bound in the remaining argument.Source: §A.3 · pp. 21–22

A.4 Proof of Lemma 6

The proof compares distributions of response vectors and relates their probability bounds to the estimator's behavior across indices. A counting argument then connects those indices to a subset defined using u⋄.

A.4 Proof of Lemma 6

  • For each index i, u⋄i and the scaled estimator bθi/ρ have the same distribution.The argument counts indices according to whether the estimator falls in B0(k/t), then identifies N with |T|.Source: §A.4 · p. 23
  • The response vectors y′ and y⋄ differ in distribution only in their last n/2 entries.The proof introduces their density functions to analyze the comparison.Source: §A.4 · pp. 22–23
  • The proof uses a density-ratio event and the standard normal CDF to express its probability.The supplied passage identifies the event through a bound on q⋄(y′)/q′(y′).Source: §A.4 · p. 23
  • The proof also uses that ˜ξi and ˜θi differ only in one subvector, by ρu∗, whose norm is at most r.Source: §A.4 · p. 24

A.5 Proof of Lemma 7

The proof compares the densities q′ and q⋄, reuses an earlier probability-bound argument, and applies Markov’s inequality. The supplied passages do not state the resulting bound.

A.5 Proof of Lemma 7

  • The proof introduces q′ and q⋄ as the densities of y′ and y⋄, respectively.Source: §A.5 · p. 24
  • It applies the proof of inequality (41) to establish an upper bound.The passage does not provide the bound's expression.Source: §A.5 · p. 24
  • The proof applies Markov’s inequality to obtain a further bound.The bound itself is not included in the supplied passage.Source: §A.5 · p. 24

B Proof of Proposition 2

The proof compares the truncated and ordinary Lasso errors to establish Proposition 2, then gives Gaussian-matrix singular-value bounds used in Theorem 1(a).

B Proof of Proposition 2

  • Lemma 9 states that the truncated Lasso error is bounded and that the estimator is essentially as good as the non-truncated Lasso.The supplied passage does not include the bound's expression.Source: B Proof of Proposition 2 · p. 25
  • The proposition proof combines the truncated-Lasso bound with the ordinary-Lasso bound obtained from Corollary 2 for the specified λ_n.The resulting claim holds with probability at least 1 − 2e^(−c4k log d).Source: B Proof of Proposition 2 · p. 25
  • When the ordinary Lasso has at most k nonzero entries, truncation leaves it unchanged; otherwise, the proof compares good entries lost with bad entries preserved.The proof uses the truncation's ordering of retained entries and the sparsity of the true parameter.Source: B Proof of Proposition 2 · p. 25

C Singular values of random matrices

  • For an i.i.d. Gaussian design, Lemma 10 gives two singular-value bounds with probability at least 1 − c1 exp(−c2n), assuming n > c0 k log d.The section presents these bounds as background needed for the proof of Theorem 1(a).Source: C Singular values of random matrices · p. 26
Loading 1402.1918v2…