A First Order Method for Solving Convex Bi-Level Optimization Problems

2017/02/13 by Shoham Sabach, Sabach, Shoham, Shimrit Shtern +1 · 30 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1702.03999

arxiv created 2017/02/13 · openalex publication_date 2017/02/13 · arxiv updated 2017/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we study convex bi-level optimization problems for which the inner level consists of minimization of the sum of smooth and nonsmooth functions. The outer level aims at minimizing a smooth and strongly convex function over the optimal solutions set of the inner problem. We analyze a first order method which is based on an existing fixed-point algorithm. Global sublinear rate of convergence of the method is established in terms of the inner objective function values.

Cited by

• Stabilizing Deep Reconstruction Operators with Contractive Anchoring
• Asymptotic behaviour of coupled random dynamical systems with multiscale aspects
• Extragradient methods with complexity guarantees for hierarchical variational inequalities
• Regularization methods for solving hierarchical variational inequalities with complexity guarantees
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications
• Learning to Evolve for Optimization via Stability-Inducing Neural Unrolling
• Quantitative results on a generalized viscosity approximation method
• Theoretical and numerical comparison of seven single-level reformulations for bilevel programs
• H-invariance theory: A complete characterization of minimax optimal fixed-point algorithms
• On the Rate of Convergence of Iterative Methods for Nonexpansive Mappings in CAT(0) Spaces and Hyperbolic Optimization
• Binno: A 1st-order method for Bi-level Nonconvex Nonsmooth Optimization for Matrix Factorizations
• Approximation and exact penalization in simple bilevel variational problems
• Finite-Time Bounds for Average-Reward Fitted Q-Iteration
• A Surrogate Value Function Formulation for Bilevel Optimization
• Cautious Weight Decay
• On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming
• Convergence, Duality and Well-Posedness in Convex Bilevel Optimization
• Tikhonov regularized exterior penalty methods for hierarchical variational inequalities
• Viscosity Stabilized Plug-and-Play Reconstruction
• On the Complexity of Finding Stationary Points in Nonconvex Simple Bilevel Optimization
• HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
• Faster Fixed-Point Methods for Multichain MDPs
• BLUR: A Bi-Level Optimization Approach for LLM Unlearning
• Pushing the Complexity Boundaries of Fixed-Point Equations: Adaptation to Contraction and Controlled Expansion
• On the Convergence Rates of Iterative Regularization Algorithms for Composite Bi-Level Optimization
• Direct Prediction Set Minimization via Bilevel Conformal Classifier Training
• Conditional Gradient Methods with Standard LMO for Stochastic Simple Bilevel Optimization
• Accelerating Diagonal Methods for Bilevel Optimization: Unified Convergence via Continuous-Time Dynamics
• Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis
• Convergence analysis of the Halpern iteration with adaptive anchoring parameters
• On iteratively regularized first-order methods for simple bilevel optimization

Related

• Convex Bi-Level Optimization Problems with Non-smooth Outer Objective Function
• Dynamic FISTA for Convex Composite Bi-Level Optimization
• A Value-Function-based Interior-point Method for Non-convex Bi-level Optimization
• Methodology and first-order algorithms for solving nonsmooth and non-strongly convex bilevel optimization problems
• Optimization with First Order Algorithms