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$.
Weaknesses
- 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.