The planar data-selection constants , including and
Version 1 / Nov 16, 2026 / CC BY 4.0
Abstract
For a finite multiset let be the least mean squared distance from a point to , and let be the least such loss attained at the average of points selected from with repetition. Hanneke, Moran, Shlimovich and Yehudayoff asked for . We prove for every : every finite planar multiset satisfies , with equality for copies of and one copy of . In particular , and receives a short proof. The proof reduces to three support points by a mean-preserving Carathéodory argument and then exhibits an explicit random selection of support points, supported on one small triangle of the selection grid, whose second moment about the population weights is dominated by times the categorical covariance. For we also give random selections attaining this second moment exactly.
Provenance statement
References
- S. Hanneke, S. Moran, A. Shlimovich, and A. Yehudayoff, Open problem: Data selection for regression tasks , Proceedings of the Thirty Eighth Conference on Learning Theory, Proc.\ Mach.\ Learn.\ Res.\ 291 (2025), 6225--6229. https://proceedings.mlr.press/v291/hanneke25e.htmllink
- S. Hanneke, S. Moran, A. Shlimovich, and A. Yehudayoff, Data selection for ERMs , Proceedings of the Thirty Eighth Conference on Learning Theory, Proc.\ Mach.\ Learn.\ Res.\ 291 (2025), 2634--2665; section numbers refer to arXiv:2504.14572v2. https://proceedings.mlr.press/v291/hanneke25a.htmlarXiv
- G. Zhang, Exact risk ratios for weighted data selection in linear regression , preprint (2026), arXiv:2608.28007.arXiv
- G. Zhang, Exact recovery thresholds for weighted data selection in vector-valued linear regression , preprint (2026), arXiv:2608.30254.arXiv
Version history
- v1 · 6 pagesSubmitted by Samuil Petkov6 pages. Determines F(2,n) for all n, resolving the d=2 row of Question 1 of the COLT 2025 open problem "Data selection for regression tasks" (Hanneke, Moran, Shlimovich, Yehudayoff).CurrentNov 16, 2026