{"id":8752,"date":"2025-12-01T07:02:52","date_gmt":"2025-12-01T07:02:52","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/12\/01\/2511-21890\/"},"modified":"2025-12-01T07:02:52","modified_gmt":"2025-12-01T07:02:52","slug":"2511-21890","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/12\/01\/2511-21890\/","title":{"rendered":"Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations"},"content":{"rendered":"

Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2511.21890v1 Announce Type: new
\nAbstract: 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.<\/div>\n

\t

\n
<\/BR>
\n Dimitris Bertsimas, Caio de Prospero Iglesias, Nicholas A. G. Johnson
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations arXiv:2511.21890v1 Announce Type: new Abstract: 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,112],"tags":[1015,1135,1957],"class_list":["post-8752","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-stat-ml","tag-best","tag-kernel","tag-response"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8752"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=8752"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/8752\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=8752"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=8752"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=8752"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}