Sketched Ridgeless Linear Regression: The Role of Downsampling

Xin Chen, Yicheng Zeng, Siyue Yang, Qiang Sun
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:5296-5326, 2023.

Abstract

Overparametrization often helps improve the generalization performance. This paper presents a dual view of overparametrization suggesting that downsampling may also help generalize. Focusing on the proportional regime $m\asymp n \asymp p$, where $m$ represents the sketching size, $n$ is the sample size, and $p$ is the feature dimensionality, we investigate two out-of-sample prediction risks of the sketched ridgeless least square estimator. Our findings challenge conventional beliefs by showing that downsampling does not always harm generalization but can actually improve it in certain cases. We identify the optimal sketching size that minimizes out-of-sample prediction risks and demonstrate that the optimally sketched estimator exhibits stabler risk curves, eliminating the peaks of those for the full-sample estimator. To facilitate practical implementation, we propose an empirical procedure to determine the optimal sketching size. Finally, we extend our analysis to cover central limit theorems and misspecified models. Numerical studies strongly support our theory.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-chen23am, title = {Sketched Ridgeless Linear Regression: The Role of Downsampling}, author = {Chen, Xin and Zeng, Yicheng and Yang, Siyue and Sun, Qiang}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {5296--5326}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/chen23am/chen23am.pdf}, url = {https://proceedings.mlr.press/v202/chen23am.html}, abstract = {Overparametrization often helps improve the generalization performance. This paper presents a dual view of overparametrization suggesting that downsampling may also help generalize. Focusing on the proportional regime $m\asymp n \asymp p$, where $m$ represents the sketching size, $n$ is the sample size, and $p$ is the feature dimensionality, we investigate two out-of-sample prediction risks of the sketched ridgeless least square estimator. Our findings challenge conventional beliefs by showing that downsampling does not always harm generalization but can actually improve it in certain cases. We identify the optimal sketching size that minimizes out-of-sample prediction risks and demonstrate that the optimally sketched estimator exhibits stabler risk curves, eliminating the peaks of those for the full-sample estimator. To facilitate practical implementation, we propose an empirical procedure to determine the optimal sketching size. Finally, we extend our analysis to cover central limit theorems and misspecified models. Numerical studies strongly support our theory.} }
Endnote
%0 Conference Paper %T Sketched Ridgeless Linear Regression: The Role of Downsampling %A Xin Chen %A Yicheng Zeng %A Siyue Yang %A Qiang Sun %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-chen23am %I PMLR %P 5296--5326 %U https://proceedings.mlr.press/v202/chen23am.html %V 202 %X Overparametrization often helps improve the generalization performance. This paper presents a dual view of overparametrization suggesting that downsampling may also help generalize. Focusing on the proportional regime $m\asymp n \asymp p$, where $m$ represents the sketching size, $n$ is the sample size, and $p$ is the feature dimensionality, we investigate two out-of-sample prediction risks of the sketched ridgeless least square estimator. Our findings challenge conventional beliefs by showing that downsampling does not always harm generalization but can actually improve it in certain cases. We identify the optimal sketching size that minimizes out-of-sample prediction risks and demonstrate that the optimally sketched estimator exhibits stabler risk curves, eliminating the peaks of those for the full-sample estimator. To facilitate practical implementation, we propose an empirical procedure to determine the optimal sketching size. Finally, we extend our analysis to cover central limit theorems and misspecified models. Numerical studies strongly support our theory.
APA
Chen, X., Zeng, Y., Yang, S. & Sun, Q.. (2023). Sketched Ridgeless Linear Regression: The Role of Downsampling. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:5296-5326 Available from https://proceedings.mlr.press/v202/chen23am.html.

Related Material