Difference of convex algorithms for bilevel programs with applications in hyperparameter selection

Jane J. Ye, Xiaoming Yuan, Shangzhi Zeng, Jin Zhang

TL;DR

This paper introduces a novel framework for solving bilevel optimization problems—where one optimization problem is nested inside another—by reformulating them as "Difference of Convex" (DC) programs. The authors develop two inexact proximal algorithms that efficiently tune machine learning hyperparameters, significantly outperforming traditional equilibrium-based approaches in both speed and accuracy.

What Problem Does This Paper Address?

Bilevel programs are notoriously difficult to solve; even the simplest linear versions are NP-hard. In machine learning, these structures appear constantly in hyperparameter selection (e.g., finding the best regularization penalty for an SVM).

The standard "first-order approach" replaces the inner optimization with its optimality conditions (KKT conditions). However, this often leads to mathematical headaches because the resulting constraints are "degenerate," meaning standard optimization solvers struggle to find even a local minimum. Furthermore, many existing algorithms require all functions to be smooth, which isn't always the case in modern ML (think Hinge loss or Lasso).

The authors target a specific but powerful class: problems where the upper-level objective is a Difference of Convex (DC) function and the lower-level problem is fully convex (convex in both the upper and lower variables).

Methods

The core innovation lies in the Value Function Reformulation.

  1. The DC Transformation: Because the lower-level problem is fully convex, its "value function" (the optimal objective value as a function of the input) is also convex. This allows the authors to rewrite the entire bilevel problem as a single-level problem with a DC constraint.
  2. Relaxation: Since the original constraint is mathematically "brittle," they introduce a small relaxation parameter ($\epsilon$) to make the problem numerically stable and ensure it satisfies standard constraint qualifications.
  3. The Algorithms: They propose two new algorithms:
  4. iP-DCA (Inexact Proximal DC Algorithm): This linearizes the concave parts of the objective and constraints, adds a "proximal term" to ensure the subproblems are easy to solve (strongly convex), and uses a simplified rule to update the penalty parameters.
  5. iPL-DCA (Inexact Proximal Linearized DCA): A faster version that also linearizes the smooth convex parts, making it ideal for large-scale problems.

Crucially, these algorithms only require approximate solutions at each step, making them much faster than methods requiring exact solutions.

Datasets

The authors evaluated their approach using Support Vector Machine (SVM) classification tasks on several real-world datasets from the LIBSVM repository:

  • Small-scale: australian_scale, breast-cancer_scale, and diabetes_scale.
  • Large-scale: mushrooms (4,062 samples) and phishing (5,526 samples).
  • Additional benchmarks: liver-disorders, sonar, a1a, and w1a.

Key Insights and Ideas

  • Convexity is a Bridge: The "aha moment" is realizing that "full convexity" in the lower level is the key to unlocking DC programming tools. This covers a surprisingly large range of ML models, including SVMs and Lasso.
  • Perspective Functions: The authors show a clever trick using "perspective functions" to turn a non-convex hyperparameter tuning problem (where parameters multiply variables) into a fully convex lower-level problem.
  • No Multipliers Needed: Unlike previous DC algorithms that require calculating complex Lagrange multipliers to update penalty terms, their update rule is based on simple triggers (like the change in the iterate), making it much easier to implement.
  • Automatic Stability: They prove that for any relaxation $\epsilon > 0$, the problem automatically satisfies the necessary conditions for convergence, bypassing the "degeneracy" issues that plague other bilevel methods.

Key Results

  • Speed: In head-to-head tests against the MPEC (Mathematical Programs with Equilibrium Constraints) approach using MATLAB’s fmincon, the new iP-DCA was often 10x to 20x faster. For the diabetes dataset, iP-DCA finished in ~3 seconds, while the strict MPEC approach took over 5 minutes.
  • Accuracy: The proposed method achieved lower cross-validation errors than the MPEC approach on several datasets (e.g., breast-cancer and diabetes).
  • Scalability: The algorithms successfully handled high-dimensional hyperparameter selection on large datasets where traditional "grid search" (testing a grid of possible values) would be computationally impossible.
  • Robustness: The results showed that the choice of the relaxation parameter $\epsilon$ didn't wildly swing the accuracy, suggesting the method is stable for practical use.

Limitations and Future Work

  • Lower-Level Constraints: The current work focuses on a specific structure. The authors note that if the upper level has additional complex DC constraints, the "automatic" stability (ENNAMCQ) might no longer hold, requiring more sophisticated handling.
  • Parameter Tuning: While the penalty update is simplified, the algorithm still introduces its own hyperparameters (like the proximal step size $\rho$), which may require some initial tuning.
  • Future Directions: The authors suggest extending this framework to even more complex models in meta-learning and neural architecture search where bilevel structures are common.

Summary updated

Abstract

In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out to be convex and hence the bilevel program can be reformulated as a difference of convex bilevel program. We propose two algorithms for solving the reformulated difference of convex program and show their convergence under very mild assumptions. Finally we conduct numerical experiments to a bilevel model of support vector machine classification.
BibTeX
@inproceedings{ye2023difference,
  author = {Jane J. Ye and Xiaoming Yuan and Shangzhi Zeng and Jin Zhang},
  title = {{Difference of convex algorithms for bilevel programs with applications in hyperparameter selection}},
  booktitle = {Math. Program},
  year = {2023},
  url = {https://openreview.net/forum?id=SVCdZE2YoJD},
}

Loading related content...

Figure