A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization
Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, Jia Liu · 2026
Read A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization by Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, Jia Liu (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-09094.txt.
Introduction
Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, and Jia Liu extend a two-level form of machine learning to many tasks at once. In such problems an outer choice shapes an inner training problem. Their 2026 paper relaxes a strong shape assumption that limited older work, then rewrites the multi-task problem as a second problem with several goals tied by an equality rule.
Because that second problem had not been studied before, the authors first define what counts as a good stopping point for it. They then give a method based on a weighted penalty and prove it reaches that point at a stated rate, in both fixed and random settings. Changing a preference setting lets the method trace out trade-offs among the goals.
Catalog record
| CREATOR | Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, Jia Liu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 140 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.09094
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, Jia Liu Abstract In recent years, bilevel optimization (BLO) has attracted significant attention for its broad applications in machine learning. However, most existing works on BLO remain confined to the single-task setting and rely on the lower-level strong convexity assumption, which significantly restricts their applicability to modern machine learning problems of growing complexity. In this paper, we make the first attempt to extend BLO to the multi-task setting under a relaxed lower-level general convexity (LLGC) assumption. To this end, we reformulate the multi-task bilevel learning (MTBL) problem with LLGC into an equality constrained multi-objective optimization (ECMO) problem. However, ECMO itself is a new problem that has not yet been studied in the literature. To address this gap, we first establish a new Karush–Kuhn–Tucker (KKT)-based Pareto stationarity as the convergence criterion for ECMO algorithm design. Based on this foundation, we propose a weighted Chebyshev (WC)-penalty algorithm that achieves a finite-time convergence rate of 𝒪 ( S T − 1 2 ) \mathcal{O}(ST^{-\frac{1}{2}}) to KKT-based Pareto stationarity in both deterministic and stochastic settings, where S S denotes the number of objectives, and T T is the total iterations. Moreover, by varying the preference vector over the S S -dimensional simplex, our WC-penalty method systematically explores the Pareto front. Finally, solutions to the ECMO problem translate directly into solutions for the original MTBL problem, thereby closing the loop between these two foundational optimization frameworks. 1 Introduction 1) Background and Motivation: As machine learning frameworks have grown increasingly complex in recent years, the demand for addressing learning problems with nested structures has become ever more compelling. Such demands typically arise from two distinct perspectives: 1) multiple, potentially conflicting tasks often need to be considered, and 2) the learning of some tasks often depend on the outcome(s) of other tasks. For instance, when aligning pre-trained large language models (LLMs) with human feedback, one needs to consider various human-aligned criteria on the one hand; on the other hand, many tasks (e.g., policy parameter optimization of LLM alignments and the actor-critic framework in reinforcement learning) often contain a subtask on reward model learning. As a result, recent years have seen growing interests in the Multi-Task Bilevel Learning (MTBL) problems in the following form: ( 74 ; 24 ; 36 ; 66 ; 70 ; 73 ; 76 ) : \displaystyle\min_{x,y}F(x,y)=\big[f_{1}(x,y),\dotsc,f_{S}(x,y)\big]^{\top} (MTBL) \displaystyle\text{s.t. }y\in\mathcal{M}(x):=\arg\min_{y}g(x,y), where S denotes the number of tasks, and x\in\mathbb{R}^{p},y\in\mathbb{R}^{q} . For example, in the aforementioned LLM alignment, the upper-level (UL) problem corresponds to minimizing the validation loss with respect to multiple human-aligned metrics, such as helpfulness and toxicity , while the lower-level (LL) problem corresponds to a data weighting task, aiming to curate a high-quality training dataset. Despite its significance, solving the MTBL problem is highly challenging due to the complex couplings between upper and lower levels and the trade-offs among multiple objectives. So far, most existing works on bilevel optimization (BLO) in the literature rely on the lower-level strong convexity (LLSC) assumption (see, e.g., ( 22 ; 3 ; 30 ; 13 ) ). Specifically, this widely adopted LLSC assumption requires that, for any given x , g(x,\cdot) is strongly convex with respect to y . It is worth noting that the LLSC assumption renders a much simplified and tractable BLO algorithm design and analysis, since the LLSC assumption i) ensures the existence of a unique solution y^{*}(x) of the LL problem, and ii) implies a well-defined hyper-gradient \nabla F(x,y^{*}(x)) that requires non-singular Hessian \nabla_{y}^{2}g(x,y^{*}(x)) ( 22 ; 30 ) . However, the LLSC assumption significantly restricts the applicability of BLO to modern machine learning problems of growing complexity. While several recent works in the BLO literature have attempted to relax the LLSC assumption to the lower-level general convexity (LLGC) assumption (i.e., the LL function g(x,\cdot) is convex but may not be strongly convex with respect to y for any x ) ( 58 ; 42 ; 7 ; 31 ; 72 ; 10 ; 45 ) , all existing works remain confined to the single-task setting, while the multi-task bilevel optimization problem under the LLGC assumption has yet to be explored. A key challenge in solving MTBL problems under the LLGC assumption stems from the fact that, not only does the hyper-gradients of the MTBL problem become ill-defined due to the lack of LLSC condition, the optimality of the UL subproblem also needs to be re-interpreted in the Pareto equilibrium sense due to the trade-off among multiple tasks. This renders most of the algorithmic techniques developed for single-task LLGC-BLO problems inapplicable. The widening gap between the rapidly growing demand for addressing more general MTBL problems and the inherent limitations of existing BLO techniques motivates us, in this work, to investigate MTBL under the LLGC assumption. 2) Overview of Our Proposed Approach: To address the ill-defined hyper-gradient challenge in the MTBL problem under the LLGC assumption, our key idea is to indirectly solve the MTBL problem by transforming this problem into an equivalent single-level constrained multi-objective optimization that shares the same optimal solutions as the original problem. To this end, we note that solving the lower-level problem in MTBL with g(x,y) being convex for any x is equivalent to solving its first-order stationarity condition \nabla_{y}g(x,y)=0 , which is both necessary and sufficient. This implies that we can reformulate the LLGC-MTBL problem as an equality constrained multi-objective (ECMO) problem as follows (also see Step 1 in Fig. 1 ): \displaystyle\min_{z\in\mathbb{R}^{k}}F(z)=\big[f_{1}(z),\dotsc,f_{S}(z)\big]^{\top} (ECMO) \displaystyle\text{s.t. }h_{i}(z)=0,i=1,\dotsc,q, where k:=p+q , z:=[x^{\top},y^{\top}]^{\top} and h_{i}(z):=\nabla_{y_{i}}g(x,y)=0 . However, even after the ECMO reformulation, we remain far from resolving the MTBL problem, as the ECMO problem itself constitutes a new formulation that has not yet been examined in the literature. Specifically, while multi-objective optimization (MOO) problems have been extensively studied (see, e.g., ( 59 ; 16 ; 14 ; 60 ; 50 ; 19 ) ), the majority of existing works only considered unconstrained MOO. Meanwhile, constrained MOO problems, including ECMO, are still in their infancy. To date, although several heuristic algorithms have been proposed for ECMO and empirically validated ( 57 ; 71 ; 12 ; 20 ) , none of these existing works offers theoretical performance guarantees in terms of finite-time convergence rate or sample/iteration complexity. To establish the theoretical foundation for solving ECMO (and thus for the LLGC-MTBL problem), there are two main technical challenges: (1) Lack of Pareto Optimality Condition Characterizations and Appropriate Convergence Metrics: Unlike unconstrained MOO problems, where the Pareto stationarity can be conveniently employed as the necessary condition of the Pareto optimality for algorithm design, the characterization of Pareto stationarity for ECMO remains unclear. Consequently, the current literature lacks appropriate convergence metrics for solving the ECMO problem; (2) Algorithm Design and Theoretical Analysis: Even with the Pareto stationarity characterization and convergence metrics established for ECMO, developing algorithms that can handle the equality constraints in ECMO and enable convergence analysis remains challenging. We address these challenges with the following contributions: Figure 1 : Roadmap of our proposed approach for solving the MTBL problem under the LLGC assumption. • To rigorously characterize the Pareto stationarity for ECMO problems, we leverage the