Local Regularization Does Not Characterize Multiclass PAC Learnability

Technical Summary: Local Regularization Does Not Characterize Multiclass PAC Learnability

Problem Statement
A central question in statistical learning theory is identifying simple algorithmic principles that characterize the learnability of hypothesis classes. In binary classification, Empirical Risk Minimization (ERM) characterizes PAC learnability. However, the multiclass setting is more complex; proper learning can fail for learnable classes, and optimal learners often rely on sample-dependent structures rather than fixed hypothesis orderings.

Asilis et al. proposed local regularization as a potential generalization of ERM for the multiclass setting. A local regularizer assigns a fixed score $\psi(h, x)$ to every hypothesis $h$ at every test point $x$, independent of the training sample. A learner induced by such a regularizer predicts the label of the hypothesis with the minimum score among those consistent with the observed sample. While Jafar, Asilis, and Dughmi previously demonstrated that local regularization fails to characterize learnability in the transductive model (where a specific withheld point is tested), it remained an open question whether this principle characterizes PAC learnability, where the withheld point may carry negligible population mass and repeated sampling could theoretically reveal it.

Methodology and Construction
The paper constructs a counterexample using a countable hypothesis class based on tournaments (complete directed graphs).

• Hypothesis Class ($H$): For an integer $q \ge 3$, hypotheses correspond to edges of a complete graph $K_q$. A hypothesis $h_{q,e}$ predicts the "head" (target vertex) of edge $e$ within a tournament instance $\tau$.
• Instance Space: Instances are pairs $(q, \tau)$, where $\tau$ is a tournament on $q$ vertices.
• Hard Distributions: The authors define a family of "hard" distributions $D_{e,v}$ for a target edge $e=\{u,v\}$ and endpoint $v$. These distributions are uniform over tournaments where the edge $e$ is oriented toward $v$. Consequently, all observed labels in the training sample are identical: $(q, v)$.
• The Mechanism of Failure:
  1. Filtering: The training sample (all labels equal to $v$) filters the version space, retaining only hypotheses corresponding to edges incident to $v$ that are oriented toward $v$ in the sampled tournaments.
  2. Fixed Ranking: The local regularizer $\psi$ imposes a strict total ordering on the edges incident to $v$ at the test point before the sample is observed.
  3. Cyclic Inversions: The core difficulty arises from cyclic triangles in the tournament. Even if the training sample removes many competitors, the fixed ordering of the remaining edges can be "inverted" relative to the true target due to the cyclic structure. Specifically, if an outgoing edge (which should not be the target) survives the filtering process and appears earlier in the regularizer's fixed ranking than the true incoming target edge, the learner makes an error.

Key Contributions and Results

1. Existence of a Counterexample: The paper proves the existence of a countable multiclass hypothesis class $H$ that is PAC learnable but not learnable by any local regularizer.

   • Learnability: The class is PAC learnable with a sample complexity of $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. An explicit learner succeeds by identifying the target edge once both endpoint labels appear in the sample.
   • Dimension Bound: The class has a Daniely–Shalev-Shwartz (DS) dimension of at most 2. This is established by showing that the image of every hypothesis contains at most two labels, preventing the formation of a 3-dimensional pseudo-cube.

2. Impossibility Theorem: For any local regularizer $\psi$, there exists an induced learner $A_\psi$ that fails to PAC learn $H$.

   • Failure Mode: For any fixed regularizer, the authors show that for arbitrarily large sample sizes $n$, there exist realizable distributions where the probability of error exceeds a constant $\delta_0 = \frac{1}{192e}$.
   • Quantitative Bounds: The error probability is bounded away from zero ($\varepsilon_0 = \frac{1}{96e}$) because the expected number of "inversions" (outgoing edges ranked before incoming edges) in the tournament structure remains significant. The proof leverages the fact that a random tournament contains $\Theta(q^3)$ cyclic triangles, ensuring that for any strict ordering of edges, a constant fraction of target incidences will result in a prediction error.

Significance and Claims
The paper concludes that local regularization does not characterize realizable multiclass PAC learnability.

• Distinction from Transductive Results: Unlike the transductive lower bound by Jafar et al., which relies on a single withheld point with potentially negligible mass, this construction distributes the error across a population of tournaments. The failure persists even as sample sizes grow arbitrarily large, preventing the learner from "learning" the hidden structure through repeated sampling.
• Limitation of Fixed Scores: The result highlights a fundamental rigidity in local regularization: because the ranking of hypotheses at a test point is fixed prior to observing the sample, the learner cannot adapt the relative ordering of surviving competitors based on the specific structure of the training data. In the tournament setting, this inability to reorder leads to constant population error despite the class having low DS-dimension and being efficiently learnable by other means.
• Scope: The result applies specifically to regularizers where scores are fixed independently of the sample. It does not address unsupervised frameworks where the regularization rule might depend on the unlabeled sample.

In summary, the paper provides a definitive negative answer to the question of whether local regularization characterizes multiclass PAC learnability, demonstrating that even for classes with low combinatorial dimension (DS-dim $\le 2$) and optimal sample complexity, fixed-score regularizers can fail to learn.