A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

• URL: http://arxiv.org/abs/2605.09094v2
• Date: Thu, 14 May 2026 14:59:48 GMT
• Title: A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization
• Abstract summary: We make the first attempt to extend bilevel optimization (BLO) to the multi-task setting under a relaxed general convexity assumption.<n> ECMO is a new problem that has not yet been studied in the literature.
• Score: 14.543177030471723
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $O(ST^{-\frac{1}{2})$ to KKT-based Pareto stationarity in both deterministic and stochastic settings, where $S$ denotes the number of objectives, and $T$ is the total iterations. Moreover, by varying the preference vector over the $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.

Related papers

• DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity [77.51981761667302]
  We introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET)<n>DUET eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective.<n>To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity.
  arXiv  Detail & Related papers  (2026-06-19T06:45:13Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• Advanced Quantum Annealing for the Bi-Objective Traveling Thief Problem: An $\varepsilon$-Constraint-based Approach [7.06690496634166]
  Bi-Objective Traveling Thief Problem (BI-TTP) requires the simultaneous optimization of travel cost and item profit.<n> Conventional methods for the BI-TTP often face severe scalability issues due to the complex interdependence between routing and packing decisions.<n>We propose an advanced hybrid approach that combines quantum annealing (QA) with the $varepsilon$-constraint method.
  arXiv  Detail & Related papers  (2026-03-13T05:26:25Z)
• Multi-Objective Bilevel Learning [12.198330173886587]
  We investigate the theoretical and algorithmic foundation of multi-objective bilevel learning (MOBL)<n>Our goal is to develop efficient MOBL optimization algorithms.<n>We propose a unifying algorithmic framework called weighted-Chebyshev multi-hyper-gradient-descent (WC-MHGD)
  arXiv  Detail & Related papers  (2025-11-11T04:42:14Z)
• A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
  We develop a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints. We demonstrate its effectiveness on two well-known real-world applications.
  arXiv  Detail & Related papers  (2024-06-14T15:59:36Z)
• Constrained Bi-Level Optimization: Proximal Lagrangian Value function Approach and Hessian-free Algorithm [8.479947546216131]
  We develop a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA) LV-HBA is especially well-suited for machine learning applications.
  arXiv  Detail & Related papers  (2024-01-29T13:50:56Z)
• A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.9047096855236125]
  We show that textbfOBCD offers stronger optimality than standard critical points.<n>We also demonstrate the non-erg convergence rate of textbfOBCD.
  arXiv  Detail & Related papers  (2023-04-07T13:44:59Z)
• Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization [36.743632418094]
  We present a single-loop algorithm to tackle a multiblock min-max bilevel optimization problem. We show that our algorithm can be used to tackle problems with hundreds of tasks.
  arXiv  Detail & Related papers  (2022-06-01T06:42:36Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Value-Function-based Sequential Minimization for Bi-level Optimization [52.39882976848064]
  gradient-based Bi-Level Optimization (BLO) methods have been widely applied to handle modern learning tasks. There are almost no gradient-based methods able to solve BLO in challenging scenarios, such as BLO with functional constraints and pessimistic BLO. We provide Bi-level Value-Function-based Sequential Minimization (BVFSM) to address the above issues.
  arXiv  Detail & Related papers  (2021-10-11T03:13:39Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.