Continuous-Time Analysis for Minimax and Bilevel Problems

Hyunwoo Lee, Jeongyeol Kwon, Dohyun Kwon · 2026

Read Continuous-Time Analysis for Minimax and Bilevel Problems by Hyunwoo Lee, Jeongyeol Kwon, Dohyun Kwon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-20898.txt.

Introduction

Hyunwoo Lee, Jeongyeol Kwon, and Dohyun Kwon study continuous-time analysis for minimax and bilevel problems via single-loop gradient-flow dynamics. In nested optimization, the outer variable shifts while auxiliary variables follow the inner solution map. While existing analyses usually rely on problem-specific Lyapunov constructions, the authors propose the first single Lyapunov template for continuous-time analysis. That template covers minimax, single via a raised penalty formulation, and min-min-max, with a modular proof from reusable lemmas.

Catalog record

CREATORHyunwoo Lee, Jeongyeol Kwon, Dohyun Kwon
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133962
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.20898

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Continuous-Time Analysis for Minimax and Bilevel Problems Hyunwoo Lee, Jeongyeol Kwon, Dohyun Kwon Abstract We study single-loop gradient-flow dynamics for nested optimization, where the outer variable evolves while auxiliary variables track the inner solution map. While existing analyses typically rely on problem- and condition-specific Lyapunov constructions, we propose, to our knowledge, the first unified Lyapunov template for continuous-time analysis that covers minimax, bilevel via a lifted penalty formulation, and min–min–max. Our proof is modular, built from reusable lemmas that yield a unified characterization of time-scale separation. This characterization bridges regimes from strong convexity/concavity to mere convexity through an error-bound condition, and produces explicit closed-form thresholds that avoid the coupled ratio conditions common in discrete-time analyses. We further compare the penalty dynamics with the ideal hyper-gradient flow, derive a finite-time tracking bound, and discuss an Euler one-step analogue; hypercleaning diagnostics show that the predicted relative time-scale regions remain visible under stable forward-Euler discretization. 1 Introduction Modern large-scale machine learning increasingly relies on nested optimization as a core design principle. Canonical examples include hyperparameter optimization, meta-learning, [ 20 , 7 , 21 , 9 , 22 ] , adversarial robustness [ 11 ] , game theory [ 24 ] and reinforcement learning [ 15 , 26 ] . In this work, we focus on the continuous-time dynamics of bilevel optimization [ 5 ] , which arise in many important applications with inherently hierarchical two-level optimization structures, formally described as the following: \min_{x\in X}\quad F(x)\ :=\ f\bigl(x,y^{*}(x)\bigr)\quad\text{ s.t. }\quad y^{*}(x)\ \in\ \arg\min_{y\in Y}\ g(x,y), ( P2 ) where f,g:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R} are continuously differentiable. The minimax is obtained by setting g(x,y)\ :=\ -f(x,y). ( P1 ) Then y^{*}(x)\in\arg\max_{y\in Y}f(x,y) , and hence F(x)=\max_{y\in Y}f(x,y). If g(x,\cdot) is strongly convex for every x\in X , then the inner minimizer y^{*}(x) is unique and hence well-defined for all x in P2 . Evaluating \nabla F(x) requires repeatedly solving the inner problem and often involves computing an implicit hyper-gradient involving second-order information. A widely used alternative is the single-loop principle [ 16 , 17 ] : evolve the outer variable while auxiliary variables track the inner optimizer on-the-fly. In continuous time, this leads naturally to coupled gradient flows [ 25 , 23 ] with explicit time-scale parameters controlling how fast the inner dynamics track their instantaneous targets relative to the x -dynamics. Recent work has started to clarify stability and convergence of such coupled dynamics via Lyapunov and time-scale separation viewpoints [ 2 , 13 , 6 , 19 ] . However, prior analyses are largely formulation-specific and discrete-time, leading to bespoke Lyapunov/absorption arguments and intertwined step-size ratio conditions whose implied time-scale thresholds are often algebraically intricate. As a result, prior case-by-case analyses often obscure the reusable structure and the role of penalty-induced terms in the time-scale absorption step. In contrast, our continuous-time normal form separates deviation-to-residual conversion from time-scale absorption, yielding closed-form threshold conditions and clarifying how the lifted penalty affects the absorption mechanism. Our main focus is bilevel optimization, but the standard penalty surrogate has an inherently saddle-type structure. Let g^{*}(x):=\min_{z}g(x,z) and define \mathcal{L}_{\lambda}(x,y)=f(x,y)+\lambda\bigl(g(x,y)-g^{*}(x)\bigr),\ \mathcal{L}_{\lambda}^{*}(x)=\min_{y}\mathcal{L}_{\lambda}(x,y). To avoid evaluating g^{*}(x) explicitly, we introduce a tracker z and lift the penalty as E_{\lambda}(x,y,z):=f(x,y)+\lambda\bigl(g(x,y)-g(x,z)\bigr), so that \min_{z}g(x,z)=g^{*}(x) is recovered by minimizing over z . This yields the lifted min–min–max formulation \min_{x}\min_{y}\max_{z}\;E_{\lambda}(x,y,z) , which places bilevel penalty dynamics in the same structural family as minimax and makes the tracking mechanism explicit. It also cleanly exposes how penalty-induced stiffness enters the Lyapunov absorption step and how the corresponding threshold conditions should be interpreted. Appendix K studies the genuine min–min–max problem \min_{x}\min_{y}\max_{z}\;E(x,y,z), ( P3 ) where E(x,y,z):=f(x,y)-g(x,z) , and no penalty parameter is involved. This serves as a calibration case: the same Lyapunov template and time-scale absorption rule apply verbatim, yielding thresholds that are intrinsic to the saddle-type coupling. Problem \Phi(x) H_{y} H_{z} Minimax F F-f 0 Bilevel \mathcal{L}_{\lambda}^{*} \mathcal{L}_{\lambda}-\mathcal{L}_{\lambda}^{*} g-g^{*} Min-min-max \mathcal{L} f-f^{*} g-g^{*} Table 1: Instantiation of the unified Lyapunov blueprint. Here F=\max_{y}f(x,y) , f=f(x,y) , g=g(x,z) , and f^{*},g^{*} denote inner optima. We develop a unified continuous-time analysis for minimax, bilevel, and min–min–max problems. All three are handled by the same value-level Lyapunov template W:=\Phi(x)+\alpha H_{y}(\cdot)+\beta H_{z}(\cdot), where \Phi is the target outer value and H_{y},H_{z}\geq 0 measure tracking gaps. Differentiating W yields outer descent plus tracking-induced cross terms. Our proof separates their control into two reusable modules: a deviation-to-residual conversion, supplied by strong convexity/concavity or an error-bound interface, and a closed-form time-scale absorption rule. Thus, once (\Phi,H_{y},H_{z}) are instantiated, the required thresholds follow from the same normal form. While unified analyses for nested optimization exist [ 3 , 27 ] , and Lyapunov analyses are known for coupled saddle dynamics [ 8 , 4 ] , we are not aware of a value-function-level continuous-time blueprint that yields plug-in time-scale thresholds across minimax envelopes and lifted-penalty bilevel dynamics. The same modular view clarifies weaker inner geometry. Under strong convexity/concavity, the conversion constant scales like 1/\mu ; under a local EB/PL/QG-type condition, it is replaced by an error-bound constant \kappa . Consequently, the thresholds deteriorate through the same C^{2} dependence, making explicit how the required time-scale separation changes when strong convexity is relaxed. This geometry–threshold relation is often less explicit inside algorithm-specific step-size conditions in discrete-time two-time-scale analyses [ 2 , 13 ] . We further corroborate this geometric interpretation on Wine and Digits hypercleaning tasks, a standard bilevel benchmark [ 9 , 22 ] . Under stable forward-Euler discretization, reducing the lower-level regularization weakens the empirical inner curvature, increases the deviation-to-residual conversion constant, and shifts the predicted thresholds upward. The phase diagrams show the same above-threshold region as the favorable time-scale regime. This supports our central message: the EB interface exposes how weaker inner geometry changes the conversion constant and shifts the time-scale thresholds, a relationship that is often hidden inside algorithm-specific step-size conditions in discrete-time two-timescale analyses [ 13 ] . This connects EB/PL/QG-type regularity [ 18 ] directly to the Lyapunov absorption thresholds. Finally, we compare the penalty-based three-variable dynamics with the ideal bilevel gradient flow \dot{w}=-\nabla F(w) and establish a finite-time trajectory tracking bound. Our result controls \sup_{t\in[0,T]}\|x(t)-w(t)\| and cleanly separates (i) the approximation bias induced by the penalty parameter \lambda from (ii) the residual tracking errors governed by the time-scale separations \delta>\delta_{0}(\lambda) and \eta>\eta_{0} . This provides an explicit quantitative link between single-loop tracking dynamics and the hyper-gradient flow they approximate. Related Work Minimax and bilevel optimization have largely separate literatures: minimax work often studies saddle-point/game dynamics, while bilevel methods typically use implicit differentiation, unrolling, or single-loop approximations [ 4 , 10 , 28 , 12 , 14 ] . Across these settings, the two-time-scale principle provides a common viewpoint from stochastic approximation and dynamical systems [ 1 , 8 , 4 ] . Existing discrete-time analyses often encode stability through algorithm-specific step-size conditions; our contribution is to isolate a value-function-level continuous-time Lyapunov template that yields plug-in thresholds and makes their dependence on inner geometry explicit. 2 Preliminaries We state several assumptions on P1 and P2 to specify the problem class of interest. In both settings, the outer objective has the composite form F(x)=f(x,y^{*}(x)) defined through an inner optimizer y^{*}(x) . We focus on well-conditioned regimes where y^{*}(x) is uniquely defined and sufficiently regular, so

Read the complete text