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

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:

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:

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):

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]: ¹¹1We will later refer the following property as $\ell_{\infty}$ guarantee.

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.

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})$.

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.

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

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