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:
- Deterministic row selection cannot guarantee a multiplicative error bound better than $n/d$ in the worst case.
- 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.
- 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 featurescpusmall: 8,192 samples, 12 featuresabalone: 4,177 samples, 8 featuresMSD(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:
FastRegVolruns 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 largeMSDbenchmark ($n \approx 464\text{k}, d=90$), the unaccelerated methodRegVoltook $>24$ hours, whileFastRegVolfinished 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