A theoretical and empirical comparison of gradient approximations in derivative-free optimization
From MaRDI portal
Publication:2143221
Abstract: In this paper, we analyze several methods for approximating gradients of noisy functions using only function values. These methods include finite differences, linear interpolation, Gaussian smoothing and smoothing on a sphere. The methods differ in the number of functions sampled, the choice of the sample points, and the way in which the gradient approximations are derived. For each method, we derive bounds on the number of samples and the sampling radius which guarantee favorable convergence properties for a line search or fixed step size descent method. To this end, we use the results in [Berahas et al., 2019] and show how each method can satisfy the sufficient conditions, possibly only with some sufficiently large probability at each iteration, as happens to be the case with Gaussian smoothing and smoothing on a sphere. Finally, we present numerical results evaluating the quality of the gradient approximations as well as their performance in conjunction with a line search derivative-free optimization algorithm.
Recommendations
- Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
- A mixed finite differences scheme for gradient approximation
- A derivative-free approximate gradient sampling algorithm for finite minimax problems
- Stochastic derivative-free optimization using a trust region framework
- On the numerical performance of finite-difference-based methods for derivative-free optimization
Cites work
- A derivative-free trust-region algorithm for the optimization of functions smoothed via Gaussian convolution using adaptive multiple importance sampling
- A stochastic line search method with expected complexity analysis
- Adaptive stochastic approximation by the simultaneous perturbation method
- An accelerated directional derivative method for smooth stochastic convex optimization
- An introduction to matrix concentration inequalities
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- ASTRO-DF: a class of adaptive sampling trust-region algorithms for derivative-free stochastic optimization
- Benchmarking Derivative-Free Optimization Algorithms
- Benchmarking optimization software with performance profiles.
- Computation of sparse low degree interpolating polynomials and their application to derivative-free optimization
- Derivative-free optimization methods
- Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods
- Estimating Computational Noise
- Geometry of interpolation sets in derivative free optimization
- Geometry of sample sets in derivative-free optimization: polynomial regression and underdetermined interpolation
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 3507890 (Why is no real title available?)
- scientific article; zbMATH DE number 1971709 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Introduction to Stochastic Search and Optimization
- More test examples for nonlinear programming codes
- Natural evolution strategies
- On lower bounds for tail probabilities
- On sampling rates in simulation-based recursions
- On the Global Convergence of Trust Region Algorithms Using Inexact Gradient Information
- 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
- ORBIT: Optimization by Radial Basis Function Interpolation in Trust-Regions
- Random gradient-free minimization of convex functions
- Sample size selection in optimization methods for machine learning
- Stochastic Estimation of the Maximum of a Regression Function
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic simulation: Algorithms and analysis
- The NEWUOA software for unconstrained optimization without derivatives
Cited in
(47)- Substitute derivatives in unconstrained optimization: A comparison of finite difference and response surface approximations
- Theoretical connections between optimization algorithms based on an approximate gradient
- Smart gradient - an adaptive technique for improving gradient estimation
- Zeroth-order methods for noisy Hölder-gradient functions
- Complex-step derivative approximation in noisy environment
- A mixed finite differences scheme for gradient approximation
- A noise-tolerant quasi-Newton algorithm for unconstrained optimization
- Adaptive gradient-free method for stochastic optimization
- Finite Difference Gradient Approximation: To Randomize or Not?
- An accelerated method for derivative-free smooth stochastic convex optimization
- Adaptive Finite-Difference Interval Estimation for Noisy Derivative-Free Optimization
- Benchmarking Derivative-Free Optimization Algorithms
- scientific article; zbMATH DE number 5018816 (Why is no real title available?)
- Full-low evaluation methods for derivative-free optimization
- Scalable subspace methods for derivative-free nonlinear least-squares optimization
- Zeroth-order optimization with orthogonal random directions
- A trust region method for noisy unconstrained optimization
- Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
- Accelerated gradient methods with absolute and relative noise in the gradient
- Quadratic regularization methods with finite-difference gradient approximations
- Adaptive sampling quasi-Newton methods for zeroth-order stochastic optimization
- Unifying framework for accelerated randomized methods in convex optimization
- Recent Theoretical Advances in Non-Convex Optimization
- Convergence of policy gradient methods for finite-horizon exploratory linear-quadratic control problems
- High probability complexity bounds for adaptive step search based on stochastic oracles
- Small errors in random zeroth-order optimization are imaginary
- Stochastic adversarial noise in the ``black box optimization problem
- New subspace method for unconstrained derivative-free optimization
- Unsupervised random quantum networks for PDEs
- Stochastic zeroth order descent with structured directions
- The ``black-box optimization problem: zero-order accelerated stochastic method via kernel approximation
- Sample complexity analysis for adaptive optimization algorithms with stochastic oracles
- The limitation of neural nets for approximation and optimization
- Derivative-free stochastic bilevel optimization for inverse problems
- A stochastic quasi-Newton method in the absence of common random numbers
- Local convergence analysis for nonisolated solutions to derivative-free methods of optimization
- Safe zeroth-order optimization using quadratic local approximations
- Derivative-free optimization with transformed objective functions and the algorithm based on the least Frobenius norm updating quadratic model
- Inexact Riemannian gradient descent method for nonconvex optimization with strong convergence
- Subdifferentially polynomially bounded functions and Gaussian smoothing-based zeroth-order optimization
- A regularized variance-reduced modified extragradient method for stochastic hierarchical games
- Curvature-aware derivative-free optimization
- Convergence analysis for a nonlocal gradient descent method via directional Gaussian smoothing
- Adaptive regularized quasi-Newton method using inexact first-order information
- A new inexact gradient descent method with applications to nonsmooth convex optimization
- Gradient and diagonal Hessian approximations using quadratic interpolation models and aligned regular bases
- Comparative study on gradient and Hessian estimation using the kriging method and neural network approximation
This page was built for publication: A theoretical and empirical comparison of gradient approximations in derivative-free optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143221)
