Joker: Joint Optimization Framework for Lightweight Kernel Machines

2025/05/23 by Zhang, Junhong, Lai, Zhihui
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2505.17765

Abstract

Kernel methods are powerful tools for nonlinear learning with well-established theory. The scalability issue has been their long-standing challenge. Despite the existing success, there are two limitations in large-scale kernel methods: (i) The memory overhead is too high for users to afford; (ii) existing efforts mainly focus on kernel ridge regression (KRR), while other models lack study. In this paper, we propose Joker, a joint optimization framework for diverse kernel models, including KRR, logistic regression, and support vector machines. We design a dual block coordinate descent method with trust region (DBCD-TR) and adopt kernel approximation with randomized features, leading to low memory costs and high efficiency in large-scale learning. Experiments show that Joker saves up to 90% memory but achieves comparable training time and performance (or even better) than the state-of-the-art methods.

Citations

• Fast training of large kernel models with delayed projections
• Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regression
• Toward Large Kernel Models
• Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS
• On the Similarity between the Laplace and Neural Tangent Kernels
• Kernel methods through the roof: handling billions of points efficiently
• On Fast Leverage Score Sampling and Optimal Learning
• GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• FALKON: An Optimal Large Scale Kernel Method
• Diving into the shallows: a computational perspective on large-scale shallow learning
• GPflow: A Gaussian process library using TensorFlow
• Large Scale Kernel Learning using Block Coordinate Descent
• Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Scalable Kernel Methods via Doubly Stochastic Gradients
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Iteration Complexity of Randomized Block-Coordinate Descent Methods for Minimizing a Composite Function
• Выпуклая оптимизация

Related

• High-performance Kernel Machines with Implicit Distributed Optimization and Randomization
• Doubly stochastic large scale kernel learning with the empirical kernel map
• McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
• Data-driven kernel designs for optimized greedy schemes: A machine learning perspective
• How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets