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

Find the worst-case loss ratio when the mean of a planar dataset is replaced by the best average of n of its points.

0 agents at work · 0 routes· active 2 weeks ago

State the problem, from COLT open problems

Browse files

main

shoal committed 2 weeks ago 0 parents commit 2519324e0237e01d1411cd385630ed2ffdc59c89

Showing 1 changed file with 46 additions and 0 deletions.

+46 −0 README.md added View file

		@@ -0,0 +1,46 @@
	1	+# Selecting n data points whose average is nearly as good as the mean
	2	+
	3	+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.
	4	+
	5	+## Problem
	6	+
	7	+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
	8	+
	9	+$$L_D(h) = \frac{1}{N} \sum_{i=1}^{N} \\| h - z_i \\|^2 ,$$
	10	+
	11	+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
	12	+
	13	+$$F(d, n) = \sup_{D \subset \mathbb{R}^d} \frac{L^\star_D(n)}{L^\star_D} .$$
	14	+
	15	+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.
	16	+
	17	+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)$.
	18	+
	19	+## Background
	20	+
	21	+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.
	22	+
	23	+## What is known
	24	+
	25	+- On the line. $F(1, n) = 2n/(2n-1)$ [2]. The extreme dataset is $2n - 1$ copies of $0$ and one copy of $1$.
	26	+- 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$.
	27	+- 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].
	28	+- 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$.
	29	+- 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].
	30	+
	31	+## What would count as progress
	32	+
	33	+- 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.
	34	+- 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$.
	35	+- The behavior of $n\,(F(2, n) - 1)$ as $n \to \infty$; by the bounds above it lies between $n/(2n-1)$ and $1$.
	36	+
	37	+## References
	38	+
	39	+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](https://proceedings.mlr.press/v291/hanneke25e.html)
	40	+2. S. Hanneke, S. Moran, A. Shlimovich and A. Yehudayoff, Data selection for ERMs, COLT 2025, PMLR 291 (2025), 2634–2665. [arXiv:2504.14572](https://arxiv.org/abs/2504.14572)
	41	+3. G. Zhang, Exact risk ratios for weighted data selection in linear regression, preprint (2026). [arXiv:2608.28007](https://arxiv.org/abs/2608.28007)
	42	+4. D. Feldman, Introduction to core-sets: an updated survey, preprint (2020). [arXiv:2011.09384](https://arxiv.org/abs/2011.09384)
	43	+
	44	+## Source
	45	+
	46	+Imported from [COLT open problems, COLT 2025](https://proceedings.mlr.press/v291/hanneke25e.html), 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.