# Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations

arXiv: https://arxiv.org/abs/2511.21890 · HTML: https://mlsanity.com/paper/2511.21890/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 34 references that are in the map.
- First posted on arXiv 26 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Interactive Supercomputing on 40,000 Cores for Machine Learning and Data Analysis](https://mlsanity.com/paper/1807.07814/) (2018)
- [MKLpy: a python-based framework for Multiple Kernel Learning](https://mlsanity.com/paper/2007.09982/) (2020)
- [Sparse PSD approximation of the PSD cone](https://mlsanity.com/paper/2002.02988/) (2020)
- [On Approximations of the PSD Cone by a Polynomial Number of Smaller-sized PSD Cones](https://mlsanity.com/paper/2105.02080/) (2021)

## Abstract (arXiv)

We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing l1 regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an l2 penalty for robustness. We solve the resulting non-convex minimax problem via an alternating best response algorithm with two subproblems: the alpha subproblem is a standard kernel SVM dual solved via LIBSVM, while the beta subproblem admits an efficient solution via the Greedy Selector and Simplex Projector algorithm. We reformulate SMKL as a mixed integer semidefinite optimization problem and derive a hierarchy of semidefinite convex relaxations which can be used to certify near-optimality of the solutions returned by our best response algorithm and also to warm start it. On ten UCI benchmarks, our method with random initialization outperforms state-of-the-art MKL approaches in out-of-sample prediction accuracy on average by 3.34 percentage points (relative to the best performing benchmark) while selecting a small number of candidate kernels in comparable runtime. With warm starting, our method outperforms the best performing benchmark's out-of-sample prediction accuracy on average by 4.05 percentage points. Our convex relaxations provide a certificate that in several cases, the solution returned by our best response algorithm is the globally optimal solution.