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.
翻译:福斯特变换是一个将分布转换成具有良好的抗浓缩特性的操作。 虽然福斯特变换并不总是存在, 但我们显示, 任何分布可以有效地分解为少数分布的脱节混合体, 其中福斯特变换存在并且可以有效计算。 作为这一结果的主要应用, 我们获得了第一个多球时算法, 用于在Massart噪音模型中以强烈的多球体样本复杂性( 即独立于这些实例的比特复杂性) 学习半空进行分配独立的 PAC 学习。 这个学习问题的先前算法都产生了样本复杂性, 与比特复杂性同时缩放, 尽管这种依赖性在信息- 理论上并不必要 。