REVIEW 7 cited by
A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima
read the original abstract
Bilevel optimization has found extensive applications in modern machine learning problems such as hyperparameter optimization, neural architecture search, meta-learning, etc. While bilevel problems with a unique inner minimal point (e.g., where the inner function is strongly convex) are well understood, such a problem with multiple inner minimal points remains to be challenging and open. Existing algorithms designed for such a problem were applicable to restricted situations and do not come with a full guarantee of convergence. In this paper, we adopt a reformulation of bilevel optimization to constrained optimization, and solve the problem via a primal-dual bilevel optimization (PDBO) algorithm. PDBO not only addresses the multiple inner minima challenge, but also features fully first-order efficiency without involving second-order Hessian and Jacobian computations, as opposed to most existing gradient-based bilevel algorithms. We further characterize the convergence rate of PDBO, which serves as the first known non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima. Our experiments demonstrate desired performance of the proposed approach.
Forward citations
Cited by 7 Pith papers
-
Limiting Stationarity of Regularized Gap-Function Reformulations for Bilevel Optimization with Unbounded Multipliers
For regularized gap-function bilevel reformulations, unbounded penalty multipliers still yield C-stationarity for the KKT/MPCC reformulation, and a new two-parameter slack penalty yields M-stationarity.
-
Second-Order Bilevel Optimization with Accelerated Convergence Rates
Second-order bilevel methods achieve Õ(ε^{-1.5}) iteration complexity for second-order stationary points, faster than first-order approaches, with a lazy variant improving computational efficiency by √d.
-
Optimization under Persistent State-Dependent Bias: Gradient-based Method and Complexity Analysis
Residual Learning, a proposed bilevel gradient method, claims exact convergence under state-dependent analog-hardware bias with rate O~(kappa1*kappa2^4*sigma^2/(mu*K)).
-
Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems
Penalty-based first-order methods find ε-KKT points in bilevel minimax problems with Õ(ε^{-4}) deterministic and Õ(ε^{-9}) stochastic oracle complexity, improving prior bounds for constrained lower-level cases via Lag...
-
Hypergradient-based Bilevel Reinforcement Learning with Improved Sample Complexity
A bilevel RL algorithm using Boltzmann-policy optimality achieves Õ(ε⁻²) sample complexity for first-order stationarity, removing the outer-level PL condition but relying on a non-realizability error bound that is not proven.
-
Efficient Bilevel Optimization for Meta Label Correction in Noisy Label Learning
EBOMLC applies dynamic barrier gradient descent with one-step inner loop, mixture upper loss, and alignment-aware barrier to make meta label correction faster and more robust on noisy data, outperforming baselines on ...
-
Bilevel learning
Bilevel learning methods rely on implicit differentiation but are restricted by assumptions of unique lower-level solutions and struggle with constraints, and connections to broader bilevel optimization literature may...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.