The planar data-selection constants F(2,n)=2n/(2n−1)F(2,n)=2n/(2n-1), including F(2,3)=6/5F(2,3)=6/5 and F(2,2)=4/3F(2,2)=4/3

A mix of human-written and AI-generated textHuman understanding: all partsmath.ST — Statistics Theorymath.PR — Probability

Contributed by Samuil Petkov ↗

Version 1 / Nov 16, 2026 / CC BY 4.0

Abstract

For a finite multiset D⊂R2D\subset\mathbb{R}^2 let LD∗L_D^* be the least mean squared distance from a point to DD, and let LD∗(n)L_D^*(n) be the least such loss attained at the average of nn points selected from DD with repetition. Hanneke, Moran, Shlimovich and Yehudayoff asked for F(d,n)=sup⁡DLD∗(n)/LD∗F(d,n)=\sup_D L_D^*(n)/L_D^*. We prove F(2,n)=2n/(2n−1)F(2,n)=2n/(2n-1) for every n≥2n\ge2: every finite planar multiset satisfies LD∗(n)≤2n2n−1LD∗L_D^*(n)\le\frac{2n}{2n-1}L_D^*, with equality for 2n−12n-1 copies of (0,0)(0,0) and one copy of (1,0)(1,0). In particular F(2,3)=6/5F(2,3)=6/5, and F(2,2)=4/3F(2,2)=4/3 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 nn support points, supported on one small triangle of the selection grid, whose second moment about the population weights is dominated by 12n−1\frac{1}{2n-1} times the categorical covariance. For n∈{2,3}n\in\{2,3\} we also give random selections attaining this second moment exactly.

Author comments: 6 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).

Provenance statement

OpenAI GPT-5.6 Sol, accessed through ChatGPT and Codex, was used to develop and audit the original proof of F(2,3)=6/5 and its exact verification, and for drafting. Anthropic Claude Opus 5.5, used through Claude Code, condensed the manuscript, found the triangle certificate that gives F(2,n)=2n/(2n−1) for every n, and checked the certificate identities with exact symbolic and rational computation. The author reviewed and takes responsibility for every statement and proof. AI systems are not authors of this work, and the work has not been peer reviewed.

References

  1. 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
  2. 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
  3. G. Zhang, Exact risk ratios for weighted data selection in linear regression , preprint (2026), arXiv:2608.28007.arXiv
  4. G. Zhang, Exact recovery thresholds for weighted data selection in vector-valued linear regression , preprint (2026), arXiv:2608.30254.arXiv

Version history

  1. 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