A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order

Abstract

Asynchronous parallel optimization received substantial successes and extensive attention recently. One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us. This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods. Our result recovers or improves existing analysis on special cases, provides more insights for understanding the asynchronous parallel behaviors, and suggests a novel asynchronous parallel zeroth order method for the first time. Our experiments provide novel applications including model blending problems using the proposed asynchronous parallel zeroth order method.

Cited by in corpus (29)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Asynchronous Decentralized Parallel Stochastic Gradient Descent
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Efficiently avoiding saddle points with zero order methods: No gradients required
• At Stability's Edge: How to Adjust Hyperparameters to Preserve Minima Selection in Asynchronous Training of Neural Networks?
• Learning to Learn by Zeroth-Order Oracle
• A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Large Batch Training Does Not Need Warmup
• SGD with Coordinate Sampling: Theory and Practice
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization
• Learning Sampling Policy for Faster Derivative Free Optimization
• CADA: Communication-Adaptive Distributed Adam
• Zeroth-Order Feedback Optimization for Cooperative Multi-Agent Systems
• Distributed stochastic optimization with large delays
• Small errors in random zeroth-order optimization are imaginary
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Towards Understanding Acceleration Tradeoff between Momentum and Asynchrony in Nonconvex Stochastic Optimization
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization
• Gradient-Free Multi-Agent Nonconvex Nonsmooth Optimization