Teacher Improves Learning by Selecting a Training Subset

Yuzhe Ma, Robert Nowak, Philippe Rigollet, Xuezhou Zhang, Xiaojin Zhu

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 of a Gaussian mean and the hard-margin support vector machine. For more complex learners, we formulate super-teaching as a mixed-integer nonlinear program and demonstrate significant error reduction on logistic and ridge regression.

Introduction

Standard machine learning paradigms operate under the assumption that more data is inherently better. As we collect more independent and identically distributed (iid) data, model error is expected to converge toward zero. However, this paper introduces the concept of super-teaching, which challenges this assumption. In super-teaching, a teacher who possesses knowledge of the "ground truth" target parameters $\theta^*$ selects a specific subset of a training set $S$ to help a learner achieve higher accuracy than they would using the entire dataset.

This approach differs from traditional coreset or data reduction methods. While those methods aim to maintain performance with less data, super-teaching leverages the teacher's knowledge to "encode" the solution into the data subset, effectively canceling out the noise inherent in iid samples.

Methods

The research employs both theoretical analysis and algorithmic optimization to explore super-teachability.

Theoretical Analysis

The authors provide proofs for two fundamental learners:

  1. Gaussian Mean Estimation: While the standard error for a Gaussian mean typically shrinks at a rate of $1/\sqrt{n}$, a teacher selecting the optimal $k$ points can achieve an error rate of $O(n^{-k})$.
  2. 1D Large Margin Classifier (SVM): By selecting the "most symmetric pair" of points relative to the decision boundary, the error rate improves from $O(1/n)$ to $O(1/n^2)$.

The MINLP Algorithm

To address general learners like Logistic or Ridge Regression, the problem is framed as a bilevel optimization: minimizing the learner's risk where the learner's output depends on the chosen subset. The authors transform this into a Mixed-Integer Nonlinear Program (MINLP) by replacing the learner's optimization problem with its Karush-Kuhn-Tucker (KKT) first-order optimality conditions. The NEOS solver is then utilized to determine the optimal binary indicators for data inclusion.

Results

The experimental results validate the super-teaching hypothesis across various synthetic datasets, including 1D intervals and $d$-dimensional Gaussian distributions.

Visualization of Super-Teaching

The impact of subset selection is most visible in the alignment of decision boundaries. As shown in Figure 3, the "super-taught" model's decision boundary (solid line) aligns much more closely with the ground truth than the model trained on the full iid set (dashed line).

Comparison of decision boundaries for logistic and ridge regression. The solid line represents the super-taught model, which closely matches the ground truth, while the dashed line shows the skew from the full iid set.

Quantitative Performance

The "super-teaching ratio" ($c_n$), defined as the ratio of the subset's error to the full set's error, demonstrates massive error reduction. In many simulations, $c_n$ was found to be below 0.01, indicating that the subset-trained model was over 100 times more accurate than the full-set model.

Performance metrics for super-teaching across different training set sizes ($n$). The table shows the super-teaching ratio ($c_n$), the fraction of the subset size ($|B(S)|/n$), and the computation time.

Interestingly, the optimal subset size is not always minimal. In higher-dimensional problems, the solver often selected between 50% and 80% of the data (as seen in the $|B(S)|/n$ column of the table), suggesting that super-teaching is about strategic selection rather than simple sparsification.

Discussion and Limitations

While the results are promising, several challenges remain:

  • Computational Complexity: The MINLP formulation is NP-hard. Solving for $n=1024$ points takes approximately 30 minutes, necessitating faster heuristic solvers for large-scale applications.
  • Teacher Requirements: The framework assumes the teacher has perfect knowledge of the ground truth $\theta^*$ and the learner's internal mechanics (loss function, regularization). In practice, teachers may only have noisy estimates or incomplete knowledge of the learner.
  • Future Directions: Identifying the optimal subset size $k$ for a given problem remains an open challenge, as current analysis largely treats $k$ as a fixed parameter.

The authors conjecture that any learner satisfying "asymptotic normality" is likely to be super-teachable, opening a broad path for future research in machine teaching.

Summary updated

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 ...
BibTeX
@inproceedings{ma2018teacher,
  author = {Yuzhe Ma and Robert Nowak and Philippe Rigollet and Xuezhou Zhang and Xiaojin Zhu},
  title = {{Teacher Improves Learning by Selecting a Training Subset}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=14waPTddXq},
}

Loading related content...

Figure