Convergence of Consensus-Based Particle Methods for Nonconvex Bi-Level Optimization

Yutong Chao, Xudong Sun, Konstantin Riedl, Majid Khadiv, Jalal Etesami · 2026

Read Convergence of Consensus-Based Particle Methods for Nonconvex Bi-Level Optimization by Yutong Chao, Xudong Sun, Konstantin Riedl, Majid Khadiv, Jalal Etesami (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-19667.txt.

Introduction

Chao, Sun, Riedl, Khadiv and Etesami study consensus based tuning for nonconvex bi level problems. Here an upper level function is minimised over the minimisers of a lower level problem. Their derivative free method builds its consensus point from smooth quantile selection plus a Gibbs type Laplace approximation. Convergence guarantees cover both mean field dynamics and finite particle approximations. The mean field law reaches any prescribed Wasserstein neighbourhood of the target at an explicit exponential rate. Tests on a constrained problem and neural network training support the theory.

Catalog record

CREATORYutong Chao, Xudong Sun, Konstantin Riedl, Majid Khadiv, Jalal Etesami
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159398
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Convergence of Consensus-Based Particle Methods for Nonconvex Bi-Level Optimization Yutong Chao, Xudong Sun, Konstantin Riedl, Majid Khadiv, Jalal Etesami Abstract In this paper, we study a consensus-based optimization method for nonconvex bi-level optimization, where the objective is to minimize an upper-level function over the set of global minimizers of a lower-level problem. The proposed approach is derivative-free, and constructs its consensus point via smooth quantile selection combined with a Gibbs-type Laplace approximation. We establish convergence guarantees for both the associated mean-field dynamics and its finite-particle approximation. In particular, under suitable assumptions on smooth quantile localization, error bounds, and stability, we show that the mean-field law reaches any arbitrary prescribed Wasserstein neighborhood of the target bi-level solution with an explicit exponential rate up to the hitting time. Numerical experiments on a two-dimensional constrained problem and neural network training further support the theoretical results. 1 Introduction Bi-level optimization provides a natural framework for hierarchical decision-making problems in which an upper-level objective is optimized subject to the solution of a lower-level optimization problem. It has become a central tool in modern machine learning, with applications in meta-learning Franceschi et al. 2018 ; Kim and Hospedales 2025 , hyperparameter optimization MacKay et al. 2019 , neural architecture search Xue et al. 2021 , reinforcement learning Gammelli et al. 2023b ; Gammelli et al. 2023a , adversarial robustness Zhang et al. 2022 , model pruning Zhang et al. 2022 , etc. In this paper, we study the bi-level optimization problem \displaystyle\theta^{\star}\in\arg\min_{\theta\in\Theta}G(\theta),\qquad\Theta:=\arg\min_{\theta\in\mathbb{R}^{d}}L(\theta), (1) where L,G:\mathbb{R}^{d}\to\mathbb{R} are the nonconvex lower- and upper-level objectives, respectively. This formulation captures situations in which many candidates may solve the lower-level task equally well, while the upper-level objective selects among them according to an additional criterion, such as robustness, sparsity or generalization Petrulionyte et al. 2024 ; Zhang et al. 2024 . Despite its simple form, this problem is challenging when the objectives are nonconvex. The feasible set of the upper-level problem is the solution set \Theta of the lower-level problem, which is typically defined only implicitly. Consequently, it is generally difficult to project onto it, parametrize it, or optimize over it directly Trillos et al. 2024 . This difficulty becomes more pronounced when the lower-level objective L is nonconvex, since \Theta may be nonconvex, disconnected, or have a complicated geometry. At the same time, the upper-level objective G may also be nonconvex, as is common in modern machine learning and engineering applications Fornasier et al. 2021 ; Bae et al. 2022 . Therefore, the problem considered in this paper is not merely a constrained optimization problem with a nonconvex feasible set; rather, both the lower-level landscape defining the feasible set and the upper-level landscape used for selection may be nonconvex. Most existing convergence analyses for bi-level optimization that are gradient-based impose structural conditions that simplify this geometry. A standard assumption is that the lower-level objective is strongly convex, which guarantees the uniqueness of the lower-level solution and enables implicit differentiation Shen et al. 2023 ; Liang et al. 2023 ; Cao et al. 2024 . Other approaches replace strong convexity with convexity, error-bound conditions, or Polyak–Lojasiewicz (PL)-type conditions Xiao et al. 2023 ; Huang 2024 . While these assumptions lead to tractable algorithms with convergence guarantees, they exclude many problems in which \Theta is a nonconvex set. In particular, such assumptions impose a regular global geometry that is not appropriate for many overparameterized or nonsmooth optimization landscapes Du et al. 2019 ; Cooper 2021 ; Islamov et al. 2024 . This motivates the development of methods that can handle nonconvex L and G . Consensus-based optimization (CBO) offers a derivative-free alternative for global optimization in nonconvex landscapes Totzeck 2021 . Instead of following gradients, CBO evolves a system of interacting particles that explore the space and communicate through a consensus mechanism. Such methods have been studied at the level of mean-field dynamics Fornasier et al. 2022 and finite-particle approximations Beddrich et al. 2024 . A key theoretical breakthrough was provided by Fornasier et al. 2024 , which shows that CBO can converge globally for a broad class of nonconvex and nonsmooth objective functions in the mean-field and discrete particle regime. Their derivative-free nature makes them particularly appealing for bi-level problems in which both objectives may be nonconvex. Recently, CBO has been adopted to solve bi-level problems of the form ( 1 ) Trillos et al. 2024 . However, the method proposed therein, called CB 2 O, relies on a hard quantile-based consensus mapping that is discontinuous (Section 2.2 ). As a consequence, convergence guarantees beyond the mean-field approximation are generally not available. In this work, we instead introduce a soft-quantile consensus-based particle method (Section 2.2 ) that maintains strong performance (Section 4 ). Given a particle distribution \rho , we define a soft lower-level quantile via a smooth selection function (Equation ( 6 )). The consensus point is then obtained by applying a Gibbs-type (Laplace) weighting to this measure with respect to the upper-level objective. This construction preserves the two-stage structure of the bi-level problem: the soft-quantile selection identifies particles close to the lower-level solution set, while the Gibbs weighting promotes favorable upper-level candidates. At the same time, the smooth selection mechanism provides sufficient regularity to analyze both the mean-field dynamics and the finite-particle interacting system. Our main contributions are as follows. • We propose a consensus-based particle method, called SCB 2 O, for nonconvex bi-level optimization problems. Unlike many existing convergence analyses for bi-level optimization, our framework does not require the lower-level solution set \Theta to be convex, nor does it require either the lower-level or the upper-level objective to be convex or to satisfy a PL condition. Instead, the method relies on a soft-quantile mechanism to identify particles near the lower-level solution set and a weighting to select favorable upper-level candidates. • We provide a quantitative convergence analysis for the finite-particle dynamics (Section 3 ). In particular, we establish a localized high-probability finite-particle approximation bound for the particle estimator, obtained by combining moment-dependent consensus bounds, a cutoff-event propagation-of-chaos estimate, and finite-sample concentration. This extends existing mean-field convergence results for CBO-based bi-level optimization. 1.1 Related Work Bi-level optimization. A large body of work has studied convergence guarantees for bi-level optimization under various curvature and smoothness assumptions. Most existing analyses impose strong structural conditions on the lower-level problem to simplify the geometry of the lower-level solution set Shen et al. 2023 ; Liang et al. 2023 ; Cao et al. 2024 . Consequently, such settings do not fully capture bi-level problems whose lower-level solution set \Theta is nonconvex, disconnected, or geometrically complex. Several recent works have attempted to relax these requirements. One line of work weakens the global PL condition to a local PL condition near the lower-level solution Masiha et al. 2025 . Under suitable regularity assumptions, this allows \Theta to be characterized as a \mathcal{C}^{2} embedded submanifold of the ambient space \mathbb{R}^{d} without boundary. However, the resulting convergence guarantees typically characterize convergence toward an invariant distribution and do not directly quantify the distance between the algorithmic output and the true bi-level solution. Another line of work reformulates the bi-level problem as a single-level unconstrained problem by combining the lower-level and upper-level objectives through an adaptive penalty or weighting parameter

Read the complete text