Triply Stochastic Gradients on Multiple Kernel Learning

Xiang Li, Bin Gu, Shuang Ao, Huaimin Wang, Charles X. LingUAI 2017 · OpenReview

Abstract

Multiple Kernel Learning (MKL) offers a powerful framework for combining diverse data representations into non-linear models. However, its high computational complexity has historically limited its application to large-scale datasets. This paper introduces Triply Stochastic Gradient Descent (Triply SGD), an optimization strategy that scales MKL by simultaneously sampling data points, random features, and kernels. We demonstrate that Triply SGD achieves a convergence rate of $O(1/t)$, making MKL feasible for datasets with millions of instances on standard hardware.

Introduction

Kernel methods are renowned for their ability to learn complex, non-linear patterns. MKL extends this by automatically determining the optimal combination of multiple base kernels. Despite its theoretical appeal, MKL is computationally expensive, with traditional solvers scaling at $O(m \cdot l^2)$, where $m$ is the number of kernels and $l$ is the number of data points. While "Doubly Stochastic" methods improved scalability for single kernels by sampling data and random features, they lacked the ability to learn kernel weights dynamically. Triply SGD addresses this gap, enabling efficient weight learning alongside model parameters.

Methods: Triple Randomness

The core innovation of Triply SGD is the introduction of a third level of randomness to the optimization process:

  1. Data Point Sampling: Standard SGD approach to handle large dataset sizes ($l$).
  2. Random Feature Sampling: Utilizing Rahimi-Recht random feature mapping to approximate kernels, avoiding the computation of full kernel matrices.
  3. Kernel Sampling: Instead of updating all $m$ kernels in every iteration, the algorithm stochastically selects a single kernel for update.

By employing $l_p$-norm regularization ($p > 1$), the authors ensure strong convexity. They derive a functional gradient to update both decision functions and kernel weights simultaneously. Theoretical analysis confirms that this triple-sampling approach maintains the $O(1/t)$ convergence rate characteristic of Doubly SGD.

Experimental Setup

The method was evaluated on several large-scale benchmarks:

  • covtype: 581,012 instances.
  • epsilon: 400,000 instances.
  • mnist8m: 8.1 million handwritten digits (binary and 10-class).
  • cifar10: 50,000 images, using features from pre-trained ResNet and CNN models.

Key Results and Insights

Convergence and Accuracy

Triply SGD converges significantly faster than traditional MKL baselines such as OBSCURE, UFO, and p-norm MKL. As shown in the figure below, Triply SGD (represented in pink) consistently reaches lower test error in less training time across diverse datasets.

Test error vs. training time across various datasets. TriplySGD (pink) demonstrates faster convergence and lower error compared to baselines.

Scalability and Data Efficiency

A major advantage of Triply SGD is its low memory footprint, never exceeding 16 GB of RAM even for 8.1 million data points. Unlike traditional solvers that require lengthy pre-computation phases, Triply SGD begins learning immediately. Furthermore, experiments illustrate that Triply SGD's accuracy continues to improve as training size increases, whereas baseline methods often plateau due to memory constraints.

Test error vs. training size. TriplySGD scales effectively to larger datasets, maintaining a downward trend in error compared to fixed-memory baselines.

The Importance of Weight Learning

Comparisons against a "naive" Doubly SGD extension (concatenating kernels with fixed weights) revealed that Triply SGD consistently achieves lower test error. This confirms that dynamically learning kernel weights is essential for maximizing model performance.

Conclusion

Triply SGD successfully brings Multiple Kernel Learning into the big data era. By combining triple stochastic sampling with strong theoretical guarantees, it offers a scalable and accurate solution for high-dimensional, large-scale problems. Future work may explore sensitivity to hyperparameters and the application of this method to more complex kernel types, such as string or graph kernels, as well as distributed implementations for web-scale datasets.

Summary updated

BibTeX
@inproceedings{li2017triply,
  author = {Xiang Li and Bin Gu and Shuang Ao and Huaimin Wang and Charles X. Ling},
  title = {{Triply Stochastic Gradients on Multiple Kernel Learning}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=1LE5EWw4JW},
}
Figure