Abstract
Given $n$ vectors $\mathbf{x}_i\in \mathbb{R}^d$, we want to fit a linear regression model for noisy labels $y_i\in\mathbb{R}$. The ridge estimator is a classical solution to this problem. However, when labels are expensive, we are forced to select only a small subset of vectors $\mathbf{x}_i$ for which we obtain the labels $y_i$. We propose a new procedure for selecting the subset of vectors, such that the ridge estimator obtained from that subset offers strong statistical guarantees in terms of the mean squared prediction error over the entire dataset of $n$ labeled vectors. The number of labels needed is proportional to the statistical dimension of the problem which is often much smaller than $d$. Our method is an extension of a joint subsampling procedure called volume sampling. A second major contribution is that we speed up volume sampling so that it is essentially as efficient as leverage scores, which is the main i.i.d. subsampling procedure for this task. Finally, we show theoretically and experimentally that volume sampling has a clear advantage over any i.i.d. sampling when labels are expensive.
Introduction
In many machine learning scenarios, obtaining labels ($y$) for a massive amount of unlabeled data (features $x$) is prohibitively expensive. To minimize costs, we must select a small subset of $s$ points to label such that the model trained on this subset approximates the performance of a model trained on the full dataset.
The standard approach, leverage score sampling, selects points independently based on their geometric importance. However, independent sampling often requires "logarithmic oversampling"—needing roughly $d \log d$ points to cover $d$ dimensions—to ensure all feature space directions are represented. In contrast, volume sampling is a joint sampling technique that selects sets of points based on the volume they span, naturally avoiding redundancy and ensuring better coverage with fewer samples.
Methods
The authors introduce two major innovations to make volume sampling practical for ridge regression:
1. Regularized Volume Sampling
Traditional volume sampling is extended to include a regularization parameter $\lambda$, aligning the sampling process with the ridge regression objective. The authors prove that the required number of labels is proportional to the statistical dimension ($d_\lambda$), which is typically much smaller than the actual feature dimension ($d$). This allows for hitting theoretical lower bounds without the $\log d_\lambda$ penalty inherent in independent methods.
2. The FastRegVol Algorithm
Previous volume sampling methods relied on a slow "reverse iterative" process ($O(n^2d)$). The proposed FastRegVol algorithm utilizes rejection sampling. By observing that the sampling distribution changes slowly as points are iteratively removed, the algorithm avoids full recomputations. This reduces complexity to $O(nd^2)$, making it as efficient as standard leverage score computations.
Experimental Results
The method was evaluated on four standard datasets: cadata, MSD, cpusmall, and abalone.
Computational Efficiency
On the largest dataset (MSD), the previous state-of-the-art algorithm failed to complete within 24 hours. In contrast, FastRegVol finished in just 39 seconds, demonstrating a massive speedup that enables volume sampling on large-scale problems. As shown in the runtime plots, FastRegVol scales linearly with data size, whereas the standard RegVol exhibits much steeper growth.
Statistical Performance
Experimental comparisons show that regularized volume sampling consistently yields lower prediction errors than leverage score sampling, particularly when the budget for labels ($s$) is very small. The joint nature of the sampling ensures that the selected subset captures the "effective" dimension of the data more efficiently than independent methods.
Conclusion
Regularized Volume Sampling provides a theoretically grounded and computationally efficient method for subsampling in ridge regression. By moving from independent to joint sampling, the FastRegVol algorithm achieves near-optimal statistical guarantees with significantly fewer labels. Future work includes extending these joint sampling guarantees to non-linear models and developing automated methods for tuning the sampling regularization parameter in active learning settings.
Summary updated