Active Regression - Randomized Numerical Linear Algebra with Examples

The active regression problem is a variant of the standard linear regression problem.

Most of the algorithms presented in Chapter 4 on linear regression require reading the entire vector $\vec{b}$ . However, in the active regression problem, we measure cost by the number of entries of $\vec{b}$ that get observed, so such methods are off the table.

This section outlines basic sampling-based approaches to the active regression problem that aim to use a small number of entry evaluations.

Leverage score sampling¶

Recall $\Call{leverage-dist}(\vec{A})$ is the distribution that corresponds to sampling an index from $\{1, \ldots, n\}$ proportional to the Leverage-scores $(\ell_1, \ldots, \ell_n)$ of $\vec{A}$ .

One can apply Algorithm 4.3 (sketch-and-solve) using the Leverage-score Sketch. Theorem 2.9 guarantees that the leverage-score sketch is a subspace embedding for $\vec{A}$ . However, we cannot immediately apply the analysis techniques used in the analysis of Sketch and Solve, because these require that the sketch is a subspace embedding for $[\vec{A},\vec{b}]$ . The standard approach to the analysis is to make use of the approximate matrix multiplication guarantee; see for example Raphael’s wiki.

Here, we describe and analyze a slight modification of this algorithm, which admits a simple analysis of the mean squared error.

Note that the rejection step does not require any additional evaluations of $\vec{b}$ , since it only requires access to $\vec{A}$ . Hence, it does not impact the number of entries of $\vec{b}$ that are observed. In many applications, an orthonormal basis $\vec{U}$ is known a priori, so the rejection step can be performed with very little overhead.

Proof

Let $\vec{U}$ be an orthonormal basis for $\range(\vec{A})$ and let $\vec{r} = \vec{b} - \vec{A}\vec{x}^*$ be the optimal residual, which is orthogonal to $\range(\vec{A})$ .

Since $\vec{A}(\vec{x} - \vec{x}^*)$ ranges over $\range(\vec{A})$ as $\vec{x}$ ranges over $\R^d$ , we may write the fitted-value error of the sketched solution as $\vec{A}(\widehat{\vec{x}} - \vec{x}^*) = \vec{U}\vec{w}$ . Because $\vec{S}(\vec{b} - \vec{A}\vec{x}) = \vec{S}(\vec{r} - \vec{U}\vec{w})$ , the first-order optimality condition $\vec{U}^\T\vec{S}^\T\vec{S}(\vec{r} - \vec{U}\vec{w}) = \vec{0}$ for the sketched least-squares problem gives

\vec{w} = (\vec{U}^\T\vec{S}^\T\vec{S}\vec{U})^{-1}\vec{U}^\T\vec{S}^\T\vec{S}\vec{r}.

Since $\vec{r} \perp \range(\vec{A})$ , the Pythagorean theorem gives

\|\vec{b} - \vec{A}\widehat{\vec{x}}\|^2 = \|\vec{r}\|^2 + \|\vec{A}(\widehat{\vec{x}} - \vec{x}^*)\|^2 = \|\vec{r}\|^2 + \|\vec{w}\|^2,

so it suffices to show that $\EE[\|\vec{w}\|^2] \leq \varepsilon \|\vec{r}\|^2$ .

Observe that

\EE[\|\vec{w}\|^2] \leq \EE[\|(\vec{U}^\T\vec{S}^\T\vec{S}\vec{U})^{-1} \|^2 \| \vec{U}^\T\vec{S}^\T\vec{S}\vec{r} \|^2] \leq O(1) \EE[\| \vec{U}^\T\vec{S}^\T\vec{S}\vec{r} \|^2],

where we have used that, $\vec{S}$ is a subspace embedding for $\vec{A}$ with constant distortion and Theorem 2.1.

Let $\vec{S}'$ be a leverage-score sketching matrix, and let $F$ be the event that $\vec{S}'$ is a subspace embedding for $\vec{A}$ with distortion $1/2$ . Then, since rejection sampling outputs a sketch $\vec{S}$ that is distributed as $\vec{S}'$ conditioned on $F$ , we have

\EE[\| \vec{U}^\T\vec{S}^\T\vec{S}\vec{r} \|^2] = \EE[\| \vec{U}^\T(\vec{S}')^\T\vec{S}'\vec{r} \|^2 \mid F].

At first glance, it seems that it may be hard to analyze this conditional expectation, since the distribution of $\vec{S}'|F$ is probably super complicated. Fortunately, there is a simple trick to get around this.^[1] Note that for any random variable $X$ and event $F$ , $\EE[X \mathbb{1}_F] = \EE[X \mathbb{1}_F | F]\PP[F] + \EE[X \mathbb{1}_F | \neg F]\PP[\neg F] = \EE[X | F]\PP[F]$ , and hence

\EE[X \mid F] = \frac{\EE[X \mathbb{1}_F]}{\PP[F]} \leq \frac{\EE[X]}{\PP[F]},

where the inequality follows from the fact that $\mathbb{1}_F \leq 1$ .

This implies that

\EE[\| \vec{U}^\T(\vec{S}')^\T\vec{S}'\vec{r} \|^2 \mid F] \leq \frac{\EE[\| \vec{U}^\T(\vec{S}')^\T\vec{S}'\vec{r} \|^2]}{\PP[F]}.

The numerator is the error of the approximate matrix multiplication estimator (note $\vec{U}^\T\vec{r} = \vec{0}$ ). Specifically, leverage score sampling uses probabilities $p_i = \ell_i / d \propto \|\vec{e}_i^\T\vec{U}\|^2$ , so the variance bound Theorem 7.1 gives

\begin{align*} \EE\left[\|\vec{U}^\T\vec{S}^\T\vec{S}\vec{r}\|^2\right] &= \EE\left[\|\vec{U}^\T\vec{r} - \vec{U}^\T\vec{S}^\T\vec{S}\vec{r}\|^2\right] \\&= \frac{1}{k}\left(\sum_{i=1}^n \frac{d}{\ell_i}\,\ell_i\, r_i^2 - \|\vec{U}^\T\vec{r}\|^2\right) \\&= \frac{d}{k}\|\vec{r}\|^2. \end{align*}

(7.4)

The denominator can be analyzed using the matrix Bernstein inequality, which yields $\PP[F] \geq 1/2$ provided $k = O(d\log d)$ . For a proof, see Rapahel’s wiki. This also implies that the number of rejections is a geometric random variable with mean at most 2.

Footnotes¶

I learned this trick from a related proof generated by Claude. I was super happy to learn about it, because I always found the typical subspace embedding + approximate matrix multiplication analysis for the sketch-and-solve algorithm unsatisfying, because of the union bound. In particular, in this book, almost all the bounds are expectation bounds, but I only had a probability bound for active regression.
↩