Data-efficient learning · Statistical learning theory · Embeddings & representations / Open question
Learning from the Fewest Labels
The most useful next example depends on what the learner already understands. Data-efficient learning must learn that notion of usefulness as well as the task.
Seed catalog · Showing the bundled record.
Problem statement
For , let the clean label be with unknown orthonormal , fixed and label-flip probability at most . An active learner may query labels only on a supplied i.i.d. pool. Determine label, pool-size and computational requirements for classification error at most above the noise floor, including the cost of recovering useful latent directions, and compare with passive sampling on the same model.
Assumptions and scope
- Fix the input/task family, pool access, noise model and allowed representation class; label queries on existing points and synthetic membership queries are different resources.
- Charge representation pretraining and all queried labels. Do not assume a task-aligned embedding or decision boundary is supplied at no cost.
- Specify the population or transductive objective and margin/disagreement structure; arbitrary finite pools can force querying nearly every point.
What would settle it?
Matching label-complexity bounds and a computationally justified active representation-learning procedure for a declared family, with a separation from passive sampling or an impossibility regime.
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
No-synthesis active halfspace bounds, optimal decision-stump queries and AGOP representation recovery are known. The target couples nonlinear representation discovery to costed adaptive labels, rather than claiming active learning or sample-efficient features are new. This is an editorial, source-motivated research target. 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
- Black et al. — Actively Learning Halfspaces without Synthetic Data ↗partial theory · source checked 2026-11-19
Publisher abstract checked: no-synthesis lower bound for arbitrary pools, optimal known-direction/decision-stump results and near-optimal noisy PAC bounds. Point synthesis and label queries on existing data are distinct access models.
- Zhu et al. — Average Gradient Outer Product in Kernel Regression Provably Recovers the Central Subspace for Multi-Index Models ↗partial theory · source checked 2026-11-19
Primary abstract checked: AGOP subspace recovery can require fewer samples than accurate fixed-kernel prediction when low-degree components expose all relevant directions. This is an established representation/prediction separation.
- Cheng et al. — Exact Dynamics and Finite-Sample Trajectory Recovery of Linear Recursive Feature Machines ↗partial theory · source checked 2026-11-19
Primary abstract checked: regularized noisy multi-output linear RFM trajectories remain close to an infinite-data reference at every iteration under stated sub-Gaussian assumptions.