Hardness of High-Dimensional Linear Classification

Our first reduction is from $k$-Sum to MaxDiscrepancy. This generalizes the previous $3$-Sum reduction [31, 46] that gave quadratic lower bounds to an arbitrary $k\ge 2$ and hereby improves the exponents in the lower bounds to depend on the dimension. Our reduction yields the following theorem:

Our second reduction is from AffineDegeneracy testing to MaxDiscrepancy and yields the following theorems:

We remark that lower bounds of the form $1/{\epsilon }^d$ do not rule out $2^{1/\epsilon }\mathrm{poly}(d)$ algorithms. The latter two results are of special importance since either under the hardness conjecture or in the sidedness query model they match the best exact and approximate algorithms for this problem up to lower order polylogarithmic terms. The exact version, MaxHalfspace, has a $O(n^d)$ complexity [21, 22], and for the approximate version, $\epsilon$-MaxHalfspace, there is an $O(\frac{1}{{\epsilon }^d}{\log }^4\frac{1}{\epsilon })$ time algorithm (after preprocessing the input in $O(n)$ time) in [46]. Notably, this is based on a range counting data structure that can be implemented to work in the sidedness query model as well. The sidedness query model may seem restrictive at first glance and indeed it does not rule out simple comparisons between values (rather than signs) of dot products and determinants which may be exploited to break such lower bounds.

However, we stress that basically all known algorithms rely exactly on that type of subroutines, see related work below, and especially the discussion in [28]. Now, 30 years later, the core sidedness query operation is precisely the heavily optimized $\mathrm{sign}(x^{T}y)$ operation which can be vectorized, optimized and accelerated on GPUs. Additionally, the study of big data models have brought up a paradigm that discretizes and reduces the search space to a few candidate solutions and then brute forces that subset using simple queries as in [46]. This underlines that the sidedness query model is even more relevant in today’s age of AI/ML and big data, than it probably was when Erickson and Seidel [28] studied it.

The hardness conjecture of AffineDegeneracy extends the same lower bound to the real RAM model in any dimension. In the Turing model, our reduction holds only in any constant dimension, due to the bit complexity of representing and adjusting small scalars.

Exact algorithms are known that compute halfspace discrepancy in $O(n^d)$ time in any dimension $d\ge 2$ [21, 22, 23].

It was shown in [46] that the $\epsilon$-MaxHalfspace problem can be solved in $O(\frac{1}{{\epsilon }^d}{\log }^4\frac{1}{\epsilon })$ time (plus a linear scan over the data in time $O(n)$). This was complemented by conditional lower bounds in $2$ dimensions: an exact solution requires $\mathrm{\Omega }(n^{3/2})$ time conditioned on the conjecture that the all-pairs-shortest-paths problem (APSP) requires $\mathrm{\Omega }(n^3)$ time to be solved. An approximate solution requires $\mathrm{\Omega }(1/{\epsilon }^2)$ by reduction from $3$-Sum under the special case $k=3$ of the aforementioned $k$-Sum conjecture detailed in Section 1.

Previous results by the same authors [45] gave $O(\frac{1}{{\epsilon }^{d+1/3}}{\log }^{2/3}\frac{1}{\epsilon })$ for $\epsilon$-MaxHalfspace. They also studied a version that considered rectangular ranges instead of halfspaces, and provided an $O(n+\frac{1}{{\epsilon }^2}\log \log \frac{1}{\epsilon })$ algorithm and an $\mathrm{\Omega }(1/{\epsilon }^2)$ lower bound leveraging a previous $\mathrm{\Omega }(n^2)$ lower bound of [6] for the exact rectangle variant. These lower bounds were again conditioned on the conjecture that APSP requires $\mathrm{\Omega }(n^3)$ time to be solved.

Aside for the classic work described above, the hardness of classification has been studied in computational learning theory from other perspectives. A touchstone result by Guruswami and Raghvendra [34] showed it was NP-Hard in the dimension $d$ to distinguish between instances where there exist halfspaces which agree on at least a $(1-\epsilon )$ fraction of the labels and ones where no halfspace agrees on more than a $(1/2+\xi )$ fraction of the data. Their work, and many others in this line (c.f. [30]), consider data from ${\{0,1\}}^d$, and since $O(d/{\epsilon }^2)$ samples are sufficient to attain this $\epsilon$-error, the number of points $n$ does not show up separately in this analysis. But this work does not for instance control the constant in the exponent of the runtime; it does not rule out algorithms with runtime $1/{\epsilon }^{\max \{2,d/1,000,000\}}$. Also, algorithms with runtime polynomial in $1/\epsilon$ and $d$ are possible with stronger noise like Massart noise [19].

A very recent and independent work by Pinto, Palit, and Raskhodnikova [52] approaches these problems from the property testing perspective, and conditioned on $k$-Sum, attains lower bound on the runtime for $\epsilon$-MaxHalfspace of $\mathrm{\Omega }(1/{\epsilon }^{\lceil (d+1)/2\rceil -c})$. The core of their argument and construction is basically the same as our $k$-Sum hardness result.

Computational geometry has recently witnessed a number of “no-dimensional” or “dimension-free” results. These are often approximate solutions to problems in ${ℝ}^d$ where the core aspect of the problem does not depend on the dimension $d$. It may take $O(d)$ time to read or process each data point, so they are not independent of the dimension $d$, but importantly, these sorts of results prevent exponential dependence. Arguably this expedition started with approximate minimum enclosing ball and geometric median problems [8, 7, 40], which only require $O(1/\epsilon )$ resp. $O(1/{\epsilon }^2)$ points to approximate within a relative $(1+\epsilon )$. This sort of analysis led to more general analyses of Frank-Wolfe style greedy algorithms [17], which induced no-dimensional results for the approximate polytope distance problem [33]. Also, classical combinatorial geometric consequences of convexity such as Carathéodory, Helly, and Tverberg theorems can be made no-dimensional when the diameter is bounded [2]. And this led to improved centerpoint and $\epsilon$-net results [16, 37].

These geometric insights have led to improvements in sublinear and no-dimensional algorithms for classic linear classification problems [18, 20]. These analyses, and the above mentioned analysis of polytope distance [33], are refinements of Novikoff’s classic analysis of the perceptron for linear classifiers, which is also no-dimensional. In particular, it requires that there exists a perfect classifier with no mistakes, and depends on the ratio between the distance between classes, and the diameter of the input set, cf. [38, 35]. The linear classification problem which optimizes an often convex loss function (e.g., logistic regression) requires additional assumptions to be made no-dimensional. Classic sparsity assumptions do not prevent from mild $\mathrm{\Theta }(\log (d)/{\epsilon }^2)$ dependence [44]. Strictly dimension-free bounds can be achieved if one uses a regularization term and also assumes the diameter is bounded (in expectation) [5]. These results $(1+\epsilon )$-approximate typical classification loss functions with $O(1/{\epsilon }^2)$ samples and an additional dependence that relies solely on the amount and type of regularization. Apart from classification there is a plethora of no-dimensional results in the clustering regime. The first dimension-free bounds for $k$-means/median clustering objectives appeared in [29, 54]. Recent developments extend the classic finite data setting to learning-theoretical dimension-free bounds for center based clustering and classification of points and polygonal curves [11, 41, 5].

In the context of these numerous no-dimensional results, it may be surprising that the geometric linear classification problem, and especially the approximately optimized variant tackled in this paper, is shown to require time exponential in $d$ under conditional hardness assumptions. What is different in our setting? First, the perceptron-based results require separability, so $\psi (h^{\ast })=0$; our constructions do not consider this case, and have $\psi (h^{\ast })$ fairly large. Second, these results mostly consider a bounded diameter of the point set, and also a structural term that prevents affine scaling, which could be the margin or the regularization term that has a similar effect. While we could affinely scale our constructions to be within a unit ball, it would make these other structural parameters (e.g., the margin between the properly separated points) proportionally small. Third, while no-dimensional $\epsilon$-nets [37] and $\epsilon$-covers [51] exist – and these play a crucial role in the best algorithms for our variant of classification [45, 46] – these results apply for bounded-radius balls or kernels, and not the halfspaces we study.

Hence, we hope our conditional hardness results help the community identify when these high-dimensional geometric problems relevant for data analysis can, and cannot, be solved in a dimension-efficient way. Our work provides recipes to show that even when approximation is allowed, exponential dependence on the dimension can be unavoidable.

We reduce $k$-Sum to MaxHalfspace with $d=k-1$ as follows. Let $A=\{a_1,\mathrm{\dots },a_n\}$ for integers $a_i\in \mathbb{Z}$ be an instance of $k$-Sum. We will transform this input into a set of $2nk$ points in ${ℝ}^d$ where the solution to MaxHalfspace will resolve the $k$-Sum instance on $A$.

For any integer $a_i,i\in [n]$ consider the following $k=d+1$ points in ${ℝ}^d$: Let $z_{i,0}:=(-a_i/(2d-3),0,\mathrm{\dots },0)$ and for each $j\in [d-1]$, let $z_{i,j}=(a_i/2,0,\mathrm{\dots },0,1,0\mathrm{\dots },0)$ which has a single $1$ entry at position $j+1$. Further we create the point $z_{i,d}=(-a_i,2,2,\mathrm{\dots },2)$.

Further for each point $z_{i,j}$ we create two points: one point, which we place in $R$ and one point, which we place in $B$. For $j\in \{0,\mathrm{\dots },d\}$ we define $x_{i,j}\in R$ by $x_{i,j}=z_{i,j}+\gamma e_1$ and $y_{i,j}\in B$ by $y_{i,j}=z_{i,j}-\gamma e_1$ where $\gamma$ is a sufficiently small number (for instance ) and $e_1$ denotes the first standard basis vector in ${ℝ}^d$.

First, assume that there is $h$ with ${\mu }_R|R|-{\mu }_B|B|\ge k$. Consider a set of $k=d+1$ lines defined by $l_0(t)=(t,0,\mathrm{\dots },0)$, $l_j(t)=(t,0,\mathrm{\dots },0,1,0,\mathrm{\dots },0)$, for $j\in [d-1]$, and $l_d(t)=(t,2,\mathrm{\dots },2)$. Observe that all points in $R$ and $B$ lie on these lines. Let $v_j$ be the point where $h$ crosses the line $l_j$, for $j\in \{0,\mathrm{\dots },d\}$.

Note, since the $z_{i,j}$ points are further apart than $2\gamma$, then the number of points $x_{i,j}$ or $y_{i,j}$ on each of the lines that lie above $h$ in $R$ can differ by at most $1$ from the number of points above $h$ in $B$.

Thus, there cannot be any hyperplane with ${\mu }_R|R|-{\mu }_B|B|>k$ and in order to achieve ${\mu }_R|R|-{\mu }_B|B|=k$, the hyperplane $h$ must cross each line $l_j$ at a point $v_j=({\beta }_{j+1},\mathrm{\dots })$ that for some $i_j\in [n]$, lies between the points $z_{i_j,j}-\gamma e_1$ and $z_{i_j,j}+\gamma e_1$. Equivalently, we have that ${\beta }_{j+1}\in [e_1^T{z}_{i,j}-\gamma ,e_1^T{z}_{i,j}+\gamma ]$. To simplify notation, we define ${\alpha }_{i,j}≔e_1^T{z}_{i,j-1}$ for all $(i,j)\in [n]\times [k]$, where $k=d+1$. With this substitution, we get that ${\beta }_j\in [{\alpha }_{i,j}-\gamma ,{\alpha }_{i,j}+\gamma ]$.

Consider the points $w_j=v_j-v_0$, for $j\in [d]$. Since these are $d$ points in ${ℝ}^d$, they must lie on a common linear hyperplane and the only way to align the upper $d-1$ coordinates is by setting $w_d=2{\sum }_{j=1}^{d-1}{w}_j$.

This is equivalent to $0=v_0-v_d+2{\sum }_{j=1}^{d-1}(v_j-v_0)=-(2d-3)v_0+(2{\sum }_{j=1}^{d-1}{v}_j)-v_d$, implying in particular for the first coordinate that

Now, since for all $j\in [k]$ there exists some $i_j\in [n]$ such that $|{\alpha }_{i_j,j}-{\beta }_j|\le \gamma$, we get that

where we used the triangle inequality and the choice . Since all $a_i$ are integers, it follows that $a_{i_1}+\mathrm{\dots }+a_{i_k}=0$.

For the other direction, assume that $a_{i_1}+\mathrm{\dots }+a_{i_k}=0$ or equivalently $a_{i_1}+\mathrm{\dots }+a_{i_{k-1}}=-a_{i_k}$. Then the points $z_{i_1,0},\mathrm{\dots },z_{i_k,d}$ lie on a hyperplane $h$. To prove this, note that any set of $d$ points in $d$ dimensions lie on a hyperplane. We need to show that the remaining point $z_{i_k,d}$ lies on the same hyperplane as the others. By a similar calculation as above, we get

For this hyperplane it holds that $|{\mu }_R|R|-{\mu }_B|B||\ge k$, since for any point $z_{i,l}$, for $l\in \{0,\mathrm{\dots },d\}$ that lies on the hyperplane, the corresponding $x_{i,l}$ (and $y_{i,l}$) lie above (respectively below) the hyperplane, all counting for one of the two classes. If it does not lie on the hyperplane, then by construction and for sufficiently small $\gamma$ as above, both $x_{i,l}$, and $y_{i,l}$ lie on the same side of the hyperplane and thus both contribute $0$ or cancel each other.

The number of points is $2nk=2n(d+1)$, and so any algorithm with runtime $O({(\beta n)}^{\alpha })$ for MaxHalfspace yields an algorithm with runtime $O({(\beta n)}^{\alpha })$ for $k$-Sum. Set $\beta =1/(2(d+1))$ and $\alpha =\lceil k/2\rceil -c=\lceil (d+1)/2\rceil -c$. Now using the Lemma’s assumption on $k$-Sum hardness, there cannot be an algorithm for MaxHalfspace within runtime $O({(\beta n)}^{\alpha })=O((n/{(2(d+1))}^{\lceil (d+1)/2\rceil -c})$.

Similar to the reduction for MaxHalfspace, we now set $\epsilon =1/(2n(d+1))$, and any algorithm with runtime $O({(\beta /\epsilon )}^{\alpha })$ for $\epsilon$-MaxHalfspace yields an algorithm with runtime $O({(\beta /\epsilon )}^{\alpha })=O{(2n(d+1)\beta )}^{\alpha })$ for $k$-Sum. We again set $\beta =1/(2(d+1))$ and $\alpha =\lceil k/2\rceil -c=\lceil (d+1)/2\rceil -c.$ Thus, assuming the $k$-Sum hardness conjecture as in the statement of the lemma, there cannot be any algorithm that solves $\epsilon$-MaxHalfspace within runtime $O(1/{(2(d+1)\epsilon )}^{\lceil (d+1)/2\rceil -c})$. We note that the time for the reduction from $k$-Sum to MaxHalfspace is $O(n{k}^2)\subseteq O(n^{\alpha })$. $◀$