Sampling Algorithms and Coresets for Lp Regression

Introduction

An important question in algorithmic problem solving is whether there exists a small subset of the input such that if computations are performed only on this subset, then the solution to the given problem can be approximated well. Such a subset is often known as a coreset for the problem. The concept of coresets has been extensively used in solving many problems in optimization and computational geometry; e.g., see the excellent survey by Agarwal, Har-Peled, and Varadarajan .

(2) Subspace-preserving sampling. We show that sampling rows of ${A}$ according to information in the rows of a well-conditioned basis of $A$ minimizes the sampling variance and consequently, the rank of $A$ is not lost by sampling. This is critical for our relative-error approximation guarantees. The notion of subspace-preserving sampling was used in for $p=2$, but we abstract and generalize this concept for all $p\in[1,\infty)$.

We note that for $p=2$, our sampling complexity matches that of , which is $O(d^{2}/\epsilon^{2})$; and for $p=1$, it improves that of from $O(d^{3.5}(\log d)/\epsilon^{2})$ to $O(d^{2.5}/\epsilon^{2})$.

Overview of our methods. Given an input matrix $A$, we first construct a well-conditioned basis for $A$ and use that to obtain bounds on a slightly non-standard notion of a $p$-norm condition number of a matrix. The use of this particular condition number is crucial since the variance in the subspace preserving sampling can be upper bounded in terms of it. An $\varepsilon$-net argument then shows that the first stage sampling gives us a $8$-approximation. The next twist is to use the output of the first stage as a feedback to fine-tune the sampling probabilities. This is done so that the “positional information” of $b$ with respect to $A$ is also preserved in addition to the subspace. A more careful use of a different $\varepsilon$-net shows that the second stage sampling achieves a $(1+\epsilon)$-approximation.

2 Related work

Preliminaries

Two crucial ingredients in our proofs are $\varepsilon$-nets and tail-inequalities. A subset $\mathcal{N}(D)$ of a set $D$ is called an $\varepsilon$-net in $D$ for some $\varepsilon>0$ if for every $x\in D$, there is a $y\in\mathcal{N}(D)$ with $\left\lVert x-y\right\rVert\leq\varepsilon$. In order to construct an $\varepsilon$-net for ${D}$ it is enough to choose $\mathcal{N}(D)$ to be the maximal set of points that are pairwise $\varepsilon$ apart. It is well known that the unit ball of a $d$-dimensional space has an $\varepsilon$-net of size at most $(3/\varepsilon)^{d}$ .

Finally, throughout this paper, we will use the following sampling matrix formalism to represent our sampling operations. Given a set of $n$ probabilities, $p_{i}\in(0,1]$, for $i=1,\ldots,n$, let $S$ be an $n\times n$ diagonal sampling matrix such that $S_{ii}$ is set to $1/p_{i}^{1/p}$ with probability $p_{i}$ and to zero otherwise. Clearly, premultiplying ${A}$ or $b$ by $S$ determines whether the $i$-th row of ${A}$ and the corresponding element of $b$ will be included in the sample, and the expected number of rows/elements selected is $r^{\prime}=\sum_{i=1}^{n}p_{i}$. (In what follows, we will abuse notation slightly by ignoring zeroed out rows and regarding $S$ as an $r^{\prime}\times n$ matrix and thus $SA$ as an $r^{\prime}\times m$ matrix.) Thus, e.g., sampling constraints from Equation (1) and solving the induced subproblem may be represented as solving

Main technical ingredients

We introduce the following notion of a “well-conditioned” basis.

The existence and efficient construction of these bases is given by the following.

Let ${A}$ be an $n\times m$ matrix of rank $d$, let $p\in[1,\infty)$, and let $q$ be its dual norm. Then there exists an $(\alpha,\beta,p)$-well-conditioned basis ${U}$ for the column space of ${A}$ such that: if $p<2$, then $\alpha=d^{\frac{1}{p}+\frac{1}{2}}$ and $\beta=1$, if $p=2$, then $\alpha=d^{\frac{1}{2}}$ and $\beta=1$, and if $p>2$, then $\alpha=d^{\frac{1}{p}+\frac{1}{2}}$ and $\beta=d^{\frac{1}{q}-\frac{1}{2}}$. Moreover, ${U}$ can be computed in $O(nmd+nd^{5}\log n)$ time (or in just $O(nmd)$ time if $p=2$).

Let ${A}=QR$, where $Q$ is any $n\times d$ matrix that is an orthonormal basis for $\operatorname{span}({A})$ and $R$ is a $d\times m$ matrix. If $p=2$, then $Q$ is the desired basis ${U}$; from the discussion following Definition 3, $\alpha=\sqrt{d}$ and $\beta=1$, and computing it requires $O(nmd)$ time. Otherwise, fix $Q$ and $p$ and define the norm, $\left\lVert z\right\rVert_{Q,p}\triangleq\left\lVert Qz\right\rVert_{p}$ . A quick check shows that $\left\lVert\cdot\right\rVert_{Q,p}$ is indeed a norm. ($\left\lVert z\right\rVert_{Q,p}=0$ if and only if $z=0$ since $Q$ has full column rank; $\left\lVert\gamma z\right\rVert_{Q,p}=\left\lVert\gamma Qz\right\rVert_{p}=\lvert\gamma\rvert\left\lVert Qz\right\rVert_{p}=\lvert\gamma\rvert\left\lVert z\right\rVert_{Q,p}$; and $\left\lVert z+z^{\prime}\right\rVert_{Q,p}=\left\lVert Q(z+z^{\prime})\right\rVert_{p}\leq\left\lVert Qz\right\rVert_{p}+\left\lVert Qz^{\prime}\right\rVert_{p}=\left\lVert z\right\rVert_{Q,p}+\left\lVert z^{\prime}\right\rVert_{Q,p}$.)

where $\left\lVert z\right\rVert_{\text{\sc lj}}^{2}=z^{T}Fz$ (see, e.g. [9, pp. 413–4]). Since the matrix $F$ is symmetric positive definite, we can express it as $F=G^{T}G$, where $G$ is full rank and upper triangular. Since $Q$ is an orthogonal basis for $\operatorname{span}({A})$ and $G$ is a $d\times d$ matrix of full rank, it follows that ${U}=QG^{-1}$ is an $n\times d$ matrix that spans the column space of ${A}$. We claim that ${U}\triangleq QG^{-1}$ is the desired $p$-well-conditioned basis.

In order to construct $U$, we need to compute $Q$ and $G$ and then invert $G$. Our matrix ${A}$ can be decomposed into $QR$ using the compact $QR$ decomposition in $O(nmd)$ time. The matrix $F$ describing the Löwner–John ellipsoid of the unit ball of $\left\lVert\cdot\right\rVert_{Q,p}$ can be computed in $O(nd^{5}\log n)$ time. Finally, computing $G$ from $F$ takes $O(d^{3})$ time, and inverting $G$ takes $O(d^{3})$ time. ∎

2 Subspace-preserving sampling

In the previous subsection (and in the notation of the proof of Theorem 4), we saw that given $p\in[1,\infty)$, any $n\times m$ matrix ${A}$ of rank $d$ can be decomposed as

where $U=QG^{-1}$ is a $p$-well-conditioned basis for $\operatorname{span}(A)$ and $\tau=GR$. The significance of a $p$-well-conditioned basis is that we are able to minimize the variance in our sampling process by randomly sampling rows of the matrix ${A}$ and elements of the vector $b$ according to a probability distribution that depends on norms of the rows of the matrix ${U}$. This will allow us to preserve the subspace structure of $\operatorname{span}(A)$ and thus to achieve relative-error approximation guarantees.

More precisely, given $p\in[1,\infty)$ and any $n\times m$ matrix ${A}$ of rank $d$ decomposed as ${A}={U}\tau$, where ${U}$ is an $(\alpha,\beta,p)$-well-conditioned basis for $\operatorname{span}(A)$, consider any set of sampling probabilities $p_{i}$ for $i=1,\ldots,n$, that satisfy:

where $r=r(\alpha,\beta,p,d,\epsilon)$ to be determined below. Let us randomly sample the $i^{th}$ row of ${A}$ with probability $p_{i}$, for all $i=1,\ldots,n$. Recall that we can construct a diagonal sampling matrix $S$, where each $S_{ii}=1/p_{i}^{1/p}$ with probability $p_{i}$ and otherwise, in which case we can represent the sampling operation as $S{A}$.

The following theorem is our main result regarding this subspace-preserving sampling procedure.

Several things should be noted about this result. First, it implies that $\mbox{rank}(SA)=\mbox{rank}(A)$, since otherwise we could choose a vector $x\in\mbox{null}(SA)$ and violate the theorem. In this sense, this theorem generalizes the subspace-preservation result of Lemma $4.1$ of to all $p\in[1,\infty)$. Second, regarding sampling complexity: if $p<2$ the sampling complexity is $O(d^{\frac{p}{2}+2})$, if $p=2$ it is $O(d^{2})$, and if $p>2$ it is $O(dd^{\frac{1}{p}+\frac{1}{2}}d^{\frac{1}{q}-\frac{1}{2}})^{p}=O(d^{p+1})$. Finally, note that this theorem is analogous to the main result of Schechtman , which uses the notion of Auerbach bases.

The sampling algorithm

In the second stage, the algorithm uses information from the residual of the $8$-approximation computed in the first stage to refine the sampling probabilities. Define the residual $\hat{\rho}={A}\hat{x}_{c}-b$ (and note that $\|\hat{\rho}\|_{p}\leq 8\,{\cal Z}$). Then, roughly $O(d^{p+1}/\epsilon^{2})$ rows of ${A}$, and the corresponding elements of $b$, are randomly sampled according to the probability distribution

Note that since the algorithm of Figure 1 constructs the $(\alpha,\beta,p)$-well-conditioned basis ${U}$ using the procedure in the proof of Theorem 4, our sampling complexity depends on $\alpha$ and $\beta$. In particular, it will be $O(d(\alpha\beta)^{p})$. Thus, if $p<2$ our sampling complexity is $O(d\cdot d^{\frac{p}{2}+1})=O(d^{\frac{p}{2}+2})$; if $p>2$ it is $O(d(d^{\frac{1}{p}+\frac{1}{2}}d^{\frac{1}{q}-\frac{1}{2}})^{p})=O(d^{p+1})$; and (although not explicitly stated, our proof will make it clear that) if $p=2$ it is $O(d^{2})$. Note also that we have stated the claims of the theorem as holding with constant probability, but they can be shown to hold with probability at least $1-\delta$ by using standard amplification techniques.

2 Proof for first-stage sampling – constant-factor approximation

To prove the claims of Theorem 6 having to do with the output of the algorithm after the first stage of sampling, we begin with two lemmas. First note that, because of our choice of $r_{1}$, we can use the subspace preserving Theorem 5 with only a constant distortion, i.e., for all $x$, we have

with probability at least $0.99$. The first lemma below now states that the optimal solution to the original problem provides a small (constant-factor) residual when evaluated in the sampled problem.

$\left\lVert S(Ax_{\text{\sc opt}}-b)\right\rVert\leq 3{\cal Z}$, with probability at least $1-1/3^{p}$.

The next lemma states that if the solution to the sampled problem provides a constant-factor approximation (when evaluated in the sampled problem), then when this solution is evaluated in the original regression problem we get a (slightly weaker) constant-factor approximation.

If $\left\lVert S({A}\hat{x}_{c}-b)\right\rVert\leq 3\,{\cal Z}$, then $\left\lVert{A}\hat{x}_{c}-b\right\rVert\leq 8\,{\cal Z}$.

To conclude the proof of the claims for the first stage of sampling, note that by our choice of $r_{1}$, Theorem 5 fails to hold for our first stage sampling with probability no greater than $1/100$. In addition, Lemma 7 fails to hold with probability no grater than $1/3^{p}$, which is no greater than $1/3$ for all $p\in[1,\infty)$. Finally, let $\widehat{r_{1}}$ be a random variable representing the number of rows actually chosen by our sampling schema, and note that $E\!\left[\widehat{r_{1}}\right]\leq r_{1}$. By Markov’s inequality, it follows that $\widehat{r_{1}}>20r_{1}$ with probability less than $1/20$. Thus, the first stage of our algorithm fails to give an $8$-approximation in the specified running time with a probability bounded by $1/3+1/20+1/100<2/5$.

3 Proof for second-stage sampling – relative-error approximation

The proof of the claims of Theorem 6 having to do with the output of the algorithm after the second stage of sampling will parallel that for the first stage, but it will have several technical complexities that arise since the first triangle inequality approximation in the proof of Lemma 8 is too coarse for relative-error approximation. By our choice of $r_{2}$ again, we have a finer result for subspace preservation. Thus, with probability $0.99$, the following holds for all $x$

As before, we start with a lemma that states that the optimal solution to the original problem provides a small (now a relative-error) residual when evaluated in the sampled problem. This is the analog of Lemma 7. An important difference is that the second stage sampling probabilities significantly enhance the probability of success.

$\left\lVert T(A{x}_{\text{\sc opt}}-b)\right\rVert\leq(1+\epsilon){\cal Z}$, with probability at least $0.99$.

Next we show that if the solution to the sampled problem provides a relative-error approximation (when evaluated in the sampled problem), then when this solution is evaluated in the original regression problem we get a (slightly weaker) relative-error approximation. We first establish two technical lemmas.

The following lemma says that for all optimal solutions $\hat{x}_{\text{\sc opt}}$ to the second-stage sampled problem, ${A}\hat{x}_{\text{\sc opt}}$ is not too far from ${A}\hat{x}_{c}$, where $\hat{x}_{c}$ is the optimal solution from the first stage, in a $p$-norm sense. Hence, the lemma will allow us to restrict our calculations in Lemmas 11 and 12 to the ball of radius $12\,{\cal Z}$ centered at ${A}\hat{x}_{c}$.

$\left\lVert{A}\hat{x}_{\text{\sc opt}}-{A}\hat{x}_{c}\right\rVert\leq 12\,{\cal Z}$.

Thus, if we define the affine ball of radius $12\,{\cal Z}$ that is centered at ${A}\hat{x}_{c}$ and that lies in $\operatorname{span}({A})$,

then Lemma 10 states that ${A}\hat{x}_{\text{\sc opt}}\in B$, for all optimal solutions $\hat{x}_{\text{\sc opt}}$ to the sampled problem. Let us consider an $\varepsilon$-net, call it $B_{\varepsilon}$, with $\varepsilon=\epsilon\,{\cal Z}$, for this ball $B$. Using standard arguments, the size of the $\varepsilon$-net is $\left(\frac{3\cdot 12\,{\cal Z}}{\epsilon\,{\cal Z}}\right)^{d}=\left(\frac{36}{\epsilon}\right)^{d}$. The next lemma states that for all points in the $\varepsilon$-net, if that point provides a relative-error approximation (when evaluated in the sampled problem), then when this point is evaluated in the original regression problem we get a (slightly weaker) relative-error approximation.

For all points $Ax_{\varepsilon}$ in the $\varepsilon$-net, $B_{\varepsilon}$, if $\left\lVert T(Ax_{\varepsilon}-b)\right\rVert\leq(1+3\epsilon){\cal Z}$, then $\left\lVert Ax_{\varepsilon}-b\right\rVert\leq(1+6\epsilon){\cal Z}$, with probability $0.99$.

Finally, the next lemma states that if the solution to the sampled problem (in the second stage of sampling) provides a relative-error approximation (when evaluated in the sampled problem), then when this solution is evaluated in the original regression problem we get a (slightly weaker) relative-error approximation. This is the analog of Lemma 8, and its proof will use Lemma 11.

If $\left\lVert T({A}\hat{x}_{\text{\sc opt}}-b)\right\rVert\leq(1+\epsilon){\cal Z}$, then $\left\lVert{A}\hat{x}_{\text{\sc opt}}-b\right\rVert\leq(1+7\epsilon){\cal Z}$.

To conclude the proof of the claims for the second stage of sampling, recall that the first stage failed with probability no greater than $2/5$. Note also that by our choice of $r_{2}$, Theorem 5 fails to hold for our second stage sampling with probability no greater than $1/100$. In addition, Lemma 9 and Lemma 11 each fails to hold with probability no greater than 1/100. Finally, let $\widehat{r_{2}}$ be a random variable representing the number of rows actually chosen by our sampling schema in the second stage, and note that $E\!\left[\widehat{r_{2}}\right]\leq 2r_{2}$. By Markov’s inequality, it follows that $\widehat{r_{2}}>40r_{2}$ with probability less than $1/20$. Thus, the second stage of our algorithm fails with probability less than $1/20+1/100+1/100+1/100<1/10$. By combining both stages, our algorithm fails to give a $(1+\epsilon)$-approximation in the specified running time with a probability bounded from above by $2/5+1/10=1/2$.

Extensions

In this section we outline several immediate extensions of our main algorithmic result.

References

Appendix A Tail inequalities

With respect to tail inequalities, we will use the following version of the Bernstein’s inequality.

Let $\{X_{i}\}_{i=1}^{n}$ be independent random variables with $E[X_{i}^{2}]<\infty$ and $X_{i}\geq 0$. Set $Y=\sum_{i}X_{i}$ and let $\gamma>0$. Then

If $X_{i}-E[X_{i}]\leq\Delta$ for all $i$, then with $\sigma_{i}^{2}=E[X_{i}^{2}]-E[X_{i}]^{2}$ we have

Appendix B Proofs for Section 3

Equation 12 follows since, according to the definition of $p_{i}$ in Equation (5), $p_{i}$ may equal $1$ for some rows, and since these rows are always included in the random sample, $X_{i}=E\!\left[X_{i}\right]$ for these rows. To bound the right hand side of Equation 12, note that for all $i$ such that $p_{i}<1$,

From Equation (13), if follows that for each $i$ such that $p_{i}<1$,

Thus, we may define $\Delta=(\alpha\beta)^{p}\left\lVert Ax\right\rVert^{p}/r$. In addition, it also follows from Equation (13) that

from which it follows that $\sum_{i:p_{i}<1}\sigma_{i}^{2}\leq\sum_{i:p_{i}<1}E\!\left[X_{i}^{2}\right]\leq(\alpha\beta)^{p}\left\lVert Ax\right\rVert^{2p}/r$.

To apply the upper tail bound in Theorem 13, define $\gamma=((1+\epsilon/4)^{p}-1)\left\lVert Ax\right\rVert^{p}$. It follows that $\gamma^{2}\geq(p\epsilon/4)^{2}\left\lVert Ax\right\rVert^{2p}$ and also that

where the second inequality follows by standard manipulations since $\epsilon\leq 1$ and since $p\geq 1$. Thus, by Equation (10) of Theorem 13, it follows that

Similarly, to apply the lower tail bound of Equation (9) of Theorem 13, define $\gamma=(1-(1-\epsilon/4)^{p})\left\lVert Ax\right\rVert^{p}$. Since $\gamma\geq\epsilon\left\lVert Ax\right\rVert^{p}/4$, we can follow a similar line of reasoning to show that

Choosing $r\geq 32^{p}(\alpha\beta)^{p}(d\ln(\frac{12}{\epsilon})+\ln(\frac{2}{\delta}))/(p^{2}\epsilon^{2})$, we get that for every fixed $x$, the following is true with probability at least $1-\left(\frac{\epsilon}{12}\right)^{d}\delta$:

where the last inequality follows since $\left\lVert y^{*}-y^{*}_{\varepsilon}\right\rVert\leq\varepsilon$, $(y^{*}-y^{*}_{\varepsilon})/\varepsilon\in B$, and

Appendix C Proofs for Section 4

Define $X_{i}=(S_{ii}\lvert{{A}}_{i\star}x_{\text{\sc opt}}-b_{i}\rvert)^{p}$. Thus, $\sum_{i}X_{i}=\left\lVert S(Ax_{\text{\sc opt}}-b)\right\rVert^{p}$, and the first moment is $E\!\left[\sum_{i}X_{i}\right]=\left\lVert Ax_{\text{\sc opt}}-b\right\rVert^{p}={\cal Z}$. The lemma follows since, by Markov’s inequality,

i.e., $\left\lVert S(Ax_{\text{\sc opt}}-b)\right\rVert^{p}>3^{p}\left\lVert Ax_{\text{\sc opt}}-b\right\rVert^{p}$, with probability no more than $1/3^{p}$. ∎

C.2 Proof of Lemma 8

We will prove the contrapositive: If $\left\lVert{A}\hat{x}_{c}-b\right\rVert>8\,{\cal Z}$, then $\left\lVert S({A}\hat{x}_{c}-b)\right\rVert>3\,{\cal Z}$. To do so, note that, by Theorem 5, and the choice of $r_{1}$, we have that

C.3 Proof of Lemma 9

Define the random variable $X_{i}=(T_{ii}\lvert{{A}}_{i\star}x_{\text{\sc opt}}-b_{i}\rvert)^{p}$, and recall that ${A}_{i\star}={U}_{i\star}\tau$ since ${A}={U}\tau$. Clearly, $\sum_{i=1}^{n}X_{i}=\left\lVert T({A}x_{\text{\sc opt}}-b)\right\rVert^{p}$. In addition, since $E\!\left[X_{i}\right]=\lvert{{A}}_{i\star}x_{\text{\sc opt}}-b_{i}\rvert^{p}$, it follows that $\sum_{i=1}^{n}E\!\left[X_{i}\right]=\left\lVert{A}x_{\text{\sc opt}}-b\right\rVert^{p}$. We will use Equation (10) of Theorem 13 to provide a bound for $\sum_{i}\left(X_{i}-E\!\left[X_{i}\right]\right)=\left\lVert T({A}x_{\text{\sc opt}}-b)\right\rVert^{p}-\left\lVert{A}x_{\text{\sc opt}}-b\right\rVert^{p}$.

From the definition of $q_{i}$ in Equation (7), it follows that for some of the rows, $q_{i}$ may equal $1$ (just as in the proof of Theorem 5). Since $X_{i}=E\!\left[X_{i}\right]$ for these rows, $\sum_{i}\left(X_{i}-E\!\left[X_{i}\right]\right)=\sum_{i:p_{i}<1}\left(X_{i}-E\!\left[X_{i}\right]\right)$, and thus we will bound this latter quantity with Equation (10). To do so, we must first provide a bound for $X_{i}-E\!\left[X_{i}\right]\leq X_{i}$ and for $\sum_{i:p_{i}<1}\sigma_{i}^{2}\leq\sum_{i}E\!\left[X_{i}^{2}\right]$. To that end, note that:

where the final inequality follows from the definition of ${\cal Z}$ and the results from the first stage of sampling. Next, note that from the conditions on the probabilities $q_{i}$ in Equation (7), as well as by Definition 3 and the output of the first-stage of sampling, it follows that

Thus, since $X_{i}-E\!\left[X_{i}\right]\leq X_{i}\leq\lvert{{A}}_{i\star}x_{\text{\sc opt}}-b_{i}\rvert^{p}/q_{i}$, it follows that for all $i$ such that $q_{i}<1$,

where we set $c_{p}=2^{p-1}(9^{p}+8^{p})$. Thus, we may define $\Delta=c_{p}(\alpha\beta)^{p}{\cal Z}^{p}/r_{2}$. In addition, it follows that

To apply the upper tail bound of Equation (10) of Theorem 13, define $\gamma=((1+\epsilon)^{p}-1){\cal Z}^{p}$. We have $\gamma\geq p\epsilon\,{\cal Z}^{p}$, and since $\epsilon\leq 1/7$, we also have $\gamma\leq\left(\left(\frac{8}{7}\right)^{p}-1\right){\cal Z}^{p}$. Hence, by Equation (10) of Theorem 13, it follows that

Thus, ${\rm Pr}\left[{\left\lVert T(Ax_{\text{\sc opt}}-b)\right\rVert>(1+\epsilon){\cal Z}}\right]\leq\exp\left(\frac{-p^{2}\epsilon^{2}r_{2}}{36^{p}(\alpha\beta)^{p}}\right)$, from which the lemma follows by our choice of $r_{2}$. ∎

C.4 Proof of Lemma 10

By two applications of the triangle inequality, it follows that

where the second inequality follows since $\left\lVert{A}\hat{x}_{c}-b\right\rVert\leq 8\,{\cal Z}$ from the first stage of sampling and since ${\cal Z}=\left\lVert{A}x_{\text{\sc opt}}-b\right\rVert$. In addition, we have that

where the third inequality follows since $\hat{x}_{\text{\sc opt}}$ is optimal for the sampled problem. The lemma follows since $\epsilon\leq 1/7$. ∎

C.5 Proof of Lemma 11

Fix a given point $y^{*}_{\varepsilon}=Ax^{*}_{\varepsilon}\in B_{\varepsilon}$. We will prove the contrapositive for this point, i.e., we will prove that if $\left\lVert Ax^{*}_{\varepsilon}-b\right\rVert>(1+6\epsilon){\cal Z}$, then $\left\lVert T(Ax^{*}_{\varepsilon}-b)\right\rVert>(1+3\epsilon){\cal Z}$, with probability at least $1-\frac{1}{100}\left(\frac{\epsilon}{36}\right)^{d}$. The lemma will then follow from the union bound.

To this end, define the random variable $X_{i}=(T_{ii}\lvert{{A}}_{i\star}x^{*}_{\varepsilon}-b_{i}\rvert)^{p}$, and recall that ${{A}}_{i\star}={{U}}_{i\star}\tau$ since ${A}={U}\tau$. Clearly, $\sum_{i=1}^{n}X_{i}=\left\lVert T({A}x^{*}_{\varepsilon}-b)\right\rVert^{p}$. In addition, since $E\!\left[X_{i}\right]=\lvert{{A}}_{i\star}x^{*}_{\varepsilon}-b_{i}\rvert^{p}$, it follows that $\sum_{i=1}^{n}E\!\left[X_{i}\right]=\left\lVert{A}x^{*}_{\varepsilon}-b\right\rVert^{p}$. We will use Equation (9) of Theorem 13 to provide an upper bound for the event that $\left\lVert T({A}x^{*}_{\varepsilon}-b)\right\rVert^{p}\leq\left\lVert{A}x^{*}_{\varepsilon}-b\right\rVert^{p}-\gamma$, where $\gamma=\left\lVert Ax^{*}_{\varepsilon}-b\right\rVert^{p}-(1+3\epsilon)^{p}{\cal Z}^{p}$, under the assumption that $\left\lVert Ax^{*}_{\varepsilon}-b\right\rVert>(1+6\epsilon){\cal Z}$.

From the definition of $q_{i}$ in Equation (7), it follows that for some of the rows, $q_{i}$ may equal $1$ (just as in the proof of Theorem 5). Since $X_{i}=E\!\left[X_{i}\right]$ for these rows, $\sum_{i}\left(X_{i}-E\!\left[X_{i}\right]\right)=\sum_{i:p_{i}<1}\left(X_{i}-E\!\left[X_{i}\right]\right)$, and thus we will bound this latter quantity with Equation (9). To do so, we must first provide a bound for $\sum_{i:p_{i}<1}E\!\left[X_{i}^{2}\right]$. To that end, note that:

where the final inequality follows from the radius of the high-dimensional ball in which the $\varepsilon$-net resides. From this, we can show that

To apply the lower tail bound of Equation (9) of Theorem 13, define $\gamma=\left\lVert Ax^{*}_{\varepsilon}-b\right\rVert^{p}-(1+3\epsilon)^{p}{\cal Z}^{p}$. Thus, by Equation (21) and by Equation (9) of Theorem 13 it follows that

Since $r_{2}\geq 24^{p}(\alpha\beta)^{p}(d\ln(\frac{36}{\epsilon})+\ln(200))/\epsilon^{2}$, it follows that $\left\lVert T(Ax^{*}_{\varepsilon}-b)\right\rVert\leq(1+3\epsilon){\cal Z}$, with probability no greater than $\frac{1}{200}\left(\frac{\epsilon}{36}\right)^{d}$. Since there are no more than $\left(\frac{36}{\epsilon}\right)^{d}$ such points in the $\varepsilon$-net, the lemma follows by the union bound. ∎

C.6 Proof of Lemma 12

We will prove the contrapositive: If $\left\lVert{A}\hat{x}_{\text{\sc opt}}-b\right\rVert>(1+7\epsilon){\cal Z}$ then $\left\lVert T({A}\hat{x}_{\text{\sc opt}}-b)\right\rVert>(1+\epsilon){\cal Z}$. Since ${A}\hat{x}_{\text{\sc opt}}$ lies in the ball $B$ defined by Equation (8) and since the $\varepsilon$-net is constructed in this ball, there exists a point $y_{\varepsilon}=Ax_{\varepsilon}$, call it ${A}x^{*}_{\varepsilon}$, such that $\left\lVert{A}\hat{x}_{\text{\sc opt}}-{A}x^{*}_{\varepsilon}\right\rVert\leq\epsilon\,{\cal Z}$. Thus,

Next, since Lemma 11 holds for all points ${A}x_{\varepsilon}$ in the $\varepsilon$-net, it follows that