ProxiCBO: A Provably Convergent Consensus-Based Method for Composite Optimization

This paper introduces ProxiCBO, a provably convergent interacting-particle method that combines consensus-based optimization with proximal gradient techniques to effectively solve non-convex composite optimization problems in signal processing, outperforming existing methods in accuracy and particle efficiency.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy, and incredibly complex mountain range. This isn't just any mountain range; it's a "composite" one. It has two distinct features:

1. The Terrain (The Smooth Part): The ground slopes up and down in complex, winding ways (this is the differentiable part of the math). It might have many small valleys that look like the bottom but aren't.
2. The Rules (The Bumpy Part): There are invisible fences, walls, or specific zones you must stay in or avoid (this is the non-differentiable part, like a "do not enter" zone or a "must be positive" rule).

Your goal is to find the absolute deepest valley (the Global Minimum) that respects all the rules.

The Problem with Old Methods

Traditionally, people used two main ways to solve this:

1. The "Hiker" (Proximal Gradient): Imagine a single hiker who looks at the slope right under their feet and takes a step downhill.
   • The Flaw: If the hiker starts in a small, shallow dip (a local minimum), they will think they've reached the bottom and stop. They get stuck. To fix this, you have to send out thousands of hikers from different random starting points, hoping one gets lucky. This is slow and inefficient.
2. The "Swarm" (Consensus-Based Optimization - CBO): Imagine a flock of birds flying over the mountains. They don't look at the ground; they look at where the other birds are. They have a "collective brain" that points toward the area where the most birds are currently finding low ground.
   • The Flaw: While great at exploring, the birds ignore the specific "Rules" (the fences). They might fly straight into a "do not enter" zone or miss the specific shape of the valley because they are just following the crowd.

The New Solution: ProxiCBO

The paper introduces ProxiCBO, a new method that combines the best of both worlds. Think of it as a Super-Swarm of Smart Hikers.

Here is how it works, using a simple analogy:

1. The Team (The Particles)

Instead of one hiker, you have a team of 1,000 explorers (particles) scattered across the mountain.

2. The "Crowd Wisdom" (Consensus)

Every few minutes, the team stops and asks: "Where is the lowest point anyone has found so far?"
They calculate a "Consensus Point"—a weighted average that leans heavily toward the explorers who found the deepest spots. The whole team then drifts slightly toward this "best known spot." This prevents them from getting stuck in tiny, shallow dips.

3. The "Rule Keeper" (The Proximal Step)

This is the magic ingredient. Before the team takes their next step, they consult a Rule Book.

• If a hiker is about to step into a forbidden zone (violating the constraints), the Rule Book instantly snaps them back to the nearest legal spot.
• If the hiker is on a slope, the Rule Book helps them calculate the perfect angle to slide down while respecting the fences.

In the paper's language, this is called the Proximal Operator. It's like a magical force field that corrects the team's path instantly to ensure they never break the rules, while still moving them toward the bottom.

4. The "Foggy Exploration" (Noise)

Sometimes, the team gets too confident and starts circling the same spot. To prevent this, the team is given a little bit of "random jitter" (noise). It's like a gentle wind that pushes them slightly off course, forcing them to explore new areas of the mountain they might have missed.

Why is this a Big Deal?

The authors prove mathematically that this method is guaranteed to find the global bottom eventually, even in very tricky, non-smooth landscapes.

• Efficiency: In their tests (like reconstructing images from very blurry, one-bit data or tracking objects with single-photon lasers), ProxiCBO found the best answer using 10 times fewer explorers than the old methods.
• Robustness: It doesn't matter if you start the team in a bad spot; the combination of "crowd wisdom" and "rule checking" pulls them out of traps and guides them to the true solution.

The Real-World Impact

The paper tested this on two real-world signal processing problems:

1. One-Bit Quantization: Imagine trying to reconstruct a photo where you only know if each pixel is "bright" or "dark" (1 bit of info). It's a nightmare for computers. ProxiCBO solved it better than anyone else.
2. Single-Photon Lidar: Imagine a radar that detects only a single photon bouncing off an object to measure its distance. It's incredibly noisy. ProxiCBO figured out the object's speed and position more accurately than existing methods.

In short: ProxiCBO is a smarter, more efficient way to find the "best" solution in a complex, rule-bound world. It uses a team of explorers who listen to each other, check the rulebook constantly, and aren't afraid to take a random step to find the hidden treasure.

Technical Summary

1. Problem Statement

The paper addresses composite optimization problems of the form:
$$\min_{v \in \mathbb{R}^d} \{ E(v) := f(v) + g(v) \}$$
where:

• $f(v)$ is differentiable but potentially non-convex (e.g., data fidelity terms in signal processing with non-linear observation models).
• $g(v)$ is convex but potentially non-differentiable (e.g., regularization terms like $\ell_1$-norm for sparsity, Total Variation for images, or indicator functions for constraints).

Context: These problems are ubiquitous in signal processing (e.g., one-bit quantization, single-photon lidar).
Challenges:

• Standard Proximal Gradient (PG) methods are sensitive to initialization, prone to getting trapped in local minima for non-convex $f$, and lack global convergence guarantees.
• Existing Consensus-Based Optimization (CBO) methods handle non-convexity well but do not explicitly exploit the composite structure ($f+g$), often treating the problem as a black box, which can lead to lower particle efficiency.

2. Methodology: ProxiCBO

The authors propose ProxiCBO, an interacting-particle method that integrates the global exploration capabilities of CBO with the structural efficiency of proximal gradient descent.

A. Continuous-Time Dynamics

The method models the evolution of $N$ particles $\{V_t^i\}_{i=1}^N$ via a system of Stochastic Differential Equations (SDEs):
$$dV_t^i = \underbrace{-\lambda_1 (V_t^i - v_\alpha(\hat{\rho}_t^N)) dt}_{\text{Consensus Drift } (T_1)} - \underbrace{\lambda_2 (\nabla f(V_t^i) + \nabla M_\mu g(V_t^i - \mu \nabla f(V_t^i))) dt}_{\text{Proximal Drift } (T_2)} + \text{Diffusion Terms}$$

• Consensus Term ($T_1$): Drives particles toward a weighted consensus point $v_\alpha$, which approximates the global minimizer based on the current particle distribution (Laplace principle).
• Proximal Drift ($T_2$): Incorporates first-order information. It uses the gradient of the Moreau envelope of $g$, denoted $\nabla M_\mu g$. This term effectively performs a proximal gradient step within the continuous dynamics, guiding particles along the composite landscape.
• Diffusion Terms ($T_3, T_4$): Add stochastic noise (anisotropic diffusion) to facilitate exploration and escape local minima.

B. Practical Implementation (Discrete Algorithm)

To handle constraints (where $g$ is an indicator function) and ensure particles remain within feasible sets, the authors propose an alternating update scheme rather than a naive Euler-Maruyama discretization:

1. Consensus & Exploration Step: Update particles using the consensus drift and diffusion terms (ignoring the proximal drift for this sub-step).
2. Proximal Step: Apply the proximal operator explicitly:
   $$V_t^i \leftarrow \text{prox}_{\mu g} \left( V_t^i - \mu \nabla f(V_t^i) \right)$$
   This ensures that constraints imposed by $g$ are strictly satisfied at every iteration.

3. Key Contributions

1. Algorithmic Innovation:

   • Development of ProxiCBO, the first CBO variant specifically tailored for composite objectives ($f+g$). It uniquely combines consensus-based global search with proximal gradient local refinement.

2. Theoretical Guarantees:

   • Global Convergence: The paper establishes rigorous global convergence guarantees for the continuous-time finite-particle system.
   • Convergence Rate: It proves that the empirical measure of the particles converges to the Dirac measure at the global minimizer $v^*$ within a finite time $T^*$.
   • Explicit Constants: The analysis explicitly characterizes the dependence of convergence constants on the problem dimension $d$ and the initial distribution, refining previous proofs (e.g., [16], [19]).
   • Well-posedness: Proves the existence and uniqueness of strong solutions for the proposed SDE system.

3. Numerical Superiority:

   • Demonstrates that ProxiCBO outperforms both standard Proximal Gradient methods (which get stuck in local minima) and vanilla CBO methods (which are less particle-efficient) in terms of accuracy and particle-efficiency.

4. Theoretical Analysis Highlights

The proof of convergence (Theorem 3.1) relies on a two-step argument:

1. Mean-Field Approximation: Bounding the Wasserstein-2 distance between the finite-particle system and its mean-field limit (infinite particle system). The authors show this error scales as $O(N^{-1})$.
2. Mean-Field Convergence: Proving that the mean-field distribution converges exponentially to the global minimizer under specific assumptions (local coercivity, Lipschitz continuity, and a "well-defined valley" around the minimizer).

Key Assumptions:

• $f$ is differentiable with Lipschitz gradient.
• $g$ is convex.
• The objective $E$ satisfies growth conditions and has a unique global minimizer $v^*$.
• The initial distribution has sufficient mass near $v^*$.

5. Numerical Results

The authors benchmark ProxiCBO against Proximal Gradient (PG), Accelerated PG (APG), and existing CBO variants on two signal processing tasks:

1. One-Bit Signal Quantization:

   • Task: Recovering sparse signals from non-monotonic, non-convex one-bit measurements.
   • Result: ProxiCBO with 1,000 particles achieved higher success rates and Signal-to-Noise Ratio (SNR) than PG/APG and vanilla CBO using 10,000 particles. This highlights superior particle-efficiency.

2. Single-Photon Lidar (SPL) Parameter Estimation:

   • Task: Estimating reflectivity, distance, and velocity from photon counting data (modeled by a non-convex Poisson log-likelihood).
   • Result: ProxiCBO achieved the Cramér-Rao Lower Bound (CRB) (the theoretical limit for unbiased estimators) with sufficient particles, whereas other methods failed to reach this accuracy or required significantly more computational resources.

6. Significance

• Bridging the Gap: ProxiCBO successfully bridges the gap between the robustness of stochastic global optimization (CBO) and the structural efficiency of deterministic proximal methods.
• Handling Non-Convexity: It provides a theoretically grounded solution for non-convex composite problems where traditional gradient methods fail due to local minima.
• Practical Impact: The method is particularly valuable for high-dimensional signal processing tasks (like imaging and radar) where the objective function is complex, non-convex, and involves non-smooth regularization, offering a way to find high-quality solutions without exhaustive grid searches or perfect initialization.

In summary, ProxiCBO represents a significant advancement in optimization theory and practice, offering a provably convergent, particle-based framework that leverages the specific structure of composite objectives to solve challenging non-convex signal processing problems more efficiently than existing state-of-the-art methods.