Robbins–Monro algorithm
E1015498
The Robbins–Monro algorithm is a foundational stochastic approximation method used to find the roots of functions when observations are corrupted by noise, forming the basis for many modern optimization and learning techniques.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
iterative algorithm
ⓘ
optimization algorithm ⓘ root-finding algorithm ⓘ stochastic approximation method ⓘ |
| application |
adaptive signal processing
ⓘ
online parameter tuning ⓘ parameter estimation ⓘ sequential experimental design ⓘ |
| assumes |
existence of root of regression function
ⓘ
independent observation noise ⓘ |
| basisFor |
adaptive control algorithms
ⓘ
online learning algorithms ⓘ reinforcement learning algorithms ⓘ stochastic gradient methods ⓘ |
| convergenceCondition |
sum a_n = infinity
ⓘ
sum a_n^2 < infinity ⓘ |
| countryOfOrigin |
United States of America
ⓘ
surface form:
United States
|
| field |
control theory
ⓘ
machine learning ⓘ optimization ⓘ statistics ⓘ stochastic approximation ⓘ |
| goal | find root of an unknown function ⓘ |
| handles | noisy observations ⓘ |
| hasKeyConcept |
almost sure convergence
ⓘ
martingale convergence ⓘ step-size schedule ⓘ unbiased noisy observations ⓘ |
| historicalSignificance | first rigorous stochastic approximation procedure ⓘ |
| inspired |
Kiefer–Wolfowitz algorithm
NERFINISHED
ⓘ
stochastic approximation theory ⓘ stochastic gradient descent ⓘ |
| mathematicalDomain |
analysis
ⓘ
probability theory ⓘ |
| namedAfter |
Herbert Robbins
NERFINISHED
ⓘ
Sutton Monro NERFINISHED ⓘ |
| property | converges almost surely under regularity conditions ⓘ |
| publicationYear | 1951 ⓘ |
| publishedIn | Annals of Mathematical Statistics NERFINISHED ⓘ |
| relatedTo |
Kiefer–Wolfowitz algorithm
NERFINISHED
ⓘ
Polyak–Ruppert averaging NERFINISHED ⓘ Robbins–Siegmund theorem NERFINISHED ⓘ stochastic gradient descent ⓘ |
| typeOfNoise | additive noise ⓘ |
| typicalStepSizeForm | a_n = c / n GENERATED ⓘ |
| updateRule | theta_{n+1} = theta_n - a_n Y_n ⓘ |
| uses |
decreasing step sizes
ⓘ
stochastic approximation ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.