zeroth-order optimization

Worst-case evaluation complexity of a derivative-free quadratic regularization method

  • Geovani Nunes Grapiglia
    • Categories Nonlinear Optimization Tags , , ,

    This short paper presents a derivative-free quadratic regularization method for unconstrained minimization of a smooth function with Lipschitz continuous gradient. At each iteration, trial points are computed by minimizing a quadratic regularization of a local model of the objective function. The models are based on forward finite-difference gradient approximations. By using a suitable acceptance condition … Read more

    Adaptive Finite-Difference Interval Estimation for Noisy Derivative-Free Optimization

  • Hao-Jun Shi
  • Yuchen Xie
  • Melody Xuan
  • Jorge Nocedal
    • Categories Nonlinear Optimization Tags , , , ,

    A common approach for minimizing a smooth nonlinear function is to employ finite-difference approximations to the gradient. While this can be easily performed when no error is present within the function evaluations, when the function is noisy, the optimal choice requires information about the noise level and higher-order derivatives of the function, which is often … Read more

    Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization

  • Raghu Bollapragada
  • Stefan M. Wild
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

    We consider unconstrained stochastic optimization problems with no available gradient information. Such problems arise in settings from derivative-free simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We develop modified versions of a norm … Read more

    On the Numerical Performance of Derivative-Free Optimization Methods Based on Finite-Difference Approximations

  • Jorge Nocedal
  • Hao-Jun Shi
  • Melody Xuan
  • Figen Oztoprak
    • Categories Nonlinear Optimization Tags , , , ,

    The goal of this paper is to investigate an approach for derivative-free optimization that has not received sufficient attention in the literature and is yet one of the simplest to implement and parallelize. It consists of computing gradients of a smoothed approximation of the objective function (and constraints), and employing them within established codes. These … Read more

    SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

  • Cong Fang
  • Chris Junchi Li
  • Zhouchen Lin
  • Tong Zhang
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, combining SPIDER with normalized gradient descent, we propose … Read more