Abstract
We present a parallel sequential Monte Carlo (PSMC) methodology for solving complex optimization problems where the cost function is a sum of many individual components. The proposed Parallel Sequential Monte Carlo Optimizer (PSMCO) is a stochastic zeroth-order algorithm that requires only function evaluations, making it suitable for black-box systems. By employing a bank of parallel samplers that generate particle approximations of probability measures, the algorithm identifies global minima by treating them as the global maxima of associated density functions. We provide analytical proofs for almost sure convergence and explicit convergence rates. Numerical experiments demonstrate that PSMCO effectively navigates cost functions with multiple minima and broad "flat" regions that typically cause gradient-based methods to fail.
Introduction
In fields ranging from machine learning to signal processing, the standard approach to optimization is Stochastic Gradient Descent (SGD). However, SGD faces significant hurdles in real-world applications: it requires computable gradients, often gets trapped in local minima in non-convex landscapes, and stalls in "flat" regions where gradients vanish.
To address these limitations, we introduce PSMCO, a gradient-free framework that transforms the optimization task into a Bayesian inference problem. By maintaining a population of candidate solutions (particles) and evolving them through a sequence of probability measures, PSMCO can explore search spaces more robustly than point-based gradient methods.
The PSMCO Framework
Optimization as Sampling
The core principle of PSMCO is the duality between optimization and sampling. We define a sequence of probability density functions $\pi_n(\theta) \propto \exp(-\gamma_n f(\theta))$, where $f(\theta)$ is the cost function and $\gamma_n$ is an increasing sequence of "inverse temperature" parameters. As $n$ increases, the distribution concentrates its mass on the global minima of $f(\theta)$.
Parallel Sampler Architecture
PSMCO utilizes $M$ independent parallel workers. Each worker processes different random shuffles of data mini-batches, ensuring diverse exploration of the parameter space. This parallelism serves two purposes: it accelerates computation and prevents the algorithm from prematurely converging to a single local optimum.
Jittering and Selection
To maintain particle diversity and explore the landscape, we employ a "jittering kernel." A critical innovation in our approach is the inclusion of a "delta" component in the kernel, which allows a portion of the particles to remain unchanged. This "doing nothing" strategy ensures that once a high-quality solution is found, it is not lost to random perturbation.
At each stage, the algorithm uses the marginal likelihood—a statistical measure of how well a sampler's particles represent the target distribution—to identify the best-performing worker. This acts as a global selection mechanism to focus the search on the most promising regions of the search space.
Theoretical Guarantees
Unlike many heuristic global optimizers, PSMCO is backed by rigorous convergence analysis. We prove that the estimator converges to a global minimum almost surely. Furthermore, we establish an explicit convergence rate of approximately $O(N^{-1/2d})$, where $N$ is the number of particles and $d$ is the dimensionality of the search space. This provides a theoretical benchmark for the algorithm's performance relative to the complexity of the problem.
Empirical Evaluation
1. Multi-modal Landscapes
Using a 2D Gaussian Mixture model with four distinct global minima, we tested PSMCO's ability to maintain diversity. The algorithm successfully populated all four minima simultaneously, demonstrating its superiority over methods that collapse to a single mode.
2. Navigating Flat Regions (Sigmoid Regression)
In a sigmoid regression task with 100,000 data points, the cost function contains vast plateaus where gradients are nearly zero. While Parallel SGD failed to move from its initialization in these regions, PSMCO’s stochastic nature allowed it to explore the plateau and successfully locate the global minimum.
3. Non-smooth Non-convex Optimization
We evaluated the algorithm on high-dimensional ($d=10, 30$) problems using the Smoothly Clipped Absolute Deviation (SCAD) penalty. This penalty is notoriously difficult due to its non-differentiability and non-convexity. PSMCO achieved significantly lower Normalized Mean Square Error (NMSE) compared to Stochastic Evolution Strategies (SES) and other particle-based filters.
Discussion and Future Work
While PSMCO provides a robust alternative to gradient-based methods, it is subject to the "curse of dimensionality." As $d$ increases, the number of particles required for convergence grows, which may become computationally expensive for extremely high-dimensional models like deep neural networks.
Future research will focus on "interacting" parallel versions where workers share information more frequently (particle islands) and hybrid approaches that incorporate gradient information—when available—into the jittering step to combine global exploration with local refinement efficiency.
Summary updated