Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
kernel SVM; (0; 1)-loss function; nonsmooth nonconvex optimization; Multiple Kernel Learning; alternating direction method of multipliers
kernel SVM; (0; 1)-loss function; nonsmooth nonconvex optimization; Multiple Kernel Learning; alternating direction method of multipliers
Summary:
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.
References:
[1] Aronszajn, N.: Theory of reproducing kernels. Trans. American Math. Soc. 68 (1950), 337-404. DOI
[2] Attouch, H., Bolte, J., Svaiter, B. F.: 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
[3] Bach, F. R., Lanckriet, G. R., Jordan, M. I.: Multiple kernel learning, conic duality, and the SMO algorithm. In: Proc. 21st International Conference on Machine Learning, 2004, pp. 41-48.
[4] Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146 (2014), 59-494. DOI
[5] Boţ, R. I., Nguyen, D. K.: The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates. Math. Oper. Res. 45 (2020), 682-712. DOI
[6] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., al., et: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3 (2011), 1-122.
[7] Boyd, S. P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004. DOI | Zbl 1058.90049
[8] Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20 (1995), 273-297. DOI
[9] Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity: The Lasso and Generalizations. CRC Press, Boca Raton 2015.
[10] Hong, M., Luo, Z. Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26 (2016), 337-364. DOI
[11] Kimeldorf, G., Wahba, G.: Some results on Tchebycheffian spline functions. J. Math. Analysis Appl. 33 (1971), 82-95. DOI
[12] Lanckriet, G. R., Cristianini, N., Bartlett, P., Ghaoui, L. E., Jordan, M. I.: Learning the kernel matrix with semidefinite programming. J. Machine Learn. Res. 5 (2004), 27-72.
[13] Li, G., Pong, T. K.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25 (2015), 2434-2460. DOI
[14] Nikolova, M.: 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
[15] Paulsen, V. I., Raghupathi, M.: An Introduction to the Theory of Reproducing Kernel Hilbert Spaces. Cambridge Studies in Advanced Mathematics 152, Cambridge University Press, Cambridge 2016.
[16] Rakotomamonjy, A., Bach, F., Canu, S., Grandvalet, Y.: SimpleMKL. J. Machine Learn. Res. 9 (2008), 2491-2521.
[17] Schölkopf, B., Smola, A. J.: Learning with Kernels. Adaptive Computation and Machine Learning 4, MIT Press, Cambridge 2001.
[18] Shi, Y., Zhu, B.: 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.
[19] Slavakis, K., Bouboulis, P., Theodoridis, S.: Online learning in reproducing kernel Hilbert spaces. In: Academic Press Library in Signal Processing 1, Academic Press, Cambridge 2014, pp. 883-987.
[20] Sonnenburg, S., Rätsch, G., Schäfer, C., Schölkopf, B.: Large scale multiple kernel learning. J. Machine Learn. Res. 7 (2006), 1531-1565.
[21] Theodoridis, S.: Machine Learning: A Bayesian and Optimization Perspective. (Second edition.). Academic Press, Cambridge 2020.
[22] Vapnik, V.: The Nature of Statistical Learning Theory. (Second edition.). Springer Science and Business Media, New York 2000.
[23] Wang, H., Shao, Y., Zhou, S., Zhang, C., Xiu, N.: Support vector machine classifier via ${L}_{0/1}$ soft-margin loss. IEEE Trans. Pattern Anal. Machine Intell.44 (2022), 7253-7265. DOI
[24] Wang, L., Liu, W., Zhu, B.: ADMM for $\ell_0$ factor analysis. In: Proc. 13th IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM 2024), Corvallis 2024.
[25] Wang, L., Liu, W., Zhu, B.: $\ell_0$ factor analysis. In: Proc. 63rd IEEE Conference on Decision and Control (CDC 2024), Milan 2024, pp. 7214-7219.
[26] Wang, L., Liu, W., Zhu, B.: 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.
[27] Wang, L., Zhu, B., Liu, W.: $\ell_0$ factor analysis: A P-stationary point theory. IEEE Trans. Automat. Control 70 (2025), 6050-6063. DOI
[28] Wang, W., Carreira-Perpinán, M. A.: Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint: 1309.1541, 2013.
[29] Wang, Y., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Scientific Computing 78 (2019), 29-63. DOI
[30] Yang, L., Pong, T. K., Chen, X.: 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
[31] Zhang, Y., Zhang, N., Sun, D., Toh, K. C.: A proximal point dual Newton algorithm for solving group graphical {L}asso problems. SIAM J. Optim. 30 (2020), 2197-2220. DOI
[32] Zhou, S.: Gradient projection Newton pursuit for sparsity constrained optimization. Appl. Comput. Harmonic Anal. 61 (2022), 75-100. DOI
[33] Zhou, S., Pan, L., Xiu, N.: Newton method for $\ell_0$-regularized optimization. Numer. Algorithms (2021), 1-30.
[34] Zhou, S., Pan, L., Xiu, N., Qi, H. D.: Quadratic convergence of smoothing Newton's method for 0/1 loss optimization. SIAM J. Optim. 31 (2021), 3184-3211. DOI
[35] Zhou, S., Xiu, N., Qi, H. D.: Global and quadratic convergence of {N}ewton hard-thresholding pursuit. J. Machine Learn. Res. 22 (2021), 1-45.
Search
Partner of
