Stochastic Approximation

Table of Contents

Overview

A simple goal: Find the solution stochastic_approximation_755a947cc5621b043f5ac028c989d937f5660938.png to

stochastic_approximation_1b48e9567d8ae6b38d1a69338afad0b494a657f7.png

Basic algorithm

stochastic_approximation_e67da1698c228571ba7fc5d0cec97d37d5badced.png

The stepsize satisfies:

  • Ensure we can reach anywhere: stochastic_approximation_84b7be96f8c55c61b5565036b09faf29115d1546.png
  • To attenuate noise: stochastic_approximation_626439236be750848404be22e6f424e96ccc18a7.png

Usually will take stochastic_approximation_8cf74ca87311f78f1db377e7fe0d62a05ae5897e.png, which satisfies both of these.

Which we can write as:

stochastic_approximation_453d053b09767174b23369184e8cf4e05a3026c9.png

Which can be interpreted as a noisy Euler approximation to the ODE:

stochastic_approximation_d8978b1301e8da0ae2d5316ff309a029acccbc4c.png