Can Local Regularization Learn All Multiclass Problems?

Let $X$ be a domain, $Y$ a label set, and $\mathcal H\subseteq Y^X$. For a sample $S$, write $\mathcal H_S(0)$ for the hypotheses of zero empirical error. A local regularizer is a map $\rho\colon\mathcal H\times X\to\mathbb R_{\geq0}$; it induces any learner $A$ satisfying

$$A(S)(x)\in\{h(x):h\in\arg\min_{g\in\mathcal H_S(0)}\rho(g,x)\}.$$

The regularizer learns $\mathcal H$ if every learner it induces is a PAC learner for $\mathcal H$.

1. In multiclass classification, can every learnable hypothesis class be learned by a local regularizer? If so, can this be done with optimal or nearly optimal sample complexity?

2. Can the specific learnable class $\mathcal H_\triangle$ constructed in the source---using triples of finite subsets $A,B,C\subseteq X$ with equal size and pairwise intersections of half that size---be learned by a local regularizer? If so, with optimal or nearly optimal sample complexity?