Second-Order Sensitivity Analysis for Bilevel Optimization
In this work we derive a second-order approach to bilevel optimization, a
type of mathematical programming in which the solution to a parameterized
optimization problem (the "lower" problem) is itself to be optimized (in the
"upper" problem) as a function of the parameters. Many existing approaches to
bilevel optimization employ first-order sensitivity analysis, based on the
implicit function theorem (IFT), for the lower problem to derive a gradient of
the lower problem solution with respect to its parameters; this IFT gradient is
then used in a first-order optimization method for the upper problem. This
paper extends this sensitivity analysis to provide second-order derivative
information of the lower problem (which we call the IFT Hessian), enabling the
usage of faster-converging second-order optimization methods at the upper
level. Our analysis shows that (i) much of the computation already used to
produce the IFT gradient can be reused for the IFT Hessian, (ii) errors bounds
derived for the IFT gradient readily apply to the IFT Hessian, (iii) computing
IFT Hessians can significantly reduce overall computation by extracting more
information from each lower level solve. We corroborate our findings and
demonstrate the broad range of applications of our method by applying it to
problem instances of least squares hyperparameter auto-tuning, multi-class SVM
auto-tuning, and inverse optimal control.