Kybernetika 62 no. 3, 481-512, 2026

MKL-$L_{0/1}$-SVM

Bin Zhu and Yijie ShiDOI: 10.14736/kyb-2026-3-0481

Abstract:

This paper presents a Multiple Kernel Learning (abbreviated as MKL) framework for the Support Vector Machine (SVM) with the $(0, 1)$ loss function in the context of the binary classification task. Some KKT-like first-order optimality conditions are provided and then exploited to develop a fast ADMM algorithm to solve the nonsmooth nonconvex optimization problem. Convergence analysis of the ADMM is presented under certain technical assumptions. Numerical experiments on real data sets show that our MKL-$L_{0/1}$-SVM can potentially outperform one of the leading approaches called SimpleMKL developed by Rakotomamonjy, Bach, Canu, and Grandvalet [Journal of Machine Learning Research, vol. 9, pp. 2491--2521, 2008] in terms of the accuracy of classification and the sparsity in the combination of kernels.

Keywords:

alternating direction method of multipliers, kernel SVM, nonsmooth nonconvex optimization, Multiple Kernel Learning, (0, 1)-loss function

Classification:

46E22, 90C26

paper.pdf

References:

  1. N. Aronszajn: Theory of reproducing kernels. Trans. American Math. Soc. 68 (1950), 337-404.   DOI:10.1090/S0002-9947-1950-0051437-7
  2. H. Attouch, J. Bolte and B. F. Svaiter: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programming 137 (2013), 91-129.   DOI:10.3917/ris.091.0129
  3. F. R. Bach, G. R. Lanckriet and M. I. Jordan: Multiple kernel learning, conic duality, and the SMO algorithm. In: Proc. 21st International Conference on Machine Learning, 2004, pp. 41-48.   CrossRef
  4. J. Bolte, S. Sabach and M. Teboulle: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146 (2014), 59-494.   DOI:10.1007/s10107-013-0701-9
  5. R. I. Boţ and D. K. Nguyen: The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Math. Oper. Res. 45 (2020), 682-712.   DOI:10.1287/moor.2019.1008
  6. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein and et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3 (2011), 1-122.   CrossRef
  7. S. P. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press, 2004.   DOI:10.1017/S275390670000070X
  8. C. Cortes and V. Vapnik: Support-vector networks. Machine Learning 20 (1995), 273-297.   DOI:10.1023/A:1022627411411
  9. T. Hastie, R. Tibshirani and M. Wainwright: Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton 2015.   CrossRef
  10. M. Hong, Z. Q. Luo and M. Razaviyayn: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26 (2016), 337-364.   DOI:10.1137/140990309
  11. G. Kimeldorf and G. Wahba: Some results on Tchebycheffian spline functions. J. Math. Analysis Appl. 33 (1971), 82-95.   DOI:10.1016/0022-247X(71)90184-3
  12. G. R. Lanckriet, N. Cristianini, P. Bartlett, L. E. Ghaoui and M. I. Jordan: Learning the kernel matrix with semidefinite programming. J. Machine Learn. Res. 5 (2004), 27-72.   CrossRef
  13. G. Li and T. K. Pong: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25 (2015), 2434-2460.   DOI:10.1137/140998135
  14. M. Nikolova: Description of the minimizers of least squares regularized with $\ell_0$-norm. uniqueness of the global minimizer. SIAM J. Imaging Sci. 6 (2013), 904-937.   DOI:10.1137/11085476X
  15. V. I. Paulsen and M. Raghupathi: An Introduction to the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies in Advanced Mathematics 152, Cambridge University Press, Cambridge 2016.   CrossRef
  16. A. Rakotomamonjy, F. Bach, S. Canu and Y. Grandvalet: SimpleMKL. J. Machine Learn. Res. 9 (2008), 2491-2521.   CrossRef
  17. B. Schölkopf and A. J. Smola: Learning with Kernels. Adaptive Computation and Machine Learning 4, MIT Press, Cambridge 2001.   CrossRef
  18. Y. Shi and B. Zhu: An ADMM solver for the {MKL-$L_{0/1}$-SVM}. In: Proc. 62nd IEEE Conference on Decision and Control (CDC 2023), Singapore 2023, pp. 3339-3346.   CrossRef
  19. K. Slavakis, P. Bouboulis and S. Theodoridis: Online learning in reproducing kernel Hilbert spaces. In: Academic Press Library in Signal Processing 1, Academic Press, Cambridge 2014, pp. 883-987.   CrossRef
  20. S. Sonnenburg, G. Rätsch, C. Schäfer and B. Schölkopf: Large scale multiple kernel learning. J. Machine Learn. Res. 7 (2006), 1531-1565.   CrossRef
  21. S. Theodoridis: Machine Learning: A Bayesian and Optimization Perspective. (Second edition.) Academic Press, Cambridge 2020.   CrossRef
  22. V. Vapnik: The Nature of Statistical Learning Theory. (Second edition.) Springer Science and Business Media, New York 2000.   CrossRef
  23. H. Wang, Y. Shao, S. Zhou, C. Zhang and N. Xiu: Support vector machine classifier via ${L}_{0/1}$ soft-margin loss. IEEE Trans. Pattern Anal. Machine Intell.44 (2022), 7253-7265.   DOI:10.1109/TPAMI.2021.3092177
  24. L. Wang, W. Liu and B. Zhu: ADMM for $\ell_0$ factor analysis. In: Proc. 13th IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM 2024), Corvallis 2024.   CrossRef
  25. L. Wang, W. Liu and B. Zhu: $\ell_0$ factor analysis. In: Proc. 63rd IEEE Conference on Decision and Control (CDC 2024), Milan 2024, pp. 7214-7219.   CrossRef
  26. L. Wang, W. Liu and B. Zhu: A Newton interior-point method for $\ell_0$ factor analysis. In: Proc. 64th IEEE Conference on Decision and Control (CDC 2025), Rio de Janeiro 2025, pp. 3232-3237.   CrossRef
  27. L. Wang, B. Zhu and W. Liu: $\ell_0$ factor analysis: A P-stationary point theory. IEEE Trans. Automat. Control 70 (2025), 6050-6063.   DOI:10.1109/TAC.2025.3552869
  28. W. Wang and M. A. Carreira-Perpinán: Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint: 1309.1541, 2013.   CrossRef
  29. Y. Wang, W. Yin and J. Zeng: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Scientific Computing 78 (2019), 29-63.   DOI:10.1007/s10915-018-0757-z
  30. L. Yang, T. K. Pong and X. Chen: Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction. SIAM J. Imaging Sci. 10 (2017), 74-110.   DOI:10.1137/15M1027528
  31. Y. Zhang, N. Zhang, D. Sun and K. C. Toh: A proximal point dual Newton algorithm for solving group graphical {L}asso problems. SIAM J. Optim. 30 (2020), 2197-2220.   DOI:10.1137/19M1267830
  32. S. Zhou: Gradient projection Newton pursuit for sparsity constrained optimization. Appl. Comput. Harmonic Anal. 61 (2022), 75-100.   DOI:10.1016/j.acha.2022.06.002
  33. S. Zhou, L. Pan and N. Xiu: Newton method for $\ell_0$-regularized optimization. Numer. Algorithms (2021), 1-30.   CrossRef
  34. S. Zhou, L. Pan, N. Xiu and H. D. Qi: Quadratic convergence of smoothing Newton's method for 0/1 loss optimization. SIAM J. Optim. 31 (2021), 3184-3211.   DOI:10.1137/21M1409445
  35. S. Zhou, N. Xiu and H. D. Qi: Global and quadratic convergence of {N}ewton hard-thresholding pursuit. J. Machine Learn. Res. 22 (2021), 1-45.   CrossRef