Abstract
Learning a computationally efficient kernel from data is an important machine learning problem. The majority of kernels in the literature do not leverage the geometry of the data, and those that do are computationally infeasible for contemporary datasets. Recent advances in approximation techniques have expanded the applicability of the kernel methodology to scale linearly with the data size. Data-dependent kernels, which could leverage this computational advantage, have however not yet seen the benefit. Here we derive an approximate large-scale learning procedure for data-dependent kernels that is efficient and performs well in practice. We provide a Lemma that can be used to derive the asymptotic convergence of the approximation in the limit of infinite random features, and, under certain conditions, an estimate of the convergence speed. We empirically prove that our construction represents a valid, yet efficient approximation of the data-dependent kernel. For large-scale datasets of millions of datapoints, where the proposed method is now applicable for the first time, we notice a significant performance boost over both baselines consisting of data independent kernels and of kernel approximations, at comparable computational cost.
Introduction
Kernel methods, such as Support Vector Machines (SVMs), are renowned for their strong theoretical foundations and effectiveness in non-linear classification. However, they face two significant challenges in the era of big data: scalability and data-blindness. Standard kernel methods require the computation and inversion of an $N \times N$ Gram matrix, leading to $O(N^3)$ computational complexity, which is prohibitive for datasets with millions of points. Furthermore, popular kernels like the Radial Basis Function (RBF) are data-independent, failing to account for the underlying manifold structure of the data.
Data-dependent kernels offer a solution by "warping" the feature space to follow the natural geometry of the data, making them ideal for semi-supervised learning. Historically, however, these kernels have been even more computationally expensive than their data-independent counterparts. This paper bridges that gap by introducing a scalable, $O(N)$ approximation for data-dependent kernels.
Methodology
The proposed method achieves linear scalability through the integration of three key mathematical components:
- Random Fourier Features (RFF): Instead of computing the full kernel matrix, the authors use a randomized feature map $\Phi$ that approximates the kernel, transforming the non-linear problem into a linear one in a higher-dimensional space.
- Manifold Regularization: A graph Laplacian matrix ($L$) is utilized to capture the geometry of both labeled and unlabeled data, allowing information to propagate along the data manifold.
- Sherman-Morrison-Woodbury (SMW) Identity: This is the critical innovation. By applying the SMW identity, the authors transform the inversion of a massive $N \times N$ matrix into the inversion of a $d \times d$ matrix, where $d$ is the number of random features. Since $d \ll N$ in large-scale settings, this reduces complexity from cubic to linear.
Experimental Results
The authors evaluated their method on several benchmarks, ranging from toy datasets like "Two Moons" to massive real-world datasets like Human3.6M (over 1 million samples).
Approximation Quality and Efficiency
Empirical results confirm that the "warped" kernel approximation is not only faster but also more accurate than standard approximations. As shown in the error analysis, the warped kernel converges more rapidly toward the true kernel values as the number of random features increases.
In terms of efficiency, training on the MNIST dataset (70,000 samples) with 10,000 features took only a few hundred seconds—a task previously considered infeasible for data-dependent methods. The linear scaling of computation time with respect to dimensionality ensures the method's viability for high-dimensional tasks.
Performance on Large-Scale Data
The most significant result was observed on the Human3.6M dataset. In a 3D pose estimation task with limited labels, the data-dependent approximation (LapRFKRR) reduced the error from 97.37mm (using standard RFKRR) to 93.2mm. This demonstrates that leveraging the manifold structure of unlabeled data provides a tangible performance boost in large-scale, semi-supervised scenarios.
Conclusion
This work presents the first practical framework for applying data-dependent kernels to datasets with millions of entries. By combining Random Fourier Features with the Sherman-Morrison-Woodbury identity, the authors achieve $O(N)$ complexity without sacrificing the benefits of manifold awareness. While challenges remain regarding the initial construction of the graph Laplacian and hyperparameter tuning, this method represents a major step forward in making sophisticated kernel methods accessible for modern big data applications.
Summary updated