Approximation Methods for Bilevel Programming

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.

Cited by in corpus (23)

• Coresets via Bilevel Optimization for Continual Learning and Streaming
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic
• Bilevel methods for image reconstruction
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Communication-Efficient Robust Federated Learning with Noisy Labels
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization
• Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee
• Pontryagin Differentiable Programming: An End-to-End Learning and Control Framework
• Provably Faster Algorithms for Bilevel Optimization
• Projection-Free Algorithm for Stochastic Bi-level Optimization
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• Pareto Efficient Fairness in Supervised Learning: From Extraction to Tracing
• Convergence Properties of Stochastic Hypergradients
• Learning from Sparse Demonstrations
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Sign-MAML: Efficient Model-Agnostic Meta-Learning by SignSGD
• Enhanced Bilevel Optimization via Bregman Distance
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Differentiable Equilibrium Computation with Decision Diagrams for Stackelberg Models of Combinatorial Congestion Games
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Stability and Generalization of Bilevel Programming in Hyperparameter Optimization
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods