局部正则化无法解决所有可学习的多分类问题
Local Regularizers Are Not Transductive Learners
- 用密码学中的秘密共享原理构造反例
- 存在一个可学习的问题，局部正则化无法在转换模型中学习
- 对理论学习者有启发，适合研究学习算法边界
我们部分回答了Asilis等人（COLT 2024）提出的一个开放问题：局部正则化这一广义显式正则化（即结构风险最小化）的算法模板，是否足以学习所有可学习的多分类问题。具体而言，在转换学习模型下，我们给出了否定答案。我们构造了一个在转换和PAC模型下均可学习的多分类问题，但无法被任何局部正则化算法在转换模型中学习。该假设类及证明基于密码学中的秘密共享原理。我们概述了将该负结果推广至PAC模型的挑战，留出了局部正则化在PAC与转换模型之间可能存在分离的诱人可能性。
原文摘要 · Abstract (English)
We partly resolve an open question raised by Asilis et al. (COLT 2024): whether the algorithmic template of local regularization -- an intriguing generalization of explicit regularization, a.k.a. structural risk minimization -- suffices to learn all learnable multiclass problems. Specifically, we provide a negative answer to this question in the transductive model of learning. We exhibit a multiclass classification problem which is learnable in both the transductive and PAC models, yet cannot be learned transductively by any local regularizer. The corresponding hypothesis class, and our proof, are based on principles from cryptographic secret sharing. We outline challenges in extending our negative result to the PAC model, leaving open the tantalizing possibility of a PAC/transductive separation with respect to local regularization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。