- 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 . However, this paper leverages the special structure of the discrete data to achieve 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
-
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 training time at error . 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).
-
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).
-
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
-
No numerical or empirical evidence. The paper is purely asymptotic. Key quantities are never instantiated: the exponent saving with is vanishingly small for moderate or alphabet size ( carries an factor, Appendix D); the success probability and all exponents are meaningless without a single data point showing at what the crossover against a naive 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.
-
Strong input restrictions. The guarantee requires well-separated alphabets (, i.e., ) and . 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 decays fast in and (, with an dependence in Appendix D). Could you provide (a) a table of instantiated constants (, , and the resulting exponent) for a few concrete values of and , 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 and that the Lemma 3 success event holds simultaneously across adaptive queries, on instances of moderate size?
Q2. Separation in practice. The condition (equivalently ) 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 is not small), does any non-trivial subquadratic guarantee remain?
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), the respective pairs (σ,δ) are approximately (2.602,2.276)×10−9, (7.787,6.814)×10−10, and (3.684,3.223)×10−12. Each gives worst-case training time n2−δ+o(1) at εn=exp[−(logn)3]. The O(nσ/8log(n/ε)) products in training use only one eighth of the per-product exponent saving, leaving δ=7σ/8. Appendix L.1 (p. 25) derives these sufficient choices.
These exponents quantify the asymptotic saving over explicit Gram construction, which writes Θ(n2) entries. A wall-clock crossover at a particular n 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/2, so every kernel entry is rational. Write eu for the basis vector at string u. Querying with e07 returns zx=2−∣x∣, where ∣x∣ counts the ones in x. Use the returned value z17=1/128 to form the signed query v=e07−z17e17. Its product has (Kv)x=2−∣x∣−2∣x∣−14 in every coordinate, including exact cancellation at x=17.
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−10. Those majorities are fixed before the first query, so one preprocessing succeeds for every adaptive query with probability at least 1−n−10.
Q2. Unit spacing and one-hot encodings
At unit spacing, Corollary 16 gives deterministic n1.94241+o(1) training at εn for every distinct Boolean subset in d≤1.8logn. For distinct binary encodings in d≤Clogn, Corollary 14 gives n2−σ(C)+o(1)log(n/ε) time whenever the largest observed off-diagonal kernel row sum is at most 1/2. One K1 query tests this condition. For concatenated one-hot fields at unit spacing, two records differing in t fields contribute e−2t to each other's row sum. Both guarantees cover all four SVM formulations (Appendix L.3, p. 26).
The identity ρ=e−a2 in the question holds for a two-symbol alphabet of spacing a. For a larger alphabet br, Theorem 6 uses the full row sum ρ=maxr∑s=re−(br−bs)2.