Swarming for faster convergence in stochastic optimization

DOI10.1137/17M1111085MaRDI QIDQ4582016zbMATH OpenOpenAlexFDO

Authors Shi Pu, Alfredo García

Publication date 22 August 2018

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

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

zbMATH Keywords

stochastic optimizationdistributed optimizationswarming-based framework

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Stochastic programming (90C15)

Abstract: We study a distributed framework for stochastic optimization which is inspired by models of collective motion found in nature (e.g., swarming) with mild communication requirements. Specifically, we analyze a scheme in which each one of $N>1$ independent threads, implements in a distributed and unsynchronized fashion, a stochastic gradient-descent algorithm which is perturbed by a swarming potential. Assuming the overhead caused by synchronization is not negligible, we show the swarming-based approach exhibits better performance than a centralized algorithm (based upon the average of $N$ observations) in terms of (real-time) convergence speed. We also derive an error bound that is monotone decreasing in network size and connectivity. We characterize the scheme's finite-time performances for both convex and non-convex objective functions.

Recommendations

• A flocking-based approach for distributed stochastic optimization
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Distributed stochastic algorithm for global optimization in networked system
• A consensus-based model for global optimization and its mean-field limit
• Optimal convergence rates for convex distributed optimization in networks

Cites work

• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• A Model Reference Adaptive Search Method for Global Optimization
• A Stochastic Approximation Method
• A class of attractions/repulsion functions for stable swarm aggregations
• A flocking-based approach for distributed stochastic optimization
• Adaptive Penalty-Based Distributed Stochastic Convex Optimization
• Design and analysis of simulation experiments
• Distributed Subgradient Methods for Convex Optimization Over Random Networks
• Noise Reduction by Swarming in Social Foraging
• Robust Stochastic Approximation Approach to Stochastic Programming
• Stochastic Estimation of the Maximum of a Regression Function
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Swarm stability and optimization

Cited in

(12)

• Swarm-based optimization with random descent
• scientific article; zbMATH DE number 6856232 (Why is no real title available?)
• A flocking-based approach for distributed stochastic optimization
• Distributed stochastic gradient tracking methods
• A swarm-inspired projection algorithm
• Decentralized coordination of autonomous swarms using parallel Gibbs sampling
• Learning to Optimize
• Safe Metropolis-Hastings algorithm and its application to swarm control
• Erratum to: ``Swarming for faster convergence in stochastic optimization
• Fast decentralized nonconvex finite-sum optimization with recursive variance reduction
• Swarm-based gradient descent meets simulated annealing
• Swarm-based gradient descent method for non-convex optimization

Describes a project that uses

Uses Software

• Boids

This page was built for publication: Swarming for faster convergence in stochastic optimization

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