PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Kernel Methods via Doubly Stochastic Gradients

Bo Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina Balcan, Le Song

arXiv:1407.5599v4cs.LGstat.ML

TL;DR

Kernel methods face scalability limits from dense kernel matrices and support-vector storage, motivating alternatives to neural networks for large nonlinear problems. The paper introduces doubly stochastic functional gradients, using random data points and kernel-associated random features, and reports optimal convergence rates, small dimension-independent memory, and competitive large-scale performance. A stated limitation is that the current proof relies on Lipschitz-smooth loss functions, despite applications to nonsmooth losses.

  • Problem

    Kernel methods are widely perceived as unscalable because dense kernel matrices require costly storage and computation, while neural nets have been preferred for large-scale nonlinear learning.

  • Method

    The method solves convex RKHS optimization problems with two unbiased stochastic functional-gradient approximations: random training points and kernel-associated random features.

  • Results

    The algorithm achieves O(1/t) convergence to the optimal RKHS function, O(1/√t) generalization performance, and competitive results with neural nets on large datasets.

  • Takeaways & Limitations

    Doubly stochasticity reduces kernel-machine memory from O(dn) to O(n) and supports scalable computation without retaining support vectors.

  • Takeaways & Limitations

    The current proof relies on Lipschitz smoothness of the loss function, although the algorithm was applied to nonsmooth losses.

Abstract

from arXiv · show

The general perception is that kernel methods are not scalable, and neural nets are the methods of choice for nonlinear learning problems. Or have we simply not tried hard enough for kernel methods? Here we propose an approach that scales up kernel methods using a novel concept called "doubly stochastic functional gradients". Our approach relies on the fact that many kernel methods can be expressed as convex optimization problems, and we solve the problems by making two unbiased stochastic approximations to the functional gradient, one using random training points and another using random functions associated with the kernel, and then descending using this noisy functional gradient. We show that a function produced by this procedure after $t$ iterations converges to the optimal function in the reproducing kernel Hilbert space in rate $O(1/t)$, and achieves a generalization performance of $O(1/\sqrt{t})$. This doubly stochasticity also allows us to avoid keeping the support vectors and to implement the algorithm in a small memory footprint, which is linear in number of iterations and independent of data dimension. Our approach can readily scale kernel methods up to the regimes which are dominated by neural nets. We show that our method can achieve competitive performance to neural nets in datasets such as 8 million handwritten digits from MNIST, 2.3 million energy materials from MolecularSpace, and 1 million photos from ImageNet.

1 Introduction

The paper addresses kernel methods’ scalability bottlenecks with doubly stochastic functional gradients, balancing computation, memory, and statistical performance. It combines stochastic sampling of training points and kernel-associated random features, with theoretical guarantees and large-scale empirical evaluations.

  • Dense kernel matrices require O(n2) space and O(n2d) computation, creating a central scalability bottleneck.
  • Existing low-rank and random-feature approximations can require nearly O(n) rank or features for strong generalization, while incurring substantial preprocessing or memory costs.
  • Doubly stochastic functional gradients use unbiased approximations based on random training points and kernel-associated random features.
  • The approach applies across kernel ridge regression, support vector machines, logistic regression, two-sample testing, and multiple kernel families.
  • The method allows random-feature flexibility to grow with data points, supporting streaming settings that fixed-feature approaches cannot readily handle.
  • At iteration t, computation is O(td) and memory is O(t), independent of data dimension, while support-vector storage is avoided.
  • O(1/t) convergence to the optimal RKHS function and O(1/√t) generalization bounds are established, with random-feature variance affecting only the final constant.
  • The method compares favorably with scalable kernel methods and neural nets on datasets including MNIST, MolecularSpace, and ImageNet.

2 Duality between Kernels and Random Processes

The section develops the duality between positive-definite kernels and random processes or features. This representation underpins the use of kernel-associated random features and extends across several kernel families.

  • A positive-definite kernel admits an integral representation through random features and a measure over random variables.
  • The representation links kernel values to expectations of products of random feature functions, although the representation need not be unique.
  • For continuous shift-invariant kernels, Bochner’s theorem characterizes positive definiteness through a finite nonnegative spectral measure.
  • Gaussian RBF, Laplace, and Matern kernels correspond respectively to Gaussian, Cauchy, and unit-ball-convolution-related random-feature distributions.
  • Explicit random-feature constructions also exist for rotation-invariant, polynomial, dot-product, and combinations of multiple kernels.

3 Doubly Stochastic Functional Gradients

The paper introduces doubly stochastic functional gradients for RKHS optimization by combining random data points with random kernel-associated functions. Both approximations remain unbiased, although the resulting random-feature function may lie outside the RKHS.

  • Many kernel methods can be formulated as convex optimizations over RKHS functions and solved using functional gradient descent.
  • The functional gradient is defined through the linear change in the objective caused by perturbing the function in an RKHS direction.
  • A stochastic functional gradient samples one training pair, while a doubly stochastic gradient adds a random feature sampled from P(ω).
  • Random features may lie outside the RKHS, as illustrated for Gaussian RBF features, but their expectation recovers the RKHS-valued stochastic gradient.
  • The resulting gradient estimator is unbiased because the stochastic functional gradient equals the expectation over random features of the doubly stochastic gradient.

4 Doubly Stochastic Kernel Machines

The algorithm applies doubly stochastic gradients across diverse kernel machines and loss functions, using seeded random features and lightweight coefficient updates. Its formulations also extend to Gaussian-process posterior quantities.

  • Algorithm: The algorithm samples one data point and one seeded random feature per iteration, then updates an additive function representation through scalar coefficients.
  • Algorithm: A learning rate γ_t chosen as O(1/t) supports the analyzed convergence rate, and fixed-dataset uniform sampling can replace access to the data distribution.
  • Applications: The method instantiates kernel machines for classification, regression, quantile regression, novelty detection, divergence estimation, and likelihood-ratio estimation.
  • Applications: Different loss derivatives produce updates for kernel SVM, logistic regression, ridge regression, robust regression, support-vector regression, and quantile regression.
  • Gaussian processes: For Gaussian-process regression, the posterior mean is obtained through kernel ridge regression, while predictive variance is addressed through separate convex optimizations.
  • Gaussian processes: Approximating the covariance operator requires O(t^2) memory, whereas estimating m test-point functions requires O(tm) memory.

5 Theoretical Guarantees

The analysis establishes convergence and generalization guarantees despite two stochastic approximations and iterates that may leave the RKHS. Martingale arguments control random-feature error while stochastic approximation handles random-data error.

  • O(1/t) convergence to the optimal RKHS function holds both in expectation and with high probability.
  • The estimator may lie outside the RKHS, so the proof constructs an intermediate RKHS function and separately bounds both error components.
  • The guarantees assume an optimal solution, Lipschitz-continuous loss derivative, bounded loss derivatives, and bounded kernel and random-feature products.
  • O(1/√t) generalization performance is obtained under the paper’s stated assumptions and probability guarantee.
  • The random-feature variance contributes additively to the constant rather than changing the overall O(1/t) convergence rate.

6 Computation, Memory and Statistics Trade-off

The paper compares computation, memory, and statistical requirements across scalable kernel algorithms under a fixed function-estimation error. Its method supports improving flexibility as more data arrive, unlike several fixed-rank approaches.

  • The comparison fixes ||f − f*||² ≤ ϵ and assumes O(1/ϵ) samples are needed for every method.
  • The proposed method, r-SDCA, r-Pegasos, r-SBMD, and r-RBCD achieve the best dimension dependence up to a logarithmic factor.
  • Increasing random-feature counts in several competing methods requires special procedures whose efficient theoretical guarantees are unclear.
  • At iteration t < n, the proposed algorithm is reported as the cheapest among the compared methods in per-iteration computation and memory.

7 Experiments

The experiments evaluate doubly stochastic kernel methods across synthetic, medium-scale, and large-scale tasks, comparing them with scalable kernel algorithms and neural networks. Results show theoretical convergence, competitive accuracy, and favorable computation or memory trade-offs in several settings.

  • Experimental setup: The evaluation covers Gaussian processes, kernel ridge regression, kernel SVM, and comparisons with convolutional neural networks across datasets of varying scale.Large-scale experiments compare against scalable kernel methods, while image experiments also compare fixed and jointly trained neural networks.
  • Kernel ridge regression: O(1/t) convergence is observed for the averaged kernel ridge regression solution on the synthetic dataset.Figure 4 uses a 1/t reference curve and reports convergence consistent with the theoretical rate.
  • Kernel ridge regression: The doubly stochastic method matches NORMA on the synthetic kernel ridge task with lower memory cost, while 28-feature Pegasos and SDCA perform worse.NORMA uses the full kernel; the alternatives use random or Nyström features.
  • Gaussian processes: Both the doubly stochastic method and NORMA converge to the Gaussian-process posterior, with comparable approximation of posterior mean and variance.The experiment evaluates both posterior quantities on synthetic data.
  • Kernel support vector machine: Kernel SVM performance varies by dataset: the method is competitive on Adult, weaker than full-kernel methods on Forest, and improves with more random features.On Adult it reaches 15.3% versus 15% for NORMA and k-SDCA; on Forest it reaches about 15% versus 10% for those full-kernel methods.
  • Kernel support vector machine: 0.26% test error is achieved on MNIST 8M 8-vs.-6, the best result under both stopping criteria with similar training time.The experiment uses PCA-reduced inputs and a Gaussian RBF kernel.
  • Comparisons to neural networks: Against neural networks, the method reports 0.5% versus 0.6% error in one comparison, approaches jointly trained networks on ImageNet, and achieves 2.97 versus 3.51 kcal/mole MAE on QuantumMachine.On the 2.3 million-material dataset, its performance is reported as comparable with a neural network.

8 Discussion

The discussion presents doubly stochastic functional gradients as a scalable kernel-machine approach with dimension-independent convergence analysis and practical implementation flexibility. It also identifies extending the current proof beyond smooth losses as future work.

  • The method reduces kernel-machine memory requirements from O(dn) to O(n) by introducing randomness associated with kernels alongside random data samples.
  • The analysis establishes an O(1/t) convergence rate for strongly convex stochastic optimization, independent of data dimension.
  • The current proof relies on Lipschitz smoothness of the loss, despite applications to kernel machines with non-smooth losses.Extending the guarantee to non-smooth loss functions is identified as future work.
  • The implementation can replace random-feature sampling with Fastfood, quasi-Monte Carlo, or data-dependent sampling, and can refine features by back-propagation.

A Convergence Rate

The appendix provides specific bounds and detailed proofs for the two error terms appearing in Theorem 4 and Theorem 5.

  • The appendix analyzes the two error terms appearing in Theorem 4 and Theorem 5.
  • It provides specific bounds for those error terms.
  • It also supplies detailed proofs for the stated bounds.

A.1 Error due to random features

This subsection establishes probabilistic bounds for the error associated with random features using martingale-difference arguments and induction-based estimates.

  • The random-feature error bounds are stated with probability at least 1 −δ over (Dt, ωt).
  • The analysis treats {Vi(x)} as a martingale difference sequence.
  • One proof proceeds by induction on i.

A.2 Error due to random data

This subsection bounds the error associated with random data by defining stochastic gradient terms, exploiting Lipschitz continuity, and deriving recursions for the iterates.

  • The sampled gradient is ˆgt = l′(ht(xt), yt)k(xt, ·) + νht, while ¯gt is its expectation over the data sample.
  • The update is ht+1 = ht −γtgt, so each iteration changes the current function using the stochastic gradient gt.
  • The analysis decomposes the stochastic-gradient behavior into Mt, Nt, and Rt terms and establishes bounds for them.
  • The resulting estimates are combined into a recursion for the expected error.
  • For specified step-size conditions, the analysis gives high-probability inequalities over (Dt, ωt).
  • The bound on Rt uses Lipschitz continuity of l′, the Cauchy–Schwarz inequality, and a bound on the kernel section norm.

B L∞distance, L2 distance, and generalization bound

The analysis establishes convergence bounds in RKHS-related distances and derives a corresponding generalization bound, with additional discussion of average-solution behavior.

  • L∞ distance: Theorem 4 implies an L∞ distance bound for the learned function.The bound follows by taking the maximum pointwise deviation over the input domain.
  • L∞ distance: The average solution can improve the L∞ bound by removing its logarithmic factor with more sophisticated analysis.This improvement is stated specifically for the average solution.
  • L2 distance: With probability at least 1 −3δ, the L2-distance bound holds under the step-size choices in Lemma 9.The displayed bound contains logarithmic factors in t and δ and constants C2 and κQ2.
  • Generalization bound: The L2-distance result is used to derive a high-probability bound on true risk.Theorem 6 defines true risk as Rtrue(f) = E(x,y)[l(f(x), y)] and states probability at least 1 −3δ.
  • Suboptimality: O(1/t) suboptimality is provided for the learned solution.The paper presents this as a bound for suboptimality rather than only distance to the optimum.
Loading 1407.5599v4…