Relax and penalize: a new bilevel approach to mixed-binary hyperparameter optimization

Nowadays, machine learning systems tend to incorporate an increasing number of hyperparameters with the purpose of improving the overall performance of learning tasks and achieving a higher flexibility. Then, optimizing such high-dimensional hyperparameters becomes a crucial step for devising efficient and fully parameter-free machine learning systems. In recent years, bilevel approaches to hyperparameter optimization have become very popular as an effective way to estimate high-dimensional hyperparameters [1, 2, 3, 6, 10, 16, 18]. On the other hand, in many circumstances binary hyperparameters are included in the model to allow the pruning of the irrelevant variables or the discovery of sparsity structures. Interesting examples are given by the pruning of large-scale deep learning models [22], the identification of the group-sparsity structures in regression problems [8, 20], and learning the discrete structure of a graph neural networks [7]. For these cases the usual optimization approach is that of relaxing the respective parameter over the unit interval [0, 1], solve the continuous optimization problem, and then rounding the solution so to get a binary output. This is essentially a heuristic, which overcomes the challenge of dealing with integer variables, but does not offer any theoretical guarantee. The aim of the present work is that of providing a more principled way of approaching mixed-binary hyperparameter optimization.