§ 5. Еще одно условие сходимости рекуррентных алгоритмов

В условиях теоремы 1 не предполагалось, что существует минимум функционала . Достаточно было того, что функционал ограничен снизу и, следовательно, существует точная нижняя грань. Сходимость к точной нижней грани и утверждала теорема.

Сейчас будем предполагать, что минимум функционала существует. Это позволит ослабить требования к порядку роста модуля градиента функции потерь.

Теорема 9.2. (Б. М. Литваков [44]). Пусть выполнены следующие условия:

1) функционал  ограничен снизу и существует непустое множество ,

2) ,

3) .

Тогда при любом  с вероятностью единица справедливо: .

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

.

Таким образом, последовательность, выйдя из гипершара, не может войти обратно.

Аналогично теореме 9.1, учитывая условия выпуклости  и условия теоремы 9.2, можно показать, что справедливо неравенство

.   (9.24)

Усилим неравенство (9.24), для чего оценим величину

.

Воспользовавшись неравенством , получим

.                        (9.25)

Подставляя (9.25) в (9.24), получим

.                  (9.26)

Из неравенства (9.26) следует, что величина  ограничена числом , не зависящим от номера . Покажем это.

Обозначим , . Покажем, что справедливо неравенство

.                (9.27)

Для  справедливость неравенства легко проверяется:

.

По индукции легко доказывается справедливость неравенства и для любого , если оно справедливо для :

Остается показать, что величина  ограничена, т. е.

.                  (9.28)

В самом деле, в произведении (9.28) сомножитель  ограничен, так как .

Сомножитель

также ограничен, так как бесконечное произведение

ограничено тогда и только тогда, когда сумма

ограничена.

Таким образом,

.

Используя неравенство Чебышева, можно получить неравенство .

На множестве  функция  ограничена. Рассмотрим процесс, отличающийся от (9.13) лишь тем, что при выходе за пределы  он «залипает». Очевидно, что все реализации исходного процесса, не покидающие , при этом сохранятся и вероятность «залипания» меньше . Применительно к новому процессу можно повторить все рассуждения теоремы (9.1) и показать, что с вероятностью, превышающей , для этого процесса

.

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

Далее, соответствующим выбором  величина  может быть сделана сколь угодно малой, откуда и следует утверждение теоремы.