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

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

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

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

Введение

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

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

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

где — неизвестная регрессионная функция. Прямое вычисление невозможно; вместо этого для любого заданного можно получить несмещённую зашумлённую оценку , такую что:

где — случайная величина с нулевым математическим ожиданием () и ограниченной дисперсией.

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

Хотя метод Роббинса — Монро является методом единичной траектории, а не популяционным алгоритмом (в отличие от генетических алгоритмов, эволюционных стратегий или дифференциальной эволюции), можно провести строгую содержательную аналогию для интуитивного понимания его компонентов: Представление решений: текущая оценка корня . Функция приспособленности: значение регрессионной функции , указывающее направление к цели. Инициализация: выбор начального приближения . Отбор: знак наблюдаемой величины определяет направление движения к корню (аналог давления отбора). Мутация: стохастический шум . В отличие от генетических алгоритмов, где мутация вводится искусственно, здесь шум является свойством среды, но при правильном затухании шага он обеспечивает необходимое "исследование" окрестностей корня. Элитизм: процедура усреднения итераций (см. Усреднение Полиака — Рупперта), сохраняющая асимптотически оптимальную оценку и отфильтровывающая высокочастотный шум последних шагов.

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

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

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

Псевдокод

Инициализировать начальное приближение Для : Получить зашумлённое наблюдение в точке Вычислить новое приближение: Вернуть (или усреднённое значение )

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

Для обеспечения сходимости с вероятностью 1 (почти наверное) последовательность шагов должна удовлетворять классическим условиям Дворецкого: для всех . (гарантирует достижение корня из любой начальной точки, баланс "исследования"). (гарантирует затухание дисперсии шума, баланс "эксплуатации"). Типичный выбор: , где . Кроме того, на функцию накладываются условия: Знакоопределённость: для всех . Ограниченный рост: для некоторых констант . Ограниченность дисперсии шума: .

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

Основная теорема сходимости была доказана Роббинсом и Монро^[1]. Позже Блюм (1954) и Дворецкий (1956) обобщили эти результаты для многомерного случая и ослабили требования к функции . Асимптотическая нормальность: при дополнительных условиях гладкости () и выборе с , оценка асимптотически нормальна:

Минимальная асимптотическая дисперсия достигается при , что даёт дисперсию .

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

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

Для достижения оптимальной асимптотической дисперсии без точного знания используется усреднение итераций:

Этот подход, предложенный Б.Т. Полиаком и А.Б. Юдицким, позволяет использовать более высокие начальные шаги (для быстрого сближения) и гарантирует оптимальную скорость сходимости по дисперсии, выступая аналогом элитизма в стохастической аппроксимации.

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

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

где — наблюдения в точках , а — последовательность возмущений.

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

Стохастический градиентный спуск (SGD) для минимизации ожидаемых потерь является прямым многомерным обобщением метода Роббинса — Монро, где . Современные адаптивные методы (Adam, RMSProp) модифицируют правило обновления шага, жертвуя строгими гарантиями сходимости классической теории Роббинса — Монро ради ускорения практической сходимости в задачах обучения нейронных сетей.

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

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

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

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

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

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

Литература

Кушин П. Стохастические методы аппроксимации и их приложения. — М.: Мир, 1980. Бенвеню А., Пристли М., Сороко М. Адаптивная фильтрация и настройка: теория и приложения. — М.: Мир, 1989. Robbins H., Monro S. A Stochastic Approximation Method // The Annals of Mathematical Statistics: Журнал. — 1951. — Т. 22. — № 3. — С. 400—407. Polyak B. T., Juditsky A. B. Acceleration of Stochastic Approximation by Averaging // SIAM Journal on Control and Optimization: Журнал. — 1992. — Т. 30. — № 4. — С. 838—855.