Стохастическая аппроксимация Роббинса — Монро

Материал из MachineLearning.

Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 23:00, 18 июля 2026 (MSD)

Содержание

1 Введение
2 Формальная постановка задачи
- 2.1 Аналогия с эволюционными и популяционными методами
3 Алгоритм Роббинса — Монро
- 3.1 Псевдокод
- 3.2 Условия сходимости
4 Теоретические результаты
5 Роль размера шага и баланс исследования с эксплуатацией
6 Варианты и обобщения метода
7 Применение в машинном обучении
8 Сравнение с другими методами оптимизации
9 Ограничения и типичные ошибки
10 Литература

Введение

Стохастическая аппроксимация Роббинса — Монро (англ. Robbins-Monro stochastic approximation) — фундаментальный итеративный метод нахождения корня регрессионной функции, когда доступны только зашумленные наблюдения этой функции. Метод, предложенный Г. Роббинсом и С. Монро в 1951 году, заложил строгие математические основы современной стохастической оптимизации и является теоретическим предшественником стохастического градиентного спуска (SGD), повсеместно применяемого в машинном обучении.

Формальная постановка задачи

Пусть требуется найти корень $x^*$ уравнения:

$M(x) = 0$

где $M(x) = \mathbb{E}[Y | X=x]$ — неизвестная регрессионная функция. Прямое вычисление $M(x)$ невозможно; вместо этого для любого заданного $x$ можно получить несмещённую зашумлённую оценку $y$ , такую что:

$y = M(x) + \xi$

где $\xi$ — случайная величина с нулевым математическим ожиданием ( $\mathbb{E}[\xi | x] = 0$ ) и ограниченной дисперсией.

Аналогия с эволюционными и популяционными методами

Хотя метод Роббинса — Монро является методом единичной траектории, а не популяционным алгоритмом (в отличие от генетических алгоритмов или эволюционных стратегий), для интуитивного понимания его компонентов в контексте оптимизации можно провести строгую содержательную аналогию: Представление решений: текущая оценка корня $x_n \in \mathbb{R}^d$ . Функция приспособленности: значение регрессионной функции $M(x)$ , указывающее направление к цели. Инициализация: выбор начального приближения $x_1$ . Отбор: знак наблюдаемой величины $y_n$ определяет направление движения к корню (аналог давления отбора). Мутация: стохастический шум $\xi_n$ . В отличие от генетических алгоритмов, где мутация вводится искусственно, здесь шум является свойством среды, но при правильном затухании шага он обеспечивает необходимое исследование окрестностей корня. Элитизм: процедура усреднения итераций (см. Усреднение Полиака — Рупперта), сохраняющая асимптотически оптимальную оценку и отфильтровывающая высокочастотный шум последних шагов.

Алгоритм Роббинса — Монро

Итеративная процедура обновления оценки корня имеет вид:

$x_{n+1} = x_n - a_n y_n$

где $a_n > 0$ — последовательность шагов (коэффициентов обучения).

Псевдокод

Инициализировать начальное приближение $x_1$ Для $n = 1, 2, \dots, N$ : Получить зашумлённое наблюдение $y_n$ в точке $x_n$ Вычислить новое приближение: $x_{n+1} = x_n - a_n y_n$ Вернуть $x_{N+1}$ (или усреднённое значение $\bar{x}_N$ )

Условия сходимости

Для обеспечения сходимости $x_n \to x^*$ с вероятностью 1 (почти наверное) последовательность шагов ${a_n}$ должна удовлетворять классическим условиям Дворецкого: $a_n > 0$ для всех $n$ . $\sum_{n=1}^\infty a_n = \infty$ (гарантирует достижение корня из любой начальной точки, баланс исследования). $\sum_{n=1}^\infty a_n^2 < \infty$ (гарантирует затухание дисперсии шума, баланс эксплуатации). Типичный выбор: $a_n = \frac{c}{n}$ , где $c > 0$ . Кроме того, на функцию $M(x)$ накладываются условия: Знакоопределённость: $(x - x^) M(x) > 0$ для всех $x \neq x^$ . Ограниченный рост: $|M(x)| \leq A + B|x|$ для некоторых констант $A, B > 0$ . Ограниченность дисперсии шума: $\mathbb{E}[\xi_n^2 | x_n] \leq \sigma^2 < \infty$ .

Теоретические результаты

Основная теорема сходимости была доказана Роббинсом и Монро^[1]. Позже Блюм (1954) и Дворецкий (1956) обобщили эти результаты для многомерного случая и ослабили требования к функции $M(x)$ . Асимптотическая нормальность: при дополнительных условиях гладкости ( $M'(x^) > 0$ ) и выборе $a_n = \frac{c}{n}$ с $c > \frac{1}{2M'(x^)}$ , оценка $x_n$ асимптотически нормальна:

$\sqrt{n}(x_n - x^) \stackrel{d}{\to} \mathcal{N}\left(0, \frac{c^2 \sigma^2}{2c M'(x^) - 1}\right)$

Минимальная асимптотическая дисперсия достигается при $c = \frac{1}{M'(x^)}$ , что даёт дисперсию $\frac{\sigma^2}{(M'(x^))^2}$ .

Роль размера шага и баланс исследования с эксплуатацией

В отличие от популяционных методов, где баланс исследования и эксплуатации регулируется размером популяции, давлением отбора и вероятностью мутации, в методе Роббинса — Монро этот баланс полностью определяется последовательностью шагов $a_n$ . Большие значения $a_n$ на начальных этапах обеспечивают быстрое продвижение к области корня (исследование). Затухание $a_n$ на поздних этапах подавляет дисперсию шума и уточняет решение (эксплуатация). Неправильный выбор темпа затухания (например, $a_n = \frac{1}{n^\alpha}$ при $\alpha \leq 0.5$ или $\alpha > 1$ ) приводит к расходимости или застреванию вдали от оптимума.

Варианты и обобщения метода

Усреднение Полиака — Рупперта

Для достижения оптимальной асимптотической дисперсии без точного знания $M'(x^*)$ используется усреднение итераций:

$\bar{x}n = \frac{1}{n} \sum{i=1}^n x_i$

Этот подход позволяет использовать более высокие начальные шаги (например, $a_n = \frac{c}{n^\alpha}$ при $0.5 < \alpha < 1$ ) для быстрого сближения и гарантирует оптимальную скорость сходимости $O(1/n)$ по дисперсии.

Метод Кифера — Вольфовица

Если цель состоит в оптимизации (поиске экстремума функции $f(x)$ ), и доступны только зашумлённые значения самой функции, применяется метод Кифера — Вольфовица^[1]. Он использует конечно-разностную аппроксимацию градиента:

$x_{n+1} = x_n + a_n \frac{y_n^+ - y_n^-}{2c_n}$

где $y_n^\pm$ — наблюдения в точках $x_n \pm c_n$ , а $c_n \to 0$ — последовательность возмущений.

Одновременное возмущение (SPSA)

В задачах высокой размерности метод Кифера — Вольфовица требует $2d$ измерений на итерацию. Метод одновременного возмущения (Simultaneous Perturbation Stochastic Approximation, SPSA) требует лишь двух измерений независимо от размерности, используя случайный вектор возмущений^[1].

Связь со стохастическим градиентным спуском

Стохастический градиентный спуск (SGD) для минимизации ожидаемых потерь $\mathbb{E}[L(x, \zeta)]$ является прямым многомерным обобщением метода Роббинса — Монро, где $M(x) = \nabla_x \mathbb{E}[L(x, \zeta)]$ . Современные адаптивные методы (Adam, RMSProp) модифицируют правило обновления шага, жертвуя строгими гарантиями сходимости классической теории ради ускорения практической сходимости в задачах обучения нейронных сетей.

Применение в машинном обучении

Обучение с подкреплением: сходимость алгоритма Q-learning строго доказывается с использованием теории стохастической аппроксимации (условия Роббинса-Монро для шагов обучения). Адаптивная фильтрация: алгоритм наименьших средних квадратов (LMS) является частным случаем стохастической аппроксимации. Онлайн-обучение: обновление моделей на потоке данных, где вычисление полного градиента невозможно. Оптимизация гиперпараметров: в задачах с зашумлёнными функциями отклика, где градиент недоступен, используются конечно-разностные аналоги (SPSA).

Сравнение с другими методами оптимизации

Детерминированный градиентный спуск: требует точного вычисления градиента, сходится быстрее ( $O(1/n^2)$ для выпуклых задач), но неприменим при зашумлённых данных или огромных выборках. Байесовская оптимизация: эффективна для дорогостоящих чёрных ящиков с малой размерностью, но масштабируется плохо; метод Роббинса — Монро масштабируется на высокую размерность. Эволюционные алгоритмы и Случайный поиск: не требуют градиентной информации и устойчивы к локальным минимумам, но имеют значительно более высокую вычислительную стоимость на одну итерацию и медленную сходимость в окрестности оптимума по сравнению с RM. Методы нулевого порядка (SPSA): обобщают RM для случаев, когда измеряется только значение функции, а не её градиент, ценой увеличения дисперсии оценки направления.

Ограничения и типичные ошибки

Чувствительность к выбору последовательности шагов $a_n$ : слишком быстрое затухание приводит к застреванию вдали от корня, слишком медленное — к неуменьшающейся дисперсии. Предположение о мартингальном шуме: теория требует, чтобы шум был несмещённым условно на текущую итерацию. Систематическое смещение (bias) нарушает сходимость. Неприменимость к недифференцируемым функциям без модификаций: классический RM требует гладкости $M(x)$ в окрестности корня. Метод практически предпочтителен, когда размерность задачи высока, вычисление точного градиента невозможно или чрезмерно дорого, а шум измерений носит аддитивный характер с ограниченной дисперсией.

Литература

Robbins H., Monro S. A Stochastic Approximation Method // The Annals of Mathematical Statistics: Журнал. — 1951. — Т. 22. — № 3. — С. 400—407. Kiefer J., Wolfowitz J. Stochastic Estimation of the Maximum of a Regression Function // The Annals of Mathematical Statistics: Журнал. — 1952. — Т. 23. — № 3. — С. 462—466. Polyak B. T., Juditsky A. B. Acceleration of Stochastic Approximation by Averaging // SIAM Journal on Control and Optimization: Журнал. — 1992. — Т. 30. — № 4. — С. 838—855. Spall J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Transactions on Automatic Control: Журнал. — 1992. — Т. 37. — № 3. — С. 332—341. Кушин П. Стохастические методы аппроксимации и их приложения. — М.: Мир, 1980. Бенвеню А., Пристли М., Сороко М. Адаптивная фильтрация и настройка: теория и приложения. — М.: Мир, 1989.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B0%D0%BF%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D1%8F_%D0%A0%D0%BE%D0%B1%D0%B1%D0%B8%D0%BD%D1%81%D0%B0_%E2%80%94_%D0%9C%D0%BE%D0%BD%D1%80%D0%BE»

Категории: Стохастическая оптимизация | Методы оптимизации | Машинное обучение | Энциклопедия анализа данных | Математическая статистика