Research map / Learning theory and algorithms / Kernels and regression theory

Joker: Joint Optimization Framework for Lightweight Kernel Machines

ICML 2025 · Learning theory and algorithms › Kernels and regression theory · approach: RKHS kernel methods

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Joker, a dual block coordinate descent with trust region (DBCD-TR) framework with random Fourier features that trains lightweight kernel machines (KRR, Huber, SVM, KLR, SVR) on large datasets using under 2GB-5GB GPU memory.

Problem

Large-scale kernel methods have high memory overhead (e.g., Falkon needs O(M^2) memory for the preconditioner) and research has focused mainly on KRR, with other models such as kernel logistic regression and SVM less scalable.

Approach

Unifies kernel models (KRR, Huber, SVC/SVR, KLR) under a dual formulation with box constraints, solves it with a block coordinate descent whose subproblems use a trust-region method with a truncated CG-Steihaug step handling box constraints, and uses random Fourier features so the solver maintains a weight vector instead of kernel blocks, avoiding Nystrom's O(M^2) memory.

Key results

• Joker-KRR uses 0.7GB to 5.3GB peak GPU memory across datasets, versus about 6-10GB for Falkon and 1.6-7GB for EigenPro3, while matching or beating baselines on most datasets.
• On HIGGS, Joker-SVM reaches 82.40% AUC and 74.41% accuracy, above Falkon (80.90% AUC, 73.42% ACC) and LogFalkon.
• Joker-KLR attains the best CIFAR-5M accuracy of 74.88% versus 68.24% for Falkon and 72.94% for EigenPro3, though it uses more time and memory than the other Joker models.

Measured effects reported in the paper

Surprising findings

• Nystrom is argued to be unsuitable here because its per-block cost of O(M^2+Md) is too expensive, despite its popularity in prior work.
• ThunderSVM's SMO solver converges slowly at large penalty values, and Joker-SVM is both faster and lighter in those settings.

Limitations

• Convergence rate of DBCD-TR is not theoretically characterized beyond a linear rate; sharper analysis left open.
• KLR is ill-conditioned near boundaries and needs a larger block size (1024) and numerical modifications, making it slower and more memory-hungry.
• Only one-versus-rest is used for multi-class problems; multi-class SVM and softmax regression are left for future work.

Experimental setup

Datasets: MSD HEPC SUSY HIGGS CIFAR-5M

Benchmarks: MSD HEPC SUSY HIGGS CIFAR-5M

Metrics: relative error RMSE AUC accuracy training time peak GPU memory

Baselines: Falkon LogFalkon EigenPro3 ThunderSVM LIBSVM

Builds on: Falkon EigenPro ThunderSVM LIBSVM random Fourier features

Closest papers by meaning

• On the Target-kernel Alignment: a Unified Analysis with Kernel Complexity (NeurIPS 2024 · similarity 0.86)
• Faster Algorithms for Structured Linear and Kernel Support Vector Machines (ICLR 2025 · similarity 0.86)
• Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.85)
• Generalization in Kernel Regression Under Realistic Assumptions (ICML 2024 · similarity 0.85)
• Learning Curves of Stochastic Gradient Descent in Kernel Regression (ICML 2025 · similarity 0.85)
• Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.85)