Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample consistent with the sample, and this principle characterizes multiclass PAC learnability is negative.
Abstract
Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--Shalev-Shwartz dimension at most two with realizable PAC sample complexity \[ O\!\left(\frac{1}{\varepsilon}\log\frac{1}{\delta}\right), \] that no local regularizer learns. Hypotheses are edges of complete graphs and instances are tournaments. At a test tournament, the scores fix an edge ranking while the training sample independently removes competitors. Cyclic triangles force enough inversions that surviving competitors produce constant population error at arbitrarily large sample sizes.
It is proved that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension $d$, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019).
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk...
Xiao-Yu Li, Andi Han, Jiao-Jiao Jiang et al.· 1 citation
We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthe...
This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.
Infinite-width limits are a standard way to reason about neural networks, but it is not automatic that the limiting learner has the same complexity-theoretic inductive bias as large finite networks. We study this question for Bayesian neural networks at the mean-field, or critical feature-learning, scaling. The central...
Invertible Logits Transformation (InvLT), which applies a learned scalar MLP element-wise to the pre-softmax logits, consistently outperforms a broad set of post-hoc baselines on standard calibration metrics.
Lening Zhao, Qipeng Zhan, Li Shen· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
