Hardness of High-Dimensional Linear Classification
Not on the map. Why?
Abstract (arXiv)
We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem, which models linear classification. Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms. However, only O(nd) and respectively tilde O(1/varepsilond) upper bounds are known and complemented by polynomial lower bounds that do not support the exponential in dimension dependence. We close this gap up to polylogarithmic terms by reduction from widely-believed hardness conjectures for Affine Degeneracy testing and k-Sum problems. Our reductions yield matching lower bounds of tildeOmega(nd) and respectively tildeOmega(1/varepsilond) based on Affine Degeneracy testing, and tildeOmega(nd/2) and respectively tildeOmega(1/varepsilond/2) conditioned on k-Sum. The first bound also holds unconditionally if the computational model is restricted to make sidedness queries, which corresponds to a widely spread setting implemented and optimized in many contemporary algorithms and computing paradigms.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 21 of its 56 references that are in the map. First posted on arXiv 19 Mar 2026.
Builds on
21 of 56 references.
References · 21
- 2018Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clusteringcited by 94
- 2019Distribution-Independent PAC Learning of Halfspaces with Massart Noisecited by 54
- 2018Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimensioncited by 27
- 2016Approximate Sparse Linear Regressioncited by 8
- 2016Tight Hardness Results for Maximum Weight Rectanglescited by 6
- 2023Optimal Sketching Bounds for Sparse Linear Regressioncited by 6
- 2018Computing Approximate Statistical Discrepancycited by 5
- 2018Theorems of Carath'eodory, Helly, and Tverberg without dimensioncited by 4
- 2019Probabilistic smallest enclosing ball in high dimensions via subgradient samplingcited by 4
- 2023On Generalization Bounds for Projective Clusteringcited by 4
- 2024No Dimensional Sampling Coresets for Classificationcited by 4
- 2021Approximate Maximum Halfspace Discrepancycited by 3
9 more
- 2013Exact Weight Subgraphs and the k-Sum Conjecturecited by 2
- 2019Scalable Spatial Scan Statistics for Trajectoriescited by 2
- 2025Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curvescited by 2
- 2025Computational Complexity in Property Testingcited by 2
- 2015A Simple Algorithm for Maximum Margin Classification, Revisitedcited by 1
- 2019No-dimensional Tverberg Theorems and Algorithmscited by 1
- 2021Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Treescited by 1
- 2022Improved Algebraic Degeneracy Testingcited by 1
- 2023No-dimensional Tverberg Partitions Revisitedcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.