For a finite multiset D⊂R2 let LD∗ be the least mean squared distance from a point to D, and let LD∗(n) be the least such loss attained at the average of n points selected from D with repetition. Hanneke, Moran, Shlimovich and Yehudayoff asked for F(d,n)=supDLD∗(n)/LD∗. We prove F(2,n)=2n/(2n−1) for every n≥2: every finite planar multiset satisfies LD∗(n)≤2n−12nLD∗, with equality for 2n−1 copies of (0,0) and one copy of (1,0). In particular F(2,3)=6/5, and F(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 n support points, supported on one small triangle of the selection grid, whose second moment about the population weights is dominated by 2n−11 times the categorical covariance. For n∈{2,3} we also give random selections attaining this second moment exactly.
The selected points x1,…,xn range over D independently, so a point may be selected more often than it occurs in D; equivalently, (x1,…,xn) is any sequence in supp(D), the set of distinct points of $D (this is the convention of [2 §7.2]). Question 1 of the COLT 2025 open-problem note [1] asks for
F(d,n)=D⊂RdsupLD∗LD∗(n),
where we use the conventions 0/0=1 and that D ranges over nonempty finite multisets. The note summarizes the known values as follows; all entries except d=n=2 are due to [2], and the authors describe their derivation of the d=n=2 entry as “somewhat tedious and computational” [1 §2].
d\n
1
2
3
n
n→∞
1
2
4/3
6/5
2n/(2n−1)
1
2
2
4/3
?
?
1
3
2
?
?
?
1
d→∞
2
3/2
4/3
(n+1)/n
undefined
Table 1.
For every d and n one has 2n/(2n−1)≤F(d,n)≤(n+1)/n[2 §7.5]; the lower bound comes from the one-dimensional example recalled in Proposition 13.
Theorem 1. Let n≥2. Every finite multiset D⊂R2 satisfies LD∗(n)≤2n2n−1LD∗, with equality for 2n−1 copies of (0,0) and one copy of (1,0). Hence F(2,n)=2n/(2n−1), and the supremum is attained.
Together with F(2,1)=2 from the table, Theorem 1 determines the row d=2 of the table. Its cases n=3 and n=2 read as follows.
Theorem 2. Every finite multiset D⊂R2 satisfies LD∗(3)≤56LD∗, with equality for five copies of (0,0) and one copy of (1,0). Hence F(2,3)=6/5, and the supremum is attained.
Theorem 3. Every finite multiset D⊂R2 satisfies LD∗(2)≤34LD∗, with equality for three copies of (0,0) and one copy of (1,0). Hence F(2,2)=4/3.
The value F(2,2)=4/3 is already stated in [1]; Theorem 3 gives a short proof of it. Other questions from [1], on weighted data selection for linear regression, are treated in [3, 4]; those works do not concern the mean-estimation constants F(d,n) studied here. For n∈{2,3} we give, besides the general argument, certificates that are exact in the sense of (5) below. Throughout, n≥2 and
rn:=2n−11
Reduction to three support points
Write a finite multiset as a probability law P={(zi,pi)}i=1m on its distinct points, pi=ni/N, and set
These definitions make sense for any finitely supported law with real weights. Expanding h−zi=(h−μ)−(zi−μ) and using ∑ipi(zi−μ)=0 gives
LD(h)=V(P)+∥h−μ(P)∥2(h∈R2).(1)
Hence LD∗=V(P), attained only at h=μ(P), and LD∗(n)=V(P)+qn(P). If V(P)=0 then D is a single repeated point and LD∗(n)=LD∗=0. If V(P)>0 then
LD∗LD∗(n)≤1+rn=2n−12n⟺qn(P)≤rnV(P).(2)
Lemma 4 (Mean-preserving support reduction). Let P be a finitely supported probability law on R2. There is a probability law P′ with suppP′⊆suppP, ∣suppP′∣≤3, μ(P′)=μ(P) and V(P′)≤V(P). Consequently qn(P)≤qn(P′) for every n.
Proof. Let z1,…,zm be the support of P and μ=μ(P). The set
P={a∈Rm:a≥0,i∑ai=1,i∑aizi=μ}
contains the weight vector p of P and is compact. The linear function J(a)=∑iai∥zi∥2 therefore attains its minimum on P; choose a minimizer a∗ with the fewest positive coordinates. Suppose a∗ had at least four positive coordinates. The corresponding columns (1,zi)∈R3 are linearly dependent, so there is u=0 supported on {i:ai∗>0} with ∑iui=0 and ∑iuizi=0. For small t>0 both a∗±tu lie in P, so minimality gives ±tJ(u)≥0, that is J(u)=0. Since u=0 and ∑iui=0, u has a negative coordinate; with t0=minui<0ai∗/(−ui)>0, the vector a∗+t0u lies in P, has J(a∗+t0u)=J(a∗), and has fewer positive coordinates than a∗, a contradiction. So the law P′ with weights a∗ has at most three support points, all in suppP, and mean μ. For every a∈P,
so V(P′)=J(a∗)−∥μ∥2≤J(p)−∥μ∥2=V(P). Finally, every selection legal for P′ is legal for P and both laws have the same mean, so qn(P)≤qn(P′).
By Lemma 4, if qn(P′)≤rnV(P′) holds for all laws with at most three support points, then for every finitely supported P
qn(P)≤qn(P′)≤rnV(P′)≤rnV(P).(3)
This reduction is of Carathéodory type; compare the use of Carathéodory’s theorem for convex functions in [2 §7.1].
Grid certificates
Let P have support contained in three labelled points v1,v2,v3 with weights p=(p1,p2,p3), pi≥0, ∑ipi=1; labels with pi=0 are padding and may not be selected. Put wi=vi−μ(P), so that ∑ipiwi=0 and V(P)=∑ipi∥wi∥2. A selection of n labels with multiplicities k=(k1,k2,k3), ∑iki=n, is encoded by the grid point s=k/n in
Gn={n1k:k∈Z≥03,k1+k2+k3=n},
and its selected mean, centred at μ(P), is ∑isiwi=∑i(si−pi)wi. Let Cp=diag(p)−ppT be the covariance matrix of a categorical draw with probabilities p, and write A⪯B if B−A is positive semidefinite.
Definition. A certificate for (n,p) is a probability distribution λ on Gn such that λs=0 whenever si>0 for some i with pi=0, and
Mλ:=s∈Gn∑λs(s−p)(s−p)T⪯rnCp.(4)
It is exact if
Mλ=rnCp.(5)
Lemma 5 (Extraction). If a certificate exists for (n,p), then qn(P)≤rnV(P).
Proof. Let S be a random grid point with law λ and Y=∑iSiwi=∑i(Si−pi)wi. Let Γ be the Gram matrix Γij=⟨wi,wj⟩, which is positive semidefinite. Then
The trace of a product of two positive semidefinite matrices is nonnegative, so (4) gives tr((rnCp−Mλ)Γ)≥0, that is E∥Y∥2≤rnV(P), with equality for exact certificates. Every s with λs>0 encodes a legal selection of n support points, and E∥Y∥2 is a λ-average of their squared errors. Hence some legal selection has squared error at most rnV(P).
No condition ES=p is required. The following identity reduces (5) to first and second moments.
Lemma 6. Let λ be a probability distribution on Gn, m=ES and Q=E[SST]. If for some c∈R3
Write e1,e2,e3 for the vertices of Gn and assume, after relabelling, p1≥p2≥p3; a simultaneous permutation of labels maps Gn to itself and conjugates both sides of (5) by the same permutation matrix.
Lemma 7 (Corner certificate, any n≥2). Let κ=n2/(2n−1) and suppose p1≥(nn−1)2. The weights
Proof. The first two weights are nonnegative, and 1−κ(1−p1)=(n2p12−(n−1)2)/(2n−1)≥0 by hypothesis; the weights sum to one. A label with pi=0 (i=2,3) receives weight zero. Using κ/n=n/(2n−1)=(1+rn)/2 and κ/n2=rn,
These are exactly the entries of rndiag(p)+cpT+pcT=rndiag(p)+2n−1n−1(e1pT+pe1T); for instance its (1,1) entry is rnp1+2n−12(n−1)p1=p1 and its (2,3) entry is 0. Lemma 6 applies.
Lemma 8 (Central certificate, n=3). Let n=3, p1≥p2≥p3 and p2≥61. Writing sabc=31(a,b,c), the weights
Proof. Nonnegativity: p3≥0; p2≥61; and p1≥31 by sortedness. The sum is 59−103−53+101=1. Only s111 uses label 3, and its weight vanishes if p3=0; labels 1, 2 have positive weight since p1≥p2≥61. The first moments are
With c=51(1,1,0) and r3=51, the matrix r3diag(p)+cpT+pcT has entries (1,1):53p1, (2,2):53p2, (3,3):5p3, (1,2):5p1+p2, (1,3):5p3, (2,3):5p3, which agree with Q. Lemma 6 applies.
Proposition 9. For n∈{2,3} an exact certificate exists for every p in the simplex.
Proof. Sort p1≥p2≥p3. For n=2 the hypothesis of Lemma 7 is p1≥41, which holds because p1≥31. For n=3: if p2≥61 use Lemma 8; otherwise p3≤p2<61, so p1≥32>94=(32)2 and Lemma 7 applies.
For n=2 the certificate of Lemma 7 is explicit: weight 34p1−1 on e1 and 34p2,34p3 on the midpoints 21(e1+e2),21(e1+e3). For n=3 and p2<61 it is 59p2 on s210, 59p3 on s201 and 59p1−4 on s300.
Certificates for every $n`
For k∈Z≥03 with k1+k2+k3=n−1, the three grid points (k+ei)/n, i=1,2,3, are the vertices of a small triangle of Gn that is a translate of n1{e1,e2,e3}.
Lemma 10 (Triangle certificate, any n≥2). Let k∈Z≥03 with k1+k2+k3=n−1 and (n−1)ki≤n2pi for i=1,2,3. Put
Proof. The weights are nonnegative by hypothesis and sum to (n2−(n−1)2)/(2n−1)=1. If pi=0, the hypothesis forces ki=0; then βi=0, and tj has i-th coordinate 0 for j=i, so the padding condition holds.
Put u=k/n and a=u−p, so that ti−p=a+n1ei. Since ∑iβi=1, ∑iβiei=β and ∑iβieieiT=diag(β),
Mλ=aaT+n1(aβT+βaT)+n21diag(β).
From β=(n2p−n(n−1)u)/(2n−1) and p=u−a we get n1β=rn(np−(n−1)u)=rn(u−na) and n21β=rnp−rnnn−1u. Hence, using 1−2nrn=−rn,
Mλ=rn(diag(p)−aaT+auT+uaT−nn−1diag(u)).
On the other hand ppT=(u−a)(u−a)T=uuT−auT−uaT+aaT, so
rnCp=rn(diag(p)−uuT+auT+uaT−aaT).
Subtracting, Mλ−rnCp=rn(uuT−nn−1diag(u))=−n2rnRk. Finally, for x∈R3, xTRkx=(∑iki)(∑ikixi2)−(∑ikixi)2≥0 by the Cauchy–Schwarz inequality, so Rk⪰0 and (4) holds.
For k=(n−1)e1 one has Rk=0, and Lemma 10 is exactly the corner certificate of Lemma 7; the same holds for k=(n−1)e2 or (n−1)e3 after relabelling. If two coordinates of k are positive, then Rk=0 and the certificate is not exact.
Lemma 11. For every n≥2 and every p in the simplex there is k∈Z≥03 with k1+k2+k3=n−1 and (n−1)ki≤n2pi for $i=1,2,3.
Proof. Put xi=n2pi/(n−1), so ∑ixi=n−1n2=n+1+n−11. Since ⌊xi⌋>xi−1,
i=1∑3⌊xi⌋>i∑xi−3=n−2+n−11>n−2,
and the left side is an integer, so it is at least $n-1.Chooseintegers$0≤ki≤⌊xi⌋ with $k_1+k_2+k_3=n-1.
Proposition 12. For every n≥2 a certificate exists for every p in the simplex.
Proof. Combine Lemmas 11 and 10.
Proofs of the theorems
Proposition 13 (Extremal examples [2]). Let Dn consist of 2n−1 copies of (0,0) and one copy of (1,0). Then LDn∗(n)/LDn∗=2n/(2n−1).
Proof. With θ=2n1, the mean is (θ,0) and LDn∗=V=θ(1−θ)=4n22n−1. A selection containing j copies of (1,0) has mean (j/n,0), at squared distance (j/n−θ)2 from the mean; the minimum, at j∈{0,1}, is θ2=4n21=rnV. By (1), LDn∗(n)=(1+rn)V.
For n=3 this is five copies of (0,0) and one copy of (1,0): mean (61,0), V=365, selected means (j/3,0) at squared distances 361,361,3625, so LD(3)∗(3)=61=56365. For n=2 it is three copies of (0,0) and one copy of (1,0), with V=163 and q2=163.
Proof of Theorems 1, 2 and 3. Let n≥2 and let D⊂R2 be a finite multiset with law P. If V(P)=0 both losses vanish. Otherwise, Lemma 4 gives P′ with at most three support points, all in suppD, the same mean and V(P′)≤V(P). Label the support of P′ as v1,v2,v3, padding with zero-weight labels if necessary. Proposition 12 (or, for n∈{2,3}, Proposition 9) and Lemma 5 give qn(P′)≤rnV(P′), and (3) gives qn(P)≤rnV(P). By (1) and (2), LD∗(n)≤2n−12nLD∗, which is 56LD∗ for $n=3 and 34LD∗ for $n=2. Proposition 13 shows that equality is attained.
Remark 14. Equality in Theorem 2 is not confined to collinear data. Take four copies of a=(1,−1) and one copy each of b=(1,5) and c=(−5,−1). The mean is 0 and V=61(4⋅2+26+26)=10. A selection with multiplicities k1+k2+k3=3 has mean 31(k1a+k2b+k3c)=(1−2k3,2k2−1), whose coordinates are odd integers; its squared norm is at least 2, with equality for instance for k=(3,0,0). Thus q3=2=V/5.
Remark 15 (Higher dimensions).Lemmas 5 and 10 extend verbatim to d+1 labels, and in Rd the argument of Lemma 4 reduces to d+1 support points. The counting in Lemma 11 then only gives ∑i∣xi∣>n−d+n−11, which is not enough for d≥3. We make no claim about F(d,n) for d≥3.
AI assistance disclosure
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 (Lemma 10, Lemma 11) that gives F(2,n)=2n/(2n−1) for every n (Theorem 1), 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.html
[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.org/abs/2504.14572
[3]G. Zhang, Exact risk ratios for weighted data selection in linear regression, preprint (2026), arXiv:2608.28007.arxiv.org/abs/2608.28007
[4]G. Zhang, Exact recovery thresholds for weighted data selection in vector-valued linear regression, preprint (2026), arXiv:2608.30254.arxiv.org/abs/2608.30254