Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction

Abstract

Zeroth-order (derivative-free) optimization attracts a lot of attention in machine learning, because explicit gradient calculations may be computationally expensive or infeasible. To handle large scale problems both in volume and dimension, recently asynchronous doubly stochastic zeroth-order algorithms were proposed. The convergence rate of existing asynchronous doubly stochastic zeroth order algorithms is $O(\frac{1}{\sqrt{T}})$ (also for the sequential stochastic zeroth-order optimization algorithms). In this paper, we focus on the finite sums of smooth but not necessarily convex functions, and propose an asynchronous doubly stochastic zeroth-order optimization algorithm using the accelerated technology of variance reduction (AsyDSZOVR). Rigorous theoretical analysis show that the convergence rate can be improved from $O(\frac{1}{\sqrt{T}})$ the best result of existing algorithms to $O(\frac{1}{T})$. Also our theoretical results is an improvement to the ones of the sequential stochastic zeroth-order optimization algorithms.

References in corpus (6)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
• Query Complexity of Derivative-Free Optimization
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization

Cited by in corpus (5)

• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Learning to Learn by Zeroth-Order Oracle
• Faster Gradient-Free Proximal Stochastic Methods for Nonconvex Nonsmooth Optimization