Parallel sequential Monte Carlo for stochastic gradient-free nonconvex\n optimization

Ömer Deniz Akyıldız, Dan Crisan, Joaquı́n Mı́guezarXiv 2018 · DOI · arXiv

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

Abstract

We introduce and analyze a parallel sequential Monte Carlo methodology for\nthe numerical solution of optimization problems that involve the minimization\nof a cost function that consists of the sum of many individual components. The\nproposed scheme is a stochastic zeroth order optimization algorithm which\ndemands only the capability to evaluate small subsets of components of the cost\nfunction. It can be depicted as a bank of samplers that generate particle\napproximations of several sequences of probability measures. These measures are\nconstructed in such a way that they have associated probability density\nfunctions whose global maxima coincide with the global minima of the original\ncost function. The algorithm selects the best performing sampler and uses it to\napproximate a global minimum of the cost function. We prove analytically that\nthe resulting estimator converges to a global minimum of the cost function\nalmost surely and provide explicit convergence rates in terms of the number of\ngenerated Monte Carlo samples and the dimension of the search space. We show,\nby way of numerical examples, that the algorithm can tackle cost functions with\nmultiple minima or with broad "flat" regions which are hard to minimize using\ngradient-based techniques.\n
BibTeX
@misc{akyldz2018parallel,
  author = {Ömer Deniz Akyıldız and Dan Crisan and Joaquı́n Mı́guez},
  title = {{Parallel sequential Monte Carlo for stochastic gradient-free nonconvex\textbackslash\{\}n optimization}},
  year = {2018},
  eprint = {1811.09469},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.09469},
}
Figure