Forster Decomposition and Learning Halfspaces with Noise
Forster Decomposition and Learning Halfspaces with Noise
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;D. Kane;Christos Tzamos
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Christos Tzamos
福斯特变换是一种将分布变成具有良好抗浓缩特性的操作。虽然福斯特变换并不总是存在，但我们表明，任何分布都可以有效地分解为几乎没有分布的混合物，并且可以有效地计算出福斯特变换的分布。作为该结果的主要应用，我们获得了第一种多项式时间算法，用于与具有强度多项式样品复杂性的Massart噪声模型中半个空格的分布无关PAC学习，即与示例的位复杂性无关。此学习问题的先前算法以比特复杂性多个单位缩放样本复杂性，即使这种依赖性在理论上不需要信息。
A Forster transform is an operation that turns a distribution into one with good anti-concentration properties. While a Forster transform does not always exist, we show that any distribution can be efficiently decomposed as a disjoint mixture of few distributions for which a Forster transform exists and can be computed efficiently. As the main application of this result, we obtain the first polynomial-time algorithm for distribution-independent PAC learning of halfspaces in the Massart noise model with strongly polynomial sample complexity, i.e., independent of the bit complexity of the examples. Previous algorithms for this learning problem incurred sample complexity scaling polynomially with the bit complexity, even though such a dependence is not information-theoretically necessary.