A Projection-Free Method for Solving Convex Bilevel Optimization Problems

2023/11/16 by Khanh-Hung Giang-Tran, Giang-Tran, Khanh-Hung, Nam Ho-Nguyen +3 · 7 citations
Computer Science · Decision Sciences · Mathematics · #90C06 #90C25 #90C30 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2311.09738

openalex publication_date 2023/11/16 · openalex created_date 2023/11/18 · openalex updated_date 2026/07/28

Abstract

When faced with multiple minima of an "inner-level" convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary "outer-level" convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free method for convex bilevel optimization which require only a linear optimization oracle over the base domain. We establish O(t^-1/2) convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to O(t^-1) and O(t^-2/3) for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.

Cited by

• Extragradient methods with complexity guarantees for hierarchical variational inequalities
• Strategic Decision-Making Under Uncertainty through Bi-Level Game Theory and Distributionally Robust Optimization
• Binno: A 1st-order method for Bi-level Nonconvex Nonsmooth Optimization for Matrix Factorizations
• Approximation and exact penalization in simple bilevel variational problems
• Convergence, Duality and Well-Posedness in Convex Bilevel Optimization
• On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
• On the Convergence Rates of Iterative Regularization Algorithms for Composite Bi-Level Optimization

Related

• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
• Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems
• A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem
• A simple algorithm for the simple bilevel programming (SBP) problem
• Near-Optimal Convex Simple Bilevel Optimization with a Bisection Method