高效学习带间隔的多面体交集，时间复杂度逼近理论下限。
Tight Bounds for Learning Polyhedra with a Margin
- 基于间隔优化的算法，避免了指数级依赖于半空间数量或间隔大小。
- 在误差ε、间隔ρ下，运行时间仅指数依赖√n log(1/ρ)log k。
- 适用于连续分布，对机器学习与密码学均有理论意义。
我们提出一种针对具有ρ间隔的k个半空间交集进行PAC学习的算法，可在误差ε内完成学习，运行时间为poly(k, ε⁻¹, ρ⁻¹) · exp(O(√(n log(1/ρ) log k)))。该算法改进了以往工作在k或ρ⁻¹上的指数依赖，且在指数部分的对数因子上逼近已知密码学和统计查询模型的下界。算法进一步推广至多数点距离多面体边界至少ρ的情形，因而可应用于连续分布。
原文摘要 · Abstract (English)
We give an algorithm for PAC learning intersections of $k$ halfspaces with a $ρ$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)$. Notably, this improves on prior work which had an exponential dependence on either $k$ or $ρ^{-1}$ and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in $k$ and $ρ$ in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least $ρ$ from the boundary of the polyhedron, making it applicable to continuous distributions as well.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。