Subsampling for Ridge Regression via Regularized Volume Sampling

Michal Derezinski, Manfred K. Warmuth

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.

Runtime comparison between standard Regularized Volume Sampling (RegVol) and the proposed FastRegVol algorithm on MSD and abalone datasets.

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.

Total Loss vs Subset size (s) across four datasets, comparing Regularized Volume Sampling to Leverage Score sampling.

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

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.
BibTeX
@inproceedings{derezinski2018subsampling,
  author = {Michal Derezinski and Manfred K. Warmuth},
  title = {{Subsampling for Ridge Regression via Regularized Volume Sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=H7awBgQ4sN},
}
Figure