EURO 2025 Leeds
Abstract Submission

1256. A Fast Smoothing Damped Newton Method for Bilevel Hyperparameter Optimization for SVC

Invited abstract in session WD-35: Bilevel optimization and augmented Lagrangian methods, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.

Wednesday, 14:30-16:00
Room: Michael Sadler LG15

Authors (first author is the speaker)

1. Qingna Li
School of Mathematics and Statistics, Beijing Institute of Technology

Abstract

Support vector classification (SVC) is a supervised learning method for classification tasks in machine learning, where hyperparameter selection has been discussed by many researchers both theoretically and practically.
In this paper, we focus on solving the large-scale mathematical program with equilibrium constraint (MPEC) derived from the bilevel hyperparameter selection of machine learning classification model, which is to choose the best parameter $C$ in L1-SVC. It is extremely challenging to design an efficient numerical algorithm to solve such MPEC due to the large number of datasets. To tackle the challenge, we smooth the complementarity constraints in the MPEC, and analyze theoretical properties of the resulting smoothing problem, including its feasible sets, Jacobian matrix and second order sufficient condition. Then we apply a damped Newton method to solve it, in which BICG-STAB algorithm is used to solve the KKT system based on its sparse square structure. Under certain assumption, the proposed smoothing damped Newton method (SDN) enjoys a quadratic rate of convergence. Finally, extensive numerical results on the datasets from the LIBSVM library verifies the high efficiency in practice with superior generalization performance of SDN over almost all the datasets used in this paper comparing with the other two methods. Further discussions on SDN also provides verification on the second-order sufficient condition, the smoothing parameter and the convergence rate.

Keywords

Status: accepted

Back to the list of papers