Unbiased Gradient Simulation for Zeroth-Order Optimization

We apply the Multi-Level Monte Carlo technique to get an unbiased estimator for the gradient of an optimization function. This procedure requires four exact or noisy function evaluations and produces an unbiased estimator for the gradient at one point. We apply this estimator to a non-convex stochastic programming problem. Under mild assumptions, our algorithm achieves a complexity bound independent of the dimension, compared with the typical one that grows linearly with the dimension.

• Publication year

  2020

• Venue

  Online World Conference on Soft Computing in Industrial Applications

• Publication date

  2020-12-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/WSC48552.2020.9384045
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications

  2019cited by this paper
• Random Gradient-Free Minimization of Convex Functions

  2015influential reference
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback

  2015cited by this paper
• Unbiased Estimation with Square Root Convergence for SDE Models

  2015cited by this paper
• Bandit Convex Optimization: Towards Tight Bounds

  2014cited by this paper
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations

  2013cited by this paper
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

  2013cited by this paper
• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization

  2012cited by this paper
• Introduction to derivative-free optimization

  2010cited by this paper
• Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback.

  2010cited by this paper
• Robust Stochastic Approximation Approach to Stochastic Programming

  2008cited by this paper
• Multilevel Monte Carlo Path Simulation

  2008cited by this paper
• Asymptotic Distribution of Coordinates on High Dimensional Spheres

  2007cited by this paper
• Online convex optimization in the bandit setting: gradient descent without a gradient

  2004cited by this paper
• A one-measurement form of simultaneous perturbation stochastic approximation

  1997cited by this paper
• Multivariate stochastic approximation using a simultaneous perturbation gradient approximation

  1992cited by this paper
• A Unified View of the IPA, SF, and LR Gradient Estimation Techniques

  1990cited by this paper
• Stochastic Estimation of the Maximum of a Regression Function

  1952cited by this paper
• A Stochastic Approximation Method

  1951cited by this paper

• On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization

  2025influential citation
• Determining the Failure Probability Gradient of the Rank-Structure System by the Fast Simulation Method

  2023cites this paper
• Hybrid Decentralized Optimization: First- and Zeroth-Order Optimizers Can Be Jointly Leveraged For Faster Convergence

  2022influential citation
• Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence

  2022influential citation