Newton-Based Methods for Bilevel Optimization Beyond Lower-Level Strong Convexity
Authors: Youran Dong, Junfeng Yang, Wei Yao, Jin Zhang
Organizations: School of Mathematics, Nanjing University, Nanjing, P. R. China. · School of Artificial Intelligence, Southern University of Science and Technology, Shenzhen, P. R. China. · Department of Mathematics and National Center for Applied Mathematics Shenzhen, Southern University of Science and Technology, Shenzhen, P. R. China.
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.
Figures & tables
Setting
Condition
Method
Gradient/JVP computations
Hessian-vector products
PL with positive spectral gap
—
GALET ( Xiao et al., 2023 )
O(κ6ϵ−1)
O(κ8ϵ−1log(κ/ϵ))
Newton-based GALET
O(κ4ϵ−1)
O(κ5ϵ−1log(κ/ϵ))
g(x,⋅) convex, f(x,⋅) strongly convex
xk,yk,uk bounded
sl-BAMM ( Liu et al., 2023 )
O(ϵ−11/(2−6τ))
O(ϵ−11/(2−6τ))
Newton-based BAMM
O(ϵ−4/(1−3τ))
O(ϵ−(9−3τ)/(2−6τ))
∇2fσk∗,uk bounded
sl-BAMM ( Liu et al., 2023 )
O(ϵ−7/(2−6τ))
O(ϵ−7/(2−6τ))
Newton-based BAMM
O(ϵ−3/(1−3τ))
O(ϵ−(7−3τ)/(2−6τ))
Table 1: Complexity comparison with the corresponding baselines beyond LL strong convexity. For BAMM, O(⋅) suppresses dependence on μf,Lf,1,Lf,2,Lg,1,Lg,2 .
Figure 1: GALET, GALET-Q, and Newton-based GALET on ( 12 ) with ζ=1 . Left: Rx . Right: Ry .
Figure 2: Results on ( 12 ) with ζ=1 . Left: Ru for GALET, GALET-Q, and Newton-based GALET. Right: Ru for Newton-based GALET with T2=6,11,21 .
Figure 3: GALET and Newton-based GALET on ( 12 ) with ζ=0.5,0.1 . Left: Rx . Right: Ry .
Figure 4: Newton-based BAMM and sl-BAMM on ( 13 ), with stepsizes chosen according to Case 1 of Theorem 3.2 .
Figure 5: Data hyper-cleaning with linear models. Comparison of sl-BAMM and Newton-based BAMM on MNIST (upper) and FashionMNIST (lower).
Figure 6: Data hyper-cleaning with two-layer MLPs. Comparison of GALET and Newton-based GALET on MNIST (upper) and FashionMNIST (lower).
Figure 7: Clean and corrupted data weights for ScaleBiO and Newton-based GALET, averaged over five random seeds.
Method
Clean weight
Corrupted weight
Validation loss
Test loss
Peak memory
ScaleBiO
0.928
0.072
2.603
2.555
9.984 GiB
Newton-based GALET
0.929
0.071
2.439
2.398
18.509 GiB
Table 2: GPT-2 data denoising after three training epochs, averaged over five random seeds.
Multi-objective bilevel optimization has wide applications in the AI area such as automated learning and multi-task meta-learning. Although recently some works have been begun to study the multi-objective bilevel optimization, the proposed methods rely on the (strongly) convex lower level problems. In fact, these multi-objective bilevel learning problems are generally nonconvex, and particularly their lower level problems are nonconvex. To fill this gap, we propose a class of Multi-Objective Moreau Envelope based Hessian-free Algorithms (MOMEHA) for the multi-objective bilevel learning problems with nonconvex lower level. Specifically, our method uses the Moreau envelope to relax the original problem into a multi-objective single-level optimization with an envelope constraint. In particular, our method retains computational advantages of being single-loop and Hessian-free in the multi-objective setting by incorporating a smooth weighted Tchebycheff scalarization. Furthermore, we propose a momentum-based variant of MOMEHA (i.e., MB-MOMEHA) method for the stochastic multi-objective bilevel learning problems. In theory, we provide the convergence properties of our algorithms under both deterministic and stochastic setting. Some experiments on few-shot meta-learning and neural architecture search demonstrate that our methods outperform the existing approaches in Pareto front, validating its effectiveness and robustness.
Yicong Jiang, Feihu Huang
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China · College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China; and also with MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, China
Although bilevel optimization (BLO) has emerged as a powerful framework for addressing many complex and nested machine learning problems in recent years, most existing studies are confined to the lower-level strongly convex (LLSC) or lower-level generally convex (LLGC) settings (i.e., the lower-level objective function is assumed to be, at least, convex). While the LLSC/LLGC assumptions render more tractable algorithmic design and theoretical analysis, they are too rigid to encompass many machine learning problems in practice. The limitations of LLSC/LLGC assumptions in BLO motivate us to investigate solving the BLO problem in the general lower-level nonconvex (LLNC) settings, which remains in its infancy. In the literature on LLNC-BLO, most of the existing works either require additional structures in the lower-level objective function for tractable theoretical analysis, or adopt the first-order stationarity reformulation as a lower-level surrogate problem, which is inherited from the LLSC/LLGC settings but could lose their effectiveness in the LLNC setting. To bridge this gap, we propose to reformulate the nonconvex lower-level problem using a second-order stationarity-based surrogate, the solution of which guarantees a local optimal solution at the lower level. Based on this reformulation, we propose the PROBE (Perturbed gradient algorithm for bilevel problem) and show that it overcomes the limitations of prior works by probing and escaping lower-level saddle points. We prove that PROBE achieves a finite-time convergence rate of O(T−2/5), where T denotes iterations. To our knowledge, this work is the first to establish the finite-time convergence for achieving lower-level second-order stationary solutions in general LLNC-BLO. Our experiments on both a large language model-based data curation task and a meta-learning task also show that PROBE outperforms SOTA methods.
Zhiyao Zhang, Menglu Yu, Alvaro Velasquez +2
The Ohio State University · Meta · University of Colorado Boulder +1
We study optimistic bilevel optimization when the lower-level problem has a non-isolated manifold of minimizers. In this setting, the hyper-objective may be non-differentiable because the upper-level criterion must choose among multiple lower-level solutions. Under a local Polyak--Łojasiewicz (PŁ) condition, we show that differentiability does not require the lower-level solution set to be a singleton: uniqueness of the optimistic selection is sufficient. This yields an explicit pseudoinverse-based hyper-gradient formula extending the classical singleton-minimizer result. We further characterize the regularity of the hyper-objective: non-degeneracy of the selected minimizer along the solution manifold yields local smoothness, while failure of uniqueness can create many non-differentiable points and failure of non-degeneracy can destroy all positive Hölder regularity of the hyper-gradient. Motivated by this theory, we propose HG-MS, a select-then-differentiate method combining explicit optimistic selection with efficient pseudoinverse-based hyper-gradient computation. Despite the nonconvex nature of optimistic selection over the lower-level solution manifold, we show that HG-MS converges to a stationary point of the optimistic objective with complexity governed by the intrinsic dimension of the solution manifold rather than its ambient dimension. Empirically, we test a practical variant of HG-MS for matched-budget LLM source reweighting. This variant preserves the select-then-differentiate principle and obtains the best GSM8K/MATH scores across the tested backbones, along with competitive or best MT-Bench instruction-following results.
Saeed Masiha, Zebang Shen, Negar Kiyavash +1
EPFL School of Management of Technology, Station 5, 1015 Lausanne, Switzerland · ETH Department of Computer Science, Universitätstrasse 6, 8092 Zürich, Switzerland