Robbins-Monro setting

The Robbins-Monro setting is a mathematical framework used to study stochastic approximation and optimization problems. It is named after Herbert Robbins and Sutton Monro, who introduced this framework in the 1950s.

In the Robbins-Monro setting, we consider a sequence of random variables (Xn, Yn) where Xn is a sequence of random variables taking values in a measurable space and Yn is a sequence of random variables taking values in the real line. The goal is to find a sequence of real numbers (θn) that converges to a solution of the optimization problem

minimize f(θ)

where f is an unknown function that we want to minimize.

The key assumption in the Robbins-Monro setting is that the function f is not known, but we can evaluate it at any point θ. Moreover, we assume that the random variables (Xn, Yn) are independent and identically distributed, and that the conditional distribution of Yn given Xn and θn is a probability distribution that depends on θn.

The Robbins-Monro algorithm is a way to solve the optimization problem in this setting. It is an iterative algorithm that updates the estimate θn based on the observed value of Yn:

θn+1 = θn - an(Xn, θn)(Yn - f(θn))

where an(Xn, θn) is a sequence of positive numbers that satisfies certain conditions. The idea behind this update rule is to move θn in the direction that reduces the expected value of the objective function f.

The Robbins-Monro algorithm has been widely used in statistics, machine learning, and control theory to solve various optimization and estimation problems. It is a powerful tool for dealing with complex and noisy data, and it can be used to find the optimal solution even when the objective function is non-convex or non-smooth.