Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization
This provides a stochastic gradient-free optimization method for nonconvex problems, addressing a bottleneck in handling functions that are difficult for gradient-based techniques, though it is incremental as it builds on Monte Carlo approaches.
The authors tackled the problem of minimizing cost functions that are sums of many components, especially those with multiple minima or flat regions, by introducing a parallel sequential Monte Carlo method, proving it converges almost surely to a global minimum with explicit rates in terms of samples and dimension.
We introduce and analyze a parallel sequential Monte Carlo methodology for the numerical solution of optimization problems that involve the minimization of a cost function that consists of the sum of many individual components. The proposed scheme is a stochastic zeroth order optimization algorithm which demands only the capability to evaluate small subsets of components of the cost function. It can be depicted as a bank of samplers that generate particle approximations of several sequences of probability measures. These measures are constructed in such a way that they have associated probability density functions whose global maxima coincide with the global minima of the original cost function. The algorithm selects the best performing sampler and uses it to approximate a global minimum of the cost function. We prove analytically that the resulting estimator converges to a global minimum of the cost function almost surely and provide explicit convergence rates in terms of the number of generated Monte Carlo samples and the dimension of the search space. We show, by way of numerical examples, that the algorithm can tackle cost functions with multiple minima or with broad "flat" regions which are hard to minimize using gradient-based techniques.