The Teaching Dimension of Regularized Kernel Learners

Hong Qian, Xu-Hui Liu, Chen-Xi Su, Aimin Zhou, Yang YuICML 2022 · OpenReview

Introduction

In traditional machine learning, the core question is: "Given this dataset, what is the best model?" Machine Teaching (MT) flips this paradigm on its head, asking: "Given a target model, what is the smallest set of data needed to train a learner to reach it?"

The "cost" of this teaching process is measured by the Teaching Dimension (TD), which represents the minimum number of examples required. While the teaching dimension for simple linear models is well understood, non-linear models—such as those utilizing Gaussian kernels—pose a significant challenge. Previous research suggested that teaching these complex models requires a prohibitive amount of data, or might even be impossible with a finite set of examples.

This paper investigates a compelling workaround: whether regularization (the standard practice of adding a penalty for model complexity) can act as a "shortcut" to make teaching non-linear models highly efficient.

The STARKE Framework

To analyze the teaching dimension of regularized kernel learners, the authors introduce a novel theoretical framework called STARKE (Subset Analysis and Extension technique).

  1. Subset Analysis: The researchers begin by analyzing teaching within a finite-dimensional subset of the model's possible hypotheses. They derive exact teaching sets for two common loss functions: Square loss (used in regression) and Hinge loss (used in classification).
  2. Extension: Leveraging the strong representation ability of these subsets, they extend their findings to the full, potentially infinite-dimensional model space, known as the Reproducing Kernel Hilbert Space (RKHS).
  3. $\epsilon$-Approximate Teaching: For models where exact teaching is theoretically impossible (like Gaussian kernels), the framework calculates the $\epsilon$-approximate TD—the number of examples needed to get the learner within a tiny error margin ($\epsilon$) of the target.
The STARKE framework illustrates how researchers move from analyzing subsets to the full model space.

Why Regularization Works

Regularization is typically viewed as a tool to prevent overfitting, but in the context of machine teaching, it acts as an inductive bias. It gives the learner a "preference" for simpler models. A teacher can exploit this preference to point the learner toward the target hypothesis using far fewer examples.

Without regularization, a learner might see a gap between teaching examples and remain uncertain about exactly where to place the decision boundary. Regularization "pulls" the boundary toward a specific, predictable spot (usually the one with the smallest norm). Because the learner's behavior becomes predictable, a single, well-placed example can often define the entire target.

Comparison of teaching a 1D classifier with and without regularization.

Key Results

The paper's primary contribution is proving that regularization drastically slashes the teaching dimension:

  • The Power of One (Linear Kernels): For linear learners, adding regularization reduces the teaching dimension from $d$ (the number of features) down to exactly 1.
  • Breaking the Infinite Barrier (Gaussian Kernels): For Gaussian kernels, which theoretically require infinite examples for exact teaching, regularization allows for approximate teaching with exponentially lower complexity. The $\epsilon$-approximate TD drops from a complex function of dimensions ($d^{O(\log^2(1/\epsilon))}$) to a simple $O(1/\epsilon^2)$, which is entirely independent of the input dimension $d$.

These theoretical findings were validated empirically across a mix of synthetic (e.g., Sine wave, Two-moon) and real-world datasets (e.g., MPG, Adult census data, Sonar). In all experiments, regularized learners reached target accuracy significantly faster, often achieving near-zero error with just a handful of examples.

Limitations and Future Work

While groundbreaking, the study acknowledges a few limitations:

  • Loss Function Scope: The current framework focuses on Square and Hinge loss. Extending this to other popular functions, like Logistic or Perceptron loss, remains a target for future research.
  • Teaching Set Constraints: The theory assumes the teacher can synthesize any arbitrary point in the input space as a teaching example. In practical scenarios (like teaching a human or a physical robot), the teacher might be restricted to a specific pool of naturally occurring examples.
  • Optimization Dominance: For certain loss functions, regularization might become too dominant, potentially preventing the model from learning specific hypotheses. Balancing this regularization power is an important next step.

Summary updated

Abstract

Teaching dimension (TD) is a fundamental theoretical property for understanding machine teaching algorithms. It measures the sample complexity of teaching a target hypothesis to a learner. The TD o...
BibTeX
@inproceedings{qian2022teaching,
  author = {Hong Qian and Xu-Hui Liu and Chen-Xi Su and Aimin Zhou and Yang Yu},
  title = {{The Teaching Dimension of Regularized Kernel Learners}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=Bs8jLrxyUiJ},
}
Figure