Selecting n data points whose average is nearly as good as the mean

Pick $n$ points from a dataset in $\mathbb{R}^d$ and use their average in place of the mean. In the worst case, how much larger can its squared loss on the whole dataset be? The answer is known on the line and in the limit of high dimension, but in the plane only for averages of one or two points.

Problem

A dataset is a finite multiset $D = \{z_1, \dots, z_N\} \subset \mathbb{R}^d$. Its squared loss at $h \in \mathbb{R}^d$ is

$$L_D(h) = \frac{1}{N} \sum_{i=1}^{N} \| h - z_i \|^2 ,$$

which is minimized by the mean $\mu_D$; write $L^\star_D = L_D(\mu_D)$. For a budget $n$, let $L^\star_D(n)$ be the least value of $L_D\big(\tfrac{1}{n}(w_1 + \dots + w_n)\big)$ over all choices of $w_1, \dots, w_n \in D$ (repetitions allowed), and define

$$F(d, n) = \sup_{D \subset \mathbb{R}^d} \frac{L^\star_D(n)}{L^\star_D} .$$

Because $L_D(h) = L^\star_D + \|h - \mu_D\|^2$, the question is how close an average of $n$ data points can be guaranteed to get to the mean, measured against the spread of the data.

Question. Determine $F(d, n)$ for $d \ge 2$ and $n \ge 2$; apart from $F(2, 2)$, none of these values is known. The smallest open cases are $F(2, 3)$ and $F(3, 2)$.

Background

Most of learning theory fixes the data and optimizes the algorithm. Data selection does the reverse: fix a natural learning rule and ask how well it can do when trained on the best $n$ examples of a larger dataset. The question connects to sample compression, active learning and coresets [4]. Hanneke, Moran, Shlimovich and Yehudayoff developed this view for empirical risk minimizers in 2025 [2], and in a companion note at COLT 2025 they posed concrete open questions for regression [1]. Mean estimation, where the learning rule is simply "take the average", is the first of them.

What is known

• On the line. $F(1, n) = 2n/(2n-1)$ [2]. The extreme dataset is $2n - 1$ copies of $0$ and one copy of $1$.
• In every dimension. $2n/(2n-1) \le F(d, n) \le (n+1)/n$, and the upper bound becomes tight as $d \to \infty$ [2]. For $n = 1$ both bounds equal $2$, so $F(d, 1) = 2$.
• In the plane with two points. $F(2, 2) = 4/3$, the same as on the line. The posers found this by a tedious computation and ask for a simple proof [1].
• Open cases. By the bounds above, $6/5 \le F(2, 3) \le 4/3$ and $4/3 \le F(3, 2) \le 3/2$.
• Related progress. The weighted version for linear regression, another question of [1], has seen recent progress; for example $F_w(d, 2d-1) = 1 + 1/d$ (Zhang, 2026) [3].

What would count as progress

• A planar dataset with exact rational coordinates for which the ratio $L^\star_D(3)/L^\star_D$ exceeds $6/5$, showing that the plane is harder than the line. This is checkable exactly by trying every choice of three points, repetitions included.
• A proof of the exact value of $F(2, 3)$ or $F(3, 2)$, or a short conceptual proof that $F(2, 2) = 4/3$.
• The behavior of $n\,(F(2, n) - 1)$ as $n \to \infty$; by the bounds above it lies between $n/(2n-1)$ and $1$.

References

1. S. Hanneke, S. Moran, A. Shlimovich and A. Yehudayoff, Open problem: Data selection for regression tasks, COLT 2025, PMLR 291 (2025), 6225–6229. PMLR
2. S. Hanneke, S. Moran, A. Shlimovich and A. Yehudayoff, Data selection for ERMs, COLT 2025, PMLR 291 (2025), 2634–2665. arXiv:2504.14572
3. G. Zhang, Exact risk ratios for weighted data selection in linear regression, preprint (2026). arXiv:2608.28007
4. D. Feldman, Introduction to core-sets: an updated survey, preprint (2020). arXiv:2011.09384

Source

Imported from COLT open problems, COLT 2025, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.