Research map / Learning theory and algorithms / Kernels and regression theory
Efficient Convex Algorithms for Universal Kernel Learning
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 an SVD-plus-QP Frank-Wolfe primal-dual algorithm for learning tessellated (semiseparable) kernels parameterized by positive matrices, replacing SDP, and extends the framework to SVM regression.
Problem
Kernel learning over a tractable, dense, universal set of kernels parameterized by positive matrices was limited to classification and required computationally expensive SDP solvers, limiting the data size that can be processed.
Approach
Reformulates the SDP-based generalized kernel learning as a minimax saddle-point problem, decomposing it into a QP subproblem (SVM over fixed kernel) and an analytic SVD subproblem (minimum singular vector of a n_P x n_P matrix), solved via Frank-Wolfe with an accelerated primal-dual variant as an option; also extends to regression.
Key results
- The Frank-Wolfe algorithm is about 100 times faster than the previous SDP-based algorithm on Liver, Cancer, Heart and Pima datasets (e.g., Liver 95.75 s SDP vs 0.12 s proposed).
- Average MSE of TKL across six regression datasets is reported as 23.6% improvement relative to the average of other algorithms, better than all other tested methods including XGBoost.
- On six classification datasets TKL achieves above-average test accuracy on all datasets, with an average 6.77% improvement over the average of all algorithms, close to AMKL's 6.84%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TKL instead of XGBoost | Regression · CCPP | MSE: 10.57 $\pm$ 0.82 vs 8.98 $\pm$ 0.81 | Hurt |
| Use TKL instead of SMKL | Regression · Airfoil | MSE: 4.33 $\pm$ 0.79 -> 1.41 $\pm$ 0.44 | Helped |
| Use TKL instead of XGBoost | Regression · CA | MSE: .012 $\pm$ .0003 vs .0092 $\pm$ .0002 | Hurt |
| Use TKL instead of SMKL | Regression · Space | MSE: .019 $\pm$ .005 -> .013 $\pm$ .001 | Helped |
| Use TKL instead of XGBoost | Regression · Boston Housing | MSE: 10.36 $\pm$ 5.80 vs 9.40 $\pm$ 4.17 | Hurt |
| Use TKL instead of the strongest listed baseline | Classification · Hill Valley | accuracy: 86.70 $\pm$ 5.49 vs 94.71 $\pm$ 1.72 | Hurt |
| Use TKL instead of NNet | Classification · Transfusion | accuracy: 77.84 $\pm$ 3.89 vs 78.78 $\pm$ 3.26 | Hurt |
| Use TKL instead of XGBoost | Classification · Shill Bid | accuracy: 99.61 $\pm$ 0.06 -> 99.76 $\pm$ 0.08 | Helped |
| Use TKL instead of SMKL | Classification · German | accuracy: 74.30 $\pm$ 3.55 -> 75.80 $\pm$ 1.89 | Helped |
| Use TKL instead of NNet | Classification · FourClass | accuracy: 99.77 $\pm$ 0.32 vs 99.99 $\pm$ 0.01 | Hurt |
| Replace the SDP-based method with the proposed algorithm | Kernel learning · Liver | computation time (s): 95.75 $\pm$ 2.68 -> 0.12 $\pm$ 0.03 | Helped |
| Replace the SDP-based method with the proposed algorithm | Kernel learning · Cancer | computation time (s): 636.17 $\pm$ 25.43 -> 0.41 $\pm$ 0.23 | Helped |
Surprising findings
- The optimal P in the saddle-point solution is always rank one, so the SVD subproblem reduces to a minimum singular vector computation.
- Random Forest and XGBoost are much faster than TKL, but TKL's computation time is comparable to neural networks despite its complexity.
Limitations
- TKL is noticeably slower than RF and XGBoost, and the reported computation times are on a single desktop.
- Several benchmark results are reported as N/A where algorithms exceeded 24 hours (e.g., SMKL on Gas Turbine).
- Reported averages are based on only 5 random splits and the benchmark datasets were chosen arbitrarily.
Experimental setup
Datasets: Liver Cancer Heart Pima Hill Valley Shill Bid Abalone Transfusion German FourClass Gas Turbine Airfoil
Benchmarks: Liver Cancer Heart Pima Hill Valley Shill Bid Abalone Transfusion German FourClass Gas Turbine Airfoil
Metrics: test set accuracy mean squared error computation time duality gap
Baselines: SDP-based tessellated kernel learning SimpleMKL Neural Networks Random Forest XGBoost AverageMKL PWMK CKA
Builds on: Tessellated kernel learning SDP SimpleMKL Frank-Wolfe algorithm accelerated primal-dual algorithm
Closest papers by meaning
- Infinite Kernel Learning: Generalization Bounds and Algorithms (AAAI 2017 · similarity 0.85)
- Optimality Implies Kernel Sum Classifiers are Statistically Efficient (ICML 2019 · similarity 0.83)
- Joker: Joint Optimization Framework for Lightweight Kernel Machines (ICML 2025 · similarity 0.81)
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.81)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.80)
- Scalable Kernel Inverse Optimization (NeurIPS 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.