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

• URL: http://arxiv.org/abs/2605.19667v1
• Date: Tue, 19 May 2026 11:00:05 GMT
• Title: Convergence of Consensus-Based Particle Methods for Nonconvex Bi-Level Optimization
• Abstract summary: We show that the mean-field law reaches any arbitrary Wasserstein neighborhood of the target bi-level solution with an explicit exponential rate up to the hitting time.
• Score: 6.757107749537041
• License: http://creativecommons.org/licenses/by/4.0/
• 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 \textit{mean-field} dynamics and its \textit{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.

Related papers

• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm [28.40732302523826]
  Bilevel optimization is a hierarchical framework where an upper-level problem is constrained by a lower-level problem.<n>Existing bilevel optimization methods assume strong convexity or Polyak-ojasiewicz (PL) conditions for the lower-level function.<n>We show that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients.
  arXiv  Detail & Related papers  (2026-02-04T03:09:52Z)
• Towards a Unified Analysis of Neural Networks in Nonparametric Instrumental Variable Regression: Optimization and Generalization [66.08522228989634]
  We establish the first global convergence result of neural networks for two stage least squares (2SLS) approach in nonparametric instrumental variable regression (NPIV)<n>This is achieved by adopting a lifted perspective through mean-field Langevin dynamics (MFLD)
  arXiv  Detail & Related papers  (2025-11-18T17:51:17Z)
• Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
  This work provides the first finite-time convergence guarantees for linearly constrained bilevel optimization using only first-order methods.<n>We address the unprecedented challenge of simultaneously handling linear constraints, noise, and finite-time analysis in bilevel optimization.
  arXiv  Detail & Related papers  (2025-11-13T00:59:20Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [17.384717824118255]
  We focus on high-dimensional and plausible settings in which the problem admits a low-rank solution.<n>We provide several theoretical results proving that, under these circumstances, the well-known Extragradient method converges to a solution of the constrained optimization problem.
  arXiv  Detail & Related papers  (2024-02-14T10:48:00Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of emphconcave unconstrained problems.<n>Our method improves the existing line-search-based min-max optimization by shaving off an $O(loglog(1/eps)$ factor in the required number of Schur decompositions.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• 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)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Consensus-Based Optimization on the Sphere: Convergence to Global Minimizers and Machine Learning [7.998311072988401]
  We investigate the implementation of a new Kuramoto-Vicsek-type model for global optimization of non functions on the sphere. We present several numerical experiments, which show that the algorithm proposed in the present paper scales well with the dimension and is extremely versatile.
  arXiv  Detail & Related papers  (2020-01-31T18:23:26Z)

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.