# A Nearly-Optimal Bound for Fast Regression with $\ell_{\infty}$ Guarantee

Zhao Song<EMAIL_ADDRESS>Adobe Research. Mingquan Ye<EMAIL_ADDRESS>University of Illinois at Chicago. Junze Yin<EMAIL_ADDRESS>Boston University.
Lichen Zhang<EMAIL_ADDRESS>MIT.

Given a matrix $A\in\mathbb{R}^{n\times d}$ and a vector $b\in\mathbb{R}^{n}$,
we consider the regression problem with $\ell_{\infty}$ guarantees: finding a
vector $x^{\prime}\in\mathbb{R}^{d}$ such that

$\displaystyle\|x^{\prime}-x^{*}\|_{\infty}\leq$
$\displaystyle~{}\frac{\epsilon}{\sqrt{d}}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|,$

where $x^{*}=\arg\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$. One popular approach
for solving such $\ell_{2}$ regression problem is via sketching: picking a
structured random matrix $S\in\mathbb{R}^{m\times n}$ with $m\ll n$ and $SA$
can be quickly computed, solve the “sketched” regression problem
$\arg\min_{x\in\mathbb{R}^{d}}\|SAx-Sb\|_{2}$.

In this paper, we show that in order to obtain such $\ell_{\infty}$ guarantee
for $\ell_{2}$ regression, one has to use sketching matrices that are _dense_.
To the best of our knowledge, this is the first user case in which dense
sketching matrices are necessary. On the algorithmic side, we prove that there
exists a distribution of dense sketching matrices with
$m=\epsilon^{-2}d\log^{3}(n/\delta)$ such that solving the sketched regression
problem gives the $\ell_{\infty}$ guarantee, with probability at least
$1-\delta$. Moreover, the matrix $SA$ can be computed in time $O(nd\log n)$.
Our row count is nearly-optimal up to logarithmic factors, and significantly
improves the result in [22], in which a super-linear in $d$ rows,
$m=\Omega(\epsilon^{-2}d^{1+\gamma})$ for $\gamma=\Theta(\sqrt{\frac{\log\log
n}{\log d}})$ is required.

Moreover, we develop a novel analytical framework for $\ell_{\infty}$
guarantee regression that utilizes the _Oblivious Coordinate-wise Embedding_
(OCE) property introduced in [31]. Our analysis is much simpler and more
general than that of [22]. Leveraging this framework, we extend the
$\ell_{\infty}$ guarantee regression result to dense sketching matrices for
computing the fast tensor product of vectors.

###### Contents

  1. 1 Introduction
  2. 2 Preliminary
    1. 2.1 Oblivious subspace embedding and coordinate-wise embedding
    2. 2.2 Sketching matrices
    3. 2.3 OSE property of dense sketches
    4. 2.4 Probability tools
  3. 3 $\ell_{\infty}$ guarantee via OCE
    1. 3.1 High probability bound for OCE
    2. 3.2 Inner product bound for SRHT and SRCT
    3. 3.3 Column norm bound for SRHT and SRCT
  4. 4 Put things together
  5. 5 Conclusion
  6. A Tools for matrices and probability
  7. B Kronecker product regression with $\ell_{\infty}$ guarantee
    1. B.1 Main result
    2. B.2 Oblivious coordinate-wise embedding for TensorSRHT and TensorSRCT
  8. C SRCT and TensorSRCT: OSE via strong JL moment property
    1. C.1 Notations
    2. C.2 Strong JL moment property
    3. C.3 SRCT and TensorSRCT satisfy strong JL moment property
  9. D Gaussian and AMS
    1. D.1 OSE property of random Gaussian and AMS
    2. D.2 OCE property of random Gaussian and AMS

##  1 Introduction

Linear regression, or $\ell_{2}$ least-square problem is ubiquitous in
numerical linear algebra, scientific computing and machine learning. Given a
tall skinny matrix $A\in\mathbb{R}^{n\times d}$ and a label vector
$b\in\mathbb{R}^{n}$, the goal is to (approximately) compute an optimal
solution $x^{\prime}$ that minimizes the $\ell_{2}$ loss $\|Ax-b\|_{2}$. For
the regime where $n\gg d$, sketching is a popular approach to obtain an
approximate solution quickly [8, 7]: the idea is to pick a random matrix
$S\in\mathbb{R}^{m\times n}$ from carefully-designed distributions, so that
1). $S$ can be efficiently applied to $A$ and 2). the row count $m\ll n$.
Given these two guarantees, one can then solve the “sketched” regression
problem:

$\displaystyle\arg\min_{x\in\mathbb{R}^{d}}\|SAx-Sb\|_{2},$

and obtain a vector $x^{\prime}$ such that
$\|Ax^{\prime}-b\|_{2}=(1\pm\epsilon)\cdot{\rm OPT}$, where OPT denotes the
optimal $\ell_{2}$ discrepancy between vectors in column space of $A$ and $b$.
Recent advances in sketching [7] show that one can design matrix $S$ with
$m=O(\epsilon^{-2}d\log^{2}(n/\delta))$ and the sketched regression can be
solved in time
$O(\operatorname{nnz}(A)+d^{\omega}+\epsilon^{-2}d^{2}\operatorname{poly}\log(n,d,1/\epsilon,1/\delta))$
where $\operatorname{nnz}(A)$ denotes the number of nonzero entries of $A$ and
$\delta$ is the failure probability.

Unfortunately, modern machine learning emphasizes more and more on large,
complex, and nonlinear models such as deep neural networks, thus linear
regression becomes less appealing as a _model_. However, it is still a very
important _subroutine_ in many deep learning and optimization frameworks,
especially second-order method for training neural networks [4, 32] or convex
optimization [19, 20, 31, 15]. In these applications, one typically seeks
_forward error_ guarantee, i.e., how close is the approximate solution
$x^{\prime}$ to the optimal solution $x^{*}$. A prominent example is Newton’s
method: given the (possibly implicit) Hessian matrix $H\in\mathbb{R}^{d\times
d}$ and the gradient $g\in\mathbb{R}^{d}$, one wants to compute $H^{-1}g$. A
common approach is to solve the regression
$\arg\min_{x\in\mathbb{R}^{d}}\|Hx-g\|_{2}$, in which one wants
$\|x-H^{-1}g\|_{2}$ or even $\|x-H^{-1}g\|_{\infty}$ to be small. When the
matrix $S$ satisfies the so-called Oblivious Subspace Embedding (OSE) property
[25], one can show that the approximate solution $x^{\prime}$ is close to
$x^{*}$ in the $\ell_{2}$ sense:

$\displaystyle\|x^{\prime}-x^{*}\|_{2}\leq$
$\displaystyle~{}O(\epsilon)\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|.$ (1)

Unfortunately, $\ell_{2}$-closeness cannot characterize how good $x^{\prime}$
approximates $x^{*}$, as $x^{*}$ can have a good spread of $\ell_{2}$ mass
over all coordinates while $x^{\prime}$ concentrates its mass over a few
coordinates. Formally speaking, let $a\in\mathbb{R}^{d}$ be a fixed vector,
then one can measure how far $\langle a,x^{\prime}\rangle$ deviates from
$\langle a,x^{*}\rangle$ via Eq. (1):

$\displaystyle|\langle a,x^{*}\rangle-\langle a,x^{\prime}\rangle|=$
$\displaystyle~{}|\langle a,x^{\prime}-x^{*}\rangle|$ $\displaystyle\leq$
$\displaystyle~{}\|a\|_{2}\|x^{\prime}-x^{*}\|_{2}$ $\displaystyle\leq$
$\displaystyle~{}O(\epsilon)\cdot\|a\|_{2}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|.$

This bound is clearly too loose, as one would expect the deviation on a random
direction is only $\frac{1}{\sqrt{d}}$ factor of the $\ell_{2}$ discrepancy.
[22] shows that this intuition is indeed true when $S$ is picked as the
subsampled randomized Hadamard transform (SRHT) [17]: 111We will later refer
the following property as $\ell_{\infty}$ guarantee.

$\displaystyle|\langle a,x^{*}\rangle-\langle
a,x^{\prime}\rangle|\lesssim\frac{\epsilon}{\sqrt{d}}\|a\|_{2}\|Ax^{*}-b\|_{2}\|A^{\dagger}\|.$
(2)

However, their analysis is not tight as they require a row count
$m=\Omega(\epsilon^{-2}d^{1+\gamma})$ for $\gamma=\Theta(\sqrt{\frac{\log\log
n}{\log d}})$. Such a row count is super-linear in $d$ as long as
$n\leq\exp(d)$ and therefore is worse than the required row count for $S$ to
be a subspace embedding, in which only $m=\epsilon^{-2}d\log^{2}n$ rows are
required for constant success probability. In contrast, for random Gaussian
matrices, the $\ell_{\infty}$ guarantee only requires nearly linear in $d$
rows. In addition to their sub-optimal row count, the [22] analysis is also
complicated: let $U\in\mathbb{R}^{n\times d}$ be an orthonormal basis of $A$,
[22] has to analyze the higher moment of matrix $I_{d}-U^{\top}S^{\top}SU$.
This makes their analysis particularly hard to generalize to other dense
sketching matrices beyond SRHT.

In this work, we present a novel framework for analyzing the $\ell_{\infty}$
guarantee induced by SRHT and more generally, a large class of _dense_
sketching matrices. Our analysis is arguably much simpler than [22], and it
exposes the fundamental structure of sketching matrices that provides
$\ell_{\infty}$ guarantee: if any two columns of the sketching matrix have a
small inner product with high probability, then $\ell_{\infty}$ guarantee can
be preserved. We then prove that the small pairwise column inner product is
also closely related to the _Oblivious Coordinate-wise Embedding_ (OCE)
property introduced in [31]. More concretely, for any two fixed vectors
$g,h\in\mathbb{R}^{n}$, we say the sketching matrix is $(\beta,\delta,n)$-OCE
if $|\langle Sg,Sh\rangle-\langle
g,h\rangle|\leq\frac{\beta}{\sqrt{m}}\cdot\|g\|_{2}\|h\|_{2}$ holds with
probability at least $1-\delta$. This property has previously been leveraged
for approximating matrix-vector product between a dynamically-changing
projection matrix and an online sequence of vectors for the fast linear
program and empirical risk minimization algorithms [20, 15, 31, 23] as these
algorithms need $\ell_{\infty}$ bound on the matrix-vector product. One common
theme shared by those applications and $\ell_{\infty}$ guarantee is to use
_dense_ sketching matrices, such as random Gaussian, the Alon-Matias-Szegedy
sketch (AMS, [2]) or SRHT. This is in drastic contrast with the trending
direction for using sparse matrices such as Count Sketch [5, 8] and OSNAP [21,
6], as they can be applied in (nearly) input sparsity time.

In recent years, sketches that can be applied to the tensor product of
matrices/vectors have gained popularity [3, 27, 10, 28, 9, 1, 35, 26, 36, 30,
29, 24] as they can speed up optimization tasks and large-scale kernel
learning. We show that dense sketches for degree-2 tensors also provide
$\ell_{\infty}$ guarantee.

######  Theorem 1.1 (Nearly-optimal bound for dense sketching matrices).

Suppose $n\leq\exp(d)$ and matrix $A\in\mathbb{R}^{n\times d}$ and vector
$b\in\mathbb{R}^{n}$ are given. Let $S\in\mathbb{R}^{m\times n}$ be a
subsampled randomized Hadamard transform matrix SRHT with
$m=O(\epsilon^{-2}d\log^{3}(n/\delta))$ rows.

For any fixed vector $a\in\mathbb{R}^{d}$,

$\displaystyle|\langle a,x^{*}\rangle-\langle a,x^{\prime}\rangle|\lesssim$
$\displaystyle~{}\frac{\epsilon}{\sqrt{d}}\cdot\|a\|_{2}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|$

with probability $1-\delta$, where
$x^{\prime}=\arg\min_{x\in\mathbb{R}^{d}}\|SAx-Sb\|_{2}$,
$x^{*}=\arg\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$.

######  Remark 1.2.

The row count $m=\epsilon^{-2}d\log^{3}n$ is nearly-optimal up to logarithmic
factors, as the row count for $S$ being an OSE is $m=\epsilon^{-2}d\log^{2}n$
for constant success probability. In comparison, [22] requires
$m=\epsilon^{-2}d^{1+\gamma}$ rows for $\gamma=\Theta(\sqrt{\frac{\log\log
n}{\log d}})$ which is only nearly-linear in $d$ if $n>\exp(d)$. In most
applications, we concern about $n=\operatorname{poly}(d)$, meaning that their
row count is worse than ours in almost all meaningful scenarios.

The row count and guarantee obtained in Theorem 1.1 extend beyond SRHT; in
fact, for a range of _dense_ sketching matrices including random Gaussian, AMS
sketch [2], SRHT and subsampled randomized Circulant Transform (see Definition
2.11) (SRCT). This is because our argument is a structural condition that can
be satisfied by various dense sketches.

Our result can also be generalized to degree-2 Kronecker product regression,
see Theorem B.1.

#### Roadmap.

In Section 2, we introduce the notations that we use and explain the key
definitions and properties to support the framework for $\ell_{\infty}$
guarantee regression. In Section 3, we introduce our framework by presenting a
sufficient condition for a sketching matrix to give a good $\ell_{\infty}$
guarantee. In Section 4, we provide a proof for our main theorem by putting
everything together. Finally, in Section 5, we summarize the main findings of
this paper and through comparing with previous work.

##  2 Preliminary

For a positive integer, we define $[n]:=\\{1,2,\cdots,n\\}$. For a vector
$x\in\mathbb{R}^{n}$, we define $\|x\|_{2}:=(\sum_{i=1}^{n}x_{i}^{2})^{1/2}$
and $\|x\|_{\infty}:=\max_{i\in[n]}|x_{i}|$. For a matrix $A$, we define
$\|A\|:=\sup_{x}\|Ax\|_{2}/\|x\|_{2}$ to be the spectral norm of $A$. We use
$\|A\|_{F}:=\sum_{i,j}A_{i,j}^{2}$ to be the Frobenius norm of $A$. In
general, we have the following property for spectral norm,
$\|AB\|\leq\|A\|\cdot\|B\|$. We use $A^{\dagger}$ to denote the Moore-Penrose
pseudoinverse of $m\times n$ matrix $A$ which if $A=U\Sigma V^{\top}$ is its
SVD (where $U\in\mathbb{R}^{m\times n}$, $\Sigma\in\mathbb{R}^{n\times n}$ and
$V\in\mathbb{R}^{n\times n}$ for $m\geq n$), is given by
$A^{\dagger}=V\Sigma^{-1}U^{\top}$.

We use $\operatorname*{{\mathbb{E}}}[\cdot]$ to denote the expectation, and
$\Pr[\cdot]$ to denote the probability. For a distribution $D$ and a random
variable $x$, we use $x\sim D$ to denote that we draw a random variable from
the distribution $D$. We use ${\cal N}(\mu,\sigma^{2})$ to denote a Gaussian
distribution with mean $\mu$ and variance $\sigma^{2}$. We say a random
variable $x$ is Rademacher random variables if $\Pr[x=1]=1/2$ and
$\Pr[x=-1]=1/2$. We also call it a sign random variable.

In addition to $O(\cdot)$ notation, for two functions $f,g$, we use the
shorthand $f\lesssim g$ (resp. $\gtrsim$) to indicate that $f\leq Cg$ (resp.
$\geq$) for an absolute constant $C$. We use $f\eqsim g$ to mean $cf\leq g\leq
Cf$ for constants $c>0$ and $C>0$. For two matrices
$A\in\mathbb{R}^{n_{1}\times d_{1}}$, $B\in\mathbb{R}^{n_{2}\times d_{2}}$, we
use $A\otimes B\in\mathbb{R}^{n_{1}n_{2}\times d_{1}d_{2}}$ to denote the
Kronecker product, i.e., the $(i_{1},i_{2})$-th row and $(j_{1},j_{2})$-th
column of $A\times B$ is $A_{i_{1},j_{1}}B_{i_{2},j_{2}}$. For two vectors
$x\in\mathbb{R}^{m},y\in\mathbb{R}^{n}$, we use $x\otimes y\in\mathbb{R}^{mn}$
to denote the tensor product of vectors, in which $x\otimes
y=\operatorname{vec}(xy^{\top})$.

###  2.1 Oblivious subspace embedding and coordinate-wise embedding

######  Definition 2.1 (Oblivious subspace embedding [25]).

We define $(\epsilon,\delta,d,n)$-Oolivious subspace embedding (OSE) as
follows: Suppose $\Pi$ is a distribution on $m\times n$ matrices $S$, where
$m$ is a function of $n,d,\epsilon$, and $\delta$. Suppose that with
probability at least $1-\delta$, for any fixed $n\times d$ orthonormal basis
$U$, a matrix $S$ drawn from the distribution $\Pi$ has the property that the
singular values of $SU$ lie in the range $[1-\epsilon,1+\epsilon]$.

The oblivious coordinate-wise embedding (OCE) is implicitly used in [20, 15]
and formally introduced in [31].

######  Definition 2.2 ($(\alpha,\beta,\delta)$–coordinate wise embedding
[31]).

We say a random matrix $S\in\mathbb{R}^{m\times n}$ satisfying
$(\alpha,\beta,\delta)$–coordinate wise embedding if

$\displaystyle~{}1.\operatorname*{{\mathbb{E}}}_{S\sim\Pi}[g^{\top}S^{\top}Sh]=g^{\top}h,$
$\displaystyle~{}2.\operatorname*{{\mathbb{E}}}_{S\sim\Pi}[(g^{\top}S^{\top}Sh)^{2}]\leq(g^{\top}h)^{2}+\frac{\alpha}{m}\|g\|_{2}^{2}\|h\|_{2}^{2},$
$\displaystyle~{}3.\Pr_{S\sim\Pi}[|g^{\top}S^{\top}Sh-g^{\top}h|\geq\frac{\beta}{\sqrt{m}}\|g\|_{2}\|h\|_{2}]\leq\delta.$

In this paper, we mainly use the property 3 of Definition 2.2. For convenient,
we redefine OCE as follows:

######  Definition 2.3 (OCE).

Let $\beta\geq 1$ and $\delta\in(0,0.1)$. We say a randomized matrix
$S\in\mathbb{R}^{m\times n}$ satisfy $(\beta,\delta,n)$-OCE, if

$\displaystyle\Pr_{S\sim\Pi}[|g^{\top}S^{\top}Sh-g^{\top}h|\geq\frac{\beta}{\sqrt{m}}\|g\|_{2}\|h\|_{2}]\leq\delta$

and the distribution $\Pi$ is oblivious to any fixed vectors $g$ and $h$.

###  2.2 Sketching matrices

In this paper, we concern a list of dense sketching matrices.

######  Definition 2.4 (Random Gaussian matrix, folklore).

We say $S\in\mathbb{R}^{m\times n}$ is a random Gaussian matrix if all entries
are sampled from $\mathcal{N}(0,1/m)$ independently.

######  Definition 2.5 (AMS sketch matrix, [2]).

Let $h_{1},h_{2},\cdots,h_{m}$ be $m$ random hash functions picking from a
4–wise independent hash family
$\mathcal{H}=\\{h:[n]\to\\{-\frac{1}{m},+\frac{1}{m}\\}\\}$. Then
$S\in\mathbb{R}^{m\times n}$ is an AMS sketch matrix if we set
$S_{i,j}=h_{i}(j)$.

The following sketching matrices can utilize fast Fourier Transform (FFT) for
efficient application to matrices.

######  Definition 2.6 (Subsampled randomized Hadamard transform (SRHT) [17,
26]).

The SRHT matrix $S\in\mathbb{R}^{m\times n}$ is defined as
$S:=\frac{1}{\sqrt{m}}PHD$, where each row of matrix $P\in\\{0,1\\}^{m\times
n}$ contains exactly one $1$ at a random position, $H$ is the $n\times n$
Hadamard matrix, and $D$ is a $n\times n$ diagonal matrix with each diagonal
entry being a value in $\\{-1,+1\\}$ with equal probability.

######  Remark 2.7.

Using the fast Fourier transform (FFT), $S$ can be applied to a vector in time
$O(n\log{n})$.

######  Definition 2.8 (Tensor subsampled randomized Hadamard transform
(TensorSRHT) [26]).

The TensorSRHT $S:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}^{m}$ is
defined as $S:=\frac{1}{\sqrt{m}}P\cdot(HD_{1}\otimes HD_{2})$, where each row
of $P\in\\{0,1\\}^{m\times n^{2}}$ contains only one $1$ at a random
coordinate and one can view $P$ as a sampling matrix. $H$ is a $n\times n$
Hadamard matrix, and $D_{1}$, $D_{2}$ are two $n\times n$ independent diagonal
matrices with diagonals that are each independently set to be a Rademacher
random variable (uniform in $\\{-1,1\\}$).

######  Remark 2.9.

By leveraging the FFT algorithm in the sketch space, $S(x\otimes y)$ can be
computed in time $O(n\log{n}+m)$.

To store and generate a Hadamard matrix is expensive, we consider a cheaper
and space-efficient way to generate an FFT matrix via circulant transform.

######  Definition 2.10 (Circulant matrix).

A circulant matrix is an $n\times n$ matrix, where $n\in\mathbb{N}$, whose row
vectors consist of the same element, and compared to the preceding row vector,
each row vector is rotated one element to the right.

######  Definition 2.11 (Subsampled randomized circulant transform (SRCT)).

Let $x\in\mathbb{R}^{n}$ be a random vector, whose elements are i.i.d.
Rademacher random variables.

Also, let $P\in\mathbb{R}^{m\times n}$ be a random matrix in which each row
contains a 1 at a uniformly distributed coordinate and zeros elsewhere.

Let $G\in\mathbb{R}^{n\times n}$ be a circulant matrix (see Definition 2.10)
generated by $x$ and $D\in\mathbb{R}^{n\times n}$ be a diagonal matrix whose
diagonal elements are i.i.d. Rademacher random variables.

Then, the subsampled randomized circulant transform is defined as follows:
$S:=~{}\frac{1}{\sqrt{m}}PGD.$

######  Definition 2.12 (Tensor subsampled randomized circulant transform
(TensorSRCT)).

Let $x\in\mathbb{R}^{n}$ be a random vector, whose elements are i.i.d.
Rademacher random variables.

Also, let $P\in\mathbb{R}^{m\times n^{2}}$ be a random matrix in which each
row contains a 1 at a uniformly distributed coordinate and zeros elsewhere.

Let $G\in\mathbb{R}^{n\times n}$ be a circulant matrix (see Definition 2.10)
generated by $x$.

Let $D_{1}\in\mathbb{R}^{n\times n}$ and $D_{2}\in\mathbb{R}^{n\times n}$ be
two independent diagonal matrices whose diagonal elements are i.i.d.
Rademacher random variables.

Then, the tensor circulant transform
$T:\mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is defined as
follows: $T:=P\cdot(GD_{1}\otimes GD_{2}).$

######  Remark 2.13.

Similar to SRHT, we can utilize the fast Fourier transform with circulant
matrix. SRCT can be applied to a vector of length $n$ in $O(n\log n)$ time,
and TensorSRCT can be applied to $x\otimes y$ in $O(n\log n+m)$ time.

###  2.3 OSE property of dense sketches

An important condition for sketch-and-solve regressions is OSE. We focus
particularly on SRHT, SRCT, and their tensor variants.

######  Lemma 2.14 (Lemma 2.11 in [26]).

Let $S$ be an SRHT matrix defined in Definition 2.6. If
$m=O(\epsilon^{-2}d\log^{2}(nd/\delta))$, then $S$ is an
$(\epsilon,\delta,d,n)$-OSE.

######  Lemma 2.15 (Lemma 2.12 in [26]).

Let $S$ be a TensorSRHT matrix defined in Definition 2.8. If
$m=O(\epsilon^{-2}d\log^{3}(nd/\epsilon\delta))$, then $S$ is an
$(\epsilon,\delta,d,n^{2})$-OSE for degree-$2$ tensors.

SRCT requires more row count than SRHT due to the Gram $G^{\top}G$ is only
$I_{n}$ in expectation.

######  Lemma 2.16 (Informal version of Corollary C.7).

Let $S$ be an SRCT matrix defined in Definition 2.11. If
$m=O(\epsilon^{-2}d^{2}\log^{2}(nd/\delta))$, then $S$ is an
$(\epsilon,\delta,d,n)$-OSE.

######  Lemma 2.17 (Informal version of Corollary C.8).

Let $S$ be an TensorSRCT matrix defined in Definition 2.12. If
$m=O(\epsilon^{-2}d^{2}\log^{3}(nd/\delta))$, then $S$ is an
$(\epsilon,\delta,d,n^{2})$-OSE.

###  2.4 Probability tools

######  Lemma 2.18 (Khintchine’s inequality [16]).

Let $\sigma_{1},\cdots,\sigma_{n}$ be i.i.d. Rademacher random variables and
$z_{1},\cdots,z_{n}$ be real numbers. Then, there exists constants
$C,C^{\prime}>0$ such that

$\displaystyle\Pr[|\sum_{i=1}^{n}z_{i}\sigma_{i}|\geq
Ct\|z\|_{2}]\leq\exp(-C^{\prime}t^{2}).$

######  Lemma 2.19 (Hoeffding bound, [13]).

Let $Z_{1},\cdots,Z_{n}$ be independent, zero-mean random variables with
$Z_{i}\in[\alpha_{i},\beta_{i}]$. Then,

$\displaystyle\Pr[|\sum_{i=1}^{n}Z_{i}|>t]\leq$
$\displaystyle~{}2\exp(-\frac{t^{2}}{2\sum_{i=1}^{n}(\beta_{i}-\alpha_{i})^{2}}).$

######  Lemma 2.20 (Lemma 1 on page 1325 of Laurent and Massart [18] ).

Let $X\sim\mathcal{X}_{k}^{2}$ be a chi-squared distributed random variable
with $k$ degrees of freedom. Each one has zero means and $\sigma^{2}$
variance. Then,

$\displaystyle\Pr[X-k\sigma^{2}\geq(2\sqrt{kt}+2t)\sigma^{2}]\leq$
$\displaystyle~{}\exp{(-t)}$ $\displaystyle\Pr[k\sigma^{2}-X\geq
2\sqrt{kt}\sigma^{2}]\leq$ $\displaystyle~{}\exp{(-t)}$

######  Lemma 2.21 (Hanson-Wright inequality [14]).

Let $x\in\mathbb{R}^{n}$ denote a random vector with independent entries
$x_{i}$ with $\operatorname*{{\mathbb{E}}}[x_{i}]=0$ and $|x_{i}|\leq K$. Let
$A$ be an $n\times n$ matrix. Then, for every $t\geq 0$,

$\displaystyle~{}\Pr[|x^{\top}Ax-\operatorname*{{\mathbb{E}}}[x^{\top}Ax]|>t]$
$\displaystyle\leq$
$\displaystyle~{}2\cdot\exp{(-c\min\\{t^{2}/(K^{4}\|A\|_{F}^{2}),t/(K^{2}\|A\|)\\})}$

######  Lemma 2.22 (Matrix Chernoff bound, Theorem 2.2 in [33]).

Let $X$ be a finite set of positive-semidefinite matrices with dimension
$d\times d$. Suppose that $\max_{X\in\mathcal{X}}\lambda_{\max}(X)\leq B$.
Sample $\\{X_{1},\cdots,X_{n}\\}$ uniformly at random from $\mathcal{X}$
without replacement. We define $\mu_{\min}$ and $\mu_{\max}$ as follows:
$\mu_{\min}:=n\cdot\lambda_{\min}(\operatorname*{{\mathbb{E}}}_{X\sim\mathcal{X}}[X])$
and
$\mu_{\max}:=n\cdot\lambda_{\max}(\operatorname*{{\mathbb{E}}}_{X\sim\mathcal{X}}[X])$.
Then,

$\displaystyle\Pr[\lambda_{\min}(\sum_{i=1}^{n}X_{i})\leq$
$\displaystyle~{}(1-\delta)\mu_{\min}]\leq
d\cdot\exp{(-\delta^{2}\mu_{\min}/B)}$

for $\delta\in[0,1)$,

$\displaystyle~{}\Pr[\lambda_{\max}(\sum_{i=1}^{n}X_{i})\leq(1+\delta)\mu_{\max}]$
$\displaystyle\leq$ $\displaystyle~{}d\cdot\exp{(-\delta^{2}\mu_{\max}/(4B))}$

for $\delta\geq 0$.

##  3 $\ell_{\infty}$ guarantee via OCE

In this section, we present a sufficient condition for a sketching matrix to
give good $\ell_{\infty}$ guarantee: given a pair of fixed vectors $g,h$ such
that $g^{\top}h=0$, if the sketching matrix approximately preserves the inner
product with high probability, then it gives good $\ell_{\infty}$ guarantee
for regression.

######  Lemma 3.1 (Core lemma).

Let $A\in\mathbb{R}^{n\times d}$ be a fixed matrix. Let
$U\in\mathbb{R}^{n\times d}$ denote the orthonormal basis of $A$. Let
$S\in\mathbb{R}^{m\times n}$ be a sketching matrix that satisfies two
properties

  * •

$S$ is an $(0.1,\delta,d,n)$-$\mathsf{OSE}$ (with $\delta\in(0,0.1)$,
Definition 2.1).

  * •

$S$ is an $(\beta,\delta,n)$-$\mathsf{OCE}$ (with $\beta\geq 1$ and
$\delta\in(0,0.1)$, Definition 2.3).

For any fixed vectors $a\in\mathbb{R}^{d}$ and $b\in\mathbb{R}^{n}$ with
$U^{\top}b=0$, we have

$\displaystyle|a^{\top}(SA)^{\dagger}Sb|\lesssim$
$\displaystyle~{}\frac{\beta}{\sqrt{m}}\cdot\|a\|_{2}\cdot\|b\|_{2}\cdot\|\Sigma^{-1}\|$

holds with probability at least $1-\delta$.

###### Proof.

With probability 1, the matrix $SA\in\mathbb{R}^{m\times d}$ has linearly
independent columns.

Therefore, $(SA)^{\dagger}\in\mathbb{R}^{d\times m}$ is

$\displaystyle(SA)^{\dagger}=$
$\displaystyle~{}(A^{\top}S^{\top}SA)^{-1}A^{\top}S^{\top}$ $\displaystyle=$
$\displaystyle~{}(V\Sigma U^{\top}S^{\top}SU\Sigma V^{\top})^{-1}V\Sigma
U^{\top}S^{\top}$ $\displaystyle=$
$\displaystyle~{}(V^{\top})^{-1}\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}\Sigma^{-1}V^{-1}V\Sigma
U^{\top}S^{\top}$ $\displaystyle=$
$\displaystyle~{}V\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}U^{\top}S^{\top},$

where the first step follows from $SA\in\mathbb{R}^{m\times d}$ has full rank,
the second step follows from SVD on $A\in\mathbb{R}^{n\times d}$, the third
step follows from $(AB)^{-1}=B^{-1}A^{-1}$, and the last step follows from the
fact that $V$ is orthogonal based on the property of SVD.

For convenience, we define $x$ as follows:

$\displaystyle
x:=a^{\top}V\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}U^{\top}S^{\top}Sb.$

In the next few paragraphs, we will explain how to upper bound $|x|$ with high
probability.

Since $S$ is a $(0.1,\delta,d,n)$-OSE (Definition 2.1), we know

$\displaystyle\Pr[\|I-U^{\top}S^{\top}SU\|\leq 0.1]\geq 1-\delta.$

We condition on this event. It follows that

$\displaystyle~{}\|V\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}U^{\top}\|$
$\displaystyle=$
$\displaystyle~{}\|\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}U^{\top}\|$
$\displaystyle\leq$
$\displaystyle~{}\|\Sigma^{-1}\|\|(U^{\top}S^{\top}SU)^{-1}\|\|U^{\top}\|$
$\displaystyle\leq$ $\displaystyle~{}\|\Sigma^{-1}\|\cdot\frac{1}{1-0.1}\cdot
1$ $\displaystyle=$ $\displaystyle~{}O(\|\Sigma^{-1}\|),$

where the first step follows from that $V$ is a rotation, the second step
follows from sub-multiplicativity, and the third step follows from
$\|I-U^{\top}S^{\top}SU\|\leq 0.1$ and that $U$ is a rotation.

Hence, we have

$\displaystyle~{}\Pr[\|a^{\top}V\Sigma^{-1}(U^{\top}S^{\top}SU)^{-1}U^{\top}\|_{2}$
$\displaystyle=$
$\displaystyle~{}O(\|\Sigma^{-1}\|\cdot\|a\|_{2})]\geq~{}1-\delta.$ (3)

Let us define a vector $u\in\mathbb{R}^{n}$

$\displaystyle u:=$
$\displaystyle~{}U(U^{\top}S^{\top}SU)^{-1}\Sigma^{-1}V^{\top}a$

By the definition of OCE (Definition 2.3, we have that

$\displaystyle\Pr[|u^{\top}S^{\top}Sb-u^{\top}b|\leq\frac{\beta}{\sqrt{m}}\cdot\|u\|_{2}\|b\|_{2}]\leq$
$\displaystyle~{}1-\delta,$

where $U^{\top}b=0$ gives us $u^{\top}b=0$ and $u^{\top}S^{\top}Sb=x$.

Thus, the above bound translates to

$\displaystyle\Pr[|x|\leq
C\cdot\frac{\beta}{\sqrt{m}}\cdot\|\Sigma^{-1}\|\|a\|_{2}\|b\|_{2}]\geq$
$\displaystyle~{}1-\delta$ (4)

as desired. ∎

We are now ready to prove the $\ell_{\infty}$ guarantee given the inner
product bound of Lemma 3.1.

######  Theorem 3.2.

Suppose $A\in\mathbb{R}^{n\times d}$ has full column rank and
$b\in\mathbb{R}^{n}$. Let $S\in\mathbb{R}^{m\times n}$ be a sketching matrix
satisfying conditions in Lemma 3.1. For any fixed vector $a\in\mathbb{R}^{d}$,
we have

$\displaystyle|\langle a,x^{*}\rangle-\langle a,x^{\prime}\rangle|\lesssim$
$\displaystyle~{}\frac{\epsilon}{\sqrt{d}}\cdot\|a\|_{2}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|,$

holds with probability at least $1-\delta$, where
$x^{*}=\arg\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$ and
$x^{\prime}=\arg\min_{x\in\mathbb{R}^{d}}\|SAx-Sb\|_{2}$.

###### Proof.

Since $A$ has full column rank, we have that $x^{*}=A^{\dagger}b$. Similarly,
$SA$ has full column rank with probability 1, therefore
$x^{\prime}=(SA)^{\dagger}Sb$ and $(SA)^{\dagger}SA=I$. Thus, we have

$\displaystyle|\langle a,x^{*}\rangle-\langle a,x^{\prime}\rangle|=$
$\displaystyle~{}|\langle a,x^{*}-(SA)^{\dagger}Sb\rangle|$ $\displaystyle=$
$\displaystyle~{}|\langle a,(SA)^{\dagger}S(Ax^{*}-b)\rangle|$
$\displaystyle=$ $\displaystyle~{}|\langle
a,(SA)^{\dagger}S(AA^{\dagger}b-b)|$ $\displaystyle=$
$\displaystyle~{}|\langle((SA)^{\dagger}S)^{\top}a,(I-UU^{\top})b\rangle|$ (5)

where $U\in\mathbb{R}^{n\times d}$ is an orthonormal basis for $A$. It is
well-known that $I-UU^{\top}=U_{\perp}U_{\perp}^{\top}$ where
$U_{\perp}\in\mathbb{R}^{n\times(n-d)}$ is the orthonormal basis for the
orthogonal component of ${\rm span}(A)$. To maximize the above expression, we
shall let $b\in{\rm span}(U_{\perp})$ or equivalently, $U^{\top}b=0$. Thus,
bounding Eq. (3) is equivalent to consider

$\displaystyle|a^{\top}(SA)^{\dagger}Sb|\lesssim$
$\displaystyle~{}\frac{\beta}{\sqrt{m}}\cdot\|a\|_{2}\cdot\|b\|_{2}\cdot\|A^{\dagger}\|,$

the inequality holds with probability at least $1-2\delta$ by Lemma 3.1.
Finally, note that since $U^{\top}b=0$, we have that $Ax^{*}=0$ and we have
proved

$\displaystyle|\langle a,x^{*}\rangle-\langle a,x^{\prime}\rangle|\lesssim$
$\displaystyle~{}\frac{\epsilon}{\sqrt{d}}\cdot\|a\|_{2}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|.$

∎

Note that we only require the ${\sf OSE}$ with $\epsilon=O(1)$ and the
$\epsilon$ dependence follows from the row count of OCE.

###  3.1 High probability bound for OCE

In this section, we provide a unified framework for proving the high
probability bound of OCE. Our analysis utilizes the three dense sketching
matrices that can all be designed as first picking a set of fresh random
signs, then picking the sketching matrix according to the distribution.

We state the key assumptions on dense sketching matrices that are sufficient
for OCE property.

######  Assumption 3.3.

Let $S\in\mathbb{R}^{m\times n}$ be a dense sketching matrix satisfying the
following two assumptions:

  * •

Pairwise inner product bound:

$\displaystyle\Pr[\max_{i\neq j}|\langle
S_{*,i},S_{*,j}\rangle|\leq\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\geq$
$\displaystyle~{}1-\delta.$

  * •

Column norm bound:

$\displaystyle\Pr[|\|S_{*,i}\|_{2}^{2}-1|\leq\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\geq$
$\displaystyle~{}1-\delta,$

for all $i\in[n]$.

######  Lemma 3.4.

Let $S\in\mathbb{R}^{m\times n}$ be a dense sketching matrix meets Assumption
3.3. Let $h\in\mathbb{R}^{n}$ and $g\in\mathbb{R}^{n}$ be two fixed vectors.
Then, the following properties hold:

$\displaystyle|(g^{\top}S^{\top}Sh)-(g^{\top}h)|\leq$
$\displaystyle~{}\frac{\log^{1.5}(n/\delta)}{\sqrt{m}}\|g\|_{2}\|h\|_{2}$

holds with probability at least $1-\delta$.

###### Proof.

We can rewrite $(g^{\top}S^{\top}Sh)-(g^{\top}h)$ as follows:

$\displaystyle~{}(g^{\top}S^{\top}Sh)-(g^{\top}h)$ $\displaystyle=$
$\displaystyle~{}\sum_{i=1}^{n}\sum_{j\in[n]\setminus i}^{n}g_{i}h_{j}\langle
S_{*,i},S_{*,j}\rangle+\sum_{i=1}^{n}g_{i}h_{i}(\|S_{*,i}\|_{2}^{2}-1)$
$\displaystyle=$
$\displaystyle~{}\underbrace{\sum_{i=1}^{n}\sum_{j\in[n]\setminus
i}^{n}g_{i}h_{j}\langle\sigma_{i}\overline{S}_{*,i},\sigma_{j}\overline{S}_{*,j}\rangle}_{\texttt{off-
diag}}$ $\displaystyle+$
$\displaystyle~{}\underbrace{\sum_{i=1}^{n}g_{i}h_{i}(\|S_{*,i}\|_{2}^{2}-1)}_{\texttt{diag}},$

where the first step follows from the fact that $\sigma_{i}$’s are independent
Rademacher random variables and $S_{*,i}=\sigma_{i}\overline{S}_{*,i}$,
$\forall i\in[n]$, the second step follows from separating diagonal and off-
diagonal terms.

We will focus on bounding the quantity off-diag, as diag can be handled in a
rather simple fashion.

We define matrix $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^{n\times n}$
as follows:

$\displaystyle~{}A_{i,j}:=g_{i}h_{j}\cdot\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle,$
$\displaystyle~{}\forall i\in[n],j\in[n]$
$\displaystyle~{}B_{i,j}:=g_{i}h_{j}\cdot\max_{i^{\prime}\not=j^{\prime}}|\langle\overline{S}_{*,i^{\prime}},\overline{S}_{*,j^{\prime}}\rangle|,$
$\displaystyle~{}\forall i\in[n],j\in[n].$

We define $A^{\circ}\in\mathbb{R}^{n\times n}$ to be the matrix
$A\in\mathbb{R}^{n\times n}$ with removing diagonal entries.

By applying Hanson-Wright inequality (Lemma 2.21), we have

$\displaystyle~{}\Pr[|\sigma^{\top}A^{\circ}\sigma|>\tau]$ $\displaystyle\leq$
$\displaystyle~{}2\cdot\exp{(-c\cdot\min\\{\tau^{2}/\|A^{\circ}\|_{F}^{2},\tau/\|A^{\circ}\|\\})}$

We can upper bound $\|A^{\circ}\|$ and $\|A^{\circ}\|_{F}$.

$\displaystyle\|A^{\circ}\|\leq$ $\displaystyle~{}\|A^{\circ}\|_{F}$
$\displaystyle\leq$ $\displaystyle~{}\|A\|_{F}$ $\displaystyle\leq$
$\displaystyle~{}\|B\|_{F}$ $\displaystyle\leq$
$\displaystyle~{}\|g\|_{2}\cdot\|h\|_{2}\cdot\max_{i\not=j}|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|,$

where the first step follows from $\|\cdot\|\leq\|\cdot\|_{F}$, the second
step follows from the definition of $A^{\circ}$, the third step follows from
the definition of $A$ and $B$, and the fourth step follows from $B$ is rank 1
as $B=\max_{i\neq j}|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|\cdot
gh^{\top}$.

It remains to obtain a bound on $\max_{i\neq
j}|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|$. Note that for any
column $i,j$,

$\displaystyle|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|=$
$\displaystyle~{}|\langle\sigma_{i}\overline{S}_{*,i},\sigma_{j}\overline{S}_{*,j}\rangle|$
$\displaystyle=$ $\displaystyle~{}|\langle S_{*,i},S_{*,j}\rangle|,$

where the first step follows from the fact that random signs do not change the
magnitude of the inner product and the second step follows from the definition
of $S_{*,i}$ and $S_{*,j}$.

Since $S$ meets Assumption 3.3, we have that with probability at least
$1-\delta$,

$\displaystyle\max_{i\neq
j}|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|\leq$
$\displaystyle~{}\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}.$

Conditioning on the above event holds, we have that

$\displaystyle~{}\Pr[|\texttt{off-diag}|>\tau]$ $\displaystyle\leq$
$\displaystyle~{}2\cdot\exp(-c\cdot\frac{\tau}{\|g\|_{2}\cdot\|h\|_{2}\cdot\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}}),$

choosing $\tau=\|g\|_{2}\cdot\|h\|_{2}\cdot\log^{1.5}(n/\delta)/\sqrt{m}$, we
can show that

$\displaystyle\Pr[|\texttt{off-
diag}|\geq\|g\|_{2}\cdot\|h\|_{2}\frac{\log^{1.5}(n/\delta)}{\sqrt{m}}]\leq\Theta(\delta).$

To bound the term diag, note that due to Assumption 3.3, we have with
probability at least $1-\delta$,
$|\|S_{*,i}\|_{2}^{2}-1|\leq\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}$.

Conditioning on this event, we have

$\displaystyle|\texttt{diag}|\leq$
$\displaystyle~{}\max_{i\in[n]}|\|S_{*,i}\|_{2}^{2}-1|\cdot|g^{\top}h|$
$\displaystyle\leq$
$\displaystyle~{}\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}\cdot\|g\|_{2}\cdot\|h\|_{2},$

where the last step is by Cauchy-Schwartz. Note that $|\texttt{diag}|$ is
subsumed by $|\texttt{off-diag}|$.

Union bounding over all events, we have that

$\displaystyle~{}\Pr[|g^{\top}S^{\top}Sh-g^{\top}h|\geq\frac{\log^{1.5}(n/\delta)}{\sqrt{m}}\cdot\|g\|_{2}\cdot\|h\|_{2}]$
$\displaystyle\leq$ $\displaystyle~{}\Theta(\delta).\qed$

###  3.2 Inner product bound for SRHT and SRCT

We will show that SRHT and SRCT satisfy Assumption 3.3. Before proving the
pairwise inner product bound, we state a general property to characterize
these sketching matrices. This key property will be used in the later proof.

######  Definition 3.5 (Sign structure).

For any sketching matrix, we say it has “Sign structure” if the following
properties hold

  * •

$S_{k,i}\in\\{\pm\frac{1}{\sqrt{m}}\\}$, for all $k\in[m],i\in[n]$.

  * •

$S_{k,i}$ and $S_{k,j}$ are independent for any $i\neq j$.

  * •

$\operatorname*{{\mathbb{E}}}[S_{k,i}]=0$ for all $k\in[m]$ and $i\in[n]$.

######  Lemma 3.6.

Both SRHT and SRCT satisfy Definition 3.5.

###### Proof.

It follows from the definitions of two sketching matrices directly. ∎

######  Lemma 3.7 (SRHT and SRCT).

Let $S\in\mathbb{R}^{m\times n}$ be any sketching matrices that satisfy the
Definition 3.5. Then, we have

$\displaystyle\Pr[\max_{i\neq j}|\langle
S_{*,i},S_{*,j}\rangle|\geq\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\leq$
$\displaystyle~{}\Theta(\delta).$

###### Proof.

Fix a pair of indices $i\neq j$ and we define $X\in\mathbb{R}^{m\times 2}$ as
follows:

$\displaystyle X:=\begin{bmatrix}S_{*,i}&S_{*,j}\end{bmatrix}$

The Gram matrix is $X^{\top}X=\sum_{k=1}^{m}G_{k}$, where

$\displaystyle G_{k}=$
$\displaystyle~{}\begin{bmatrix}S_{k,i}&S_{k,j}\end{bmatrix}^{\top}\begin{bmatrix}S_{k,i}&S_{k,j}\end{bmatrix}$
$\displaystyle=$ $\displaystyle~{}\begin{bmatrix}S_{k,i}\\\
S_{k,j}\end{bmatrix}\begin{bmatrix}S_{k,i}&S_{k,j}\end{bmatrix}$
$\displaystyle=$ $\displaystyle~{}\begin{bmatrix}S_{k,i}^{2}&S_{k,i}S_{k,j}\\\
S_{k,i}S_{k,j}&S_{k,j}^{2}\end{bmatrix}$ $\displaystyle=$
$\displaystyle~{}\begin{bmatrix}\frac{1}{m}&S_{k,i}S_{k,j}\\\
S_{k,i}S_{k,j}&\frac{1}{m}\end{bmatrix}.$

where the first step follows from the definition of $G_{k}$, the second step
follows from rewriting $\begin{bmatrix}S_{k,i}&S_{k,j}\end{bmatrix}^{\top}$,
the third step follows from the definition of matrix multiplication, and the
last step follows from $S_{k,i}^{2}=1/m$ and $S_{k,j}^{2}=1/m$.

Note that $G_{k}$ has eigenvalues 0 and $\frac{2}{m}$, i.e.,

$\displaystyle\lambda_{1}(G_{k})=~{}2/m,~{}~{}~{}\lambda_{2}(G_{k})=~{}0.$

Since $S_{k,i}$ and $S_{k,j}$ are independent Rademacher random variables, we
have

$\displaystyle\operatorname*{{\mathbb{E}}}[S_{k,i}S_{k,j}]=\operatorname*{{\mathbb{E}}}[S_{k,i}]\cdot\operatorname*{{\mathbb{E}}}[S_{k,j}]=0.$

Thus, we know

$\displaystyle\operatorname*{{\mathbb{E}}}[G_{k}]=\begin{bmatrix}1/m&0\\\
0&1/m\end{bmatrix}.$ (6)

Consequently, we have

$\displaystyle\operatorname*{{\mathbb{E}}}[X^{\top}X]=$
$\displaystyle~{}\operatorname*{{\mathbb{E}}}[\sum_{k=1}^{m}G_{k}]=~{}m\cdot\operatorname*{{\mathbb{E}}}[G_{k}]$
$\displaystyle=$ $\displaystyle~{}m\cdot\begin{bmatrix}1/m&0\\\
0&1/m\end{bmatrix}$ $\displaystyle=$ $\displaystyle~{}\begin{bmatrix}1&0\\\
0&1\end{bmatrix},$

where the first step follows from the definition of $X^{\top}X$, the second
step follows from the fact that
$\operatorname*{{\mathbb{E}}}[ca]=c\operatorname*{{\mathbb{E}}}[a]$ for a
constant $c$, the third step follows from Eq. (6), and the last step follows
from simple algebra.

Let $\lambda_{i}(X^{\top}X)$ be the $i$-th eigenvalue of
$X^{\top}X\in\mathbb{R}^{2\times 2}$. By matrix Chernoff bound (Lemma 2.22
with $B=2/m$), for any $t>0$, we have

$\displaystyle\Pr[\forall i\in[2],|\lambda_{i}(X^{\top}X)-1|\geq t]\leq$
$\displaystyle~{}4\exp(-t^{2}m/2)$

This means with probability at least $1-4\exp(-t^{2}m/2)$, the eigenvalues of
$X^{\top}X$ are between $[1-t,1+t]$ and consequently, the eigenvalues of
$X^{\top}X-I_{2}$ are between $[-t,t]$. Let us choose
$t=O(\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}})$, we have

$\displaystyle\Pr[\|X^{\top}X-I_{2}\|\geq
C\cdot\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\leq$
$\displaystyle~{}\frac{\delta}{n^{2}}.$

The proof can be wrapped up by noting that

$\displaystyle X^{\top}X-I_{2}=$ $\displaystyle~{}\begin{bmatrix}0&\langle
S_{*,i},S_{*,j}\rangle\\\ \langle S_{*,i},S_{*,j}\rangle&0\end{bmatrix},$

the spectral norm of this matrix is $|\langle S_{*,i},S_{*,j}\rangle|$ and
union bound over all $n^{2}$ pairs of columns, we have

$\displaystyle\Pr[\max_{i\neq j}|\langle S_{*,i},S_{*,j}|\geq
C\cdot\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\leq\delta.$

∎

###  3.3 Column norm bound for SRHT and SRCT

In this section, we prove the column norm bound for SRHT and SRCT. In
particular, their columns are unit vectors. In Appendix D, we prove for random
Gaussian matrix, the squared column norm is $\chi^{2}_{m}$ random vriable that
concentrates around 1 with high probability.

######  Lemma 3.8 (SRHT and SRCT).

Let $S\in\mathbb{R}^{m\times n}$ be an SRHT matrix or SRCT matrix.

Then, for any $i\in[n]$, we have $\|S_{*,i}\|_{2}^{2}=~{}1.$

###### Proof.

The proof directly follows from the definition.

For SRHT, recall $S=PHD$, the column norm of $H$ is $\sqrt{n}$, and $D$ is a
random sign that does not change the norm. The matrix $P$ subsamples $m$ rows
and rescale each entry by $\sqrt{\frac{1}{m}}$. The (squared) column norm is
then 1.

For SRCT, the column norm of $G$ is $\sqrt{n}$ as well. Thus, by the same
argument, SRCT has its column vectors being units. ∎

##  4 Put things together

Now, we’re ready to present the proof for Theorem 1.1.

###### Proof of Theorem 1.1.

Using Lemma 2.14 (it shows SRHT gives OSE), we know if $m\geq
d\log^{2}(n/\delta)$, it gives $(O(1),\delta,n,d)$-OSE.

Using Lemma 3.7 (it shows SRHT gives OCE), we know
$\beta=O(\log^{1.5}(n/\delta))$.

Using Lemma 3.1 (it shows OSE \+ OCE implies our result), we need to choose

$\displaystyle
m\geq\epsilon^{-2}d\beta^{2}\geq\epsilon^{-2}d\log^{3}(n/\delta)$

Combining the above equation together, we have

$\displaystyle
m\geq~{}d\log^{2}(n/\delta)+\epsilon^{-2}d\log^{3}(n/\delta)\geq~{}\epsilon^{-2}d\log^{3}(n/\delta).$

∎

##  5 Conclusion

In this paper, we study the sketching-based regression algorithm with an
$\ell_{\infty}$ guarantee. We show that SRHT with
$m=\epsilon^{-2}d\log^{3}(n/\delta)$ rows provides the desired $\ell_{\infty}$
guarantee solution, improving upon the $\epsilon^{-2}d^{1+\gamma}$ rows for
$\gamma=\sqrt{\frac{\log\log n}{\log d}}$ of [22]. This is nearly-optimal up
to logarithmic factors. Our proof adapts the oblivious coordinate-wise
embedding property introduced in [31] in a novel way. We also greatly extends
the reach of $\ell_{\infty}$ guarantee to degree-2 Kronecker product
regression via TensorSRHT matrix.

In addition, we introduce the SRCT and TensorSRCT matrices. These matrices can
be applied in a fashion similar to SRHT, and they have similar OCE behaviors
as SRHT.

Our result provides an elegant way to integrate fast, sketching-based
regression solver for optimization process, in particular second-order
methods. The regression problem per iteration can be solved in time nearly-
linear in the input size, and the $\ell_{\infty}$ guarantee comes in handy
when analyzing convergence with approximate step. It also gives improved
generalization bound on approximate regression via SRHT [22].

## Appendix

#### Roadmap.

In Section A, we introduce the fundamental definitions and properties that we
will use in Appendix. In Section B, we analyze and develop the $\ell_{\infty}$
guarantee of Kronecker product regressions. In Section C, we introduce the
Strong JL Moment Property and prove that both Circulant Transform and Tensor
Circulant Transform satisfy this. In Section D, we focus on studying AMS,
random Gaussian, and SRHT and show that the inner product is bounded on any
pair of different columns of AMS, random Gaussian, and SRHT–dense sketching
matrices.

##  Appendix A Tools for matrices and probability

For matrix $A_{1}\in\mathbb{R}^{n_{1}\times d_{1}}$ and
$A_{2}\in\mathbb{R}^{n_{2}\times d_{2}}$, we use $A_{1}\otimes
A_{2}\in\mathbb{R}^{n_{1}n_{2}\times d_{1}d_{2}}$ to denote the matrix that
$(i_{1}-1)\cdot(n_{2})+i_{2},(j_{1}-1)d_{2}+j_{2}$ -th entry is
$(A_{1})_{i_{1},j_{1}}\cdot(A_{2})_{i_{2},j_{2}}$.

######  Lemma A.1 (Markov’s inequality).

If $X$ is a non-negative random variable and $a>0$. Then we have

$\displaystyle\Pr[X\geq a]\leq\operatorname*{{\mathbb{E}}}[X]/a.$

######  Definition A.2 (Sub-exponential distribution ([12])).

We say $X\in{\sf SubExp}(\sigma^{2},\alpha)$ with parameters $\sigma>0$,
$\alpha>0$ if:

$\displaystyle\operatorname*{{\mathbb{E}}}[e^{\lambda
X}]\leq\exp{(\lambda^{2}\sigma^{2}/2)},\forall|\lambda|<1/\alpha.$

######  Lemma A.3 (Tail bound for sub-exponential distribution ([12])).

Let $X\in{\sf SubExp}(\sigma^{2},\alpha)$ and
$\operatorname*{{\mathbb{E}}}[X]=\mu$. Then,

$\displaystyle\Pr[|X-\mu|\geq
t]\leq\exp{(-0.5\min\\{t^{2}/\sigma^{2},t/\alpha\\})}.$

######  Claim A.4.

For every matrix $A\in\mathbb{R}^{n_{1}\times
n_{2}},B\in\mathbb{R}^{n_{2}\times n_{3}},C\in\mathbb{R}^{d_{1}\times
d_{2}},D\in\mathbb{R}^{d_{2}\times d_{3}}$

$\displaystyle(A\cdot B)\otimes(C\cdot D)=(A\otimes C)\cdot(B\otimes D).$

##  Appendix B Kronecker product regression with $\ell_{\infty}$ guarantee

In this section, we study the $\ell_{\infty}$ guarantee of Kronecker product
regressions. Given two matrices $A_{1},A_{2}\in\mathbb{R}^{n\times d}$ and a
label vector $b\in\mathbb{R}^{n^{2}}$, the goal is to solve the regression
$\arg\min_{x\in\mathbb{R}^{d^{2}}}\|(A_{1}\otimes A_{2})x-b\|_{2}^{2}$. This
problem can be easily generalized to product of $q$ matrices and fast, input-
sparsity time algorithms have been studied in a line of works [10, 28, 9, 11,
24].

###  B.1 Main result

######  Theorem B.1 (Tensor version of Theorem 1.1).

Suppose $n\leq\exp(d)$ and matrix $A\in\mathbb{R}^{n^{2}\times d^{2}}$ and
vector $b\in\mathbb{R}^{n^{2}}$ are given, where $A=A_{1}\otimes A_{2}$ for
matrices $A_{1},A_{2}\in\mathbb{R}^{n\times d}$ and $b=b_{1}\otimes b_{2}$ for
vectors $b_{1},b_{2}\in\mathbb{R}^{n}$. Let $S\in\mathbb{R}^{m\times n^{2}}$
be a

  * •

tensor subsampled randomized Hadamard transform matrix (TensorSRHT) with
$m=\Theta(\epsilon^{-2}d^{2}\log^{3}(n/\delta))$ rows or

  * •

tensor subsampled randomized circulant transform matrix (TensorSRCT) with
$m=\Theta(\epsilon^{-2}d^{4}\log^{3}(n/\delta))$ rows.

For

$\displaystyle x^{\prime}=\arg\min_{x\in\mathbb{R}^{d^{2}}}\|SAx-Sb\|_{2}$

and

$\displaystyle x^{*}=\arg\min_{x\in\mathbb{R}^{d^{2}}}\|Ax-b\|_{2},$

and any fixed $a\in\mathbb{R}^{d^{2}}$,

$\displaystyle|\langle a,x^{*}\rangle-\langle
a,x^{\prime}\rangle|\leq\frac{\epsilon}{d}\cdot\|a\|_{2}\cdot\|Ax^{*}-b\|_{2}\cdot\|A^{\dagger}\|$

with probability $1-1/\operatorname{poly}(d)$.

###### Proof.

Recall that we require $(O(1),\delta,d,n)$-OSE and
$\beta=O(\log^{1.5}(n/\delta))$-OCE for it to give $\ell_{\infty}$ guarantee.

For OCE, it follows from Lemma B.3.

For TensorSRHT’s OSE, it follows from Lemma 2.15 and for TensorSRCT, it
follows from Corollary C.8. ∎

######  Remark B.2.

The slightly different guarantee follows from the small dimension becomes
$d^{2}$ instead of $d$. Let us discuss the utility of using these sketching
matrices for solving the regression. As discussed in Def. 2.8 and 2.12, each
column of $A_{1}\otimes A_{2}$ can be computed in $O(n\log n+m)$ time instead
of $n^{2}$, thus the total running time of applying $S$ to $A$ is
$O(nd^{2}\log n+\operatorname{poly}(d))$. Similarly, $Sb$ can be applied in
time $O(n\log n+\operatorname{poly}(d))$. The regression can then be solved in
$\widetilde{O}(nd^{2}+\operatorname{poly}(d))$ time. Prior works mainly focus
on input-sparsity sketches [10], importance sampling [9], iterative method
[11] or more complicated sketches that scale well to $q$ products and in
dynamic setting [24]. To the best of our knowledge, this is the first
$\ell_{\infty}$ guarantee for Kronecker product regression (with two
matrices).

###  B.2 Oblivious coordinate-wise embedding for TensorSRHT and TensorSRCT

######  Lemma B.3 (TensorSRHT and TensorSRCT, Tensor version of Lemma 3.7).

Let $S\in\mathbb{R}^{m\times n}$ be TensorSRHT or TensorSRCT. Then, $S$ is an
OCE with parameter $\beta=\log^{1.5}(n/\delta)$.

###### Proof.

To prove this result, we show that TensorSRHT and TensorSRCT satisfy
Definition 3.5.

For TensorSRHT, recall $S=\frac{1}{\sqrt{m}}P(HD_{1}\times HD_{2})$, since $H$
is Hadamard matrix and $D_{1},D_{2}$ are just diagonal matrices with random
signs. Thus, all entries of $HD_{1}\times HD_{2}$ are also in $\\{\pm 1\\}$.
As $P$ is a row sampling matrix and we rescale each entry by
$\frac{1}{\sqrt{m}}$. Thus, each entry of $S$ is in
$\\{\pm\frac{1}{\sqrt{m}}\\}$. For entries at the same row but two different
columns $i,j$, if $i$ is generated from two columns disjoint from $j$, then
it’s clear then are independent. Otherwise, suppose $i$ is generated from
columns $a,b$ and $j$ is generated from columns $a,c$ with $b\neq c$. Then it
is again independent, as the sign is completely determined by signs of $b$ and
$c$. Finally, we need to verify $\operatorname*{{\mathbb{E}}}[S_{k,i}]=0$,
this is trivially true since product of two random signs is still a random
sign. For TensorSRCT, the argument is exactly the same.

Now that both of these matrices satisfy Definition 3.5, we can use Lemma 3.7
to give a bound on pairwise inner product. The column norm bound is
automatically satisfied by definition. Thus, we can invoke Lemma 3.4 to wrap
up the proof. ∎

##  Appendix C SRCT and TensorSRCT: OSE via strong JL moment property

In this section, we prove that both SRCT and TensorSRCT are OSE’s. We prove
this property via the strong JL moment property [1]. This gives a worse row
count compared to that of SRHT and TensorSRHT. We believe that these two
family of distributions should have similar row count for an OSE and leave it
as a major open problem to close the gap between these two distributions.

###  C.1 Notations

To make the notation less heavy, we will use $\|X\|_{L^{t}}$ for the $t$-th
moment of a random variable $X$. This is formally defined below.

######  Definition C.1 ($t$-th moment).

For every integer $t\geq 1$ and any random variable $X\in\mathbb{R}$, we write

$\displaystyle\|X\|_{L^{t}}=\left(\operatorname*{{\mathbb{E}}}\left[|X|^{t}\right]\right)^{1/t}$

Note that

$\displaystyle\|X+Y\|_{L^{t}}\leq\|X\|_{L^{t}}+\|Y\|_{L^{t}}$

for any random variables $X$, $Y$ by the Minkowski inequality.

###  C.2 Strong JL moment property

We show that both SRCT (see Definition 2.11) and TensorSRCT (see Definition
2.12) satisfy the so-called _strong JL moment property_. Strong JL moment
property is one of the core properties that can show the sketching matrix has
subspace embedding property [25].

######  Definition C.2 (Strong JL moment property [1]).

For every $\epsilon,\delta\in[0,1]$, we say a distribution over random
matrices $S\in\mathbb{R}^{m\times n}$ has the Strong $(\epsilon,\delta)$-JL
Moment Property when

$\displaystyle\|\|Sx\|_{2}^{2}-1\|_{L^{t}}\leq\epsilon\sqrt{{t}/{\log(1/\delta)}}$

and

$\displaystyle\operatorname*{{\mathbb{E}}}\left[\|Sx\|_{2}^{2}\right]=1$

for all $x\in\mathbb{R}^{n}$, $\|x\|_{2}=1$ and every integer
$t\leq\log(1/\delta)$.

Given a distribution with strong JL moment property, it is well-known that
such distribution provides OSE.

######  Lemma C.3 (Lemma 11 of [1]).

Let $S\in\mathbb{R}^{m\times n}$ be a random matrix with
$(\epsilon/d,\delta)$-strong JL moment property (Def. C.2). Then, $S$ is also
an $(\epsilon,\delta,d,n)$-OSE (Def. 2.1).

To prove that SRCT (see Definition 2.11) and TensorSRCT (see Definition 2.12)
satisfy the strong JL moment property, we will do this by proving that a more
general class of matrices satisfies the strong JL moment property.

More precisely, let $k\in\operatorname*{\mathbb{Z}}_{>0}$ be a positive
integer and

$\displaystyle(D^{(i)})_{i\in[k]}\in\prod_{i\in[k]}\mathbb{R}^{n_{i}\times
n_{i}}$

be independent matrices, each with diagonal entries given by independent
Rademacher variables.

Let $n=\prod_{i\in[k]}n_{i}$ and $P\in\\{0,1\\}^{m\times n}$ be a random
sampling matrix in which each row contains exactly one uniformly distributed
nonzero element which has value one.

Then, we prove that the matrix

$\displaystyle S=\frac{1}{\sqrt{m}}PG\cdot(D_{1}\otimes\dots\otimes D_{k})$

satisfies the strong JL moment property, where $G$ is $n\times n$ circulant
matrix (see Definition 2.10) generated by a random vector whose elements are
Rademacher variables.

If $k=1$, then $S$ is just a SRCT (see Definition 2.11). If $k=2$, then $M$ is
a TensorSRCT (see Definition 2.12).

In order to prove this result we need a couple of lemmas. The first lemma can
be seen as a version of Khintchine’s Inequality (see Lemma 2.18) for higher
order chaos.

######  Lemma C.4 (Lemma 19 in [1]).

Let $t\geq 1$ and $k\in\mathbb{Z}_{>0}$. Let
$(\sigma^{(i)})_{i\in[k]}\in\prod_{i\in[k]}\mathbb{R}^{n_{i}}$ be independent
vectors each satisfying the Khintchine’s inequality (see Lemma 2.18):

$\displaystyle\|\langle\sigma^{(i)},x\rangle\|_{L^{t}}\leq C_{t}\|x\|_{2}$

for $t\geq 1$ and any vector $x\in\mathbb{R}^{d_{i}}$.

Let $(a_{i_{1},\ldots,i_{k}})_{i_{1}\in[n_{j}],\ldots,i_{k}\in[n_{k}]}$ be a
tensor in $\mathbb{R}^{n_{1}\times\cdots\times n_{k}}$. Then,

$\displaystyle\left\|\sum_{i_{1}\in[n_{1}],\ldots,i_{k}\in[n_{k}]}(\prod_{j\in[k]}\sigma_{i_{j}}^{(j)})a_{i_{1},\ldots,i_{k}}\right\|_{L^{t}}\leq
C_{t}^{k}(\sum_{i_{1}\in[n_{1}],\ldots,i_{k}\in[n_{k}]}a_{i_{1},\ldots,i_{k}}^{2})^{\frac{1}{2}},$

for $t\geq 1$.

Viewing $a\in\mathbb{R}^{n_{1}\times\ldots\times n_{k}}$ as a vector, then

$\displaystyle\|\langle\sigma^{(1)}\otimes\cdots\otimes\sigma^{(k)},a\rangle\|_{L^{t}}\leq
C_{t}^{k}\|a\|_{2},$

for $t\geq 1$.

###### Proof.

The proof will be by induction on $k$.

Base case: For $k=1$, the result is by the assumption that the vectors satisfy
Khintchine’s inequality.

Inductive case: Assume that the result is true for every value up to $k-1$.

Let

$\displaystyle
B_{i_{1},\ldots,i_{k-1}}=\sum_{i_{k}\in[d_{k}]}\sigma_{i_{k}}^{(k)}a_{i_{1},\ldots,i_{k}}.$
(7)

We then pull it out of the left hand term in the theorem:

$\displaystyle\|\sum_{i_{1}\in[n_{1}],\ldots,i_{k}\in[n_{k}]}(\prod_{j\in[k]}\sigma_{i_{j}}^{(j)})a_{i_{1},\ldots,i_{k}}\|_{L^{t}}=$
$\displaystyle~{}\|\sum_{i_{1}\in[n_{1}],\ldots,i_{k-1}\in[n_{k-1}]}(\prod_{j\in[k-1]}\sigma_{i_{j}}^{(j)})B_{i_{1},\ldots,i_{k-1}}\|_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}C_{t}^{k-1}\|(\sum_{i_{1}\in[d_{1}],\ldots,i_{k-1}\in[n_{k-1}]}B_{i_{1},\ldots,i_{k-1}}^{2})^{\frac{1}{2}}\|_{L^{t}}$
$\displaystyle=$
$\displaystyle~{}C_{t}^{k-1}\|\sum_{i_{1}\in[n_{1}],\ldots,i_{k-1}\in[n_{k-1}]}B_{i_{1},\ldots,i_{k-1}}^{2}\|_{L^{t/2}}^{\frac{1}{2}}$
$\displaystyle\leq$
$\displaystyle~{}C_{t}^{k-1}(\sum_{i_{1}\in[n_{1}],\ldots,i_{k-1}\in[n_{k-1}]}\|B_{i_{1},\ldots,i_{k-1}}^{2}\|_{L^{t/2}})^{\frac{1}{2}}$
$\displaystyle=$
$\displaystyle~{}C_{t}^{k-1}(\sum_{i_{1}\in[n_{1}],\ldots,i_{k-1}\in[n_{k-1}]}\|B_{i_{1},\ldots,i_{k-1}}\|_{L^{t}}^{2})^{\frac{1}{2}},$

where the first step follows from Eq. (7), the second step follows from the
inductive hypothesis, the third step follows from the definition of
$\|\cdot\|$, the fourth step follows from the triangle inequality, the fifth
step follows from the definition of $\|\cdot\|$.

It remains to bound

$\displaystyle\|B_{i_{1},\ldots,i_{k-1}}\|_{L^{t}}^{2}\leq
C_{t}^{2}\sum_{i_{k}\in[n_{k}]}a_{i_{1},\ldots,i_{k}}^{2}$

by Khintchine’s inequality, which finishes the induction step and hence the
proof. ∎

The next lemma we will be using is a type of Rosenthal inequality based on
first principles. It mixes large and small moments of random variables in an
intricate way. For completeness, we include a proof here.

######  Lemma C.5 (Properties of random variables with $t$-moment, Lemma 20 in
[1]).

There exists a universal constant $L$, such that, for $t\geq 1$ if
$X_{1},\dots,X_{k}$ are independent non-negative random variables with
$t$-moment, then

$\displaystyle\|\sum_{i\in[k]}(X_{i}-\operatorname*{{\mathbb{E}}}[X_{i}])\|_{L^{t}}\leq
L\cdot\big{(}\sqrt{t}\cdot\|\max_{i\in[k]}X_{i}\|^{1/2}_{L^{t}}\cdot(\sum_{i\in[k]}\operatorname*{{\mathbb{E}}}[X_{i}])^{1/2}+t\cdot\|\max_{i\in[k]}X_{i}\|_{L^{t}}\big{)}.$

###### Proof.

Throughout these calculations $L_{1},L_{2}$ and $L_{3}$ will be universal
constants.

$\displaystyle\|\sum_{i\in[k]}(X_{i}-\operatorname*{{\mathbb{E}}}[X_{i}])\|_{L^{t}}\leq$
$\displaystyle~{}L_{1}\|\sum_{i\in[k]}\sigma_{i}X_{i}\|_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}L_{2}\sqrt{t}\cdot\|\sum_{i\in[k]}X^{2}_{i}\|^{1/2}_{L^{t/2}}$
$\displaystyle\leq$
$\displaystyle~{}L_{2}\sqrt{t}\cdot\|\max_{i\in[k]}X_{i}\cdot\sum_{i\in[k]}X_{i}\|^{1/2}_{L^{t/2}}$
$\displaystyle\leq$
$\displaystyle~{}L_{2}\sqrt{t}\cdot\|\max_{i\in[k]}X_{i}\|^{1/2}_{L^{t}}\cdot\|\sum_{i\in[k]}X_{i}\|^{1/2}_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}L_{2}\sqrt{t}\cdot\|\max_{i\in[k]}X_{i}\|^{1/2}_{L^{t}}\cdot\Big{(}(\sum_{i\in[k]}\operatorname*{{\mathbb{E}}}[X_{i}])^{1/2}+L_{2}\|\sum_{i\in[k]}(X_{i}-\operatorname*{{\mathbb{E}}}[X_{i}])\|^{1/2}_{L^{t}}\Big{)}$
(8)

where the first step follows from symmetrization of $X_{i}$, the second step
follows from Khintchine’s inequality (see Lemma 2.18), the third step follows
from Non-negativity of $X_{i}$, the fourth step follows from Cauchy-Schwartz
inequality, and the last step follows from the triangle inequality.

Now, let $A,B,C$ be defined as follows:

$\displaystyle
C:=\|\sum_{i\in[k]}(X_{i}-\operatorname*{{\mathbb{E}}}[X_{i}])\|^{1/2}_{L^{t}},$
$\displaystyle
B:=L_{2}(\sum_{i\in[k]}\operatorname*{{\mathbb{E}}}[X_{i}])^{1/2},$

and

$\displaystyle A:=\sqrt{t}\|\max_{i\in[k]}X_{i}\|^{1/2}_{L^{t}}.$

Then, by rewriting Eq. (C.2), we have

$\displaystyle C^{2}\leq A(B+C).$

This implies $C$ is smaller than the largest of the roots of the quadratic.

Solving this quadratic inequality gives

$\displaystyle C^{2}\leq L_{3}(AB+A^{2}),$

which completes the proof. ∎

###  C.3 SRCT and TensorSRCT satisfy strong JL moment property

We can now prove that SRCT (see Definition 2.11) and TensorSRCT (see
Definition 2.12) have the strong JL moment property.

######  Theorem C.6.

There exists a universal constant $L$, such that, the following holds.

Let $k\in\operatorname*{\mathbb{Z}}_{>0}$. Let
$(D^{(i)})_{i\in[k]}\in\prod_{i\in[k]}\mathbb{R}^{n_{i}\times n_{i}}$ be
independent diagonal matrices with independent Rademacher variables.

We define $n:=\prod_{i\in[k]}n_{i}$, $D:=D_{1}\otimes D_{2}\otimes\dots\otimes
D_{k}\in\mathbb{R}^{n\times n}$ and $G:=G_{1}\otimes\ldots\otimes
G_{k}\in\mathbb{R}^{n\times n}$, where each $G_{i}\in\mathbb{R}^{n_{i}\times
n_{i}}$ is a circulant matrix generated by an independent Rademacher random
vector. Let $P\in\mathbb{R}^{m\times n}$ be a row sampling matrix that has
exactly one nonzero per row. Let $S:=PGD$.

Let $x\in\mathbb{R}^{n}$ be any vector with $\|x\|_{2}=1$ and $t\geq 1$.

Then,

$\displaystyle\left\|\frac{1}{m}\|PGDx\|_{2}^{2}-1\right\|_{L^{t}}\leq
L(\sqrt{\frac{tr^{k}}{m}}+\frac{tr^{k}}{m}),$

where $r=\max\\{t,\log m\\}$.

There exists a universal constant $C_{0}>1$, such that, by setting

$\displaystyle
m=\Omega(\epsilon^{-2}\log(1/\delta)\cdot(C_{0}\log(1/(\epsilon\delta)))^{k}),$

we get that $\frac{1}{\sqrt{m}}PGD$ has $(\epsilon,\delta)$-strong JL moment
property.

###### Proof.

Throughout the proof $C_{1}$, $C_{2}$ and $C_{3}$ will denote universal
constants.

For every $i\in[m]$, we let $P_{i}$ be the random variable that says which
coordinates the $i$-th row of $P$ samples.

We define the random variable

$\displaystyle Z_{i}:=M_{i}x=G_{P_{i}}Dx.$

We note that since the variables $(P_{i})_{i\in[m]}$ are independent, so the
variables $(Z_{i})_{i\in[m]}$ are conditionally independent given $D$, that
is, if we fix $D$, then $(Z_{i})_{i\in[m]}$ are independent.

Then, we could get the following inequality:

$\displaystyle~{}\|\frac{1}{m}\sum_{i\in[m]}Z^{2}_{i}-1\|_{L^{t}}$
$\displaystyle=$
$\displaystyle~{}\|(\operatorname*{{\mathbb{E}}}[(\frac{1}{m}\sum_{i\in[m]}Z^{2}_{i}-1)~{}\big{|}~{}D])^{1/t}\|_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}C_{1}\|\frac{\sqrt{t}}{m}\cdot(\operatorname*{{\mathbb{E}}}[(\max_{i\in[m]}Z^{2}_{i})~{}\big{|}~{}D])^{1/(2t)}\cdot(\sum_{i\in[m]}\operatorname*{{\mathbb{E}}}[Z^{2}_{i}~{}\big{|}~{}D])^{1/2}+\frac{t}{m}\cdot(\operatorname*{{\mathbb{E}}}[(\max_{i\in[m]}Z^{2}_{i})^{t}~{}\big{|}~{}D])^{1/t}\|_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}C_{1}\frac{\sqrt{t}}{m}\cdot\|(\operatorname*{{\mathbb{E}}}[(\max_{i\in[m]}Z^{2}_{i})~{}\big{|}~{}D])^{1/(2t)}\cdot(\sum_{i\in[m]}\operatorname*{{\mathbb{E}}}[Z^{2}_{i}~{}\big{|}~{}D])^{1/2}\|_{L^{t}}+C_{1}\frac{t}{m}\cdot\|\max_{i\in[m]}Z^{2}_{i}\|_{L^{t}}$
$\displaystyle\leq$
$\displaystyle~{}C_{1}\frac{\sqrt{t}}{m}\cdot\|\max_{i\in[m]}Z^{2}_{i}\|^{1/2}_{L^{t}}\cdot\|\sum_{i\in[m]}\operatorname*{{\mathbb{E}}}[Z^{2}_{i}~{}\big{|}~{}D]\|^{1/2}_{L^{t}}+C_{1}\frac{t}{m}\cdot\|\max_{i\in[m]}Z^{2}_{i}\|_{L^{t}}$

where the first step follows from Definition C.1, the second step follows from
Lemma C.5, the third step follows from triangle inequality, and the last step
follows from Cauchy-Schwartz inequality.

Note that each row of $G$ is generated by taking the tensor product of
independent Rademacher random vectors, we thus can view the row vector itself
as a length $n$ Rademacher random vector. Thus,

$\displaystyle\operatorname*{{\mathbb{E}}}[Z^{2}_{i}|D]=$
$\displaystyle~{}\sum_{\sigma\in\\{-1,+1\\}^{n}}p_{\sigma}\cdot(\langle
x,\sigma\rangle)^{2}$ $\displaystyle=$
$\displaystyle~{}\frac{(x_{1}+x_{2}+\cdots+x_{n})^{2}}{2^{n}}+\frac{(x_{1}+x_{2}+\cdots-
x_{n})^{2}}{2^{n}}+\dots+\frac{(-x_{1}-x_{2}-\cdots-x_{n})^{2}}{2^{n}}$
$\displaystyle=$ $\displaystyle~{}x^{2}_{1}+x^{2}_{2}+\cdots+x^{2}_{n}$
$\displaystyle=$ $\displaystyle~{}\|x\|^{2}_{2},$ (9)

where the first step follows from the definition of the expected value,
$\operatorname*{{\mathbb{E}}}[Z^{2}_{i}|D]$, the second step follows from
expanding all the $2^{n}$ possibilities, the third step follows from simple
algebra, and the last step follows from the definition of $\|\cdot\|_{2}^{2}$.

We could get that

$\displaystyle\sum_{i\in[m]}\operatorname*{{\mathbb{E}}}[Z_{i}^{2}~{}\big{|}~{}D]=$
$\displaystyle~{}\sum_{i\in[m]}\|x\|_{2}^{2}$ $\displaystyle=$
$\displaystyle~{}m,$

where the first step follows from Eq. (C.3) and the second step follows from
$\|x\|^{2}_{2}=1$.

To bound $\|\max_{i\in[m]}Z^{2}_{i}\|_{L^{t}}$, we could show

$\displaystyle\|Z^{2}_{i}\|_{L^{r}}=$
$\displaystyle~{}\|G_{P^{i}}Dx\|^{2}_{L^{2r}}$ $\displaystyle=$
$\displaystyle~{}\|Dx\|^{2}_{L^{2r}}$ $\displaystyle\leq$
$\displaystyle~{}r^{k}\|x\|^{2}_{2}.$

where the first step follows from the definition of $Z_{i}$, the second step
follows from each row of $G$ is independent Rademacher vector, therefore
$\operatorname*{{\mathbb{E}}}[G^{\top}G]=I$, and the last step follows from
Lemma C.4.

We then bound the maximum using a sufficiently high-order sum:

$\displaystyle\|\max_{i\in[m]}Z^{2}_{i}\|_{L^{t}}\leq$
$\displaystyle~{}\|\max_{i\in[m]}Z^{2}_{i}\|_{L^{r}}$ $\displaystyle\leq$
$\displaystyle~{}(\sum_{i\in[m]}\|Z^{2}_{i}\|^{r}_{L^{r}})^{1/r}$
$\displaystyle\leq$ $\displaystyle~{}m^{1/r}r^{k}\|x\|_{2}^{2}\leq er^{k},$

where the first step follows from Definition C.1, the second step follows from
$Z^{2}_{i}$ is non-negative, and the last step follows from $r\geq\log m$.

This gives us that

$\displaystyle\|\frac{1}{m}\sum_{i\in[m]}Z^{2}_{i}-\|x\|_{2}^{2}\|_{L^{t}}\leq
C_{2}\sqrt{\frac{tr^{k}}{m}}+C_{2}\frac{tr^{k}}{m}$ (10)

which finishes the first part of the proof.

We want to choose $m$ as follows

$\displaystyle
m=16C^{2}_{2}\epsilon^{-2}\cdot\log(1/\delta)\cdot(C_{3}\log(1/(\delta\epsilon)))^{k}.$

According to the above choice of $m$, we know following condition for $r$ is
holding

$\displaystyle r\leq C_{3}\log(1/(\delta\epsilon)).$

Hence,

$\displaystyle m\geq 16C^{2}_{2}\epsilon^{-2}\cdot\log(1/\delta)\cdot r^{k}.$

For all $1\leq t\leq\log(1/\delta)$, we then get that

$\displaystyle\|\|PGDx\|_{2}^{2}-1\|_{L^{t}}\leq$
$\displaystyle~{}C_{2}\sqrt{\frac{tr^{k}}{m}}+C_{2}\frac{tr^{k}}{m}$
$\displaystyle\leq$
$\displaystyle~{}C_{2}(\frac{tr^{k}}{16C_{2}^{2}\epsilon^{-2}\log(1/\delta)r^{k}})^{1/2}+C_{2}\frac{tr^{k}}{16C^{2}_{2}\epsilon^{-2}\log(1/\delta)r^{k}}$
$\displaystyle\leq$
$\displaystyle~{}0.5\epsilon\sqrt{t/\log(1/\delta)}+0.5\epsilon^{2}t/\log(1/\delta)$
$\displaystyle\leq$ $\displaystyle~{}\epsilon\sqrt{{t}/{\log(1/\delta)}}.$

where the first step follows from Eq. (10), and the second step follows from
choice of $m$, the third step follows from simple algebra, and the last step
follows from $\epsilon^{2}\leq\epsilon$ and
$t/\log(1/\delta)\sqrt{t/\log(1/\delta)}$ (since $t/\log(1/\delta)\in(0,1)$) .

This finishes the proof. ∎

As two corollaries, we have SRCT and TensorSRCT are OSE’s with $d^{2}$ rows,
instead of $d$ rows.

######  Corollary C.7 (SRCT is an OSE).

Let $S\in\mathbb{R}^{m\times n}$ be an SRCT matrix with
$m=\Theta(\epsilon^{-2}d^{2}\log^{2}(n/\epsilon\delta))$, then $S$ is an
$(\epsilon,\delta,d,n)$-OSE.

###### Proof.

The proof follows from combining Lemma C.3 and Theorem C.6 with $k=1$. ∎

######  Corollary C.8 (TensorSRCT is an OSE).

Let $S\in\mathbb{R}^{m\times n}$ be a TensorSRCT matrix with
$m=\Theta(\epsilon^{-2}d^{2}\log^{3}(n/\epsilon\delta))$, then $S$ is an
$(\epsilon,\delta,d,n^{2})$-OSE.

###### Proof.

The proof follows from combining Lemma C.3 and Theorem C.6 with $k=2$. ∎

##  Appendix D Gaussian and AMS

In this section, we prove that both random Gaussian matrices and AMS matrices
satisfy OCE with good parameter $\beta$. Combining with the fact that they are
OSE’s, one can derive $\ell_{\infty}$ guarantee for them.

###  D.1 OSE property of random Gaussian and AMS

The OSE property for these two distributions are folklore. For a proof for
them, see, e.g., [34].

######  Lemma D.1.

Let $S$ be a random Gaussian matrix defined in Def. 2.4. If
$m=\Theta(\epsilon^{-2}(d+\log(d/\delta)))$, then $S$ is an
$(\epsilon,\delta,d,n)$-OSE.

######  Lemma D.2.

Let $S$ be an AMS matrix defined in Def. 2.5. If
$m=\Theta(\epsilon^{-2}d\log^{2}(n/\delta))$, then $S$ is an
$(\epsilon,\delta,d,n)$-OSE.

###  D.2 OCE property of random Gaussian and AMS

In this section, we prove the OCE property of random Gaussian and AMS. We
start with the pairwise inner product bound for these two distributions. For
column norm bound, AMS has unit columns and we will prove for random Gaussian.

######  Lemma D.3 (Gaussian pairwise inner product bound, Lemma B.18 in [31]).

Let $S\in\mathbb{R}^{m\times n}$ be a random Gaussian matrix (Definition 2.4).

Then, we have:

$\displaystyle\Pr[\max_{i\not=j}|\langle S_{*,i},S_{*,j}\rangle|\geq
C\cdot\frac{\sqrt{\log{(n/\delta)}}}{\sqrt{m}}]\leq\Theta(\delta).$

###### Proof.

Note for $i\not=j$, $S_{*,i},S_{*,j}\sim\mathcal{N}(0,\frac{1}{m}I_{m})$ are
two independent Gaussian vectors. Let $z_{k}=S_{k,i}S_{k,j}$ and $z=\langle
S_{*,i},S_{*,j}\rangle$.

Then, we have for any $|\lambda|\leq m/2$,

$\displaystyle\operatorname*{{\mathbb{E}}}[e^{\lambda
z_{k}}]=\frac{1}{\sqrt{1-\lambda^{2}/m^{2}}}\leq\exp{(\lambda^{2}/m^{2})},$

where the first step follows from
$z_{k}=\frac{1}{4}(S_{k,i}+S_{k,j})^{2}+\frac{1}{4}(S_{k,i}-S_{k,j})^{2}=\frac{m}{2}(Q_{1}-Q_{2})$
where $Q_{1},Q_{2}\sim\chi_{1}^{2}$, and
$\operatorname*{{\mathbb{E}}}[e^{\lambda Q}]=\frac{1}{\sqrt{1-2\lambda}}$ for
any $Q\sim\chi_{1}^{2}$.

This implies $z_{k}\in{\sf SubExp}(2/m^{2},2/m)$ is a sub-exponential random
variable. Here ${\sf SubExp}$ is the shorthand of sub-exponential random
variable.

Thus, we have

$\displaystyle z=\sum_{k=1}^{m}z_{k}\in{\sf SubExp}(2/m,2/m),$

by sub-exponential concentration Lemma A.3, we have

$\displaystyle\Pr[|z|\geq t]\leq 2\exp{(-mt^{2}/4)}$

for $0<t<1$. Picking $t=\sqrt{\log{(n^{2}/\delta)/m}}$, we have

$\displaystyle\Pr[|\langle S_{*,i},S_{*,j}\rangle|\geq
C\cdot\frac{\sqrt{\log{(n/\delta)}}}{\sqrt{m}}]\leq\delta/n^{2}.$

Taking the union bound over all $(i,j)\in[n]\times[n]$ and $i\not=j$, we
complete the proof. ∎

######  Lemma D.4 (AMS pairwise inner product bound).

Let $S\in\mathbb{R}^{m\times n}$ be an AMS matrix (Definition 2.5. Let
$\\{\sigma_{i}\\}_{i\in[n]}$ be independent Rademacher random variables and
$\overline{S}\in\mathbb{R}^{m\times n}$ with
$\overline{S}_{*,i}=\sigma_{i}S_{*,i}$, $\forall i\in[n]$.

Then, we have:

$\displaystyle\Pr[\max_{i\not=j}|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|\geq\frac{\sqrt{\log{(n/\delta)}}}{\sqrt{m}}]\leq\Theta(\delta)$

###### Proof.

Note for any fixed $i\not=j$, $\overline{S}_{*,i}$ and $\overline{S}_{*,j}$
are independent. By Hoeffding inequality (Lemma 2.19), we have

$\displaystyle~{}\Pr[|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|\geq
t]$ $\displaystyle\leq$
$\displaystyle~{}2\exp{(-\frac{2t^{2}}{\sum_{i=1}^{m}(\frac{1}{m}-(-\frac{1}{m}))^{2}})}$
$\displaystyle\leq$ $\displaystyle~{}2e^{-t^{2}m/2},$

where the second step follows from simple algebra ($m\cdot 1/m^{2}=1/m$).

Choosing $t=\sqrt{2\log{(2n^{2}/\delta)}}/\sqrt{m}$, we have

$\displaystyle\Pr[|\langle\overline{S}_{*,i},\overline{S}_{*,j}\rangle|\geq\sqrt{2\log{(2n^{2}/\delta)}}/\sqrt{m}]\leq\frac{\delta}{n^{2}},$

union bound over all $n^{2}$ pairs of columns gives the desired result. ∎

######  Lemma D.5 (Gaussian column norm bound).

Let $S\in\mathbb{R}^{m\times n}$ be a random Gaussian matrix.

Then, for any $i\in[n]$, we have

$\displaystyle\Pr[|\|S_{*,i}\|_{2}^{2}-1|\geq\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\leq$
$\displaystyle~{}\Theta(\delta).$

###### Proof.

For any column $S_{*,i}$, note that $\|S_{*,i}\|_{2}^{2}\sim\chi_{m}^{2}$,
each one with zero mean and variance $\frac{1}{m}$.

By Lemma 2.20, we have

$\displaystyle\Pr[|\|S_{*,i}\|_{2}^{2}-1|\geq 2\frac{\sqrt{t}}{\sqrt{m}}]\leq$
$\displaystyle~{}2\exp(-t).$

Setting $t=\log(n/\delta)$, we have

$\displaystyle\Pr[|\|S_{*,i}\|_{2}^{2}-1|\geq
C\cdot\frac{\sqrt{\log(n/\delta)}}{\sqrt{m}}]\leq$ $\displaystyle~{}\delta/n,$

the proof is concluded by union bounding over all $n$ columns. ∎

We conclude random Gaussian and AMS are OCE’s.

######  Lemma D.6 (Gaussian OCE).

Let $S\in\mathbb{R}^{m\times n}$ be a random Gaussian matrix, then $S$ is a
$(\log^{1.5}(n/\delta),\delta,n)$-OCE.

###### Proof.

By Lemma D.3 and Lemma D.5, we know both pairwise inner product bound and
column norm bound hold and thus, by Lemma 3.4, $S$ satisfies the desired OCE
property. ∎

######  Lemma D.7 (AMS OCE).

Let $S\in\mathbb{R}^{m\times n}$ be an AMS matrix, then $S$ is a
$(\log^{1.5}(n/\delta),\delta,n)$-OCE.

###### Proof.

The proof is similar to Lemma D.6. The column norm bound follows from
definition. ∎

## References

  * AKK+ [20] Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh.  Oblivious sketching of high-degree polynomial kernels.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 141–160. SIAM, 2020.
  * AMS [96] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20–29, 1996.
  * ANW [14] Haim Avron, Huy Nguyen, and David Woodruff.  Subspace embeddings for the polynomial kernel.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2258–2266. 2014.
  * BPSW [21] Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein.  Training (overparametrized) neural networks in near-linear time.  In ITCS, 2021.
  * CCFC [02] Moses Charikar, Kevin Chen, and Martin Farach-Colton.  Finding frequent items in data streams.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 693–703. Springer, 2002.
  * Coh [16] Michael B Cohen.  Nearly tight oblivious subspace embeddings by trace inequalities.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 278–287. SIAM, 2016.
  * CSWZ [23] Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, and Samson Zhou.  Optimal algorithms for linear algebra in the current matrix multiplication time.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.
  * CW [13] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference(STOC), pages 81–90, 2013.
  * DJS+ [19] Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff.  Optimal sketching for kronecker product regression and low rank approximation.  Advances in neural information processing systems, 32, 2019.
  * DSSW [18] Huaian Diao, Zhao Song, Wen Sun, and David Woodruff.  Sketching for kronecker product regression and p-splines.  In International Conference on Artificial Intelligence and Statistics, pages 1299–1308. PMLR, 2018.
  * FFG [22] Matthew Fahrbach, Thomas Fu, and Mehrdad Ghadiri.  Subquadratic kronecker regression with applications to tensor decomposition.  In Thirty-Sixth Conference on Neural Information Processing Systems, NeurIPS’22, 2022.
  * FKZ [11] Sergey Foss, Dmitry Korshunov, and Stan Zachary.  An Introduction to Heavy-Tailed and Subexponential Distributions.  Springer series in operations research. Springer, New York, NY, 1st ed edition, 2011.
  * Hoe [63] Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In Journal of the American Statistical, pages 13–30. 1963.
  * HW [71] David Lee Hanson and Farroll Tim Wright.  A bound on tail probabilities for quadratic forms in independent random variables.  The Annals of Mathematical Statistics, 42(3):1079–1083, 1971.
  * JSWZ [21] Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang.  A faster algorithm for solving general lps.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 823–832, 2021.
  * Khi [23] Aleksandr Khintchine.  Über dyadische brüche.  Mathematische Zeitschrift, 18(1):109–116, 1923.
  * LDFU [13] Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar.  Faster ridge regression via the subsampled randomized hadamard transform.  In Advances in neural information processing systems (NIPS), pages 369–377, 2013.
  * LM [00] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  Annals of Statistics, pages 1302–1338, 2000.
  * LS [14] Yin Tat Lee and Aaron Sidford.  Path finding methods for linear programming: Solving linear programs in ${O}(\sqrt{rank})$ iterations and faster algorithms for maximum flow.  In 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 424–433, 2014.
  * LSZ [19] Yin Tat Lee, Zhao Song, and Qiuyi Zhang.  Solving empirical risk minimization in the current matrix multiplication time.  In Conference on Learning Theory, pages 2140–2157. PMLR, 2019.
  * NN [13] Jelani Nelson and Huy L Nguyên.  Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 117–126. IEEE, 2013.
  * PSW [17] Eric Price, Zhao Song, and David P Woodruff.  Fast regression with an $\ell_{\infty}$ guarantee.  In ICALP, 2017.
  * QSZZ [23] Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo.  An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization.  In AISTATS, 2023.
  * RSZ [22] Aravind Reddy, Zhao Song, and Lichen Zhang.  Dynamic tensor product regression.  In Thirty-Sixth Conference on Neural Information Processing Systems, NeurIPS’22, 2022.
  * Sar [06] Tamas Sarlos.  Improved approximation algorithms for large matrices via random projections.  In 2006 47th annual IEEE symposium on foundations of computer science (FOCS), pages 143–152. IEEE, 2006.
  * SWYZ [21] Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang.  Fast sketching of polynomial kernels of polynomial degree.  In International Conference on Machine Learning, pages 9812–9823. PMLR, 2021.
  * SWZ [16] Zhao Song, David Woodruff, and Huan Zhang.  Sublinear time orthogonal tensor decomposition.  Advances in Neural Information Processing Systems, 29, 2016.
  * SWZ [19] Zhao Song, David P Woodruff, and Peilin Zhong.  Relative error tensor low rank approximation.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2772–2789. SIAM, 2019.
  * SXYZ [22] Zhao Song, Zhaozhuo Xu, Yuanyuan Yang, and Lichen Zhang.  Accelerating frank-wolfe algorithm using low-dimensional and adaptive data structures.  arXiv preprint arXiv:2207.09002, 2022.
  * SXZ [22] Zhao Song, Zhaozhuo Xu, and Lichen Zhang.  Speeding up sparsification using inner product search data structures.  arXiv preprint arXiv:2204.03209, 2022.
  * SY [21] Zhao Song and Zheng Yu.  Oblivious sketching-based central path method for solving linear programming problems.  In 38th International Conference on Machine Learning (ICML), 2021\.
  * SZZ [21] Zhao Song, Lichen Zhang, and Ruizhe Zhang.  Training multi-layer over-parametrized neural network in subquadratic time.  arXiv preprint arXiv:2112.07628, 2021.
  * Tro [10] Joel A. Tropp.  Improved analysis of the subsampled randomized hadamard transform.  2010\.
  * Woo [14] David P Woodruff.  Sketching as a tool for numerical linear algebra.  Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
  * WZ [20] David P Woodruff and Amir Zandieh.  Near input sparsity time kernel embeddings via adaptive sampling.  In ICML, 2020.
  * WZ [22] David Woodruff and Amir Zandieh.  Leverage score sampling for tensor product matrices in input sparsity time.  In Proceedings of the 39th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2022.