There is a newer version of the record available.

Published October 3, 2026 | Version v1

Exact Three-Example Selection in Every Dimension

Authors/Creators

  • 1. ROR icon Wuhan University

Description

We determine the exact worst-case risk inflation for mean regression when a selector chooses exactly three points from the support of a finite dataset, with repetition allowed, and predicts their equally weighted mean. Let F(d,3) be the worst-case ratio between the best such predictor's squared loss and the loss of the full-data mean in dimension d. We prove that F(d,3)-1 equals 1/5 for d=1,2,3; (11-sqrt(13))/36 for d=4; (16-2sqrt(10))/45 for d=5; and (d-2)/(3d) for every d>=6.

The extremal geometry changes with dimension. In dimensions four and five, the extremizers have one apex and an equally weighted regular base. Their irrational masses imply that the supremum cannot be attained by a finite equal-weight multiset, although rational approximations approach it. Dimension six has exactly two extremal types, while in every dimension d>=7 the uniform regular simplex is the unique extremal type up to similarities and relabeling. Explicit sharp finite datasets are provided in the remaining dimensions.

The proof combines variance-minimizing support reduction, explicit second-moment certificates, conditionally unbiased splitting of merged atoms, and a distinct-triple certificate with a positive semidefinite remainder consisting of a rank-one matrix and a graph Laplacian. The record includes the manuscript, LaTeX source, verification scripts, and computational results. This resolves the n=3 column of the mean-regression data-selection question posed by Hanneke, Moran, Shlimovich, and Yehudayoff at COLT 2025.

Files

exact-three-example-selection-source-v1.0.zip

Files (306.5 kB)

Name Size
md5:e05460a9d4fde27e815aedfb10f5a563
27.9 kB Preview Download
md5:b99d75e845aff2438dafa57bbe4839b1
278.6 kB Preview Download