A Theoretical and Empirical Comparison of Gradient Approximations in\n Derivative-Free Optimization

2019/05/03 by Albert S. Berahas, Liyuan Cao, Berahas, Albert S. +5 · 20 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1905.01332

openalex publication_date 2019/05/03 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28

Abstract

In this paper, we analyze several methods for approximating gradients of\nnoisy functions using only function values. These methods include finite\ndifferences, linear interpolation, Gaussian smoothing and smoothing on a\nsphere. The methods differ in the number of functions sampled, the choice of\nthe sample points, and the way in which the gradient approximations are\nderived. For each method, we derive bounds on the number of samples and the\nsampling radius which guarantee favorable convergence properties for a line\nsearch or fixed step size descent method. To this end, we use the results in\n[Berahas et al., 2019] and show how each method can satisfy the sufficient\nconditions, possibly only with some sufficiently large probability at each\niteration, as happens to be the case with Gaussian smoothing and smoothing on a\nsphere. Finally, we present numerical results evaluating the quality of the\ngradient approximations as well as their performance in conjunction with a line\nsearch derivative-free optimization algorithm.\n

Cited by

• Gauss-Newton accelerated MPPI Control
• Zeroth-order gradient estimators for stochastic problems with decision-dependent distributions
• Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations
• On Complexity of Model-Based Derivative-Free Methods
• Adversarial Attacks on Downstream Weather Forecasting Models: Application to Tropical Cyclone Trajectory Prediction
• SAFA-SNN: Sparsity-Aware On-Device Few-Shot Class-Incremental Learning with Fast-Adaptive Structure of Spiking Neural Network
• Zeroth-Order Constrained Optimization from a Control Perspective via Feedback Linearization
• CR-Net: Scaling Parameter-Efficient Training with Cross-Layer Low-Rank Structure
• SEGA: A Transferable Signed Ensemble Gaussian Black-Box Attack against No-Reference Image Quality Assessment Models
• Complexity Analysis of the Regular Simplicial Search Method with Reflection and Shrinking Steps for Derivative-Free Optimization
• SAGE: A Set-based Adaptive Gradient Estimator
• Interpolation-Based Gradient-Error Bounds for Use in Derivative-Free Optimization of Noisy Functions
• Quantum Algorithms for Projection-Free Sparse Convex Optimization
• Subspace-based Approximate Hessian Method for Zeroth-Order Optimization
• Accelerating Single-Point Zeroth-Order Optimization with Regression-Based Gradient Surrogates
• A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm
• An Introduction to Zero-Order Optimization Techniques for Robotics
• Branch, or Layer? Zeroth-Order Optimization for Continual Learning of Vision-Language Models

Related

• Linear interpolation gives better gradients than Gaussian smoothing in derivative-free optimization
• Full-low evaluation methods for derivative-free optimization
• On the Numerical Performance of Derivative-Free Optimization Methods\n Based on Finite-Difference Approximations
• Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study
• Noisy Optimization: Fast Convergence Rates with Comparison-Based Algorithms