Truly Subquadratic High-Precision Gaussian SVM Training on Structured Inputs

We establish truly subquadratic randomized algorithms for high-precision Gaussian support vector machine training by exploiting coordinate structure. For every fixed $C$, we give randomized algorithms that train $n$ inputs from a sufficiently separated fixed-size real alphabet in $d\le C\log n$ dimensions to additive dual objective error $\exp [-(\log n{)}^3]$ using $n^{2-\delta +o(1)}$ arithmetic operations for some constant $\delta >0$, 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 $k\le c\log n/\log \log n$ additional arbitrary real coordinates, for any fixed $c<0.16$, using subquadratic space.