REVIEW 26 cited by
Approximation Methods for Bilevel Programming
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
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.
Forward citations
Cited by 26 Pith papers
-
DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity
DUET achieves O(1/T^{1-5p-11/4 τ}) iteration complexity for approximate KKT-stationary points in decentralized bilevel optimization without lower-level strong convexity, using gradient tracking for data heterogeneity.
-
On Second-Order Methods for Bilevel Optimization
A deterministic single-loop cubic regularized Newton method for NCSC bilevel optimization that attains the optimal O(ε^{-1.5}) SOSP rate without repeated lower-level solves.
-
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.
-
Distribution-Aware Robust Bilevel Optimization: Quantile-Guided Huber Updates in Two-Timescale Stochastic Approximation
RQ-TTSA achieves O(T^{-(p-1)/(3p-2)}) convergence for nonconvex-strongly convex bilevel optimization under heavy-tailed noise (p in (1,2]) via quantile-guided Huber clipping and shows empirical gains on vision, games,...
-
Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization
Formalizes Root-Finding Bilevel Optimization (RF-BO) and introduces a Jacobian-free TTSA algorithm that structurally avoids variance amplification, with convergence guarantees and reported gains over squared-residual ...
-
Pseudospectral Bounds for Transient Amplification in Coupled Gradient Descent
Pseudospectral bounds are proven for the Kreiss constant of block-triangular coupled Jacobians with symmetric diagonal blocks, yielding an O(K(J)^2 log(1/δ)) iteration complexity for stochastic coupled descent.
-
S$^3$LDBO: A Snapshot Single-Loop Algorithm for Decentralized Bilevel Optimization
S³LDBO is a snapshot single-loop algorithm for decentralized bilevel optimization that reduces computational cost via intermittent derivative skipping and provides ergodic and high-probability nonergodic iteration com...
-
Detectability in Diversity: Improved Canary Crafting for Privacy Auditing in One Run
New canary crafting via greedy influence-based init and bilevel optimization for diversity in embedding space yields stronger one-run privacy leakage estimates at lower cost.
-
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 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.
-
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.
-
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.