Introduction
In large-scale linear regression, we often face a "label-expensive" scenario: we have a massive design matrix $\mathbf{X}$ (features), but obtaining the corresponding labels $\mathbf{y}$ is costly or time-consuming. The goal is to select a small subset of columns $S$ to label such that the solution derived from this subset, $\mathbf{w}^*(S)$, is a good approximation of the optimal solution $\mathbf{w}^*$ for the entire dataset.
This paper demonstrates that volume sampling—selecting a subset of data points with probability proportional to the squared volume they span—provides an exactly unbiased estimator for the pseudo-inverse of a matrix and the optimal weights in linear regression. Furthermore, the authors introduce a new algorithm for volume sampling that is significantly faster (by a factor of $n^2$) than previous state-of-the-art methods, bridging a critical gap between theoretical elegance and practical efficiency.
The Challenge of Minimal Coresets
Standard approaches like i.i.d. leverage score sampling require at least $O(d \log d)$ samples to guarantee a finite error bound. Deterministic methods, on the other hand, can perform poorly if the data isn't perfectly distributed. The authors tackle the "minimal coresets" problem: what is the smallest number of samples $s$ needed to achieve an expected loss that is at most a constant factor larger than the optimal loss?
Methods: Volume Sampling and Algorithmic Optimization
The core technique is Volume Sampling. For a matrix $\mathbf{X}$ with $d$ rows and $n$ columns, a subset $S$ of size $s$ is chosen with probability proportional to the determinant of the sub-covariance matrix: $P(S) \propto \det(\mathbf{X}_S \mathbf{X}_S^\top)$.
The paper introduces several novel methodological contributions to make this feasible:
- Expectation Formulas: Using a Directed Acyclic Graph (DAG) representation of the sampling process, the authors prove that the estimator for the pseudo-inverse is unbiased.
- Reverse Iterative Volume Sampling: Instead of building a set from scratch, the authors propose an algorithm that starts with the full set of columns and iteratively removes them.
- Algorithmic Optimization: By applying the Sherman-Morrison formula for rank-1 updates, they maintain and update the inverse of the sub-covariance matrix efficiently during the removal process.
Key Insights and Theoretical Breakthroughs
- Unbiasedness is Rare: In most sub-sampling schemes for regression, the resulting estimator is biased. The discovery that volume sampling yields an exactly unbiased estimator ($\mathbb{E}[(\mathbf{X}\mathbf{I}_S)^+] = \mathbf{X}^+$) is a major theoretical "aha moment."
- Closed-Form Covariance: The authors didn't just find a bound for the variance; they found an exact closed-form expression for the covariance of the estimator, which equals a specific scalar factor times $\mathbf{X}^{+\top}\mathbf{X}^+$.
- The Power of Joint Sampling: Unlike i.i.d. sampling (where points are picked independently), volume sampling is a joint distribution. It "knows" which points have already been picked and prefers to pick new points that span a different part of the space. This is why it can achieve a multiplicative loss bound with only $s=d$ samples, whereas i.i.d. methods need $O(d \log d)$.
- The $(d+1)$ Magic Number: For a sample of size $d$ (the minimum required for a unique solution), the expected loss is exactly $(d+1)$ times the minimum possible loss. This is a tight, fundamental limit.
Summary of Key Results
- Unbiased Estimator: Proved that $\mathbb{E}[\mathbf{w}^*(S)] = \mathbf{w}^*$ for any sample size $s \geq d$.
- Exact Loss Bound: For $s=d$, the expected loss is $\mathbb{E}[L(\mathbf{w}^*(S))] = (d+1)L(\mathbf{w}^*)$.
- Computational Speedup: The new "reverse iterative" algorithm runs in $O((n - s + d)nd)$ time. For the case where $s=d$, this is $O(n^2d)$, which is a factor of $n^2$ faster than the previous $O(n^4s)$ state-of-the-art.
- A-Optimality: The paper shows that volume sampling provides a randomized solution for A-optimality (minimizing the trace of the inverse covariance), a classic but NP-hard problem in experimental design.
Limitations and Future Work
While this work establishes a fundamental connection between linear least squares and volume sampling, some open questions remain. First, while the authors found an exact loss formula for $s=d$, finding a similarly tight, exact formula for $s > d$ remains an open problem. Second, the paper provides bounds for the average of $k$ independent volume samples, but it is still unknown if taking the solution of the union of those $k$ samples (a joint subproblem) provides even better theoretical guarantees. Finally, some of the exact equalities rely on the matrix being in "general position" (any $d$ columns are linearly independent); if this doesn't hold, the equalities become inequalities.
Summary updated