Submitted works

Advanced search

math.ST — Statistics Theory

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

Contributed by Samuil Petkov

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

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 16, 20266 pages
PDFView work