提出高斯分布下半空间可靠学习的新算法，显著降低误差与计算成本。
Reliable Learning of Halfspaces under Gaussian Marginals
- 设计新算法，实现高斯半空间的可靠学习
- 样本与计算复杂度达 d^{O(log(1/α))} 级别，误差ε极低
- 揭示可靠学习与标准学习的计算本质差异
研究在高斯边际下半空间的可靠近似正确（PAC）学习问题。该模型适用于某类错误代价更高的学习场景。本文提出一种新算法，可在维度d的高斯半空间上实现可靠学习，其样本与计算复杂度为 d^{O(log(min{1/α,1/ε}))} · min(2^{log(1/ε)^{O(log(1/α))}}, 2^{poly(1/ε)})，其中ε为超额误差，α为最优半空间的偏差。进一步给出统计查询下界，表明d^{Ω(log(1/α))}的依赖关系已最优。结果表明，在高斯设定下，可靠近似学习与标准近似学习存在强计算分离。
原文摘要 · Abstract (English)
We study the problem of PAC learning halfspaces in the reliable agnostic model of Kalai et al. (2012). The reliable PAC model captures learning scenarios where one type of error is costlier than the others. Our main positive result is a new algorithm for reliable learning of Gaussian halfspaces on $\mathbb{R}^d$ with sample and computational complexity $$d^{O(\log (\min\{1/α, 1/ε\}))}\min (2^{\log(1/ε)^{O(\log (1/α))}},2^{\mathrm{poly}(1/ε)})\;,$$ where $ε$ is the excess error and $α$ is the bias of the optimal halfspace. We complement our upper bound with a Statistical Query lower bound suggesting that the $d^{Ω(\log (1/α))}$ dependence is best possible. Conceptually, our results imply a strong computational separation between reliable agnostic learning and standard agnostic learning of halfspaces in the Gaussian setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。