Approximation Methods for Bilevel Programming
read the original abstract
In this paper, we study a class of bilevel programming problem where the inner objective function is strongly convex. More specifically, under some mile assumptions on the partial derivatives of both inner and outer objective functions, we present an approximation algorithm for solving this class of problem and provide its finite-time convergence analysis under different convexity assumption on the outer objective function. We also present an accelerated variant of this method which improves the rate of convergence under convexity assumption. Furthermore, we generalize our results under stochastic setting where only noisy information of both objective functions is available. To the best of our knowledge, this is the first time that such (stochastic) approximation algorithms with established iteration complexity (sample complexity) are provided for bilevel programming.
This paper has not been read by Pith yet.
Forward citations
Cited by 19 Pith papers
-
Semiparametric Efficient Bilevel Gradient Estimation
Introduces a cross-fitted orthogonal hypergradient estimator derived from the efficient influence function that achieves asymptotic normality and uniform control for bilevel gradient estimation under quadratic losses.
-
IGT-OMD: Implicit Gradient Transport for Decision-Focused Learning under Delayed Feedback
IGT-OMD reduces gradient transport error from quadratic to linear in delay length for delayed bilevel optimization and achieves sublinear regret with adaptive steps.
-
A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization
A barrier-smoothed first-order method achieves stationarity rates of tilde O(K to the -2/3) deterministic and tilde O(K to the -2/5) stochastic for linearly constrained bilevel optimization.
-
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.
-
On the Stability and Generalization of First-order Bilevel Minimax Optimization
Provides the first systematic generalization analysis via algorithmic stability for single-timescale and two-timescale stochastic gradient descent-ascent in bilevel minimax problems.
-
Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimization
Derives upper bounds on on-average argument stability for single- and two-timescale SGD in bilevel optimization under NC-NC, C-C, and SC-SC regimes, linking stability directly to generalization gaps.
-
Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization
Algorithms achieve optimal regret bounds of Ω(1+V_T) for standard bilevel local regret with O(T log T) inner gradients and Ω(T/W²) for window-averaged regret using adaptive and window-based analyses.
-
A Hessian-Free Actor-Critic Algorithm for Bi-Level Reinforcement Learning with Applications to LLM Fine-Tuning
A Hessian-free single-loop actor-critic algorithm achieves finite-time convergence to the unregularized bi-level RL optimum using attenuating entropy regularization under a special Polyak-Lojasiewicz condition.
-
Continuous-Time Analysis for Minimax and Bilevel Problems
Introduces a modular unified Lyapunov template for continuous-time analysis of minimax, bilevel (via penalty), and min-min-max problems with explicit time-scale thresholds.
-
CHAL: Council of Hierarchical Agentic Language
CHAL is a multi-agent dialectic system that performs structured belief optimization over defeasible domains using Bayesian-inspired graph representations and configurable meta-cognitive value system hyperparameters.
-
BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization
BROS achieves the same O(ε^{-2}) sample complexity as exact single-loop SBO methods while cutting peak memory by up to 44.9% through randomized subspaces and bias-corrected Hessian estimation.
-
BROS: Bias-Corrected Randomized Subspaces for Memory-Efficient Single-Loop Bilevel Optimization
BROS achieves memory-efficient single-loop stochastic bilevel optimization with O(ε^{-2}) sample complexity by performing updates in randomized subspaces and using Rademacher bi-probe correction for unbiased estimation.
-
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...
-
Interactive Inverse Reinforcement Learning of Interaction Scenarios via Bi-level Optimization
Interactive IRL is cast as bi-level optimization with an inner loop learning expert rewards and an outer loop learning interaction policies, solved by the convergent BISIRL algorithm.
-
S2MAM: Semi-supervised Meta Additive Model for Robust Estimation and Variable Selection
S2MAM is a new semi-supervised model that uses bilevel optimization to automatically identify informative variables, update similarity matrices, and provide interpretable predictions with theoretical guarantees.
-
Representation-Guided Parameter-Efficient LLM Unlearning
REGLU guides LoRA-based unlearning via representation subspaces and orthogonal regularization to outperform prior methods on forget-retain trade-off in LLM benchmarks.
-
A Distributed Bilevel Framework for the Macroscopic Optimization of Multi-Agent Systems
A distributed bilevel algorithm optimizes emergent macroscopic behavior in multi-agent systems by combining local exponential-family state estimation with hypergradient microscopic updates and proves convergence via t...
-
Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization
Introduces a novel search direction enabling sublinear stochastic bilevel regret guarantees for first- and zeroth-order online bilevel optimization algorithms without relying on window smoothing.
-
Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic Approximation
Under nested local linearity, nonlinear two-time-scale SA achieves finite-time decoupled convergence; nonlinearity in the slow update alone can destroy it.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.