Efficient Algorithms and Lower Bounds for Robust Linear Regression

Introduction

Linear regression is a prototypical problem in statistics with a range of applications in signal processing (e.g., face recognition, time series analysis) and various other data analysis tasks. The reader is referred to [RL87, BJK15] and references therein. In the realizable case, linear regression is well-understood. Here we study the problem in a robust model where an $\varepsilon$-fraction of the samples are adversarially corrupted. We explore the tradeoff between sample complexity, computational complexity, and robustness in high-dimensional linear regression, obtaining both efficient algorithms and nearly matching computational-statistical-robustness tradeoffs.

Estimation in the presence of outliers is an important goal in statistics and has been systematically studied within the robust statistics community since [Hub64]. Nevertheless, until recently, all known efficient estimators could only tolerate a negligible fraction of outliers in high-dimensional settings, even for the simplest statistical tasks. Recent work in the theoretical computer science community [KLS09, ABL14, DKK+16, LRV16] gave the first efficient robust estimators for basic high-dimensional statistical tasks, including learning linear separators, and mean and covariance estimation. Since the dissemination of [DKK+16, LRV16], there has been a flurry of research activity on robust learning (see Section 1.3 for a discussion).

where $\eta_{i}$ is some kind of random observation noise. The goal is to compute a hypothesis vector $\widehat{\beta}$ such that $\|\widehat{\beta}-\beta\|_{2}$ is small. In this work, we study the fundamental setting that $\mathcal{D}$ is $\operatorname{\mathcal{N}}(0,\Sigma)$, where the covariance matrix $\Sigma$ is either a priori known or unknown to the algorithm. For simplicity, we also assume that $\eta_{i}\sim\operatorname{\mathcal{N}}(0,\sigma^{2})$ and is independent of $X_{i}$.

We consider the following model of robust estimation that generalizes other existing models, including Huber’s contamination model:

Given $\varepsilon>0$ and a family of probabilistic models $\mathcal{M}$, the adversary operates as follows: The algorithm specifies some number of samples $m$. The adversary generates $m$ samples $X_{1},X_{2},\ldots,X_{m}$ from some (unknown) $M\in\mathcal{M}$. The adversary is allowed to inspect the samples, removes $\varepsilon m$ of them, and replaces them with arbitrary points. This set of $m$ points is then given to the algorithm. We say that a set of samples is $\varepsilon$-corrupted if it is generated by the aforementioned process.

In summary, the adversary is allowed to inspect the samples before corrupting them, both by adding corrupted points and deleting uncorrupted points. In contrast, in Huber’s model the adversary is oblivious to the samples and is only allowed to add corrupted points.

In the context of robust linear regression studied in this paper, the adversary can change an arbitrary $\varepsilon$-fraction of the labeled samples $(X_{i},y_{i})$ that satisfy the aforementioned definition of linear regression. The goal is to output a hypothesis vector $\widehat{\beta}$ such that $\|\widehat{\beta}-\beta\|_{2}$ is as small as possible.

2 Our Results and Techniques

Let $S^{\prime}$ be an $\varepsilon$-corrupted set of labeled samples of size $\Omega((d/\varepsilon^{2})\operatorname{polylog}(\frac{d}{\varepsilon\tau}))$. There exists an efficient algorithm that on input $S^{\prime}$ and $\varepsilon>0$, returns a candidate vector $\widehat{\beta}$ such that with probability at least $1-\tau$ it holds $\|\widehat{\beta}-\beta\|_{2}=O(\sigma_{y}\varepsilon\log(1/\varepsilon))$, where $\sigma_{y}=\sqrt{\sigma^{2}+\|\beta\|_{2}^{2}}$).

Roughly speaking, the algorithm establishing Theorem 1.2 relies on the observation that robust linear regression can be reduced to robust mean estimation. The main drawback of this approach is that the error guarantee depends on $\|\beta\|_{2}$ and in particular does not go to when $\sigma$ goes to . To eliminate $\|\beta\|_{2}$ from the RHS while retaining a near-optimal sample complexity, we require a more sophisticated approach. Specifically, our main algorithmic contribution is as follows:

Let $S^{\prime}$ be an $\varepsilon$-corrupted set of labeled samples of size $\Omega((d/\varepsilon^{2})\operatorname{polylog}(\frac{d}{\varepsilon\tau}))$. There exists an efficient algorithm that on input $S^{\prime}$ and $\varepsilon>0$, returns a candidate vector $\widehat{\beta}$ such that with probability at least $1-\tau$ it holds $\|\widehat{\beta}-\beta\|_{2}=O(\sigma\varepsilon\log(1/\varepsilon))$.

We note that an error of $\Omega(\sigma\varepsilon)$ is information-theoretically necessary for this problem, even when the sample size is unbounded (see, e.g., [Gao17]). Hence, our second algorithm achieves the minimax optimal error, up to a logarithmic factor in $1/\varepsilon$.

With $O(d/\varepsilon^{2})$ samples, the empirical covariance matrix of $yX$ also concentrates around the true covariance matrix. Hence, the above key observation provides an indicator to determine whether the mean may be corrupted. However, even if we manage to detect the abnormality by looking at the empirical covariance, it’s still not clear how we are able to fix it. Luckily, this many samples are enough to obtain strong empirical tail bounds. More concretely, the empirical tail will be close to the true tail in any direction. Combing these two facts, in the case that the empirical covariance is abnormal, we can look at the top principal component direction and check if the data satisfies the desired tail bound. We claim that since the variance is abnormally large, there must a threshold where the tail bound is significantly violated. Hence, we can throw away samples above this threshold which mostly consists of outliers.

To remove the $\log(\|\beta\|_{2})$ dependence in the sample complexity, one may consider subtracting $\widehat{\beta}^{T}X$ from $y$ using the same batch of samples repeatedly. The main problem with doing this naively is that, for arbitrary $\beta^{\prime}$, we would need the second moment matrix of $(y-\beta^{\prime T}X)X$ to be close to its expectation. Unfortunately, we are not going to get this guarantee for all $\beta^{\prime}$ with fewer than $\Omega(d^{2})$ samples. To see this, let $\|\beta\|_{2}=O(1)$ and consider that with high probability one of our samples $X_{1}$ will have $\|X_{1}\|_{2}=\Theta(\sqrt{d})$ and $X_{1}\cdot\beta=O(1)$. Now if we let $\beta^{\prime}=\frac{X_{1}}{\|X_{1}\|_{2}}$ and consider $v=\beta^{\prime}$, we would have $\|(y_{1}-\beta^{\prime T}X_{1})^{2}X_{1}X_{1}^{T}\|_{2}=\Theta((v\cdot X_{1})^{4})=\Theta(d^{2})$. Since the expected second moment matrix has operator norm $O(1)$, we need $\Omega(d^{2})$ samples to achieve concentration. Somewhat surprisingly, the only problem that prevents the empirical covariance from achieving the desired concentration is the samples with large $y-\beta^{\prime T}X$, as illustrated in the previous example. The concentration property holds if we temporally ignore samples with large $|y-\beta^{\prime}\cdot X|$, thus we can run the previous algorithm on the same batch of samples repeatedly. Notice that we will need to add the ignored samples back at the end of each iteration, since these samples may contain more good samples than corrupted samples.

2.2 Statistical Query Lower Bounds

In this section, we describe our Statistical Query (SQ) lower bounds establishing a tradeoff between sample complexity and computation complexity for robust linear regression with unknown (bounded) covariance.

We start with some basic background. A Statistical Query (SQ) algorithm relies on an oracle that given any bounded function on a single domain element provides an estimate of the expectation of the function on a random sample from the input distribution. This computational model was introduced by Kearns [Kea98] in the context of supervised learning as a natural restriction of the PAC model [Val84]. Subsequently, the SQ model has been extensively studied in a plethora of contexts (see, e.g., [Fel16b] and references therein). We remark that all recently developed algorithms for robust high-dimensional estimation fit in the SQ framework.

A recent line of work [FGR+13, FGV15, FPV15, Fel16a] developed a framework of SQ algorithms for search problems over distributions, which encompasses the linear regression problem studied here. It turns out that one can prove unconditional lower bounds on the computational complexity of SQ algorithms via the notion of Statistical Query dimension. This complexity measure was introduced in [BFJ+94] for PAC learning of Boolean functions and was recently generalized to the unsupervised setting [FGR+13, Fel16a]. A lower bound on the SQ dimension of a learning problem provides an unconditional lower bound on the computational complexity of any SQ algorithm for the problem.

As our main negative result in this paper, we prove a Statistical Query (SQ) lower bound giving evidence that if $X$ has an unknown (bounded) covariance, it is computationally hard to approximate $\beta$ well given significantly fewer than $d^{2}$ samples. The reason that this result is interesting is because this learning problem can be information-theoretically solved with $d$ samples to optimal accuracy. More concretely, we prove (see Theorem 3.1 for a more detailed formal statement):

No SQ algorithm for robust linear regression for Gaussian covariates with unknown bounded covariance and random noise with $\sigma^{2}\leq 1$ can output a candidate $\beta^{\prime}$ with $\|\beta^{\prime}-\beta\|_{2}\leq o(\sqrt{\varepsilon})$ on all instances unless it uses $2^{\Omega(d)}$ statistical queries or each query requires $\Omega(d^{2})$ samples to be simulated.

To prove this result, we require a generalization of the technique in [DKS17c], which was designed for unsupervised learning problems. That work established SQ lower bounds for unsupervised learning problems using a construction consisting of distributions which are standard Gaussians in all except one direction, by showing that if such a distribution agrees with the first few moments of the standard Gaussian, then it is hard to find the hidden direction.

As already mentioned, [DKS17c] considers unsupervised learning problems and the distribution in the construction is a suitable model for $X$, but not for the joint distribution $(X,y)$, where the direction of the $y$ coordinate is very different. We instead try to make $X$ conditioned on $y$ match moments with a Gaussian. When the momets match for all $y$, it is hard to learn the direction $\beta$ where these conditional distributions are different. We show that when $\|\beta\|_{2}=O(\sqrt{\varepsilon})$, we can match three moments and it is hard to find the direction of $\beta$. Thus, we obtain a lower bound that says that we cannot approximate $\beta$ to within $o(\sqrt{\varepsilon})$ with fewer than exponential in $d$ statistical queries, unless we use queries of precision greater than we could simulate with $O_{\varepsilon}(d^{2})$ samples.

3 Comparison to Prior Work

Since the initial works [DKK+16, LRV16], there have been a considerable number of papers on a wide range of topics related to robust high-dimensional estimation, including: learning graphical models [DKS16], understanding computation-robustness tradeoffs [DKS17c, DKK+18a], giving applications to exploratory data analysiis [DKK+17a], establishing connections to supervised PAC learning [DKS17a], tolerating more noise by outputting a list of candidate hypotheses [CSV17, DKS17b], learning sparse models [BDLS17], and robust estimation via sum-of-squares [KS17b, HL17, KS17a].

4 Concurrent and Independent Works

5 Structure of this Paper

In Section 2, we describe our robust algorithms and in Section 3 we give our SQ lower bounds. For the clarity of the presentation, most proofs are deferred to the appendix.

Robust Algorithm for Linear Regression

Under our corruption model where an $\varepsilon$-fraction of the samples can be arbitrarily corrupted, we will typically use $S$ to denote the set of samples before being corrupted by the adversary. Given a set of samples, $S^{\prime}$, we denote the set $E$ to be $S^{\prime}\setminus S$ (which contains the samples added by the adversary), and the set $L$ to be $S\setminus S^{\prime}$ (which contains the samples removed from the set of clean samples).

2 Basic Robust Linear Regression Algorithm

The algorithm that achieves the performance guarantee stated in Theorem 1.2 is an iterative algorithm that invokes the following algorithm, Algorithm 1, multiple times as a subroutine. Every time Algorithm 1 gets called, it either returns an estimate of $\beta$ or returns a set of “cleaner” data points on which another iteration of Algorithm 1 can be invoked. We describe the algorithm as follows:

Let $G\sim\operatorname{\mathcal{N}}(0,I_{d})$ and $\varepsilon,\tau>0$. Let $S$ be an $(\varepsilon,\tau)$-good set with respect to $(G,\beta)$. Let $S^{\prime}$ be any multiset with $\Delta(S,S^{\prime})\leq 2\varepsilon$. The algorithm Filter-LR-Identity covariance runs in polynomial time and, given $S^{\prime}$ and $\varepsilon>0,$ returns one of the following:

A multiset $S^{\prime\prime}\subseteq S^{\prime}$ such that $\Delta(S,S^{\prime\prime}){<}\Delta(S,S^{\prime})$,

where $\Delta(S,S^{\prime})$ is the size of the symmetric difference of multisets $S$ and $S^{\prime}$ divided by the cardinality of $S.$

The proof of Proposition 2.1 is deferred to Appendix B. Assuming Proposition 2.1 holds, we are now ready to show Theorem 1.2, which is restated below for convenience:

Theorem 1.2 Let $S^{\prime}$ be an $\varepsilon$-corrupted set of labeled samples of size $\Omega((d/\varepsilon^{2})\operatorname{polylog}(\frac{d}{\varepsilon\tau}))$. There exists an efficient algorithm that on input $S^{\prime}$ and $\varepsilon>0$, returns a candidate vector $\widehat{\beta}$ such that with probability at least $1-\tau$ it holds $\|\widehat{\beta}-\beta\|_{2}=O(\sigma_{y}\varepsilon\log(1/\varepsilon))$ (recalling that $\sigma_{y}=\sqrt{\sigma^{2}+\|\beta\|_{2}^{2}}$).

By the definition of $\Delta(S,S^{\prime}),$ since $S^{\prime}$ has been obtained from $S$ by corrupting an $\varepsilon$-fraction of the points in $S,$ we have that $\Delta(S,S^{\prime})\leq 2\varepsilon.$ By Proposition 2.3 (see below), the set $S$ of uncorrupted samples is $(\varepsilon,\tau)$-good with respect to $G$ with probability at least $1-\tau.$ We henceforth condition on this event.

We iteratively apply the Filter-LR-Identity covariance procedure of Proposition 2.1 until it terminates returning a vector $\beta$ with $\|\widehat{\beta}-\beta\|_{2}=O(\sigma_{y}\varepsilon\log(1/\varepsilon)).$ We claim that we need at most $O(N)$ iterations for this to happen, simply because the sequence of iterations results in a sequence of sets $S_{i}^{\prime}$ satisfy $S_{i}^{\prime}>S^{\prime}_{i+1}$. ∎

To better illustrate how Algorithm 1 works, we provide a proof sketch of Proposition 2.1. Our algorithm succeeds under a set of deterministic conditions that are satisfied by an uncorrupted set of samples with high probability.

For all $(X,y)\in S$, we have $\|\frac{yX}{\sigma_{y}}\|_{2}\leq 4\sqrt{d}\log(|S|/\tau)$ and $y/\sigma_{y}\leq\sqrt{4\log(|S|/\tau)}$.

We have that $\left\|{\beta_{S}-\beta}\right\|_{2}\leq O(\sigma_{y}\varepsilon).$

We have that $\left\|M_{S}-(\sigma_{y}^{2}I+{\beta\beta^{T}})\right\|_{2}\leq O({\sigma_{y}^{2}\varepsilon}).$

Roughly speaking, condition (i) claims that none of the uncorrupted samples is too big in magnitude, condition (ii) establishes the empirical tail bound of the set of samples, condition (iii) and (iv) guarantee that the empirical mean and empirical covariance converge well to the true mean and covariance. The following proposition states that the above deterministic properties hold with high probability for a set of samples of near-linear size:

We note that the sample size in the above proposition is optimal, up to logarithmic factors, and is crucial in establishing the near-optimal sample complexity of our algorithm. The proof of Proposition 2.3 is deferred to Appendix A.

Given that the deterministic conditions hold for the uncorrupted data, our algorithm simply computes the sample mean and covariance (Step 5). Notice that condition (iii) and (iv) also establishes a connection between the sample mean and covariance, in the sense that for uncorrupted data, sample covariance can be predicted using the sample mean. Hence, the algorithm checks whether the sample mean and covariance satisfies their presumptive relationship, i.e., $\widehat{M_{S^{\prime}}}\approx(\sigma^{\prime}_{y}I+\beta_{S^{\prime}}\beta_{S^{\prime}}^{T})$ (Steps 6, 7). If it is the case, the sample mean cannot possibly be corrupted by too much due to Corollary B.4, and hence the algorithm can output the sample mean confidently (Step 8). If it is not the case, the sample covariance must have been corrupted by a lot in some direction and thus violate the tail bound in this direction. The algorithm will then find a threshold such that there are more samples beyond the threshold than twice of the number predicated by condition (iii) (Step 10), and remove all the sample beyond the threshold (Step 11), which contains more “bad” samples than uncorrupted samples, due to Claim B.5. The full proof of Proposition 2.1 is given in Appendix B.

In this section, we describe an algorithm establishing Theorem 1.3, which we restate below for completeness.

Theorem 1.3 Let $S^{\prime}$ be an $\varepsilon$-corrupted set of labeled samples of size $\Omega((d/\varepsilon^{2})\operatorname{polylog}(\frac{d}{\varepsilon\tau}))$. There exists an efficient algorithm that on input $S^{\prime}$ and $\varepsilon>0$, returns a candidate vector $\widehat{\beta}$ such that with probability at least $1-\tau$ it holds $\|\widehat{\beta}-\beta\|_{2}=O(\sigma\varepsilon\log(1/\varepsilon))$.

Similarly to the basic algorithm of the previous subsection, the algorithm that achieves the performance guarantee of Theorem 1.3 is iterative and invokes Algorithm 2 multiple times as a subroutine. Every time Algorithm 2 gets called, it either returns an estimate of $\beta$ or returns a set of “cleaner” data points.

Let $G\sim\operatorname{\mathcal{N}}(0,I_{d})$ and $\varepsilon,\tau>0$. Let $S$ be $(\varepsilon,\tau)$-representative with respect to $(G,\beta)$. Let $S^{\prime}$ be any multiset with $\Delta(S,S^{\prime})\leq 2\varepsilon$. There exists a polynomial time algorithm Filter-LR-Identity covariance-2 that, given $S^{\prime}$ and $\varepsilon>0,$ returns one of the following:

A multiset $S^{\prime\prime}\subseteq S^{\prime}$ such that $\Delta(S,S^{\prime\prime}){<}\Delta(S,S^{\prime})$,

where $\Delta(S,S^{\prime})$ is the size of the symmetric difference of multisets $S$ and $S^{\prime}$ divided by the cardinality of $S.$

Like the basic algorithm we discussed in the previous subsection (which has dependency on $\|\beta\|$), the success of our new algorithm relies on the deterministic conditions which hold with high probability for a set of clean samples of size $N=\Omega(d\operatorname{polylog}(d/\varepsilon\tau)/\varepsilon^{2})$. Definition C.1 in Appendix C lists the conditions that need to hold for our algorithm to work, which are similar to Definition 2.2 for the basic algorithm. As usual, each condition consists of four sub-conditions, which guarantee that the set of uncorrupted samples are bounded, satisfy certain tail bounds and have mean and covariance concentration. The first condition simply holds for a set of samples from an isotropic Gaussian distribution, through which our filter algorithm on $X$ can remove the corrupted samples. The second condition holds for $y-\beta^{\prime}\cdot X$ with arbitrary $\beta^{\prime}$, which allows us to run a filter algorithm on $y-\beta^{\prime}\cdot X$ for any $\beta^{\prime}$. While the first two conditions are in analogy to those in Definition 2.2 for the basic algorithm, the third condition is different. Specifically, the third condition does not hold unconditionally for a set of clean data with size $O(d\operatorname{polylog}(d/\varepsilon\tau)/\varepsilon^{2})$, but only after conditioning on $|y-\beta^{\prime}\cdot X|$ being not too big. In Appendix C, we prove that these conditions will be satisfied with high probability after $O(d\operatorname{polylog}(d/\varepsilon\tau)/\varepsilon^{2})$ samples.

Statistical Query Lower Bounds

In this section, we formally describe our main lower bound result and provide a high-level proof sketch. Consider the joint distribution of $(X,y)$ in a linear regression problem without corruptions when the covariance of $X$ is unknown. Formally, let $Q$ be the distribution of $(X,y)$, where $X\sim\mathcal{N}(0,\Sigma)$ for some unknown but bounded $\Sigma$, and $y$ conditioned on $X$ has $y|X\sim\beta^{T}X+\eta$, where $\beta$ is unknown and $\eta\sim\mathcal{N}(0,\sigma^{2})$ for unknown but bounded $\sigma^{2}$. If we consider noise given by Huber’s $\varepsilon$-contamination model, then instead of seeing samples from $Q$, we observe samples from $Q^{\prime}$, which is a mixture between $Q$ and a noise distribution, i.e., $Q^{\prime}=(1-\varepsilon)Q+\varepsilon N$. Here we show that given statistical query access to $Q^{\prime}$, we cannot approximate $\beta$ well without needing precision stronger than is possible with a strongly sub-quadratic number of samples:

No algorithm given statistical query access to $Q^{\prime}$, defined as above with unknown noise and unknown variances $\frac{1}{2}I\preceq\Sigma\preceq I$ and $\sigma^{2}\leq 1$, gives an output $\beta^{\prime}$ with $\|\beta^{\prime}-\beta\|_{2}\leq o(\sqrt{\varepsilon})$ on all instances unless it uses more than $2^{\Omega(d^{c})}d^{4c-2}$ calls to the

The detailed proof of Theorem 3.1 is given in Appendix E.

Informally speaking, the theorem shows that no Statistical Query algorithm can approximate $\beta$ to within $o(\sqrt{\varepsilon})$ with fewer than exponential in $d$ queries, unless using queries of precision greater than we could simulate with $O(d^{2}/e^{O(1/\varepsilon)})$ samples. Notice that without the lower bound on $\Sigma$, the result would be unsurprising. Indeed, if $\Sigma v=0$ for some non-zero $v$, then we could not approximate $v\cdot\beta$ at all, simply because $v\cdot\beta$ can be arbitrary without affecting $y$.

In the proof of Theorem 3.1, we use the construction in Proposition 3.3 of [DKS17c], which intuitively says that if we have a distribution which is standard Gaussian in all except one direction, then if the low-degree moments match the standard Gaussian, then that direction is hard to find with an SQ algorithm. The idea is that, if we consider $X$ conditioned on $y$ for non-zero $\beta$, then $X$ has a non-zero mean in the $\beta$ direction. The conditional distribution $X|y$ is derived as follows:

Let $Q$ be the joint distribution of $(X,y)$ with $X\sim\mathcal{N}(0,\Sigma)$ and $y|X\sim\beta^{T}X+\eta$, where $\beta$ is unknown an $\eta\sim\mathcal{N}(0,\sigma^{2})$. Then $y\sim\mathcal{N}(0,\sigma_{y}^{2})$, where $\sigma_{y}^{2}=\beta^{T}\Sigma\beta+\sigma^{2}$ and $X|y\sim\mathcal{N}(\frac{y}{\sigma_{y}}\Sigma\beta,\Sigma-\frac{(\Sigma\beta)(\Sigma\beta)^{T}}{\sigma_{y}})$.

Notice that $(X,y)$ is a $d+1$ dimensional Gaussian distribution with covariance

By the mean and covariance formula of the conditional distribution of a Gaussian, we have that $X|y\sim\mathcal{N}(\frac{y}{\sigma_{y}}\Sigma\beta,\Sigma-\frac{\Sigma\beta\beta^{T}\Sigma}{\sigma_{y}})$. ∎

Notice that $X|y$ is indeed standard Gaussian in all except the $\Sigma\beta$ direction. By adding corruptions, we can make the distribution of $X|y$ projected onto $\Sigma\beta$ agree with the first three moments of $\mathcal{N}(0,I)$ and, like the construction of [DKS17c], still be a standard Gaussian in all the other orthogonal directions. Then we can show that we cannot find the direction of $\beta$ with an SQ algorithm. Lemma E.4 establishes the upper bound of the statistical correlation between a pair of distributions under our construction, which allows the classical statical query scheme (see, e.g., Corollary 3.12 in [FGR+13]) to be applied and yield the desired lower bound.

The further the mean of $X$ conditioned on $y$ is from , the more noise needs to be added to match the first three moments. Lemma E.2, which is the main lemma of the lower bound proof, shows that we can match the first three moments by adding $O(\mu^{2})$ fraction of noise when the $X|y$ has mean $\mu$ in the $\beta$ idrection. As long as $\|\beta\|_{2}=O(\sqrt{\varepsilon})$, after taking the integral over $y$, the overall noise added will still be smaller than $\varepsilon$.

We would like to thank Jason Lee for his contributions to the early stages of this work. I.D. and A.S. thank Daniel Kane for numerous discussions on robust high-dimensional estimation over the last five years.

References

Appendix A Proof of Proposition 2.3: Deterministic Regularity Conditions for Algorithm 1

This section establishes Proposition 2.3.

We will require a couple of technical facts. We start with the following basic Gaussian concentration result:

We will make essential use of the following concentration inequality for quadratic forms:

The following lemma proves property (i) of Definition 2.2:

Let $G\sim\operatorname{\mathcal{N}}(0,I_{d})$ and $\varepsilon,\tau>0$. If the multiset $S$ consists of $\Omega((d/\varepsilon^{2})\operatorname{poly}\log(d/\varepsilon\tau))$ pairs $(X,y)$, where $X\sim G$ and $y=\beta\cdot X{+\sigma E}$, it satisfies $\|\frac{yX}{\sigma_{y}}\|_{2}\leq 4\sqrt{d}\log(|S|/\tau)$, $\|X\|_{2}\leq 2\sqrt{d\log(|S|/\tau)}$, $y/\sigma_{y}\leq 2\sqrt{\log(|S|/\tau)}$ with probability at least $1-\tau$.

Let $N=\Omega((d/\varepsilon^{2})\operatorname{poly}\log(d/\varepsilon\tau))$ be the size of $S$. Consider the unlabeled set of samples $X_{1},\ldots,X_{N}$ drawn from $G$.To establish (i), we note that the probability that a coordinate of a sample $X_{i}$ has absolute value at least $\sqrt{2\log(20Nd/\tau)}$ is at most $\tau/(10dN)$ by Fact A.1. By a union bound over $d$ coordinates, the probability that all coordinates of all samples have absolute value smaller than $\sqrt{2\log(20Nd/\tau)}$ is at least $1-\tau/10$. In this case, $\|X\|_{2}\leq\sqrt{2d\log(20Nd/\tau)}\leq 2\sqrt{d\log(N/\tau)}$ assuming $N>20d$. Also note that $y/\sigma_{y}\sim\operatorname{\mathcal{N}}(0,1)$. By Fact A.1, the probability that $|y|/\sigma_{y}\geq\sqrt{2\log(20N/\tau)}$ is at most $\tau/(10N)$. By a union bound, the probability that all $|y|/\sigma_{y}$ are smaller than $\sqrt{2\log(20N/\tau)}<\sqrt{4\log(N/\tau)}$ is at least $1-\tau/10$. Hence, $\|\frac{yX}{\sigma_{y}}\|_{2}\leq(4\sqrt{d}\log(N/\tau))$ holds for all the samples with probability at least $1-\tau/10$. This completes the proof. ∎

We will require the following technical claim:

Let $S$ be a set of $N\geq 10$ independent samples from $\operatorname{\mathcal{N}}(0,1)$. For $0<\delta\leq 1$, we have with probability at least $1-\ln(N/\delta)\exp(-\Omega(N\delta/\log(1/\delta)))$, for all $T$, $\Pr_{X\sim S}[|X|\geq T]\leq 5\exp(-T^{2}/2)+\delta/T^{2}$ and all $X\in S$ have $|X|\leq 2\sqrt{N/\delta}$.

To prove the claimed tail for all $T$, we first show that for any $T=2^{i}$, where $1\leq i\leq\ln(N/\delta)$, the claimed tail bound divided by $2$ (i.e., $\frac{5}{2}\exp(-T^{2}/2)+\frac{\delta}{2T^{2}}$) holds with probability $1-\exp(-\Omega(N\delta/\log(1/\delta))$. Then, by a simple union bound, we get the desired upper bound for all $T$.

Given $Y\sim\operatorname{\mathcal{N}}(0,1)$, we have that $\Pr[|Y|\geq T]=2\mbox{\text{e}rfc}(T)$ where erfc is the complementary error function. We define the function $Q(T)=5\mbox{\text{e}rfc}(T)/2+\delta/2T^{2}$. Observe that $N\Pr_{X\sim S}[|X|\geq T]$ is a sum of $N$ independent Bernoulli random variables with mean $2\mbox{\text{e}rfc}(T)$. Since $Q(T)\geq\frac{5}{4}(2\mbox{\text{e}rfc}(T))$, by the Chernoff bound, $\Pr_{X\sim S}[|X|\geq T]\geq Q(T)$ with probability at most $\exp(-NQ(T)/60)$. Let $T^{\prime}$ be such that $\mbox{\text{e}rfc}(T^{\prime})=\delta^{2}/4T^{\prime 4}$. Since $\exp(-T^{2}/2)/T\leq\mbox{\text{e}rfc}(T)\leq\exp(-T^{2}/2)$ for all $T>0$, we have that $T^{\prime 2}/2=\Theta(\ln(T^{\prime})+\ln(1/\delta))$ and hence $T^{\prime}=\Theta(\sqrt{\ln(1/\delta)})$. Thus, we have that for all $T\leq T^{\prime}$, $Q(T)\geq\delta/2T^{\prime 2}=\Omega(\delta/\log(1/\delta))$ and this bound suffices.

When $T\geq T^{\prime}$, note that $\mbox{\text{e}rfc}(T)\leq(\delta/2T^{2})^{2}$. Here we need to use a more explicit version of the Chernoff bound. That gives that $\Pr[|X|\geq T]\geq Q(T)$ with probability at most $\exp(-ND(Q(T)||2\mbox{\text{e}rfc}(2)))$, where $D(p||q)=p\ln(p/q)+(1-p)\ln((1-p)/(1-q))$ is the KL-divergence between Bernoulli’s with probabilities $p$ and $q$. When $T\geq T^{\prime}$, $p=\delta/2T^{2}$, $q=2\mbox{\text{e}rfc}(T)$, we obtain

Thus, we have that $\Pr[|v\cdot X|\geq T]\geq Q(T)$ with probability at most $\exp(-ND(Q(T)||2\mbox{\text{e}rfc}(2)))=\exp(-\Omega(N\delta))$ in this case.

Note that $Q(T)<1/N$ for $T\geq\max\{\sqrt{N/\delta},\sqrt{2\ln(5N/2)}\}=\sqrt{N/\delta}$ for $N\geq 10$. By a union bound, we have that for $T^{\prime}=2^{i}$ for integers $1\leq i\leq\ln(N/\delta)/2+1$ that $\Pr[|v\cdot X|\geq T^{\prime}]\leq Q(T^{\prime})\leq 5\exp(T^{2}/2)/2+\delta/2T^{2}$ for all such $T^{\prime}$ is $O(\ln(N/\delta)\exp(-\Omega(N\delta))$. Note that the largest $T^{\prime}$ has $\Pr[|v\cdot X|\geq T^{\prime}]<1/N$ and since $X\sim S$ and $|S|=N$, this means that $\Pr[|v\cdot X|\geq T^{\prime}]=0$.

If $T<1$, $5\exp(T^{2}/2)/2+\delta/2T^{2}\geq 1$ and so the result is trivial. If $T\geq 2\sqrt{N/\delta}$, then $\Pr[|v\cdot X|\geq T]=0$. Otherwise, there is a $T^{\prime}$ with $T/2\leq T^{\prime}\leq T$ and thus $\Pr[|v\cdot X|\geq T^{\prime}]\leq\Pr[|v\cdot X|\geq T]\leq 5\exp(T^{2}/2)+\delta/T^{2}$. This completes the proof of Claim A.5. ∎

Let $C$ be a $1/5$-cover of the set of unit vectors including all coordinate directions of size $2^{O(d)}$. Then, by a union bound, Claim A.5 holds for $v\cdot X$ for all $v\in C$ except with probability $2^{d}\ln(N/\delta)\exp(-\Omega(N\delta/\log(1/\delta)))$, where $\delta=\frac{\varepsilon^{2}}{2\log^{3}\left(|S|/\tau\right)}$. This is smaller than $\tau/10$ when $\Omega(N\delta/\log(1/\delta))\geq\ln\ln(N/\delta)+d+\ln(1/\tau)$, which holds when $N$ is a sufficiently large multiple of $d\log(d/(\delta\tau))/\delta$. The latter statement in turn holds when $N$ is a sufficiently large multiple of $d\log^{4}(d/(\delta\tau))/\varepsilon^{2}$. We assume this holds in the following.

Now consider a unit vector $v$ and $T\geq 1$. Let $v_{1}=v$ and $T_{i}=T$. Let $v^{\prime}_{i}\in C$ have $\|v_{i}-v^{\prime}_{i}\|_{2}\leq 1/5$. Then let $v_{i+1}=(v_{i}-v^{\prime}_{i})/\|v_{i}-v^{\prime}_{i}\|_{2}$. If $x$ has $|v_{i}\cdot x|\geq T_{i}$, using the triangle inequality, it follows that either $|v^{\prime}_{i}\cdot x|\geq T_{i}/2$ or else $|v_{i+1}\cdot x|=(v_{i}-v^{\prime}_{i})/\|v_{i}-v^{\prime}_{i}\|_{2}\cdot x\geq T_{i}/2\|v_{i}-v^{\prime}_{i}\|_{2}\geq 2T_{i}$. So we let $T_{i+1}=2T_{i}$ and we have

If we iterate this procedure, for large enough $i$, we will have $T_{i}\geq 2\sqrt{dN/\delta}$, and so $\Pr[|v^{\prime}_{i}\cdot X|\geq T_{i}]=0$ and hence we have $\Pr[|v\cdot X|\geq T]\leq\sum_{i=1}^{\log(2\sqrt{dN/\delta})}\Pr[|v^{\prime}_{i}\cdot X|\geq T_{i}/2].$ By Claim A.5, we have $\Pr[|v^{\prime}_{i}\cdot X|\geq 2^{i-1}T]\leq 5\exp(-T^{2}2^{2i-3})+2^{-(2i-2)}\delta/T^{2}\leq 2^{-(2i-1)}(5\exp(-T^{2}/4)+2\delta/T^{2})$, and so

So we have shown that, for all $v$ and $T\geq 1$, $\Pr[|v\cdot X|\geq T]\leq 5\exp(T^{2}/4)+\frac{\varepsilon^{2}}{T^{2}\log^{3}\left(|S|/\tau\right)}$. Since this is trivial for $T\leq 1$, we are done. ∎

The following lemma proves property (ii) of Definition 2.2:

For all $T>0$, we have that $\Pr_{(X,y)\sim S}\left[|y(v\cdot X)/\sigma_{y}|>T\right]\leq 8\exp(-T/8)+\frac{\varepsilon}{T^{2}\log(N/\tau)}$.

The proof of the lemma will make essential use of the following elementary fact:

Notice that when $T<16$, the RHS is greater than $1$ and hence the inequality is trivial. When $T>4\sqrt{d}\log(N/\tau)$, by condition (i) of Definition 2.2, the LHS is which makes the inequality trivial as well. For the rest of the analysis we will assume $4\sqrt{d}\log(N/\tau)>T>16$. By Fact A.7, we can write that

By condition (i) of Definition 2.2, we have that $\Pr_{(X,y)\sim S}[|y/\sigma_{y}|\geq\sqrt{4\log N/\tau}]=0$.

Thus, we can set the integer parameter $t$ to be $\min\left\{\lceil\log_{2}T\rceil,\lceil\log_{2}(\sqrt{4\log N/\tau})\rceil\right\}$. By Claim A.4, the term $\Pr_{(X,y)\sim S}[|v\cdot X|\geq T]$ is at most $5\exp(-T^{2}/4)+\frac{\varepsilon}{T^{2}\log^{3}(N/\tau))}$. Due to the simple fact

We first establish an upper bound for $T\geq 8\log N/\tau$ in which case $a^{2}\leq T/2$. Each term in the summation above satisfies

Note that there exists a sufficiently large universal constant $C>0$ such that for $N>C/\varepsilon$, we have that $5\exp(-T/8)<\frac{16\varepsilon}{100T^{2}\log^{2}(N/\tau)}$, which implies that the exponential term is negligible for this range of $T$. There are at most $\lceil\log_{2}(\sqrt{4\log N/\tau})\rceil+1$ such terms in the summation, which yields an upper bound of the summation as $1.01(\lceil\log_{2}(\sqrt{4\log N/\tau})\rceil+1)\frac{16\varepsilon}{T^{2}\log^{2}(N/\tau)}\leq\exp(-T/4)+\frac{\varepsilon}{T^{2}\log(N/\tau)}$ for sufficiently large $N$.

We now prove an upper bound for the case that $T\leq 8\log N/\tau$. For $a=\sqrt{T/2}$, the first term in the min function satisfies $5\exp(-a^{2}/4)+\frac{\varepsilon}{a^{2}\log^{3}(N/\tau)}=5\exp(-T/8)+\frac{2\varepsilon}{T\log^{3}(N/\tau)}\leq 5\exp(-T/8)+\frac{16\varepsilon}{T^{2}\log^{2}(N/\tau)}$. Similarly, the second term in the min function satisfies $5\exp(-\frac{T^{2}}{16a^{2}})+\frac{\varepsilon 4a^{2}}{T^{2}\log^{3}(N/\tau)}\leq 5\exp(-T/8)+\frac{16\varepsilon}{T^{2}\log^{2}(N/\tau)}$. The first term monotonically decreases as $a$ gets larger. The second term monotonically increases as $a$ gets larger. We can thus conclude that

There are at most $\lceil\log_{2}T\rceil+1$ such terms, which yields an upper bound of

Now note that for $T\geq 16$, the above is smaller than $16\exp(-T/16)+\frac{\varepsilon}{T^{2}\log(N/\tau)}$ because we can assume $T\leq 4\sqrt{d}\log(N/\tau)$. Hence, we obtain an upper bound of $16\exp(-T/16)+\frac{\varepsilon}{T^{2}\log(N/\tau)}$, which completes the proof. ∎

The following lemma proves property (iii) of Definition 2.2:

For $N=\Omega(\frac{d}{\varepsilon^{2}}\operatorname{poly}\log(d/\varepsilon\tau))$, we have that $\|\beta_{S}-\beta\|_{2}\leq\varepsilon\sigma_{y}$, with probability at least $1-\tau/10$.

The proof requires two simple technical claims. Our first claim gives an explicit formula for the distribution of the projections of $yX$ in any direction:

where $Z_{1},Z_{2}\sim\operatorname{\mathcal{N}}(0,1)$ and $Z_{1},Z_{2}$ are independent.

Let $Y_{1}=v^{T}X,Y_{2}=\frac{(X-(v^{T}X)v)^{T}\beta+\varepsilon}{\sqrt{\sigma_{y}-v^{T}\beta}}$. Note that $Y_{1},Y_{2}\sim\operatorname{\mathcal{N}}(0,1)$ and are independent. Define $Z_{1}=\sqrt{\frac{\sigma_{y}+v^{T}\beta}{2\sigma_{y}}}Y_{1}+\sqrt{\frac{\sigma_{y}-v^{T}\beta}{2\sigma_{y}}}Y_{2},Z_{2}=-\sqrt{\frac{\sigma_{y}-v^{T}\beta}{2\sigma_{y}}}Y_{1}+\sqrt{\frac{\sigma_{y}+v^{T}\beta}{2\sigma_{y}}}Y_{2}$. It is now easy to verify that the claim statement holds. ∎

Our second claim gives a tight concentration inequality for $\beta_{S}$:

where $\|A\|_{F}^{2}=2N((v\cdot\beta)^{2}+\sigma_{y}^{2})$ and $\|A\|_{2}=\max(|v\cdot\beta-\sigma_{y}|,|v\cdot\beta+\sigma_{y}|)$.

where $\|A\|_{F}^{2}=2N((v\cdot\beta)^{2}+\sigma_{y}^{2})$ and $\|A\|_{2}=\max(|v\cdot\beta-\sigma_{y}|,|v\cdot\beta+\sigma_{y}|)$. This completes the proof. ∎

The following lemma proves property (iv) of Definition 2.2:

For $N=\Omega(\frac{d}{\varepsilon^{2}}\operatorname{poly}\log(d/\varepsilon\tau))$, we have that $\left\|M_{S}-(\sigma_{y}^{2}I+{\beta\beta^{T}})\right\|_{2}\leq{\sigma_{y}^{2}\varepsilon}$, with probability at least $1-\tau/10$.

The proof idea is the following: By standard results, it is straightforward to handle the concentration of the empirical covariance of a distribution with bounded support. Hence, we split the distribution into two parts. One part contains most of the probability mass and has almost identical covariance as the original distribution. In addition it has bounded support. The other part is unbounded but has small probability. We first argue that removing the second part has little effect on the covariance of the distribution. Then the empirical covariance concentration result follows easily.

Applying Claim A.10 with $N=1$, we get $\Pr[|(v\cdot X)y-v\cdot\beta|\geq t]\leq 2\exp(-c_{0}(\frac{t}{\sigma_{y}}))$ for some absolute constant $c_{0}$. Notice that $\Pr[|y(v\cdot X)|>t+|v\cdot\beta|]\leq\Pr[|y(v\cdot X)-v\cdot\beta|>t]$, which is equivalent to $\Pr[|(v\cdot X)y|\geq t]\leq\exp(-c_{0}(\frac{t-|v\cdot\beta|}{\sigma_{y}}))\leq\exp(-c_{0}(\frac{t}{\sigma_{y}}-1))$. Pick appropriate $t=\Theta(\sigma_{y}\log(\frac{|S|}{\tau}))$ such that $\Pr[|y(v\cdot X)|>t]\leq 2\exp(-\Omega(\log(\frac{|S|}{\tau})))=\frac{\tau}{|S|}$. Notice that $t\geq t^{\prime}$ and we can rewrite Equation (2) as

By Equation (1), $vF^{\prime}v=vFv+\sigma_{y}^{2}O(\log^{2}(\frac{|S|}{\tau})\frac{\tau}{|S|}+\frac{\tau}{|S|})=vFv+\sigma_{y}^{2}O(\log^{2}(\frac{|S|}{\tau})\frac{\tau}{|S|})$ and hence $\|F-F^{\prime}\|_{2}=\sigma_{y}^{2}O(\log^{2}(\frac{|S|}{\tau})\frac{\tau}{|S|})$.

Given $|S|=N=\Omega((d/\varepsilon^{2})\operatorname{poly}\log(d/\varepsilon\tau))$, we have $\log^{2}(\frac{|S|}{\tau})\frac{\tau}{|S|}=O(\varepsilon)$, and hence with probability at least $1-\tau/5$, $\|M_{S}-(\sigma_{y}^{2}I+\beta\beta^{T})\|=O(\varepsilon\sigma_{y}^{2})$.

This completes the proof of Proposition 2.3.

A.1 Handling Approximate Identity Covariance

In this subsection, we discuss the case where the covariance matrix of $X$ is not exactly identity, but instead satisfies $(1-\varepsilon)I\preceq\Sigma\preceq(1+\varepsilon)I.$ We will prove that a slightly modified deterministic regularity condition (i.e., Definition 2.2) still holds for this setting. The same algorithm yields an estimate of $\beta$ with the same guarantee as the exact case.

We prove the all the conditions in Definition 2.2 will be satisfied by reducing to the identity covariance case and applying Proposition A.12. Let $Z=\Sigma^{-1/2}X$, we have that pair $(y,Z)$ follows the setting of Proposition 2.3, where $Z\sim\operatorname{\mathcal{N}}(0,I)$ and $y=\beta^{T}\Sigma^{1/2}Z+\sigma E$. Let $S_{a}$ be the set that contains pairs $(y,\Sigma^{-1/2}X)$.

For condition (i), we can apply Proposition A.12 and get $|\frac{yX}{\sigma_{y}}|\leq(1+\varepsilon)|\frac{y(\Sigma^{1/2}Z)}{\sqrt{\beta^{T}\Sigma\beta+\sigma^{2}}}|\leq(1+\varepsilon)4\sqrt{d}\log(|S|/\tau)$ and $|\frac{y}{\sigma_{y}}|\leq\sqrt{1+\varepsilon}|\frac{y}{\sqrt{\beta^{T}\Sigma\beta+\sigma^{2}}}|\leq\sqrt{1+\varepsilon}\sqrt{4\log(|S|/\tau)}.$

Appendix B Proof of Proposition 2.1

We start by proving concentration bounds for $L$. In particular, we show:

We have that $\|M_{L}\|_{2}/\sigma_{y}^{2}={O\left(\log^{2}(|S|/|L|)+\varepsilon|S|/|L|\right)}.$

For unit vectors $v$, the RHS is bounded from above as follows:

where the third line follows from the fact that $|v\cdot\beta|/\sigma_{y}\leq 1$, the fourth line holds since the probability must be less than $1$, $S$ satisfies condition (i) of Definition 2.2 and Equation 6; and the fifth line follows from condition (iii) of Definition 2.2. ∎

We have that $M_{S^{\prime}}=(\sigma_{y}^{2}I+\beta\beta^{T})+(|E|/|S^{\prime}|)M_{E}+O(\sigma_{y}^{2}\varepsilon\log^{2}(1/\varepsilon))$, where the $O(\sigma_{y}^{2}\varepsilon\log^{2}(1/\varepsilon))$ term denotes a matrix of spectral norm $O(\sigma_{y}^{2}\varepsilon\log^{2}(1/\varepsilon))$.

By definition, we have that $|S^{\prime}|M_{S^{\prime}}=|S|M_{S}-|L|M_{L}+|E|M_{E}$. Thus, we can write

where the second line uses the fact that $1-2\varepsilon\leq|S|/|S^{\prime}|\leq 1+2\varepsilon$, the goodness of $S$ (condition (iv) in Definition 2.2), and Lemma B.1. Specifically, Lemma B.1 implies that $(|L|/|S^{\prime}|)\|M_{L}\|_{2}=O(\sigma_{y}^{2}\varepsilon\log^{2}(1/\varepsilon))$. Therefore, we have that $M_{S^{\prime}}=\sigma_{y}^{2}I+\beta\beta^{T}+O(\sigma_{y}^{2}\varepsilon\log^{2}(1/\varepsilon))+(|E|/|S^{\prime}|)M_{E}$. ∎

By definition, we have that $|S^{\prime}|(\beta_{S^{\prime}}-\beta)=|S|({\beta_{S}-\beta})+|E|({\beta_{E}-\beta})-|L|(\beta_{L}-\beta)$. Since $S$ is a good set, by condition (iii) of Definition 2.2, we have $\|\beta_{S}-\beta\|\leq O(\sigma_{y}\varepsilon)$. Since $1-2\varepsilon\leq|S|/|S^{\prime}|\leq 1+2\varepsilon$, it follows that $(|S|/|S^{\prime}|)\|\beta_{S}-\beta\|=O(\sigma_{y}\varepsilon)$. Using the valid inequality $\|M_{L}\|_{2}\geq\|\beta_{L}-\beta\|_{2}^{2}$ and Lemma B.1, we obtain that $\|\beta_{L}-\beta\|_{2}/\sigma_{y}\leq O(\log(|S|/|L|)+\sqrt{\varepsilon|S|/|L|})$. Therefore, $(|L|/|S^{\prime}|)\|\beta_{L}-\beta\|_{2}/\sigma_{y}\leq O((|L|/|S|)\log(|S|/|L|)+\sqrt{\varepsilon|L|/|S|})\leq O(\varepsilon\log(1/\varepsilon))$. In summary, we have ${\beta_{S^{\prime}}-\beta}=(|E|/|S^{\prime}|)({\beta_{E}-\beta})+O(\sigma_{y}\varepsilon{\log(1/\varepsilon)})$ as desired. This completes the proof of the lemma. ∎