Feature Adaptation for Sparse Linear Regression
Authors: Jonathan Kelner
Frederic Koehler
Raghu Meka
Dhruv Rohatgi
Venue: NeurIPS 2023 spotlight (2023)
Keywords: theory
sparse linear regression
feature adaptation
lasso
TL;DR: We provably generalize Lasso to tolerate a small number of approximate dependencies, via a broad algorithmic framework of feature adaptation.

Abstract: Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaussian $N(0,\Sigma)$, and we seek an estimator with small excess risk. 

If the true signal is $t$-sparse, information-theoretically, it is possible to achieve strong recovery guarantees with only $O(t\log n)$ samples. However, computationally efficient algorithms have sample complexity linear in (some variant of) the *condition number* of $\Sigma$. Classical algorithms such as the Lasso can require significantly more samples than necessary even if there is only a single sparse approximate dependency among the covariates.

We provide a polynomial-time algorithm that, given $\Sigma$, automatically adapts the Lasso to tolerate a small number of approximate dependencies. In particular, we achieve near-optimal sample complexity for constant sparsity and if $\Sigma$ has few ``outlier'' eigenvalues.
Our algorithm fits into a broader framework of *feature adaptation* for sparse linear regression with ill-conditioned covariates. With this framework, we additionally provide the first polynomial-factor improvement over brute-force search for constant sparsity $t$ and arbitrary covariance $\Sigma$.

Feature Adaptation for Sparse Linear Regression
Jonathan A. Kelner" MIT
Frederic Koehler Stanford
Raghu Meka UCLA
Dhruv Rohatgi MIT
Abstract
Sparse linear regression is central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaussian N 2). and seek estimator with small excess risk. If the true signal is t-sparse, information-thert theoretically, it is possible to achieve strong recovery guarantees with only O log n) samples. However, computa- tionally efficient algorithms have sample complexity linear in (some variant of) the condition number of Σ. Classical algorithms such as the Lasso can require significantly
samples than necessary even if there is only single sparse approximate dependency among the covariates.
We provide polynomial-tin algorithm that, given E, automatically adapts the Lasso tolerate small number of approximate dependencies. In particular, we achieve near-optimal sample complexity for constant sparsity and if Σ has few "outlier" eigenvalues. Our algorithm fits into broader framework of feature adaptation for sparse linear regression with ill-conditioned covariates. With this framework, we additionally provide the first polynomial-facee improvement over brute-force search for constant sparsity and arbitrary covariance Σ.
1
Introduction
Sparse linear regression a fundamental problem in high-dimensional statistics. In natural random design formulation of this problem,
given independent and identically distributed samples vector X, 1== where each sample's covariates are drawn from an n-dimensional Gaussian random ((0, Σ), and each response is Y/i (Xe, v²) + & for independent noise & NOO, o2) and a t-sparse ground truth regressor v" E IR"" where f much smaller than n. The goa is to output vector Rn for which the excess risk
(X,, yt }mm
E((Xo, 0) yo)² 0² (0 - -0) (i 1 (
is as small as possible, where (Xu. yo) is an independent sample from the same model.
Without the sparsity assumption, the number of samples needed to achieve small excess risk (say, O(a²)) is linear in the dimension; with O(n) samples, simple and computationally efficient algo- rithms such as ordinary least squares achieve the statistically optimal excess risk O Sparsity
'kelnermmit. edu. This work was supported in part by NSF Large CCF-1565235, NSF Medium CCF- 1955217, and NSF TRIPODS 1740751.
Ifkoehheerstaanord edu. This work supported in part by NSF award CCF-1704417, NSF award 1S-19907744 N. Anari's Sloan Research Fellowship
rraghun@cs.ucl ucla. This work was supported in part by NSF CAREER Award CCF-1553605 and
NSF Small CCF-2007682
$ sarohatgi@mit edu. This work was supported by a U.S. DoD NDSEG Fellowship.
"More generally, from learning theory perspective, could consider arbitrary improper learner out- putting a function f(Xu), rather than specifically learning linear function (Xa, 0). At least when Σ is known, there is no advantage as we can always project / onto the space of linear functions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

allows for a significant statistical improvement: ignoring computational efficiency, it is well known that there is an estimator with excess risk O( o² e'tlogg ") as long as m = [t log n) e.. Theorem 4.1 in (23).
m
The catch is that computing this estimator involves brute-force search over (?) possibilities (i.e., the possible supports for v²). At first glance, this combinatorial search may seem unavoidable if wish take advantage of sparsity. Indeed, similar problems are notoriously difficult: the only non-trivial algorithms for e.g., learning t-sparse parities with noise still require n no(()) time (29 37..
However, it is a celebrated fact that for sparse linear regression, computationally efficient methods such Lasso and Orthogonal Matching Pursuit avoid this combinatorial search and still achieve very strong theoretical guarantees under conditions such as the Restricted Isometry Property (see e.g. 10
In the random design setting we consider, the Lasso is known to achieve optimal statistical rates (up to constants) when the covariance matrix Σ is well-conditioned [32 46
What about when Σ is ill-conditioned? In contrast with the statistically optimal estimator, Lasso and its cousins provably require sample complexity scaling with (some variant of) the condition number of 2 (see c.g. Theorem 14 in [38 Theorem 6.5 in (23). And with few exceptions (c.g.. in some settings with special graphical structure (23)) there has been little progress on designing new efficient algorithms for sparse linear regression with ill-conditioned Σ (see Section 4 for further discussion). For general covariance Σ. no algorithm is even known that can achieve sample complexity f(t) 1- (for an arbitrary function f) without brute-force search.
A computationally efficient algorithm that approaches the optimal statistical rate for arbitrary Σ might be too much to hope for. While no computational lower bounds are known, even in restricted computational models such as the Statistical Query model related worst-case problem of find- ing a t-sparse solution to system of linear equations requires (t)))) time under standard complexity assumptions [15]. So it is plausible, though not certain, that some assumptions on Σ are neces- sary. In this work- inspired by long tradition (in random matrix theory, statistics, graph theory, and other areas) of studying matrices with spectrum that is split between a large "bulk" and small number of outlier "spike" eigenvalues [28 39
we identify a broad generalization of the standard well-conditionedness assumption, under which brute-force search can still be avoided.
1.1 Beyond well-conditioned E
Say that Σ has eigenvalues A S .... I An. and that the sparsity t is a constant Then standard bounds for Lasso require sample complexity (An/A1) Olog But if the covariates contain even a single approximate linear dependency, then An/Ai may be arbitrarily large. Moreover, if the dependency is sparse (e.g. two covariates are highly correlated), then there is natural choice of v" for which Lasso provably fails (see Theorem 6.5 of (23)). Indeed, this phenomenon is not just a limitation of the analysis: Lasso fails empirically as well, even for very small t (see Figure 2 in Appendix H for simple example with t = 3).
Such dependencies arise in applications ranging from finance (e.g., where some pairs of stocks or ETFs may be highly correlated, and an investor may be interested in the differences) to genomic data (where functionally related genes may have highly correlated expression patterns). Two-sparse dependencies can be directly identified by looking at the covariance matrix; see Section 4 for some discussion of previous research in this direction. But as / increases, naive methods for identifying L- sparse dependencies quickly become computationally intractable. With domain knowledge it may be possible to manually identify and correct such dependencies, but this process would also be time-consuming. Thus, we ask the following question: instead of assuming that An/A1 is bounded, suppose that there are constants de and d, so that An / / 1 is bounded, i.c. the spectrum of
Σ has only de outliers at the low end, and only dn outliers at the high end. Can we still design an comeleeooopeii
algorithm that achieves sample complexity Ologgn without resorting to brute-force search?
Main result. We give positive answer: an algorithm for sparse linear regression that is both computationally and statistically efficient for covariance matrices with a small number of "outlier"
'There are lower bounds for family of regression estimators with coordinate separable regularization 44 and a family of ppreconditioned Lasso" estimators 23 24).
Note that for moderate-shne sized datasets (e.g. n = 1000), brute-force search is infeasible even for as small
four five.

---

eigenvalues. In particular, this means we can handle few approximate dependencies among the covariates (quantified by the number of eigenvalues below a threshold). In comparison, Lasso and other classical algorithms cannot tolerate even single sparse approximate dependency. Our main algorithmic result is the following:
Theorem 1.1. Let n. t. de, dr, L E N and 0,8 > O. Let Σ R= be positive semi-definite matrix with (non-negative) eigenvalues x I .... ..... An- Let v- E R" be any t-sparse vector. Let (X,, y be independent with X; (0, Σ) and y (X,, v*) Eo where ~ (N0,0 o2),
Let Deff" == t(An-da/ /dd,+1) log(nL/8) + d + dn. Given E, t, de, 8, and v:) there is an estimator E IR." that has excess risk
o F + 1-2-.110011
|1 - 1 11 S
m
with probability at least 1 - 8, so long poly(n).
((n.p.)) Moreover, è can be computed in time
Specifically, taking ~ log(m || /o"), the time complexity is dominated by L eigendecom- positions and L calls to a Lasso program, for overall runtime Ö(n²) (see Algorithm 2 This is substantially faster than the brute-force method (which takes (nz)) time) even for small values of
The excess risk decays rate Ó(oPnar/m) (hiding the logarithmic factor), which is the statis- tically optimal rate of ((o2t/m) so long as net small, i.e. t small and only a few eigenvalues lie outside constant-factor range. In our analysis, we prove that the standard Lasso estimator can already tolerate a few large eigenvalues few small eigenvalues, which turns out to be much trickier. Notice that when de d, = O we recover standard Lasso guarantees up to the factor of L; thus, Theorem morally represents generalization of classical results.
the main algorithmic innovation is needed to tolerate
We also show how to achieve different trade-off between time and samples, eliminating the depen- dence on de in sample complexity at the cost of larger runtime:
Theorem 1.2. In the setting of Theorem 1.1 let n'dr := t(An-da/
\ /on-dd//de-11 log(nL/8) + log(t) + dn. Given Σ, t, de, 5, and (X,, y: there an estimator E TR." that has excess risk
o o'nn'
v0 SO
+ +22--110011
with probability at least 1 - 6, so long as m 2 D) Moreover, é can be computed time poly(n, m, d',, tt?).
Discussion & limitations. We discuss two limitations of the above results. First, both results incur exponential dependence the sparsity / (in the sample complexity for Theorem 1.1 and the runtime for Theorem 1.2). which may be suboptimal. For Theorem T.T we remark that in practice the algorithm may not suffer this dependence (see e.g. Figure []. and is possible that the analysis can be tightened. For Theorem 1.2] we emphasize that the runtime is still fundamentally different than brute-force search: in particular, it's
tractable in and de.
Second, both results require that E is known. Thus, they are only applicable in settings where we estimate Σ accurately because a large amount of unlabelled
either have priori knowledge, data available. At a high level, this limitation is due to the need to compute the eigendecomposition of Σ, which cannot be approximated from the empirical covariance of small number of samples.
For simplicity, we have stated our results in terms of Gaussian covariates and noise, but this is not a fundamental limitation. We expect it is possible to prove similar results in the sub- lub-Gaussian case at the cost of making the proof longer - for instance, by building upon the techniques from 25 and related works.
Pseudocode & simulation. See Algorithm | for complete pseudocode of AdaptedBP (), a sim- plification of the method for the noiseless setting = O. In Figure | we show that AdaptedBP () significantly outperforms standard Basis Pursuit (i.e. Lasso for noiseless data (7) on a simple ex- ample with = 1000 variables, de 10 sparse approximate dependencies, and ground truth
3

---

Algorithm 1: Adapted BP for sparse linear regression with few outlier eigenvalues
Procedure FindHeavyyCorddnatees (U1,...,, (4
computes an orthonormalization of 01 01y...,0 ag f -RAN-SCUMIDDT(IL.....
/*
return { [x]] ((a,))) 2 a²}
Procedure IterativePeelling (E, d,
Compute eigendecompositiinn Σ Au=
P Li=d4 u
K; f {i [n] Pa < <1-1/(9f)}
for j to 1 do
[p(K;) FindlearyCordinatess (PP; Kj).1/(6t))
K5-1 < K2 (I))K))
return Ko
Procedure AdaptedBP (E, d, t. (1)
S ---rraaaiveePelinn[[. d, d.
return E argmin Σ igs 1i
Adupted SP
1.75
1.50
Facoss rld
1.00
0.75
100
200
300
400
500
Numbar bummples
Figure 1: Basis Pursuit (BP) versus Adapted BP in a simple synthetic example with n = 1000 covariates. The x-axis is the number of samples. The y-axis is the out-of-sample prediction error (averaged over 10 independent runs, and error bars indicate the standard deviation).
regressor with sparsity 13. The covariates X1:1000 are independent N(0, 1) except for 10 disjoint triplets ((X,, X,+1, X2+2) : 1,., 28), each of which has joint distribution
X, Ze; X1+1 Z; 0.4Z++1: X Z441 + 0.4Z
where Zi, Zi+1, Zi42 N(, 1) are independent. The (noiseless) responses are y 6.25(X: X2) + 2.5X3 +
1 1000 X,. See Appendix for implementation details.
Vio
1.2
Organization
In Section 2 we give overview of the proofs of Theorem 1.1 and 1.2 (the complete proofs and full algorithm pseudocode are given in Appendix [C. Section we discuss our other results obtained via feature adaptation. Section 4 covers related work.
Proof techniques
We obtain Theorems [.I and as outcomes flexible algorithmic approach for tackling sparse linear regression with ill conditioned covariates: feature adaptation. As pre-processing step, adapt

---

or augment the covariates with additional features (i.e. well-chosen linear combinations of the co- variates). Then, to predict the responses, apply & -reeulaariee regression (Lasso) over the new set of features rather than the original covariates. In other words, we algorithmically change the dictionary (set of features) used the Lasso regression. See Section [ for a comparison to past approaches.
We start by explaining the goals of feature adaptation for general ), and then show how we achieve those desiderata when > has few outlier eigenvalues. More precisely, the main technical difficulty is in dealing with the small cigenvalues, so in this proof overview we focus on the case where the only outliers are small eigenvalues. Complete proofs of Theorems and are in Appendix C
2.1 What makes a good dictionary: the view from weak learning
Obviously, the feature adaptation approach generalizes Lasso. Surprisingly, even though the sample complexity of the standard Lasso estimator is thoroughly understood, the basic question of whether for every covariate distribution (i.e. every Σ) there exists good dictionary remains wide-open. To crystallize the power of feature adaptation, we introduce the following notion of a "good" dictionary. We suggest considering the simplified setting of a-weak learning, where the goal just to find some é so that the predictions (X, 6) are a-correlated with the ground truth (X, x") when X ~ (O, E) Moreover, we focus first on the existential question (rather than the algorithmic question of finding the dictionary). We will return to the setting of Theorems 1.1 and 1.2 later. For now, in the weak learning setting, a good dictionary (when the covariate distribution is N(0, E)) is one that satisfies the following covering property, but is not too large:
Definition 2.1. Let Σ E Rax= be positive semi-definite matrix and let a > 0. A set (Di....,Dy, Dr) C I is a (t, -iciiiionn for Σ if for every t-sparse u E R", there is some E [N] with
(ev, Di)x 2 a ||0|| |
where we define (ar, u)5; := x T Ey and | == x. T Ex for any x. y E RR. Let Ne, (E) be the size of the smallest (t, a diciioooon.
The relevance of the covering number (E) is quite simple: given a (t,, ax--dictionary D for Σ, and given samples (X,, 3 the weak learning algorithm can simply output the vector é 'D that maximizes the empirical correlation between the predictions (X,, 6) and the responses ys. So long as there are enough samples for empirical correlations to concentrate, Definition 2.1 guarantees success. Formally, allowing for preprocessing time to compute the dictionary, O(ar)weakk learning possible in time Ni,a(E) poly(n), with O(a 2 log Ni,a(E) samples (Proposition A.5
Hypothetically, bounding Ni, may not be necessary to develop an efficient sparse linear regres- sion algorithm. However, all assumptions Σ that are currently known to enable efficient sparse linear regression also immediately imply bounds on Ne,,. (see Appendix G For example, when Σ is well-conditioned, the standard basis is good dictionary of size n (Fact]A.4).
In contrast, the only known bounds for arbitrary Σ (until the present work) are Ne, st (7) (the brute-force dictionary, which includes a E-orthonormal basis for every set of covariates) and Ne.1/y1(2) < n (a E-orthonormal basis for all covariates, which doesn't 't take advantage of sparsity and corresponds to algorithms such as Ordinary Least Squares). Thus, the following basic question when can we improve upon these trivial bounds seems central to understanding when brute-force search can be avoided in sparse linear regression:
Question 2.2. How large is Nr. (E) for an arbitrary positive semi-definite Σ E Raxn? Are there natural families of ill-conditioned E (and functions f. for
for which Ne,1/ (E) g() (n)y
2.2 Constructing a good dictionary when Σ has few small eigenvalues
We now address Question 2 in the setting where Σ has small number of eigenvalues that much smaller than An. In this setting, the standard basis may not be a good dictionary. For example, if two covariates are highly correlated, their difference may not be correlated with any of them. Nonetheless, we can prove the following covering number bound:
Theorem 2.3. Let n, t, d E N. Let Σ E Raax be a positive semi-definite matrix with eigervalues t S ... < An. Then Ni, (E) < ((7t)22 26 +t + n, where a = 7/i 1 / /
5

---

In particular, when t = O(1) and Σ is well-conditioned except for ((1) outliers λ1..... Ad, we get linear-size dictionary just as in the case where Σ is well-conditioned. In fact, the desired (I, o))ddictionary can be constructed efficiently. Our key lemma shows that when E has few small eigenvalues, there a small subset of covariates that "causes" all of the sparse approximate depen- dencies in the sense that the l2 norm of any sparse vector, excluding the mass on the subset, can be upper bounded in terms of the Enmorm of the vector. Moreover, there is an efficient algorithm that finds superset of these covariates. Formally, we prove the following:
Lemma 2.4. Let n. f, E N. Let E E IR be a positive semi-definite matrix with eigenvalues A1 S... S An- Given E, d, and t, there is polynomial-time algorithm IterativePeeling producing a set S S [n] with the following guarantees:
(a) For every I-sparse E IR"" it holds that | 33x441 |1l||
(b) |S| < (71)2t+1d.
Once this set S has been found, the dictionary is simply the standard basis (E1,..., J. together with a E-orthonormal basis for every set of covariates in S. By guarantee (a), we can prove that every t-sparse vector correlates with some element of this dictionary under the i-inner product. By guarantee (b), the dictionary is much smaller than the brute-force dictionary that contains a basis for all (") sets of covariates. Together, this gives an algorithmic proof for Theorem 2.3
Intuition for IterativePeeling() We compute the set S via a new iterative method which leverages knowledge of the small eigenspaces of Σ. See Algorithm I for the pseudocode. To com- pute S, the algorithm IterativePeeling projects onto the subspace spanned by the top n d eigenvectors of Σ. Starting with the set of coordinates that correlate with ker( P), the procedure then iteratively grows S in such way that at each step, a new participant of each approximate sparse dependency discovered. but S does not become too much larger.
first computes the orthogonal projection matrix P that
The intuition is as follows: a preliminary attempt, could identify all O(d) coordinates that correlate (with respect to the standard inner product) with the lowest d eigenspaces of Σ. If e.g. the covariates have sparse dependency
X2 0,
then ker Σ contains the vector e1 + 62, so the coordinates fei, e2) will be correctly discovered. Unfortunately, if Σ contains a more complex sparse dependency such as
eX1
X3 X1=
where e > 0 is very small, then this heuristic will discover (e1, but miss {e3, e4)- For this example, the solution is to notice that e3 and e₁ do correlate with the subspace spanned by ker ker(2)) (ei,e2) e (which contains + e4). In general, if S is the set of coordinates discovered thus far, then by finding basis vectors that correlate with an appropriate subspace (of dimension (S)), we can efficiently augment S with at least one new coordinate from each t-sparse approximate dependency, without making S bigger by more than factor of O(t). Iterating this augmentation times therefore provably identifies all problematic coordinates.
most
To formalize this intuition, the following lemma will be needed bound how much S grows each iteration; it shows that the number of coordinates that correlate with a low-dimensional subspace is not too large (proof deferred to Appendix B):
Lemma 2.5. Let V C RR be subspace with d == dim V. For some a > O define
J2 2 a
S
sup zEV
|
Then |S] S d/a2. Moreover, given a set of vectors that span V, we can compute S in time poly (n).
We also define the set of vectors v that have unusually large norm outside a set S, compared to VeT Pe, which is the distance from to the subspace spanned by the bottom d eigenvectors of Σ: Definition 2.6. For any matrix E B and subset 5 C [n], define Wr.s == {u E R ||us- >
PPT.

---

We then formalize the guarantee of each iteration of Iterative IterativePeeling() as follows: Lemma 2.7. Let n,t I and let P be an orthogonal projection matrix. Suppose T
and K = [n] satisfy
for (a) Pa 2 1- 19( for all i & K,
(b) supp(v) \\ K| S T for every V E Bu(l)nWp..
Then there exists set (K) with [Ip(K) S 36t||K such that [supp(e) \ (Ip(K) U <
for all e E Bo(l) n Wp.k. Moreover, given P. K, and I, we can compute Ip(K) in time poly(n).
Proof sketch. We define the set
2 1/(6t) } ||0||
|ral
Ip(K): E \ K:
sup [Espan( (Pe
is clear from Lemma B.2 (applied with parameters V := span{Pe; : E K} and a == 1/(6t)) that (I)) < 36t K and that (K) can be computed in time poly(n). It remains to show that [9r(v) \ (Ip (K) U KO] S 7 - 1 for all v E (t).).
Consider any E (t) (a(t)/Pp. Wp..- Then ||xx=l12 P It's sufficient to show that Ip(K) contains some j E supp(v) \ K, that there some j E supp(v) \ K such that e; correlates with span i E KJ. We accomplish this by showing that uK= correlates with Pex Liek U,P.
At high level, the reason for this is that UK- is close to Puge (since P. e, for i K9), and Pv = PUx + Pug= = is much smaller than Puge zo Uke, so Puk and Puge must be highly correlated. See Appendix B for the full proof.
We can now complete the proof of Lemma 2.4 by repeatedly invoking Lemma B.4
Proof of Lemma 2.4. Let Σ = Σ \nniu, be the eigendecomposition of Σ, and let P
E u, be the projection onto the top d eigenspaces of Σ. Set K2 {i [n] : Pa <
1- 1-1/(9;²)) Because tr(P)= = n and P.. S for all [n], it must be that [Ke]] < 96 d. Also, for any v E Bo()) I WP.K, we have trivially by t-sparsity that |supp(v) \ Kil S. t.
Define K2-1 to be K, (K,, where (K(K)) is defined in Lemma B.4 we have the guarantees that K,-1| I it holds that WP.K,-, S Wp,k, and thus (GP(v) K2 < t - for all E Bu()) n WP..K..- K,-1- This
and (9p(v) Kg| S 1-1 for all u E (t P.K,. Since K 2 K₁,
Moreover, since K₃-1 Ke, it obviously holds that P.: 2 - 1/((2) for all means we can apply Lemma B.4 with := - 1 and K == K,-1 and so iteratively define sets K C... C K2 C Ko C in the same way. In the end, obtain the set Ko S [n] with [Ko S dfd + 36 and supp(v) C Ko for all e E (t Wp... The latter guarantee means that in fact (I) Wp,Ko 0. So for any I-sparse u E R" it holds that
| l12 < 3300 Po SusA 3 VoT Ev where the last inequality holds since \ P 2 E.
2.3 Beyond weak learning
So far, have sketched proof that if Σ has few outlier cigenvalues, then there is an efficient algorithm to compute a good dictionary (as in 2..3rem This gives an efficient a-weak learning algorithm (via Proposition A.5). However, our ultimate goal is to find a regressor i with prediction error going to 0 as the number of samples increases. Definition 2.1 is not strong enough to ensure
this However, it turns out that the dictionary constructed in Theorem 2.3 in fact satisfies stronger guarantee that is sufficient to achieve vanishing prediction error:
Moreover, standard notions boosting weak learners (e.g. in distribution free classification) do not apply this setting.
See Lemma A.3 for proof that the L rerresessettttoon property implies the (t, dicciiooy property.
7

---

Definition 2.8. Let Σ E R be a positive semi-defings matrix and let t, B > 0. A set (Di....: Dx) R is a (t. reppessettnnnn for Σ if for any t-sparse E I² there some a OER" with = Ei-1 D; and E lasl Dills S B ||e||s:-
With this definition in hand, we can actually prove the following strengthening of Theorem 2.3
Lemma 2.9. Let n, n,t,d N. Let Σ E Rax be a positive semi-definite matrix with eigen- values X1 S I An. Then E has a (t. (trVet//nnAAn))-rerrerreeeaaa rerreeesenttiinn DD of size at most + +1(777)) + Moreover, D can be computed in time (0(t)) d' poly(n).
Proof sketch. Let be the output of IterativePeeling (2, d, t). The dictionary D consists of the standard basis, together with Eoorthogonal basis for each set of coordinates from S. The bound on [D] comes from the guarantee |S| I (7t)2t+1d. For any t-sparse vector E IR", we know that øg is efficiently represented by the standard basis (because Theorem B.I guarantees that ||us=lly l|2 x 0 [!lly)), and vy efficiently represented by one of the E-orthonormal bases. See Appendix B for the full proof.
Why the above guarantee useful? If each Dj is normalized to unit E-norm, then the condition of (t, -rppeeeerrrlslllllliiiy is equivalent to ||a||| B || That is, with respect to the new set of features, the regressor a has bounded l norm. Thus, if we apply the Lasso with set of features that is (t, (.B))-(--rerreeentttiin for E, then standard "slow rate" guarantees hold (proof in Section (A:
Proposition 2.10. Let m, N,t E N and B > O. Let Σ E ggxx be positive semi-definite matrix and let D be a (t, ( represeepprssnnntooonn of size N for E, normalized so that |/lll = for all v E D. Fix a sparse vector o" R", let X1,.. Xm N0, Σ) be independent and let y (X,, +& where & ~ (0, d²). For any >> O, define
v argmin WERN: s|ll,,
|XDw -y1/
where D E R is the matrix with columns comprising the elements of DD and X E Rmxx is the matrix with rows X1 X1...., Xm- So long as m (log((/0)) and I| 1l [R/2, RJ. it holds with probability at least - 8 that
log(2n/0)
o² log((4/8)
Ba
I 2 log(n)
Diu w" 0 B 110"
1x o
Combining Proposition with with Lemma 2.9 shows that there is an algorithm with time complexity log(n) log(d)) for finding regressor
(o (oly(n) and sample complexity O (Pooy((((An/Aeee
with squared prediction error o(o² + ||0 |1 12)). This is simplified version of Theorem 1.2 The full proof involves additional technical details (e.g. more careful analysis to take care of large eigenvalues. and to avoid needing an estimate R for [[=))lx)) but the above exposition contains the
central ideas. Theorem 1.1 similarly computes the set S from Lemma 2.4 but uses it to construct a
different dictionary: the standard basis, plus E-orthonormal basis for S See Appendix C for the full proofs and pseudocode.
3 Additional Results
We now return to Question 2.2 and ask whether there are other families of ill-conditioned Σ for which we can prove non-trivial bounds on Ne,a(
First, we ask what can be shown for arbitrary covariance matrices. We prove that every covari- ance matrix Σ satisfies non-trivial bound N2 Jogn)) (E) < O In fact, building on tools from computational geometry, we show the stronger result that Σ has (t, O(13/2 log --11 representation that of size O(n'-1/2) that is computable from samples in time (0((t))))) for
10 More precisely, the algorithm just skips regularizing S, which is morally equivalent. As it is simpler to implement, that is shown in Algorithm [ and analyzed for the proofs.
8

---

any constant t >> (Theorem D.5). As a corollary. we provide the first sparse linear regression algo- rithm with time complexity that is a polynomial factor better than brute force, and with near-optimal sample complexity, for any constant and arbitrary E (proof in Section D):
Theorem 3.1. Let n, n,m, I, B E N and σ O, and let Σ R be a positive-definite matrix. Let lg E 1B2 B). Suppose m 2 92( log Let (Xi,9)) be independent samples where X; ~ [(0 Σ) and yi = (X,, w²) + NN0 Then there is an O 1/2 +nt-(((/t)) log O(1) n)-time algorithm that, given (X,, )i B, and o², produces an estimate i E IR" satisfying, with probability o(1),
w" E In" be I-sparse, and suppose ||w"|ly
||00 w w'll S
SŌ o² Vm
o
11000 11I 69/2
| 1
v'm
77
Second, one goal is to improve "sample complexity" (i.e. obtain a without dependence on condition number) without paying too much in "time complexity" (i.e. retain bounds on NNi that are better than n²). To this end, we prove that the dependence on k in the correlation level (see Fact A.4 can actually be replaced by dependence
"
K. in the dictionary size (proof in Appendix [E]:
Theorem 3.2. Let n, E N. Let E Ruxa be a poxitive-definite matrix with condition rumber k. Then N11133+1 (E) < 20(2) x 21+1 n2.
In particular, for any constant 1/c, our result shows that there is nearly-linear size dictionary with constant correlations even for covariance matrices with polynomially-lare condition number 120000 While we not currently aware of an efficient algorithm for computing the dictionary, the above bound nonetheless raises the interesting possibility that there may be a sample-efficien and computationalll--fficienn weak learning algorithm under super-constant bound on
4 Related work
Dealing with correlated covariates. There is considerable work on improving the performance of
Lasso in situations where some clusters of covariates are highly correlated [47 19 2 42
21 [2 27).
These methods can work well for two-sparse dependencies, but generally do not work as well for higher-order dependencies hence they cannot be used to prove our main result. The approach of 2 is perhaps the closest in spirit to ours. They perform agglomerative clustering of correlated covariates, orthonormalize the clusters with respect to Σ. and apply Lasso (or solve essentially cquivalent group Lasso problem). This method fails, for example, when there is a single three- sparse dependency, and the remaining covariates have some mild correlations. Depending on the correlation threshold, their method will either aggressively merge all covariates into a single cluster, or fail to merge the dependent covariates.
Feature adaptation and preconditioning Generalizations of Lasso via a preliminary change-of- basis (or explicitly altering the regularization term) have been studied in the past, but largely not to solve sparse linear regression per se; instead the goal has been using & regularization to encourage other structural properties such as piecewise continuity (e.g. in the "fused lasso", see 35 36 20
for some more examples). An exception recent work showing that a "sparse preconditioning" step can enable Lasso to be statistically efficient for sparse lincar regression when the covariates have a certain Markovian structure [23]. Our notion of feature adaptation via dictionaries generalizes sparse preconditioning, which corresponds to choosing non-standard basis in which Σ becomes well-conditioned and the sparsity of the signal is preserved.
Statistical query (SQ) model; sparse halfspaces. From the complexity standpoint, Ni. (E) is covering number and therefore closely corresponds to a packing number Pt.cx (2) (see Section A. for the definition). This packing number is essentially the (correlational) statistical dimension, which governs the complexity of sparse linear regression with covariates from (O, Σ) in the (cor- relational) SQ model (see e.g. [4 for exposition of this model). Whereas strong n ((t)) SQ lower bounds are known for related problems such as sparse parities with noise 229. no non-trivial (i.e. super-linear) lower bounds are known for sparse linear regression. Relatedly, in a COLT open prob- lem, Feldman asked whether any non-trivial bounds can be shown for the complexity of weak learn- ing sparse halfspaces in the SQ model [.. Our results also yield improved bounds for weakly SQ-learning sparse halfspaces over certain families of multivariate Gaussian distributions.

---

Improving brute-force for arbitrary Σ. Several prior works have suggested improvements on
brute-force search for variants of t-sparse linear regression [[8 16 31 6]. However, all of these have limitations preventing their application to the general setting we address in Theorem 3.1 Specifically, [8 requires Q(n²) preprocessing time on the covariates; [16 [1 require noiseless
responses; and [6] has time complexity scaling with log" (since our random-desigt setting neces- sitates m 2 (tt log n),, their algorithm has time complexity much larger than n²).
References
[1] Peter Bickel, Ya'acor acov Ritov, Alexandre Tsybakov, et al. Simultancous analysis of lasso and dantzig selector. The Annals of statistics, 37(4):
2009.
[2] Peter Bühlmann, Philipp Rütimann, Sara Van De Geer, and Cun-Hui Zhang. Correlated vari- ables regression: clustering and sparse estimation. Journal of Statistical Planning and Inference, 143(11):1835-885 2013.
[3] Emmanuel Candes, Terence Tao, al. The dantzig selector: Statistical estimation when p is much larger than n. Amnal of statistics, 35(6) 2007.
[4] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incom- plete and inaccurate measurements. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute of Mathematical Sciences, 59(8): ((8)):207-122,) 2006.
[5] Emmanuel J Candes and Terence Tao. Decoding by linear programming. IEEE transactions on information theory, ((12)):4033442)) 2005.
[6] Jean Cardinal and Aurélien Ooms. Algorithms for approximate sparse regression and nearest induced hulls. Journal of Computational Geometry, 13(1):377-398, 2022.
[7] Shaobing Chen and David Donoho. Basis pursuit. In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers, volume I, pages 41-44. IEEE, 1994.
[8] Arnak S Dalalyan, Mohamed Hebiri, Johannes Lederer, et al. On the prediction performance of the lasso. Bernoulli, 23(1):552-555 2017.
[9] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. arXiv preprint arXiv:1102.3975. 2011.
[10] David L Donoho and Philip B Stark. Uncertainty principles and signal recovery. SIAM Journal on Applied Mathematics, 49(3):906 993-93,, 1989.
[11] Vitaly Feldman. Open problem: The statistical query complexity of learning sparse halfspaces.
In Conference on Learning Theory, pages 1283-1289. PMLR, 2014.
[12] Mario Figueiredo and Robert Nowak. Ordered weighted 11 regularized regression with strongly correlated covariates: Theoretical aspects. In Artificial Intelligence and Statistics, pages 930- 938. PMLR, 2016.
[13] Dean P Foster and Edward I George. The risk inflation criterion for multiple regression. The Annals of Statistics, pages 1947-1975, 1994.
[14] Surbhi Goel, Aravind Gollakota. Zhihan Jin, Sushrut Karmalkar, and Adam Klivans. Super- polynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.
[15] Aparna Gupte and Vinod Vaikuntanathan. The fine-grained hardness of sparse linear regres- sion. arXiv preprint wxXiv22106003133 2021.
[16] Aparna Ajit Gupte and Kerri Lu. Fine-grained complexity of sparse linear regression. 2020.
[17] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
[18] Sariel Har-Peled, Piotr Indyk, and Sepideh Mahabadi. Approximate sparse linear regression. In 45th International Colloquium on Automata. Languages, and Programming (ICALP 2018). fuer Informatik, 2018.
Schloss Beassuhhl-eebnni-Zeeene
[19] Jim C Huang and Nebojsa Jojic. Variable selection through correlation sifting. In RECOMB, volume 6577, pages 106-123. Springer, 2011.
10

---

[20] Jan- Christian Hütter and Philippe Rigollet. Optimal rates for total variation denoising. In Conference on Learning Theory, pages 1115-1146. PMLR, 2016.
[21] Jinzhu Jia, Karl Rohe, et al. Preconditioning the lasso for sign consistency. Electronic Journal of Statistics, 9():1150-1172, 2015.
[22] Jonathan Kelner, Frederie Koehler, Raghu Meka, and Ankur Moitra. Learning some popu- lar gaussian graphical models without condition number bounds. In Proceedings of Neural Information Processing Systems (NeurIPS), 2020.
[23] Jonathan Kelner, Frederic Koehler, Raghu Meka, and Dhruv Rohatgi. On the power of pre- conditioning in sparse linear regression. 62nd Anmual IEEE Symposium on Foundations of Computer Science, 2021.
[24] Jonathan A Kelner, Frederic Koehler, Raghu Mcka, and Dhruv Rohatgi. Distributional hard- ness against preconditioned lasso via erasure-robust designs. arXiv preprint arXiv:2203.02822 2022.
[25] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper and minimax bounds. arXiv preprint urXiv:1305: 30...025..5... 2013.
[26] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Sympo- sium on Foundations of Computer Science, pages 1049-1065. IEEE, 2015.
[27] Yuan Li, Benjamin Mark, Garvesh Raskutti, and Rebecca Willett. Graph-based regularization for regression problems with highly-correlated designs. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 740-742. IEEE, 2018.
[28] Shahar Mendelson et al. On the performance of kernel classes. 2003.
[29] Elchanan Mossel, Ryan O' O'Donell, and Rocco Servedio. Learning juntas. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 206-212, 2003.
[30] Wolfgang Mulzer, Huy L Nguyên, Paul Seiferth, and Yannik Stein. Approximate k-flat nearest neighbor search. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 783-792, 2015.
[31] Eric Price, Sandeep Silwal, and Samson Zhou, Hardness and algorithms for robust and sparse optimization. In International Conference on Machine Learning, pages 17944. PMLR, 2022.
[32] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Restricted eigenvalue properties for correlated gaussian designs. The Journal of Machine Learning Research, 11:2241-2259, 2010.
[33] Phillippe Rigollet and Ch-rChhsitaan Hütter. High dimensional statistics. Lecture notes for course 185997, 813:814, 2015.
[34] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with smooth loss. arXiv preprint arXiv:1009.388 (8966 2010.
[35] Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and smoothness via the fused lasso. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 6111))11-108 2005.
[36] Ryan Tibshirani and Jonathan Taylor. The solution path of the generalized lasso. The annals of statistics, 3935)113351137) 2011.
[37] Gregory Valiant. Finding correlations in subquadratic time, with applications to learning par- ities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11-20. IEEE, 2012.
[38] Sara Van De Geer. On tight bounds for the lasso. Journal of Machine Learning Research, 19:46, 2018.
[39] Sara A Van de Geer. Empirical Processes in M-estimation, volume 6. Cambridge university press, 2000.
[40] Sara A Van De Geer, Peter Bühlmann, et al. On the conditions used to prove oracle results for the lasso. Electronic Journal of Statistics, 3: 160-1392, 2009.
[41] Roman Vershynin. High-dimensional probability: An introduction with applications data science, volume 47. Cambridge university press, 2018

---

[42] Fabian L Wauthier, Nebojsa Jojic, and Michael Jordan. A comparative framework for precon- ditioned lasso algorithms. Advances in Neural Information Processing Systems, 26:1061-1069, 2013.
[43] Tong Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural Computation, 1709:20777-0988, 2005.
[44] Yuchen Zhang, Martin J Wainwright, Michael Jordan, al. Optimal prediction for sparse linear models? lower bounds for coordinate-scparable m-estimators. Electronic Journal of Statistics, 11(1):752-799, 2017.
[45] Lijia Zhou, Frederic Koehler, Danica J Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization linear regression. arXiv preprint arXiv:21 2.. 044400, 2021.
[46] Shuheng Zhou. Restricted eigenvalue conditions on subgaussian random matrices. arXiv preprint arXiv:0912.4044 2009.
[47] Hui Zou and Trevor Hastie. Regularization and variable selection via the clastic net. Journal of the royal statistical society: series B (statistical methodology), 67(2):001-320, 2005.
12

---

A Preliminaries
Throughout, use the following standard notation. For positive integers n, N, write A m n to denote a matrix with m rows, n columns, and real-valued entries. The standard inner product R" is denoted (u, == u." u'u. For positive semi-definite matrix E
define
the >-innerr product on IK by (u, u), = Ev and the E-norm by ||u||s - V(u, u)g. For n E N (made clear by context) we let eI,...,f E In be the standard basis vectors e4 := 1[i = i]. For a vector R" and set S [n]] we write us to denote the restriction of coordinates in S. For symmetric matrices A, B
we write A = B to denote that B A is positive semi-definite.
A.1 Covering, packing, and é e-rrppreeetaability
We previously defined the covering number of t-sparse vectors with respect to covariance matrix E. We next define the packing number (i.e. correlational statistical dimension) and & f1-representability, and discuss the connections between these quantities well as their algorithmic implications.
Definition A.1. Let E n x n be a positive semi-definite matrix and let l, > 0. A set (Ui,..., UN) C R is (4, a:) -racking for Σ if every ei is (-sparse, and
Ke,, uy)=l < a || |lylll
for all i,j [N] with * j. The (correlational) statistical dimension of t-sparse vectors with maximum correlation a, under the Viinner product, is denoted (2)) and defined the size of the largest (t, a--pacinnn.
We will make use of the following connections between packing, covering, and é Ei-representability
Lemma A.2 (Covering + packing), For any positive semi-definite matrix Σ and t, 0, it holds that (a² (o)/33)Proom (2) I (Z) I (V)
Proof. First inequality. Let (D....., Dx) be any maximum-size (t, a. a2/22)-packing Since the D,'s are all I-sparse, each must be correlated with some element of (t,, a -idctiiiioo Thus, it suffices to show that for any E R", the set S(v) = (i E [N] [D; v)sl 2 a | |i [|vlls has size [S()) s 3/a?. Indeed, for any i,j E S(v) with A j. we have by the definition of packing that
(D,, D/S D:
2 v, Dj - (D,, u/g
(D,, u/ (D,
= (D,,
|
||0| 2
1
E
< 2
Dills 1D
For each i E S(v) define R2 = De- (Di, u//u// ||0| Then
R
(Ra, R3Y S (S(x) ((())((())))) -1) - a² 1Ry1s
0
Σ
= [S())) +
R
|R
(ES(O)
where the last inequality uses the bound | D, Dills-- Rearranging gives [S(b) - 1 (2/a²).
Second inequality. Let (D)...., Dx) be any maximal (t, ppacking Then for any 1-sparse
Ra maximality implies that there must be some E [N] with (D;, u)xzl 2 a Di ||
So (D....,,Dy is also a (t, ar) -diciioiona
Lemma A.3 (6 reppreseeenatoo and let 1, > If (Di...., Dx) RD (1, By-4 11-11-representation for E, then it is also (t, LLBB)-ddctiionayy for E.
covering). Let E, n x be positive semi-definite matrix
13

---

Proof. Pick any t-sparse E R". By 4 f-rrerreeetaablityy there is some a E RN with v =
Ei=l a;D; and Ei=1 aasl Dills B. |ol|s Hence
N
|00| = Σ
(u Diyx
Ke, Dÿ)æ
loal ||ll|x Dills
JE[N] ||0|| w
max
|| Pylls
KV, Dzyæl
< B |ulls
JE[N]
max
| 1
(v. (v,)))sl and thus max
2 1/B.
Psll
We can now easily prove that the standard basis is a good dictionary for well-conditooeed E.
Fact A... Let Σ be positive definite matrix with condition number Ans (2)
)aae S K. Under the E-inner
product, every t-sparse vector is at least 1/( kit))--))-ooo correelte with some standard basis vector.
Proof. By Lemma A.3 it suffices to show that the standard basis fei,..., en } is (t, --t representation for Indeed, for any t-sparse R
|u ||eells
ussl v Amax (2) leell2 v Amax (E) [ull
Amax (2)
< Amax ())illlll2 s
Vl |1ollx
Amin (E)
as desired.
A.2 Algorithmic implications
An existential proof that Ne, (E) is small unfortunately does not in general give efficient algo- rithm for constructing a concise dictionary. However, with the caveat that the dictionary must be given the algorithm advice, bounds on Nr. do imply weak learning algorithms with sample complexity O(a log(n)):
Proposition A.5. Let Σ x be positive semi-definite matrix and let D be a (t, al-diciionary for Σ. for some E N and a E 1). For m E N and t-sparse v R", let XI...., Xm N 2) be independent and let y (Xi, v²) + E where & (0, o²). Define the estimator
G = argmin
|1 - =112
RED BER
where X. m X n. is the matrix with rows X1, XI...., Xm- For any 5 > 0, if 2 Co Ca-22 log(3//0)2) for sufficiently large absolute constant C, then with probability at least
| -0 N - a1-2244 1|00 400g² log( (
amm m
Proof. Since D is a adiatddiy,,,, know that there some & E D with ((,
|| ||00|l We then apply Lemma F.4
The above guarantee is essentially of the form "at least 1% of the signal variance can be explained".
Under the E reprrcsseetablly condition, something much stronger is true:
Proposition A.6. Let n, m, N, N and B > Let E: n be a positive semi-definite matrix and let D be a (t, B) Bee-BB))(r--eeeeee repreesseennnnonnnnn of size N for E, normalized that |ells ffrrr all E D.
14

---

Fix a t-sarse vector o' IR, let Xi..... Xm ~ E) be independent and let = (X,,0))+3 where & ((0, )² For any 0, define
v argmin
|XDw - -v112
wERN:|ueliSBA
where D : X N is the matrix with columns comprising the elements of DD and X : m x n is the matrix with rows X1, X1...., Xm- So long as m ((log(n/6)) and 2 1|0* l1x it holds with probability at least - 8 that
DD - w0 1l's =0 0 [Ro
(BRoy
log(2n/0
o² 1og(4/8)
B R² log(n)
Proof. By & f--representaiility and normalization of D, there is some w" RR such that v- = Dw and || 1| S B ||=0|> S BR. Let r = ED. Also, by normalization, max; I'a = 1. Thus, we can apply standard "slow rate" Lasso guarantees to the samples (D X4, y: to get the claimed bound (see e.g. Theorem 14 of (22).
A.3 Optimizing the Lasso in near-linear time
Theorem A.7 (see e.g. Corollary 4 and Section 5.3 in [34] Let m. B, H.T E N and 0. Fix X1,.... Xm E TR" with | S H for all i, and fix w" E R with [| 1| S B. For i E [m] define y: = (X;, w²) + & where 4 ~ [ a²) are independemt random variables. Given (X )m as well as B, T. and 0², there is algorithm MirrorDescentLasso ((x,, ys) B, T, 0 o²), which optimizes the Lasso objective via T iterations of mirror descent, that produces an estimate i E R" satisfying ||0||| $ B and, with probability 1 o1)).
H² T
H2 T
||X m
y
s
||
v1l2 + δ
m
Moreover, the time complexity of MirrorDescentLasso0 () is Ö(mTT)
be positive semi-definite with maxje(n) Mij S H², Fix w E R" with lww)) S. B. Let (X,, n be independent draws where X, ~ N(0,E) E) and y: = wx) + N(0,0², Then MirrorDescentLassol ((X,, y,) B, m, ²²) computes, in time Ö(nm²), an estimate v satisfying, with probability 1 - o(1),
Theorem A.8. Let n, m, B, H E N and > 0. Let E
| - - S o²
oHB m
H
m
Proof. Since max, Σn S H we have that max; || S O(H logn) with probability 1 1-((1) Applying Theorem A.7 with this bound and with T = m, we obtain some w E R with | B and, with probability o(1).
1
1 |8
X 21l m
v11 +
m
where B² H2 By cococenntnnniin have || v11 < d² +1++10 O(1//m)) with probability o(1). Thus,
|| Ø 2ll2 < |[w= - vll2 - + Vem S <amm + Vem
and
| - 21 < X v11 + me S o² + O Vm) + em.
Next, since sup <B (w over x ~ (0, Σ), we can apply Theorem C.I to get that with probability 1 - o(),
wx x)) S 2B | S O(HB n) with probability o(1)
1 ((L
+ n 11 0² <
(IIX
vll, + O(HB))²
m
15

---

Substituting the bounds on || 3/12 and | vll gives
|| w" ==1 | o z o² + 0 O + O( 1/2 H HBBe/m) + Ó /m))
Substituting in the value of and simplifying, we get
0² Vm
oHB vm
H²B
1
- w0 s
as claimed.
B Iterative Peeling
In this section we give the complete proof Lemma 2.4 restated below as Theorem B.1 which describes the guarantees of IterativePeeling O (see Algorithm [ This is key ingredient in the proofs Theorems Lemma 2.9
and 1.2 We also use to formally prove Theorem 2.3 as well as
Theorem B.1. Let n. n,,,ddd Let E : n X n be a positive semi-definite matrix with eigenvalues A .... I An- Given E, d, and t, there is polynomial-time algorithm IterativePeeling! producing a set S S [n] with the following guarantees:
* For every t-sparse E RR, it holds that | 33x |el|
-1/2
. |SI & (7t)2++1d.
Essentially, the set S contains every coordinate i E [n]] that "participates" in an approximate sparse dependency, the sense that there is some sparse linear combination of the covariates with small variance compared to the coefficient on i. To compute S, the algorithm sterativePeeling () first computes the orthogonal projection matrix that projects onto the subspace spanned by the top n n-d cigenvectors of Σ. Starting with the set of coordinates that correlate with ker(P), the procedure then iteratively grows S in such a way that at each step, a new participant of each approximate sparse dependency is discovered, but S does not become too much larger.
The following lemma will be needed to bound how much S grows at each iteration:
Lemma B.2. Let V R= be subspace with d == dim V. For some 0 define
S
[n]
sup zEV
T2 2
|
Then [8| < d/a². Moreover, given set of vectors that span V, compute S in time poly (n.).
{l....,ki) k). Define a matrix A puxn follows. For 1 < < k let row A, V be some vector such that ||Arl| and Aμ 2 a. For 1 + rank(AA < d, so the singular values 2 02 2 ... 2 on 2 0 of A satisfy att1 = 0. Thus,
Proof. Let = [S| and without loss of generality suppose
n let A, 0. Then tr(A) 2 ka and ||A|| Vh. However,
n
ka S tr(A) S
Σ
o. S Vd
Σ of vd ||| = ddk
where the second inequality is by e.g. Von Neumann's trace incquality, and the third incquality is by d-sparsity of the vector It follows that k: d/o² claimed.
Let A be the matrix with columns consisting of the given spanning set for V. By Gram-Schmidt, we may transform the spanning set into orthonormal basis for V, so that A has d columns, and
A Ig. Fix E [n]. Then supzev\çor z:/ ||=||| 2 if and only if (Au)? a² ||abl| 2 0 for some nonzero E Rdd. Equivalently, (Av)? a² for some unit vector u. This is possible if and only if || 2 (where A, is the i-th row of A), which can be checked in polynomial time.
For notational convenience, we also define the set WP.s of vectors v with unusually large norm outside the set S.
16

---

Definition B.3. For any matrix P: n x n and subset S _ [n], define Wp.s == {u E R" l 3 Pt).
We then formalize the guarantee of each iteration of IterativePeeling() as follows: Lemma B.4. Let n,t E N and let P: n x n be an orthogonal projection matrix. Suppose T 2
and K _ [n] satisfy
(a) Pu 2 1 for all i K,
(b) supp(u) \ K S 7 for every V E Bu(t)
Then there exists set (K) with [Ir(K)] 36t K] such that
[supp(v) \ (Ir(K) U K) -
for all e E Bo(t) n Wr.k. Moreover, given P, K, and compute Ip(K) in time poly(n).
Proof. We define the set
[ral ||0||
Ip(K)=
[n] K:
sup
1/(6l)
#Espan Pe Kof0
is clear from Lemma B.2 (applied with parameters == span that [Ip [K) S 36t K and that Ip(K) can be computed in time poly(n). It remains to show that supp(u) \ (Ip KUUUUK) K) I r - for all v E Bo(t) n Wp.k
Pe; ( E K} and a = 1/(6t))
Consider any E Bo(t) n Wr.k. Then ||uxe > 3.
Pv. We have
lu- 12
n
P |Poll
Σ
P.P
where the first equality the fact that P projection matrix. We also know that
Σ /EIn|VK
ur ex)
<
Σ
|u e:ll2 - 3/8 || 11 S 3
luxell2
(2)
KEinJKK
by the triangle inequality, the bound [.P e 112 (1 P)# 1 Ps 1/(9t) (since K), and t-sparsity of v. Moreover, 2 implies that
Σ
P.P:
Σ iE[M]iK
us(P: ei)
4 +|luko ll2 S 12x
(3)
FE(M]KK
Combining
and
the triangle inequality gives
n
5 ||u llz.
Σ
o.P:
s
u.P.
+
Σ
U1 P.
(4)
3
iEK
2
2
Next, observe that
l
Σ 0/
|loKellz llz
(by
3
2
Σ
U. Pt. UKo
(by Sauchy-Schwarce
1=1
Σ
u;Pr, Ux
)
)
Σ
UrPis UK
(by triangle incquality)
WEE
17

---

M
/
Σ J
uses, UKE
Σ SE(nIiK
us(P: ei),uk
-
Us Pi, use
VEEK (by triangle inequality)
|uu=l122
Σ
vs(P: ei)
luxe112
Σ UpPis une
IEK
(by Cauchy-Schwarz)
2 || 12
||ux 11
Σ ViEK
U/ Pi, uKe
(by
and hence
Σ
PiP uk=
1 ||uk= 112 2 11xx ll2
1
Σ P;P:
LIEK
iEK
where the last inequality is by
On the other hand, observe that
>/
Σ uu vePPses)) )
Σ C.PP UKE
Σ
1051
vl ||uxeel2
Σ us us WEE
max jESupp(o)
KEKK
JE
WEKK
Hence, there some j supp(e) \\ K such that
EurPiee)) likk
>>>>>>>>>>>>>
1
Σ s.P.
5VE
So the vector z(v) = ΣSEK U.P: E spantP, : i E K} satisfies (z(U);| > |x(v)]] (5vt).
Moreover, s((e) is nonzero since (u(())) > 0. Thus, j E Ip(K). Since we chose j to be in supp(v) \ K, it follows that
supp(c) \ (Ir(K) K) < |supp(u) K1 - --
where the last inequality is by assumption (b) in the lemma statement.
We can now complete the proof of Theorem B. by repeatedly invoking Lemma B.4 (this proof was given in Section 2.2land and is duplicated here for completenes)).
Proof of Theorem B.1 Let Σ._ Am be the eigendecomposition of E, and let P : Ex=41 u. be the projection onto the top n cigenspaces of Σ. Set K, {i [n] : Pa <
1-1/ 1-)/( Because tr(P) = n-nd and P.. < for all i E [x]], it must be that [K,] S 9ddd. Also, for any E (t( Me, we have trivially by t-sparsity that (uupp(v) K,l S t.
Define K₁- to be K, (IKKK) where Ip (K,) is as defined in Lemma B.4 we have the guarantees that KK-1l < 36+ and (Gr(v)) Ke| < t-1 for all u E (t) (r,,),WWKKKK.. Since K₁-1 2 K,, for all E Bu()) n Wr.k.-1 Moreover, since K,-1 2 K,, it obviously holds that P., 2 1011-1(990 1-1/ for all & K,-1- This means we can apply Lemma B.4 with = 1 and K = K,- and so iteratively define sets K C... C Ki C Kn S n in the same way. In the end, we obtain the set Ko S [r]] with [Ka] S 962 + 3) and supp(w) C Ko for all e E (b( n WP, The latter guarantee means that in fact Bt( n WP.Ko 0. So for any t-sparse U E R" it holds that
holds that Wr,k,- C Wr.k, and thus (g)(v) Kg S f
|ukslls 11, 33 Pu & 3
1/2 To
where the last inequality holds since P E.
18

---

Proof of Lemma 2.9. By Theorem B.1 there is polynomial-time computable set S S [n]] such
that ||os= 1l2 I 3 3 d+1 |oll for all E Bo(t), and |S] I (7t)2++1d. d. Let the dictionary D consist of the standard basis (ei....,ey) together with E-orthogonal basis for each subspace spanned by t vectors in fer : E S}. Let v E R" be t-sparse. Let us denote the restriction of u to S, i.e. os = v - Eigin use.. By construction of the dictionary, there a E-orthogonal basis for fez Dg:iESt S nupppt)) so there are di....,dy dg E 'D and coefficients bd....., bJ. E R with us = Eiz ba, d, and (di d 0 for all i, E [t] with + j. Note that ||e 1| = Ei= by || l so
1/2
ba. dells: S Vt
|d.ll Villuslb:
Now, we claim that the desired coefficient vector faa E D} for v is defined by aa = ba +
Eielmnis [1 ei]. We can check that EIeD and = Ei=1 ba, + Eie(n]]s die; = t. Also,
||us|l> - ||0|| + ||/s-lls 1|x
$ ||0|| + An 1103e122
$ (1 3v An (2411) |101
by the guarantee of set S. It follows that
ba,, $ (143/lss55(433//xxii\vvell VnnAee1.
Thus,
Σ
lcal (1t3////5((5/////m/a///a + Σ leal lleills:
dED
kE[n](s
vt || llz An
5 (1+33/nn/a- 3v ||uls v An/Aa+1
< /TVtvAn//uu /441 /
which completes the proof.
Proof of Theorem 2.3 Immediate from Lemma 2.9 and Lemma A.3
C An efficient algorithm for handling outlier eigenvalues
In this section describe and provide error guarantees for novel sparse linear regression algo- rithm BOAR-Lasao () (see Algorithm 2 for pseudocode), completing the proof of Theorem I.I in Section C we then analyze modified algorithm to prove Theorem 1.2
The key subroutine of BOAR-Lasso is the procedure Alapuiivelyylgullaiiiddddss (), which (like the simplified procedure AdaptedBP() from Section 3) first invokes procedure IterativePeelingl to compute the set of coordinates that participate sparse approximate dependencies, and second computes modified Lasso estimate where those coordinates are not reg- ularized.
We start with Theorem C.2 which shows that, in the setting where Σ has few outlier eigenvalues, the procedure
estimates the sparse ground truth regressor the "slow rate" (e.g. the noiseless setting, the excess risk is at most O(I I]²= rea/ma). Typical excess risk analyses for Lasso proceed by applying some general- purpose machinery for generalization bounds, such as the following result which only requires understanding (w w", X) for X ~ N (0, ))
19

---

Algorithm 2: Solve sparse linear regression when covariate eigenspectrum has few outliers
Procedure v SeiegullrizzdLasssoC (X,, (r) I, d,, 8)
Data: Covariance matrix Σ : n, samples (X, 1:) ) sparsity t, small eigenvalue count d,, failure probability
Result: Estimate i of unknown sparse regressor, satisfying Theorem
> A - cigendecomposition of Σ
+ IteratiieeeellingCC.....
/* See Algori timm
*/
Return
+ argmin Σ O) 2)) + log( (2((12//)) llus 1|; (aar22nn-na dr log(12n/0) Us
Procedure BOAR-Lasso (E, (Y, M:) t, d₁ L, 6)
Data: Covariance matrix Σ : n,, samples (X,, y)) sparsity t, small eigenvalue count d, repetition count I,, failure probability 5
Result: Estimate i of unknown sparse regressor, satisfying Theorem
3(4) f- 0 E R"
for 0 j j L do
Set
Σ +
Σ
(3
(s(D) Σ8S1
Set A0) I,.., m(j m(
a(+1) +- Alagttielyllguuarizeeoloooo (Σ6),
((X,, (X,, () (X,, (EA0,,, t + di 8/L)
((+1)
(00-1) - + n+1
+ +(1+1)30)
[n|
g(+1) + glا) + 0(++1)
return g(L)
Theorem C.1 (Theorem in [45 Let semi-definite matrix and fix w² E R". Let : m x n have i.i.d. rows XI,...,X,, ~ N (0, Σ), and
N and c, 0. Let E n be positive
let y = Xw" + & where & (0, (m)) Let F Rd + [0, oo] be a continuous function such that
Pr sup (w w", ,.) F (w) > S 5.
No,N( weR"
If m 2 196c log(12/0), then with probability at least 1 48 holds that for all w E IRd,
|| - - +0² 1+E (II - 2ll + F(w))2
In classical settings, e.g. (a) where || is bounded and max, E3 < (see Proposition A.6) or (b) where satisfies the compatibility condition (see Definition G.I.. the above result can applied together with the straightforward bound (w v² X) < 100 1' ||X ll To prove Theorem C.2
we follow the same general recipe (a), with several modifications.
First, since max; Σi could be arbitrarily large, we need to treat the (few) large eigenspaces of Σ separately when bounding (v 1 v0, X). Similarly, since Theorem B. only gives bounds u² for coordinates outside S, we separately bound (U=-v")s, achieve the optimal rate of a² rather than 0² VVnent/ m. we do not directly apply Theorem C.1 to the noisy samples (X,, ys); instead, we derive a modification of that result (Lemma F.7 that only invokes Theorem C.I on the noiseless samples (X;, (X., v²)), and separately bounds the in-sample
using that |S] is small. Second, to
similar technique used in 45 for constrained least-squares programs (see their Lemma 15); our Lemma F.7 applies to broad family of additively regular- ized programs, which obviates the need to independently estimate |l= but otherwise achieves comparable bounds.
prediction error [ - x*) b-
Theorem C.2. Let n, di, dr, m E N and a 6 > 0. Lei E: n ni positive semi-defiitt matrix with eigenvalues A 5 ... S Am. Let (Xi, ym 1 be independent samples where X, NN,,, E) and
20

---

(x. (0, 0²) and a fixed t-sparse vector o' E R". Let ė be the output of d,,5). tt, Let Let Reg:= (7t) + dn + log (8/4 /6) bdapiiioolRBuuuuaroooooossss (E, (X,, ;,,
and let raff == 1(An d., Aa (g((12/ There are absolute constants C >> O so that the following holds. If m 2 Coeg. then with probability least 6,
( o
(o+ + 110 (100]l>)) 11000 lbs VTel + | 1101 Tall
1 0'1 S
Vm
Proof. Define projection matrix P ;: RR-da
iill u;u, so that vank(P1) p-]= dn and maa (EP)) S
An And For any E R and X N(0 E), we can bound
(0 -0-v..X) = ((v ((v-v")s- PX) + ((v - v*)s-, p-x) + ((v - 0²) X)
-1)=-))s:: P + /2 (1- -- (p- 1/ X)sz) + (EV/3(0 (0000% -0-)) (0""(o--')>) -1
11 |X + ||2 (r vn) 0/1 ||W|))
where PX N(0, PEP), Z NOO (P- 1/2,, and W
((, E-112Ess--119 1/2.. First, since maxx(PEP) Amax PEP) S An- we have the Gaus-
sian tail bound
Pr PX >
I 88/12.
Second, since
1-1/3(P1 EP! s= (p 1P11
(by Cauchy Interlacing Theorem) (since p1 commutes with E)
=
have that ||2|| is stochastically dominated by x². and thus
Pr 12112 > 2dh se m/4 < 8/12.
Third, similarly, since Σ y 1/2 = 1 (again by Cauchy Interlacing Theorem) and also
rank(E-1/28) E 1/2) < S/). we have that [W]l2 is stochastically dominated by Xis) and thus
Pr [ > 2| se m/4 s 5/12.
Combining the above bounds, we have that with probability at least - 5/4 over X ~ NO, E), for all E R".
v')s=1l 11 v /n-dd 2log(12n/8) + ( (v= vr)1/1 (V2d,, /2(SS).
(v u² x) S (1(v ((--v')ss
We can therefore apply Lemma
F.7 with covariance Σ, seminorm Φ(v)
2 222 log(12n/6) [us= == 4(d, + S)) ). ground truth v², samples (Xt. and failure
probability 5/4. By the bound on |S| (Theorem I.I we have |S] + dn < (7t)2++1 di + d, S Reffs
so it holds that 2 16p + 196 log((8///))) (8)) Thus, with probability at least 25, we have
( o (ftnee m
(a | ) ||ugell Il, VAn-d, log 1og(12n/8) ||uge 1l A de log log(12n/8)
||0 11 5
+
vm
m
By the guarantee of S. (Theorem B.1 and t-sparsity of 8*, we have || ll2 S 3A 1/2 || and 1/2
thus ||uše 1| I /// d.41
fu'|, lls. Substituting into the previous bound, we get
o (a + 110 1bx:) 11u 1/
Teff
|00 E Ten
||0 - 01 < 0
/ m
as claimed.
21

---

The limitation of Adapriieeyyfegulllrrzzaaaaas is that the excess risk bound depends on ||=" rather than just o². We next show that by a boosting approach, we can exponentially at- tenuate that dependence, essentially achieving the near-optimal rate of nan m. The key insight is that after producing an estimate of o², we can augment the set of covariates with the feature (x, B), and try to predict the response y- (x, i).. which is now (1+ [++ 1) )spprse combination of the features. In standard settings, this is typically a bad idea because it introduces a sparse linear dependence. However, by the Cauchy Interlacing Theorem it increases the number of outlier eigenvalues by at most one - so our algorithms still apply. Thus, we have enough samples that the excess risk bound in Theorem C.2 is non-trivially smaller than ||o" l|g- then we can iteratively achieve better and better estimates up to the noise limit. This is precisely what L () does; the precise guarantees are stated in the following theorem, which completes the proof of Theorem [.I
Theorem C.3. Let n,t, di, dn, m. E N and o, 5 > 0. Let E n X n. be a positive semi-definite matrix with eigenvalues x1 I .... An- Let (X V:) be independent samples where X₁ (0, Σ) and yi V*) + En, for & ~ NN o²) and a fixed t-sparse vector e E R".
Then, given Σ, (Xi,u))= 1, di, and 6, the algorithm BOAR-Lasso outputs estimator i with the following properties.
Let Reff := (7t)2t+ di + dn + log(48/6) and let Teff := t(An- dn,/ ( log There are absolute constants co: Co > such that the following holds. Z CoL(net + Tef), then with probability at least - 8, it holds that
(n +rg) 2 1 11001
||0 - 10-0112
m/L
Moreover, BOAR-Lasso () has time complexity poly(n, m.
Proof. Let (Ao...., Ar-1) 1) be an partition of [m]] into L sets of size m/L. The idea of the algorithm is to compute vectors ((1)) ..... ((L) where each (()) is an estimate of 0" شド= ((1), Concretely, fix some 0 $ j S L and suppose that we have computed some vectors ((1), ,(.,,.. 861) Set g(d) = f(1) +... + ((5), Define a matrix Σú) (n 1) x (n + by
x = Σ&SI
Σ
(BU)) (Z())T
Thus, for example, [()) has zeroes in the last row and last column. Now for each i E A,, define (x()) ()) by
x (Xi, (X,,,80)
y1 = yi - -X,, (()))
By construction, the m/L samples (x(10 (1) (3) )iEd, are independent and distributed as x!!)
V/
(0, g and ( = (x("), (v" -1)) + &. Let X < ... S (i) be the eigenvalues of ΣU)
Now we apply Theorem C.2 with covariance Σt), samples (x(3), .,) )E sparsity / + 1, outlier
(5) counts di 1 and dn + 1, and failure probability 8/ L: let nen and (G) be the induced parameters defined in that theorem statement, and c, C' be the constants. By the Cauchy Interlacing Theorem,
d.+2 have > (7) 2 Ad.+1 and similarly x())
(()) An-d,, Thus rall 2ran- Also ni Σ Bell--
(1)
1=+1-(d,+1)
Thus, the constant Co is chosen appropriately large, then m/ L 2 16er.6) and also m/L Z Cn
Hence (by the error guarantee of Theorem C.2) with probability at least 1 8/L we obtain a vector w(+1) such that
n nn
(
(,( + ca -1)0l-)))0 V m/L
(00+1) (00, -10 <
m/L +oll(0" 11]1
V
m//
< 200 neil
-1)1l
(1] (1I00,
4c2 2
4 +
m/ L
4 m/ L
22

---

cn (net + ret)
[[(",, 1) -1)1l
2 m/L +
(5)
2
where the second inequality uses AM-GM to bound the third term, and the third inequality is by choosing co 2 + &c?..
(((+11 Then we observe that I1(v", -1]1 = ||ue $ 1| and | - (0= - -1) ||0(+1) - -v- -(0
But now define gli+1) = (6+1)
[n]
+ fn
||0 - 3(++)) 1 where
g(++1) = 60)) + + 800+11, So 5 equivalent to
10- - 3(++1) -
Co o² (Motf + Tett)
0- =36)
+ 2
Σ
2
m/ L
Inductively, we conclude that
| ||
(mett + Tett)
S
+ 2 1 ||00
m/L
as desired. The time complexity (see Algorithm 2 for full pseudocode) is dominated by L eigen- decompositions of n x n Hermitian matrices (each of which takes time O(n²) by e.g. the QR algorithm), as well as convex optimizations (each of which takes time Ó(n²) to solve to inverse- polynomial accuracy 266), which is sufficient for the correctness proof).
C.1 An alternative algorithm (proof of Theorem 1.2
In this section we prove Theorem which essentially states that the sample complexity depen- dence di in BOAR-Lasso () can be removed the cost of time complexity depending dj- See Algorithm3 for the pseudocode of how we modify tially, we brute force search over all size-l subsets of the set S produced by IterativePeellng O)
(): essen-
construct an appropriate dictionary for each of these ((5)) subsets, and then perform a final model selection step (with fresh samples) to pick the best dictionarylestimator The boosting step is exactly identical that BOAR-Lasso)).
Lemma C.4. Let n, n,t,d= N. Let Σ : X n. be a positive semi-definite matrix with eigenvalues A .... S Am Then there is a family C Rax((+s) of size [D] S (7d)) consisting
entirely of n x (n + matrices with the form
[In d1
de).
with the following property. For any t-sparse E RR," there is some E and w E R.n with Dw and
7/2/2
||w|| <
Ev.
Aut1
Proof. Let ui...., Un Rn be the eigenvectors of Σ corresponding eigenvalues A An
respectively, that Σ = Σr_ f-1 \uu;u, Define Σ = X Σ i=1 min(Ai, Aat1)u,, Let S be the output of IterativePee ing (E, di, 1), and let D = (D(T)= : TE (9) where for any T E (9). we let (d)...., } be E-orthonormal basis for span(e; i E T). and let D(T") be the (n + () matrix with columns e....., Cn, d1, ..., dg. The bound on [D] follows from Theorem B.
For any t-sparse v E R. pick the matrix D D indexed by any T ( Let di...., de E Ra be the last columns of D. Then there are coefficients bi...., by so that we can write us = Et= b,d,, Since d. Edg- = [ = i'] for all i, i' E [t]. we have ug Evs Σi 03
(9) with S n supp(()) C T.
Hence, [|6|]] S Vt ug Eus. But we can bound
Us
2
1/2
1
/
Uge
(by triangle inequality)
23

---

Algorithm 3: Alternative algorithm to solve sparse linear regression when covariate eigenspec-
trum has few outliers
Procedure wtw.rerrecddic...ooaaaaaaaso
(x y1) de, 6) Data: Covariance matrix Σ : n, samples (X,, yt) sparsity t. small eigenvalue count d,, failure probability 5
Result: Estimate i of unknown sparse regressor, satisfying Theorem C.5
Σ \qu,u, < eigendecooppositinn of Σ
f IterativePeelinggC.
/* See Algorithe thm */
Σ+ Σ+ d E i= min(A, Ad+11)u;
for E
(1)) do
d ,....,,y
d + E-orthogonal basis for spanfes : E
D(T) + In d
Compute
m22 (Xx, 31:m/22)
(T) + argmin
Σ t=1
wERntH
84 -ahaalogha log(8n/0) ||ll] + 22222nnllgll (ac/))))/lmm))) / 110l1
Select best hypothesis
i - argmin
Σ
D(T)((()) -11)
TE i=m/241
return (T)
|1/3/ //
+ +1lus=11
(by E M and Σ R I,)
A41
1/2
11/22/ |1,
+ +3 V
and (by Theorem B.J and t-sparsity of v)
141
S 4 1/2 Ev. Ev.
1+1
We conclude that [b]1 < 4V Ve Σv. Thus, if we define
1/2
Σ
Uses +
bienti:
1=1
where here e.,..., cn+* refer to the standard basis vectors in Ri+ then we have Dw = U/x]/ + Eim b,d, and also
7Vi
||w]| s |bbl +
Σ kE(n])s
|oa| S 4vix~1//2 VuT Ew + Villus=l12 s
Ve
Tw
1/2 A441
as desired.
n, 1, de, m N and let E, eigenvalues A1 S ... S Am- Let () be independent samples where X; ~ N Σ) and (Xi, 0*) for &, ~ N(O, o²) and fixed t-sparse vector v² E R." Set k == ((71)2( (10))2++000 +1 and let be the the family of matrices (of size at most k) guaranteed by Lemma C.4
Theorem C.5. Let n,
be a positive semi-definite matrix with
Let 8 > 0. For every D E D, define
( Dw 91.m/2 1| lo [| 22t/22nnnllgg000 (11
w () E argmin WERnie
|1 ||
(6)
24

---

where x(), (m/2) x n is the matrix with rows X1... Xm/2, and define = Dw((D) where
D E argmin
x Dw((D) - Um/2211mm
DED
where (²) (m/2) x n is the matrix with rows Xm/2+1..... Xm.
Let Rel == (2 log(t) + log(d)) + da + log(48, (0) and let relf == 1 MAn-da/ dd, (d,+1) 11) log(8n/6r There absolute constants c, > O so that the following holds. If m 2 Cneg then with probability at least 1 35 it holds that
v0lv0 c
o m
1|00
Telf m
Feff m
110
11
Teff m
V
Let D' E DD and n² E IR=+ be the matrix and vector guaranteed by Lemma C.4 for the t-sparse vector v². Let (D*) with eigenvalues "i ... I "nn+e We make the following claim:
Claim C.6. With probability at least 1 - 8/4 over G (0,1)), it holds uniformly in E gu+t that
(w- w. G) - 1 w" "111 Vnndd, -2 1lg((8n/8) + l|w w" ll1 2(dh + t).
Proof. Since E is a principal submatrix of I, we have nn-d, I An (by the Cauchy Interlacing Theorem). Suppose that I' has eigendeconposition I' = > P (n + t) x (n t) by P Σi=1. di, gig; so that rank(P-) dA + and Amax (PTP) s
shtt 7999 and define projection matrix
-n I An-da- Then for any E m and G ~ N),, we can bound
(w w., G)
(w w", PG) + (w w", w',P''.G G)
|| w² w²11, PG + (T2/2 - T-),,-1122p-0
|| w01l PG + 11 (w -,) p-1
< Il w01|, PG]| + | (w w² 2/1 1Z
where Z ~ NO, P-). The second equality above uses that 1-2 and PL are simultaneously diagonalizable (and therefore commute). But now for any > 0, we have the Gaussian tail bounds
Pr
| /max(PTPP): 2log(8n/8) $ 6//8
and
Pr 12112 > /2rank(==) S Se-mie < 6/8.
Thus, with probability at least - 6/4 over G ~ N(O,T) ['), for any w E Butt we have
(w wº G) 5 || w 1l1 (Pa(() .aiii.2logg(e 2log(8n/0)) +||111/((00) (oow-w)) w") w²)l| v 2rank((P))
|///
w w 1|1 Vdn-da 2.a..22ogge 2log(8n/0) + (w wi)l 22(cn +1)
= F(w)
which proves the claim.
We now proceed with proving the theorem.
Proof of Theorem C.5 Applying Claim C.6 we invoke Lemmal F.7 with covariance matrix 2 log 8n/8) ||e||, p 2(d,, + t). ground truth w*. samples ((D*) X;, mn/2 and failure probability 5/4. Since we chose m sufficiently large that m/2 > 16p 196 log(12/8)) we conclude that with probability least 28 over the randomness of W/m/ m/2 it holds that
r, seminorm (vv)
odh +t) + (a + ||l* (p)) " / An-d, log log(8n/ö) +
||w An An-dn log log(8n/8) (8n/8)
[[((D*) - "1 5
m
m
m
25

---

Since v² = ="""" and || S 7
-1 1/2 d.
||0 11 (the guarantees of Lemma C.4 it follows that
[D''((D)) s 0
o (d +1)
+ (o (o
||0 (s))) ||0 l1s
Tetf
Teff
m
Vi
m
To complete the proof of the theorem, condition on any values of (X,, ) for which the above bound holds. By applying Lemma F2 with covariance matrix Σ, hypothesis set W (Di(D): D E D), and samples (X,, yo) k-m/2+1 (which are independent of W), since m/2 2
32 1ogg(2 have with probability least 1 26 over the samples (X yb ) imm/2+1 that
Di(D) - -011 - 6 min [DD(D) -0 32o² log (2g(2(1)/0)
1
DED
Hence, with probability at least 56 we have
(a + [10))ls)) 110 11x: Tofff (D(()= -2- 1 50 02 (dh, + log log(2(D)/0))
||
Feir
+
Vm
which proves the theorem.
We can use the above theorem (together with the previously discussed boosting approach) to get the following result, which proves Theorem 1.2
be a positive semi-definite matrix with eigenvalues x1 S ... S An- Let (x,, ) be independent samples where X; ~ (0, Σ) and y: (X;, u²) Et. for & N(0, a²) and a fixed t-sparse vector of E TR.
Theorem C.7. Let n. di, dr, m.
N and a, 5 > O. Let Σ
Then, given 2, (i) t, di, and 6, there is an estimator with the following properties.
Let n'y = 1 log(t)= + t log(di) - da + log(48L/5) and let T'g == t(An-da, (dd++)) 10g(8nL/0), There are absolute constants co. Co > 0 such that the following holds. m 2 CoL(n' + Tr')), then with probability at least 1 - 5, it holds that
22 + rr'g) +2- 1
|10 - l S co
m/L
Moreover, e is computable in time (t + (1+1))()) (di + 1) poly(n).
Proof. Identical to that of Theorem C
except using Theorem C.5
instead of Theorem C.2
D Faster sparse linear regression for arbitrary Σ
In this section we prove Theorem 3.1 The approach is via feature adaptation: in Theorem D.5 we show that any covariance matrix has (t, (t33/2 log n)-6 rer-essrprrsnnnaiionn of size On"' (nn that is computable in time (21(1)))) lot
O(t) n, using O log n) samples from N(0, Σ). The algorithm for computing this representation is described Algorithm One of the key tools is the following result from computational geometry:
Theorem D.1 (30). Let n. d, le E and > 0. Given points Pi.... : E Rd. query dimen- sion k. and failure probability 8, there algorithm (S(P.....,PP).Kk 6) with time complexity k+1 (log O(k poly(d) log(1/5), that constructs data structure N that answers queries of the following form. Given a k-dimensional subspace F C Rd, the output ((F) is some i' E [n]. With probability at least 1 - 8, the query time complexity is 1221/((2k) poly(d) log(1 /8), and it holds that
min I|p-- 41122 S O(log n) min min llp: - 4112- REF
xE(n) 9EF
How do we use the above theorem to efficiently construct the é éi-representation? The intuition is as follows. Let X be the x n matrix where each row a sample from ((, Σ). Then each column is a vector representing particular covariate. To find the f-rrepresentation, it essentially suffices
26

---

Algorithm 4: L represeenttan for arbitrary
Procedure FindOrthonormal ization (ptiion((p.i.))).. (p1..... ,p:)
Data: Nonzero vectors Pi...-.PP E R Result: a1),, ,..., (!) E I'' such that span (a (......!!! spanfer,..... ,t} and (1)
( af pe: Ee at pz) = 0 for all +
for = I,...,tdu do
(11) - e/ lpillp E R2
for j 1,...,
do
Ee o Pe + then
a + a
(
pt. pt.
1 pe) a1)
Σe Pt
return (1) " (K)
Procedure RepresentVecttors
Pn J.t,)
Data: Unit vectors p1...., E Rmm sparsity parameter i, failure probability
Result: Set C IR" of size O(n'~1/2) where all elements E DD are I-sparse (and
represented succinctly)
10
11
Compute partition I LI T/ = [n] where |1, $ [vn] for all Initialize D <- 0
12
13
for j = 1,.... /n do
14
Construct data structure A DS((p:: 1,), 1,8/n")
Theorem
D.1
*/
for T ((=)) do
15
16
h(T,j) < (spaan i TT)
/* Theorem D.1
*/
17
Find y IRT such that Σier "iPi (p.ssp))(p.sieT) Ph(T.)
Write y sparse vector in IR" (supported on T)
19
Add - EM(T,) to 'D
20
for T' S (1-2) do
21
for b I do
(1), ...., ((()) <- FindOrrhonoommllzzttiiioog :ie T {a, b)))
Write (1)
(1) as sparse vectors in R" (supported T U {a, b))
Add (1) 7 (2) to
24
25
return D
Procedure
(1X); (1)
27
Let X m x n be the matrix with rows XI.... X
Xm
Let f1.....:6 In be the columns of X, and let p; = qi/ l1 for i E [n]
D t RepresentVectors (erreecctor((pp....pete Pa em
29
30
D diag(1]41l2.... .|,.)l)),)1))
D -- (Dd: D) return D
31
32
find a dictionary of O(n'11/3 sparse combinations of {P...... Pn} so that every t-sparse combination of (pı...., } can be written in terms of the chosen combinations, with coefficient vector that has bounded l norm.
For notational ease, we define C(x)) to be the "cost" a particular linear combination r E R with respect the set D of chosen combinations:
Definition D.2. For a subset C R=, define Cp R -> [0, oo] by
Cp(x):
min
Σ laal- Σ dep
o Deep Oadma
27

---

With this notation, we want to construct set D of size 0/2²-1/3), consisting of t-sparse vectors, such that
Co(a)= S (og
Σ riPi
for all t-sparse x E R"
The construction is quite simple: divide the set {PI..... . into vn equal-sized groups. For each set 7 of t vectors and each of the v groups, find the closest vector in the group to the subspace spanned by T (using Theorem D.1 to achieve sublinear time complexity). Then add the difference between the vector and its projection (onto the subspace) to the dictionary. Finally, for each set of t vectors where two of the vectors lie in the same group, add an orthonormal basis for those vectors to the dictionary. See the procedure Represent Vectors () Algorithm 5 for pseudocode.
By construction, the dictionary clearly has size 0(n'-1/2). At high level, the reason it satisfies the representational property is the following. Consider some f-sparse combination, such as P1 +.....p. If --p; is not very close to P1 +.. Pt-1, then can bound C(p1 +............................. by C(pi +... Pt-1) and C(pt). which are ( [IpI +.... + Pt-1 (l2) and O(v7 (ppell2) respectively, since the dictionary contains an orthonormal basis for both terms. The only case where these bounds are not good enough is when ||pı + + pellz is much smaller than ||p + + Pt-1 2l2 and l|pellz- In this case, Pt is very close to (pa ... Pt-11) However, in the construction we found some (potentially different) P5 which is just as close to span(pi. ................................ Pt-1). }. and moreover is in the same group as pt. Letting q be the projection of Pj onto span Pt-1 we have the crucial fact that [p; - 4ll is as small as [lp: + P=ll2-
Now, bounding C(p1 +... + pt) proceeds as follows. We can subtract some appropriate (bounded) out at least of the coefficients. This residual
multiple of Pj q from P1 + + Pt then is a t-sparse combination of (p),...,,' Pt. Pj where two of the vectors {Pt,P}} are in the same group; thus it has small cost with respect D. Moreover, Pj q is contained in D and thus has small cost (specifically, not much more than ||25 ج|اa- which crucially is not much more than |lp: +... + P.ll)). It follows that P1 + Pt has small cost.
Formalizing this argument, we start by proving one the facts that we freely used above: that the cost function C' satisties the triangle inequality.
Fact D.3. For any D C R and x. E RR", it holds that C(x + v) I C(x) + CCv)
Proof. For any ax B E RRP with Egadd = x and Ea 3ad = y. the vector a + 3 satisfies Ea(a + 3)dd = + y. Applying the triangle inequality to Ea 1(a + 3)al 11 d.pill2 completes the proof.
We now prove the key lemma, formalizing the above intuition.
Lemma D.4. Let n. m, t E N, with t > 2, and 8 > O. Fix PI..... . E R with ||p:l|2 = for all .Ppp.....PP.... 1,)) Then [D] (22
i E [n). Let 'D be the oulput of VepresentVectors and every element of D is t-sparse. Also, with probability at least 1 - 8, the following guarantees hold. The time complexity of computing D is O(n' (nn-)((11))))) (log mm0) 0(1) log(1/8)). Moreover, for every t-sparse x E R it holds that
Cp(x) s 0(11/220gg) logn).
Σ r.Pi
Proof. Since the algorithm RepresentVectorssl makes less than n' queries to the data structures A3, and each query has failure probability most 8' = 5/n', the probability that any query fails is at most - 6. We henceforth assume that all queries succeed, i.c. satisfy the correctness guarantee and time complexity bound stated in Theorem D.I
Time complexity. We start by analyzing the time complexity of RepresentVectorse ((p....(p...... Pp), 1),). For any fixed [v]]. the construction time of No (with |4, ((vn) points in R" query dimension t 1. and failure probability 5/n*) is (n (log (l 0(1) log(1/5)). We make (.")) (,,) = O(n-11) queries to N each with time complexity 11/2-1/(40-1))mm01 log(1/0), Each projection step and each orthonor- malization step has time complexity poly m). Thus, since 2, the time complexity for any
28

---

fixed is bounded by n (logn) ( ml( 0(1) (og(116)) Summing over j. the overall time complexity to compute D is at most n²" 1/(t) (logn) ))(()) m 0(1) log(1/6) as claimed.
Correctness.
The bound on [D] and the fact that all elements D are t-spas are immediate from the algorithm definition. It remains to bound (x) for t-sparse vectors 2. First, note that for any (t - -s--sprse y E R2, because step (4), the dictionary contains vectors 7 ...., f-1 that span T.P,)) for all l. Thus, letting 01.,.... 0 R be
su)p(y) and satisfy (2 Y/P,, Di Di=1 " get such that y an7!
+ 01-17
(-1
n
L-
1
Crlu)= S
Layl ==1
Pi
Sv
PiPi
Vi
y:P:
i=1
j=1
2
Now fix any nonzero t-saarse R" Fix any arg max (aal, and let E [V be such that E Ij. Let T supp(æ) {a}. Let q = Protspa(prrte) Ph(T.))- Then by the correctness guarantee No on query span (p::m(p;:100 :iET)
[PaCT..) al12 s Ologn))
Pa
34 Pi
Olog n)
1 a.Pill2
(8)
Da
igfa
Case I. Suppose that [|PиTT:5) - all2 2 1/2. Then by (8) Thus, by the triangle inequality,
we have |xa|| S ((lgg)) n) ||E x.pill2-
TaPs
< [aal
+
Σ xxps
Ollogn)
Σ niPi
i
2
It follows from Fact D.3
and
that
Cp(x) & CD(Iaca) + Cpla - xala) S Maa + +
Σ x:Pi igla
I <((Vilogn)
Σ x:Pi
as desired.
Case II. It remains to consider the case that [| 4112 < 1/2.. In this case we have ||4112 2 [PPer-silla-14 -1/2 2 1/2. By step (3) of the algorithm, the dictionary contains some vector - such that supp(>) S T and q Eier Yppt. Fix any b e arg max, hr). Since q Σ
Emp, nPP we get
had |llll2 1/(2.). Now, by Fact D.3
(-h (entes)) -1)
Ib (ENTT,)) - x +
Cp(x) S CD
CD
7
By construction, CN(T.) y is an element of the dictionary, so we can bound the first term as
CD
3b (CN(T - -))
s
Σ
(CA(T.)) - -)ipp
76
nbl
i=1
|Ipu(T.)) - -1l12
< 2f/rral
|IPT(TT))) - -g/12
< O(t log
Σ T.Pi
where the equality uses that g = Σ" 1/(2t), and the final inequality uses
TPPs. the second inequality uses that [1t] S |ara and hmo 2
29

---

Finally, observe that
Tb 2: x (eA(T.) -7) = Iala + 76b
Tb en(T +
Σ
Jb%
24
76
78
MaT
since the coefficients on cancel out. Thus, is linear combination of two elements of {p: :
i E 1j} together with - 2 elements of {p: : i E [n]]. Because of step (4) of the algorithm, the that span supp(=) and satisfy (2
dictionary contains vectors 7² ,.,,, 7f for all k + L. The same argument as for 7 gives that
2i=1 75 Pt, Ei= M(p)
CD x
4b (e)(T.)) -7) s Vv
Σ x:P:
+
Tb - (Ph(TT)) - 9)
%b
10b
S Vi
Σ
00( #VVElogg n²)
Σ i=1
PiPi
TiPi
16
Ia
i=1
s 00tt3/111gg logn)
Σ T.Pi
where the second inequality uses the triangle inequality and (8). and the final inequality uses that [ea] S [ea| and ha/ 2 1/(21). Putting everything together, we conclude that
Cp(r) 0(13/22 (185/2logn)
Σ 1=1
as claimed.
We show that RepresentVectors () be applied the columns of the sample matrix to obtain a E ég-rppresentation for Σ (procedure ComputeelRRerrsentttiiii an appropriate rescaling of the covariates, Lemma D.4 immediately implies that D gives 41- representation for the empirical covariance E. The main result then follows from concentration of E and sparsity of the elements of the dictionary.
in Algorithm [5). Up
Theorem D.5. Let n, m.t E N and let E X n be a desitive-definite matrix. Suppose m Cogog n for a sufficiently large constant C. Let XI..... Xm N NO,, Σ) be indepen- dent samples, and let 'D be the oulput of
((X,,.... X,),1). Then
[D) < {(nn'1122) and every element of is t-sparse. Also, with probability at least 1 (-(mm the time complexity of the algorithm is O (logn) m())) and 'D is (t, Cstrept 3/2 log n)- f é-rrppresentation for E. for some universal constant Citrep
Proof. Let = = Let D denote the intermediary dictionary constructed by the algorithm using RepresentVectors. (). With probability at -- the successful event of Lemma D.4 holds. By standard concentration bounds (see e.g. Exercise 4.7.3 in (41), it holds that 2 ||=||>> S ||al| I 2 ||=l|s:: for I-sparse x R", with probability at least 2(m)) Henceforth assume that both of these events hold.
Time complexity. The time complexity of the algorithm is dominated by the call to RepresentVectorscC O(n ((11/)())))0g n) o()).
By the guarantee of Lemma D.4 this takes
time
Correctness. The bounds [D] and sparsity of elements of D follow from identical bounds for D (see Lemma D.4), and the fact that every element of D is obtained by rescaling the coordinates of some element of D. It remains to show that D is (t, (t logn))-(z representation for Σ.
Fix any t-sparse E R", and define ē De. By the guarantee of Lemma D.4 since 7 is also t-sparse, there some a E _d such that EiED ad and
Σ logl deD
d.
4
$ 0 logn)
02
4
1
l1
l
1=1
30

---

Algorithm 5: Sparse linear regression for arbitrary 2
Procedure Spareeelinnnrroegressiooo ((X,, y:) B, 0²)
D ComputaallRepreeentaiiooo ((x (X1,-... 1000 log n
for j = m 2 ,, do
for d E D do
Xidd
[, d (2/m) (x, xx,
/* See Theorem A.7 for definition of MirrorDescentLassoo) and Theorem D.5 for definition of Ciree
MirrorDescentLasaa ((1,, v1) 20 BB m/2, o²)
+
w t EXED ELED (2/m) Em d),
return 1
But note that Dau, || ll2 by for all i. Similarly, every DD corresponds some d 'D with d, l1q.l12 d for all Thus, reindexing a according D the natural way, we have that EdED and and
n
Σ aal
Σ d,q.
S S logn)
Σ
DED
But now let E 1x 1xx X. For any i,j E [n] we have (4:, 9₁) = mm Hence,
Σ
Σ
wu = Tiv
1=1
(.E((n)
and similarly for |Σ degel 11. Thus, we get
Σ dED
aal ||d|| I Ott3 log ||ulls
But as shown above, we know that 1 ||>ا| I ||r||s: I ||ا|| for all t-sparse x E R". Since v and all d E DD are t-sparse, we conclude that
2
laal ||d|b> S 0(13/2 log ||/||
IED
as desired.
We finally restate and prove Theorem 3.1 as corollary Theorem D.5 and the well-known fact that standard "slow rate" guarantees for Lasso (i.e. based on the f norm of the regressor) can be achieved in near-linear time (Theorem A.8 The pseudocode for the main algorithm given in Algorithm 5)
Corollary D.6. Let n. m, t, B E N and o > O, and let Σ n. X n be positive-definite matrix. Let Suppose m Z C't n for sufficiently large constant Let (1) be independent samples where X; N((, Σ) and y; (X,, w NO, o²). Then there is an O(m2n'11723 - (01//)) log O(t) ni)-tmme algorithu (Algorithm 5) that, given (X,, y t, B, o², produces estimate v IR" satisfying, with probability 1 oT).
w T be t-sparse with ||l' II
(0 0² m
BB3322
+ B2t
|| - w 11
S
mm
Proof. By Theorem D.5 holds with probability n 1100
100s that D (1, Ctrep /3/2 log n)-
representation for Σ. Also, by standard concentration bounds (e.g. Exercise 4.7.3 in (1)), have
31

---

| < | s 2 ||:|| for all I-sparse E IR" (where == 2 Em XxX;)) with probability
at least - exp( (m())) Suppose that both of these events occur.
For each of the remaining m/2 samples X,, compute X3 E R.P where the entry Xj.d correspond-
ing to d E D is (X;,d/ {] (where Σ = 2 Eee X;X, is not explicitly computed; since d is sparse, both (X,,d) d) and |[d||s l: can be computed poly m) time). Let (O, denote the distri- bution of each Xz. For each d E 'D since d is L-spanse, we have that EE-NO,,) (2, d/ [[d]l))² =
/ |d]] S 4. Thus, L'a S for all d. 13/2 C log(n)) || lls. Define 3 E Ied by Ba = Old lIdlls. Then w" Ex Bad/ ||d||s and
Moreover, since w" is t-sparse, there is some IP with w' Ea and Es laal I|d|x S
Σ 13 2 Σ loaa |d S 2Chrrep 83/2 log(n) -1ww
But now for any of the remaining m/2 samples, we have that
(X,,3) E(x,, d/ [ddls)aa IId|s= = (X,, Σ aad) = (Xj, w))
and thus - (X, B) ~ N(O, o²) So we can apply Theorem A.8 to samples (X Uj U;) j=mm2+11mm+1111 to compute an estimator 3 satisfying
0² ( +
BB/22
Bag
B B 3 S
m
Vm
m
using that ||3|| I 2// (02gg()))))))) ||l* 11
< 2Chtrep 13/2 B log(n), and using the bound
maxa Idd I 4. The time complexity of this step is Ó(ID) m2 (mm2n(11/2). Finally, com-
pute ú == Ea Bad/ [|d|l. We have that || w" >
B 3
which completes the proof. O
E Fixed-parameter tractability in and t
In this section we prove Theorem 3.2 which shows we can achieve upper bounds on Ni, (E) for a independent of and n, if we are willing to incur dependence on k in the resulting bound. In fact, we actually prove an upper bound on the packing number Pr,a(()..
To achieve this, the first key idea is to consider the dual certificates for a packing. Suppose that u1,..., UN are unit vectors (in the E-norm) with (us, ry>x I a for all i + j. Then (0,, Ev;)1 2 maxjjx (v,, Ee,}l, so En; certifies that any linear combination v; Σÿfı Ky شyリ must have the property that ||>]]] 2 a- Thus, to show that there cannot be a large packing of sparse vectors in the E-norm, it would suffice to prove that any large set of sparse vectors must have one vector that can be written as a linear combination of the remaining vectors, where the coefficient vector has small & norm. In fact, this would give an upper bound on Ng.a (E) for all Σ.
We do not know if such a statement is true. However, we can prove an approximate analogue. The following lemma shows that under condition number bound on Σ, the dual certificate argument can be generalized to require only a weaker property: that any large set of sparse vectors must have one vector that can be approximately written as a linear combination of the remaining vectors, with low E cost. The approximation error determines how small the condition number must be:
Lemma E. Let n, N, 1, T E N and let > O. Suppose that for all t-sparse vectors U1,..., PN E RR, there exists some E [N] and x E B& such that |0]], S T and
1/2
Σ マイリ j
< max |10y122 JEIN]
Then for every desitive-defintte matrix Σ n with <(E) < 1/(48?) it holds that Po./(37) (E) N loga k k()).
32

---

Proof. Fix a positive-definite matrix Σ x and suppose that := := P(11(33) > N Vlog R: R(E). By definition, there are nonzero t-sparse vectors " UK R. such that
(o,, uy)xs -
37 || وn ||u
for all i + j. Without loss of generality, assume that ||u:l|2 = 1 for all i E [K], so that
miin (2) S ||u:llss
S Xmax (E).
So we can partition [K] into log2 x(E) buckets such that m |ll.lls/ / /inne 10:11 < 2 for each bucket B S [K]. There must be some bucket B with [B] 2 N. By assumption, there is some
i B and E RV such that ||0||] s T and
Σ jER:jşi
Egly
S.
2
Now
(0), 01)x =
Evi; Σ
Ijly
+
Evi, Ui
Σ
JEB:J
JEB:jæt
Σ 1y(1 U)) +
Eugg
Σ 13gyg
jEBijii
JEB:jAi
$ ||=|||
max jEB:ji
(00, u5)sl 1 ||0,7 2:112
||æl|
max
|1::1y ||5 5. Amax (E) . 02 Evg
3T jeBij
22 |oull + |olllx 8. Amax (27).
Simplifying, we get || S 25 Amax (E). Since also |1ll| 2 Amax (E)/ /min (E) 2 1/(48").
Amin (E), it follows that k(E)
remains to show that the precondition of Lemma E.1 can be satisfied for sub-constant ō without requiring N to scale with n'. We start by proving the desired property when the vectors are all t-sparse and binary, i.e. vI...., uN E 10.1)" and afterwards we will black-box extend the result to the real-valued setting. Concretely, given sparse binary vectors Vi...., uN E {0, 1)" (with N > n), we want to find one that can be "efficiently" approximated (in &g norm) by the rest, where "efficiint" means that the coefficients have small absolute sum. Thinking of each vector as the indicator vector of a subset of [n], a first step towards an efficient approximation for v; 1 S.) may be constructing an efficient approximation for standard basis vector ej for some j E S;.
Indeed, there is some j E [n] such that S := Vig = 1} is large, i.e. | 2 N/n. the vectors (ui)sess were in some sense random, then the average [ST Eiess Vs would be a good approximation for ej. It is also efficient, in that the absolute sum of coefficients is 1. But of course the vectors are not random; it could be that many vectors in S also contain some other coordinate j'. In this case restrict the set of vectors containing both j and j'. Now we may hope to approximate the vector 1[- E (i.j") ]. Completing this argument, we get the following lemma which states that there exists subset of [r] that is contained in many of the vectors, and that is appl-appro by the average of those vectors.
For notational convenience, for vectors x, {0, 1 we say that x 3 y if x; y, for all E [n]. Lemma E.2. Let n, N, W, E N with sn < N. and let U1,..., UN E {0. 13" be nonzero t-sparse binary vectors. Then there is some set S C [N] of size |S] 2 s and some nonzero vector u. E {0, 1) such that u 3 for all i E S, and
S
SES
2
33

---

Proof. For each J _ [n], define S := fi [ bi =1 Aj J}. Since all v are nonzero,
there is some jr E [n] with 815"1 2 N/n. We iteratively construct set J S [n] follows.
Initially, set J = ( j. While there exists some E [n] \
such that [SJu(a)] > (sn Bon/N)"/1S*
update J to U {a} (if there are multiple such a, pick any one of them arbitrarily). At termination
of this process, we have |S'| 0. Since every et is t-sparse. it must be that J| I t. Thus, |8" (N/n)) (sn/N)(t-1)/ 2 Set S == S and == 1, E {0, 1)" By definition of S we have that u 3 22 for E
For any j J, we have Uj = 1 =
1 [s] Eies Pij. For any j & J. we have uj = 0 and
{i S v.y -
I (sm/N)
Vij
S
|S|
|
iE
by construction of J.. Thus.
(sm/N)1/t
u
S
IES
8
Additionally,
U2
<
|1:l11 S L.
IS
S
S
EE
iES
iE
By the inequality ||>:1/
||0:||
|
bo
we conclude that
1
t(snn/N))
22
S
I
iES
2
as claimed.
We now use Lemma E.2 to show that if N is sufficiently large, then at least one of the vectors uy can be efficiently approximated by the rest. The proof is by induction on t. As a first attempt, one {0, 13"h and some large set S C [N] such that 3 for
might use Lemma E.2 to find some all i E S, and the average of the uy's approximates u. Then, restrict to the vectors in S, and induct on the (t })-spa residual vectors {o, approximated by the other residuals, then since u can also be efficiently approximated, we can derive an efficient approximation of v; by the remaining 2y 's.
i E S}. If one of the v; u's can be efficiently
This doesn't t quite work, since at each step the induction the set vectors will become smaller by a factor of roughly n. However, instead of throwing away the vectors outside =: 5(1) we can iteratively re-apply Lemma E.2 to get disjoint sets 5(1), (,,,)...,, S(m),, where each S(a) has the same property as S (for some potentially different vector (())). We can then induct on the residual vectors Un {ui (0)) i E S(a)). J. This suffices to efficiently approximate some Since we throw away fewer vectors at each step of the induction, we not need the initial number of vectors N to be large.
We formalize the above ideas in the following theorem.
Theorem E.3, Let n, N,t E N and let U1, ....... Uy E {0, 1) be t-sparse binary vectors. Then there is some E [N] and x E N such that ||x]|] S 3' and
Σ jf1
S 4' 9t(tn/N)
Proof. We induct on f, observing that the case = is immediate. Fix > and t-sparse vectors (UI...., ) {0, 1)". and suppose that the theorem statement holds for f - 1. If any is identically zero, then the claim is trivially true with x = I S +3*+1 n then the RHS of the desired norm bound exceeds 4t LL, so the claim is trivially true with x and any E [N]. Thus, may assume that all 2s are nonzero, and N 2 tzt+1, Applying the previous lemma with
34

---

s 3 < N/n gives some S())
_ [N] and nonzero u()) E 13" such that | 2 3 and
u()) I v for all i E ((1), and
$ V 9t(n/N)1/
|
2/ tES
If - - | 2 N/t + then can reapply the lemma with vectors (M)) and
8 = 3 to get some 5(2) C [N] and E {0, 10. Continuing this process so long as there
are at least N/t 2 3 n remaining vectors, we can generate disjoint sets 5(1) ,...,, $ [N]
and vectors u (1), (m)) E {0, 1]" with the following properties:
ii (5(1) ( > N N/t
(ii) |S() 2 3 for every a E [m]
(iii) For every a [m], it holds that (()) is nonzero and u(() 3 oy for all i S(a)
(iv) For every a E [m].
(aa)
V 9l(ln/N)1/
[Sta]
iES(o)
For each a E [m] and i E 5(a), define of : 0. (a)) By Property (iii) we have that of E (0, 1] and of is (t !)-sparse. By the inductive hypothesis applied to vectors (t).esss.....si there is some E ((1) U... U...U. S(m) and x' RN (supported on ((1) U... U gim)) such that || 3 and
1/
Σ o/ j
<4- V 2 1)((t 1)n/IS()) U... u... Stmi))2/((-1) U..
(((t-)(((-
< 44 (l((n/N)a/
where the last inequality uses Property (i) and the bound N > in. Of course, without loss of generality of 0. Let [m] be the unique index such that i E S(a), We define 1]
(supported on ((1) U... U ((m)) follows. For each E [m] and each S(0), set
1
3T
S5
SS(
JES()
Since ||''|| 3 we can see that
| < ||''||
Σ
|S(b]
[S(]]
bE [m] rest
JESU)
rESta)
< 1 +1
2 +1.
Next, we use x to approximate
The following bound is almost what we want:
Claim E.4. |oo ΣjE(M 2,03
/|,
<3 41
/9t(tn/N)Iz
Proof of claim. We have
84 Σ Fy
S (a)
Sta)]
Σ
Ur
+ 1
S(a)
Σ
Ur
Σ
Fy
rE[N]
(t)
g()
rE[N]
35

---

Staj
Ur
+
1/
Σ
E
|ttb]
Σ
rESta)
rE[N]
be [é[m] rest))
jESCN
Σ Up
of
Σ
Sta]]
rES(a)
rE|N]
Σ
Σ
Σ
+
|Ktb]
bE[m] rES(3)
bE/m] rE
JES(()
2
((a)
[S(a]
Ur
o
Σ
rES(s)
TE|N]
Σ be(m) JES())
(0)
Σ
+
S5
Ur
rES
where the first and third inequalities use that u, o/ + (0) for all E 5 and throughout we use
that xr x = 0 for r & 8(1) ((mm) Applying Property (iv), equation ( and the bound
||<e 11 S 3 we get
U/ Σ
S / + 4t-1 VM(tn/NN)/+++ + +3 Ve((tn/NN)
Ir Ur
rE[N]
2
3 4' 100001/96tm//0/// 9t((nnNN)
as claimed.
However, we wanted bound on Ezzt Uy and unfortunately * 0. Fortunately, is enough that 2; is bounded away from 1. Since x = 0, we have
|
30-1 30+1
|2a||
<
<
Sta)
[S(J]
St(a)
9
JES(a)
Thus, by Claim
E.4
1
3..4 13.4"'1/ (9((tnNN)1* < 4' /9ttnn/N)
1/
S
jti
Finally, we have ||z/(1- =; < (9/8)
3- 1) 3", x x.)) satisfies all the desired
conditions. This completes the induction.
Finally, extend Theorem E.3 to real-valued sparse vectors via discretization argument.
Lemma E.S. Let n,, N,t E N and let U1,...,UN UN E 1nn be t-sparse vectors. Then there is some i [N] and Rn such that |æ]|| S 3' and
Σ 2yy j+i
< 4 4 ((nNNN)((1))
max JE[N] ||151b,0
Proof. Without loss of generality assume that maxje[N] |1o = 1. Let t E N be fixed later. Define map s [] + {0, 1] 12 by
Cx+1+[ok]
if c < 0
pp(c)
Ck+l
if c = 0.
[k+1+[ek]]
if c > 0
36

---

Also let & : R2=+1 - R be the linear map that sends Pe; + (i - k - 1)/k for each i E [2k + 1]. Note that (c) cl 1 1/k for all c [-1,1] and 4p((0)
Define Loun [-1, 1]
{0. (2(2+11)n by p(c......G.) = (p(c),..... ..... (en))), and define क5n {0. (2(2++1)) - I by
gen (I1,..., Fa) (0))),... ((xx)). For any E [N], the vector (v;) is t-sparse and lies
in {0, (2(2++))m Thus, applying Theorem E.3
gives some E [N] and E R with ||||| S 3 and
(w:)
(u;)
Σ
xyp en (vz)
4' 44V (t ( 1)/N)
JFL
Since d Rn is a linear map and
||
11
S 22k + I, we then get
eommmnu (vs)
Σ x, x
< < < 90 1)(mm(2 1)/N)1/
But for every j E [NT, know that
||0/ 4 mm
sn (1))
Σ aEsupp(1;)
(Ujo - )b(()aa)3 t
k
We conclude that
Σ
8m
(ws))
Σ
x r
on
(1))
+110; - 1 x on (1;)11
pm
3
jz
+
Σ
Fzy |10/ - 1 nn
((())))l2
en
jf1
Vt
< 4'v 92kk + + 1)/N)// + (1+3))
k
(2k + 1) ++ V(nnNN)ven 4'vE
k
Taking A = (N/n)2/(10 gives the claimed bound.
Combining Lemma E.5 with Lemma lets us prove Theorem 3.2
Proof of Theorem 3.2
Set 5 11/(4)) and N 410(++) 22 By Lemma E.5 for any
t-sparse vectors ......, UN E R= with |elll2 I for all illie e [N], there is some i e [N] and E I=" such that ||=||| S 3 and
U4
Σ UJU
1 V(n/N) <
4VR
<.8
jitt
It follows from Lemma E. that Pe.1/3+11() (2) & N logg k. Finally, by Lemma A.2
we conclude
that 1/344 (E)= & N loga K.
F Generalization bounds
F.1 Finite-class model selection
Lemma F.1. Let n. m, neg E N and let Σ, be a positive semi-definite matrix. Fix a vector w² E T and closed W C Rn and let (x,, be independent draws X, N(0,E) E) and yi (X,, wo) + & where & ~ N(O, Pick
④ E argmin [Xw- v112 WEW
where m X n. the matrix with rows X1, XI,..., Xm- For any e, E (0, 1),1), suppose that with probability at least - 8, the following bounds hold uniformly over E W:
37

---

1.
|| w1)l 2 11w w1
S < w
m
2. (5, X(--w-] |<<wow>>Ta> Mot.
Then with probability at least 1 - it also holds that
| w" 11 S V I T+
2n
inf wEW
|1 w" + 20
Proof. Consider the event in which both bounds hold. Let Wopt argmin |/we w" Then
| w²) 102 || |x v1l2 + 2 X( w²)) ||&1|2
< Kwopt u12 + 2(, [( - -w") - |1El12
X WWot w =1)l X(x w")) 2({, X(upp w²))
- X Wopp w ">)112 + (I) - =2)ll2 + [ Wopt w 112)) a /vnnn-
Subtracting [[(oo w" )l{ from both sides and dividing by || w" )l2 + ||x(wope w' 1|2 we get that
[( w 112
[xx( w²)) "=)ll2 20 /neil
follows that
|| wt w0llx= I
|x(10 w w=)122
(1 e)m
(1 + e)
[X(Wopt - wn'll + 20
(1 e)m
2nehf
||
f15 + 2
m
as desired.
Lemma F.2. Let n. E N and let E, be a positive semi-definite matrix. Fix vector w" R. and finite set W C I2" and let (X,, (.) be independent draws X; ~ NO, E) and yi = (Xi, w + Ea where & N(0,0²) Pick
à E argmin |xw- - -
wEW
For any 8 E (0, 1), ifm= 2 86 ll then with probability at least 1 26, we have
1+E inf
log(2/W//0)
||0 wn 1bx <
||w
w 211sx 4
wEW
m
Proof. For any fixed W. the random variables (X,, w²) N(0, w| w= ( are inde-
pendent, and therefore [X(w w 1 ~ ||w - w/ w1 X2. It follows that for any c > O.
Pr
1 m
X w² 11 ||l " 1 ||w w'1l
s 2e mc²/8
By the union bound, if m 2 8c- (l then with probability at least 8 holds that for all w E W,
1 X w²) w0 || w < w|l w" w²1
(10)
m
Also, for any fixed W, conditioned on X, the random variable (E. [[((
X(w--" w IT,
has distribution
N (0, o²). Thus, by a Gaussian tail bound and the union bound, we have for any t > 0 that
X(w (s,
w²) X(w=w"> -
2 at < 2|W1 e -012
Pr
max WEW
[X - -
38

---

In particular, with probability at least 1 - it holds that
| 50/21og(22110))
X w w²)) X w w=*)
max WEW
5,
(1I)
Using
10
and
11)
apply Lemma
F.1 which gives the desired bound.
F22
Weak learning
Lemma F.3. Let n, m E N and é, > O. Let Σ n n be a positive semi-definite matrix and ((, E). For any fixed u, IR", if m 2 Se -2 log(8/8), then it holds with probability at least 8 that
let X m x n have independent rows XI,...,X,
x 2) - 2E ||lll |1el|
m
Proof. Decompose u av + w where (v, w)r - O, so that - (u, u)2\/ |10|s: Since |xee| 2 ~
[|lll Xm and m 8c 8c- log(4/6) it holds with probability at least - 6/2 that
o (1 -
Ex, 0) 1111
S |10|
Next,
T
1 1 - Σ m
X, w/ (X),0)
1
(Z 1/, (Zi, I112
m
where we define independent random vectors Zı.... Zm N(,0 In) so that X; /,1/2 Since m 2 8 log(2/)), with probability at least 1 - 6/4 we have Σm (Z₁ ///²0) < 2m || Condi- tion on the value of this sum, and note that since 122 1 ///22, the random variables (2,, //
are still (independent and) distributed as N(O, (1-)) Thuus
Thus
0, 1 m
12, 12,,21/2 w) (2,, 21,2) ~ N
Σ
Iwll (Z (Z, ///22
When the variance is at most //ll 13 |101 /m, we have with probability at least 1 8/4 that the sum is at most 2 || ||u]| / (og 8)/m in magnitude. So, using m 2 Sc log(8/6) it holds unconditionally with probability at least 8/2 that
1
Zz, 1/ /2/ (Zz,
S 1|lllx ||illx (Z,, E1/30)
In all, we have that
IuT (1 m
x 1'1xxxx -2) I lale Ilul + 11 |1ll S 2e Re||ullz |1u|l
using that |a| S ||ulls/ / |/lll and || S ||u||s
Lemma F.4. Let n, m E N and let E be a positive semi- refiniee matrix. Fix a vector w² E Rd and a
finite set W C R and let (X,, y.m be independent draws X; NO,, Σ) and y, (X,, w²) + &,
where & ~ o2), Pick
(w. 3) E argmin [18Ku - - weW
BER
Suppose max
(w, has || l|w Bg
O. For any 8 0. if 2 Co Ca-22 log (o2(W/ for
sufficiently large absolute constant C, then with probability at least 1 1-6
|8:0 wn [|3
1/00311 12 + 400e log (4/))/88
s (1 a² /24 ||0"
amm
39

---

Proof. For any vectors u, E R", define ((,,)) =u (1xx
Claim F5. With probability at least 8, the following bounds hold uniformly over w E W and
3 E R:
1. (: [|x - -00 )112
X(Ow-
S
o Moj where ney == 2
2. (Sw, w²)l 5 100
|/wllls |,0
3. (Bw,, Bw)l S
a 100
2
Proof of claim. For item (1), fix W. Let p((), 2 x m be matrix whose rows form an orthonormal basis for span Xw C R Then (denoting the unit Euclidean ball in I² by B2) we have for all E that
X(Bw w²)) Ks E, [x - w=)) w=)lba/
S
sup BEB,
(s. (B(1))) u)) - [(()g {
S 22 max ( (o(")) .
(1)
(E[2]
Since (Tb (w) .E ~ _N(0,00) we have Pr[l 5) o /2ogg 4 < (/() A union
(w)
bound over E [2] and W gives that condition (2) in Lemma F.l is satisfied with probability least 1 5/2.
For items (2) and (3), note that A is bilinear, so it suffices to take 3 = 1. Applying Lemma and
the union bound, so long as m 2 Ca 1og(32|W)] / for a sufficiently large constant C, items (2) and (3) hold simultaneously with probability at least 8/2.
Henceforth we assume that all of the events in the above claim hold. Let wo E W be such that (wo, >>l = a ||wal| ||w" Let 3o = (wo, w= )x/))/////// [| 12- Then
||3,wn
w" w0ll 12 (1 - a²) 1
Claim F.6. The excess empirical risk can be bounded as
|x(3i - w²) [|x(wo w² 212 20 nug.
Proof of claim. We have
2 + 2(5, X(3r0 w²)) - 1K |x(30 - wn)) 11/- XBO - /
< 188o000 - v1l2 + 2(E, X(3r0 - -w") - ||5112
[X(ooro w² >12 + 2 X(3re w²)) 2(S, X(Bono - -w²))
[ w" >12 + (
X X(3r w²)
+ || w=" =²)]la) / Dofff
where the last bound is by item (1) of Claim
F.5 Simplifying, we get the claimed bound.
Now we have
2
X(300 wn)) w²)1/2 A(30 - w², -", 9r00 w*)
Bro w²
15
(1i0(30000 - w2)ll2 + 20 22 mell) A - -w", Büü w²)
m
1 + a²/100
Nene
| w² + (1 + 100a
A w,,,
Bro -,,Brr w*)
σ² 22n
=(1 + a² a²/100) 11,0wb w" u0113 11 + (1 + 100a 2)
m
a²
A(30 - - 3r0 w²) + 1 1+
A (Bywo - =",,, ,000000 - w²)
100
40

---

(1 + a² /1000) 11,0 000 w" w"1 + (1 + 100a -3 n
m
+ (3rr; Bro)1 + 2 2 w²))
(1 a² 100)0000 (B) 20 + 2(1 + aa/100)) (8 w*)l
(a² /100) ( ("", :0")) :1
where the first inequality is by Claim F.6 the second inequality is by AM-GM, and the final in-
equality is expanding out the terms A w", Fr w²) and A(Sowo w Bowg =²) (via
bilinearity) and cancelling out the common term A(w", w*) Finally applying items (2) and (3) of
Claim F.5 get
|B0 w² 2 S (1 + a² /1000)
- o'natt
|/
w011 + (1 100a -3
w=
a
a
3ri 1|w0
+
+
100
50
a
1130w
+
11/oowolls
1/ 11 +
||0*11
50
25
100
10102ner
$ (1 - 9a?
/10)
||00
| +
a²m
|م0
+
||300]
w= [| x. ||=
(12)
100
50
where the second inequality uses the bounds ||3owo
(1 a²) || and
(wo, w >xl
||Bowollz
||
||wll|
But now on the other hand,
| - w- |
3r0 x:
+ 110212 2(Bro, wn w0)> 2 |10 + |100 + 2a |30
||=*|lx
Comparing with gives
(1
a 100
3:0
101o
a²m + 3x Bro
1 lls:
and therefore
101 a²m
Bu 5
S 4a
11 11x + Vov
Substituting into 12 finally get
(1 a²/2) 1|0 1 200g nan
|Bw w² 3
a²m
as desired.
F.3 Excess risk at optima of additively-reguulrrzze programs
Lemma F.7. Let n N, and let Σ n be positive semi-definite matrix. For some seminorm
Φ R. + [0, oo) and some p. O, assume that with probability at least - over G N Σ) it holds uniformly over Ih that
(v, G) S 2
((v)) 1olle
Fix a vector v" R... For any m E N and o 0 (X,, ye be independent samples distributed as X; ~ NO, Σ) and = (X,, u²) + E where E, ~ (0, 0²), Define
argmin || 211 + (v))2 + ||v||2 4(v) eER"
where X : m is the matrix with rows X Xi...., Xmm Then with probability at least 1 78 over (X,, y so long as m 2 16p + 196 log (12/6)), it holds that
128a2p p 8(0 + || 1b (v=))
6 - v 1 <
m
41

---

Proof. For notational convenience, define F(u) == (1/2) -2)+ vpll lle - l'1ss. We apply the lemma's assumption twice:
For any fixed E, the random variable X has distribution (N0,, ||||] Σ). By the above claim, with probability at least - 8 over X, we have (E. X(e v²) ||El|2 F(v) uniformly in V R".
Since || 12 o2xm and m 2 8 log(2/))) it holds with probability at least 1 - that ||11|2 S /20.. Thus, with probability at least 1 - 20, we have
(E:X(v - u²)} S V2moF(v)
(13)
uniformly in R"
The assumption means that we can apply Theorem C.1 with (noiseless) samples
(X,, (X,, 0²) )=)))= to get the following: since m 2 196 196log ( 12/6), at least 46 over the randomness of X that for all E R
it holds with probability
2 [X(e 0 11
2 m F(U)?
(14)
We also observe that the entries of y are independent and identically distributed as N [N || +o²),
so by a x" tail bound, since m 2 32 log(2/8), holds with probability least 1 - that
1 (1|= + + 3 (100 o2) -
1
lbl2
E
(15)
We now condition the event (which occurs with probability least 1 76) that the bounds 14 and (15) all hold. Specifying (14) to == é, we get that
13
< |x " )1 2
< |x(( - "² u²)1 | - v12 00)) Ilvl22 4(0)
+ |Xxe" - - - +
110l, 2(0))(()))))) +
2(Xv" y. X(0 v()=
(6)) - |1v||2 (6) + (1 (()) F())2
I 22m F(0) (0)) |ul| (0) (())) ||ull x(v") + F(D)
where the first inequality is by [4 the second inequality is by optimality of 6, and the third in- equality is by (13p. We now expand F(6) in the above expression. If /2mpo l|ē l*Ils exceeds
8 | 20 و/ then the lemma immediately holds since
128o2p
| 001
10---11 <
So we may assume that in fact / 2mpo ||0
0011z
m | v 1 By the lemma assumptions, and applying these bounds.
we also know that m 2 16p. Thus, expanding F(u)
m 6 - 0² 111 < v 2mo
4 0*) + vbllē - o 8'l1s)
2
2
(0)) - lull (0) + (10)² + llvll2 +b())
4 w-)² + 2p v'1
+ 2
m
m 2 000(6 -²) |m | 1
2 - |ul| 2(6) + (2 |lvll2 21²))
42

---

+
( w² + m
8 |/0 v² 00
Simplifying, applying the triangle inequality Φ o*) S (0) + +(v²), and grouping terms,
get
m7
0
8" I
4
m
(V
m 20 [1all2) D(v") 2
11v122
(
2
2( - V 2 2T(x*)2
where the last inequality uses both sides of the bound [5
G Covering bounds from classical assumptions
In this section, we further motivate the definition of our covering number Ni,a (E) by showing that in all settings where efficient SLR algorithms are known, there straightforward linear upper bound on the covering number. This lends weight to the need for stronger upper bounds on Ne. as a stepping stone towards more efficient algorithms for sparse linear regression.
G.1 Compatibility condition
Definition G.1 (Compatibilityy Condition, see e.g. [0]) For positive semidefinite matrix E nxn,
I, 2 1, and set S C [ri], we say has S-restricted & eiggenvalee
|S|
(w, Ew)
(E,
min WEC(S)
|us 1
where the cone C(S) is defined as
C(S) = w + 0: || ll s L|]
Fort t E N, the t-restricted eiggenvve x² (2,E t) the minimum over S of size most
well-known that an upper bound on max, E.g is sufficient for the success of Lasso (as well as (=1,14)
nearly necessary; see e.g. the Weak Compatibility Condition defined in (23)):
Theorem G.2 (see e.g. Corollary 5 in (45)). Fix n, m, E N, or O, and positive semi-definite
matrix Σ X n with max; Di < 1. Fix t-sparse vector v" E R" and let (Xi, y:). be independent samples distributed as X, ~ N(0, Σ) and yi = (Xi,v") + Ee where & ~ ((0,0²). Define
dE argmin
| v12
where : m X n is the matrix with rows X XI.... Xm. mf 2 40² llg(166n/5) then with probability at least - 8, it holds that
| 16-w- 16-0 ( (o21lg((66n/0)
(E,,t)m
Fact G.3. Let t E N. For any positive semiidefinite nxn with @² = (E(,t and max, Σn S it holds that No No (2)) S
Proof. The proof essentially the same as that of Fact Fact By Lemma A.3 suffices to show that the standard basis is (t,
for Σ. Indeed, for any t-sparse R2" we have
wel leells S || max V /t [|lls
claimed.
43

---

G.2
Submodularity ratio
Definition G.4 (see e.g. 19) For positive semi definief matrix Σ n x n and set S [n] define the normalized residual covariance matrx I(4) n n by
y (1D13)) (2- (ー-2AE1121) (
where D= diag (I- EE
=
Definition G.3. Fix positive
matrix E n x n, a positive integer E N, and any 0" R". Define the t-suboodularity ratio of E with respect V" by
(EED) ysv Slst (E*) (E (E (E())su*
m(E,0")) :=
min
In any 1-sparse linear regression model with true regressor v², when the above quantity 7 == Th (E,, v²) is bounded away from zero, it be shown that the standard Forward Regression al- gorithm finds some t-sparse estimate 0 IR" such that | "1 se- [|e* 1 (see e.g. Theorem 3.2 in [9]; that result is for the model where the algorithm is given exact access to (u. v" b²)>; for any t-sparse E RR", but analogous finite-sample bounds can be obtained with O logg(m) sam- ples by applying the theorem to the empirical covariance matrix and using concentration of x submatrices). A similar guarantee is also known for Orthogonal Matching Pursuit (Theorem 3.7 in 9
Once again, it is simple to show that the standard basis is a good dictionary for matrices with large submodularity ratio.
Fact G.6. Let n.t N. For any positive semi-definite Σ
with
min," (E(E, v"), it holds that N N (E) Inn n.
Proof. We show that the standard basis (t, 7/t) (itt)ddcctioaryy for E. Without loss of generality assume that Σg = 1 for all í E [n]. Then E(1) = E. Fix any t-sparse v* E R". Setting == supp(v"), we have that
Σ 00 = - ( Egv 2 ((0") T (Ess) RSS
(Ess) Ese" = 1|
where the inequality is by definition of y, and the final equality that Esn" Egs(v")s (since o" supported on 8). follows that maxissle, 0²)3 2 (x/t) ||v**1 Since ||e/lls: 1 for all i, we conclude that
Ke, v / |eilix 10 11
V Y
max KE|n
as claimed.
G.3 Sparse preconditioning
Recent work 23 showed that if n X n is positive definite matrix and the support of θ = Σ-1 is the adjacency matrix of a graph with low treewidth, then there is polynomial-timg
sample- efficient algorithm for sparse linear regression with covariates drawn from N(00 Σ). The key to this result was proof that such covariance matrices sparsely preconditionable: i.e., there is matrix S : n x n such that = SST and 5 has sparse rows. We claim that this property also immediately enables succinct dictionaries.
Concretely, suppose that S has s-sparse rows. By change-of-basis argument, any t-sparse vec- tor in the standard basis is st-sparse in the basis {(ST)= ..... (ST) > Moreover these vec- tors are orthonormal under Σ. Thus, by the same argument as for Fact A.4 it's easy to see that {(ST ".....,(SS" (ST) } is a (t, (t)sss/dicitoonaryy for E.
44

---

H Supplementary figure
1.0
0.8
0.4
0.2
100
200
300
400
500
Number samples
Figure 2: Performance of Basis Pursuit in synthetic example with n 1000 covariates. The co- variates X110000 are all independent N(0. 1) except for (Xo, X1, X2). which have joint distribution Xn Zo. X1 = Zo + 0.421. and X2 = Zi + 0.4Z, where Zo, Z1, Z2 ~ N(0, 1) are independent. The noiseless responses
X2) + 2.5X3, i.e. the ground truth is 3-sparse. The --axis is the number of samples. The y-axis is the out-of-sample prediction error (averaged over 10 independent runs, and error bars indicate the standard deviation).
y 6.25(Xi
I Experimental details
The simulations were done using Python 3.9 and the Gurobi library 17 Each figure took several minutes to generate using standard laptop. See the file auglasso. py for code and execution instructions.
45


Reviews:
[{"review_id": "54Bo55vZPf", "reviewer": "Reviewer_EHBK", "summary": "This paper studies the correlated random design setting, where the covariates are drawn from a multivariate Gaussian, and seeks an estimator with small excess risk. This work provides a polynomial-time algorithm that, given Σ, automatically adapts the Lasso to tolerate a small number of approximate dependencies, and achieves near-optimal sample complexity for constant sparsity and if Σ has few “outlier” eigenvalues.", "questions": "See “Weaknesses”.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Sparse linear regression is a fundamental problem in high-dimensional statistics.\nThis paper studies a polynomial-time algorithm that automatically adapts the Lasso to tolerate a small number of approximate dependencies. In theoretical analysis, this work achieves near-optimal sample complexity for constant sparsity. The proposed algorithm fits into a broader framework of feature adaptation for sparse linear regression with ill-conditioned covariates.", "weaknesses": "1.If this work can provide experimental verification of the superiority of the proposed algorithm, it will be more convincing. For example, compare with the related work to verify the performance of the proposed algorithm in terms of time complexity and accuracy.\n\n2.In figure 1, when the number of samples is greater than 100, is the standard deviation of adapted BP algorithm zero?\n\n3.The presentation of references is not standardized, such as:\n\n[38] Sara Van De Geer. On tight bounds for the lasso. Journal of Machine Learning Research, 19:46, 2018.\n\n[22] Jonathan Kelner, Frederic Koehler, Raghu Meka, and Ankur Moitra. Learning some popular gaussian graphical models without condition number bounds. In Proceedings of Neural Information Processing Systems (NeurIPS), 2020. \n\n4.The organization and presentation of this paper can be further improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. To address their questions:\n\n**Q:** *``compare with the related work to verify the performance of the proposed algorithm in terms of time complexity and accuracy.''* We would like to emphasize that *no* prior work has addressed the problem of sparse dependencies among covariates, aside from the very special case where the dependencies have sparsity $2$. We did provide experimental evidence (Figure 1) that our algorithm achieves superior accuracy to Lasso/Basis Pursuit, the algorithm that practitioners would typically try. We did not experimentally compare with e.g. the agglomerative clustering approach mentioned in our related work section, since (as discussed) it's clear from first principles that this approach cannot succeed in our general setting.\n\n**Q:** *``In figure 1, when the number of samples is greater than 100, is the standard deviation of adapted BP algorithm zero?''* Yes. For each sample size beyond $100$, in all ten trials our algorithm achieves zero prediction error. Note that this is reasonable since the samples are noiseless.\n\n**Q:** *``The organization and presentation of this paper can be further improved.''* If the reviewer has constructive and concrete suggestions for improvement of the organization/presentation, we would love to hear."}, {"review_id": "irZTV9yBdP", "reviewer": "Reviewer_8yrN", "summary": "This paper presents an innovative polynomial-time algorithm for sparse linear regression in the correlated random design setting. The algorithm adapts the Lasso technique to effectively tolerate a limited number of approximate dependencies, resulting in both computational and statistical efficiency for covariance matrices with a few \"outlier\" eigenvalues. The proposed method is part of a more extensive framework of feature adaptation for sparse linear regression with ill-conditioned covariates and offers the first polynomial-factor improvement over brute-force search for constant sparsity and arbitrary covariance.", "questions": "1. The paper assumes constant sparsity $t$ for simplicity. It is unclear whether this assumption is necessary to establish the main results of the paper? In particular, it would be interesting to examine the case where the sparsity $t$ takes the order of $\\log n$.\n\n2. It is important to consider the more general case where $t$ is treated as a variable instead of a constant. I wonder whether the main results in the paper remain valid in this case.\n\n\n", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper contributes a novel algorithm for sparse linear regression, adeptly adapting the Lasso to accommodate a small number of approximate dependencies.\n\n2. The proposed algorithm exhibits both computational and statistical efficiency for covariance matrices with a few \"outlier\" eigenvalues, providing a substantial advancement over existing methods in this context.", "weaknesses": "1. The paper assumes constant sparsity for simplicity, but it is essential to explore the impact of this assumption on the main results.\n\n2. To more convincingly demonstrate the algorithm's computational and statistical efficiency, the paper would benefit from the inclusion of supplementary numerical simulations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. In case it was a point of confusion, we'd like to emphasize that our results do apply when $t$ is a variable, i.e. in Theorems 1.1 and 1.2, there are no factors of $t$ ``hidden'' in any constants. So for example when $t = \\log \\log n$ our results still yield state-of-the-art sample efficiency / computational efficiency tradeoffs. It is indeed true that when $t = \\Omega(\\log n)$ our results become vacuous, and it's a very interesting direction for future research whether this limitation can be alleviated further.\n\n**Q:** *``To more convincingly demonstrate the algorithm's computational and statistical efficiency, the paper would benefit from the inclusion of supplementary numerical simulations.''* Certainly; this paper was primarily theoretical (with some simple numeric validation) but it would indeed be interesting to eventually apply to real data."}, {"review_id": "qGqKZxOrbP", "reviewer": "Reviewer_BTho", "summary": "The paper introduces an algorithm to solve sparse regression when the covariates are generated from a normal distribution with ill-conditioned covariance matrix, i.e. outlayer eigenvalues. The algorithm is based on feature augmentation where, meaning that the covariates are completed with well-chosen vectors, and is designed to provably achieve near optimal sample complexity in the studied framework.", "questions": "The ideas of experiments below may help provide more information on the practical behavior of the algorithm and put it into perspective with the theoretical results.\n\n* Could the authors provide the number of samples necessary to reach low risk with respect to the ratio $\\frac{\\lambda_{n - d_h}}{\\lambda_{d_l+1}}$ and with respect to the number of outlayer eigenvalues when using their algorithm and when using BP ?\n\n* Could the authors provide the computation time with respect to the number of samples in addition to the risk ?\n\n* Could the authors provide the size of the set $S$ obtained in practice with Iterative Peeling, and compare it to the bounds given in Lemma 2.4 and 2.5, with respect to the sparsity $t$ ? \n\n* Could the authors provide a comparison of the performance with and without the knowledge of $\\Sigma$ (estimated from samples v. known distribution) ?\n", "limitations": "The limitations are discussed by the authors.\n\n-----------\n\nAfter reading the other reviews and the rebuttal, I increased my rating.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "Regarding presentation, the paper is clearly written and presented. Each theoretical result is explained and justified, which makes the paper easy to follow. Regarding the content, the idea of augmenting the features by taking the data distribution into account before solving the Lasso seems new. The paper provides interesting theoretical insights on this method, while maintaining a computational perspective, for instance when explaining the design of the dictionary.", "weaknesses": "While the main contributions of the paper are theoretical, it would have been interesting to get more experimental details on the algorithm. In particular, numerical illustrations of the behavior with respect to the conditioning of the covariance matrix (number of outlayers, gap between largest and smallest eigenvalues, ...), and of the robustness with respect to standard algorithms like Basis Pursuit (for instance in \"phase transitions\" between well and ill-conditioned scenarios), may broaden the audience and the impact of the contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. In particular thanks for the good suggestions for experimental directions to consider. It's tricky to understand which instances are the ``worst'' practical instances for the algorithm. However we can give partial answers to some of your questions:\n\nFirst, regarding the size of $S$. We're actually not aware of any instances where in practice the size of $S$ will exceed roughly $d \\cdot t$ (number of outlier eigenvalues times sparsity). It would be quite interesting to understand if there is indeed a ``hard'' example for our algorithm or if there is a tighter analysis than what we were able to show.\n\nSecond, regarding estimating $\\Sigma$ using samples. Unfortunately our algorithm does not have a hope of succeeding when the estimated covariance is low-rank, because it needs an accurate estimate of the eigenspaces of $\\Sigma$ --- thus, we need at least $\\Omega(n)$ unlabelled samples (in addition to the $m$ labelled samples) to have any hope of success. Numerically, on our simple synthetic example (Figure 1) we do find that the algorithm works when we estimate $\\Sigma$ using $2n$ samples.\n\nThird, regarding numerical runtime. Our algorithm has two parts. The first part is dentifying the set $S$. This has runtime that does not depend on the number of samples, but depends on the dimension due to requiring an eigendecomposition of $\\Sigma$; for our example in Figure 1, this step took $0.65$ seconds. The second part of the algorithm is solving the adapted basis pursuit, which had runtime ranging from $0.12$ seconds (on average) when $m = 20$, to $1.8$ seconds when $m = 500$. The scaling was roughly linear in the number of samples. The runtime of the standard basis pursuit was very similar to the runtime of the second part of our algorithm.\n\nFinally, regarding the number of outlier eigenvalues. For our simple synthetic example, we observe that adding a second, independent sparse dependency does not double the sample complexity; in fact, it's essentially unchanged even with $10$ independent dependencies. This tracks with our theoretical understanding: the sample complexity is additive between (a) a component due to size of $S$, and (b) a component on the order of $t\\log n$. In our setting when $d \\leq 10$, it appears that the second component is dominant."}, {"review_id": "e6HkKpPW9x", "reviewer": "Reviewer_Ahsd", "summary": "This work studies the problem of sparse linear regression under the statistical model where the examples are drawn as zero-mean Gaussians with covariance matrix $\\Sigma$ and each response is a t-sparse linear combination of the examples plus i.i.d. Gaussian noise. While classical results establish that the LASSO can computationally efficiently recover a good solution v* with a nearly optimal number of samples when the covariance matrix $\\Sigma$ is well-conditioned, guarantees beyond this simple setting are substantially lacking, with a few notable exceptions. In general, not much is known beyond a brute-force approach of trying all $\\binom{n}{t}$ sparsity patterns, which requires $n^t$ time. This work shows that even if $\\Sigma$ is ill-conditioned, if Sigma is well-conditioned after removing the top or bottom O(1) eigenvalues (i.e. a notion of “robust” well-condtionedness), then this running time can be improved to roughly $f(t) \\cdot n^3$. \n\nWhen there are a small number of tiny eigenvalues, the main problem is the existence of sparse linear dependencies among the variables. The algorithmic approach to address this problem is then to iteratively peel off a small number of these variables at a time (IterativePeeling()). This procedure gives a construction of a small dictionary of vectors such that any t-sparse vector can be written as a linear combination of this dictionary with coefficients bounded in L1 (Lemma 2.9), which in turn implies that the LASSO identifies a good solution v in the sense of bounded excess risk. The authors interpret the technique of applying LASSO to an augmented dictionary as “feature adaptation”. ", "questions": "n/a", "limitations": "The authors have provided adequate discussion of limitations", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* Sparse linear regression is a widely studied yet notoriously difficult problem, and this work identifies a very natural class of inputs for which positive results can be obtained. \n* I find the discussion in Section 2.1 on the proposal of (t, alpha) dictionaries as a canonical abstraction of all existing approaches to sparse linear regression to be very interesting and valuable. It helps concentrate research efforts on this problem to this more structured approach, and I believe it may prove to be influential in following works on sparse linear regression.", "weaknesses": "* It seems like like there are no bounds on the sparsity of the approximate solution v that is outputted by this algorithm, probably due to the fact that the feature adaptation step augments the feature set with dense linear combinations of the existing variables (please let me know if I have misunderstood). Thus, the measure of the “sparsity” of this algorithm lies in the small sample complexity, rather than its ability to output a sparse solution. Thus, the guarantees of this algorithm are tightly linked to the statistical setting of sparse linear regression, and it may be difficult to adapt these techniques to the problem of outputting a good sparse solution to linear regression. However, I do find this limitation very interesting, and I wonder if there are gaps between the performance of these algorithms if one is required to output a sparse solution. Such separations are known in certain sparse recovery settings (see, e.g., https://arxiv.org/abs/1110.4414). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments, and for appreciating our techniques! The question about sparsity of the estimate is indeed interesting. In general, if we use a feature adaptation approach, some feature may be a dense combination of the original covariates and so we cannot guarantee sparsity in the original basis.\n\nNevertheless, for our main result it should be possible to guarantee some level of sparsity in the original basis by using tools from high-dimensional geometry. This is because (ignoring the final boosting step) the adapted features used in Algorithm 1 are rescalings of the coordinate basis, and because the proof of the result establishes an $\\ell_1$-norm bound on the predictor in the rescaled space outside of the set $S$ (which has bounded size) \\--- see page 21 of the supplementary material. Given this, one can sparsify the predictor using the Approximate Caratheodory Theorem (Theorem 0.0.2 of Vershynin's book [41]) to ensure sparsity $|S|$ plus a polynomial in the $\\ell_1$-norm bound and the reciprocal of the desired prediction error. It should also be possible to achieve a similar sparsity guarantee by replacing the LASSO with an orthogonal matching pursuit method; see theorem 15 and remark 5 of [24]. \n\nIt's true that the boosting step includes (one) denser feature at each iteration, but this feature corresponds to the predictor at the previous iteration, so it may be possible to iteratively bound the sparsities of the predictors at each iteration. Understanding the guarantees achieved here is an interesting open problem. Another is understanding whether a stronger sparsity guarantee (than that obtained by approximate Caratheodory) is possible in our setting. "}]

Author rebuttal:

Meta-review: The paper presents an adaptively regularized Lasso algorithm for sparse linear regression with ill-conditioned random covariates. Consistency analysis shows that the proposed method is able to achieve near-optimal sample complexity even if the convariance matrix has a few outlier eigenvalues. After discussions, the reviewers generally agreed that this is a theoretically sound paper that contributes several new insights into the addressed fundamental problem. The meta-reviewer thus would be happy to recommend the paper for acceptance.
Decision: Accept (spotlight)