Let $G:\mathbb R_{\geq 0}\to\mathbb R_{\geq 0}$ be a nonnegative convex function with $G(0) = 0$. Then for $\bfy\in\mathbb R^n$, the Orlicz norm of $\bfy$ is defined by

\[
\norm*{\bfx}_G = \inf\braces*{t > 0 : \sum_{i=1}^n G(\abs*{\bfy_i}/t) \leq 1}.
\]

Given a set of nonnegative weights $\bfw\in\mathbb R^n$, the weighted Orlicz norm of $\bfy$ is defined by

\[
\norm*{\bfx}_{G,\bfw} = \inf\braces*{t > 0 : \sum_{i=1}^n \bfw_i G(\abs*{\bfy_i}/t) \leq 1}.
\]

We can naturally define the sensitivty of Orlicz norms as follows.

Let $\bfA\in\mathbb R^{n\times d}$. We define the $i$th Orlicz sensitivity by

\[
\bfs_i^G(\bfA) \coloneqq \sup_{\bfx\in\mathbb R^d, \norm*{\bfA\bfx}_G \leq 1} G(\abs*{[\bfA\bfx](i)}) = \sup_{\bfx\in\mathbb R^d, \bfA\bfx\neq 0} G\parens*{\frac{\abs*{[\bfA\bfx](i)}}{\norm*{\bfA\bfx}_G}}
\]

Let $\bfw\geq\mathbf{1}_n$ be a set of weights. We define the $i$th weighted Orlicz sensitivity by

\[
\bfs_i^{G,\bfw}(\bfA) \coloneqq \sup_{\bfx\in\mathbb R^d, \norm*{\bfA\bfx}_G \leq 1} \bfw_i G(\abs*{[\bfA\bfx](i)}) = \sup_{\bfx\in\mathbb R^d, \bfA\bfx\neq 0} \bfw_i G\parens*{\frac{\abs*{[\bfA\bfx](i)}}{\norm*{\bfA\bfx}_G}}
\]

The Orlicz norm can be thought of as a scale invariant version of $M$-estimators, and is the gauge norm of the $M$-ball of radius $1$. By homogeneity of the Orlicz norm, we can then restrict our attention to radius $1$, where the Orlicz norm is equivalent to the corresponding $M$-norm. Thus, our results for $M$-estimators from earlier easily carry forth to Orlicz norms. For instance, the following corollary is a simple consequence of Theorem <ref>:

Let $\bfA\in\mathbb R^{n\times d}$. Let $G:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ be an Orlicz function that is polynomially bounded above with degree $p_G$, and satisfies the requirements analogous to those for $M$ in Theorem <ref>. Let $1\leq \tau\leq n$ be a parameter. Then, with probability at least $99/100$, Algorithm <ref> computes upper bounds $\tilde\bfs_i^G(\bfA)$ on Orlicz sensitivities $\bfs_i^G(\bfA)$ that sum to at most

\[
\tilde{\mathcal T}^G(\bfA) \coloneqq \sum_{i=1}^n \tilde\bfs_i^G(\bfA) = O(d^{\max\{1,p_G/2\}}\log^2 n + \tau).
\]

If constant factor Lewis weight approximation takes for an $n\times d$ matrix $\bfB$ takes $O(\nnz(\bfB)\log n + T)$ time (see Theorem <ref>), then the total running time is

\[
O\parens*{\nnz(\bfA)\log^3 n + \frac{nT}{\tau}\log n}.\qedhere
\]

As with $M$-estimators, we can also extend these results to the weighted case. The following lemma is a version of Lemma <ref> (or Lemma 39 in [21]), but requires a slightly different proof due to the fact that Orlicz norms are not “entrywise” norms.

Let $\bfw\in\mathbb R^n$ with $\bfw \geq \mathbf{1}^n$. Let $N\coloneqq \ceil*{\log_2(1+\norm*{\bfw}_\infty)}$. For $j\in[N]$, let

\[
T_j\coloneqq \braces*{i\in[n] : 2^{j-1} \leq \bfw_i < 2^j},
\]

let $\bfA\mid_{T_j}$ denote the restriction of $\bfA$ to the rows of $T_j$, and let $G_j \coloneqq 2^{j-1}\cdot G$. Then,

\[
\bfs_i^{G,\bfw}(\bfA) \leq 2\cdot \bfs_i^{G_j}(\bfA\mid_{T_j})
\]

\[
\sum_{i=1}^n \bfs_i^{G,\bfw}(\bfA) \leq O\parens*{N\cdot d^{\max\{1,p_G/2\}}\log n}.
\]

The proof can be found in Appendix <ref>.

The following is the resulting corollary for efficient computation of upper bounds on weighted Orlicz sensitivities, analogous to Corollary <ref> for $M$-estimators.

Let $G$ satisfy the hypotheses of Corollary <ref> and let $p_G$ be the polynomial upper bound exponent for $G$. Let $\bfw\geq\mathbf{1}_n$ be a set of weights. Define $N$ as in Lemma <ref>. There is an algorithm that computes weighted Orlicz norm sensitivities that sum to at most $O(Nd^{\max\{1,p_G/2\}}\log^2 n + N\tau)$ in time

\[
O\parens*{\nnz(\bfA)\log^3 n + N\frac{nT}{\tau}\log n},
\]

where $T$ is such that constant factor $\ell_{p_G}$ Lewis weight approximation for an $n\times d$ matrix $\bfB$ takes $O(\nnz(\bfB)\log n + T)$ time (see Theorem <ref>).

This is simply the result of applying Corollary <ref> on the $N$ matrices $\bfA\mid_{T_j}$ as defined in Lemma <ref>.

With upper bounds on Orlicz sensitivities in hand, we immediately obtain subspace embeddings by sampling from them.

Let $\bfA\in\mathbb R^{n\times d}$ and $\eps>0$. Let $G:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ be a convex Orlicz function satisfying the requirements analogous to those for $M$ in Theorem <ref>. Let $\bfw\geq\mathbf{1}_n$ be a set of weights. Let $\tilde\bfs_i^G(\bfA)\geq \bfs_i^{G,\bfw}(\bfA)$ be upper bounds on the weighted Orlicz sensitivities of $\bfA$ (see Definition <ref>) and let

\[
\tilde{\mathcal T}^{G,\bfw}(\bfA) \coloneqq \sum_{i=1}^n \tilde\bfs_i^{G,\bfw}(\bfA).
\]

Let $m\geq m_0$ be a parameter larger than some

\[
m_0 = O\parens*{\frac{d}{\eps^2}\parens*{\log\frac1\eps}\parens*{\log\frac1\delta}}.
\]

Let $\bfw'\geq \mathbf{1}_n$ be a set of weights chosen randomly so that

\[
\bfw_i' \coloneqq \begin{cases}
\bfw_i/\bfp_i & \text{w.p. $\bfp_i$} \\
0 & \text{otherwise}
\end{cases}
\]

\[
\bfp_i \coloneqq \min\braces*{1, m\cdot \tilde\bfs_i^{G,\bfw}(\bfA)}
\]

Then with probability at least $1 - \delta$,

\[
\norm*{\bfy}_{G,\bfw'} = (1\pm\eps)\norm*{\bfy}_{G,\bfw}
\]

for all $\bfy\in\Span(\bfA)$. Furthermore,

\[
\E\nnz(\bfw') \leq m\tilde{\mathcal T}^{G,\bfw}(\bfA).
\]

The proof follows from the proof of Lemma 7 of [61], replacing their sampling process with our sensitivity sampling. We only briefly outline the necessary changes, since the proof is almost identical to their proof, as well as other sensitivity Bernstein bounds done in this paper, such as Lemma <ref>.

By Lemma <ref>, it suffices to show that $\norm*{\bfy}_{G,\bfw'} = (1\pm\eps)\norm*{\bfy}_{G,\bfw}$ for all $\bfy\in\mathcal N$ where $\mathcal N$ is an $\eps$-net on the unit Orlicz sphere. Such a net can be chosen to have size at most $\log\abs*{\mathcal N} \leq O(d\log\frac1\eps)$ by Lemma <ref>.

It is shown in the proof of Lemma 7 of [61] that if

\[
\sum_{i=1}^n \bfw_i' G(\abs*{\bfy_i}) \in \bracks*{1-\frac\eps4, 1+\frac\eps4},
\]

then $\norm*{\bfy}_{G,\bfw'} \in [1-\eps/4,1+\eps/4]$ as long as $G(0) = 0$ and $G$ is convex. Then, the result follows from exactly the same sensitivity sampling and Bernstein bound calculation as done in Lemma <ref>.

§.§ Nearly Input Sparsity Time Algorithms

Lemma <ref> immediately yields subspace embeddings of size $O(d^{\max\{2,p_G/2+1\}}\poly(\log n, \eps^{-1}))$ by computing Orlicz sensitivity upper bounds as in Corollary <ref> with $\tau = 1$. However, this does not yield input sparsity time algorithms, and as done in previous sections (see, e.g., Theorem <ref>), we can apply Theorem <ref> in a two step process in order to obtain these subspace embeddings in nearly input sparsity time.

We first obtain sensitivity upper bounds $\tilde\bfs_i^G(\bfA)$ by Corollary <ref> with $\tau = T$, so that they sum to

\[
\tilde{\mathcal T}^G(\bfA) = \sum_{i=1}^n \tilde\bfs_i^G(\bfA) = O\parens*{d^{\max\{1,p_G/2\}}\log^2 n + T}
\]

and can be computed in time

\[
O\parens*{\nnz(\bfA)\log^3 n + n\log n} = O\parens*{\nnz(\bfA)\log^2 n}.
\]

Then by Lemma <ref>, we can obtain a set of weights $\bfw$ such that

\[
\nnz(\bfw) \leq O\parens*{(d^{\max\{1,p_G/2\}}\log^2 n + T) \cdot \frac{d}{\eps^2}\log\frac1\eps}
\]

with constant probability, and

\[
\norm*{\bfy}_{G,\bfw} = (1\pm\eps)\norm*{\bfy}_G
\]

for all $\bfy\in\Span(\bfA)$. We then compute weighted Orlicz sensitivities $\tilde\bfs_i^{G,\bfw}(\bfA)$ for $\bfw$ via Corollary <ref> with $\tau = d$. Since the sensitivity upper bounds are at least $1/n$, $\norm*{\bfw}_\infty = O(n)$ so that the weighted Orlicz sensitivity upper bounds sum to at most

\[
\tilde{\mathcal T}^G(\bfA) = \sum_{i=1}^n \tilde\bfs_i^G(\bfA) = O\parens*{d^{\max\{1,p_G/2\}}\log^3 n}.
\]

Furthermore, the number of nonzero entries rows is at most $\nnz(\bfw)$, so these can be computed in time at most

\[
O\parens*{\nnz(\bfA)\log^3 n + \frac{(Td^{\max\{1,p_G/2\}} + T^2)\log^4 n}{\eps^2}\log\frac1\eps},
\]

Again applying Lemma <ref>, we can obtain a random set of weights $\bfw'$ such that, with constant probability,

\[
\nnz(\bfw') \leq O\parens*{d^{\max\{1,p_G/2\}}\log^3 n \cdot \frac{d}{\eps^2}\log\frac1\eps} = O\parens*{\frac{d^{\max\{2,p_G/2+1\}} \log^3 n}{\eps^2}\log\frac1\eps}
\]

\[
\norm*{\bfy}_{G,\bfw'} = (1\pm\eps)\norm*{\bfy}_{G,\bfw} = (1\pm\eps)^2\norm*{\bfy}_G
\]

for all $\bfy\in\Span(\bfA)$. Rescaling $\eps$ by constant factors gives the desired conclusion.

§ APPLICATIONS: ROBUST SUBSPACE APPROXIMATION

By using our improvements in sensitivity sampling, we are able to obtain improvements to the robust subspace approximation algorithms of [21].

In the subspace approximation problem, we are given a matrix $\bfA\in\mathbb R^{n\times d}$, which we think of as a set of $n$ points in $\mathbb R^d$. Our task is then to compute a $d\times d$ rank $k$ projection matrix $\bfX$ that minimizes

\[
\norm*{\bfA\bfX - \bfA}_M,
\]

where here, the $M$-norm of an $n\times d$ matrix $\bfM$ is defined as

\[
\norm*{\bfM}_M = \parens*{\sum_{i=1}^n M(\norm*{\bfe_i^\top\bfM}_2)}^{1/p_M}
\]

or equivalently, the vector $M$-norm for the vector of $\ell_2$ row norms of $\bfM$. We also define the weighted version

\[
\norm*{\bfM}_{M,\bfw} = \parens*{\sum_{i=1}^n \bfw_i M(\norm*{\bfe_i^\top\bfM}_2)}^{1/p_M}
\]

We consider approximation algorithms to the above problem, so that we seek a rank $k$ $\bfX$ such that

\[
\norm*{\bfA\bfX - \bfA}_M \leq (1+\eps)\min_{\rank(\bfY) = k}\norm*{\bfA\bfY - \bfA}_M.
\]

For this problem, [21] obtained an algorithm with parameters depending on $K = (\log n)^{O(\log k)}$, running in time

\[
O\parens*{\nnz(\bfA)\log n + (n+d)\poly(K/\eps)}
\]

to reduce the problem to an instance of size $\poly(K/\eps)\times \poly(K/\eps)$. Furthermore, their algorithm makes use of an oblivious subspace embedding, which is only applicable to $M$-estimators with growth bounded by a quadratic, i.e., $p_M\leq 2$. By using our improved sensitivity bounds of Section <ref>, we match the guarantees of their robust subspace approximation and regression algorithms for $\ell_p$, up to $\poly(\log(n))$ factors, for any $p_M$. That is, we obtain the following improved theorem:

Let $\norm*{\cdot}_M$ be an $M$-norm. There is an algorithm which computes matrices $\bfT$, $\bfS$, and $\bfU$, and a set of weights $\bfw$ such that

\[
\min_{\rank(\bfY) = k}\norm*{\bfT\bfA\bfS^\top - (\bfT\bfA\bfU)\bfY(\bfU\bfS^\top)}_{M,\bfw} \leq (1+\eps)\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfY}_M.
\]

Furthermore, $\bfT$ and $\bfS$ only have $\poly(k(\log n)/\eps)$ rows and $\bfU$ only has $\poly(k(\log n)/\eps)$ columns, and the matrices $\bfT\bfA\bfS^\top$, $\bfT\bfA\bfU$, and $\bfU\bfS^\top$ can be formed in

\[
O\parens*{[\nnz(\bfA) + (n+d)\poly(k/\eps)]\poly(\log n)}
\]

We now briefly sketch out the changes, leaving many of the details to the [21] paper, as the algorithm and analysis is essentially identical to their algorithms for $\ell_p$ losses. The approach of [21], like many other coreset algorithms, begins with an initial crude relative error approximation, which is later refined down to $(1+\eps)$ relative error.

§.§ Crude Relative Error Approximation

In this section, we derive the analogues of the ConstApprox algorithm, which is Algorithm 4 and Theorem 47 of [21]. This computes a $\poly(k\log n)$-dimensional subspace, such that projection to this subspace is within a $\poly(k\log n)$ factor of optimal.

The first step is to reduce the number of columns of $\bfA$ via standard $\ell_2$ dimension reduction techniques, as formalized by the following theorem.

Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ be increasing and polynomially bounded with degree $p$ (Definition <ref>). Let $\bfR\in\mathbb R^{m\times d}$ be an  sparse embedding [51] with sparsity parameter $s$. Then, there is $s = O(p^3/\eps)$ and $m = O(k^2/\eps^{O(p)})$ such that with constant probability,

\[
\min_{\rank(\bfX) = k} \norm*{\bfA\bfR^\top\bfX - \bfA\bfR^\top}_M \leq (1+\eps)\min_{\rank(\bfY) = k}\norm*{\bfA\bfY - \bfA}_M.
\]

By applying the above theorem with $\eps$ set to a constant, we make work instead with $\bfA\bfR$, which only has $\poly(k)$ columns. We may then apply our improved sensitivity bounds to efficiently reduce the number of rows for a crude bicriteria guarantee.

input: Matrix $\bfA \in \mathbb R^{n \times d}$, rank parameter $k$

output: Projection $\bfU\bfU^\top$
[1]
Let $\bfR$ be a sparse embedding matrix from Theorem <ref>
Compute $M$-sensitivity upper bounds $\tilde\bfs_i^M(\bfA\bfR)$ by Theorem <ref> with $\tau = \poly(k)$
Let $r$ be sufficiently large in $\poly(k)$
Let $\bfw_i$ be $1/\bfp_i$ w.p. $\bfp_i$ and $0$ otherwise, for $\bfp_i \coloneqq \min\{1,r\cdot \tilde\bfs_i^M(\bfA\bfR)\}$
$\bfU\bfU^\top$, where $\bfU^\top$ is an orthonormal basis for the row space of

With constant probability, the matrix $\bfU$ output by Algorithm <ref> has

\[
\norm*{\bfA - \bfA\bfU\bfU^\top}_{M,\bfw} \leq \poly(k)\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfY}_M
\]

The running time is

\[
O\parens*{[\nnz(\bfA) + (n+d)\poly(k)]\poly\log (n)}
\]

with high probability.

The proof is nearly identical to the $\ell_p$ case of Theorem 47 of [21]. Instead of using their Lemma 39 to compute sensitivity upper bounds that sum to approximately $\poly(k)\sqrt n$, we use our Theorem <ref> to compute sensitivity upper bounds that sum to $\poly(k\log n)$. Then, we only require one round of sampling in order to reduce the number of rows to $\poly(k\log n)$, and thus results in guarantees analogous to their $\ell_p$ loss case, up to a $\poly\log(n)$ factor.

Note that [21] only achieve a much larger distortion of $\poly(k)^{O(\log\log n)} = (\log n)^{O(\log k)}$ rather than $\poly(k\log n)$, due to their recursive application of sensitivity sampling for a depth of $O(\log\log n)$, which each incurs a distortion of $\poly(k)$.

§.§ Refinement to (1+eps)-Approximations

Using the crude $\poly(k)$ approximation, the next step in the [21] algorithm is to adapt a result of [27] to obtain a $d\times \poly(k(\log n)/\eps)$ matrix $\bfU$ with orthonormal columns such that

\[
\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfU\bfY\bfU}_{M,\bfw} \leq (1+\eps)\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfY}_M.
\]

This is the DimReduce algorithm described as Algorithm 2 of [21] as well as Theorem 46.

Let $K>0$ and let $\hat\bfX\in\mathbb R^{d\times d}$ be a $m$-dimensional projection such that

\[
\norm*{\bfA(\bfI - \hat\bfX)}_{M,\bfw} \leq K\min_{\rank(\bfY) = k}\norm*{\bfA(\bfI - \bfY)}_{M}.
\]

Then, there is an algorithm that returns $\bfU\in\mathbb R^{d\times(m+K\poly(k/\eps))}$ such that

\[
\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfU\bfY\bfU}_{M,\bfw} \leq (1+\eps)\min_{\rank(\bfY) = k}\norm*{\bfA - \bfA\bfY}_M.
\]

This problem can then by sketched from the left by sparse embedding $\bfS$ with $\poly(k(\log n)/\eps)$ rows so that we are left with solving the problem

\[
\min_{\rank(\bfY) = k}\norm*{\bfA\bfS^\top - \bfA\bfU\bfY\bfU\bfS^\top}_{M,\bfw}.
\]

Finally, the last step is to conduct another row sampling process to reduce the number of rows $n$ to a $\poly(k(\log n)/\eps)$-sized instance. For this step, we again use our improved sensitivity sampling lemma as in Theorem <ref>. However, there is an additional challenge in this setting in that we cannot afford to compute the matrix $\bfA\bfU$ explicitly, since this requires $\nnz(\bfA)\poly(k(\log n)/\eps)$ time to compute. The solution to this problem described in [21] is to use an oblivious sparse $\ell_p$ subspace embedding $\bfPi$ and then to compute a QR decomposition of $\bfPi\bfA[\bfS^\top~\bfU] = \bfQ\bfR$ in order to obtain a well-conditioned basis $\bfU = \bfA[\bfS^\top~\bfU]\bfR^{-1}$. Then, the row norms of $\bfU$, which can be used as approximate sensitivity upper bounds, are estimated by multiplying by a Gaussian matrix $\bfG$ with $O(1)$ columns, so that $\bfU\bfG = \bfA([\bfS^\top~\bfU]\bfR^{-1}\bfG)$ can be computed efficiently in $O(\nnz(\bfA))$ time. However, this approach has a drawback, in that the use of an oblivious subspace embedding restricts the range of applicable growth upper bounds $p_M$ to at most $2$.

Instead, as observed in [59], we make use of the fact that Lewis weight computation can be done efficiently as long as matrix vector products can be computed efficiently, so that $\nnz(\bfA)$ dependencies can approximately be replaced by $T(\bfA)$ dependencies, where $T(\bfA)$ denotes the time required to compute a matrix vector product. Thus, for computing the Lewis weights of $\bfA[\bfS^\top~\bfU]$, we can approximately replace all $\nnz(\bfA)$ terms with $\nnz(\bfA) + \poly(k(\log n)/\eps)$, by multiplying the product one matrix at a time. This is implicit in the proof of Theorem 3 of [59].

Thus, following the Approx algorithm described as Algorithm 7 with their sensitivity bound replaced by our sensitivity bound of Theorem <ref>, we may find a set of weights $\bfw'$ such that

\[
\norm*{\bfA\bfS^\top - \bfA\bfU\bfY\bfU\bfS^\top}_{M,\bfw'} = (1\pm\eps)\norm*{\bfA\bfS^\top - \bfA\bfU\bfY\bfU\bfS^\top}_{M,\bfw}.
\]

for all $\bfY$ with $\rank(\bfY) = k$, with $\poly(k(\log n)/\eps)$ nonzero entries. After this step, all of the matrices involved are of size $\poly(k(\log n)/\eps) \times \poly(k(\log n)/\eps)$, as desired.

§ LOWER BOUNDS

We now present various lower bounds on active sampling for $\ell_p$ regression. Our first result obtains a nearly optimal lower bound of $\Omega(d/\eps^2)$ for $p\in(0,1)$, which matches our upper bound of Theorem <ref> up to logarithmic factors. Our lower bound is similar to Theorem 5.1 of [11], and is based on distinguishing biased coin flips. We also show that the same instance gives a lower bound $\Omega(d/\eps)$ in the range of $p\in(1,2)$, which is also tight with our upper bound in Theorem <ref>. For $d = 1$, we note that the active $\ell_p$ regression problem is equivalent to the $\ell_p$ power means problem. Thus, these results also improve upon a query complexity lower bound for this problem by [19], which shows a lower bound of $\Omega(\eps^{1-p})$ in one dimension. However, this lower bound is useful for us for $p > 2$, which shows that our Theorem <ref> is off by a factor of $\eps$ in the $\eps$ dependence.

Our next result shows that $\Omega(d^{\max(1,p/2)})$ samples are required to solve Problem <ref> for the $\ell_p$ norm for any $p \ge 1$ to a constant approximation factor.
This show that Algorithm <ref> is optimal in its dependence on $d$, up to
polylogarithmic factors (see Theorem <ref>).

Finally, our last lower bound concerns algorithms which solve the $\ell_p$-regression problem $\min_\bfx \|\bfA\bfx-\bfb\|_p$ up to a constant factor in a specific way. Namely, say an algorithm
is a sampling-and-reweighting algorithm if, given an $n \times d$ input matrix $\bfA$, the algorithm first reads $\bfA$ and then decides on a subset $S$ of $s$ entries of $\bfb$ to read in an arbitrary way. The algorithm also decides on a diagonal rescaling matrix $\bfD \in \R^{s \times s}$ – $\bfD$ may be arbitrary, except that we require that if two rows of $\bfA$ are identical and are both sampled in $S$, they are given the same weight in $\bfD$. We also assume that the number $s$ of samples is a function of $d, \epsilon,$ and the failure probability $\delta$, and is independent of $n$. These assumptions hold for all importance-based sampling methods for subspace preservation.

After deciding on $S$ and $\bfD$, the algorithm then reads
the entries in $\bfb$ indexed by the set $S$, denoted $\bfb_S$, and sets
$\bfx' = \textrm{argmin}_x \|\bfD \bfA_S\bfx - \bfD \bfb_S\|_p$, where $\bfA_S$
is the subset of rows of $\bfA$ corresponding to the entries in $\bfb_S$.

We show that any sampling-and-reweighting algorithm which
fails with probability at most $\delta$, necessarily takes $|S| = \Omega(1/\delta^{p-1})$ samples.
Moreover, this remains true even if $\|\bfb\|_p = O(1) \cdot \min_\bfx \|\bfA\bfx-\bfb\|_p$.

We stress that our main algorithms are not sampling-and-reweighting algorithms due to the success probability boosting steps of Section <ref> which ensure that $\|\bfb\|_p = O(1) \cdot \min_\bfx \|\bfA\bfx-\bfb\|_p$ and $\norm{\bfS\bfb}_p = O(\norm{\bfb}_p)$ with probability at least $1-\delta$. With these steps, our approach

achieves a $O(\log 1/\delta)$ dependence overall, an exponential improvement over what is possible by simple sampling-and-reweighting algorithms. We also remark that our lower bound becomes vacuous when $p = 1$, which is required – Chen and Dereziński [11] as well as Parulekar, Parulekar, and Price [53] achieve $O(\log(1/\delta))$ dependence with simple sampling-and-reweighting for $\ell_1$ regression.

§.§ Lower Bounds for p in (0, 1)

We first show an $\Omega(d/\eps^2)$ lower bound for $p\in(0,1)$, which is tight up to logarithmic factors. The idea is essentially the same as the lower bound of [11]. We use Yao's minimax principle to restrict our attention to deterministic algorithms which must succeed with high probability over a random distribution over input instances.

We first recall the result of [11], which provides a generic reduction from $d$-dimensional lower bounds to $1$-dimensional lower bounds via a padding argument. Although [11] prove a theorem online in the case of $\ell_1$, the following result is an easy generalization that is implicit from their proof:

Let $\mathcal D_0$ and $\mathcal D_1$ be two distributions over label vectors $\bfb\in\mathbb R^m$ such that distinguishing between $\bfb\sim\mathcal D_0$ and $\bfb\sim\mathcal D_1$ with probability at least $2/3$ requires at least $q$ queries to $\bfb$ in expectation, for any deterministic algorithm. Furthermore, suppose that there exists $\bfa\in\mathbb R^m$ such that, with probability at least $99/100$, $\mathcal D_0$ and $\mathcal D_1$ can be distinguished by $\tilde x\in\mathbb R$ such that

\[
\norm*{\bfa\tilde x-\bfb}_p^p \leq (1+\eps)\min_{x\in\mathbb R}\norm*{\bfa x-\bfb}_p^p.
\]

Finally, suppose that there exist $R>0$ and $c\geq1$ such that $\min_x\norm*{\bfa x-\bfb}_p^p \in [R, cR]$ with probability at least $99/100$ for $\bfb\sim\frac12(\mathcal D_0+\mathcal D_1)$. Then, there exists an $md\times d$ matrix $\bfA$ and a distribution $\mathcal D$ over label vectors $\bfb\in\mathbb R^{md}$ such that any deterministic algorithm which outputs $\tilde\bfx\in\mathbb R^d$ such that

\[
\Pr\braces*{\norm*{\bfA\tilde\bfx-\bfb}_p^p \leq \parens*{1+\frac{\eps}{200 c}}\min_{\bfx\in\mathbb R^d}\norm*{\bfA\bfx-\bfb}_p^p} \geq \frac{99}{100}
\]

must make at least $\Omega(dq)$ queries to $\bfb$ in expectation.

Thus, it suffices to show a $1$-dimensional lower bound which suits the hypotheses of Theorem <ref>. Our hard input distribution will be the same as that of <cit.>.

Let $0 < p < 1$ be a constant. Let $\eps>0$ be sufficiently small and let $n = 100\ceil*{\eps^{-2}}$. Let $\bfa\in\mathbb R^n$ be the all ones vector. Let $\mathcal D_0$ be the distribution over binary vectors $\bfb\in\{0,1\}^n$ which independently draws each coordinate as a Bernoulli with bias $1/2 + \eps$ and let $\mathcal D_1$ be the distribution which independently draws each coordinate as a Bernoulli with bias $1/2 - \eps$. Then, any $\tilde x$ such that

\[
\norm*{\bfa\tilde x-\bfb}_p^p \leq (1+\eps)\min_{x\in\mathbb R}\norm*{\bfa x-\bfb}_p^p
\]

distinguishes whether $\bfb\sim\mathcal D_0$ or $\bfb\sim\mathcal D_1$ with probability at least $99/100$.

Note that the optimal $x^*$ minimizing $\norm*{\bfa x-\bfb}_p^p$ over $x\in\mathbb R$ must lie in $[0, 1]$. Indeed, if $x < 0$, then $-x$ has a strictly lower cost than $x$, and if $x > 1$, then $x = 1$ has a strictly lower cost. Thus, the objective function can be written as

\begin{equation}\label{eq:lp-obj-p<1}
\norm*{\bfa x-\bfb}_p^p = (n-r)\cdot x^p + r\cdot (1-x)^p
\end{equation}

where $r$ is the number of ones in $\bfb$. As noted by [11], note that $r \in [(\frac12 + \frac\eps2)n, (\frac12 + \frac{3\eps}2)n]$ with probability at least $99/100$ if $\bfb\sim\mathcal D_0$, and similarly, $r \in [(\frac12 - \frac\eps2)n, (\frac12 - \frac{3\eps}2)n]$ with probability at least $99/100$ if $\bfb\sim\mathcal D_1$. Let this event be denoted as $\mathcal E$, and condition on this event. Write this as $r = n/2 + a\eps n$ for some $a\in[1/2, 3/2]$ if $\bfb\sim\mathcal D_0$ and $a\in[-3/2,-1/2]$ if $\bfb\sim\mathcal D_1$.

Optimal Solutions. We will first compute the optimal cost. Since $x\mapsto x^p$ for $p\in(0,1)$ is nonconvex, we have three candidate solutions for the optimum: the endpoints $x = 0$, $x = 1$, and the unique stationary point

\[
x = \frac1{1+(n/r-1)^{1/(p-1)}}
\]

of Equation (<ref>). It can easily be seen that the costs for $x = 0$ and $x = 1$ are $r$ and $n-r$, respectively. Now assume that $\bfb\sim\mathcal D_0$, since the other case follows symmetrically. Then,

\[
(n/r-1)^{1/(p-1)} = \bracks*{\frac{1}{1/2 + a\eps}-1}^{1/(p-1)} = \bracks*{\frac{1/2 + a\eps}{1/2 - a\eps}}^{1/(1-p)} = 1 + O(\eps)
\]

\[
x = \frac1{2 + O(\eps)} = \frac12 - O(\eps).
\]

The objective cost is thus

\begin{align*}
(n-r)\cdot x^p + r\cdot(1-x)^p &= \parens*{\frac12-a\eps}n\cdot\parens*{\frac12-O(\eps)}^p + \parens*{\frac12+a\eps}n\cdot\parens*{\frac12+O(\eps)}^p \\
&= \frac{n}{2^p}\bracks*{\parens*{\frac12-a\eps}(1-O(\eps))^p + \parens*{\frac12+a\eps}(1+O(\eps))^p} \\
&= \frac{n}{2^p}(1\pm O(\eps)).
\end{align*}

Since $p < 1$, this has cost worse than $r$ or $n-r$, so the optimal solution is $n-r$, conditioned on $\mathcal E$. Likewise, if $\bfb\sim\mathcal D_1$, then the optimal solution is $x = 0$ with cost $r$.

Suboptimal Solutions. We now show that, given a nearly optimal solution $\tilde x$, we can determine whether $\bfb$ is drawn from $\mathcal D_0$ or $\mathcal D_1$ with high probability by testing whether $\tilde x \in [1/2, 1]$ or $\tilde x \in [0, 1/2]$. Again, assume by symmetry that $\bfb\sim\mathcal D_0$. Suppose that $x \in [0, 1/2]$. If $x > 1/2 - O(\eps)$, then as calculated above, $x$ is not even an $\alpha$-factor solution for some constant $\alpha$. Otherwise, we have that

\[
x \leq \frac12 - O(\eps) = \frac1{1 + (n/r-1)^{1/(p-1)}}
\]

which rearranges to

\[
p\cdot (n-r)x^{p-1} - pr\cdot (1 - x)^{p-1} > 0
\]

which means that the objective is increasing on this interval. Thus, for $x\in[0,1/2]$, the smallest that the cost can be is $r$, which is a factor of $(1+\eps)$ larger than $n-r$. Thus, a $(1+\eps)$-factor approximation must distinguish between $\bfb$ drawn from $\mathcal D_0$ and $\mathcal D_1$.

As discussed in [11], the distributions of Theorem <ref> require at least $\Omega(\eps^{-2})$ queries to distinguish, by standard arguments. Then, by combining Theorems <ref> and <ref>, we arrive at the following:

Let $p\in (0,1)$ be a constant. Let $\bfA\in\mathbb R^{n\times d}$ and let $\bfb\in\mathbb R^n$. Suppose that with probability at least $99/100$, an algorithm $\mathcal A$ returns $\tilde\bfx\in\mathbb R^d$ such that

\[
\norm*{\bfA\tilde\bfx - \bfb}_p^p \leq (1+\eps)\min_{\bfx\in\mathbb R^d}\norm*{\bfA\bfx-\bfb}_p^p.
\]

Then, $\mathcal A$ queries $\Omega(d/\eps^2)$ entries of $\bfb$ in expectation.

§.§ Lower Bounds for p in (1, 2)

In the range of $p\in (1,2)$, we analyze the same lower bound instance as in Theorem <ref>. However, the nature of the objective function changes in this parameter regime, and our lower bound weakens to $\Omega(d/\eps)$. In particular, the value of the endpoints $x = 0$ and $x = 1$ stay at $r$ and $n-r$, but the value of the stationary point, which is near $x = 1/2$ and has a value of around $n/2^p$, becomes significantly better than the endpoint solutions. This causes a phase transition in the lower bound that we are able to achieve with this method.

We now present our $1$-dimensional lower bound of $\Omega(\eps^{-1})$ for $p\in(1,2)$. For easy reuse of our calculations from Theorem <ref>, we state this result as a lower bound of $\Omega(\eps^{-2})$ for any algorithm achieving an $O(\eps^2)$-approximation. This can be reparameterized to an $\Omega(\eps^{-1})$ lower bound for $O(\eps)$-approximations.

Let $1 < p < 2$ be a constant. Let $\eps>0$ be sufficiently small and let $n = 100\ceil*{\eps^{-2}}$. Let $\bfa\in\mathbb R^n$ be the all ones vector. Let $\mathcal D_0$ be the distribution over binary vectors $\bfb\in\{0,1\}^n$ which independently draws each coordinate as a Bernoulli with bias $1/2 + \eps$ and let $\mathcal D_1$ be the distribution which independently draws each coordinate as a Bernoulli with bias $1/2 - \eps$. Then, there exists a constant $c$ such that any $\tilde x$ such that

\[
\norm*{\bfa\tilde x-\bfb}_p^p \leq (1+c\cdot\eps^2)\min_{x\in\mathbb R}\norm*{\bfa x-\bfb}_p^p
\]

distinguishes whether $\bfb\sim\mathcal D_0$ or $\bfb\sim\mathcal D_1$ with probability at least $99/100$.

Many of our calculations from Theorem <ref> directly carry over. Recall our notation of setting $r$ to be the number of ones in $\bfb$, which is $r = n/2 + a\eps n$ for $a\in[1/2,3/2]$ if $\bfb\sim\mathcal D_0$ and $a\in[-3/2,-1/2]$ if $\bfb\sim\mathcal D_1$. Recall also that the unique stationary point, which is the optimum now by convexity, is

\[
x = \frac1{1+(n/r-1)^{1/(p-1)}}.
\]

Optimal Solutions.
We now calculate the value of the optimum. We carry out calculations for $\bfb\sim\mathcal D_0$ since $\bfb\sim\mathcal D_1$ gives symmetric results. Note first that

\begin{align*}
(n/r-1)^{1/(p-1)} &= \bracks*{\frac{1}{1/2 + a\eps}-1}^{1/(p-1)} = \bracks*{\frac{1 - 2a\eps}{1 + 2a\eps}}^{1/(p-1)} = \bracks*{(1 - 2a\eps)\cdot \sum_{i=0}^\infty (-2a\eps)^i}^{1/(p-1)} \\
&= \bracks*{(1 - 2a\eps) - (2a\eps)(1-2a\eps) + (2a\eps)^2(1-2a\eps) + O(\eps^3)}^{1/(p-1)} \\
&= \bracks*{1 - 4a\eps + 2(2a\eps)^2 + O(\eps^3)}^{1/(p-1)} \\
&= 1 - \frac{4a}{p-1}\eps + \frac{8a^2}{p-1} \eps^2 + O(\eps^3)
\end{align*}

\[
x = \frac12 \parens*{1 + \frac{2a}{p-1}\eps - \frac{4a^2}{p-1}\eps^2 + O(\eps^3)}.
\]

Then, the objective value at this $x$ is

\begin{align*}
&\frac{n}{2^p}\bracks*{\parens*{\frac12-a\eps}\parens*{1 + \frac{2a}{p-1}\eps - \frac{4a^2}{p-1}\eps^2 + O(\eps^3)}^p + \parens*{\frac12+a\eps}\parens*{1 - \frac{2a}{p-1}\eps + \frac{4a^2}{p-1}\eps^2 + O(\eps^3)}^p} \\
= ~&\frac{n}{2^p}\bracks*{\parens*{\frac12-a\eps}\parens*{1 + \frac{2pa}{p-1}\eps - \frac{4pa^2}{p-1}\eps^2 + O(\eps^3)} + \parens*{\frac12+a\eps}\parens*{1 - \frac{2pa}{p-1}\eps + \frac{4pa^2}{p-1}\eps^2 + O(\eps^3)}} \\
= ~&\frac{n}{2^p}\bracks*{1 + \parens*{\frac12-a\eps}\parens*{\frac{2pa}{p-1}\eps - \frac{4pa^2}{p-1}\eps^2 + O(\eps^3)} + \parens*{\frac12+a\eps}\parens*{- \frac{2pa}{p-1}\eps + \frac{4pa^2}{p-1}\eps^2 + O(\eps^3)}} \\
= ~&\frac{n}{2^p}\bracks*{1 - \frac{4pa^2}{p-1}\eps^2 + O(\eps^3)}.
\end{align*}

If $\bfb\sim\mathcal D_1$, then we have that

\[
x = \frac12 \parens*{1 - \frac{2a}{p-1}\eps + \frac{4a^2}{p-1}\eps^2 + O(\eps^3)}
\]

with the same objective value.

Suboptimal Solutions.
We now show that, given a nearly optimal solution $\tilde x$, we can determine whether $\bfb$ is drawn from $\mathcal D_0$ or $\mathcal D_1$ with high probability by testing whether $\tilde x \in [1/2, 1]$ or $\tilde x \in [0, 1/2]$. Again, assume by symmetry that $\bfb\sim\mathcal D_0$. Suppose that $x \in [0, 1/2]$. Then,

\[
x \leq \frac12 < \frac1{1 + (n/r-1)^{1/(p-1)}}
\]

which rearranges to

\[
p(n-r)\cdot x^{p-1} - pr\cdot (1 - x)^{p-1} < 0
\]

which means that the objective is decreasing on this interval. Thus, for $x\in[0,1/2]$, the smallest that the cost can be is $x = 1/2$, which gives a value of

\[
(n-r)\cdot (1/2)^p + r\cdot (1/2)^p = \frac{n}{2^p},
\]

which is a factor of $1 - \Theta(\eps^2)$ larger than the optimal solution. Thus, a $(1+\Theta(\eps^2))$-approximate solution can distinguish between $\mathcal D_0$ and $\mathcal D_1$.

Then, by combining Theorems <ref> and <ref>, we arrive at the following:

Let $p\in (1,2)$ be a constant. Let $\bfA\in\mathbb R^{n\times d}$ and let $\bfb\in\mathbb R^n$. Suppose that with probability at least $99/100$, an algorithm $\mathcal A$ returns $\tilde\bfx\in\mathbb R^d$ such that

\[
\norm*{\bfA\tilde\bfx - \bfb}_p^p \leq (1+\eps)\min_{\bfx\in\mathbb R^d}\norm*{\bfA\bfx-\bfb}_p^p.
\]

Then, $\mathcal A$ queries $\Omega(d/\eps)$ entries of $\bfb$ in expectation.

§.§ Lower Bounds for p > 2

In the range of $p>2$, a lower bound of $\Omega(\eps^{1-p})$ follows from Theorem 3 of [19], which shows that in the $1$-dimensional $\ell_p$ power mean problem, which is equivalent to $1$-dimensional active $\ell_p$ regression, $\Omega(\eps^{1-p})$ queries are necessary to obtain $(1+\eps)$-approximate solutions. This matches our $\eps$ dependence in the upper bound by at most $\eps$. For $d$ dependence, it is clear that solving Problem <ref> to any non-trivial relative error approximation factor for any norm requires at least $d$ samples, as otherwise, we would have non-zero error in the case that $\bfA\bfx = \bfb$. Here, we show that $\Omega(d^{p/2})$ samples are required to solve the problem for any $\ell_p$ norm with $p \ge 2$. In combination, this shows that the $\tilde O(d^{\max(1,p/2)})$ bound of Theorem <ref> is tight up to polylogarithmic factors.

We use the following standard fact from coding theory.

For any real $q \geq 1$ and $d = 2^k-1$ for some integer $k$, there exists a set
$\bfS \subset \{-1,1\}^d$ and a constant $C_q$ depending on $q$ which satisfy

* $|S| = d^q$

* For any $s, t \in S$ such that $s \neq t$, $|\langle s, t \rangle | \leq C_q \sqrt{d}$.

Using Lemma <ref> with $q = p/2$, we can find $r = d^{p/2}$ vectors $\bfx_1, \ldots,\bfx_r$
for which $\|x_i\|_2^2 = d$ and $|\langle\bfx_i,\bfx_j \rangle| \leq C \sqrt{d}$ for all $i \neq j$, for a constant $C > 0$. We work with a fixed subset of $s= C' \cdot d^{p/2}$ of these vectors, for
a sufficiently small constant $C' > 0$. Let these $s$ vectors form the rows $a_1,\ldots,a_s$ of $\bfA \in \R^{s \times d}$.
We choose a uniformly random index $I \in [s]$ and set $\bfb_I = d$, while we set
$\bfb_j = 0$ for all $j \neq I$. The claim is that any solution to the $\ell_p$-regression problem
can be used to predict the index $I$. However, by standard information-theoretic arguments,
any algorithm for predicting $I$ with constant
probability requires reading $\Omega(s) = \Omega(d^{p/2})$ entries of $\bfb$.

To see the claim, consider a $(1+\epsilon)$-approximate solution vector $\bfx$ to
$\min_\bfx \|\bfA\bfx-\bfb\|_p$, where $\epsilon > 0$ is less than a sufficiently small constant.
Suppose $| \langle a_j,\bfx \rangle| \geq d/2$ for some $j \neq I$.
Then the regression cost is at least $(d/2)^p$, since this is the cost on the $j$-th coordinate
alone. Alternatively, suppose $| \langle a_I,\bfx \rangle | \leq d/2$.
Then the regression cost is at least $(d/2)^p$, since this is the cost on the $I$-th coordinate
alone. On the other hand, consider the solution vector $\bfx' = a_I$.
Then the regression cost is at most
$(s-1) \cdot (C \sqrt{d})^{p} \leq d^p \cdot C^{p} \cdot C'.$
Since $C' > 0$ can be made an arbitrarily small constant (while suffering a constant factor
in the lower bound on the number of entries of $\bfb$ read),
the regression cost is a constant factor smaller than $(d/2)^p$.

Hence, any $(1+\epsilon)$-approximate solution vector $\bfx$, for $\epsilon > 0$ less
than a small enough constant, must be such that $|\langle a_I,\bfx \rangle | \geq d/2$ and
$|\langle a_j,\bfx \rangle | < d/2$ for all $j \neq I$. Thus,
from the solution vector $\bfx$, one can determine the value of $I$. We thus have:

Let $p \geq 2$ and $\epsilon > 0$ be less than a sufficiently small constant. Any algorithm which outputs
a $(1+\epsilon)$-approximate solution $\bfx$ to the $\ell_p$-regression problem $\min_{\bfx\in\R^d} \|\bfA\bfx-\bfb\|_p^p$
with constant probability requires reading $\Omega(d^{p/2})$ entries of $\bfb$.

Lemma <ref> has been used to obtain lower bounds for the stronger subspace
sketch problem [47], which is related, though does not immediately give a lower bound for regression.

§.§ A 1/delta**p-1 Lower Bound for Sampling-and-Reweighting Algorithms

We next show that sampling-and-reweighting algorithms for $\ell_p$ regression must pay a polynomial dependence in the failure probability $\delta$, contrasting with the logarithmic dependence achieved by our approach.

Let $p > 1$. Any sampling-and-reweighting algorithm which, with probability at least $1-\delta$,
outputs a $(1+\epsilon)$-approximate solution $\bfx$
to the $\ell_p$-regression problem, for $\epsilon > 0$ less than a sufficiently small constant,
requires reading $\Omega(1/\delta^{p-1})$ entries of $\bfb$.

In our hard instance we will have $d = 1$ and require a sufficiently fine constant factor approximation
with failure probability $\delta$. Suppose, with these parameters, that there is an algorithm reading
$s$ entries. We set $n = s/\delta$, and will show that the algorithm cannot output
a constant factor approximation to the $\ell_p$-regression problem with probability at least

Let $\bfA$ be a single column of $n$ $1$s. Since the entries of $\bfA$ are indistinguishable from each other, we can assume without loss of generality that the sampling-and-reweighting algorithm samples entries uniformly at random. By assumption, since the rows of $\bfA$ are all identical, the algorithm reweights the sampled rows uniformly (equivalently assigns weight $1$ to each sampled entry). We choose $\bfb = \bfe_I$ for a random standard basis vector $\bfe_I$.

For the optimal $x$, necessarily $0 \leq x \leq 1$ since if $x < 0$, replacing $x$ with $-x $
would give lower cost. Similarly, if $x > 1$, then replacing $x$ with $1$ would give lower cost.
Then the cost is $(1-x )^p + (n - 1)x^p$. This is convex and differentiable for $p > 1$, and is minimized when
the derivative is $0$. Differentiating, the optimal $x$ satisfies
$-p(1-x )^{p-1} + p (n-1)x^{p-1} = 0$, or
$(1-x )^{p-1} = (n - 1)x^{p-1}$. Taking $(p-1)$-th roots,
$1-x = (n - 1)^{1/(p-1)}x$, or $x = 1/(1 + (n-1)^{1/(p-1)})$. The optimal cost is therefore

$$\left (1-\frac{1}{1 + (n - 1)^{1/(p-1)}} \right )^p + \frac{n-1}{(1 + (n-1)^{1/(p-1)})^p}.$$

For $n = \omega(1)$, this is
$\Theta(1 + n^{1-p/(p-1)}) = O(1)$ for any constant $p > 1$.

On the other hand, given that $n = s/\delta$, with probability at least $\delta$, the algorithm's sample includes $\bfb_I$.
If this is the case, for the sampled problem, the cost is
$(1-x )^{p-1} + (s - 1)x^p$ for a given $x$. Setting the derivative to $0$,
we now have that the optimal $x'$ for the sampled problem is:
$x' = \frac{1}{1 + (s-1)^{1/(p-1)}}$.
Computing the cost of using $x'$ for the original problem, our cost of using $x'$ is

$$\left (1-\frac{1}{(1 + (s - 1)^{1/(p-1)})^p} \right ) + \frac{(n-1)}{\left (1 + (s-1)^{1/(p-1)} \right )^p}.$$

The cost is at least the second term, which for $n = \omega(1)$ and $s = \delta n = \omega(1)$ is
$\Theta((s/\delta) / s^{p/(p-1)})$. This term must be $O(1)$ to be an
$O(1)$-approximation, by our above calculation of the optimal cost. Hence,
$s^{p/(p-1) - 1} = \Omega(1/\delta)$, or $s^{1/(p-1)} = \Omega(1/\delta)$, or
$s = \Omega(1/\delta^{p-1})$.

§ ACKNOWLEDGEMENTS

Cameron Musco's work on this project was supported in part by NSF Grants 2046235 and 1763618, along with an Adobe Research Grant. Christopher Musco was supported by NSF Grant 2045590. David P. Woodruff and Taisuke Yasuda were supported by ONR grant N00014-18-1-2562 and a Simons Investigator Award. Taisuke Yasuda thanks Cody Johnson and Yi Li for helpful discussions. We thank anonymous reviewers for comments which helped improve the presentation of the paper.

[1]
Deeksha Adil, Brian Bullins, Rasmus Kyng, and Sushant Sachdeva.
Almost-linear-time weighted $\ell_p$-norm solvers in slightly dense
graphs via sparsification.
In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming,
ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference),
volume 198 of LIPIcs, pages 9:1–9:15. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2021.

[2]
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya
Velingker, and Amir Zandieh.
A universal sampling method for reconstructing signals with simple
fourier transforms.
In 2019, 2019.

[3]
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva.
Iterative refinement for $\ell_p$-norm regression.
In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego,
California, USA, January 6-9, 2019, pages 1405–1424. SIAM, 2019.

[4]
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong.
Subspace embedding and linear regression with Orlicz norm.
In 2018, 2018.

[5]
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li.
An homotopy method for l\({}_{\mbox{p}}\) regression provably beyond
self-concordance and in input-sparsity time.
In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors,
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages
1130–1137. ACM, 2018.

[6]
Jean Bourgain, Joram Lindenstrauss, and Vitali Milman.
Approximation of zonoids by zonotopes.
Acta Mathematica, 162(1):73–141, 1989.

[7]
Aharon Ben-Tal, Tamar Margalit, and Arkadi Nemirovski.
The ordered subsets mirror descent optimization method with
applications to tomography.
SIAM J. Optim., 12(1):79–108, 2001.

[8]
Vladimir Braverman and Rafail Ostrovsky.
Zero-one frequency laws.
In Leonard J. Schulman, editor, Proceedings of the 42nd ACM
Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA,
5-8 June 2010, pages 281–290. ACM, 2010.

[9]
Markus Baldauf and JMC Santos Silva.
On the use of robust regression in econometrics.
Economics Letters, 114(1):124–127, 2012.

[10]
Joshua Batson, Daniel A. Spielman, and Nikhil Srivastava.
Twice-Ramanujan sparsifiers.
SIAM Journal on Computing, 41(6):1704–1721, 2012.

[11]
Xue Chen and Michał Dereziński.
Query complexity of least absolute deviation regression via robust
uniform convergence.
In 2021, 2021.

[12]
Albert Cohen, Mark A. Davenport, and Dany Leviatan.
On the stability and accuracy of least squares approximations.
Foundations of Computational Mathematics, 13(5):819–834, 2013.

[13]
Kamalika Chaudhuri, Sham M. Kakade, Praneeth Netrapalli, and Sujay Sanghavi.
Convergence rates of active learning for maximum likelihood
In 2015, 2015.

[14]
Xue Chen, Daniel M. Kane, Eric Price, and Zhao Song.
Fourier-sparse interpolation without a frequency gap.
In 2016, pages 741–750, 2016.

[15]
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng,
and Aaron Sidford.
Uniform sampling for matrix approximation.
In 2015, pages 181–190, 2015.

[16]
Albert Cohen and Giovanni Migliorati.
Optimal weighted least-squares methods.
SMAI Journal of Computational Mathematics, 3:181–203, 2017.

[17]
Michael B Cohen and Richard Peng.
$l_p$ row sampling by Lewis weights.
In 2015, pages 183–192, 2015.

[18]
Xue Chen and Eric Price.
Active regression via linear-sample sparsification active regression
via linear-sample sparsification.
In 2019, 2019.

[19]
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.
Improved coresets and sublinear algorithms for power means in
euclidean spaces.
In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan,
editors, Advances in Neural Information Processing Systems, 2021.

[20]
Kenneth L. Clarkson and David P. Woodruff.
Numerical linear algebra in the streaming model.
In Proceedings of the 41st Annual ACM Symposium on Theory of
Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages
205–214, 2009.

[21]
Kenneth L. Clarkson and David P. Woodruff.
Input sparsity and hardness for robust subspace approximation.
In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on
Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20
October, 2015, pages 310–329. IEEE Computer Society, 2015.

[22]
Kenneth L. Clarkson and David P. Woodruff.
Sketching for M-estimators: A unified approach to robust
In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA,
January 4-6, 2015, pages 921–939. SIAM, 2015.

[23]
Kenneth Clarkson, Ruosong Wang, and David Woodruff.
Dimensionality reduction for Tukey regression.
In 2019, pages 1262–1271. PMLR, 2019.

[24]
Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W
Sampling algorithms and coresets for $\ell_p$ regression.
SIAM Journal on Computing, 38(5):2060–2078, 2009.

[25]
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David P. Woodruff.
Optimal sketching for kronecker product regression and low rank
In Advances in Neural Information Processing Systems 32: Annual
Conference on Neural Information Processing Systems 2019, NeurIPS 2019,
December 8-14, 2019, Vancouver, BC, Canada, pages 4739–4750, 2019.

[26]
Huaian Diao, Zhao Song, Wen Sun, and David P. Woodruff.
Sketching for kronecker product regression and p-splines.
In International Conference on Artificial Intelligence and
Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary
Islands, Spain, pages 1299–1308, 2018.

[27]
Amit Deshpande and Kasturi R. Varadarajan.
Sampling-based dimension reduction for subspace approximation.
In David S. Johnson and Uriel Feige, editors, Proceedings of the
39th Annual ACM Symposium on Theory of Computing, San Diego, California,
USA, June 11-13, 2007, pages 641–650. ACM, 2007.

[28]
Michal Derezinski, Manfred K. K Warmuth, and Daniel J Hsu.
Leveraged volume sampling for linear regression.
In 2018, 2018.

[29]
Tamás Erdélyi, Cameron Musco, and Christopher Musco.
Fourier sparse leverage scores and approximate kernel learning.
2020, 2020.

[30]
Dan Feldman and Michael Langberg.
A unified framework for approximating and clustering data.
In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of
the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA,
USA, 6-8 June 2011, pages 569–578. ACM, 2011.

[31]
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford.
Computing Lewis weights to high precision.
2110.15563, 2021.

[32]
John Fox.
Robust Regression: Appendix to an R and S-PLUS Companion to Applied
Regression, 2002.

[33]
Dan Feldman and Leonard J. Schulman.
Data reduction for weighted and outlier-resistant clustering.
In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual
ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan,
January 17-19, 2012, pages 1343–1354. SIAM, 2012.

[34]
Mehrdad Ghadiri, Richard Peng, and Santosh S Vempala.
Faster $p$-norm regression using sparsity.
arXiv preprint arXiv:2109.11537, 2021.

[35]
Antoine Guitton and William W Symes.
Robust and stable velocity analysis using the huber function.
In SEG Technical Program Expanded Abstracts 1999, pages
1166–1169. Society of Exploration Geophysicists, 1999.

[36]
Gene H. Golxub and Charles F. Van Loan.
Matrix computations.
Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins
University Press, Baltimore, MD, 2013.

[37]
Jerrad Hampton and Alireza Doostan.
Coherence motivated sampling and convergence analysis of least
squares polynomial chaos regression.
Computer Methods in Applied Mechanics and Engineering,
290:73–97, 2015.

[38]
Godfrey H. Hardy, John Edensor Littlewood, and George Pólya.
Cambridge mathematical library. Cambridge Univ. Press, Cambridge,

[39]
Peter J Huber.
Robust estimation of a location parameter.
In Breakthroughs in statistics, pages 492–518. Springer, 1992.

[40]
William B. Johnson and Gideon Schechtman.
Finite dimensional subspaces of $L_p$.
In Handbook of the geometry of Banach spaces, Vol. I,
pages 837–870. North-Holland, Amsterdam, 2001.

[41]
Jack Kiefer and Jacob Wolfowitz.
Optimum designs in regression problems.
Annals of Mathematical Statistics, 30(2):271–294, 1959.

[42]
D Lewis.
Finite dimensional subspaces of ${L}_p$.
Studia Mathematica, 63(2):207–212, 1978.

[43]
Po-Ling Loh.
Statistical consistency and asymptotic normality for high-dimensional
robust $M$-estimators.
Ann. Statist., 45(2):866–896, 2017.

[44]
Po-Ling Loh.
Scale calibration for high-dimensional robust regression.
CoRR, abs/1811.02096, 2018.

[45]
Yin Tat Lee and He Sun.
Constructing linear-sized spectral sparsification in almost-linear
SIAM Journal on Computing, 47(6):2315–2336, 2018.

[46]
Michel Ledoux and Michel Talagrand.
Probability in Banach spaces.
Classics in Mathematics. Springer-Verlag, Berlin, 1991.

[47]
Yi Li, Ruosong Wang, and David P. Woodruff.
Tight bounds for the subspace sketch problem with applications.
In Proceedings of the 2020 ACM-SIAM Symposium on Discrete
Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages
1655–1674, 2020.

[48]
Olvi L. Mangasarian and David R. Musicant.
Robust linear and support vector regression.
IEEE Trans. Pattern Anal. Mach. Intell., 22(9):950–955,

[49]
Tung Mai, Cameron Musco, and Anup B. Rao.
Coresets for classification – simplified and strengthened.
2106.04254, 2021.

[50]
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P
On coresets for logistic regression.
2018, 2018.

[51]
Jelani Nelson and Huy L. Nguyen.
OSNAP: faster numerical linear algebra algorithms via sparser
subspace embeddings.
In 54th Annual IEEE Symposium on Foundations of Computer
Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages
117–126. IEEE Computer Society, 2013.

[52]
Dmitry Panchenko.
Symmetrization approach to concentration inequalities for empirical
Ann. Probab., 31(4):2068–2081, 2003.

[53]
Aditya Parulekar, Advait Parulekar, and Eric Price.
$l_1$ regression with Lewis weights subsampling.
2105.09433, 2021.

[54]
Udaya Parampalli, Xiaohu Tang, and Serdar Boztas.
On the construction of binary sequence families with low correlation
and large sizes.
IEEE transactions on information theory, 59(2):1082–1089,

[55]
Friedrich Pukelsheim.
Optimal Design of Experiments.
Society for Industrial and Applied Mathematics, 2006.

[56]
Tamas Sarlos.
Improved approximation algorithms for large matrices via random
In 2006, pages 143–152, 2006.

[57]
Gideon Schechtman.
More on embedding subspaces of $L_p$ in $l^n_r$.
Compositio Math., 61(2):159–169, 1987.

[58]
Christian Sohler and David P. Woodruff.
Subspace embeddings for the l1-norm with applications.
In 2011, pages 755–764, 2011.

[59]
Xiaofei Shi and David P. Woodruff.
Sublinear time numerical linear algebra for structured matrices.
In The Thirty-Third AAAI Conference on Artificial
Intelligence, AAAI 2019, The Thirty-First Innovative Applications of
Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium
on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu,
Hawaii, USA, January 27 - February 1, 2019, pages 4918–4925. AAAI Press,

[60]
Jerome Sacks, William J. Welch, Toby J. Mitchell, and Henry P. Wynn.
Design and analysis of computer experiments.
Statistical Science, 4(4):409–423, 1989.

[61]
Zhao Song, Ruosong Wang, Lin F. Yang, Hongyang Zhang, and Peilin Zhong.
Efficient symmetric norm regression via linear sketching.
In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence
d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances
in Neural Information Processing Systems 32: Annual Conference on Neural
Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019,
Vancouver, BC, Canada, pages 828–838, 2019.

[62]
Zhao Song, David P. Woodruff, and Peilin Zhong.
Towards a zero-one law for column subset selection.
In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence
d'Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances
in Neural Information Processing Systems 32: Annual Conference on Neural
Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019,
Vancouver, BC, Canada, pages 6120–6131, 2019.

[63]
Gideon Schechtman and Artem Zvavitch.
Embedding subspaces of ${L}_p$ into $\ell_p^n$, $0< p< 1$.
Mathematische Nachrichten, 227(1):133–142, 2001.

[64]
Michel Talagrand.
Embedding subspaces of $L_1$ into $l^N_1$.
Proc. Amer. Math. Soc., 108(2):363–369, 1990.

[65]
Michel Talagrand.
Embedding subspaces of $L_p$ in $l^N_p$.
In Geometric aspects of functional analysis (Israel,
1992–1994), volume 77 of Oper. Theory Adv. Appl., pages 311–325.
Birkhäuser, Basel, 1995.

[66]
Murad Tukan, Alaa Maalouf, and Dan Feldman.
Coresets for near-convex functions.
In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell,
Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in
Neural Information Processing Systems 33: Annual Conference on Neural
Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020,
virtual, 2020.

[67]
Roman Vershynin.
High-dimensional probability, volume 47 of Cambridge
Series in Statistical and Probabilistic Mathematics.
Cambridge University Press, Cambridge, 2018.

[68]
Charles F Van Loan.
Computational frameworks for the fast Fourier transform,
volume 10 of Frontiers in Applied Mathematics.
Society for Industrial and Applied Mathematics (SIAM), Philadelphia,
PA, 1992.

[69]
Charles F Van Loan and N. Pitsianis.
Approximation with Kronecker products.
In Linear algebra for large scale and real-time applications
(Leuven, 1992), volume 232 of NATO Adv. Sci. Inst. Ser. E Appl.
Sci., pages 293–314. Kluwer Acad. Publ., Dordrecht, 1993.

[70]
Alastair J Walker.
New fast method for generating discrete random numbers with arbitrary
frequency distributions.
Electronics Letters, 10(8):127–128, 1974.

[71]
Alastair J Walker.
An efficient method for generating discrete random variables with
general distributions.
ACM Transactions on Mathematical Software (TOMS),
3(3):253–256, 1977.

[72]
P. Wojtaszczyk.
Banach spaces for analysts, volume 25 of Cambridge Studies
in Advanced Mathematics.
Cambridge University Press, Cambridge, 1991.

[73]
David P. Woodruff.
Sketching as a tool for numerical linear algebra.
Foundations and Trends in Theoretical Computer Science,
10(1–2):1–157, 2014.

[74]
A. Zvavitch.
More on embedding subspaces of $L_p$ into $l^N_p$, $0<p<1$.
In Geometric aspects of functional analysis, volume 1745 of
Lecture Notes in Math., pages 269–280. Springer, Berlin, 2000.

§ MISSING PROOFS FOR SECTION <REF>

§.§ Proof of Lemma <ref>

We will need the following short lemma.

Let $\bfy\in\mathbb R^n$, $q>0$, $p \geq q$, and $\gamma>0$. Suppose that $\norm*{\bfy}_\infty \leq \gamma^{1/q}\norm*{\bfy}_q$. Then,

\[
\norm*{\bfy}_p^p \leq \frac1\gamma\parens*{\gamma^{1/q}\norm*{\bfy}_1}^p.\qedhere
\]

We have

\begin{align*}
\norm*{\bfy}_p^p &= \sum_{i=1}^n \abs*{\bfy_i}^p \leq \sum_{i=1}^n \norm*{\bfy}_\infty^{p-q} \abs*{\bfy_i}^{q} = \norm*{\bfy}_\infty^{p-q}\norm*{\bfy}_q^q  \\
&\leq \gamma^{(p-q)/q}\norm*{\bfy}_q^{p-q}\norm*{\bfy}_q^q  \leq \gamma^{p/q-1}\norm*{\bfy}_q^p = \frac1\gamma (\gamma^{1/q}\norm*{\bfy}_q)^p.
\end{align*}

We now proceed to the main proof of this section.

If $\norm*{\bfy}_M^2 \geq 2n$, then $\norm*{\bfy}_H^2 = \Theta(\norm*{\bfy}_q^q)$, since the Huber mass of the entries at most $1$ is at most $n$ over the $n$ entries. Furthermore, if $\norm*{\bfy}_\infty \leq 1$, then $\norm*{\bfy}_M^2 = \norm*{\bfy}_2^2$. Thus, in what follows, we assume that $\norm*{\bfy}_M^2 < 2n$ and $\norm*{\bfy}_\infty > 1$. Note then that $\norm{\bfy}_q^q \leq \norm*{\bfy}_M^2 + n < 3n$.

Reduction to $\norm*{\bfy}_\infty \leq \gamma\norm*{\bfy}_M^2$.

Suppose that $\norm*{\bfy}_M^2 > 2\norm*{\bfy\mid_T}_M^2$. Then, at least a $1/2$ fraction of the squared Huber norm mass is located in coordinates of size at least $\gamma\norm*{\bfy}_M^2$. If $\gamma\norm*{\bfy}_M^2 \geq 1$, then we have that $\norm*{\bfy}_M^2 = \Theta(\norm*{\bfy}_q^q)$, since over $1/2$ fraction of the mass is in the $\ell_q$ part. Otherwise, we have that $\gamma \norm*{\bfy}_M^2 \leq 1$ so $\norm*{\bfy}_\infty^q \leq \norm*{\bfy}_M^2 \leq 1/\gamma$. Then, letting $S = \braces*{i\in[n] : \abs*{\bfy_i} \leq 1}$,

\begin{align*}
\norm*{\bfy}_2^2 &= \norm*{\bfy\mid_S}_2^2 + \norm*{\bfy\mid_{\overline S}}_2^2 \\
&\leq \norm*{\bfy\mid_S}_2^2 + \norm*{\bfy}_\infty^{2-q} \norm*{\bfy\mid_{\overline S}}_q^q \\
&\leq \norm*{\bfy}_\infty^{2-q} \norm*{\bfy}_M^2 \\
&\leq \frac1{\gamma^{(2-q)/q}} \norm*{\bfy}_M^2.
\end{align*}

Thus, in either case, we have the conclusion that

\[
\norm*{\bfy}_M^2 \geq c\gamma^{2/q-1}\min_{p\in\{1,2\}}\norm*{\bfy}_p^p.
\]

We thus assume that $\norm*{\bfy}_M^2 \leq  2\norm*{\bfy\mid_T}_M^2$ in what follows. Furthermore, by restricting our attention to the set $T$, we assume that we have a vector $\bfy$ such that $\norm*{\bfy}_\infty \leq \gamma\norm*{\bfy}_M^2$ and work on showing that

\[
\norm*{\bfy}_M^2 \geq c\frac1{(\gamma n)^{\beta}}\min_{p\in[1,2]}\norm*{\bfy}_p^p
\]

for such a vector, where $\beta$ is as stated in the statement of the lemma.

Reduction to Spiked Vectors.

Let $S = \braces*{i\in[n] : \abs*{\bfy_i} \leq 1}$. Note that if $S = [n]$, then $\norm*{\bfy}_M^2  = \norm*{\bfy}_2^2$ so we may assume that $S \subsetneq [n]$. Similarly, if $S = \varnothing$, then $\norm*{\bfy}_M^2  = \Theta(\norm*{\bfy}_q^q)$ so we may assume that $S \neq \varnothing$.

Furthermore, we will assume that $\norm*{\bfy\mid_S}_q^q = \Theta(\norm*{\bfy\mid_{S}}_2^2)$. This is without loss of generality, because $\norm*{\bfy\mid_{\overline S}}_q^q \leq 3n$ and $\norm*{\bfy\mid_{S}}_2^2$ can be as large as $n$, so we can always increase the smaller of $\norm*{\bfy\mid_{\overline S}}_q^q$ and $\norm*{\bfy\mid_{S}}_2^2$ to match the other, which only increases $\norm*{\bfy}_M^2$ by a constant factor. However, this can only increase $\norm*{\bfy}_p^p$ for any $p$, so restricting to such vectors can only affect the claimed inequalities by a constant factor.

Now consider the vector $\bfz$, defined as follows:

\[
\bfz_i = \begin{cases}
\frac{1}{\sqrt{n}}\norm*{\bfy}_M & \text{if $i\in[n-1/\gamma]$} \\
(\gamma\norm*{\bfy}_M^2)^{1/q} & \text{if $i \in [1/\gamma] + n-1/\gamma$}
\end{cases}
\]

\[
\norm*{\bfz}_M^2 = \frac1\gamma \cdot [(\gamma \norm*{\bfy}_M^2)^{1/q}]^q + (n-1/\gamma) \cdot \parens*{\frac{\norm*{\bfy}_M}{\sqrt n}}^2 = \Theta(\norm*{\bfy}_M^2)
\]

and for any $p\in[1,2]$, we have that

\begin{align*}
\norm*{\bfy}_p^p &= \norm*{\bfy\mid_{\overline S}}_p^p + \norm*{\bfy\mid_{S}}_p^p \\
&\leq O(1)\frac1\gamma \cdot (\gamma \norm*{\bfy\mid_{\overline S}}_q^q)^{p/q} + (n^{1/p - 1/2}\norm*{\bfy\mid_{S}}_2)^p && \text{Lemma \ref{lem:lp-convexity}} \\
&\leq O(1)\frac1\gamma \cdot (\gamma \norm*{\bfy}_M^2)^{p/q} + n\cdot \parens*{\frac{\norm*{\bfy}_M}{\sqrt n}}^p \\
&= O(\norm*{\bfz}_p^p)
\end{align*}

Thus, by similar reasoning as before, it suffices to consider vectors of the form of $\bfz$. These vectors can be parameterized by a single number $r\in[0,1]$ by setting $\norm*{\bfy}_M = n^r$, so that the first $[n-1/\gamma]$ coordinates are $n^{r - 1/2}$ and the last $1/\gamma$ coordinates are $\gamma n^{2r}$. Thus,

\begin{align*}
\sup_{\bfy\in\mathbb R^n, \norm*{\bfy}_\infty \leq \gamma\norm*{\bfy}_M^2 }\frac{\min_{p\in[1,2]}\norm*{\bfy}_p^p}{\norm*{\bfy}_M^2} &= \Theta(1)\sup_{r\in[0,1]}\min_{p\in[q,2]}\frac{(1/\gamma)(\gamma n^{2r})^{p/q} + n\cdot n^{p(r - 1/2)}}{n^{2r}} \\
&= \Theta(1) \sup_{r\in[0,1]} \min_{p\in[q,2]}\max\braces*{n^{\alpha + (2r-\alpha)p/q - 2r}, n^{1 + p(r - 1/2) - 2r}}.
\end{align*}

To find the above minimum, we wish to choose the $p$ such that the two exponents are equal, so we solve for

\[
\alpha + (2r-\alpha)p/q - 2r = 1 + p(r - 1/2) - 2r,
\]

which gives

\[
p = \frac{2(1 - \alpha)}{(2r-\alpha)(2/q) + (1-2r)} = \frac{2(1 - \alpha)}{(1-\alpha)(2/q) - (1-2r)(2/q-1)}
\]

Plugging this back into the exponent gives

\[
1 + p(r-1/2) - 2r = (1-2r) - \frac{p}{2}(1-2r) = (1-2r) - \frac{(1-\alpha)(1-2r)}{(1-\alpha)(2/q) - (1-2r)(2/q-1)}.
\]

We now wish to optimize this exponent over $r\in[0,1]$. Writing $x = 1-2r$, $a = 2/q > 1$, and $c = 1-\alpha$, this the objective is

\begin{align*}
x - \frac{cx}{ca-(a-1)x} &= \frac{1}{a-1} \bracks*{(a-1)x - c\cdot\frac{(a-1)x}{ca-(a-1)x}} \\
&= \frac{1}{a-1} \bracks*{ca - \parens*{[ca - (a-1)x] + c\cdot\frac{(a-1)x}{ca-(a-1)x}}} \\
&= \frac{1}{a-1} \bracks*{c(a+1) - \parens*{[ca - (a-1)x] + c\cdot\frac{ca}{ca-(a-1)x}}} \\
&= \frac{1}{a-1} \bracks*{c(a+1) - 2c\sqrt a} && \text{AM-GM} \\
&= c\frac{1}{a-1} \bracks*{(a+1) - 2\sqrt a} \\
&= c\beta
\end{align*}

as long as $ca - (a-1)x\geq 0$, which we have for $\alpha\leq 1/a = q/2$. Note that equality holds when $x = c(a-\sqrt a)/(a-1)$. We thus have that

\[
\sup_{\bfy\in\mathbb R^n, \norm*{\bfy}_\infty \leq \gamma\norm*{\bfy}_H^2 }\frac{\min_{p\in[1,2]}\norm*{\bfy}_p^p}{\norm*{\bfy}_H^2} = \Theta(n^{(1-\alpha)\beta}) = \Theta((\gamma n)^{\beta})
\]

§ MISSING PROOFS FOR SECTION <REF>

§.§ Properties of Lewis Bases

Let $\bfA\in\mathbb R^{n\times d}$ and $0<p<\infty$. There exists a basis matrix $\bfU\in\mathbb R^{n\times d}$ of the column space of $\bfA$, known as the $\ell_p$ Lewis basis, such that if $\bfD$ is the diagonal matrix with $\bfD_{i,i} = \norm*{\bfe_i^\top\bfU}_2$, then $\bfD^{p/2 - 1}\bfU$ is an orthonormal matrix.

The fact that $\bfD^{p/2 - 1}\bfU$ is orthonormal from Theorem <ref> implies the following bound, which is stated in III.B Proposition 7 of [72] for $1 < p < \infty$, but requires a short proof for $0 < p < 1$.

Let $\bfA\in\mathbb R^{n\times d}$ and $0<p<\infty$. Let $\bfU$ be as defined in Theorem <ref>. Then,

\[
\sum_{i=1}^n \norm*{\bfe_i^\top \bfU}_2^{p} = d.
\]

Let $\bfD$ be as defined in Theorem <ref>. Note that

\begin{align*}
d &= \norm*{\bfD^{p/2 - 1}\bfU}_F^2  && \text{Frobenius norm of orthonormal matrices} \\
&= \sum_{i=1}^n \norm*{\bfe_i^\top \bfD^{p/2-1}\bfU}_2^2 \\
&= \sum_{i=1}^n \norm*{\bfe_i^\top \bfU}_2^{p-2} \norm*{\bfe_i^\top \bfU}_2^2 \\
&= \sum_{i=1}^n \norm*{\bfe_i^\top \bfU}_2^{p}.\qedhere
\end{align*}

We then have the following fact is crucial for obtaining sensitivity bounds using Lewis weights.

Let $\bfA\in\mathbb R^{n\times d}$ and $0<p<\infty$. Let $\bfD$ and $\bfU$ be as defined in Theorem <ref>. Then for all $\bfx\in\mathbb R^d$, the following inequalities hold:

* if $0 < p < 2$, then

\[
\norm*{\bfx}_2 \leq \norm*{\bfU\bfx}_p \leq d^{1/p - 1/2}\norm*{\bfx}_2
\]

* if $2\leq p < \infty$, then

\[
\norm*{\bfU\bfx}_p \leq \norm*{\bfx}_2 \leq d^{1/2 - 1/p}\norm*{\bfU\bfx}_p.
\]

For $p\geq 2$, the result is recorded in III.B Lemma 8 of [72]. For $0 < p < 2$, the computation exactly follows III.B Lemma 8 of [72] for $1 < p < 2$, which we reproduce for completeness. We first bound

\begin{align*}
\norm*{\bfx}_2^2 &= \norm*{\bfD^{p/2-1}\bfU\bfx}_2^2 \\
&= \sum_{i=1}^n \abs*{\bfe_i^\top \bfD^{p/2-1}\bfU\bfx}^2 \\
&= \sum_{i=1}^n \norm*{\bfe_i^\top\bfU}_2^{p-2} \abs*{\bfe_i^\top \bfU\bfx}^2 \\
&= \sum_{i=1}^n \norm*{\bfe_i^\top\bfU}_2^{p-2} \abs*{\bfe_i^\top \bfU\bfx}^{2-p}\abs*{\bfe_i^\top \bfU\bfx}^p \\
&\leq \max_{i=1}^n \bracks*{\norm*{\bfe_i^\top\bfU}_2^{p-2} \abs*{\bfe_i^\top \bfU\bfx}^{2-p}} \norm*{\bfU\bfx}_p^p && \text{H\"older, $2-p>0$} \\
&\leq \max_{i=1}^n \bracks*{\norm*{\bfe_i^\top\bfU}_2^{p-2} \norm*{\bfe_i^\top \bfU}_2^{2-p}\norm*{\bfx}_2^{2-p}} \norm*{\bfU\bfx}_p^p && \text{Cauchy-Schwarz} \\
&= \norm*{\bfx}_2^{2-p}\norm*{\bfU\bfx}_p^p.
\end{align*}

Rearranging then gives

\[
\norm*{\bfx}_2 \leq \norm*{\bfU\bfx}_p.
\]

For the upper bound, we have

\begin{align*}
\norm*{\bfU\bfx}_p^p &= \sum_{i=1}^n \abs*{\bfe_i^\top\bfU\bfx}^p \\
&= \sum_{i=1}^n \abs*{\bfe_i^\top\bfU\bfx}^p (\norm*{\bfe_i^\top\bfU}_2^{p-2})^{p/2}(\norm*{\bfe_i^\top\bfU}_2^{p-2})^{-p/2} \\
&\leq \parens*{\sum_{i=1}^n\abs*{\bfe_i^\top\bfU\bfx}^2 \norm*{\bfe_i^\top\bfU}_2^{p-2}}^{p/2}\parens*{\sum_{i=1}^n (\norm*{\bfe_i^\top\bfU}_2^{p-2})^{(-p/2)(2/(2-p))}}^{(2-p)/2} \\
&= \norm*{\bfD^{p/2-1}\bfU\bfx}_2^p \parens*{\sum_{i=1}^n \norm*{\bfe_i^\top\bfU}_2^{p}}^{(2-p)/2} \\
&= \norm*{\bfD^{p/2-1}\bfU\bfx}_2^p d^{(2-p)/2} \\
&= \norm*{\bfx}_2^p d^{(2-p)/2}
\end{align*}

where the inequality is by Hölder with exponent $2/p$, and the second to last identity uses Lemma <ref>. Taking $1/p$th powers on both sides gives

\[
\norm*{\bfU\bfx}_p \leq d^{1/p - 1/2} \norm*{\bfx}_2.\qedhere
\]

Finally, using Lemmas <ref> and <ref>, we obtain an $\ell_p$ sensitivity bound for all $0 < p < \infty$ via Lewis weights.

Let $\bfU$ be as defined in Theorem <ref>. Then for all $\bfx\in\mathbb R^d$,

\[
\frac{\abs*{\bfe_i^\top\bfU\bfx}^p}{\norm*{\bfU\bfx}_p^p} \leq d^{\max\{0,p/2-1\}}\norm*{\bfe_i^\top\bfU}_2^p = d^{\max\{0,p/2-1\}}\bfw_i^p(\bfA)
\]

\[
\sum_{i=1}^n d^{\max\{0,p/2-1\}}\norm*{\bfe_i^\top\bfU}_2^p = \sum_{i=1}^n d^{\max\{0,p/2-1\}}\bfw_i^p(\bfA) = d^{\max\{1,p/2\}}.
\]

Let $\bfx\in\mathbb R^d$. By using Lemma <ref>, we have

\[
\abs*{\bfe_i^\top\bfU\bfx}^p \leq \norm*{\bfe_i^\top\bfU}_2^p \norm*{\bfx}_2^p \leq d^{\max\{0,p/2-1\}}\norm*{\bfe_i^\top\bfU}_2^p \norm*{\bfU\bfx}_p^p
\]

which rearranges to

\[
\frac{\abs*{\bfe_i^\top\bfU\bfx}^p}{\norm*{\bfU\bfx}_p^p} \leq d^{\max\{0,p/2-1\}}\norm*{\bfe_i^\top\bfU}_2^p.
\]

To bound the sum of these, we use Lemma <ref> to conclude.

§ ADDITIONAL PROPERTIES OF M-NORMS

We prove additional properties of $M$-norms that we need in this section. These results are generally relatively straightforward generalizations of results in [21].

§.§ Consequences of Polynomial Boundedness

The polynomial boundedness condition allows us to compare the $M$-norm with the $\ell_{p_M}$ norm.

Let $\bfx\in\mathbb R^n$. Let $\bfw\geq\mathbf{1}_n$ be a set of weights. Then,

\[
M\parens*{\norm*{\bfx}_{p_M,\bfw}} \leq c_U^3 \norm*{\bfx}_{M,\bfw}^{p_M}
\]

Furthermore, if $M$ is strictly increasing, then

\[
\norm*{\bfx}_{p_M,\bfw} \leq M^{-1}(c_U^3 \norm*{\bfx}_{M,\bfw}^{p_M}).
\]

If $\bfw = \mathbf{1}_n$, then the $c_U^3$ may be replaced by a $c_U^2$.

Let $\bfW$ be the $n\times n$ diagonal matrix with $\bfw$ down the diagonal. Then,

\[
\norm*{\bfx}_{p_M,\bfw} = \norm*{\bfW^{1/p_M}\bfx}_{p_M}.
\]

We have

\begin{align*}
M\parens*{\norm*{\bfW^{1/p_M}\bfx}_{p_M}} &\leq c_U\frac{\norm*{\bfW^{1/p_M}\bfx}_{p_M}^{p_M}}{\norm*{\bfW^{1/p_M}\bfx}_{\infty}^{p_M}}M\parens*{\norm*{\bfW^{1/p_M}\bfx}_\infty} \\
&= c_U\sum_{i=1}^n \frac{\bfw_i\abs*{\bfx_i}^{p_M}}{\norm*{\bfW^{1/p_M}\bfx}_{\infty}^{p_M}}M\parens*{\norm*{\bfW^{1/p_M}\bfx}_\infty} \\
&\leq c_U^2\sum_{i=1}^n \frac{\bfw_i\abs*{\bfx_i}^{p_M}}{\norm*{\bfW^{1/p_M}\bfx}_{\infty}^{p_M}}\frac{\norm*{\bfW^{1/p_M}\bfx}_\infty^{p_M}}{\bfw_i\abs*{\bfx_i}^{p_M}}M(\bfw_i^{1/p_M}\abs*{\bfx_i}) \\
&\leq c_U^3\sum_{i=1}^n \bfw_i M(\abs*{\bfx_i}) \\
&= c_U^3\norm*{\bfx}_{M,\bfw}^{p_M}.
\end{align*}

If $\bfw = \mathbf{1}_n$, then inequality is not needed, so $c_U^3$ can be replaced by $c_U^2$. If $M$ is strictly increasing, then $M^{-1}$ is strictly increasing and thus we may apply $M^{-1}$ on both sides of the above inequality.

The following is a simple property of Definition <ref>.

Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ be strictly increasing. Then:

* If $M$ is polynomially bounded above with degree $p$ and constant $c_U\geq 1$. Then, $M^{-1}$ is polynomially bounded below with degree $1/p$ and constant $1/c_U^{1/p}$.

* If $M$ is polynomially bounded below with degree $q$ and constant $c_L\geq 1$. Then, $M^{-1}$ is polynomially bounded above with degree $1/q$ and constant $1/c_L^{1/q}$.

Let $M$ be polynomially bounded above. Let $y/x = \kappa > 1$. Then,

\[
M\parens*{\parens*{\frac{\kappa}{c_U}}^{1/p} M^{-1}(x)} \leq c_U\parens*{\frac{\kappa}{c_U}}M(M^{-1}(x)) = \kappa x.
\]

Applying $M^{-1}$ on both sides gives that

\[
M^{-1}(\kappa x) \geq \frac1{c_U^{1/p}} \kappa^{1/p}M^{-1}(x).
\]

Similarly, let $M$ be polynomially bounded below. Let $y/x = \kappa > 1$. Then,

\[
M\parens*{\parens*{\frac{\kappa}{c_L}}^{1/q} M^{-1}(x)} \geq c_L\parens*{\frac{\kappa}{c_L}}M(M^{-1}(x)) = \kappa x.
\]

Applying $M^{-1}$ on both sides gives that

\[
M^{-1}(\kappa x) \leq \frac1{c_L^{1/q}} \kappa^{1/q}M^{-1}(x).\qedhere
\]

The next lemma compares important entries using the polynomial boundedness condition.

Let $M$ be polynomially bounded above with degree $p$ and constant $c_U\geq 1$. Let $\bfx\in\mathbb R^n$ be a vector with entries arranged in order, i.e., $\abs*{\bfx_1} \geq \abs*{\bfx_2} \geq \dots \geq \abs*{\bfx_n}$. Then,

\[
\frac{M(\abs*{\bfx_1})}{\norm*{\bfx}_M^p} \leq c_U \frac{\abs*{\bfx_1}^p}{\norm*{\bfx}_p^p}.
\]

Note that for all $i \geq 2$, we have by the polynomially boundedness condition that

\[
\frac{M(\abs*{\bfx_1})}{M(\abs*{\bfx_i})} \leq c_u \parens*{\frac{\abs*{\bfx_1}}{\abs*{\bfx_i}}}^p = c_U \frac{\abs*{\bfx_1}^p}{\abs*{\bfx_i}^p}.
\]

\begin{align*}
\frac{M(\abs*{\bfx_1})}{\norm*{\bfx}_M^p} &= \frac{M(\abs*{\bfx_1})}{M(\abs*{\bfx_1}) + \sum_{i=2}^n M(\abs*{\bfx_i})} \\
&= \bracks*{1 + \sum_{i=2}^n \frac{M(\abs*{\bfx_i})}{M(\abs*{\bfx_1})}}^{-1} \leq \bracks*{1 + \sum_{i=2}^n \frac1{c_U}\frac{\abs*{\bfx_i}^p}{\abs*{\bfx_1}^p}}^{-1} \\
&= \frac{\abs*{\bfx_1}^p}{\abs*{\bfx_1}^p + c_U^{-1}\sum_{i=2}^n \abs*{\bfx_i}^p} \leq c_U\frac{\abs*{\bfx_1}^p}{\norm*{\bfx}_p^p}.\qedhere
\end{align*}

§.§ The Triangle Inequality

It will be useful to have the triangle inequality for the $M$-norm. For this we will need to assume that $M^{1/p_M}$ is subadditive.

Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and furthermore that $M^{1/p_M}$ is subadditive. Let $\bfw\geq\mathbf{1}_n$ be a set of weights. Then, for all $\bfy_1, \bfy_2\in\mathbb R^n$,

\[
\norm*{\bfy_1 + \bfy_2}_{M,\bfw} \leq \norm*{\bfy_1}_{M,\bfw} + \norm*{\bfy_2}_{M,\bfw}.
\]

The proof is by a simple modification of the proof of Minkowski's inequality. We first bound

\begin{align*}
\norm*{\bfy_1 + \bfy_2}_{M,\bfw}^{p_M} &= \sum_{i=1}^n \bfw_i M(\abs*{(\bfy_1)_i + (\bfy_2)_i}) \\
&= \sum_{i=1}^n \bfw_i \parens*{M(\abs*{(\bfy_1)_i + (\bfy_2)_i})^{1/p_M}} \parens*{M(\abs*{(\bfy_1)_i + (\bfy_2)_i})^{(p_M-1)/p_M}} \\
&\leq \sum_{i=1}^n \bfw_i[M^{1/p_M}(\abs*{(\bfy_1)_i}) + M^{1/p_M}(\abs*{(\bfy_2)_i})]\parens*{M(\abs*{(\bfy_1)_i + (\bfy_2)_i})^{(p_M-1)/p_M}} \tag{Subadditivity} \\
&= \sum_{i=1}^n \bfw_i M^{1/p_M}(\abs*{(\bfy_1)_i})M(\abs*{(\bfy_1)_i + (\bfy_2)_i})^{(p_M-1)/p_M} + \\
&\hspace{3em}\sum_{i=1}^n \bfw_i M^{1/p_M}(\abs*{(\bfy_2)_i})M(\abs*{(\bfy_1)_i + (\bfy_2)_i})^{(p_M-1)/p_M} \\
&\leq \parens*{\sum_{i=1}^n \bfw_i M(\abs*{(\bfy_1)_i})}^{1/p_M}\parens*{\sum_{i=1}^n \bfw_i M(\abs*{(\bfy_1)_i + (\bfy_2)_i})}^{(p_M - 1)/p_M} + \\ &\hspace{3em}\parens*{\sum_{i=1}^n \bfw_i M(\abs*{(\bfy_2)_i})}^{1/p_M}\parens*{\sum_{i=1}^n \bfw_i M(\abs*{(\bfy_1)_i + (\bfy_2)_i})}^{(p_M - 1)/p_M} \tag{H\"older} \\
&= \parens*{\norm*{\bfy_1}_{M,\bfw} + \norm*{\bfy_2}_{M,\bfw}} \norm*{\bfy_1 + \bfy_2}_{M,\bfw}^{p_M - 1}.
\end{align*}

Rearranging then gives the desired result.

We note that the subadditivity condition in fact implies the polynomially boundedness condition with constant $2^{p_M}$.

Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ be any increasing function such that $M^{1/p_M}$ is subadditive. Then, $M$ is polynomially bounded above with degree $p_M$ and constant $2^{p_M}$.

Let $k\geq 0$ be an integer and $f$ a subadditive and increasing function. Then, it is easy to see by subadditivity that

\[
f(2^k x) \leq 2^k f(x)
\]

by repeatedly applying subadditivity $k$ times. Now let $u > v$. Then,

\[
2^k v < u \leq 2^{k+1} v
\]

for some integer $k\geq 0$. Then, by using that $f$ is increasing,

\[
\frac{f(u)}{f(v)} \leq \frac{f(2^{k+1}v)}{f(v)} \leq \frac{2^{k+1}f(v)}{f(v)} < 2\frac{u}{v}.
\]

Applying the above to $f = M^{1/p_M}$ so that

\[
\frac{M^{1/p_M}(y)}{M^{1/p_M}(x)} \leq 2\parens*{\frac{y}{x}}.
\]

Raising both sides to the $p_M$th power leads to the desired conclusion.

§.§ Nets for M-Estimators

It is often desirable to construct nets in the $M$-norm in order to design row sampling algorithms for $M$-estimators. For this, we additionally need a polynomial lower bound as in Definition <ref>.

We first define balls, spheres, and covers for the $M$-norm. Note that we specialize our definitions to a subspace specified by an $n\times d$ matrix $\bfA$. The dependence on $\bfA$ will be clear from context and thus implicit.

Let $\bfA\in\mathbb R^{n\times d}$ and let $\mathcal V = \Span(\bfA)$. Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and let $\bfw\geq\mathbf{1}_n$ be a set of weights. Let $\eps>0$. Define an $\eps$-net (or $\eps$-cover) of a set $\mathcal A$ as a set of points $\mathcal N \subseteq\mathcal A$ such that

\[
\mathcal A \subseteq \bigcup_{\bfy\in \mathcal N} (\bfy + \mathcal B_{\eps}^{M,\bfw})
\]

where $\mathcal B_\eps^{M,\bfw}$ is the $M$ ball of radius $\eps$ (see Definition <ref>).

For norms, the following is known.

Let $\mathcal B$ be the unit ball of a $d$-dimensional subspace of a normed space $(X,\norm*{\cdot})$. Then for any $0<\eps<1$, there is a net $\mathcal N$ with

\[
\log\abs*{\mathcal N} = O\parens*{d\log\frac1\eps}
\]

such that, for any $\bfy\in\mathcal B$, there is a $\bfy'\in\mathcal N$ such that $\norm*{\bfy-\bfy'} \leq \eps$.

We give the following analogous result on covers of $M$ balls.

Let $\bfA\in\mathbb R^{n\times d}$. Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and furthermore that $M$ is polynomially bounded below with degree $q_M$ and constant $c_L$ (see Definition <ref>). Let $\bfw\geq\mathbf{1}_n$ be a set of weights. Consider the subspace $\mathcal V = \Span(\bfA)$. Let $\mathcal C\subset\mathcal V$. Then, there is an $\eps\rho$-covering $\mathcal N$ of $\mathcal B_\rho\cap \mathcal C$ of size at most

\[
\log\abs*{\mathcal N} \leq O\parens*{d\log\frac1{\eps^{p_M/q_M}}}.
\]

Note that by Lemma <ref>, $M$ is polynomially bounded above with degree $p_M$ and constant $c_U = 2^{p_M}$. Thus,

\[
c_L \parens*{\frac{y}{x}}^{q_M} \leq \frac{M(y)}{M(x)} \leq c_U\parens*{\frac{y}{x}}^{p_M}.
\]

Then for any $\kappa \geq 1$ and $x\geq 0$, this implies that

\[
c_L \kappa^{q_M} M(x) \leq M(\kappa x) \leq c_U \kappa^{p_M} M(x).
\]

This in turn implies the “scale insensitivity” condition

\begin{equation}\label{eqn:scale-insensitivity}
c_L\kappa^{q_M}\norm*{\bfy}_{M,\bfw}^{p_M}\leq \norm*{\kappa\bfy}_{M,\bfw}^{p_M} \leq c_L\kappa^{p_M} \norm*{\bfy}_{M,\bfw}^{p_M}
\end{equation}

for $\kappa \geq 1$ for the $M$-norm. Now let $\alpha = (c_L\eps^{p_M})^{1/q_M}$. Then,

\[
\norm*{\alpha\bfy}_{M,\bfw}^{p_M} \leq \frac{\alpha^{q_M}}{c_L}\norm*{\bfy}_{M,\bfw}^{p_M} = \eps^{p_M}\norm*{\bfy}_{M,\bfw}^{p_M}
\]

so $\alpha\mathcal B_\rho \subseteq \mathcal B_{\eps\rho}$. Then, the volume argument in Lemma 33 of [21] then shows that at most $(1/\alpha)^d$ translates of $\alpha\mathcal B_{\rho}$ can fit in $\mathcal B_{\rho}$, which in turn implies that there exists an $\eps\rho$-cover of $\mathcal B_\rho$ of size at most $O(1/\alpha)^d$.

§.§ From Nets to Balls

Next, we show an adaptation of Lemma 34 of [21], which shows that approximation guarantees on nets over the ball imply approximation guarantees on the entire ball. This requires both the triangle inequality as discussed in Section <ref> and the polynomial lower bound as discussed in Section <ref>.

We first show that the two additional assumptions give us the continuity of the $M$-norm.

Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and furthermore that

* $M^{1/p_M}$ is subadditive

* $M$ is polynomially bounded below with degree $q_M$ and constant $c_L$ (see Definition <ref>)

Let $\bfw\geq \mathbf{1}_n$ be a set of weights. Let $\bfx\in\mathbb R^n$ and $\bfb\in\mathbb R^n$. Then,

\[
\kappa \mapsto \norm*{\kappa\bfx - \bfb}_{M,\bfw}
\]

is a continuous function.

Let $\kappa > 0$ and $\eps > 0$. Let $\kappa'$ be such that

\[
\abs*{\kappa' - \kappa} \leq \parens*{c_L\bracks*{\frac{\eps}{\norm*{\bfx}_{M,\bfw}}}^{p_M}}^{1/q_M}
\]

\begin{align*}
\abs*{\norm*{\kappa'\bfx-\bfb}_{M,\bfw} - \norm*{\kappa\bfx-\bfb}_{M,\bfw}} &\leq \norm*{\kappa'\bfx - \kappa\bfx}_{M,\bfw} && \text{triangle inequality} \\
&= \norm*{(\kappa' - \kappa)\bfx}_{M,\bfw} \\
&\leq \bracks*{\frac{\abs*{\kappa' - \kappa}^{q_M}}{c_L}}^{1/p_M}\norm*{\bfx}_{M,\bfw} && \text{Equation \eqref{eqn:scale-insensitivity}} \\
&\leq \eps
\end{align*}

as desired.

With the continuity of the $M$-norm in hand, we will next show that we may translate approximation guarantees on a net for the $M$-norm ball to approximation guarantees on the entire ball. For norms, the following is known.

Let $\eps\in(0,1/2)$. Let $\norm*{\cdot}_X$ and $\norm*{\cdot}_Y$ be two norms over a subspace $\mathcal V\subseteq\mathbb R^n$. Let $\mathcal N$ be an $\eps$-net over the unit sphere $\mathcal S_{X} = \braces*{\bfy\in \mathcal V : \norm*{\bfy}_X = 1}$ for $\norm*{\cdot}_X$. Then if

\[
\abs*{\norm*{\bfy}_X - \norm*{\bfy}_Y} \leq \eps
\]

for all $\bfy\in\mathcal N$, then

\[
\abs*{\norm*{\bfy}_X - \norm*{\bfy}_Y} \leq 4\eps
\]

for all $\bfy\in\mathcal S_X$.

The analogous result for $M$-norms is the following:

Let $\bfA\in\mathbb R^{n\times d}$ and let $\mathcal V = \Span(\bfA)$. Let $\bfb\in\mathbb R^n$. Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and furthermore that

* $M^{1/p_M}$ is subadditive

* $M$ is polynomially bounded below with degree $q_M$ and constant $c_L$ (see Definition <ref>)

Let $\bfw, \bfv\geq \mathbf{1}_n$ be two sets of weights. Let $\eps\in(0,1/2)$ and $\rho > 0$. Let $\mathcal N$ be an $\alpha\rho$-cover of $\mathcal B_\rho^{M,\bfw}$ for

\[
\alpha = \frac{c_L^{1/q_M}}{c_U^{1/p_M}}\eps^{p_M/q_M}.
\]

Then, if

\[
\abs*{\norm*{\bfy}_{M,\bfv} - \norm*{\bfy}_{M,\bfw}} \leq \eps\rho
\]

for all $\bfy\in(\mathcal N - \bfb)$ and $\bfy\in\mathcal N$, then

\[
\abs*{\norm*{\bfy}_{M,\bfv} - \norm*{\bfy}_{M,\bfw}} \leq 4\eps\rho
\]

for all $\bfy\in(\mathcal B_\rho^{M,\bfw} - \bfb)$ and $\bfy\in\mathcal B_\rho^{M,\bfw}$.

\[
\Delta \coloneqq \sup\braces*{\frac{\abs*{\norm*{\bfy}_{M,\bfv} - \norm*{\bfy}_{M,\bfw}}}\rho  : \bfy\in (\mathcal B_\rho^{M,\bfw} - \bfb)\cup\mathcal B_\rho^{M,\bfw}}.
\]

Let $\bfy\in(\mathcal B_\rho^{M,\bfw} - \bfb)\cup\mathcal B_\rho^{M,\bfw}$. Let $\bfy'\in(\mathcal N - \bfb)\cup\mathcal N$ be such that $\bfy - \bfy' \in\mathcal V$ (by choosing $\bfy'$ to be in the appropriate net to cancel out the possible $\bfb$) and

\[
\norm*{\bfy - \bfy'}_{M,\bfw} \leq \alpha\rho
\]

and let $\kappa\geq1$ be such that $\kappa(\bfy - \bfy') \in \mathcal S_\rho^{M,\bfw}$, which exists by Lemma <ref>. By the polynomial lower bound condition, we have the scale insensitivity condition (see Equation (<ref>)), which in turn implies that

\[
\rho = \norm*{\kappa(\bfy-\bfy')}_{M,\bfw} \leq c_U^{1/p_M}\kappa\norm*{\bfy-\bfy'}_{M,\bfw} \leq c_U^{1/p_M}\kappa \alpha \rho = \kappa ((c_L\eps^{p_M})^{1/q_M}) \rho
\]

\begin{equation}\label{eqn:kappa-lower-bound}
\kappa \geq \frac1{(c_L\eps^{p_M})^{1/q_M}}
\end{equation}

\begin{align*}
\norm*{\bfy - \bfy'}_{M,\bfv} &\leq \frac1{(c_L\kappa^{q_M})^{1/p_M}}\norm*{\kappa(\bfy - \bfy')}_{M,\bfv} && \text{scale insensitivity} \\
&\leq \eps\norm*{\kappa(\bfy - \bfy')}_{M,\bfv} && \text{Equation \eqref{eqn:kappa-lower-bound}} \\
&\leq \eps(1+\Delta)\rho.
\end{align*}

\begin{align*}
\norm*{\bfy}_{M,\bfv} \leq \norm*{\bfy'}_{M,\bfv} + \norm*{\bfy-\bfy'}_{M,\bfv} \leq \norm*{\bfy'}_{M,\bfw} + \eps\rho + \eps(1+\Delta)\rho
\end{align*}

\[
\frac{\norm*{\bfy}_{M,\bfv} - \norm*{\bfy'}_{M,\bfw}}\rho \leq \eps + \eps(1+\Delta).
\]

By taking supremums over both sides,

\[
\Delta \leq 2\eps + \eps\Delta \implies \Delta \leq \frac{2\eps}{1-\eps} \leq 4\eps
\]

We then also have that

\begin{align*}
\norm*{\bfy}_{M,\bfv} &\geq \norm*{\bfy'}_{M,\bfv} - \norm*{\bfy-\bfy'}_{M,\bfv} \\
&\geq \norm*{\bfy'}_{M,\bfw}-\eps\rho - \eps(1+4\eps)\rho \\
&\geq \norm*{\bfy'}_{M,\bfw} - 4\eps\rho.\qedhere
\end{align*}

One way to cope with the scale invariance is to show looser approximations for all “large” and all “small” scales, given a guarantee on a sphere of a single radius.

Let $\bfA\in\mathbb R^{n\times d}$ and let $\mathcal V = \Span(\bfA)$. Let $M:\mathbb R_{\geq0}\to\mathbb R_{\geq0}$ satisfy the conditions of Definition <ref>, and furthermore that

* $M^{1/p_M}$ is subadditive

* $M$ is polynomially bounded below with degree $q_M$ and constant $c_L$ (see Definition <ref>)

Let $\bfw, \bfv\geq \mathbf{1}_n$ be two sets of weights. Let $\eta > 0$. Then,

* If $\norm*{\bfy}_{M,\bfw} \leq \eta\rho$ for all $\bfy\in\mathcal S_\rho^{M,\bfw}$, then $\norm*{\bfy}_{M,\bfw} \leq \eta\rho/c_L^{1/p_M}$ for all $\bfy\in\mathcal B_\rho^{M,\bfw}$.

* If $\norm*{\bfy}_{M,\bfw} \geq \eta\rho$ for all $\bfy\in\mathcal S_\rho^{M,\bfw}$, then $\norm*{\bfy}_{M,\bfw} \geq c_L^{1/p_M}\eta\rho$ for all $\bfy\notin\mathcal B_\rho^{M,\bfw}$.

Let $\bfy\in\mathcal B_\rho^{M,\bfw}$ and let $\kappa\geq 1$ be such that $\norm*{\kappa\bfy}_{M,\bfw} = \rho$. Then,

\[
\norm*{\bfy}_{M,\bfv} \leq \frac1{(c_L\kappa^{q_M})^{1/p_M}}\norm*{\kappa\bfy}_{M,\bfv} \leq \frac1{c_L^{1/p_M}}\eta\rho.
\]

Let $\bfy\notin\mathcal B_\rho^{M,\bfw}$ and let $\alpha\leq 1$ be such that $\norm*{\alpha\bfy}_{M,\bfw} = \rho$. Then,

\[
\norm*{\bfy}_{M,\bfv} \geq \parens*{c_L\frac1{\alpha^{q_M}}}^{1/p_M}\norm*{\alpha\bfy}_{M,\bfv} \geq c_L^{1/p_M}\eta\rho.\qedhere
\]

§.§ Proof of Lemma <ref>

By Lemma <ref>, it suffices to prove the approximation guarantee on a $\alpha\rho$-cover $\mathcal N$ of $\mathcal S_\rho^{M}$, where $\alpha = O(\eps^{p_M/q_M})$. By Lemma <ref>, this has size at most

\[
\log\abs*{\mathcal N} \leq O\parens*{d\log\frac1\eps}.
\]

Fix a $\bfy\in\mathcal N$ and define the random variable

\[
W_i \coloneqq \bfw_i' M(\bfy(i))
\]

for each $i\in[n]$. Then,

\[
\E\bracks*{\sum_{i=1}^n W_i} = \sum_{i=1}^n \frac{\bfw_i}{\bfp_i}M(\bfy(i))\cdot \bfp_i = \norm*{\bfy}_{M,\bfw}^{p_M}.
\]

We next bound the variance:

\[
\Var\bracks*{\sum_{i=1}^n W_i} = \sum_{i=1}^n \Var[W_i] \leq \sum_{i=1}^n \frac{\bfw_i^2}{\bfp_i^2}M(\bfy(i))^2\cdot \bfp_i = \sum_{i=1}^n \frac{\bfw_i}{\bfp_i}M(\bfy(i))\cdot \bfw_i M(\bfy(i))
\]

Note that

\[
\frac{\bfw_i}{\bfp_i}M(\bfy(i)) \leq \frac{\tilde\bfs_i^{M,\bfw}(\bfA)\norm*{\bfy}_{M,\bfw}^{p_M}}{m\cdot \tilde\bfs_i^{M,\bfw}(\bfA)} \leq \frac1m \norm*{\bfy}_{M,\bfw}^{p_M}
\]

so the variance is bounded by

\[
\Var\bracks*{\sum_{i=1}^n W_i} \leq \frac1m \norm*{\bfy}_{M,\bfw}^{p_M} \sum_{i=1}^n \bfw_i M(\bfy(i)) = \frac{1}{m}\norm*{\bfy}_{M,\bfw}^{2p_M}.
\]

Then by Bernstein's inequality,

\begin{align*}
\Pr\braces*{\abs*{\sum_{i=1}^n W_i - \norm*{\bfy}_{M,\bfw}^{p_M}} > t} &\leq 2\exp\parens*{-\Theta(1)\frac{t^2}{\frac{1}{m}\norm*{\bfy}_{M,\bfw}^{2p_M} + \frac1m \norm*{\bfy}_{M,\bfw}^{p_M} t}} \\
&= 2\exp\parens*{-\Theta(1)\frac{mt^2}{\norm*{\bfy}_{M,\bfw}^{p_M}(\norm*{\bfy}_{M,\bfw}^{p_M} + t)}}.
\end{align*}

For $t = \eps\norm*{\bfy}_{M,\bfw}^{p_M}$, this gives a bound of

\[
2\exp\parens*{-\Theta(1)\frac{m(\eps\norm*{\bfy}_{M,\bfw}^{p_M})^2}{\norm*{\bfy}_{M,\bfw}^{2p_M}}} =  2\exp\parens*{-\Theta(1)m\eps^2}.
\]

We then set

\[
m = O\parens*{\frac{d}{\eps^2}\parens*{\log\frac1\eps}\parens*{\log\frac1\delta}}
\]

which is enough to union bound over the net $\mathcal N$ with failure probability at most $\delta$.

\[
\E\nnz(\bfw') = \sum_{i=1}^n \bfp_i \leq m\sum_{i=1}\tilde\bfs_i^{M,\bfw}(\bfA) = m\tilde{\mathcal T}^{M,\bfw}(\bfA).\qedhere
\]

§ MISSING PROOFS FOR SECTION <REF>

§.§ Proof of Lemma <ref>

Suppose that $\bfA\bfx$ satisfies

\[
1 = \sum_{i=1}^n \bfw_i G(\abs*{[\bfA\bfx](i)}) = \sum_{j=1}^N \sum_{i\in T_j}  \bfw_i G(\abs*{[\bfA\bfx](i)}).
\]

Then for each $j\geq 0$,

\[
\sum_{i\in T_j}  G_j (\abs*{[\bfA\bfx](i)}) = \sum_{i\in T_j}  2^{j-1}  G(\abs*{[\bfA\bfx](i)})\leq \sum_{i\in T_j}  \bfw_i G(\abs*{[\bfA\bfx](i)}) \leq 1.
\]

Then using our previous result, we have that

\[
G_j (\abs*{[\bfA\bfx](i)}) \leq \bfs_i^{G_j}(\bfA\mid_{T_j})
\]

where $\bfA\mid_{T_j}$ is the restriction of $\bfA$ to the rows of $T_j$, and

\[
\sum_{i\in T_j}\bfs_i^{G_j}(\bfA\mid_{T_j}) \leq O(d^{\max\{1,p_G/2\}}\log n).
\]

\[
\bfw_i G(\abs*{[\bfA\bfx](i)}) \leq 2^{j+1}\cdot G(\abs*{[\bfA\bfx](i)}) \leq 2\cdot G_j (\abs*{[\bfA\bfx](i)}) \leq 2\bfs_i^{G_j}(\bfA\mid_{T_j})
\]

\[
\bfs_i^{G,\bfw}(\bfA) \leq 2\cdot \bfs_i^{G_j}(\bfA\mid_{T_j})
\]

\[
\sum_{i=1}^n \bfs_i^{G,\bfw}(\bfA) = \sum_{j=1}^N \sum_{i\in T_j}\bfs_i^{G,\bfw}(\bfA) \leq \sum_{j=1}^N O(d^{\max\{1,p_G/2\}}\log n) \leq O(N\cdot d^{\max\{1,p_G/2\}}\log n)
\]

as claimed.