Abstract
We call a learner super-teachable if a teacher can trim down an iid training set while making the learner learn even better. We provide sharp super-teaching guarantees on two learners: the maximum likelihood estimator for the mean of a Gaussian, and the large margin classifier in 1D. For general learners, we provide a mixed-integer nonlinear programming-based algorithm to find a super teaching set. Empirical experiments show that our algorithm is able to find good super-teaching sets for both regression and classification problems.
Introduction
The standard paradigm in machine learning assumes that "more data is better," with error typically decreasing at a rate of $1/\sqrt{n}$ for i.i.d. datasets. This paper challenges that assumption by introducing the concept of "super-teaching." In this framework, a teacher who knows the ground truth ($\theta^*$) selects a specific subset of a training set to help a learner achieve higher accuracy than it would using the entire dataset. This curated approach allows learners to surpass standard statistical convergence rates, demonstrating that quality and strategic selection can outweigh quantity.
Theoretical Foundations
The authors provide mathematical guarantees for super-teaching in two fundamental scenarios:
- Gaussian Mean Estimation: By selecting the $k$ most informative points from $n$ samples, the learning rate improves from $O(n^{-1/2})$ to $O(n^{-k})$.
- 1D Large Margin Classifier (SVM): Selecting the "most symmetric pair" of points around the true decision boundary improves the risk from $O(n^{-1})$ to $O(n^{-2})$.
These results suggest that "super-teachability" may be linked to the property of asymptotic normality. In the SVM case, just two perfectly balanced points are more informative than a large set of random samples.
General Super-Teaching via Optimization
For more complex learners, such as those used in Logistic or Ridge Regression, the authors formulate super-teaching as a Mixed-Integer Non-Linear Programming (MINLP) problem. The teacher uses binary indicator variables to decide which data points to include in the subset. To ensure the learner's resulting model is optimal for that specific subset, the optimization incorporates Karush-Kuhn-Tucker (KKT) conditions.
Empirical Results
The MINLP algorithm was evaluated using synthetic datasets with high-dimensional Gaussian features. The experiments demonstrated that the "super-taught" models significantly outperformed those trained on full datasets.
In logistic regression simulations with $n=16$, the solver found subsets that were over 1,000 times more accurate than the full dataset (super-teaching ratio $c_n = 8.5 \times 10^{-4}$). These subsets typically comprised only about half of the available data points. Furthermore, the algorithm occasionally selected subsets smaller than the number of dimensions, effectively utilizing the learner's regularization to improve performance.
Discussion and Limitations
The authors define the Super-Teaching Ratio ($c_n$) to measure success; a ratio below 1 indicates that the teacher has successfully improved the learner's performance. While the results are promising, several challenges remain:
- Computational Cost: The MINLP solver is currently slow, taking approximately 30 minutes for a dataset of 1,024 points, which limits its scalability.
- Theoretical Scope: Current proofs are limited to simpler 1D or Gaussian models. Extending these to deep neural networks is a significant open challenge.
- Subset Size: The optimal size for the subset ($k$) must currently be pre-determined or searched for manually.
Future research will focus on improving the efficiency of the optimization process and testing the approach on real-world tasks, such as finding representative examples to interpret "black-box" models.
Summary updated