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

Problem Setting

The paper addresses the challenge of nonconvex bi-level optimization, formulated as:
$$\theta^\star \in \arg \min_{\theta \in \Theta} G(\theta), \quad \text{where} \quad \Theta := \arg \min_{\theta \in \mathbb{R}^d} L(\theta)$$
Here, $L$ (lower-level) and $G$ (upper-level) are nonconvex objectives. The feasible set $\Theta$ is the solution set of the lower-level problem, which is typically defined only implicitly. When $L$ is nonconvex, $\Theta$ may be nonconvex, disconnected, or possess a complex geometry, making direct projection or parametrization difficult. Furthermore, the upper-level objective $G$ may also be nonconvex.

Existing gradient-based methods often rely on strong structural assumptions, such as the strong convexity of $L$ (ensuring a unique solution) or Polyak–Łojasiewicz (PL) conditions, to simplify the geometry of $\Theta$. These assumptions exclude many modern machine learning scenarios involving overparameterized or nonsmooth landscapes. While derivative-free Consensus-Based Optimization (CBO) offers a promising alternative for global optimization in nonconvex landscapes, previous applications to bi-level problems (specifically the CB2O method by Trillos et al. [2024]) utilized a hard quantile-based consensus mapping. This mapping is discontinuous, preventing the application of standard Lipschitz-based propagation-of-chaos arguments and limiting theoretical convergence guarantees to the mean-field regime only.

Methodology: Soft Consensus-Based Bi-Level Optimization (SCB2O)

The authors propose SCB2O, a derivative-free particle method that replaces the hard thresholding of CB2O with a soft-quantile consensus mechanism.

1. Soft Quantile Selection

Instead of selecting a discrete subset of particles based on a hard cutoff of lower-level objective values, SCB2O defines a soft $\beta$-quantile $q_{\beta, \tau}^\rho$ for a particle distribution $\rho$ as the unique solution to:
$$\int_{\mathbb{R}^d} \psi\left(\frac{q - L(\theta)}{\tau}\right) d\rho(\theta) = \beta$$
where $\psi: \mathbb{R} \to (0, 1)$ is a smooth, strictly increasing selection function (e.g., a sigmoid), and $\tau > 0$ is a localization parameter. As $\tau \to 0$, this soft selection converges to the hard quantile used in CB2O.

2. Consensus Point Construction

The consensus point $m_{\alpha, \beta, \tau}^{G,L}(\rho)$ is computed by applying a Gibbs-type (Laplace) weighting to the measure weighted by the soft quantile selection:
$$m_{\alpha, \beta, \tau}^{G,L}(\rho) = \frac{\int_{\mathbb{R}^d} \theta e^{-\alpha G(\theta)} dJ_{\beta, \tau}^L[\rho](\theta)}{\int_{\mathbb{R}^d} e^{-\alpha G(\theta)} dJ_{\beta, \tau}^L[\rho](\theta)}$$
where $J_{\beta, \tau}^L[\rho](d\theta) = \eta_{\rho, \tau}(\theta) d\rho(\theta)$ and $\eta_{\rho, \tau}(\theta) = \psi\left(\frac{q_{\beta, \tau}^\rho - L(\theta)}{\tau}\right)$. This two-stage process first identifies particles near the lower-level solution set (via soft quantile) and then selects favorable candidates based on the upper-level objective (via Gibbs weighting).

3. Dynamics

The method evolves a system of $N$ interacting particles $\{\Theta_t^{i,N}\}_{i=1}^N$ governed by the stochastic differential equation (SDE):
$$d\Theta_t^{i,N} = -\lambda \left( \Theta_t^{i,N} - m_{\alpha, \beta, \tau}^{G,L}(\rho_t^{N}) \right) dt + \sigma D\left( \Theta_t^{i,N} - m_{\alpha, \beta, \tau}^{G,L}(\rho_t^{N}) \right) dW_t^i$$
where $\rho_t^N$ is the empirical measure of the particles. The smoothness of the soft consensus mapping allows for the analysis of both the mean-field limit and the finite-particle system.

Key Contributions

1. Novel Algorithm (SCB2O): The paper introduces a consensus-based particle method for nonconvex bi-level optimization that does not require the lower-level solution set $\Theta$ to be convex, nor does it require $L$ or $G$ to satisfy PL conditions. It relies on a soft-quantile mechanism to handle the implicit feasible set.
2. Finite-Particle Convergence Analysis: A primary theoretical contribution is the establishment of high-probability convergence guarantees for the finite-particle system. Unlike the hard-threshold CB2O, the smoothness of the soft consensus map enables the derivation of:
   • Mean-field convergence: The mean-field law reaches an arbitrary prescribed Wasserstein neighborhood of the target solution with an explicit exponential rate.
   • Finite-particle approximation: A localized high-probability bound is established, showing that the particle estimator converges to the mean-field solution. This is achieved by combining moment-dependent consensus bounds, a cutoff-event propagation-of-chaos estimate, and finite-sample concentration.
3. Theoretical Conditions: The analysis relies on mild assumptions including:
   • Hölderian error bounds for the lower-level objective (relating objective value gaps to distance from the solution set).
   • Inverse continuity conditions for the upper-level objective near lower-level minimizers.
   • Boundedness of objectives (sufficient but not necessary conditions for the proof).

Experimental Results

The authors validate the theoretical findings through numerical experiments on two settings:

1. 2D Constrained Problems: The method was tested on circular and star-shaped constraints.
   • Performance: SCB2O with sufficiently large $\xi$ (a parameter related to $\tau$ and $\alpha$) achieves constraint satisfaction and consensus distance comparable to the hard-threshold CB2O.
   • Trade-off: Smaller $\xi$ values allow for faster initial descent of the upper-level objective at the cost of looser constraint adherence, while larger $\xi$ values enforce stricter constraint satisfaction and faster particle collapse.
2. MNIST Neural Network Training: The method was applied to train a CNN with bias parameters.
   • Stability: SCB2O with $\xi \ge 100$ remains competitive with CB2O across different quantile parameters ($\beta$), demonstrating stable training loss and test accuracy.
   • Sensitivity: Small $\xi$ values (e.g., 1 or 5) degrade performance by allowing poorly performing particles to influence the consensus, confirming the theoretical connection between the soft parameter and the hard limit.

Significance and Claims

The paper claims to bridge a critical gap in the theoretical analysis of consensus-based bi-level optimization. While previous methods like CB2O demonstrated strong empirical performance, their discontinuous consensus mappings prevented rigorous finite-particle convergence analysis. By introducing a smooth consensus rule, the authors:

• Enable the use of standard Lipschitz-based propagation-of-chaos and numerical stability arguments.
• Provide the first quantitative convergence guarantees for the finite-particle system in nonconvex bi-level settings without convexity assumptions.
• Demonstrate that the smooth approximation (SCB2O) recovers the performance of the hard-threshold method (CB2O) as the smoothing parameter vanishes, while offering a theoretically tractable framework.

The authors remain modest regarding the scope, noting that the boundedness assumptions on objectives are sufficient but not necessary, and that future work could extend these results to parameterized lower-level solution sets and broader classes of overparameterized models.