§ 4. Условия сходимости рекуррентных алгоритмов

Итак, пусть задана выпуклая по  при любом фиксированном  функция потерь  и определена процедура получения последовательности :

.

Рассмотрим несколько более общую, чем в главе IV, процедуру образования последовательности

,                   (9.13)

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

,

.

Будем считать, что величины , образующие бесконечную последовательность неотрицательных чисел, таковы, что

,

.

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

и

.

Справедлива теорема.

Теорема 9.1. (Б. М. Литваков [441]: Если:

1) функционал  ограничен снизу,

2) функция  ограничена сверху, т. е.,

3) дисперсия помехи  ограничена сверху, т. е. , то при любом начальном векторе  последовательность с вероятностью 1.

Доказательство теоремы опирается на следующие леммы.

Лемма 1. Для любых  и  можно подобрать такое , чтобы вероятность того, что вектор  окажется внутри гипершара  с центром в  и радиусом , была больше .

Доказательство. Покажем сначала, что для любого  существует ограниченная величина . Согласно процедуре (9.13) справедливо равенство

         (9.14)

Увеличим правую часть этого равенства. Согласно условию теоремы

,

,

.

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

                                           ,

оценим величину :

где .

Таким образом, оказывается справедливым неравенство

,                      (9.15)

где .

Используя неравенство (9.15) и учитывая, что

,

непосредственно получаем, что

,

т. е. величина  ограничена числом .

Для доказательства леммы воспользуемся неравенством Чебышева для нецентрированных случайных величин

.

Усилим это неравенство; учитывая, что

,

получим

.

Потребуем, чтобы эта вероятность не превосходила . Это произойдет, если величины , ,  будут связаны соотношением

,

откуда следует, что с вероятностью, превышающей , точка  будет находиться внутри гипершара  с центром в  и радиусом

.

Лемма 1 доказана.

Пусть, далее,

.

Обозначим через  область значений :

.

Лемма 2. Для любых  и  последовательность  с вероятностью 1 хоть раз войдет в область  при .

Утверждение леммы 2 эквивалентно такому: вероятность того, что подпоследовательность  ни разу не заходит в область  стремится к нулю при .

Доказательство. Для доказательства удобно рассмотреть процедуру, отличающуюся от (9.13) только тем, что если последовательность при  входит в область , то она там и остается.

Для этого будем считать, что соотношение

выполняется всегда при , а при  – лишь для . В случае же, когда при  элемент  принадлежит , последовательность «залипает», т. е.

.

Очевидно, что если последовательность , построенная в силу исходного алгоритма, ни разу не заходит в  при , то последовательность, построенная по новому правилу, ничем не отличается от исходной и, в частности, не заходит в  при . Поэтому достаточно оценить вероятность того, что новая последовательность ни разу не войдет в  при .

В области  выберем точку , для которой

(это всегда можно сделать), и оценим величину  для процедуры

               (9.16)

Согласно этой процедуре при

В силу условий теоремы

,

а также

 и .

Поэтому справедливо неравенство

              (9.17)

Далее, поскольку функция  выпукла, то

и поэтому

.       (9.18)

Но точки  и  выбраны так, что

(поскольку ) и

и, следовательно,

.                  (9.19)

Объединяя (9.17), (9.18) и (9.19), получаем, что при

.

Если же при  элемент , то

.

Пусть  – вероятность того, что . Тогда, переходя к безусловному математическому ожиданию, получим для

.

Из этого рекуррентного соотношения, очевидно, следует, что при

.

В силу леммы 1 величина

ограничена, и по условию теоремы ряд  сходится. Поэтому

,                  (9-20)

где  – константа, не зависящая от .

Далее, поскольку процедура (9.16) организована так, что, попав в , последовательность «залипает», вероятность  не возрастает с ростом .

Если бы при этом  оставалась больше некоторого , то величина

с ростом  неограниченно возрастала, поскольку при этом

,

а ряд  расходится.

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

Остается отметить, что последовательность  организована процедурой (9.16) так, что если она хоть раз войдет в  при , то она там и останется к моменту . Следовательно, вероятность того, что последовательность  ни разу не заходит в , равна  и стремится к нулю при .

Лемма доказана.

Лемма 3. Для любых  и  существует такое , что при всех  вероятность последовательности  выйти из области

,

при условии , меньше .

Доказательство. Оценим вероятность  того, что в последовательности  хотя бы один элемент не принадлежит  при условии, что . Для этого изменим процедуру (9.13) при , положив

                    (9.21)

Очевидно, что величина  равна вероятности того, что  при условии , если, начиная с , действует процедура (9.21).

Обозначим через  точку множества , ближайшую к , и оценим величину

.

Очевидно, справедливо неравенство

.

Поэтому при  в силу процедуры (9.21)

В силу выпуклости  справедливо неравенство

Но при  элементы  и  совпадают, а при

.

Поэтому

.

Следовательно,

Если же  при , то

.

Таким образом, всегда

Из этого рекуррентного соотношения следует, что при  справедливо

          (9.22)

поскольку при  имеет место

.

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

,

для всякой точки  выполняется неравенство

и для всякой точки  – неравенство

,

то

.                   (9.23)

Поэтому

.

Воспользуемся неравенством Чебышева

Учитывая далее (9.22) и (9.23), получаем

.

Правая часть неравенства не зависит от , поэтому, выбрав  достаточно большим, можно добиться, чтобы  было меньше  при всех , а это и значит, что последовательность выходит из  с вероятностью, меньшей .

Лемма доказана.

Докажем теперь теорему 9.1.

Для заданных  и  подберем  так, чтобы для всякого  вероятность последовательности выйти за пределы области

при условии, что , была меньше . Это можно сделать в силу леммы 3.

Далее, в силу леммы 2 последовательность  с вероятностью 1 хоть раз войдет в  после момента  и, следовательно, выйдет из  с вероятностью, меньшей . Ввиду произвольности  и  это означает, что

с вероятностью единица.

Теорема доказана.