An Introduction to Bi-level Optimization - Foundations and Applications in Signal Processing and Machine Learning

Aug 4, 2026

Upload by Patrick

Bi-level optimization (BLO) uses a two-level hierarchical structure in which solving the upper-level objective requires solving a lower-level problem. BLO is widely used to model nested objective functions in signal processing and machine learning, with applications spanning wireless resource allocation and adversarial machine learning. The document surveys tractable BLO concepts including optimality conditions, standard solution algorithms with practical implementation principles, and how these ideas support state-of-the-art results across key SP and ML tasks. It also reviews recent advances in BLO theory, application implications, and current limitations motivating future research.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages46

Reading Time1 h 56 min

AccessFree to download

Introduction

Bi-level optimization definition and formulation

Connections to Stackelberg games and early applications

Motivating application: Coreset selection for model training

BLO formulation for coreset selection

arXiv :2308 .00788v2 [ cs .LG] 3 Aug 2023 An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning Yihua Zhang 1 , Prashant Khanduri2 , Ioannis Tsaknakis3 , Yuguang Yao 1 , Mingyi Hong3 , Sijia Liu 1 ,4 1 CSE, Michigan State University, USA, 2 CS, Wayne State University, USA, 3ECE, University of Minnesota, USA, 4MIT-IBM Watson AI Lab, USA Abstract Recently, bi-level optimization (BLO) has taken center stage in some very exciting developments in the area of signal processing (SP) and machine learning (ML) . Roughly speaking, BLO is a classical optimization problem that involves two levels of hierarchy (i.e., upper and lower levels), wherein obtaining the solution to the upper-level problem requires solving the lower-level one. BLO has become popular largely because it is powerful in modeling problems in SP and ML, among others, that involve optimizing nested objective functions. Prominent applications of BLO range from resource allocation for wireless systems to adversarial machine learning. In this work, we focus on a class of tractable BLO problems that often appear in SPand ML applications. We provide an overview of some basic concepts of this class of BLO problems, such as their optimality conditions, standard algorithms (including their optimization principles and practical implementations), as well as how they can be leveraged to obtain stateof-the-art results for a number of key SP and ML applications. Further, we discuss some recent advances in BLO theory, its implications for applications, and point out some limitations of the state-of-the-art that require significant future research efforts. Overall, we hope that this article can serve to accelerate the adoption of BLO as a generic tool to model, analyze, and innovate on a wide array of emerging SP and ML applications. Index Terms Bi-level optimization (BLO), convex/non-convex optimization, signal processing (SP), machine learning (ML), resource allocation, wireless communications, adversarial robustness, generalization, datamodel efficiency, I. INTRODUCTION Bi-level optimization (BLO) is a class of optimization problems involving two nested levels (upper and lower-level), where the objective and variables of the upper-level problem depend on the optimizer of the lower-level one. The canonical formulation of BLO is given by: Upper-level optimization over θ ~~ ~~}|~~ ~~ z { minimize θ∈U f (θ , ϕ∗ (θ)), subject to ϕ∗ (θ) ∈ arg min g(θ , ϕ), h (θ ,ϕ)≤0 |~~ ~~ ~~ ~~}{z (BLO) Lower-level optimization over ϕ where we assume that f , g and h are bivariate smooth functions, θ ∈ Rm denotes the upper-level variable subject to the upper-level constraint set U , ϕ ∈ Rn is the lower-level variable subject to the constraint h (θ , ϕ) ≤ 0 that couples both θ and ϕ, and ϕ∗(θ) is one lower-level optimal solution. It is evident that the lower-level problem is an auxiliary problem since its solution supports the upper-level problem in finding a better solution. The study of BLO can be traced to that of Stackelberg games [1], where the upper (resp. lower) problem optimizes the action taken by a leader (resp. the follower) . Early works in optimization utilized BLO to solve resource allocation problems [2]–[4]; see [5] for a comprehensive survey of BLO algorithms up until mid-2000, and some more recent surveys on discrete BLO [6], BLO under uncertainty [7], and nonlinear and nonconvex aspects of BLO [8] . In recent years, BLOhas regained popularity because a subclass of BLO has been used to formulate and solve various challenging problems in signal processing (SP), machine learning (ML), and artificial intelligence (AI) . Notable applications in SP include resource management [9]–[12], signal demodulation [13]–[15], channel prediction [16]–[18], image reconstruction [19] and image denoising [20] . In addition, BLO has also been used to make ML models, especially deep neural networks (

FAQs

What is bi-level optimization (BLO) and how do the two levels interact?

BLO consists of upper and lower nested optimization levels. The upper-level problem depends on an optimizer of the lower-level problem, typically through the lower-level optimal solution ϕ*(θ).

Why has BLO become popular in signal processing and machine learning?

BLO provides a modeling framework for problems with implicit hierarchical structures and nested objectives. It enables approaches for resource management, robustness, generalization, efficiency, and scalability in SP and ML systems.

How is coreset selection for model training formulated as a BLO problem?

The task includes selecting representative data via weights w (upper-level) and validating training performance using parameters θ*(w) (validation loss). The lower-level corresponds to training by minimizing a training loss ℓtr with respect to θ under the selected weights.

Aug 4, 2026

Upload by Patrick