On ℓp-hyperparameter Learning via Bilevel Nonsmooth Optimization

We propose a bilevel optimization strategy for selecting the best hyperparameter value for the nonsmooth ℓp regularizer with 0<p≤ 1. The concerned bilevel optimization problem has a nonsmooth, possibly nonconvex, ℓp-regularized problem as the lower-level problem. Despite the recent popularity of nonconvex ℓp-regularizer and the usefulness of bilevel optimization for selecting hyperparameters, algorithms for such bilevel problems have not been studied because of the difficulty of ℓp-regularizer. Our contribution is the proposal of the first algorithm equipped with a theoretical guarantee for finding the best hyperparameter of ℓp-regularized supervised learning problems. Specifically, we propose a smoothing-type algorithm for the above mentioned bilevel optimization problems and provide a theoretical convergence guarantee for the algorithm. Indeed, since optimality conditions are not known for such bilevel optimization problems so far, new necessary optimality conditions, which are called the SB-KKT conditions, are derived and it is shown that a sequence generated by the proposed algorithm actually accumulates at a point satisfying the SB-KKT conditions under some mild assumptions. The proposed algorithm is simple and scalable as our numerical comparison to Bayesian optimization and grid search indicates.