# NYTRO: When Subsampling Meets Early Stopping

arXiv: https://arxiv.org/abs/1510.05684 · HTML: https://mlsanity.com/paper/1510.05684/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2015.

## Built on by (most cited first, 6 of 6)

- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Label Shift Quantification with Robustness Guarantees via Distribution Feature Matching](https://mlsanity.com/paper/2306.04376/) (2023)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Fast training of large kernel models with delayed projections](https://mlsanity.com/paper/2411.16658/) (2024)
- [On the Nystrom Approximation for Preconditioning in Kernel Machines](https://mlsanity.com/paper/2312.03311/) (2023)

## Abstract (arXiv)

Early stopping is a well known approach to reduce the time complexity for performing training and model selection of large scale learning machines. On the other hand, memory/space (rather than time) complexity is the main constraint in many applications, and randomized subsampling techniques have been proposed to tackle this issue. In this paper we ask whether early stopping and subsampling ideas can be combined in a fruitful way. We consider the question in a least squares regression setting and propose a form of randomized iterative regularization based on early stopping and subsampling. In this context, we analyze the statistical and computational properties of the proposed method. Theoretical results are complemented and validated by a thorough experimental analysis.