An accelerated method for derivative-free smooth stochastic convex optimization

DOI10.1137/19M1259225MaRDI QIDQ5081777zbMATH OpenOpenAlexFDO

Authors Eduard Gorbunov, Pavel Dvurechensky, Alexander V. Gasnikov

Publication date 17 June 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09022

zbMATH Keywords

accelerationderivative-free optimizationsmoothnessstochastic convex optimizationzeroth-order optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Convex programming (90C25) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: We consider an unconstrained problem of minimizing a smooth convex function which is only available through noisy observations of its values, the noise consisting of two parts. Similar to stochastic optimization problems, the first part is of stochastic nature. The second part is additive noise of unknown nature, but bounded in absolute value. In the two-point feedback setting, i.e. when pairs of function values are available, we propose an accelerated derivative-free algorithm together with its complexity analysis. The complexity bound of our derivative-free algorithm is only by a factor of $sqrtn$ larger than the bound for accelerated gradient-based algorithms, where $n$ is the dimension of the decision variable. We also propose a non-accelerated derivative-free algorithm with a complexity bound similar to the stochastic-gradient-based algorithm, that is, our bound does not have any dimension-dependent factor except logarithmic. Notably, if the difference between the starting point and the solution is a sparse vector, for both our algorithms, we obtain a better complexity bound if the algorithm uses an $1$-norm proximal setup, rather than the Euclidean proximal setup, which is a standard choice for unconstrained problems

Recommendations

• An accelerated directional derivative method for smooth stochastic convex optimization
• A zeroth order method for stochastic weakly convex optimization
• Random gradient-free minimization of convex functions
• Improved exploitation of higher order smoothness in derivative-free optimization
• Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises

Cites work

• A theoretical and empirical comparison of gradient approximations in derivative-free optimization
• About the power law of the PageRank vector component distribution. II: The Buckley-Osthus model, verification of the power law for this model, and setup of real search engines
• Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
• Accelerated randomized stochastic optimization.
• Algorithms for approximate calculation of the minimum of a convex function from its values
• An accelerated directional derivative method for smooth stochastic convex optimization
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• An optimal method for stochastic composite optimization
• Compressed sensing
• Derivative-free optimization methods
• Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
• First-order methods of smooth convex optimization with inexact oracle
• Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 3388498 (Why is no real title available?)
• Introduction to Derivative-Free Optimization
• Introduction to Stochastic Search and Optimization
• Introductory lectures on convex optimization. A basic course.
• Kernel-based methods for bandit convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Linear coupling: an ultimate unification of gradient and mirror descent
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
• Online convex optimization in the bandit setting: gradient descent without a gradient
• Optimal order of accuracy of search algorithms in stochastic optimization
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
• Optimization of convex functions with random pursuit
• Parallel algorithms and probability of large deviation for stochastic convex optimization problems
• Random gradient-free minimization of convex functions
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Robust Stochastic Approximation Approach to Stochastic Programming
• Smooth minimization of non-smooth functions
• Stable signal recovery from incomplete and inaccurate measurements
• Stochastic Approximation of Minima with Improved Asymptotic Speed
• Stochastic convex optimization with bandit feedback
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• Stochastic intermediate gradient method for convex optimization problems
• Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
• Universal intermediate gradient method for convex problems with inexact oracle
• Zeroth-order methods for noisy Hölder-gradient functions

Cited in

(20)

• An accelerated directional derivative method for smooth stochastic convex optimization
• Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
• Improved exploitation of higher order smoothness in derivative-free optimization
• Accelerated stochastic variance reduction for a class of convex optimization problems
• scientific article; zbMATH DE number 6719722 (Why is no real title available?)
• Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
• Stochastic three points method for unconstrained smooth minimization
• Derivative-free optimization methods
• Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
• Accelerated gradient methods with absolute and relative noise in the gradient
• First-order methods for convex optimization
• Unifying framework for accelerated randomized methods in convex optimization
• Recent theoretical advances in decentralized distributed convex optimization
• Recent Theoretical Advances in Non-Convex Optimization
• Stochastic adversarial noise in the ``black box optimization problem
• The ``black-box optimization problem: zero-order accelerated stochastic method via kernel approximation
• Zeroth-order proximal clipped gradient method with shifts for distributed stochastic composite optimization problems with infinite variance
• One-point feedback for composite optimization with applications to distributed and federated learning
• Zero order algorithm for decentralized optimization problems
• Globally convergent derivative-free methods in nonconvex optimization with and without noise

Describes a project that uses

Uses Software

• BRENT
• LIBSVM

This page was built for publication: An accelerated method for derivative-free smooth stochastic convex optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5081777)