Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
From MaRDI portal
Abstract: We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for -dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and non-smooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple () evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.
Cited in
(80)- Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises
- On the convergence rate issues of general Markov search for global minimum
- An accelerated directional derivative method for smooth stochastic convex optimization
- A stochastic subspace approach to gradient-free optimization in high dimensions
- A zeroth order method for stochastic weakly convex optimization
- A new one-point residual-feedback oracle for black-box learning and control
- Model-free linear quadratic regulator
- Distributed online bandit optimization under random quantization
- Noisy zeroth-order optimization for non-smooth saddle point problems
- One-point gradient-free methods for smooth and non-smooth saddle-point problems
- Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Zeroth-order algorithms for stochastic distributed nonconvex optimization
- Gradient-free distributed optimization with exact convergence
- On the upper bound for the expectation of the norm of a vector uniformly distributed on the sphere and the phenomenon of concentration of uniform measure on the sphere
- Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case
- Decentralized online convex optimization based on signs of relative states
- Personalized optimization with user's feedback
- Improved complexities for stochastic conditional gradient methods under interpolation-like conditions
- Zeroth-order feedback optimization for cooperative multi-agent systems
- Exact optimization: Part I
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
- Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem
- Derivative-free methods for policy optimization: guarantees for linear quadratic systems
- Bandit convex optimization in non-stationary environments
- New first-order algorithms for stochastic variational inequalities
- scientific article; zbMATH DE number 7625189 (Why is no real title available?)
- Finite Difference Gradient Approximation: To Randomize or Not?
- Zeroth-order stochastic compositional algorithms for risk-aware learning
- An accelerated method for derivative-free smooth stochastic convex optimization
- Black-box reductions for zeroth-order gradient algorithms to achieve lower query complexity
- Derivative-free optimization methods
- Distributed subgradient-free stochastic optimization algorithm for nonsmooth convex functions over time-varying networks
- Full-low evaluation methods for derivative-free optimization
- Worst case complexity of direct search under convexity
- Zeroth-order optimization with orthogonal random directions
- Gradient-free federated learning methods with l₁ and l₂-randomization for non-smooth convex stochastic optimization problems
- Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact
- Non-smooth setting of stochastic decentralized convex optimization problem over time-varying graphs
- A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization
- A gradient‐free distributed optimization method for convex sum of nonconvex cost functions
- Direct Search Based on Probabilistic Descent in Reduced Spaces
- Distributed Nash equilibrium learning: A second‐order proximal algorithm
- Optimistic optimisation of composite objective with exponentiated update
- Federated learning for minimizing nonsmooth convex loss functions
- Re-thinking high-dimensional mathematical statistics. Abstracts from the workshop held May 15--21, 2022
- Adaptive sampling quasi-Newton methods for zeroth-order stochastic optimization
- Online distributed dual averaging algorithm for multi-agent bandit optimization over time-varying general directed networks
- Unifying framework for accelerated randomized methods in convex optimization
- Adaptive Catalyst for Smooth Convex Optimization
- Distributed zeroth-order optimization: convergence rates that match centralized counterpart
- Small errors in random zeroth-order optimization are imaginary
- Stochastic adversarial noise in the ``black box optimization problem
- Accelerated zero-order SGD method for solving the black box optimization problem under ``overparametrization condition
- Convergence guarantees for forward gradient descent in the linear regression model
- Expected decrease for derivative-free algorithms using random subspaces
- Stochastic zeroth order descent with structured directions
- Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
- Hierarchical dynamic graphical games for optimal leader-follower consensus control
- Derivative-free stochastic bilevel optimization for inverse problems
- A line search framework with restarting for noisy optimization problems
- A stochastic quasi-Newton method in the absence of common random numbers
- One-point residual feedback algorithms for distributed online convex and non-convex optimization
- Convergence rate of payoff-based generalized Nash equilibrium learning
- Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles
- One-point feedback for composite optimization with applications to distributed and federated learning
- Derivative-free optimization with transformed objective functions and the algorithm based on the least Frobenius norm updating quadratic model
- Countering the communication bottleneck in federated learning: a highly efficient zero-order optimization technique
- On quasi-convex smooth optimization problems by a comparison oracle
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime
- Convergence analysis for a nonlocal gradient descent method via directional Gaussian smoothing
- Zeroth-order random subspace algorithm for non-smooth convex optimization
- Almost sure convergence of randomised-difference descent algorithm for stochastic convex optimisation
- Online boosting with bandit feedback
- Algorithm 1053: SOLNP+: a derivative-free solver for constrained nonlinear optimization
- Zeroth-order feedback-based optimization for distributed energy management
- One-point residual feedback gradient tracking algorithm for distributed online optimization with gradient noises
- Gradient is all you need? How consensus-based optimization can be interpreted as a stochastic relaxation of gradient descent
- The Nesterov-Spokoiny acceleration achieves strict o(1/k^2) convergence
- Globally convergent derivative-free methods in nonconvex optimization with and without noise
This page was built for publication: Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978646)
