Bilevel hyperparameter optimization for support vector classification: theoretical analysis and a solution method
Qingna Li, Zhen Li, Alain B. Zemkoho · Mathematical Methods of Operations Research · 2022
Abstract Support vector classification (SVC) is a classical and well-performed learning method for classification problems. A regularization parameter, which significantly affects the classification performance, has to be chosen and this is usually done by the cross-validation procedure. In this paper, we reformulate the hyperparameter selection problem for support vector classification as a bilevel optimization problem in which the upper-level problem minimizes the average number of misclassified data points over all the cross-validation folds, and the lower-level problems are the $$l_1$$ l 1 -loss SVC problems, with each one for each fold in T-fold cross-validation. The resulting bilevel optimization model is then converted to a mathematical program with equilibrium constraints (MPEC). To solve this MPEC, we propose a global relaxation cross-validation algorithm (GR–CV) based on the well-know Sholtes-type global relaxation method (GRM). It is proven to converge to a C-stationary point. Moreover, we prove that the MPEC-tailored version of the Mangasarian–Fromovitz constraint qualification (MFCQ), which is a key property to guarantee the convergence of the GRM, automatically holds at each feasible point of this MPEC. Extensive numerical results verify the efficiency of the proposed approach. In particular, compared with other methods, our algorithm enjoys superior generalization performance over almost all the data sets used in this paper.
Cited by 8 works. doi:10.1007/s00186-022-00798-6 Open-access PDF
Authors
References
- The Nature of Statistical Learning Theory
- An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
- Advances in neural information processing systems 7
- The Nature of Statistical Learning Theory
- Choosing Multiple Parameters for Support Vector Machines
- Pegasos: primal estimated sub-gradient solver for SVM
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- Solving large scale linear prediction problems using stochastic gradient descent algorithms
- A dual coordinate descent method for large-scale linear SVM
- Mathematical Programs with Equilibrium Constraints