239. A highly efficient single-loop smoothing damped Newton method for large-scale bilevel hyperparameter optimization of SVC
Invited abstract in session MB-7: Hyperparameter Optimization for Classification, stream Bilevel and multilevel optimization.
Monday, 10:30-12:30Room: B100/5015
Authors (first author is the speaker)
| 1. | Yixin Wang
|
| Beijing Institute of Technology |
Abstract
Bilevel hyperparameter optimization has received growing attention thanks to the fast development of machine learning. Due to the tremendous size of data sets, the scale of bilevel hyperparameter optimization problem could be extremely large, posing great challenges in designing efficient numerical algorithms. In this paper, we focus on solving the large-scale mathematical programs with equilibrium constraints (MPEC) derived from hyperparameter selection of L1-support vector classification (L1-SVC). We propose a highly efficient single-loop smoothing damped Newton method (SDN) for solving such MPEC. Compared with most existing algorithms where subproblems are involved and solved by on-shelf packages, our approach fully takes advantage of the structure of MPEC and therefore is single-loop. Moreover, the proposed SDN enjoys a quadratic convergence rate under proper assumptions. Extensive numerical results over LIBSVM dataset show the superior performance of SDN over other state-of-art algorithms including the Scholtes global relaxation method with subproblem solved by SNOPT and the Matlab built-in function fmincon, especially in CPU time. For example, for dataset w4a, SDN is 20 times faster than SGRM and 3 times faster than fmincon. Further numerical results also verifies the quadratic convergence of SDN as well as the fulfillment of the second order sufficient condition, while guarantees that SDN returns a strict local minimizer of the smoothing problem of MPEC.
Keywords
- Non-smooth optimization
- Complexity and efficiency of algorithms
- Large-scale optimization
Status: accepted
Back to the list of papers