Research map / Learning theory and algorithms / Sample complexity
Estimating Learnability in the Sublinear Data Regime
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Estimate unexplained variance directly instead of fitting the linear predictor | Linear regression with isotropic covariance · Isotropic covariance regression | sample complexity for learnability estimation: O(√d) samples; fitting the best-fit function requires on the order of d samples | Helped |
| Extend the estimator to unknown non-isotropic covariance with bounded condition number | Linear regression · Unknown non-isotropic covariance regression, bounded condition number | sample complexity for noise-variance estimation to error ε: n=O(d^{1-1/log{1/ε}}) | Helped |
| Use the non-isotropic estimator without a covariance condition-number bound | Linear regression · Unknown non-isotropic covariance regression, no condition-number bound | sample complexity for noise-variance estimation to error ε: n=O(d^{1-√ε}) | Helped |
| Apply the isotropic estimator without assuming a linear-plus-independent-noise label model | Best linear predictor · Agnostic regression, isotropic covariance | estimation error: O(C\frac{\sqrt{d+n}}{\tau n}) | Helped |
| Apply learnability estimation to logistic-model binary classification | Best linear classifier · Binary classification, isotropic Gaussian | sample complexity for estimating classification error: O(√d) samples | Helped |
| Estimate higher covariance moments and combine them to approximate the first moment | Learnability estimator for non-isotropic regression · Unknown non-isotropic covariance regression | estimation error: O(1/k^2); O(e^{-(k-1)√b}) when covariance eigenvalues lie in [b,1] | Helped |
| Use the learnability estimator without bounds on covariance magnitude or signal norm | Linear regression · Arbitrary covariance with no norm bounds | samples required for sublinear estimation: c·d | Hurt |
| Estimate learnability when signal depends on directions of extremely small variance | Non-isotropic learnability estimator · Heavy-tailed covariance spectra | ability to capture signal | Hurt |
Closest papers by meaning
- Practical estimation of the optimal classification error with soft labels and calibration (ICLR 2026 · similarity 0.87)
- Towards a statistical theory of data selection under weak supervision (ICLR 2024 · similarity 0.87)
- Exploiting Class Learnability in Noisy Data (AAAI 2019 · similarity 0.87)
- Leveraging Data Symmetries to Select an Optimal Subset of Training Data under Label Noise (NeurIPS 2026 · similarity 0.86)
- Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification (NeurIPS 2026 · similarity 0.85)
- Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.