Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
arXiv:2005.09261
Abstract
In this paper, we design and analyze a new family of adaptive subgradient methods for solving an important class of weakly convex (possibly nonsmooth) stochastic optimization problems. Adaptive methods that use exponential moving averages of past gradients to update search directions and learning rates have recently attracted a lot of attention for solving optimization problems that arise in machine learning. Nevertheless, their convergence analysis almost exclusively requires smoothness and/or convexity of the objective function. In contrast, we establish non-asymptotic rates of convergence of first and zeroth-order adaptive methods and their proximal variants for a reasonably broad class of nonsmooth \& nonconvex optimization problems. Experimental results indicate how the proposed algorithms empirically outperform stochastic gradient descent and its zeroth-order variant for solving such optimization problems.
References in corpus (11)
- ADADELTA: An Adaptive Learning Rate Method
- Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
- ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
- On the Convergence of Adam and Beyond
- AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
- On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
- On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
- ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization