提出离散域半空间平滑学习新框架，实现高效可学习性突破。
Smoothed Agnostic Learning of Halfspaces over the Hypercube
- 用随机比特翻转模拟平滑扰动，构建离散版平滑学习模型
- 在弱指数假设下，运行时间和样本复杂度为 n^{poly(1/(σε))}
- 首个针对布尔超立方体的高效平滑学习算法，适合实际离散数据
布尔半空间的抗噪声学习是计算学习理论中的基本问题，但即使弱学习也被证明是计算困难的。近期工作[CKKMK24]提出平滑分析作为绕过此类难题的方法，但现有框架依赖加性高斯扰动，不适用于离散域。本文引入一种新的布尔输入平滑抗噪声学习框架，其中扰动通过随机比特翻转建模，定义了高斯情形的自然离散类比。在输入分布满足严格亚指数假设的前提下，我们给出一个高效算法，其运行时间与样本复杂度约为 n^{poly(1/(σ·ε))}。此前此类算法仅在强结构性假设（如坐标独立或对称分布）下成立。本结果首次为布尔超立方体上的平滑抗噪声半空间学习提供了计算上高效的保证，弥合了最坏情况不可行性与实际可学习性之间的差距。
原文摘要 · Abstract (English)
Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [CKKMK24] proposed smoothed analysis as a way to bypass such hardness, but existing frameworks rely on additive Gaussian perturbations, making them unsuitable for discrete domains. We introduce a new smoothed agnostic learning framework for Boolean inputs, where perturbations are modeled via random bit flips. This defines a natural discrete analogue of smoothed optimality generalizing the Gaussian case. Under strictly subexponential assumptions on the input distribution, we give an efficient algorithm for learning halfspaces in this model, with runtime and sample complexity approximately n raised to a poly(1/(sigma * epsilon)) factor. Previously, such algorithms were known only with strong structural assumptions for the discrete hypercube, for example, independent coordinates or symmetric distributions. Our result provides the first computationally efficient guarantee for smoothed agnostic learning of halfspaces over the Boolean hypercube, bridging the gap between worst-case intractability and practical learnability in discrete settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。