Abstract
We study the problem of learning a kernel matrix from an apriori kernel and training data. In this context, we propose a new unconstrained convex optimization formulation, with an arbitrary convex second-order differentiable loss function on kernel entries and a LogDet divergence term for regularization. Since the number of variables is of order $O(n^2)$, the computational cost of standard Newton and quasi-Newton methods for learning a kernel matrix is prohibitive. Here an operator form Hessian is used to develop an $O(n^3)$ trust-region inexact Newton method, where the Newton direction is computed using several conjugate gradient steps on the Hessian operator equation. On the uspst dataset, our algorithm can handle 2 million optimization variables within one hour. Experiments are shown for both linear (Mahalanobis) metric learning and for kernel learning. The convergence rate, speed and performance of several loss functions and algorithms are discussed.
Introduction
Kernel learning is a fundamental task in machine learning, where the goal is to determine an optimal similarity matrix directly from data. However, this task faces two significant hurdles: the requirement that the kernel matrix be positive semi-definite (PSD) and the high dimensionality of the optimization space ($O(n^2)$ variables for $n$ data points). Traditional Semi-Definite Programming (SDP) approaches are often too slow to scale to large datasets.
Methodology
This paper proposes a framework that transforms kernel learning into an unconstrained optimization problem.
The LogDet Barrier
Rather than enforcing PSD constraints explicitly, we utilize the LogDet divergence as a regularizer. The term $\log \det(K)$ acts as a natural barrier, approaching infinity as eigenvalues near zero. This ensures the resulting matrix remains within the PSD cone while allowing for smooth, unconstrained optimization.
Trust-Region Inexact Newton (TRIN)
To manage millions of variables, we avoid the $O(n^4)$ complexity of explicit Hessian construction. Instead, we employ a Hessian operator that maps matrices to matrices, reducing complexity to $O(n^3)$. The Newton system is solved approximately using Conjugate Gradient (CG) steps, further accelerated by a specialized preconditioner.
Regularization Path and Warm-Starts
The solution path relative to the regularization parameter $\gamma$ mirrors the "central path" of interior-point methods. This property enables efficient "warm-starts," where the solution for one $\gamma$ serves as an excellent starting point for the next, significantly speeding up the computation of a full regularization path.
Experimental Results
The TRIN algorithm was evaluated against standard benchmarks and the popular ITML algorithm.
Scalability and Speed
A key advantage of TRIN is its robustness to the number of constraints ($c$). While ITML's performance degrades as constraints increase, TRIN's execution time remains relatively stable across different constraint densities.
On the USPST dataset, which involves over 2 million optimization variables, the TRIN algorithm successfully converged in approximately one hour, demonstrating its practical scalability for large-scale kernel learning.
Accuracy
The method achieved state-of-the-art error rates across various UCI datasets (Breast Cancer, Sonar, Ionosphere, Heart, and Wine). Notably, it outperformed Laplacian Eigenmaps and standard linear metrics on the Heart and Wine datasets.
Conclusion
By reformulating kernel learning as an unconstrained problem and leveraging an operator-form Newton method, we achieve a significant leap in scalability. The shift from $O(n^4)$ to $O(n^3)$ complexity makes learning kernels with millions of variables feasible. Future work will explore other divergence functions and further exploit potential sparsity in constraint matrices.
Summary updated