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
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 to comment.