Is the Kernel Time–Accuracy Curve for Margin Halfspaces Optimal?

A halfspace is a linear classifier that labels a point by which side of a hyperplane it falls on. When the labels are noisy, logistic regression and hinge-loss SVMs train such classifiers quickly. They optimize a convex stand-in for the error rate, though, and that stand-in can cost a lot of accuracy. In 2012, Birnbaum and Shalev-Shwartz showed you can buy back accuracy with computation. You map the data through a special "composition" kernel and run an ordinary convex SVM in the resulting feature space. The output is an improper classifier, meaning it is a kernel machine rather than a plain hyperplane. Its error is within a factor $(1+\alpha)$ of the best margin error achievable by any hyperplane, and the running time grows smoothly as $\alpha$ shrinks (Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs). That smooth curve has never been matched by a lower bound. Nobody knows whether a cleverer algorithm could reach the same accuracy exponentially faster.

This note proposes to settle the question with a cryptographic hardness reduction. A cryptographic hardness reduction is a proof that any fast learner could be turned into a fast attack on a lattice problem widely believed to be intractable. The target result is that, assuming Learning With Errors (LWE) is subexponentially hard, every algorithm needs time roughly $\exp(\tilde\Omega(1/(\gamma\alpha)))$ to reach error $(1+\alpha)$ times the optimal margin error. This holds for all algorithms, including improper ones and ones that use no convex surrogate. If the result holds, the composition-kernel curve is essentially Pareto-optimal. The gap between convex surrogates and the true error would then be a computational fact, not a failure of algorithm design. If the reduction fails, the obstruction should point to a faster algorithm.

Core Claim

Write $L^*_\gamma$ for the smallest margin error of any unit-norm hyperplane on a distribution over the unit ball. Margin error is the fraction of points either misclassified or classified correctly with margin less than $\gamma$. Birnbaum and Shalev-Shwartz show that an SVM with kernel $K(x,x') = 1/(1-\tfrac12\langle x,x'\rangle)$ outputs $\hat h$ with error at most $(1+\alpha)L^*_\gamma+\epsilon$ in time

$$T_{\text{upper}}(\gamma,\alpha) = \exp\!\big(C\,\tau\log(1/\gamma)\big), \qquad \tau = \frac{1}{\gamma\alpha},$$

where $C$ is an absolute constant. The exponent has a natural reading. The kernel effectively fits a polynomial of degree about $\tau$ that approximates a step function with a transition window of width $\gamma\alpha$. Running over an effective dimension of $\mathrm{poly}(1/\gamma)$, which is what remains after random projection preserves margin $\gamma$, then costs $(1/\gamma)^{O(\tau)}$.

The conjecture we aim to prove is the matching lower bound. For every constant $c<1$ and every $\alpha$ in the range $[\gamma^{-o(1)}\cdot\text{const},\ 1/\gamma]$, any algorithm achieving $(1+\alpha)L^*_\gamma+\epsilon$ requires time $\exp(\Omega(\tau^{c}\log(1/\gamma)))$ under subexponential LWE. At the endpoint $\alpha\approx 1/\gamma$ the curve becomes polynomial. That endpoint is exactly where ordinary convex surrogates already operate, and the Generalized Linear Methods result says they cannot do better. So the curve would connect three facts: the surrogate gap at one end, the improper kernel in the middle, and cryptographic intractability of exact minimization at the other end.

Where This Sits Relative to Prior Work

Three lower-bound lines motivate the question, but each covers only a piece of the curve. Learning Kernel-Based Halfspaces with the 0-1 Loss gives an efficient algorithm for a sigmoid-smoothed error. It also proves, under unique-SVP hardness, that no learner runs in time polynomial in the inverse margin $L$. That is one point on the curve (exact optimality) and says nothing about how runtime should scale with $\alpha$. The Complexity of Learning Halfspaces using Generalized Linear Methods proves that any kernel method minimizing a fixed convex surrogate has approximation ratio $\Omega((1/\gamma)/\mathrm{poly}\log(1/\gamma))$. This lower bound needs no assumption, but it applies only to that restricted family. It cannot rule out localized, multi-phase, or non-convex learners. Our target is a bound against every efficient algorithm, which requires a cryptographic assumption.

Two recent reductions supply the method we plan to reuse. Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems and Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals both run worst-case lattice problems through Continuous LWE. They use periodic hard labelings $f_s(x)=(-1)^{\lfloor\langle x,s\rangle\rfloor}$. The second reaches runtime $n^{\Omega(1/(\epsilon\sqrt{\log n})^\alpha)}$ for additive error $\mathrm{OPT}+\epsilon$ under Gaussian inputs.

Continuous LWE (Continuous LWE) is the problem of telling plain Gaussian samples apart from samples concentrated on hidden parallel slabs, often called "pancakes", along a secret direction. These reductions differ from our target in two ways. They measure additive error under Gaussian inputs, which have no margin. Our target is multiplicative error against margin error on the ball. Cryptographic Hardness of Learning Halfspaces with Massart Noise constrains the design in a useful direction. It shows that LWE-based constructions on a torus, combined with rejection sampling and polynomial lifting maps, can produce a constant-factor barrier of $\Omega(\eta)$ against improper learners. Multiplicative barriers are therefore reachable with this toolkit. We would reuse its rejection-sampling and lifting steps.

Two results look like they might contradict the conjecture, and both are cases where benign distributions make learning easier. An Efficient Tester-Learner for Halfspaces reaches $O(\mathrm{opt})+\epsilon$ in polynomial time under Gaussian marginals. Agnostic Learnability of Halfspaces via Logistic Loss reaches $\tilde O(\mathrm{OPT}\ln(1/\mathrm{OPT}))$ with a two-phase convex procedure. Both rely on structural assumptions such as log-concavity or the anti-concentration that comes with isotropic distributions. Neither applies to arbitrary distributions on the ball measured against margin error. The conjecture is about that distribution-free margin setting. Part of the program is to show empirically that these methods fail on the hard instances while succeeding on benign ones.

Research Program

The theoretical core has three steps.

The first step is a feasibility check. We test whether a direct rescaling of Tiegel's distribution-free reduction already gives the curve. That reduction yields error near $1/2$ while the optimum is tiny, which is a multiplicative statement at the extreme end. If setting the additive slack to $\epsilon \approx \alpha L^*_\gamma$ and projecting to dimension $\mathrm{poly}(1/\gamma)$ recovers the full $\tau$-dependence, the result is a corollary. The proposal would then shift to the upper bound, as described below.

We expect the rescaling to lose the $1/\alpha$ dependence, because Tiegel's instances are not tuned to a margin window. The second step is therefore a new hard family. Take Continuous LWE samples in dimension $n=\mathrm{poly}(1/\gamma)$. Lift them through a polynomial feature map, in the style of the Massart reduction, so that a single unit-norm hyperplane in the lifted space separates the "pancake" structure with margin $\gamma$. Points between pancakes are placed inside the margin window, so they contribute exactly $L^*_\gamma$. Labels are then arranged so that reaching error below $(1+\alpha)L^*_\gamma$ requires resolving about $k\approx 1/(\gamma\alpha)$ consecutive pancakes inside the window. The quantitative heart of the reduction is the lemma that a learner which resolves $k$ periods yields a Continuous LWE distinguisher with advantage polynomial in $1/k$. Combined with the polynomial-method intuition that $k$ periods need degree $\Omega(k)$ to approximate, subexponential LWE hardness in dimension $\mathrm{poly}(1/\gamma)$ would give the claimed $\exp(\Omega(\tau^c\log(1/\gamma)))$.

The third step is to identify which constant the bound leaves open. Birnbaum and Shalev-Shwartz report constants in the exponent as large as $e^{16}$. A lower bound with exponent $\tau^c$ would show that only constant and polylogarithmic slack remain. That converts a practical complaint about the kernel into a precise question about how small the constant can be.

The empirical part is secondary but concrete. We implement the composition-kernel learner using random features with the degree truncated at $D$. This approximates the rational kernel, whose power series has coefficients $2^{-j}$. We generate the planted instances from the second step at small, laptop-scale dimensions. On these instances we measure how the minimal compute needed to reach ratio $1+\alpha$ scales.

Baselines

The "do nothing" reference is plain logistic regression and a linear SVM on the raw inputs. These are the convex surrogates whose gap motivates the whole question. Theory predicts their ratio is stuck near $1/\gamma$ (GLM lower bound) and near $\sqrt{\mathrm{OPT}}$ on adversarial isotropic instances (Ji et al.). Beating this reference means reaching a ratio well below $1/\gamma$ at all, which the kernel learner should do.

The strongest competitor for the theoretical claim is $L_1$ polynomial regression, the algorithm that matches the Gaussian-marginal hardness. Near-Optimal Cryptographic Hardness… reports its upper bound as runtime $n^{O(1/\epsilon^2)}$ for error $\mathrm{OPT}+\epsilon$. It is the strongest competitor because it is the known algorithm whose cost scales most favorably near optimality. If its cost on our instances scaled like $n^{O(1/\alpha)}$ with no $1/\gamma$ factor, the conjecture would be false. No reported empirical result was found on Lacuna for $L_1$ regression, or for any baseline, on margin-error ratio benchmarks. All numbers will therefore be produced here.

The algorithmic competitors are the two-phase logistic-then-localized-hinge procedure and projected gradient descent on the ramp loss from the tester-learner. They represent the best non-kernel ideas for escaping the surrogate gap. Fairness means four things. Every method gets the same samples and the same wall-clock budget, measured both in floating-point operations and in feature count. Every method gets the same hyperparameter search: twenty configurations each over regularization, step size, and degree or localization radius. And every method is scored by the same held-out estimate of error divided by $L^*_\gamma$, where $L^*_\gamma$ is known exactly because the instances are planted.

The ablation that isolates the key ingredient replaces the rational composition kernel with a plain polynomial kernel of the same degree $D$ and the same feature budget. This separates "any degree-$D$ method" from "this particular kernel". The conjecture predicts that the two have the same cost exponent on hard instances. A gap would suggest the specific kernel matters, which bears on whether the constant can be reduced.

Why not just…?

Why not just cite the GLM lower bound and call the curve tight? That bound (Daniely et al.) applies only to methods that minimize a fixed convex loss over a fixed feature space. Ji et al.'s second phase and the tester-learner's ramp-loss descent are exactly the kind of non-GLM procedure it cannot address, and both beat GLMs under assumptions. Only a reduction against arbitrary algorithms can say the curve is optimal. Our experiments run those non-GLM learners on the planted instances to show the restriction matters.

Why not just reparametrize the existing Gaussian-marginal hardness? This is the real threat. If setting $\epsilon\approx\alpha L^*_\gamma$ in Tiegel or Diakonikolas et al. already yields $\exp(\tilde\Omega(1/(\gamma\alpha)))$, the main theorem is a short corollary. That is why feasibility is the first step rather than an afterthought. Our current reading is that those instances have no margin and give a bound in terms of the absolute ε rather than $\gamma\alpha$, so the dependence on $\gamma$ is lost. If the corollary does go through, we would publish it as a note and redirect effort to lowering the kernel's constant.

Why not just design a better algorithm instead of a lower bound? The two-phase method and the tester-learner show that faster learners exist under structural assumptions. A distribution-free faster learner would refute the conjecture, and that is a legitimate outcome. The experiments test for it directly by measuring whether either method reaches a fixed ratio with compute that grows more slowly than $1/(\gamma\alpha)$ on the planted family. Both outcomes are informative. A refutation would also point to which property of the hard family the faster learner exploits.

Proposed Experiments

The decisive empirical check uses the planted families at margins $\gamma\in\{0.2,0.1,0.05\}$ and target ratios $1+\alpha$ with $\alpha\in\{1/(2\gamma),1/(4\gamma),2,1\}$. For each method we record the smallest feature budget that reaches the target ratio. The conjecture predicts that the log of the required budget is linear in $\tau\log(1/\gamma)$ for every method, with only the slope varying. A method whose log-budget is sublinear in $\tau$ on these instances refutes the conjecture at that scale.

As a control we run the same sweep on benign distributions. These are the log-concave and heavy-tailed soft-margin families of Frei et al. and the adversarial isotropic distribution $Q$ of Ji et al. There, the tester-learner and the two-phase method should succeed cheaply. This confirms that any hardness we observe comes from the planted structure and not from implementation weaknesses.

A second check compares the rational kernel against the polynomial-kernel ablation, which gives an empirical read on whether the $e^{16}$-scale constant is intrinsic. All the theoretical claims remain conditional on subexponential LWE. The empirical sweeps cannot prove hardness. What they can do is falsify the conjecture early, or show that the reduction's parameters match observed behavior.