A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
复制标题
一种近似福斯特变换的强多项式算法及其在半空间学习中的应用
DOI：
10.1145/3564246.3585191
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Kane, Daniel M.
中科院分区：
文献类型：
--
作者：
Diakonikolas, Ilias;Tzamos, Christos;Kane, Daniel M.
Forster变换是一种通过将数据集置于径向各向同性位置而使其正则化的方法，同时保持其一些基本属性。福斯特变换在横跨计算机科学和泛函分析的各种环境中发挥了关键作用。以前的工作给出了计算Forster变换的弱多项式时间算法，如果它们存在的话。我们的主要结果是第一个计算给定数据集的近似Forster变换或证明不存在这样的变换的强多项式时间算法。利用我们的强多项式Forster算法，我们得到了第一个用于分布的强多项式时间算法--半空间的自由PAC学习。这个学习结果令人惊讶，因为半空间的适当的PAC学习等价于线性规划。我们的学习方法扩展到在存在随机分类噪声和更一般的Massart噪声的情况下给出一个强多项式半空间学习器。
The Forster transform is a method of regularizing a dataset by placing it inradial isotropic positionwhile maintaining some of its essential properties. Forster transforms have played a key role in a diverse range of settings spanning computer science and functional analysis. Prior work had givenweaklypolynomial time algorithms for computing Forster transforms, when they exist. Our main result is the firststrongly polynomial timealgorithm to compute an approximate Forster transform of a given dataset or certify that no such transformation exists. By leveraging our strongly polynomial Forster algorithm, we obtain the first strongly polynomial time algorithm fordistribution-freePAC learning of halfspaces. This learning result is surprising becauseproperPAC learning of halfspaces isequivalentto linear programming. Our learning approach extends to give a strongly polynomial halfspace learner in the presence of random classification noise and, more generally, Massart noise.
登录
查看更多内容
一类可分离凸目标最小成本流问题的强多项式算法
DOI：
--
发表时间：
2011
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
László A. Végh
通讯作者：
László A. Végh
通过感知器在多项式时间内学习噪声感知器
DOI：
10.1109/sfcs.1997.646140
发表时间：
1997
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
E. Cohen
通讯作者：
E. Cohen
一种近似混合判别式和混合体积的确定性算法以及组合推论
影响因子：
0.8
作者：
L. Gurvits;Alex Samorodnitsky
通讯作者：
Alex Samorodnitsky
Paulsen 问题、连续算子缩放和平滑分析
DOI：
10.1145/3188745.3188794
发表时间：
2017
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
T. C. Kwok;L. Lau;Y. Lee;Akshay Ramachandran
通讯作者：
Akshay Ramachandran
一种线性规划的缩放不变算法，其运行时间仅取决于约束矩阵
影响因子：
2.7
作者：
D. Dadush;Sophie Huiberts;Bento Natura;L. V'egh
通讯作者：
L. V'egh