Classifying data with a straight line (a halfspace) while making as few mistakes as possible is computationally hard once the labels are noisy. Practical methods therefore minimize a convex stand-in for the error count, such as hinge or logistic loss. These stand-ins provably lose a factor of roughly $1/\gamma$ against the best achievable error, where $\gamma$ is the margin, meaning how far correctly classified points sit from the boundary. A decade ago, Birnbaum and Shalev-Shwartz showed that this loss can be traded smoothly against running time. They map the data into a much larger feature space with a special kernel, a similarity function that implicitly defines that space. There, a smoothed error count becomes a linear, and hence convex, problem. Their method reaches error $(1+\alpha)$ times the optimum in time roughly $\exp(\tau\log(1/\gamma))$, where $\tau = 1/(\gamma\alpha)$. It is known that no convex method of this "generalized linear" kind can do better. What is not known is whether any algorithm can.
This note proposes to settle that question in the direction we expect. Using the lattice-based cryptographic tools that recently produced sharp hardness results for noisy halfspace learning, we aim to show that beating the kernel curve by more than a polynomial in the exponent would break a standard post-quantum cryptographic assumption. If this succeeds, the surrogate-loss gap would no longer be a weakness of convex optimization but a real computational limit, and the kernel trick would be essentially the best possible algorithm, not just the best convex one. We pair the theory with an empirical study on the planted instances themselves. The study checks whether cheap non-convex methods can beat the curve where the theory says nobody should.
Core Claim
Fix a margin $\gamma$ and let $L^*_\gamma$ be the smallest fraction of points any unit-norm halfspace gets wrong or classifies with margin less than $\gamma$. The time-accuracy tradeoff of Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs gives an improper learner, one whose output need not itself be a halfspace, with
$$\text{err}(\hat h) \le (1+\alpha)\,L^*_\gamma + \epsilon \quad\text{in time}\quad \exp\!\big(C\,\tau\log(1/\gamma)\big),\qquad \tau = \tfrac{1}{\gamma\alpha}.$$
Our conjecture is that, assuming subexponential hardness of Learning with Errors (LWE, the lattice problem underlying post-quantum encryption), every algorithm reaching $(1+\alpha)L^*_\gamma$ needs time $\exp(\tilde\Omega(\tau^{c}))$ for some constant $c>0$. Our target is $c=1$, which would match the upper bound up to logarithms. This would be the first lower bound that tracks the continuous parameter $\tau$ rather than only the endpoints of the curve. Even $c<1$ would already show that the curve's shape reflects a real limit on all algorithms, and is not just an artifact of convex methods.
How This Differs From What Exists
Three lines of work each cover one piece of this question.
Upper bounds and the convex-method lower bound. Learning Kernel-Based Halfspaces with the 0-1 Loss introduced the composition kernel $K(x,x') = 1/(1-\nu\langle x,x'\rangle)$. It also proved, from a unique-shortest-vector lattice assumption, that no algorithm runs in time polynomial in $1/\gamma$. That is an endpoint statement and says nothing about intermediate $\alpha$. The Complexity of Learning Halfspaces using Generalized Linear Methods shows that every efficient kernel or generalized linear method has approximation ratio $\Omega((1/\gamma)/\mathrm{poly}\log(1/\gamma))$, and that ratio $(1/\gamma)^{1-\epsilon}$ needs time exponential in $1/\gamma$. Since the composition kernel is itself such a method, this already shows the Birnbaum curve is optimal within convex methods. Our question is exactly the remaining one: does the curve also bind algorithms that do not reduce to convex optimization?
Cryptographic hardness without margins. 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 reduce Continuous LWE (CLWE) to agnostic halfspace learning. CLWE asks a learner to tell plain Gaussian samples from Gaussians sliced into thin, evenly spaced parallel slabs ("pancakes") along a hidden direction. Both papers obtain sharp bounds in the error-plus-$\epsilon$ regime and in the distribution-free "beat random guessing" regime. Neither parameterizes hardness by margin and multiplicative approximation, which is the regime the kernel curve lives in.
The technique we reuse. Cryptographic Hardness of Learning Halfspaces with Massart Noise supplies the key method. It uses a Veronese polynomial embedding, which turns a polynomial threshold rule into a halfspace over all monomials, together with rejection sampling on a torus. Together these turn a periodic CLWE labeling into a halfspace instance that is hard even for improper learners.
We combine these pieces in a specific way. The degree of the Veronese embedding plays the role on the hardness side that the polynomial approximation degree $\tau$ plays in Birnbaum's algorithm. Making these two degrees meet is the technical content of the proposal.
Two further works constrain the empirical side. Agnostic Learnability of Halfspaces via Logistic Loss gives a two-phase method: logistic regression for a warm start, then projected SGD on hinge loss. It escapes the $\Omega(\sqrt{OPT})$ floor of plain logistic regression and reaches $\tilde O(OPT\ln(1/OPT)+\epsilon)$. Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins shows plain gradient descent on convex losses reaches $\tilde O(OPT^{1/2})$ on log-concave data. Both results are for nice marginal distributions, and both are exactly the kind of non-generalized-linear procedure our lower bound must also rule out on worst-case instances.
Research Program
Step 1: the reduction. Start from CLWE in secret dimension $k$, with a frequency parameter that sets the pancake spacing. Label each sample by a periodic rule along the hidden direction that covers a bounded window of $\ell$ pancakes, and add bounded label noise outside the window. Under the planted distribution, this labeling agrees with a degree-$O(\ell)$ polynomial threshold on most of the mass. After the Veronese lift and normalization to the unit ball, that threshold becomes a halfspace whose margin $\gamma$ shrinks polynomially in $\ell$ and $k$. Under the null distribution, labels are independent of inputs and every predictor has error near $1/2$.
The parameters are then chosen so that $(1+\alpha)L^*_\gamma < 1/2 - \Omega(1)$. Any learner meeting the $(1+\alpha)$ guarantee therefore distinguishes CLWE from Gaussian. Matching the constraints forces $\ell$, and with it the lattice dimension $k$, to grow with $\tau = 1/(\gamma\alpha)$. Subexponential LWE hardness then gives time $\exp(k^{\delta})$, which equals $\exp(\tau^{c})$ for some $c$.
Step 2: tracking the exponent. The technical work is to track how the margin degrades under the lift, since this degradation sets $c$. The Massart reduction did not need this bookkeeping because it had no margin to preserve. A fallback is available if the lift's margin loss is too steep for $c=1$. In that case we will report the best $c$ the route gives and identify which step, the lift or the normalization, accounts for the remaining gap.
Step 3: sharpening the upper curve. The comparison is only meaningful if the upper curve is sharp in practice. Its known constants are very large (an $e^{16}$-type factor in the exponent). We will therefore re-derive the Birnbaum learner with best-approximation (Chebyshev-type) polynomials for the smoothed step function in place of Taylor expansions. The goal is a curve whose constants allow it to be measured at moderate $\tau$. This is a supporting contribution, not the headline.
Step 4: the empirical program. We generate the planted instances from Step 1 at small secret dimensions. On each, we run every competing method at a fixed compute budget and plot its error against compute. This lets us check whether any method's frontier lies strictly above the kernel curve on instances where the theory says this is impossible.
Baselines
Naive reference. The do-nothing reference is the constant predictor, at error about $1/2$. Next to it is standard kernel SVM and logistic regression on the raw inner product, the generalized linear methods covered by The Complexity of Learning Halfspaces using Generalized Linear Methods. These should sit near approximation ratio $1/\gamma$. Beating them is expected and is not the claim.
The curve itself. The direct reference is the composition-kernel learner of Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs. We run it both as originally specified and with our sharpened polynomials. It is implemented through random features or Nyström approximation, with feature count as the compute knob.
Strongest non-convex competitor. The strongest competitor on our question is the two-phase method of Agnostic Learnability of Halfspaces via Logistic Loss. It is not a generalized linear method, so the existing lower bound does not cover it, and it has the best known guarantee of the cheap methods: $\tilde O(OPT\cdot\ln(1/OPT)+\epsilon)$ with $\tilde O(d/\epsilon^2)$ samples, as reported in that paper for well-behaved marginals. We found no reported empirical error for it, or for any method, on CLWE-planted margin instances on Lacuna. Alongside it we run plain gradient descent from Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins and the stochastic-logit accuracy optimizer of EXACT: How to train your accuracy. EXACT trains directly on expected accuracy; its paper reports top accuracy on 6 of 10 UCI datasets, but gives no numbers on synthetic hard distributions.
Fairness of comparison. Every method sees identical samples and receives the same wall-clock budget per point on the frontier. Each gets the same hyperparameter search budget, and selection uses a held-out split drawn from the same planted distribution. The phase-switch threshold of the two-phase method is tuned within that budget, not fixed in advance.
Lattice attack. A lattice attack, basis reduction (LLL) applied to recover the hidden direction, serves as a sanity baseline. Per Continuous LWE and its Applications, noiseless CLWE is solvable by LLL from $n+1$ samples. LLL should therefore succeed on our noiseless instances and fail once CLWE noise is added.
Ablation. The ablation that isolates the key ingredient keeps $L^*_\gamma$, $\gamma$ and the label-noise rate fixed but replaces the pancake structure with unstructured noise of the same mass. If the non-convex methods then beat the kernel curve while they cannot on the planted instances, the hardness is coming from the lattice structure and not from the noise level.
What counts as success. Beating the kernel curve means some method achieves a lower $(1+\alpha)$ at equal compute across a range of $\tau$. The proposal's prediction is that no method does so on planted instances, while some may on the ablation.
Why not just…?
Why not just cite the generalized-linear-method lower bound and call the curve optimal? That bound covers kernels, Fourier methods and logistic regression, but only those. The two-phase procedure, EXACT, and sum-of-squares-style methods all fall outside it. A representation-independent statement is the only way to know whether the curve is a fact about computation or about convexity. The endpoint lattice result in Learning Kernel-Based Halfspaces with the 0-1 Loss says nothing about intermediate $\alpha$.
Why not just reuse the Gaussian-marginal CLWE bounds? The bounds of 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 concern additive $OPT+\epsilon$ error under Gaussian inputs, where there is no margin. Translating them into a multiplicative ratio at margin $\gamma$ is exactly the missing step. The margin bookkeeping in the Veronese lift is where it could fail. This is a real risk, and Step 2's fallback exists for it.
Why not just run a better non-convex method and see whether it beats kernels? This is a genuine threat. It is the main empirical test of the proposal, not something to argue away. If the two-phase method or EXACT clearly beats the kernel curve on our planted instances at moderate dimension, either the construction is flawed or the conjecture is false. The frontier experiment is designed to show this directly, and the LLL control separates "the instance is easy" from "the method is clever."
Why not just improve the algorithm instead of proving a lower bound? We do improve its constants (Step 3), but no algorithmic improvement can answer whether the exponent's dependence on $\tau$ is necessary. Only a lower bound can.
Decisive Checks
The theory is decisive if the reduction yields any $c>0$, and fully decisive at $c=1$.
Empirically, the work runs on four of the file's synthetic benchmarks: the planted CLWE instances, the symmetrized margin distribution of the generalized-linear-method paper, the tail-noise distribution of Ji et al., and the Massart torus construction. Secret dimensions range from 10 to about 60, and $\tau$ is swept by varying $\gamma$ and $\alpha$. We report error against compute frontiers, the approximation ratio $\text{err}/L^*_\gamma$ (with $L^*_\gamma$ known by construction), and the LLL control.
The most informative contrast is between benchmarks. Non-convex methods may beat the kernel curve on the symmetrized margin distribution, which is hard only for convex methods. If they fail to beat it on our planted instances, that shows the new instances capture a barrier the old ones do not. If the non-convex methods beat the curve on our planted instances as well, we will treat that as evidence against the conjecture and revisit the construction.
References
- Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs
- Learning Kernel-Based Halfspaces with the 0-1 Loss
- The Complexity of Learning Halfspaces using Generalized Linear Methods
- Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems
- Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
- Cryptographic Hardness of Learning Halfspaces with Massart Noise
- Agnostic Learnability of Halfspaces via Logistic Loss
- Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
- EXACT: How to Train Your Accuracy
- Continuous LWE and its Applications