An accelerated directional derivative method for smooth stochastic convex optimization
From MaRDI portal
Publication:2029381
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.
Recommendations
- An accelerated method for derivative-free smooth stochastic convex optimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated stochastic algorithms for convex-concave saddle-point problems
- A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization
- A stochastic Nesterov's smoothing accelerated method for general nonsmooth constrained stochastic composite convex optimization
- Smoothing accelerated proximal gradient method with fast convergence rate for nonsmooth convex optimization beyond differentiability
- scientific article; zbMATH DE number 6719722
- Accelerated stochastic variance reduction for a class of convex optimization problems
- Smoothing accelerated algorithm for constrained nonsmooth convex optimization problems
- Smoothed Variable Sample-Size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
Cites work
- A quasi-variational inequality problem in superconductivity
- A simple automatic derivative evaluation program
- A unified framework for stochastic 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
- About the Power Law of the PageRank Vector Component Distribution. Part 1. Numerical Methods for Finding the PageRank Vector
- Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Accelerated, parallel, and proximal coordinate descent
- An analytical study on peeling of an adhesively bonded joint based on a viscoelastic Bernoulli-Euler beam model
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- An optimal method for stochastic composite optimization
- Coderivative Analysis of Quasi‐variational Inequalities with Applications to Stability and Optimization
- Derivative-free optimization methods
- Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
- Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization
- Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Efficiency of the accelerated coordinate descent method on structured optimization problems
- Fast primal-dual gradient method for strongly convex minimization problems with linear constraints
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- Gradient methods for problems with inexact model of the objective
- 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 3891110 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 951780 (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.
- Katyusha: the first direct acceleration of stochastic gradient methods
- Lakes and rivers in the landscape: a quasi-variational inequality approach
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Mirror descent and convex optimization problems with non-smooth inequality constraints
- Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
- Random gradient-free minimization of convex functions
- Stochastic Approximation of Minima with Improved Asymptotic Speed
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- 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 gradient methods for convex optimization problems
Cited in
(16)- Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
- A stochastic subspace approach to gradient-free optimization in high dimensions
- Oracle complexity separation in convex optimization
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
- Improved exploitation of higher order smoothness in derivative-free optimization
- Accelerated directional search with non-Euclidean prox-structure
- Stochastic three points method for unconstrained smooth minimization
- An accelerated method for derivative-free smooth stochastic convex optimization
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- First-order methods for convex optimization
- Unifying framework for accelerated randomized methods in convex optimization
- Recent Theoretical Advances in Non-Convex Optimization
- Stochastic adversarial noise in the ``black box optimization problem
- One-point feedback for composite optimization with applications to distributed and federated learning
This page was built for publication: An accelerated directional derivative method for smooth stochastic convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029381)
