Newton methods improve bilevel optimization without strong convexity assumptions
Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
Machine Learning
Summary
Bilevel optimization is a way to solve problems where one task depends on another, useful in machine learning areas like tuning settings or cleaning data. Most existing methods rely on a key assumption called strong convexity in the lower problem, which limits their use. The authors propose new Newton-based methods that work even when this assumption doesn't hold, allowing for more general and challenging problems. They provide mathematical guarantees for these methods and show through experiments that they perform well in practical tasks such as cleaning data and adjusting model training.
What this means in practice
- •For machine learning engineers: Improve hyperparameter tuning and meta-learning where lower-level problem solutions are not unique or well-behaved.
- •For data science teams: Enhance data cleaning and model training by using bilevel optimization without restrictive assumptions on lower-level objectives.
Authors
Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang
Abstract
Bilevel optimization provides a framework for machine learning tasks such as hyperparameter optimization, data reweighting, and meta-learning. Existing Newton-based bilevel methods typically rely on the classical hypergradient formula, which is generally unavailable when lower-level solutions are nonunique and the lower-level Hessian is singular. We develop two Newton-based methods beyond lower-level strong convexity by exploiting curvature shared by the lower-level and multiplier updates. Newton-based GALET handles potentially singular lower-level curvature under a positive spectral-gap condition, exploiting its range structure to avoid the squared-Hessian multiplier system used in GALET. Newton-based BAMM uses a strongly convex aggregation model when the lower-level objective is convex and the upper-level objective is strongly convex in the lower-level variable. We establish convergence guarantees and improved complexity bounds relative to GALET and sl-BAMM under the corresponding assumptions. We further introduce GNBO, a generalized Newton-based framework that captures the shared-curvature structure of the proposed methods and several existing Newton and quasi-Newton bilevel methods. Experiments on synthetic problems, data hyper-cleaning, and GPT-2 data reweighting evaluate the proposed methods across different bilevel learning tasks.