改进高斯分布下概念类学习的复杂度上界，逼近最优。
Agnostic learning in (almost) optimal time via Gaussian surface area
- 用高斯表面面积分析学习复杂度，改进多项式阶数上界。
- 将多项式阶数从 $O(Γ^2 / ε^4)$ 降低至 $\tilde O(Γ^2 / ε^2)$。
- 适用于多项式阈值函数学习，接近理论最优，适合理论学习研究者。
在困难的近似模型中，基于高斯边缘学习概念类的复杂度与其在 $L_1$ 范数下被低次多项式逼近的能力密切相关。Klivans 等人（2008）证明，对于高斯表面面积不超过 $Γ$ 的任意概念类，次数 $d = O(Γ^2 / ε^4)$ 的多项式即可实现 $ε$-近似。该结果给出了多种概念类学习复杂度的最佳已知上界。本文通过改进其分析，证明 $d = \tilde O(Γ^2 / ε^2)$ 已足够。结合 Diakonikolas 等人（2021）的下界，这一结果在统计查询模型中为多项式阈值函数的近似学习提供了（近）最优复杂度界。证明方法借鉴了 Feldman 等人（2020）在布尔超立方体上的构造，建立了直接类比。
原文摘要 · Abstract (English)
The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its $L_1$-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most $Γ$, Klivans et al. (2008) show that degree $d = O(Γ^2 / \varepsilon^4)$ suffices to achieve an $\varepsilon$-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree $d = \tilde O (Γ^2 / \varepsilon^2)$ is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered $L_1$-approximation on the Boolean hypercube.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。