局部正则化无法刻画多分类PAC可学习性，反例显示其在特定场景下失效。
Local Regularization Does Not Characterize Multiclass PAC Learnability
- 用测试点依赖的分数选择假设，训练时仅保留与样本一致的解。
- 存在可实现的多分类问题，样本复杂度为O(1/ε·log(1/δ))，但无局部正则化能学习。
- 反例基于完全图边与竞赛图实例，循环三角形导致错误率恒定，不随样本量下降。
局部正则化通过为每个假设分配依赖于测试点的得分，并选择与样本一致的最小得分假设进行预测。Asilis等人提出该原则是否能刻画多分类PAC可学习性。本文给出否定回答：存在一个可数类，Daniely--Shalev-Shwartz维度至多为2，且在可实现情形下样本复杂度为O(1/ε · log(1/δ))，但没有任何局部正则化方法能够学习它。假设是完全图的边，实例是竞赛图。在测试竞赛图上，得分确定一条边的排名，而训练样本独立地移除竞争者。循环三角形引发足够多的逆序，导致幸存的竞争者始终产生常数级别的总体误差，即使样本规模无限增大。
原文摘要 · Abstract (English)
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}δ\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。