acceptodds
Under review as a conference paper at ICLR 2027

Truly Subquadratic High-Precision Gaussian SVM Training on Structured Inputs

Abstract

We establish truly subquadratic randomized algorithms for high-precision Gaussian support vector machine training by exploiting coordinate structure. For every fixed , we give randomized algorithms that train inputs from a sufficiently separated fixed-size real alphabet in dimensions to additive dual objective error using arithmetic operations for some constant , with near-linear preprocessing and space. This truly subquadratic guarantee allows arbitrary repetitions and covers hard and soft margins, with or without bias, provided identical inputs have consistent labels in the hard-margin case. To achieve this, we construct an exact kernel-product procedure whose single success event holds for all real weight vectors simultaneously, including adaptive signed queries. Tensor spectral bounds then turn these products into fast optimization. Building on this procedure, local Taylor features and a diagonal correction extend the guarantee to inputs with distinct discrete parts and additional arbitrary real coordinates, for any fixed , using subquadratic space.

Primary area:
optimization
Keywords:
Support vector machines, Gaussian kernels, High-precision optimization, Subquadratic algorithms.

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_KmEGOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper is a pure theory work about support vector machine (SVM) with Gaussian kernel and structued input. The classical kernel SVM solvers have time complexity of at least O(n2)O(n^2). However, this paper leverages the special structure of the discrete data to achieve O(n2−σ)O(n^{2-\sigma}) complexity (subquadratic, claimed as the title) at high precision. As a comparison, the classical kernel approximation may lose precision when accelerating. The paper established the path: efficient kernel operator (K*v) computation (Theorem 2) -> subquadratic complexity (Theorem 1) -> discrite alphabet support (Theorem 6) -> further continuous feature combination (Theorem 7).

Critical strengths
  1. The paper identifies a gap: fast solvers for a fixed feature representation (e.g., Gu et al. 2025) do not imply high-precision training of the original kernel objective, and resolves it for Gaussian SVMs on separated finite alphabets, giving truly subquadratic n2−δ+o(1)n^{2-\delta+o(1)} training time at error exp⁡(−(log⁡n)3)\exp(-(\log n)^3). The mechanism is constructive and cleanly decomposed: an exact kernel-product oracle whose single success event covers all adaptive signed queries (Theorem 2, Lemma 3), paired with tensor spectral bounds that keep the iteration count subpolynomial (Lemmas 4 and 5).

  2. The analysis clarifies what low-rank kernel approximation sacrifices: Proposition 10 shows that at this precision, any uniform quadratic surrogate requires near-full rank, which directly justifies the blockwise exact-recovery route over global low-rank replacement. The framework is also fairly complete in scope: all four SVM formulations (soft/hard margin, with/without bias), repeated inputs (Appendix E.2), and a continuous-coordinate extension without a diameter bound via the diagonal correction (Theorem 7, Lemma 8).

  3. The limitation is discussed. The conclusion explicitly states that the exponent saving is small, that separation weakening can erase it, and that coefficient-growth control is needed for a practical algorithm.

Critical weaknesses
  1. No numerical or empirical evidence. The paper is purely asymptotic. Key quantities are never instantiated: the exponent saving δ(C)=7σ(C)/8\delta(C) = 7\sigma(C)/8 with σ=Ω(1/(Clog⁡2(C+2)))\sigma = \Omega(1/(C\log^2(C+2))) is vanishingly small for moderate CC or alphabet size (σ\sigma carries an L0−4L_0^{-4} factor, Appendix D); the n−10n^{-10} success probability and all o(1)o(1) exponents are meaningless without a single data point showing at what nn the crossover against a naive O(n2)O(n^2) solver or Gu et al. (2025) occurs. The conclusion itself admits a practical version needs "error-tolerant recovery and coefficient-growth control," which are not developed. As written, the paper's practical statement that coordinate structure enables subquadratic training remains unverifiable.

  2. Strong input restrictions. The guarantee requires well-separated alphabets (ρ≤σ/12C\rho \le \sigma/12C, i.e., a2≥log⁡(12C/σ)a^2 \ge \log(12C/\sigma)) and d≤Clog⁡nd \le C\log n. The conclusion also states that weaker separation erases the saving.

Questions for authors

Q1. Instantiation and mechanism check. All guarantees are asymptotic and the saving δ=7σ/8\delta = 7\sigma/8 decays fast in CC and L0L_0 (σ=Ω(1/(Clog⁡2(C+2)))\sigma = \Omega(1/(C\log^2(C+2))), with an L0−4L_0^{-4} dependence in Appendix D). Could you provide (a) a table of instantiated constants (σ\sigma, δ\delta, and the resulting exponent) for a few concrete values of CC and L0L_0, to show the regime where the bound is non-vacuous; and (b) a small-scale demonstration (e.g., in exact rational arithmetic) that the product oracle of Theorem 2 returns the exact KvKv and that the Lemma 3 success event holds simultaneously across adaptive queries, on instances of moderate size?

Q2. Separation in practice. The condition ρ≤σ/(12C)\rho \le \sigma/(12C) (equivalently a2≥log⁡(12C/σ)a^2 \ge \log(12C/\sigma)) requires well-separated symbols, and the conclusion notes weaker separation can erase the saving. For real discrete features (e.g., one-hot or categorical encodings with symbols at constant spacing, where q=e−a2q = e^{-a^2} is not small), does any non-trivial subquadratic guarantee remain?

1 comment
AuthorsOpenReview ↗

Response to Reviewer KmEG

Q1(a). Exponent savings and the quadratic baseline

Table 2 (p. 8) gives the requested exponents. For (C,L0)=(2,2),(4,2),(2,4)(C,L_0)=(2,2),(4,2),(2,4), the respective pairs (σ,δ)(\sigma,\delta) are approximately (2.602,2.276)×10−9(2.602,2.276)\times10^{-9}, (7.787,6.814)×10−10(7.787,6.814)\times10^{-10}, and (3.684,3.223)×10−12(3.684,3.223)\times10^{-12}. Each gives worst-case training time n2−δ+o(1)n^{2-\delta+o(1)} at εn=exp⁡[−(log⁡n)3]\varepsilon_n=\exp[-(\log n)^3]. The O(nσ/8log⁡(n/ε))O(n^{\sigma/8}\log(n/\varepsilon)) products in training use only one eighth of the per-product exponent saving, leaving δ=7σ/8\delta=7\sigma/8. Appendix L.1 (p. 25) derives these sufficient choices.

These exponents quantify the asymptotic saving over explicit Gram construction, which writes Θ(n2)\Theta(n^2) entries. A wall-clock crossover at a particular nn depends on the constants and the cost of each operation in the implementations. For Gu et al., the comparison also depends on the feature dimension required at the same input scale and objective error. Gu et al. (2025, Theorem G.7)

Q1(b). An exact adaptive query

The new example after Theorem 2 (Section 3.1, p. 4) uses all 128 seven-bit strings with q=1/2q=1/2, so every kernel entry is rational. Write eue_u for the basis vector at string uu. Querying with e07e_{0^7} returns zx=2−∣x∣z_x=2^{-|x|}, where ∣x∣|x| counts the ones in xx. Use the returned value z17=1/128z_{1^7}=1/128 to form the signed query v=e07−z17e17v=e_{0^7}-z_{1^7}e_{1^7}. Its product has (Kv)x=2−∣x∣−2∣x∣−14(Kv)_x=2^{-|x|}-2^{|x|-14} in every coordinate, including exact cancellation at x=17x=1^7.

In seven variables, the exact threshold base case in Appendix L.1 reproduces every entry of each block. Thus the same preprocessing gives both products and the product for any later weights. In general, Lemma 3 bounds the probability that any row–group pair lacks a strict majority of samples correct on every entry by n−10n^{-10}. Those majorities are fixed before the first query, so one preprocessing succeeds for every adaptive query with probability at least 1−n−101-n^{-10}.

Q2. Unit spacing and one-hot encodings

At unit spacing, Corollary 16 gives deterministic n1.94241+o(1)n^{1.94241+o(1)} training at εn\varepsilon_n for every distinct Boolean subset in d≤1.8log⁡nd\le1.8\log n. For distinct binary encodings in d≤Clog⁡nd\le C\log n, Corollary 14 gives n2−σ(C)+o(1)log⁡(n/ε)n^{2-\sigma(C)+o(1)}\log(n/\varepsilon) time whenever the largest observed off-diagonal kernel row sum is at most 1/21/2. One K1K\mathbf1 query tests this condition. For concatenated one-hot fields at unit spacing, two records differing in tt fields contribute e−2te^{-2t} to each other's row sum. Both guarantees cover all four SVM formulations (Appendix L.3, p. 26).

The identity ρ=e−a2\rho=e^{-a^2} in the question holds for a two-symbol alphabet of spacing aa. For a larger alphabet br\\{b_r\\}, Theorem 6 uses the full row sum ρ=max⁡r∑s≠re−(br−bs)2\rho=\max_r\sum_{s\ne r}e^{-(b_r-b_s)^2}.

Reviewer_UbPpOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper titled “Truly Subquadratic High-Precision Gaussian SVM Training on Structured Inputs” proposes an approach for truly subquadratic running time randomized algorithms for high-precision Gaussian support vector machine training by exploiting coordinate structure. The dual formulation of SVMs with a Gaussian kernel is a fundamental convex optimization problem. However, training requires optimizing a quadratic objective involving all pairs of n training points. The paper shows inputs drawn from separated alphabets, optionally augmented by a limited number of continuous coordinates, allows solution with subquadratic arithmetic operations, training to ultra-high additive dual objective precision. Overall its a nice theoretical contribution to a problem that has been studied in ML for decades.

Critical strengths

The proofs cover all standard SVM variants: hard-margin and soft-margin with or without unregularized bias, so it is widely applicable. In addition, coincident inputs and within-group label conflicts are handled via proximal reductions. The theorems and other theoretical constructs derived are sound and also enough details are provided to understand them. The paper explicitly works out degree bounds, coordinate padding, accelerated restarts with inexact projections, and fast rectangular matrix multiplication tensor budgets in the appendix.

Critical weaknesses

While the results are definitely an advance on the front of complexity of SVMs, the practical applicability of the model is somewhat limited. The discrete alphabet requires a strict separation parameter, a bound on the dimension and also continuous coordinates are restricted to o(log n) dimensions. Many real datasets may not satisfy such stringent criteria. The paper does not identify, discuss, or evaluate any specific real-world datasets that satisfy these conditions. Nearly coincident points with opposite labels cause dual objectives to diverge to infinity. Therefore the algorithm cannot handle arbitrary label noise among continuous coordinates under hard margins without external assumptions.

Questions for authors

na

1 comment
AuthorsOpenReview ↗

Response to Reviewer UbPp

Which inputs satisfy the assumptions?

The dimension and separation conditions in Theorem 6 can be checked from the encoding. They require d≤Clog⁡nd\le C\log n and an off-diagonal row sum of at most σ/(12C)\sigma/(12C) in every row of the L0×L0L_0\times L_0 alphabet kernel. For distinct unit-spaced binary data in d≤Clog⁡nd\le C\log n, there is also a test on the sample itself. One product K1K\mathbf1 gives r=max⁡i(K1)i−1r=\max_i(K\mathbf1)_i-1, the largest off-diagonal row sum. If r≤1/2r\le1/2, Corollary 14 gives a worst-case subquadratic training bound for every labeling. Proposition 15 gives a concrete family passing this test with high probability, namely independent uniform binary records in d=⌊8log⁡n⌋d=\lfloor8\log n\rfloor (Appendix L.3, p. 26).

Can nearby continuous coordinates make the hard-margin objective unbounded?

For the distinct discrete parts in Theorem 7, the hard-margin optimum stays bounded even if the continuous coordinates coincide and the labels are opposite. Lemma 8 gives Q=YKY⪰μIQ=YKY\succeq\mu I with μ=(1−ρ)d\mu=(1-\rho)^d. Hence OPT≤n/(2μ)\mathrm{OPT}\le n/(2\mu) for any labels. Theorem 7 bounds the number of real coordinates by k≤clog⁡n/log⁡log⁡nk\le c\log n/\log\log n and permits arbitrary values in those coordinates (Section 6, p. 8).

For an instance consisting of two oppositely labeled points with the same discrete part and continuous distance h>0h > 0, the hard-margin optimum is 1/(1−e−h2)1/(1-e^{-h^2}), with or without bias (Appendix H, p. 20). It is finite at each positive distance and diverges as hh tends to zero. At coincidence the feasible ray (t,t)(t,t) has objective 2t2t. Proposition 9 uses a within-group value bound for precisely this hard-margin case. With a finite soft-margin cap UU, the objective is at most nUnU even for conflicting labels.

Reviewer_5JVCOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper gives randomized, truly subquadratic algorithms for Gaussian SVM dual optimization to additive error exp⁡[−(log⁡n)3]\exp[-(\log n)^3] on sufficiently separated finite-alphabet inputs in O(log⁡n)O(\log n) dimensions. It combines an exact kernel-vector oracle supporting adaptive signed weights with tensor spectral bounds and accelerated optimization. Extensions handle repetitions and a limited number of arbitrary continuous coordinates.

Critical strengths
  • The meaningful contribution is the end-to-end high-precision training guarantee without a globally accurate low-rank kernel approximation. It connects established counting and optimization techniques in a useful way.
  • Lemma 3 genuinely establishes one success event for all adaptive signed queries. The tensor conditioning argument, diagonal correction, and repetition reductions address important obstacles rather than assuming them away.
  • Assumptions, computational model, and objective-error criterion are explicit. The paper distinguishes its new guarantees from consequences of existing methods and supplies substantial supporting proofs.
Critical weaknesses

I did not noticed any particular weakness other than the significance of the claim. The signed-query argument does not suffer from an adaptivity gap, and the singularity caused by repetitions is explicitly handled. The restrictive separation assumptions and exact-real arithmetic model limit the result's scope, but are disclosed—not contradictions of the stated theorems.

Questions for authors
  1. Could you more precisely distinguish Theorem 2 from the blockwise counting construction in Björklund & Kaski (2021), Section 4? Their method already recovers each block before summing. Which additional ingredients, beyond retaining individual rows and introducing weights, constitute the main algorithmic advance?
  2. Under bounded-bit input assumptions, what precision would be needed to preserve reliable median recovery and the objective guarantee? This is not necessary for the stated arithmetic-model theorem, but would clarify whether its subquadratic exponent plausibly survives a finite-precision implementation.
2 comments
AuthorsOpenReview ↗

Response to Reviewer 5JVC

Q1. What does Theorem 2 add to blockwise counting?

Theorem 2 constructs a reusable Gaussian matrix–vector oracle. For each row and group, we prove that a strict majority of samples reproduces every Gaussian entry before the query weights are chosen. With probability at least 1−n−101-n^{-10}, this holds for all rows and groups, so one preprocessing answers KvKv exactly for every real vv, including signed vectors chosen from earlier answers. Björklund and Kaski use the blockwise majority to recover a count of pairs at a prescribed inner product in each batch, then add those counts. Björklund and Kaski (2021, Section 4)

In a two-entry block, the coefficient vectors (1,q)(1,q) and (q,1)(q,1) have the same sum and give opposite answers at weights (1,−1)(1,-1). We write the Gaussian value at Hamming distance hh as qh=1+∑k=1d(qk−qk−1)[h≥k]q^h=1+\sum_{k=1}^d(q^k-q^{k-1})[h\ge k] and sample low-degree polynomials for these thresholds. On the event in Lemma 3, each polynomial in the correct majority for row ii and group GG therefore gives the same linear form ∑j∈GKijvj\sum_{j\in G}K_{ij}v_j, regardless of signs or cancellations. Evaluating one output submatrix at a time gives n2−σ(C)+o(1)n^{2-\sigma(C)+o(1)} operations per query with near-linear preprocessing and space (Sections 3.1–3.3).

A gradient query in the SVM optimizer uses the signed vector YbjYb_j, where the iterate bjb_j depends on previous gradients. Reusing these exact products and applying the tensor condition bound gives n2−7σ/8+o(1)log⁡(n/ε)n^{2-7\sigma/8+o(1)}\log(n/\varepsilon) operations for the original Gaussian dual on separated Boolean inputs (Theorem 1).

Q2. What precision suffices for median recovery and the objective guarantee?

At εn=exp⁡[−(log⁡n)3]\varepsilon_n=\exp[-(\log n)^3], O(log⁡3n+log⁡Aeval)O(\log^3 n+\log A_{\mathrm{eval}}) bits suffice for the block evaluations on distinct separated discrete inputs. Here Aeval2−pA_{\mathrm{eval}}2^{-p} bounds the absolute error of a good block estimate at pp bits, including errors in its coefficients and kernel parameters.

If a strict majority lies within εblk\varepsilon_{\mathrm{blk}} of the true block sum, the median lies in the same interval. For target dual gap ε\varepsilon, Appendix L.2 (p. 25) takes

\qquad p\ge\left\lceil\log_2(A_{\mathrm{eval}}/\varepsilon_{\mathrm{blk}})\right\rceil,$$ where $m$ counts groups, $J$ is the restart length, and $D_{\mathrm{fp}}$ bounds the diameter of a feasible set retaining an optimum. Allowing another $m\varepsilon_{\mathrm{blk}}$ per coordinate for summation and other gradient arithmetic keeps the gradient error at most $\varepsilon/(8JD_{\mathrm{fp}})$. A feasible projection with optimality residual at most $\varepsilon/(8J)$ then suffices for all four SVM formulations. The arithmetic exponent carries over if input bit lengths, $\log A_{\mathrm{eval}}$, and the bit overhead for construction, evaluation, scalar functions, and projection are polylogarithmic in $n$.

Thanks for addressing my concerns! I will raise my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

We thank the reviewers for their questions. The revisions are marked in red.

  • Theorem 2 and blockwise counting. Section 1.1 (p. 2) clarifies that the query weights multiply individual Gaussian entries within each block. An exact example after Theorem 2 (Section 3.1, p. 4) uses an entry of the first product to set a negative weight in the next query. Section 3.2 (p. 5) credits Björklund and Kaski (2021, Section 4) for recovering each block count before summing.

  • Finite precision. Section 3.2 (p. 5) shows that the median preserves the error tolerance met by a strict majority of block estimates. Appendix L.2 (p. 25) derives block-evaluation and projection tolerances sufficient for the target dual objective error on distinct discrete inputs.

  • Explicit exponents. Table 2 (p. 8) gives the product saving σ\sigma, the training saving δ\delta, and the resulting exponent 2−δ2-\delta for three choices of dimension constant and alphabet size. Appendix L.1 (p. 25) derives the values.

  • Unit spacing. Section 4.1 (p. 6) now specifies that the lower eigenvalue bound 1−(n−1)q1-(n-1)q uses Kij≤qK_{ij}\le q for every i≠ji\ne j. Section 5 (p. 7) and Appendix L.3 (p. 26) give two guarantees for distinct unit-spaced Boolean inputs. One uses the observed kernel row sums, and the other applies to every such subset in d≤1.8log⁡nd\le1.8\log n.

  • Continuous coordinates and opposite labels. After Theorem 7 (p. 8), we give an upper bound on the dual optimum that holds for any labels when the discrete parts are distinct. Appendix H (p. 20) gives the exact hard-margin optimum for two oppositely labeled points sharing a discrete part.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.