Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization

Abstract

Two types of zeroth-order stochastic algorithms have recently been designed for nonconvex optimization respectively based on the first-order techniques SVRG and SARAH/SPIDER. This paper addresses several important issues that are still open in these methods. First, all existing SVRG-type zeroth-order algorithms suffer from worse function query complexities than either zeroth-order gradient descent (ZO-GD) or stochastic gradient descent (ZO-SGD). In this paper, we propose a new algorithm ZO-SVRG-Coord-Rand and develop a new analysis for an existing ZO-SVRG-Coord algorithm proposed in Liu et al. 2018b, and show that both ZO-SVRG-Coord-Rand and ZO-SVRG-Coord (under our new analysis) outperform other exiting SVRG-type zeroth-order methods as well as ZO-GD and ZO-SGD. Second, the existing SPIDER-type algorithm SPIDER-SZO (Fang et al. 2018) has superior theoretical performance, but suffers from the generation of a large number of Gaussian random variables as well as a $\sqrt{\epsilon }$-level stepsize in practice. In this paper, we develop a new algorithm ZO-SPIDER-Coord, which is free from Gaussian variable generation and allows a large constant stepsize while maintaining the same convergence rate and query complexity, and we further show that ZO-SPIDER-Coord automatically achieves a linear convergence rate as the iterate enters into a local PL region without restart and algorithmic modification.

Published in ICML 2019

Cited by in corpus (9)

• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Small errors in random zeroth-order optimization are imaginary
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization