Zeroth-order optimization with orthogonal random directions
From MaRDI portal
Abstract: We propose and analyze a randomized zeroth-order approach based on approximating the exact gradient byfinite differences computed in a set of orthogonal random directions that changes with each iteration. A number ofpreviously proposed methods are recovered as special cases including spherical smoothing, coordinate descent, as wellas discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence ratesunder different parameter choices and assumptions. In particular, we consider convex objectives, but also possiblynon-convex objectives satisfying the Polyak-{L}ojasiewicz (PL) condition. Theoretical results are complemented andillustrated by numerical experiments.
Recommendations
- Random gradient-free minimization of convex functions
- Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling
- Zeroth-order methods for noisy Hölder-gradient functions
- A zeroth order method for stochastic weakly convex optimization
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
Cites work
- A Stochastic Approximation Method
- A stochastic line search method with expected complexity analysis
- A stochastic subspace approach to gradient-free optimization in high dimensions
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- An Implicit Filtering Algorithm for Optimization of Functions with Many Local Minima
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
- Coordinate descent algorithms
- Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
- Direct search based on probabilistic descent
- Discrete gradient methods for solving variational image regularisation models
- Faster least squares approximation
- Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
- Gradient Convergence in Gradient methods with Errors
- How to generate random matrices from the classical compact groups
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 5564091 (Why is no real title available?)
- scientific article; zbMATH DE number 3449561 (Why is no real title available?)
- scientific article; zbMATH DE number 772597 (Why is no real title available?)
- Introduction to Derivative-Free Optimization
- Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
- On a Stochastic Approximation Method
- On the complexity of parallel coordinate descent
- On the convergence of block coordinate descent type methods
- On the global optimization properties of finite-difference local descent algorithms
- On the optimal order of worst case complexity of direct search
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
- Quelques propriétés des opérateurs angle-bornes et n-cycliquement monotones
- Random gradient-free minimization of convex functions
- Random optimization
- Randomized numerical linear algebra: Foundations and algorithms
- Simple statistical gradient-following algorithms for connectionist reinforcement learning
- Sketching as a tool for numerical linear algebra
- Stochastic approximation methods for constrained and unconstrained systems
- Stochastic Estimation of the Maximum of a Regression Function
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping
- Weak convergence of the sequence of successive approximations for nonexpansive mappings
Cited in
(22)- A zeroth order method for stochastic weakly convex optimization
- Zeroth-order methods for noisy Hölder-gradient functions
- Variable metric random pursuit
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
- Optimization of convex functions with random pursuit
- Randomized Hessian estimation and directional search
- Zeroth-order stochastic compositional algorithms for risk-aware learning
- Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling
- A Zeroth-Order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization
- Direct Search Based on Probabilistic Descent in Reduced Spaces
- Global solutions to nonconvex problems by evolution of Hamilton-Jacobi PDEs
- Small errors in random zeroth-order optimization are imaginary
- A derivative-free nonlinear least squares solver for nonsmooth functions
- On the global complexity of a derivative-free Levenberg-Marquardt algorithm via orthogonal spherical smoothing
- Expected decrease for derivative-free algorithms using random subspaces
- Stochastic zeroth order descent with structured directions
- A derivative-free regularized primal-dual interior-point algorithm for constrained nonlinear least squares problems
- Fully adaptive zeroth-order method for minimizing functions with compressible gradients
- A regularized variance-reduced modified extragradient method for stochastic hierarchical games
- Zeroth-order random subspace algorithm for non-smooth convex optimization
- Quasi-Newton method with subspace gradients
- Title not available (Why is no real title available?)
This page was built for publication: Zeroth-order optimization with orthogonal random directions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038668)
