Efficient Kernel Learning from Side Information Using ADMM
This work addresses the scalability bottleneck of kernel matrix learning for large datasets, offering a practical solution for practitioners in machine learning.
The paper proposes an ADMM-based solver for kernel learning from side information that avoids expensive eigen-decomposition, achieving one to two orders of magnitude speedup while maintaining accuracy comparable to direct SDP solvers.
Side information is highly useful in the learning of a nonparametric kernel matrix. However, this often leads to an expensive semidefinite program (SDP). In recent years, a number of dedicated solvers have been proposed. Though much better than off-the-shelf SDP solvers, they still cannot scale to large data sets. In this paper, we propose a novel solver based on the alternating direction method of multipliers (ADMM). The key idea is to use a low-rank decomposition of the kernel matrix $\K = \V^\top \U$, with the constraint that $\V=\U$. The resultant optimization problem, though non-convex, has favorable convergence properties and can be efficiently solved without requiring eigen-decomposition in each iteration. Experimental results on a number of real-world data sets demonstrate that the proposed method is as accurate as directly solving the SDP, but can be one to two orders of magnitude faster.