Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization

DOI10.1007/S11222-020-09964-4zbMATH Open1452.62025arXiv1811.09469OpenAlexW3045675320MaRDI QIDQ2209727FDOQ2209727

Joaquín Míguez, Dan Crisan, Ömer Deniz Akyildiz

Publication date: 4 November 2020

Published in: Statistics and Computing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1811.09469

zbMATH Keywords

samplingsequential Monte Carlononconvex optimizationstochastic optimizationgradient-free optimization

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Monte Carlo methods (65C05) Parallel numerical computation (65Y05) Nonconvex programming, global optimization (90C26)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sequential Monte Carlo Samplers
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Optimization by Simulated Annealing
• PRMLT
• A Stochastic Approximation Method
• On parallel implementation of sequential Monte Carlo methods: the island particle model
• Random gradient-free minimization of convex functions
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Introduction to Derivative-Free Optimization
• On Accelerated Random Search
• A Survey of Some Model-Based Methods for Global Optimization
• Noisy Monte Carlo: convergence of Markov chains with approximate transition kernels
• Particle-kernel estimation of the filter density in state-space models
• Stochastic global optimization as a filtering problem
• On the convergence of two sequential Monte Carlo methods for maximum a posteriori sequence estimation and stochastic global optimization
• Particle Filtering Framework for a Class of Randomized Optimization Algorithms
• Maslov Idempotent Probability Calculus, I
• Nested particle filters for online parameter estimation in discrete-time state-space Markov models
• Optimization Methods for Large-Scale Machine Learning
• Analysis of a sequential Monte Carlo method for optimization in dynamical systems
• Sequential Monte Carlo simulated annealing
• Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
• The landscape of empirical risk for nonconvex losses
• Adapting the Number of Particles in Sequential Monte Carlo Methods Through an Online Scheme for Convergence Assessment
• Nudging the particle filter

Cited In (1)

• Parallel Nonstationary Direct Policy Search for Risk-Averse Stochastic Optimization

Uses Software

• KernSmooth
• AdaGrad
• Adam
• PRMLT

This page was built for publication: Parallel sequential Monte Carlo for stochastic gradient-free nonconvex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2209727)