betaFeedback

WorksMathematics

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

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.

Problem and context

Let D={z1,…,zN}⊂RdD=\{z_1,\ldots,z_N\}\subset\mathbb{R}^d be a finite multiset and

LD(h)=1N∑r=1N∥h−zr∥2,LD∗=min⁡h∈RdLD(h),LD∗(n)=min⁡x1,…,xn∈DLD(1n∑k=1nxk).L_D(h)=\frac{1}{N}\sum_{r=1}^{N}\lVert h-z_r\rVert^2,\qquad L_D^*=\min_{h\in\mathbb{R}^d}L_D(h),\qquad L_D^*(n)=\min_{x_1,\ldots,x_n\in D}L_D\left(\frac{1}{n}\sum_{k=1}^{n}x_k\right).

The selected points x1,…,xnx_1,\ldots,x_n range over DD independently, so a point may be selected more often than it occurs in DD; equivalently, (x1,…,xn)(x_1,\ldots,x_n) is any sequence in supp⁡(D)\operatorname{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)=sup⁡D⊂RdLD∗(n)LD∗,F(d,n)=\sup_{D\subset\mathbb{R}^d}\frac{L_D^*(n)}{L_D^*},

where we use the conventions 0/0=10/0=1 and that DD ranges over nonempty finite multisets. The note summarizes the known values as follows; all entries except d=n=2d=n=2 are due to [2], and the authors describe their derivation of the d=n=2d=n=2 entry as “somewhat tedious and computational” [1 §2].

d\nd\backslash n123nnn→∞n\to\infty
124/34/36/56/52n/(2n−1)2n/(2n-1)1
224/34/3??1
32???1
d→∞d\to\infty23/23/24/34/3(n+1)/n(n+1)/nundefined

Table 1.

For every dd and nn one has 2n/(2n−1)≤F(d,n)≤(n+1)/n2n/(2n-1)\le F(d,n)\le(n+1)/n [2 §7.5]; the lower bound comes from the one-dimensional example recalled in Proposition 13.

Theorem 1. Let n≥2n \ge2. Every finite multiset D⊂R2D \subset\mathbb{R}^{2} satisfies LD∗(n)≤2n−12nLD∗L_D^*(n) \le\frac{2n-1}{2n}L_D^*, with equality for 2n−12n-1 copies of (0,0)(0,0) and one copy of (1,0)(1,0). Hence F(2,n)=2n/(2n−1)F(2,n)=2n/(2n-1), and the supremum is attained.

Together with F(2,1)=2F(2,1)=2 from the table, Theorem 1 determines the row d=2d=2 of the table. Its cases n=3n=3 and n=2n=2 read as follows.

Theorem 2. Every finite multiset D⊂R2D \subset\mathbb{R}^{2} satisfies LD∗(3)≤65LD∗L_D^*(3) \le\frac{6}{5}L_D^*, with equality for five copies of (0,0)(0,0) and one copy of (1,0)(1,0). Hence F(2,3)=6/5F(2,3)=6/5, and the supremum is attained.

Theorem 3. Every finite multiset D⊂R2D \subset\mathbb{R}^{2} satisfies LD∗(2)≤43LD∗L_D^*(2) \le\frac{4}{3}L_D^*, with equality for three copies of (0,0)(0,0) and one copy of (1,0)(1,0). Hence F(2,2)=4/3F(2,2)=4/3.

The value F(2,2)=4/3F(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)F(d,n) studied here. For n∈{2,3}n \in\{2,3\} we give, besides the general argument, certificates that are exact in the sense of (5) below. Throughout, n≥2n \ge2 and

rn:=12n−1r_n := \frac{1}{2n-1}

Reduction to three support points

Write a finite multiset as a probability law P={(zi,pi)}i=1mP=\{(z_i,p_i)\}_{i=1}^{m} on its distinct points, pi=ni/Np_i=n_i/N, and set

μ(P)=∑ipizi,V(P)=∑ipi∥zi−μ(P)∥2,qn(P)=min⁡x1,…,xn∈supp⁡P∥1n∑k=1nxk−μ(P)∥2.\mu(P)=\sum_i p_i z_i,\qquad V(P)=\sum_i p_i\lVert z_i-\mu(P)\rVert^2,\qquad q_n(P)=\min_{x_1,\ldots,x_n\in\operatorname{supp} P}\left\lVert\frac{1}{n}\sum_{k=1}^{n}x_k-\mu(P)\right\rVert^2.

These definitions make sense for any finitely supported law with real weights. Expanding h−zi=(h−μ)−(zi−μ)h-z_i=(h-\mu)-(z_i-\mu) and using ∑ipi(zi−μ)=0\sum_i p_i(z_i-\mu)=0 gives

LD(h)=V(P)+∥h−μ(P)∥2(h∈R2).(1)L_D(h)=V(P)+\lVert h-\mu(P)\rVert^2\qquad(h\in\mathbb{R}^{2}). \tag*{(1)}

Hence LD∗=V(P)L_D^*=V(P), attained only at h=μ(P)h=\mu(P), and LD∗(n)=V(P)+qn(P)L_D^*(n)=V(P)+q_n(P). If V(P)=0V(P)=0 then DD is a single repeated point and LD∗(n)=LD∗=0L_D^*(n)=L_D^*=0. If V(P)>0V(P)>0 then

LD∗(n)LD∗≤1+rn=2n2n−1⟺qn(P)≤rnV(P).(2)\frac{L_D^*(n)}{L_D^*}\le1+r_n=\frac{2n}{2n-1}\quad\Longleftrightarrow\quad q_n(P)\le r_nV(P). \tag*{(2)}

Lemma 4 (Mean-preserving support reduction). Let PP be a finitely supported probability law on R2\mathbb{R}^{2}. There is a probability law P′P' with supp⁡P′⊆supp⁡P\operatorname{supp}P'\subseteq\operatorname{supp}P, ∣supp⁡P′∣≤3|\operatorname{supp}P'|\le3, μ(P′)=μ(P)\mu(P')=\mu(P) and V(P′)≤V(P)V(P')\le V(P). Consequently qn(P)≤qn(P′)q_n(P)\le q_n(P') for every nn.

Proof. Let z1,…,zmz_1,\ldots,z_m be the support of PP and μ=μ(P)\mu=\mu(P). The set

P={a∈Rm:a≥0, ∑iai=1, ∑iaizi=μ}\mathcal{P}=\left\{a\in\mathbb{R}^{m}: a\ge0,\ \sum_i a_i=1,\ \sum_i a_i z_i=\mu\right\}

contains the weight vector pp of PP and is compact. The linear function J(a)=∑iai∥zi∥2J(a)=\sum_i a_i\lVert z_i\rVert^2 therefore attains its minimum on P\mathcal{P}; choose a minimizer a∗a^* with the fewest positive coordinates. Suppose a∗a^* had at least four positive coordinates. The corresponding columns (1,zi)∈R3(1,z_i)\in\mathbb{R}^{3} are linearly dependent, so there is u≠0u\ne0 supported on {i:ai∗>0}\{i:a_i^*>0\} with ∑iui=0\sum_i u_i=0 and ∑iuizi=0\sum_i u_i z_i=0. For small t>0t>0 both a∗±tua^*\pm tu lie in P\mathcal{P}, so minimality gives ±tJ(u)≥0\pm tJ(u)\ge0, that is J(u)=0J(u)=0. Since u≠0u\ne0 and ∑iui=0\sum_i u_i=0, uu has a negative coordinate; with t0=min⁡ui<0ai∗/(−ui)>0t_0=\min_{u_i<0}a_i^*/(-u_i)>0, the vector a∗+t0ua^*+t_0u lies in P\mathcal{P}, has J(a∗+t0u)=J(a∗)J(a^*+t_0u)=J(a^*), and has fewer positive coordinates than a∗a^*, a contradiction. So the law P′P' with weights a∗a^* has at most three support points, all in supp⁡P\operatorname{supp}P, and mean μ\mu. For every a∈Pa\in\mathcal{P},

∑iai∥zi−μ∥2=J(a)−2⟨∑iaizi,μ⟩+∥μ∥2=J(a)−∥μ∥2,\sum_i a_i\lVert z_i-\mu\rVert^2=J(a)-2\left\langle\sum_i a_i z_i,\mu\right\rangle+\lVert\mu\rVert^2=J(a)-\lVert\mu\rVert^2,

so V(P′)=J(a∗)−∥μ∥2≤J(p)−∥μ∥2=V(P)V(P')=J(a^*)-\lVert\mu\rVert^2\le J(p)-\lVert\mu\rVert^2=V(P). Finally, every selection legal for P′P' is legal for PP and both laws have the same mean, so qn(P)≤qn(P′)q_n(P)\le q_n(P').

By Lemma 4, if qn(P′)≤rnV(P′)q_n(P') \le r_n V(P') holds for all laws with at most three support points, then for every finitely supported PP

qn(P)≤qn(P′)≤rnV(P′)≤rnV(P).(3)q_n(P) \le q_n(P') \le r_n V(P') \le r_n V(P). \tag*{(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 PP have support contained in three labelled points v1,v2,v3v_1,v_2,v_3 with weights p=(p1,p2,p3)p=(p_1,p_2,p_3), pi≥0p_i \ge0, ∑ipi=1\sum_i p_i=1; labels with pi=0p_i=0 are padding and may not be selected. Put wi=vi−μ(P)w_i=v_i-\mu(P), so that ∑ipiwi=0\sum_i p_iw_i=0 and V(P)=∑ipi∥wi∥2V(P)=\sum_i p_i\lVert w_i\rVert^2. A selection of nn labels with multiplicities k=(k1,k2,k3)k=(k_1,k_2,k_3), ∑iki=n\sum_i k_i=n, is encoded by the grid point s=k/ns=k/n in

Gn={1nk:k∈Z≥03, k1+k2+k3=n},G_n=\left\{\frac{1}{n}k:k\in\mathbb{Z}_{\geq0}^3,\ k_1+k_2+k_3=n\right\},

and its selected mean, centred at μ(P)\mu(P), is ∑isiwi=∑i(si−pi)wi\sum_i s_iw_i=\sum_i(s_i-p_i)w_i. Let Cp=diag⁡(p)−ppTC_p=\operatorname{diag}(p)-pp^{\mathsf T} be the covariance matrix of a categorical draw with probabilities pp, and write A⪯BA\preceq B if B−AB-A is positive semidefinite.

Definition. A certificate for (n,p)(n,p) is a probability distribution λ\lambda on GnG_n such that λs=0\lambda_s=0 whenever si>0s_i>0 for some ii with pi=0p_i=0, and

Mλ:=∑s∈Gnλs(s−p)(s−p)T⪯rnCp.(4)M_\lambda:=\sum_{s\in G_n}\lambda_s(s-p)(s-p)^{\mathsf T}\preceq r_n C_p. \tag*{(4)}

It is exact if

Mλ=rnCp.(5)M_\lambda=r_n C_p. \tag*{(5)}

Lemma 5 (Extraction). If a certificate exists for (n,p)(n,p), then qn(P)≤rnV(P)q_n(P)\le r_nV(P).

Proof. Let SS be a random grid point with law λ\lambda and Y=∑iSiwi=∑i(Si−pi)wiY=\sum_i S_iw_i=\sum_i(S_i-p_i)w_i. Let Γ\Gamma be the Gram matrix Γij=⟨wi,wj⟩\Gamma_{ij}=\langle w_i,w_j\rangle, which is positive semidefinite. Then

E∥Y∥2=∑i,jE[(Si−pi)(Sj−pj)]Γij=tr⁡(MλΓ),tr⁡(CpΓ)=∑ipi∥wi∥2−∥∑ipiwi∥2=V(P).\mathbb{E}\lVert Y\rVert^2=\sum_{i,j}\mathbb{E}[(S_i-p_i)(S_j-p_j)]\Gamma_{ij}=\operatorname{tr}(M_\lambda\Gamma),\qquad\operatorname{tr}(C_p\Gamma)=\sum_i p_i\lVert w_i\rVert^2-\left\lVert\sum_i p_iw_i\right\rVert^2=V(P).

The trace of a product of two positive semidefinite matrices is nonnegative, so (4) gives tr⁡((rnCp−Mλ)Γ)≥0\operatorname{tr}((r_nC_p-M_\lambda)\Gamma)\geq0, that is E∥Y∥2≤rnV(P)\mathbb{E}\lVert Y\rVert^2\leq r_nV(P), with equality for exact certificates. Every ss with λs>0\lambda_s>0 encodes a legal selection of nn support points, and E∥Y∥2\mathbb{E}\lVert Y\rVert^2 is a λ\lambda-average of their squared errors. Hence some legal selection has squared error at most rnV(P)r_nV(P).

No condition ES=p\mathbb{E}S=p is required. The following identity reduces (5) to first and second moments.

Lemma 6. Let λ\lambda be a probability distribution on GnG_n, m=ESm=\mathbb{E}S and Q=E[SST]Q=\mathbb{E}[SS^{\mathsf T}]. If for some c∈R3c\in\mathbb{R}^3

m=1+rn2p+candQ=rndiag⁡(p)+cpT+pcT,m=\frac{1+r_n}{2}p+c\qquad\text{and}\qquad Q=r_n\operatorname{diag}(p)+cp^{\mathsf T}+pc^{\mathsf T},

then λ\lambda satisfies (5).

Proof. E[(S−p)(S−p)T]=Q−mpT−pmT+ppT=rndiag⁡(p)+cpT+pcT−(1+rn)ppT−cpT−pcT+ppT=rnCp\mathbb{E}[(S-p)(S-p)^{\mathsf T}]=Q-mp^{\mathsf T}-pm^{\mathsf T}+pp^{\mathsf T}=r_n\operatorname{diag}(p)+cp^{\mathsf T}+pc^{\mathsf T}-(1+r_n)pp^{\mathsf T}-cp^{\mathsf T}-pc^{\mathsf T}+pp^{\mathsf T}=r_nC_p.

Write e1,e2,e3e_1,e_2,e_3 for the vertices of GnG_n and assume, after relabelling, p1≥p2≥p3p_1\geq p_2\geq p_3; a simultaneous permutation of labels maps GnG_n to itself and conjugates both sides of (5) by the same permutation matrix.

Lemma 7 (Corner certificate, any n≥2n\geq2). Let κ=n2/(2n−1)\kappa=n^2/(2n-1) and suppose p1≥(n−1n)2p_1\geq\left(\frac{n-1}{n}\right)^2. The weights

λ(e1+1n(e2−e1))=κp2,λ(e1+1n(e3−e1))=κp3,λ(e1)=1−κ(p2+p3)\lambda\left(e_1+\frac{1}{n}(e_2-e_1)\right)=\kappa p_2,\qquad \lambda\left(e_1+\frac{1}{n}(e_3-e_1)\right)=\kappa p_3,\qquad \lambda(e_1)=1-\kappa(p_2+p_3)

form an exact certificate for (n,p)(n,p).

Proof. The first two weights are nonnegative, and 1−κ(1−p1)=(n2p12−(n−1)2)/(2n−1)≥01-\kappa(1-p_1)=(n^2p_1^2-(n-1)^2)/(2n-1)\ge0 by hypothesis; the weights sum to one. A label with pi=0p_i=0 (i=2,3i=2,3) receives weight zero. Using κ/n=n/(2n−1)=(1+rn)/2\kappa/n=n/(2n-1)=(1+r_n)/2 and κ/n2=rn\kappa/n^2=r_n,

m1=1−κn(p2+p3)=np1+n−12n−1,m2=n2n−1p2,m3=n2n−1p3.m_1=1-\frac{\kappa}{n}(p_2+p_3)=\frac{np_1+n-1}{2n-1},\qquad m_2=\frac{n}{2n-1}p_2,\qquad m_3=\frac{n}{2n-1}p_3.

so m=1+rn2p+cm=\frac{1+r_n}{2}p+c with c=n−12n−1e1c=\frac{n-1}{2n-1}e_1. For the second moments,

Q22=κn2p2=rnp2,Q33=rnp3,Q23=0,Q12=κ(n−1)n2p2=n−12n−1p2,Q13=n−12n−1p3,Q_{22}=\frac{\kappa}{n^2}p_2=r_np_2,\qquad Q_{33}=r_np_3,\qquad Q_{23}=0,\qquad Q_{12}=\frac{\kappa(n-1)}{n^2}p_2=\frac{n-1}{2n-1}p_2,\qquad Q_{13}=\frac{n-1}{2n-1}p_3,
Q11=1−κ(p2+p3)(1−(n−1n)2)=1−(1−p1)=p1.Q_{11}=1-\kappa(p_2+p_3)\left(1-\left(\frac{n-1}{n}\right)^2\right)=1-(1-p_1)=p_1.

These are exactly the entries of rndiag⁡(p)+cpT+pcT=rndiag⁡(p)+n−12n−1(e1pT+pe1T)r_n\operatorname{diag}(p)+cp^{\mathsf T}+pc^{\mathsf T}=r_n\operatorname{diag}(p)+\frac{n-1}{2n-1}(e_1p^{\mathsf T}+pe_1^{\mathsf T}); for instance its (1,1)(1,1) entry is rnp1+2(n−1)2n−1p1=p1r_np_1+\frac{2(n-1)}{2n-1}p_1=p_1 and its (2,3)(2,3) entry is 0. Lemma 6 applies.

Lemma 8 (Central certificate, n=3n=3). Let n=3n=3, p1≥p2≥p3p_1\ge p_2\ge p_3 and p2≥16p_2\ge\frac{1}{6}. Writing sabc=13(a,b,c)s_{abc}=\frac{1}{3}(a,b,c), the weights

λ(s111)=95p3,λ(s120)=95p2−310,λ(s210)=95p1−35,λ(s300)=110\lambda(s_{111})=\frac{9}{5}p_3,\qquad\lambda(s_{120})=\frac{9}{5}p_2-\frac{3}{10},\qquad\lambda(s_{210})=\frac{9}{5}p_1-\frac{3}{5},\qquad\lambda(s_{300})=\frac{1}{10}

form an exact certificate for (3,p)(3,p).

Proof. Nonnegativity: p3≥0p_3\ge0; p2≥16p_2\ge\frac{1}{6}; and p1≥13p_1\ge\frac{1}{3} by sortedness. The sum is 95−310−35+110=1\frac{9}{5}-\frac{3}{10}-\frac{3}{5}+\frac{1}{10}=1. Only s111s_{111} uses label 3, and its weight vanishes if p3=0p_3=0; labels 1, 2 have positive weight since p1≥p2≥16p_1\ge p_2\ge\frac{1}{6}. The first moments are

m1=13λ111+13λ120+23λ210+λ300=3p1+15,m2=13λ111+23λ120+13λ210=3p2+15,m_1=\frac{1}{3}\lambda_{111}+\frac{1}{3}\lambda_{120}+\frac{2}{3}\lambda_{210}+\lambda_{300}=\frac{3p_1+1}{5},\qquad m_2=\frac{1}{3}\lambda_{111}+\frac{2}{3}\lambda_{120}+\frac{1}{3}\lambda_{210}=\frac{3p_2+1}{5},
m3=13λ111=35p3,m_3=\frac{1}{3}\lambda_{111}=\frac{3}{5}p_3,

so m=35p+cm=\frac{3}{5}p+c with c=15(1,1,0)c=\frac{1}{5}(1,1,0), and 35=1+r32\frac{3}{5}=\frac{1+r_3}{2}. The second moments are

Q11=19λ111+19λ120+49λ210+λ300=35p1,Q22=19λ111+49λ120+19λ210=35p2,Q_{11}=\frac{1}{9}\lambda_{111}+\frac{1}{9}\lambda_{120}+\frac{4}{9}\lambda_{210}+\lambda_{300}=\frac{3}{5}p_1,\qquad Q_{22}=\frac{1}{9}\lambda_{111}+\frac{4}{9}\lambda_{120}+\frac{1}{9}\lambda_{210}=\frac{3}{5}p_2,
Q12=19λ111+29λ120+29λ210=p1+p25,Q13=Q23=Q33=19λ111=15p3.Q_{12}=\frac{1}{9}\lambda_{111}+\frac{2}{9}\lambda_{120}+\frac{2}{9}\lambda_{210}=\frac{p_1+p_2}{5},\qquad Q_{13}=Q_{23}=Q_{33}=\frac{1}{9}\lambda_{111}=\frac{1}{5}p_3.

With c=15(1,1,0)c=\frac{1}{5}(1,1,0) and r3=15r_3=\frac{1}{5}, the matrix r3diag⁡(p)+cpT+pcTr_3\operatorname{diag}(p)+cp^{\mathsf T}+pc^{\mathsf T} has entries (1,1):3p15(1,1):\frac{3p_1}{5}, (2,2):3p25(2,2):\frac{3p_2}{5}, (3,3):p35(3,3):\frac{p_3}{5}, (1,2):p1+p25(1,2):\frac{p_1+p_2}{5}, (1,3):p35(1,3):\frac{p_3}{5}, (2,3):p35(2,3):\frac{p_3}{5}, which agree with QQ. Lemma 6 applies.

Proposition 9. For n∈{2,3}n\in\{2,3\} an exact certificate exists for every pp in the simplex.

Proof. Sort p1≥p2≥p3p_1\ge p_2\ge p_3. For n=2n=2 the hypothesis of Lemma 7 is p1≥14p_1\ge\frac{1}{4}, which holds because p1≥13p_1\ge\frac{1}{3}. For n=3n=3: if p2≥16p_2\ge\frac{1}{6} use Lemma 8; otherwise p3≤p2<16p_3\le p_2<\frac{1}{6}, so p1≥23>49=(23)2p_1\ge\frac{2}{3}>\frac{4}{9}=\left(\frac{2}{3}\right)^2 and Lemma 7 applies.

For n=2n=2 the certificate of Lemma 7 is explicit: weight 4p1−13\frac{4p_1-1}{3} on e1e_1 and 43p2,43p3\frac{4}{3}p_2,\frac{4}{3}p_3 on the midpoints 12(e1+e2),12(e1+e3)\frac{1}{2}(e_1+e_2),\frac{1}{2}(e_1+e_3). For n=3n=3 and p2<16p_2<\frac{1}{6} it is 95p2\frac{9}{5}p_2 on s210s_{210}, 95p3\frac{9}{5}p_3 on s201s_{201} and 9p1−45\frac{9p_1-4}{5} on s300s_{300}.

Certificates for every $n`

For k∈Z≥03k\in\mathbb{Z}_{\ge0}^3 with k1+k2+k3=n−1k_1+k_2+k_3=n-1, the three grid points (k+ei)/n(k+e_i)/n, i=1,2,3i=1,2,3, are the vertices of a small triangle of GnG_n that is a translate of 1n{e1,e2,e3}\frac{1}{n}\{e_1,e_2,e_3\}.

Lemma 10 (Triangle certificate, any n≥2n\ge2). Let k∈Z≥03k\in\mathbb{Z}_{\ge0}^3 with k1+k2+k3=n−1k_1+k_2+k_3=n-1 and (n−1)ki≤n2pi(n-1)k_i\le n^2p_i for i=1,2,3i=1,2,3. Put

ti=1n(k+ei)∈Gn,βi=n2pi−(n−1)ki2n−1(i=1,2,3),t_i=\frac{1}{n}(k+e_i)\in G_n,\qquad\beta_i=\frac{n^2p_i-(n-1)k_i}{2n-1}\qquad(i=1,2,3),

and let λ=∑iβiδti\lambda=\sum_i\beta_i\delta_{t_i}. Then λ\lambda is a certificate for (n,p)(n,p); more precisely

Mλ=∑i=13βi(ti−p)(ti−p)T=rnCp−rnn2Rk,Rk:=(n−1)diag⁡(k)−kkT⪰0.(6)M_\lambda=\sum_{i=1}^{3}\beta_i(t_i-p)(t_i-p)^{\mathsf T}=r_nC_p-\frac{r_n}{n^2}R_k,\qquad R_k:=(n-1)\operatorname{diag}(k)-kk^{\mathsf T}\succeq0. \tag*{(6)}

Proof. The weights are nonnegative by hypothesis and sum to (n2−(n−1)2)/(2n−1)=1(n^2-(n-1)^2)/(2n-1)=1. If pi=0p_i=0, the hypothesis forces ki=0k_i=0; then βi=0\beta_i=0, and tjt_j has ii-th coordinate 00 for j≠ij\ne i, so the padding condition holds.

Put u=k/nu=k/n and a=u−pa=u-p, so that ti−p=a+1neit_i-p=a+\frac{1}{n}e_i. Since ∑iβi=1\sum_i\beta_i=1, ∑iβiei=β\sum_i\beta_i e_i=\beta and ∑iβieieiT=diag⁡(β)\sum_i\beta_i e_i e_i^{\mathsf T}=\operatorname{diag}(\beta),

Mλ=aaT+1n(aβT+βaT)+1n2diag⁡(β).M_\lambda=aa^{\mathsf T}+\frac{1}{n}(a\beta^{\mathsf T}+\beta a^{\mathsf T})+\frac{1}{n^2}\operatorname{diag}(\beta).

From β=(n2p−n(n−1)u)/(2n−1)\beta=(n^2p-n(n-1)u)/(2n-1) and p=u−ap=u-a we get 1nβ=rn(np−(n−1)u)=rn(u−na)\frac{1}{n}\beta=r_n(np-(n-1)u)=r_n(u-na) and 1n2β=rnp−rnn−1nu\frac{1}{n^2}\beta=r_np-r_n\frac{n-1}{n}u. Hence, using 1−2nrn=−rn1-2nr_n=-r_n,

Mλ=rn(diag⁡(p)−aaT+auT+uaT−n−1ndiag⁡(u)).M_\lambda=r_n\left(\operatorname{diag}(p)-aa^{\mathsf T}+au^{\mathsf T}+ua^{\mathsf T}-\frac{n-1}{n}\operatorname{diag}(u)\right).

On the other hand ppT=(u−a)(u−a)T=uuT−auT−uaT+aaTpp^{\mathsf T}=(u-a)(u-a)^{\mathsf T}=uu^{\mathsf T}-au^{\mathsf T}-ua^{\mathsf T}+aa^{\mathsf T}, so

rnCp=rn(diag⁡(p)−uuT+auT+uaT−aaT).r_nC_p=r_n\left(\operatorname{diag}(p)-uu^{\mathsf T}+au^{\mathsf T}+ua^{\mathsf T}-aa^{\mathsf T}\right).

Subtracting, Mλ−rnCp=rn(uuT−n−1ndiag⁡(u))=−rnn2RkM_\lambda-r_nC_p=r_n\left(uu^{\mathsf T}-\frac{n-1}{n}\operatorname{diag}(u)\right)=-\frac{r_n}{n^2}R_k. Finally, for x∈R3x\in\mathbb{R}^3, xTRkx=(∑iki)(∑ikixi2)−(∑ikixi)2≥0x^{\mathsf T}R_kx=(\sum_i k_i)(\sum_i k_ix_i^2)-(\sum_i k_ix_i)^2\ge0 by the Cauchy–Schwarz inequality, so Rk⪰0R_k\succeq0 and (4) holds.

For k=(n−1)e1k=(n-1)e_1 one has Rk=0R_k=0, and Lemma 10 is exactly the corner certificate of Lemma 7; the same holds for k=(n−1)e2k=(n-1)e_2 or (n−1)e3(n-1)e_3 after relabelling. If two coordinates of kk are positive, then Rk≠0R_k\ne0 and the certificate is not exact.

Lemma 11. For every n≥2n\ge2 and every pp in the simplex there is k∈Z≥03k\in\mathbb{Z}_{\ge0}^3 with k1+k2+k3=n−1k_1+k_2+k_3=n-1 and (n−1)ki≤n2pi(n-1)k_i\le n^2p_i for $i=1,2,3.

Proof. Put xi=n2pi/(n−1)x_i=n^2p_i/(n-1), so ∑ixi=n2n−1=n+1+1n−1\sum_i x_i=\frac{n^2}{n-1}=n+1+\frac{1}{n-1}. Since ⌊xi⌋>xi−1\lfloor x_i\rfloor>x_i-1,

∑i=13⌊xi⌋>∑ixi−3=n−2+1n−1>n−2,\sum_{i=1}^{3}\lfloor x_i\rfloor>\sum_i x_i-3=n-2+\frac{1}{n-1}>n-2,

and the left side is an integer, so it is at least $n-1.Chooseintegers$0≤ki≤⌊xi⌋. Choose integers \$0\le k_i\le\lfloor x_i\rfloor with $k_1+k_2+k_3=n-1.

Proposition 12. For every n≥2n\ge2 a certificate exists for every pp in the simplex.

Proof. Combine Lemmas 11 and 10.

Proofs of the theorems

Proposition 13 (Extremal examples [2]). Let DnD_n consist of 2n−12n-1 copies of (0,0)(0,0) and one copy of (1,0)(1,0). Then LDn∗(n)/LDn∗=2n/(2n−1)L^*_{D_n}(n)/L^*_{D_n}=2n/(2n-1).

Proof. With θ=12n\theta=\frac{1}{2n}, the mean is (θ,0)(\theta,0) and LDn∗=V=θ(1−θ)=2n−14n2L^*_{D_n}=V=\theta(1-\theta)=\frac{2n-1}{4n^2}. A selection containing jj copies of (1,0)(1,0) has mean (j/n,0)(j/n,0), at squared distance (j/n−θ)2(j/n-\theta)^2 from the mean; the minimum, at j∈{0,1}j\in\{0,1\}, is θ2=14n2=rnV\theta^2=\frac{1}{4n^2}=r_nV. By (1), LDn∗(n)=(1+rn)VL^*_{D_n}(n)=(1+r_n)V.

For n=3n=3 this is five copies of (0,0)(0,0) and one copy of (1,0)(1,0): mean (16,0)(\frac{1}{6},0), V=536V=\frac{5}{36}, selected means (j/3,0)(j/3,0) at squared distances 136,136,2536\frac{1}{36},\frac{1}{36},\frac{25}{36}, so LD(3)∗(3)=16=65536L^*_{D(3)}(3)=\frac{1}{6}=\frac{6}{5}\frac{5}{36}. For n=2n=2 it is three copies of (0,0)(0,0) and one copy of (1,0)(1,0), with V=316V=\frac{3}{16} and q2=316q_2=\frac{3}{16}.

Proof of Theorems 1, 2 and 3. Let n≥2n\ge2 and let D⊂R2D\subset\mathbb{R}^2 be a finite multiset with law PP. If V(P)=0V(P)=0 both losses vanish. Otherwise, Lemma 4 gives P′P' with at most three support points, all in supp⁡D\operatorname{supp}D, the same mean and V(P′)≤V(P)V(P')\le V(P). Label the support of P′P' as v1,v2,v3v_1,v_2,v_3, padding with zero-weight labels if necessary. Proposition 12 (or, for n∈{2,3}n\in\{2,3\}, Proposition 9) and Lemma 5 give qn(P′)≤rnV(P′)q_n(P')\le r_nV(P'), and (3) gives qn(P)≤rnV(P)q_n(P)\le r_nV(P). By (1) and (2), LD∗(n)≤2n2n−1LD∗L^*_{D}(n)\le\frac{2n}{2n-1}L^*_{D}, which is 65LD∗\frac{6}{5}L^*_{D} for $n=3 and 43LD∗\frac{4}{3}L^*_{D} 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)a=(1,-1) and one copy each of b=(1,5)b=(1,5) and c=(−5,−1)c=(-5,-1). The mean is 00 and V=16(4⋅2+26+26)=10V=\frac{1}{6}(4\cdot2+26+26)=10. A selection with multiplicities k1+k2+k3=3k_1+k_2+k_3=3 has mean 13(k1a+k2b+k3c)=(1−2k3,2k2−1)\frac{1}{3}(k_1a+k_2b+k_3c)=(1-2k_3,2k_2-1), whose coordinates are odd integers; its squared norm is at least 22, with equality for instance for k=(3,0,0)k=(3,0,0). Thus q3=2=V/5q_3=2=V/5.

Remark 15 (Higher dimensions). Lemmas 5 and 10 extend verbatim to d+1d+1 labels, and in Rd\mathbb{R}^d the argument of Lemma 4 reduces to d+1d+1 support points. The counting in Lemma 11 then only gives ∑i∣xi∣>n−d+1n−1\sum_i \lvert x_i\rvert>n-d+\frac{1}{n-1}, which is not enough for d≥3d\ge3. We make no claim about F(d,n)F(d,n) for d≥3d\ge3.

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/5F(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)F(2,n)=2n/(2n-1) for every nn (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. [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. [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. [3]G. Zhang, Exact risk ratios for weighted data selection in linear regression, preprint (2026), arXiv:2608.28007.arxiv.org/abs/2608.28007
  4. [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

Paper details

vlnc:W_79ygfsur
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-5.6 Sol (bare), Anthropic Claude Opus 5.5

View statement
Looking for related papers…
Contents