Robust Sparse Regression with Non-Isotropic Designs

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:39:23

Abstract: We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries: oblivious and adaptive.
Consider the model $y^*=X^*\beta^*+ \eta$ where $X^*$ is an $n\times d$ random design matrix, $\beta^*\in \mathbb{R}^d$ is a $k$-sparse vector, and the noise $\eta$ is independent of $X^*$ and chosen by the \emph{oblivious adversary}. 
Apart from the independence of $X^*$, we only require a small fraction entries of $\eta$ to have magnitude at most $1$. 
The \emph{adaptive adversary} is allowed to arbitrarily corrupt an $\varepsilon$-fraction of the samples $(X_1^*, y_1^*),\ldots, (X_n^*, y_n^*)$.
Given the $\varepsilon$-corrupted samples $(X_1, y_1),\ldots, (X_n, y_n)$, the goal is to estimate $\beta^*$.  
We assume that the rows of $X^*$ are iid samples from some $d$-dimensional distribution $\mathcal{D}$  with zero mean and (unknown) covariance matrix $\Sigma$ with bounded condition number.

We design several robust algorithms that outperform the state of the art even in the special case of Gaussian noise $\eta \sim N(0,1)^n$. 
In particular, we provide a polynomial-time algorithm that with high probability recovers $\beta^*$ up to error $O(\sqrt{\varepsilon})$  as long as  $n \ge \tilde{O}(k^2/\varepsilon)$, only assuming some bounds on the third and the fourth moments of $\mathcal{D}$. 
In addition, prior to this work, even in the special case of Gaussian design $\mathcal{D} = N(0,\Sigma)$ and noise $\eta \sim N(0,1)$, no polynomial time algorithm was known to achieve error $o(\sqrt{\varepsilon})$ in the sparse setting $n < d^2$.  
We show that under some assumptions on the fourth and the eighth moments of $\mathcal{D}$, there is a polynomial-time algorithm that achieves error $o(\sqrt{\varepsilon})$ as long as $n \ge \tilde{O}(k^4 / \varepsilon^3)$. 
For Gaussian distribution $\mathcal{D} = N(0,\Sigma)$, this algorithm achieves error $O(\varepsilon^{3/4})$. 
Moreover, our algorithm achieves error $o(\sqrt{\varepsilon})$ for all log-concave distributions if $\varepsilon \le 1/\text{polylog(d)}$. 

Our algorithms are based on the filtering  of the covariates that uses sum-of-squares relaxations, and weighted Huber loss minimization with $\ell_1$ regularizer.  We provide a novel analysis of weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries. Furthermore, we complement our algorithmic results with Statistical Query lower bounds, providing evidence that our estimators are likely to have nearly optimal sample complexity.

Main paper: 
  
 Appendix:  


Decision: This paper studies sparse linear regression robust against both oblivious and adaptive adversaries. The majority of reviewers agree that both the theoretical results and the technical contributions seem qualitatively strong. Although concerns about the practical nature of the proposed algorithms were raised, the general consensus is that the paper is primarily of theoretical interest. Author responses during the rebuttal phase adequately addressed additional initial reviewer concerns.

I recommend the authors incorporate reviewer feedback and improve the clarity/presentation to ensure the work has a stronger impact. Further, it has been brought to my attention two additional works that examine similar error models in related contexts: https://ieeexplore.ieee.org/document/4544953 and https://dl.acm.org/doi/10.1145/1250790.1250804. While these studies focus on problems where the signal is not required to be sparse, considering these connections may provide useful insights or strengthen the theoretical foundations of the current work. I encourage the authors to review these references and evaluate whether citing them could benefit their contribution.

Reviews: review: paper_summary: paper_summary: This paper studies sparse linear regression with oblivious and adaptive adversaries. The design matrix is random, the noise is chosen by an adversary, and the goal is to find the optimal k-sparse weight vector. The results are as follows: to achieve $O(\sqrt{\varepsilon})$ error, a sample complexity of $\widetilde{O}(k^2/\varepsilon)}$ is needed, and to achieve $O(\varepsilon^{3/4})$ error, a sample complexity of $\widetilde{O}(k^4/\varepsilon^3)$ is needed. Previous work did not achieve error better than $\sqrt{\varepsilon}$ with any sample complexity better than $d^2$, unless the rows of a design matrix are drawn from an isotropic Gaussian distribution.

To obtain their results, the authors make the following assumptions: (1) the noise vector has at least $0.01n$ entries that are bounded by $\sigma$, where $n$ is the number of examples, (2) at most an $\varepsilon$ fraction of rows of $X$/entries of $y$ are corrupted, and (3) the rows of $X$ have bounded 3rd moments and entrywise-bounded 4th moments, i.e. the rows of X can be heavy-tailed random vectors. 

In this setting, they obtain two results:
1. With $O(k^2/\varepsilon)$ samples, they obtain $O(\sqrt{\varepsilon})$ error. Compared to the best prior work for heavy-tailed design matrices, the advantage of this result is that there is no dependence on the norm of the optimal k-sparse regression vector.
2. With $k^4/\varepsilon^3$ samples, they obtain $O(\varepsilon^{3/4})$ error. This result additionally assumes that the distribution of the rows of the design matrix has a bounded 4th moment, with a constant-degree sum-of-squares proof of the bound. It also additionally assumes that the rows of the design matrix have entrywise-bounded 8th moment.
Additionally, they give matching statistical query lower bounds.

The algorithm consists of obtaining a filtered set of examples, then minimizing Huber loss with l1 regularization, on the remaining examples. In the analysis, the authors show that if the following two conditions:
(1) A bound on the gradient of the loss function
(2) A condition similar to strong convexity
hold on the boundary of certain regions they call "elastic balls" (the elastic ball of radius $r$ has points with $\ell_2$ norm at most $r$ and $\ell_1$ norm at most $\sqrt{k} \cdot r$) then the weight vector they obtain will be similar to the true optimal weight vector. 

One of the key steps in this analysis, compared to prior works is as follows: instead of using Cauchy-Schwarz to bound certain terms in the gradient bound, they use Holder's inequality. This leads to them having to bound the sum of $\langle X_i, u \rangle^4$, as $X_i$ ranges over the examples in the filtered set, and $u$ can be any vector in the elastic ball of radius 1. Thus, during the algorithm, they must select $\widehat{S}$ so that it satisfies this property, and thus need an efficient algorithm to find such a set of size $(1 - O(\varepsilon))n$. They do this using a sum-of-squares relaxation with elastic constraints, which makes it so the relaxation set is a superset of $u^{\otimes 4}$ for $u$ in the elastic ball.

For the heavy-tailed case, it is also necessary to do some thresholding of X, which may have large entries even without adversarial noise. In previous works, the thresholding parameter needs to depend polynomially on the norm of the weight vector (to preserve the relationship between the un-corrupted X and y). This paper observes that in order to preserve the relationship between X and y, it is only necessary to analyze the effect of thresholding for the entries that are in the support of the optimal k-sparse regression vector $\beta^*$. This allows the thresholding parameter to only depend on $k$ and $\varepsilon$ and not the norm of $\beta^*$.

The proof strategy for showing the strong convexity property for heavy-tailed design matrices is also interesting. They first show it for vectors $u$ in the elastic balls which are $k$-sparse, then extend to dense vectors $u$. They show the bound for all k-sparse vectors using Bernstein's inequality, and a small $\epsilon$-net for the k-sparse vectors. To extend to dense vectors, they use the fact that if a quadratic form is $\Theta(r^2)$ on $k$-sparse vectors of norm $r$, then the quadratic form is $\Theta(r^2)$ on the elastic ball of radius $r$.
strength_weakness: strength_weakness: - While the writing is mostly good, it would be nice to organize the techniques section better. It would be useful for readers if you explicitly write the algorithm in a separate box, and divide the techniques section into some subsections.
questions: questions: - On line 278, what is $\hat{\beta}$? I thought the final estimator you return is $\hat{\beta}_{\hat{S}}$. Do you mean to refer to the ground-truth $k$-sparse regression vector?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper focuses on robust estimation of sparse linear regression in the presence of both oblivious and adaptive adversaries. It claims to offer polynomial-time algorithms capable of recovering a sparse coefficient vector with high probability. The paper includes theoretical analyses using the standard techniques such as pre-filtering, truncation to ensure robustness.
strength_weakness: strength_weakness: As per my understanding, the oblivious and adaptive adversary are dealt in literature separately. 

- For the oblivious adversary, the existing literature can handle constant outlier proportions and deliver consistent estimates. 

- For adaptive adversary, existing literature [PFL20] already has the results which are proposed in the submission. They use a trimmed MLE algorithm whose convergence rates are analyzed. Further, [Sas22] and [SF23] already extended these results for sparse settings (line 264). 

So, as per my understanding, the authors claim bounds similar to those in the existing literature for a slightly more complex setting of two adversaries. 

- Why are few entries of $\eta$ required to be close to $1$ in magnitude? Doesn't that make the oblivious adversary weak? 

- The authors use pre-filtering ideas, assuming a known covariance matrix and truncation to deal with heavy tails. They use standard techniques like sum-of-squares and weighted Huber loss minimization with $\ell_1$ regularization. 

These ideas are well explored in the literature. So, strictly speaking, there is a lack of major novelty in new ideas to deal with outliers and encourage robustness.  

- More importantly, $O(\sqrt{\varepsilon})$ error is already proved to be minimax optimal in the existing literature even when $n \to \infty$ while using techniques like trimming, pre-filtering, or truncation. A more interesting question could be under what conditions on $\varepsilon \neq 0$ or adversary can we achieve zero error for at least $n \to \infty$.
questions: questions: - Is the oblivious adversary allowed to change all the $n$ samples, unlike the adaptive adversary, which only changes $\varepsilon*n$ samples? 

- If the oblivious adversary is also restricted to $\varepsilon * n$ samples, it should be stated in line 6. Also, are the oblivious and adaptive adversaries changing the same $\varepsilon * n$ samples? 

- The authors claim that their algorithm achieves $o(\sqrt{\varepsilon})$ error for all log-concave distributions if $\varepsilon \leq 1/\text{polylog}(d)$. Hence, $\varepsilon$ can be very small for large $d$. Can this upper bound on $\varepsilon$ be improved? 

- The condition number of the covariance matrix is assumed to be bounded. Is that assumed in the existing literature or a new assumption in this submission? 

- Line 110 typo: 'ehrtr' and from 's' more 

- Line 234 typo: 'ghdsample' complexity
limitations: limitations: - In Definition 2.1, why was $|x_i| \leq 2$ chosen as the threshold to define the quadratic and linear part of Huber loss? In general, it could be dependent on the data? For example, there could be some dataset where $|x_i| \leq 3$ may be more appropriate. 

- The above could affect the upper bound on the gradient $|\phi(\eta)|$ taken as 2 in line 288. 

- A conclusion section and pointers to future work seem to be missing. 

- Towards the end of the main manuscript, the focus seems too much on the proof sketch. The writing or presentation can be improved. 

-  Some sort of empirical justification for the proposed results on synthetic or real datasets would have been really nice. This would have also helped to draw attention to the significance of the contributions of polynomial time algorithms. In Proposition 1.10 and 1.11, the number of queries is claimed as $\exp(d^{\Omega(1)})$, which does not seem to be very useful for practitioners.
paper_summary: paper_summary: It developed efficient estimators for sparse linear regression in the presence of oblivious and adaptive adversaries. It presents a robust algorithm that outperforms sota under desired conditions on the moment of the distribution.
strength_weakness: strength_weakness: - algorithms may require significant computational resources, which could limit practical applications.

- There is a lack of empirical evidence comparison with the sota even on a toy setup.
questions: questions: NA.
limitations: limitations: The results depend on specific assumptions about the distribution and moments of the data, which may not always hold in real-world scenarios.
paper_summary: paper_summary: This paper studies sparse linear regression $y^* = X^* \beta^* + \eta$ (where $\beta^*$ is $k$-sparse) in the presence of two types of adversaries. 

- First, the noise vector $\eta$ is sampled before $X^*$ in an (obliviously) adversarial way. Then $X^*$ is sampled independently of $\eta$ with i.i.d. rows and $y^*$ is generated according to the model. 

- Second, an adaptive adversary takes $(X^*, y^*)$ and (adaptively) corrupts at most $\epsilon$ fraction of $(X_i^*, y_i^*)$. 
The resulting samples given to the statistician are denoted by $(X, y)$. 

The results are two-fold. 

- First, a poly-time algorithm for estimating $\beta^*$ up to $\epsilon$ expected prediction error using $n \approx k^2/\epsilon^2$ samples. 

- Second, a poly-time algorithm for estimating $\beta^*$ up to $o(\epsilon)$ expected prediction error using $n \approx k^4/\epsilon^6$ samples. 
For correlated Gaussian design, this can be improved to $n\approx k^4/\epsilon^4$.
strength_weakness: strength_weakness: NA
questions: questions: I'm not familiar with the SoS machinery, so the authors may find my comments shallow and unconstructive. 
That said, I am familiar with ordinary (sparse) linear regression and I do think that the presentation of the paper should be improved. 

Major comments: 

1. The sample complexity bounds are written in a wacky way. 
Why don't we fix the goal to be achieving $\epsilon$ error and write the sample complexity bounds accordingly?

1. The two results in the paper (for achieving $O(\sqrt{\epsilon})$ and $o(\sqrt{\epsilon})$ errors) seem to have very discontinuous transitions as $\epsilon$ varies. 
Can the authors comment on whether it's expected to be so or it's a proof artifact?
In fact, should I think of $\epsilon$ as potentially depending on $n,k,d$ in an arbitrary way? 
This is not clear since sometimes the authors view $\epsilon$ as a constant in which case $O(\epsilon), o(\epsilon)$ don't make sense to me. 

1. I suggest the authors add a short section discussing related work at the level of techniques (e.g., filtering, SoS, etc.). 
Currently, these techniques and the difference between the present paper and prior work are buried in Section 2 which itself is written in an obscure way. 

Minor comments:

1. Line 48-51 seems out of place.

1. Please unify the notation $N(0,\mathrm{Id}), N(0,1)^n$. 

1. Multiple typos in line 110. 

1. Line 114, should $X$ be $X^*$?

1. Typo in line 234. 

1. I don't understand line 243-244. 
Please define "simulation". 
My shallow understanding is that SQ lower bounds only apply to detection version of the problem. 
I'm not sure if this has the same spirit as "simulation". 

1. Section 2 (Techniques) is written in a very informal and dense way. 
As someone who's not familiar with these techniques, I couldn't get much out of it. 

1. Typo in line 259, $\eta\sim N(0,\mathrm{Id})$. 

1. Typo in line 264, it --> in. 

1. Line 291, please provide a reference for the sentence in the parentheses. 

1. Is line 298 the only property one needs from the output of filtering?
If so, why not say it upfront in line 266?

1. Line 364, 365, there're two "only"'s in the sentence. 

1. I don't understand line 371, even grammatically. 

1. A very minor comment on the writing. I feel that the language used in this paper is quite informal and the writing was perhaps done in a hasty. 
For instance, there're ~20 "only", ~20 "even", ~10 "likely"...
limitations: limitations: NA
paper_summary: paper_summary: The authors provide a computationally efficient estimator for robust and sparse linear regression under non-isotropic covariance matrices. Their first result achieves $O(\sqrt{\epsilon})$ error with state-of-the-art sample complexity under a weaker noise assumption than prior work. Their second result is the first to achieve $o(\sqrt{\epsilon})$ error for robust and sparse linear regression under non-isotropic covariance matrices, under a sum-of-squares certificate for the $4^{th}$ moment. They further provide Statistica Query Lower bounds supporting their results.
strength_weakness: strength_weakness: I don't see any weaknesses per se, was just curious to understand if the authors believe that the sum-of-squares assumption is necessary to achieve $o(\sqrt{\epsilon})$ error or a weaker assumption such as Definition 1.6 suffices.
questions: questions: Small typo on Line 110 - ehtr

See weakness section.
limitations: limitations: NA

Comments: comment: I thank the authors for their response. My scores are unchanged.
Thank you for your reply. I will keep my original score.
I thank the authors for their detailed response. I will keep my original score.
I thank the reviewer for the detailed response. 
In particular, regarding item 1 and 2 in the response: 

1. I realize that my previous question here didn't make much sense. Sorry about that and thanks anyway for the clarification. 

2. Thanks for the discussion on the scaling of $\epsilon$ which is helpful and, as the authors mentioned, should be included in the paper somewhere. 

My overall evaluation remains unchanged.