Newton bilevel methods drop the lower-level strong-convexity assumption
Original title: Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
Experiments cover synthetic tasks, data hyper-cleaning, and GPT-2 reweighting, with claimed better complexity than GALET and sl-BAMM.
The paper proposes Newton-based GALET and Newton-based BAMM for bilevel optimization when lower-level solutions need not be unique and the Hessian may be singular. GALET relies on a positive spectral-gap condition, while BAMM uses a strongly convex aggregation model under stated convexity assumptions. The authors also introduce GNBO, a generalized Newton framework covering these and several existing methods, and report convergence and complexity bounds. Experiments include synthetic problems, data hyper-cleaning, and GPT-2 data reweighting.
Unconfirmed: Improved complexity is claimed relative to GALET and sl-BAMM only under the paper's assumptions.
- Newton-based GALET avoids the squared-Hessian multiplier system used in GALET.
- BAMM applies when the lower level is convex and the upper level is strongly convex in that variable.
- GNBO is presented as a shared-curvature framework for Newton and quasi-Newton bilevel methods.
From the original article
1 min read at arxiv.orgBilevel 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.
By Youran Dong · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.