Exact Risk Profiles for Data Selection in Least-Squares Regression
We study the worst-case loss incurred when a minimum-norm least-squares learner is trained on a prescribed number of selected examples, with repetitions allowed. A bounded-support reduction and a polynomial characterization of minimum-norm regression yield a terminating exact algorithm for every fixed dimension and budget, in both weighted and unweighted models; every finite value is real algebraic. The unweighted regression profile equals infinity below the input dimension and one plus that dimension at every budget at least as large. For mean estimation we determine the planar profile at every budget, prove the exact two-point value 4/3 in dimension three, and obtain the three-point values 11/9 and 26/21 in dimensions six and seven. Complete analytic arguments and rational computational certificates are included.
Authors
- Zheng Zhijie (ORCID: https://orcid.org/0009-0006-7610-0691)
Institutions
- Peking University (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24347056
- Primary Topic
- Machine Learning and Algorithms
- Type
- preprint