# Estimating Learnability in the Sublinear Data Regime

arXiv: https://arxiv.org/abs/1805.01626 · HTML: https://mlsanity.com/paper/1805.01626/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2018.

## Built on by (most cited first, 10 of 10)

- [Active Fairness Auditing](https://mlsanity.com/paper/2206.08450/) (2022)
- [A Query-Optimal Algorithm for Finding Counterfactuals](https://mlsanity.com/paper/2207.07072/) (2022)
- [Universal and data-adaptive algorithms for model selection in linear contextual bandits](https://mlsanity.com/paper/2111.04688/) (2021)
- [Data Budgeting for Machine Learning](https://mlsanity.com/paper/2210.00987/) (2022)
- [Are all models wrong? Fundamental limits in distribution-free empirical model falsification](https://mlsanity.com/paper/2502.06765/) (2025)
- [A Data-driven feature selection and machine-learning model benchmark for the prediction of longitudinal dispersion coefficient](https://mlsanity.com/paper/2107.12970/) (2021)
- [Estimating Optimal Policy Value in General Linear Contextual Bandits](https://mlsanity.com/paper/2302.09451/) (2023)
- [FSDR: A Novel Deep Learning-based Feature Selection Algorithm for Pseudo Time-Series Data using Discrete Relaxation](https://mlsanity.com/paper/2403.08403/) (2024)
- [On computing and the complexity of computing higher-order U-statistics, exactly](https://mlsanity.com/paper/2508.12627/) (2025)
- [Bridging Lifelong and Multi-Task Representation Learning via Algorithm and Complexity Measure](https://mlsanity.com/paper/2511.01847/) (2025)

## Abstract (arXiv)

We consider the problem of estimating how well a model class is capable of fitting a distribution of labeled data. We show that it is often possible to accurately estimate this "learnability" even when given an amount of data that is too small to reliably learn any accurate model. Our first result applies to the setting where the data is drawn from a d-dimensional distribution with isotropic covariance (or known covariance), and the label of each datapoint is an arbitrary noisy function of the datapoint. In this setting, we show that with O(√d) samples, one can accurately estimate the fraction of the variance of the label that can be explained via the best linear function of the data. In contrast to this sublinear sample size, finding an approximation of the best-fit linear function requires on the order of d samples. Our sublinear sample results and approach also extend to the non-isotropic setting, where the data distribution has an (unknown) arbitrary covariance matrix: we show that, if the label y of point x is a linear function with independent noise, y = langle x , β rangle + noise with |β | bounded, the variance of the noise can be estimated to error ε with O(d^1-1/log1/ε) if the covariance matrix has bounded condition number, or O(d^1-√ε) if there are no bounds on the condition number. We also establish that these sample complexities are optimal, to constant factors. Finally, we extend these techniques to the setting of binary classification, where we obtain analogous sample complexities for the problem of estimating the prediction error of the best linear classifier, in a natural model of binary labeled data. We demonstrate the practical viability of our approaches on several real and synthetic datasets.