# A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning

arXiv: https://arxiv.org/abs/2212.03008 · HTML: https://mlsanity.com/paper/2212.03008/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 61 references that are in the map.
- First posted on arXiv 6 Dec 2022.

## Builds on (most cited first, 18 of 18)

- [Distribution-Independent PAC Learning of Halfspaces with Massart Noise](https://mlsanity.com/paper/1906.10075/) (2019)
- [Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2012.09720/) (2020)
- [Cryptographic Hardness of Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2207.14266/) (2022)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise](https://mlsanity.com/paper/2201.09818/) (2022)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing](https://mlsanity.com/paper/1804.01076/) (2018)
- [Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling](https://mlsanity.com/paper/1607.06711/) (2016)
- [Efficient algorithms for tensor scaling, quantum marginals and moment polytopes](https://mlsanity.com/paper/1804.04739/) (2018)
- [On Radial Isotropic Position: Theory and Algorithms](https://mlsanity.com/paper/2005.04918/) (2020)
- [Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers](https://mlsanity.com/paper/2009.04942/) (2020)
- [A Simpler and Faster Strongly Polynomial Algorithm for Generalized Flow Maximization](https://mlsanity.com/paper/1611.01778/) (2016)
- [The Paulsen Problem Made Simple](https://mlsanity.com/paper/1809.04726/) (2018)
- [A strongly polynomial algorithm for generalized flow maximization](https://mlsanity.com/paper/1307.6809/) (2013)
- [Recent progress on scaling algorithms and applications](https://mlsanity.com/paper/1808.09669/) (2018)
- [A Strongly Polynomial Algorithm for Linear Exchange Markets](https://mlsanity.com/paper/1809.06266/) (2018)
- [A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix](https://mlsanity.com/paper/1912.06252/) (2019)

## Built on by (most cited first, 11 of 11)

- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Efficient Discrepancy Testing for Learning with Distribution Shift](https://mlsanity.com/paper/2406.09373/) (2024)
- [A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise](https://mlsanity.com/paper/2501.09691/) (2025)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Do PAC-Learners Learn the Marginal Distribution?](https://mlsanity.com/paper/2302.06285/) (2023)
- [Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise](https://mlsanity.com/paper/2502.11413/) (2025)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)
- [Self-Directed Linear Classification](https://mlsanity.com/paper/2308.03142/) (2023)
- [Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift](https://mlsanity.com/paper/2605.07005/) (2026)

## Abstract (arXiv)

The Forster transform is a method of regularizing a dataset by placing it in em radial isotropic position while 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 given em weakly polynomial time algorithms for computing Forster transforms, when they exist. Our main result is the first em strongly polynomial time algorithm 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 for em distribution-free PAC learning of halfspaces. This learning result is surprising because em proper PAC learning of halfspaces is em equivalent to 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.