.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/optimization/stochastic/plot_01_robbins_monro.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_optimization_stochastic_plot_01_robbins_monro.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_optimization_stochastic_plot_01_robbins_monro.py:


Robbins-Monro: stochastic gradient descent with decaying steps
====================================================================

Minimizes a quadratic using only noisy gradient observations. With
Robbins and Monro's step sizes :math:`a_k = a_0/(k+1)`, the noise
averages out and the error shrinks like :math:`1/\sqrt{k}`. A constant
step size instead stalls at a noise floor.

.. GENERATED FROM PYTHON SOURCE LINES 12-17

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.optimization import robbins_monro








.. GENERATED FROM PYTHON SOURCE LINES 18-20

Noisy gradients of f(x) = ||x - mu||^2 / 2
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 20-40

.. code-block:: Python


    mu = np.array([2.0, -1.0])


    def noisy_grad(x, rng):
        return x - mu + rng.normal(scale=2.0, size=2)


    n = 20000
    result = robbins_monro(noisy_grad, [0.0, 0.0], a0=1.0, n_iter=n, seed=0)
    print(f"estimate after {n} steps: {result.x.round(4)} (true minimizer {mu})")

    # Constant step size, for comparison.
    rng = np.random.default_rng(0)
    x = np.zeros(2)
    const_err = []
    for _ in range(n):
        x = x - 0.05 * noisy_grad(x, rng)
        const_err.append(np.linalg.norm(x - mu))





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    estimate after 20000 steps: [ 1.9888 -0.9979] (true minimizer [ 2. -1.])




.. GENERATED FROM PYTHON SOURCE LINES 41-43

Error versus iteration
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 43-53

.. code-block:: Python


    k = np.arange(1, n + 1)
    fig, ax = plt.subplots()
    ax.loglog(k, np.linalg.norm(result.path[1:] - mu, axis=1), label=r"Robbins-Monro, $a_k = 1/(k+1)$")
    ax.loglog(k, const_err, alpha=0.7, label=r"constant step $a = 0.05$")
    ax.loglog(k, 2.0 * np.sqrt(2.0 / k), "k--", label=r"$\propto 1/\sqrt{k}$")
    ax.set_xlabel("iteration k")
    ax.set_ylabel(r"$\|x_k - \mu\|$")
    ax.legend()
    ax.set_title("Stochastic approximation (Robbins-Monro, 1951)")



.. image-sg:: /api/gallery/optimization/stochastic/images/sphx_glr_plot_01_robbins_monro_001.png
   :alt: Stochastic approximation (Robbins-Monro, 1951)
   :srcset: /api/gallery/optimization/stochastic/images/sphx_glr_plot_01_robbins_monro_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    Text(0.5, 1.0, 'Stochastic approximation (Robbins-Monro, 1951)')




.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.147 seconds)


.. _sphx_glr_download_api_gallery_optimization_stochastic_plot_01_robbins_monro.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_01_robbins_monro.ipynb <plot_01_robbins_monro.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_01_robbins_monro.py <plot_01_robbins_monro.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_01_robbins_monro.zip <plot_01_robbins_monro.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_