Convergence Rates of Finite Difference Stochastic Approximation Algorithms

Abstract

Recently there has been renewed interests in derivative free approaches to stochastic optimization. In this paper, we examine the rates of convergence for the Kiefer-Wolfowitz algorithm and the mirror descent algorithm, under various updating schemes using finite differences as gradient approximations. It is shown that the convergence of these algorithms can be accelerated by controlling the implementation of the finite differences. Particularly, it is shown that the rate can be increased to n-2/5 in general and to n-1/2 in Monte Carlo optimization for a broad class of problems, in the iteration number n.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2016
Accession Number
AD1023882

Entities

People

  • Liyi Dai

Organizations

  • North Carolina State University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Simulations
  • Computers
  • Convergence
  • Demographic Cohorts
  • Distribution Functions
  • Information Processing
  • Information Systems
  • Inversion
  • Iterations
  • Monte Carlo Method
  • New York
  • Operations Research
  • Probability
  • Random Variables
  • Simulations
  • Statistics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Statistical inference.