Reverse Iterative Volume Sampling for Linear Regression

Michal Derezinski, Manfred K. Warmuth

TL;DR

Acquiring labels in regression problems can be expensive, but querying the right subset of points can yield near-optimal models. This paper demonstrates that volume sampling allows a learner to achieve an expected loss within a factor of $d+1$ of the optimal least squares model using just $d$ responses (where $d$ is the feature dimension), while yielding a strictly unbiased estimator of the true model weights. Furthermore, the authors introduce reverse iterative sampling, deriving the first nearly linear-time ($O(nd^2)$) algorithm for volume sampling and extending it to regularized ridge regression.

What Problem Does This Paper Address?

In pool-based active learning and experimental design, a learner has access to $n$ feature vectors $x_i \in \mathbb{R}^d$ but must pay to observe their target responses $y_i$. The objective is to select a small subset $S \subseteq \{1..n\}$ of size $s \ll n$, observe only their labels $y_S$, and fit a linear weight vector that minimizes the total squared loss over the entire dataset.

Standard approaches face major hurdles when the sample budget is small:

  1. Deterministic row selection cannot guarantee a multiplicative error bound better than $n/d$ in the worst case.
  2. Independent (i.i.d.) sampling methods (such as leverage score sampling) suffer from the coupon collector's problem: they need $\Omega(d \log d)$ samples just to ensure the sampled submatrix has full rank ($d$), failing when sample budgets are tight.
  3. Prior exact algorithms for volume sampling larger than $d$ were prohibitively slow (running in $O(n^4 s)$ time).

Methods

The paper focuses on volume sampling, a joint distribution where a subset $S$ of size $s \ge d$ is chosen with probability proportional to the squared volume of the parallelepiped spanned by its rows, $\det(X_S^\top X_S)$.

The core methodological innovations include:

  • Reverse Iterative Sampling: Rather than building the subset from the empty set upwards, the algorithm starts with the full dataset $\{1..n\}$ and iteratively eliminates rows down to size $s$. At each step, row $i$ is dropped with probability proportional to $\det(X_{S-i}^\top X_{S-i}) / \det(X_S^\top X_S) = \frac{1 - x_i^\top (X_S^\top X_S)^{-1} x_i}{s - d}$.
  • Fast Sampling via Rejection (FastRegVol): The transition probabilities change slowly between iterations. By utilizing local rejection sampling with Bernoulli trials, the authors eliminate the need to recompute all leverage weights at each step, slashing runtime to $O((n + \log(n/d)\log(1/\delta))d^2)$ with high probability.
  • $\lambda$-Regularized Volume Sampling: A generalized reverse process sampling with probabilities proportional to $\det(X_S^\top X_S + \lambda I)$. This extends volume sampling to subsets smaller than $d$ ($s \ge d_\lambda$, where $d_\lambda$ is the statistical dimension or effective degrees of freedom).

Datasets

The authors evaluated runtime and predictive loss on four benchmark regression datasets from the LIBSVM repository:

  • cadata: 20,640 samples, 8 features
  • cpusmall: 8,192 samples, 12 features
  • abalone: 4,177 samples, 8 features
  • MSD (Million Song Dataset): 463,715 samples, 90 features

No new datasets were introduced.

Key Insights and Ideas

  • $d$ Responses Are Necessary and Sufficient: Volume sampling exactly $d$ rows guarantees an expected total loss $\mathbb{E}[L(w^*(S))] = (d+1)L(w^*)$ when $X$ is in general position. The paper proves that no algorithm querying fewer than $d$ rows can achieve any bounded multiplicative approximation ratio.
  • Unbiased Pseudoinverse Estimator: The volume-sampled least squares estimator is fundamentally unbiased: $$\mathbb{E}[(I_S X)^+] = X^+ \implies \mathbb{E}[w^*(S)] = w^*$$ Because it is unbiased, independent runs can be averaged to systematically drive down variance.

  • Exact Matrix Covariance Formulas: The reverse iterative proof technique provides clean closed forms for the second moment: $$\mathbb{E}\left[(X_S^\top X_S)^{-1}\right] = \frac{n - d + 1}{s - d + 1} (X^\top X)^{-1}$$

  • Beating the i.i.d. Barrier: Under a noisy linear model ($y = X\tilde{w} + \xi$), regularized volume sampling achieves a mean squared prediction error bounded by $\frac{\sigma^2 d_\lambda}{s - d_\lambda + 1}$ for $s \ge d_\lambda$. By taking row interactions into account jointly, volume sampling succeeds with $2d_\lambda$ samples where any i.i.d. method requires at least $d_\lambda \ln(d_\lambda)$.

Key Results

  • Computational Speedup: FastRegVol runs in $O(nd^2)$ time, improving over the previous state-of-the-art $O(n^4 s)$ algorithm by at least a factor of $n^2$. On the large MSD benchmark ($n \approx 464\text{k}, d=90$), the unaccelerated method RegVol took $>24$ hours, while FastRegVol finished in 39 seconds—approaching the 12 seconds taken by simple leverage score sampling.
  • Subsampled Ridge Regression: On all benchmark datasets, regularized volume sampling consistently achieved lower mean squared test loss than leverage score sampling at small sample sizes $s$. On cpusmall ($d = 12$), leverage score sampling suffered severe error spikes until passing $s \approx d \ln d \approx 30$, while volume sampling exhibited smooth, low error starting right at small $s$.

Limitations and Future Work

  • The $1+\epsilon$ Sample Complexity Gap: Averaging $k$ independent volume-sampled estimators of size $d$ yields an unbiased estimator with $(1+\epsilon)$ relative error using $O(d^2/\epsilon)$ total labels. It remains an open question whether a single volume sampling variant can achieve a $(1+\epsilon)$ approximation using only $O(d/\epsilon)$ responses in expectation.
  • Higher Dimensions / Generalization: The closed-form projection covariance formula (Theorem 7) currently only holds for $s = d$; extending it to $s > d$ remains unsolved.
  • Tensor Extensions: The authors pose extending volume sampling distributions and matrix expectation identities to higher-order tensors as an open challenge.

Summary updated

Abstract

We study the following basic machine learning task: Given a fixed set of input points in $\mathbb{R}^d$ for a linear regression problem, we wish to predict a hidden response value for each of the points. We can only afford to attain the responses for a small subset of the points that are then used to construct linear predictions for all points in the dataset. The performance of the predictions is evaluated by the total square loss on all responses (the attained as well as the remaining hidden ones). We show that a good approximate solution to this least squares problem can be obtained from just dimension $d$ many responses by using a joint sampling technique called volume sampling. Moreover, the least squares solution obtained for the volume sampled subproblem is an unbiased estimator of optimal solution based on all $n$ responses. This unbiasedness is a desirable property that is not shared by other common subset selection techniques. Motivated by these basic properties, we develop a theoretical framework for studying volume sampling, resulting in a number of new matrix expectation equalities and statistical guarantees which are of importance not only to least squares regression but also to numerical linear algebra in general. Our methods also lead to a regularized variant of volume sampling, and we propose the first efficient algorithm for volume sampling which makes this technique a practical tool in the machine learning toolbox. Finally, we provide experimental evidence which confirms our theoretical findings.
BibTeX
@article{derezinski2018reverse,
  author = {Michal Derezinski and Manfred K. Warmuth},
  title = {{Reverse Iterative Volume Sampling for Linear Regression}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=Ql5w4HkBTu},
}

Loading related content...

Figure