Statistical learning theory · Data-efficient learning / Open question
How Little Training Data Is Enough?
Data curation can be more valuable than changing the optimizer. Even linear regression leaves sharp questions about how much performance a carefully chosen tiny dataset can preserve.
Seed catalog · Showing the bundled record.
Problem statement
Determine the sharp worst-case full-data loss ratio when a fixed minimum-Frobenius-norm linear-regression learner is trained on at most nonnegatively weighted examples selected from a finite dataset in . Target the unresolved intermediate budgets between the spanning budget and the exact-recovery threshold .
Assumptions and scope
- The selector sees the full dataset, but must transmit selected original examples and nonnegative weights; the learner minimizes the weighted squared loss with the specified min-norm tie-break.
- Evaluate the learned predictor on the original uniformly weighted dataset; restrict the loss ratio to datasets with positive optimal loss and treat exact-fit datasets separately.
- Fix d, m and n before taking the supremum over dataset sizes and values. Weighted selection, unweighted selection and unrestricted decoder compression are different problems.
What would settle it?
Matching upper and lower bounds for the intermediate selection profile, ideally a formula in d, m and n; exact unresolved low-dimensional cells provide concrete milestones.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
The COLT 2025 note poses the profile questions. Zhang's 2026 papers claim the vector exact-recovery threshold, near-threshold formula and several scalar cells. For example, the reported (d,m,n)=(2,2,3) interval remains [13/8,15/8]. Those solved thresholds are baselines, not the target. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Hanneke et al. — Open Problem: Data Selection for Regression Tasks ↗problem statement · source checked 2026-11-19
PDF Sections 2–4 checked: fixed min-norm ERM, weighted and unweighted selection, full-dataset loss ratios. Scalar weighted endpoints are known; subsequent 2026 work settles further cells and the vector exact-recovery threshold.
- Zhang — Exact Risk Ratios for Weighted Data Selection in Linear Regression ↗partial theory · source checked 2026-11-19
Primary search abstract checked: near-threshold scalar formula and several small cells proved; a balanced-partition lower bound is conjectured exact in the remaining scalar regime.
- Zhang — Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression ↗partial theory · source checked 2026-11-19
Primary search abstract checked: exact threshold (m+1)d and near-threshold value; (d,m,n)=(2,2,3) remains between 13/8 and 15/8, and (2,2,4) between 5/4 and 3/2. The sharp intermediate profile remains a target.