4. Об оптимизации процесса стохастической аппроксимации

Для процедур Роббинса — Монро и Кифера-Вольфовица сходимость процесса стохастической аппроксимации с вероятностью единица и в среднеквадратичном доказывается при довольно широких предположениях относительно входящих в эти процедуры коэффициентов. Требуется лишь сходимость и расходимость некоторых рядов, члены которых зависят от коэффициентов процедуры. Однако скорость сходимости существенно зависит от выбора этих коэффициентов. Поэтому можно ставить задачу об оптимальном в том или ином смысле выборе коэффициентов. Оценка скорости сходимости процедуры Роббинса — Монро в среднеквадратичном и некоторые результаты по ее оптимизации получены в работе Шметтерера [3]. Им рассмотрена следующая схема.

Пусть класс функций распределения, зависящий от параметра Предположим, что для некоторого тождественно по х с

и Пусть а — действительное число и уравнение имеет единственное решение Рассматривается процедура Роббинса — Монро для отыскания

При этом имеет функцию распределения Величины и имеют место соотношения

Функция удовлетворяет следующим предположениям:

Для некоторого при

а для

Обозначим

Шметтерер [3] доказал следующее утверждение:

Теорема 4.1 (Шметтерер). В принятых предположениях имеет место оценка

где некоторая константа,

При доказательстве теоремы 4.1 получена оценка

и показало, что она не может быть улучшена. Из теоремы 4.1 непосредственно следует, что всегда можно выбрать удовлетворяющие условиям (4.1), так, чтобы стремились к нулю как некоторая степень величины При этом, если известна величина такая, что условие выполняется в большинстве приложений), то у можно сделать как угодно близким к единице.

В работе Дупача [2] показано, что если к условиям теоремы 4.1 добавить предположение о существовании то, полагая можно доказать, что Здесь же оценивается скорость сходимости процедуры Кифера — Вольфовица в зависимости от порядка убывания коэффициентов и рассматривается вопрос об оптимальном (в смысле асимптотической скорости сходимости в среднеквадратичном этой процедуры) выборе порядка убывания коэффициентов. Показано, что оптимальная скорость сходимости существенно зависит от степени гладкости функции регрессии в окрестности ее точки максимума. Так, при отыскании максимума функции регрессии на отрезке с помощью обычной процедуры Кифера — Вольфовица вида

в предположении, что в окрестности точки максимума функция регрессии непрерывно дифференцируема, получается оценка

независимые случайные величины с распределением распределение это распределение, математическим

ожиданием которого является максимизируемая функция регрессии, а символ означает

В (4.2) , причем выбор является оптимальным, т. е. при этом скорость стремления к нулю наибольшая. Более точно, для Для существуют такие которые удовлетворяют всем условиям процедуры и для которых для некоторого

В предположении, что функция трижды непрерывно дифференцируема в окрестности точки 0, справедлива оценка

причем в этих условиях выбор является оптимальным. В предположении аналитичности функции в некоторой окрестности точки 0 и симметрии этой функции относительно 0 в некоторой окрестности этой точки имеет место оценка

Дупач в той же работе [2] дал оценку скорости сходимости многомерного процесса Роббинса-Монро для случая линейной функции регрессии. При некоторых условиях эта оценка имеет вид

Весьма интересной является работа Стратоновича [3]. Он исследовал возможности получения итерационных алгоритмов для отыскания корня уравнения регрессии по наблюдениям за реализациями

случайной величины при различных значениях параметра. Для получения алгоритмов использовалось разложение функции регрессии в ряд Тейлора. Каждый из алгоритмов определяется несколькими первыми членами ряда. Показано, что процедура Роббинса — Монро соответствует в этой схеме случаю, когда в разложении Тейлора сохраняются лишь линейные члены. Стратонович показал, что если в его схеме удерживать также члены более высокого порядка, то можно получить итерационные алгоритмы, которые дадут большую скорость сходимости, чем обычная процедура Роббинса — Монро.

Методика Стратоновича применима не только для случая одномерной процедуры Роббинса — Монро, но и к случаю многомерной процедуры, а также к отысканию экстремума функции регрессии.