An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization

Abstract

We consider smooth stochastic convex optimization problems in the context of algorithms which are based on directional derivatives of the objective function. This context can be considered as an intermediate one between derivative-free optimization and gradient-based optimization. We assume that at any given point and for any given direction, a stochastic approximation for the directional derivative of the objective function at this point and in this direction is available with some additive noise. The noise is assumed to be of an unknown nature, but bounded in the absolute value. We underline that we consider directional derivatives in any direction, as opposed to coordinate descent methods which use only derivatives in coordinate directions. For this setting, we propose a non-accelerated and an accelerated directional derivative method and provide their complexity bounds. Our non-accelerated algorithm has a complexity bound which is similar to the gradient-based algorithm, that is, without any dimension-dependent factor. Our accelerated algorithm has a complexity bound which coincides with the complexity bound of the accelerated gradient-based algorithm up to a factor of square root of the problem dimension. We extend these results to strongly convex problems.

arXiv admin note: text overlap with arXiv:1802.09022

References in corpus (10)

• Derivative-free optimization methods
• An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
• Decentralize and Randomize: Faster Algorithm for Wasserstein Barycenters
• Gradient-Free Methods for Saddle-Point Problem
• An Accelerated Method for Derivative-Free Smooth Stochastic Convex Optimization
• Adaptive Sampling Quasi-Newton Methods for Derivative-Free Stochastic Optimization
• Optimal Decentralized Distributed Algorithms for Stochastic Convex Optimization
• An Accelerated DFO Algorithm for Finite-sum Convex Functions
• Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model
• Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise

Cited by in corpus (11)

• Universal gradient descent
• Randomized gradient-free methods in convex optimization
• Solving smooth min-min and min-max problems by mixed oracle algorithms
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Stochastic Subspace Descent
• Non-Smooth Setting of Stochastic Decentralized Convex Optimization Problem Over Time-Varying Graphs
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis
• Parallel and Distributed algorithms for ML problems
• New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback
• One-Point Feedback for Composite Optimization with Applications to Distributed and Federated Learning