证明高维线性分类的计算难度随维度指数级增长，为算法设计设限。
Hardness of High-Dimensional Linear Classification
- 从仿射退化与k-Sum难题出发，构建归约证明下界。
- 在维度上获得接近最优的指数级下界，与已知上界匹配。
- 适用于仅支持方向查询的计算模型，对实际算法有指导意义。
我们建立了最大半空间偏差问题在高维下的新指数级维度下界，该问题建模了线性分类任务。尽管已有 $O(n^d)$ 与 $ ilde O(1/\varepsilon^d)$ 的上界，但此前的下界仅为多项式级，无法反映维度指数依赖。本文通过从广义接受的仿射退化测试和k-Sum难题假设出发的归约，首次实现近似匹配的下界：基于仿射退化测试，得到 $ ildeΩ(n^d)$ 与 $ ildeΩ(1/\varepsilon^d)$；基于k-Sum假设，得到 $ ildeΩ(n^{d/2})$ 与 $ ildeΩ(1/\varepsilon^{d/2})$。当计算模型仅允许方向查询时，第一个下界可无条件成立，对应当前众多算法中广泛采用的计算范式。
原文摘要 · Abstract (English)
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(n^d)$ and respectively $\tilde O(1/\varepsilon^d)$ 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 $\tildeΩ(n^d)$ and respectively $\tildeΩ(1/\varepsilon^d)$ based on Affine Degeneracy testing, and $\tildeΩ(n^{d/2})$ and respectively $\tildeΩ(1/\varepsilon^{d/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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。