Polyak’s Method Based on the Stochastic Lyapunov Function for Justifying the Consistency of Estimates Produced by a Stochastic Approximation Search Algorithm under an Unknown-But-Bounded Noise

Толық мәтін

1. ВВЕДЕНИЕ

Решение задач оптимизации часто сводится к нахождению точки экстремума некоторой функции. При этом принято полагаться на использование известных итерационных процедур, использующих значения исследуемой функции в выбираемых последовательно точках. Наличие помех при измерениях оказывает существенное влияние на результат. Для практики важно предложить такую итерационную схему, которая как можно более быстрая (по количеству итераций), простая (по сложности, требуемым ресурсам и времени выполнения одной итерации) и работоспособная при почти произвольных помехах. Именно такого типа процедуры были предложены в [1]–[3], основная идея которых состоит в решении сложных многомерных (в пространстве ${ℝ}^d$) задач оптимизации методами, похожими на процедуру Кифера–Вольфовица, но использующими на каждой итерации для формирования новой градиентной аппроксимации вместо 2d-измерений целевой функции только одно или два измерения в точках на случайно выбираемой линии, проходящей через точку предыдущей оценки. В статье 1989 г. [1] была предложена новая стохастическая рекуррентная процедура с одним измерением на итерации с пробными возмущениями на входе, для которой была обоснована состоятельность оценок при почти произвольных зависимых помехах в наблюдениях. Позже этот результат был распространен на векторный случай (см. [4]–[6]). В 1990 г. в статье Б. Т. Поляка и А. Б. Цыбакова [2] такого типа алгоритмы получили название поисковые алгоритмы стохастической аппроксимации, и для них при достаточно общих условиях была доказана асимптотическая оптимальность в том смысле, что для класса близких функций невозможно предложить итеративный алгоритм, который будет асимптотически сходится быстрее. Похожий алгоритм в англоязычной литературе под называнием метод SPSA (Simultaneously Perturbed Stochastic Approximation) в варианте с двумя измерениями был предложен в 1992 г. в статье [3] и с одним измерением — в [7]. Позднее в 1999 г. в статье [8] был обоснован новый алгоритм с двумя измерениями, в одном из которых измерение псевдоградиента проводилось в возмущенной точке, а в другом — в точке предшествующей оценки без возмущения. Такая версия лучше подходит для оптимизации в реальном времени, когда данные поступают в обновляющемся потоке. Основная идея метода состоит в решении сложных многомерных (в пространстве ${ℝ}^d$) задач методами, похожими на процедуру Кифера–Вольфовица, но используя на каждой итерации для формирования одной градиентной аппроксимации вместо 2d-измерений целевой функции только одно или два измерения в точках на случайно выбираемой линии, проходящей через точку предыдущей оценки.

В последнее время подобного рода алгоритмы привлекают внимание исследователей (см., например, [9], [10]). Их часто стали называть безградиентными методами с неточным оракулом. В 2023 г. вышла статья [11], развивающая идеи из [5]. Алгоритм, рассматриваемый в этой статье, был первоначально предложен в [12] для нахождения центров восходящих термических потоков, используемых для увеличения длительности полетов БПЛА планерного типа. При исследовании скорости сходимости оценок ключевую роль играет способ формирования размеров шагов алгоритмов. В статье [13] этот алгоритм с постоянными размерами шага использовался для решения задачи трекинга. На практике с течением времени вид исследуемой функции может несколько видоизменяться, и точки экстремумов могут дрейфовать со временем. В зависимости от скорости дрейфа и уровня помех в измерениях выбор постоянного большего размера шага алгоритма на итерации может давать более высокую скорость сходимости, но только в некоторую окрестность текущей точки экстремума, при малом постоянном размере шага оценки сходятся медленнее, но результаты точнее при отсутствии дрейфа. Важно, чтобы за время сходимости искомая точка экстремума не отдрейфовала далеко. Если нет возможности сходиться точно, есть возможность сойтись быстрее. Например, в задачах слежения за маневрирующими целями не так важно, чтобы оценки точно сошлись к искомому решению, как важно успеть отслеживать дрейф точки минимума (точность отходит на второй план, важнее становится скорость сходимости). Для задач распределенной оптимизации (в частности, распределенного отслеживания целей) в [14] была предложена модификация алгоритма, совмещенная с консенсусным протоколом локального голосования. В [15] показаны возможности ускорения сходимости по Нестерову, основанные на использовании метода тяжелого шарика Б. Т. Поляка (см. [16]).

Детальный вклад известных работ Б. Т. Поляка в развитие численных методов оптимизации анализируется в [17].

Далее в настоящей статье свойства оценок алгоритма из [13] анализируются на основе использования стохастической функции Ляпунова, опираясь на результаты статьи [18], в которой Б. Т. Поляк предложил и обосновал метод на основе стохастической функции Ляпунова для исследования свойств оценок псевдоградиентных итеративных алгоритмов стохастической оптимизации (см. также [6], гл. 5).

2. ПОСТАНОВКА ЗАДАЧИ, АЛГОРИТМ И ОСНОВНЫЕ ПРЕДПОЛОЖЕНИЯ

Пусть x₁, x₂, ... — последовательность точек измерения (план наблюдения, выбираемый или контролируемый экспериментатором), $x_n\in {ℝ}^d$, в которых в каждый момент времени n = 1, 2, ... доступно наблюдению с помехами v_n значение некоторой дифференцируемой по x_n штрафной функции (функции потерь) F (x_n, w_n):

$y_n=F\left(x_n,w_n\right)+v_n$, (1)

где $F:{ℝ}^d\times {ℝ}^p\to {ℝ}^1$, {w_n} — неконтролируемая последовательность p-мерных случайных векторов w_n (возмущений) с одинаковым (может быть) неизвестным распределением P_w(·) с компактным носителем $\mathbb{W}=supp\left(P_w\left(\cdot \right)\right)\subset {ℝ}^p$.

Рассмотрим задачу минимизации функции

$f\left(x\right):={\mathbb{E}}_w\left[F\left(x,w\right)\right]={\int }_{{ℝ}^p}F\left(x,w\right)P_w\left(dw\right)$. (2)

Здесь и далее $\mathbb{E}$ — символ математического ожидания.

Задача: по доступным наблюдениям необходимо построить последовательность оценок ${\hat{\theta }}_n$ неизвестного вектора θ, минимизирующего функцию .

Для решения поставленной задачи воспользуемся итеративным алгоритмом из [13] с двумя измерениями.

Алгоритм: выберем произвольный вектор начальной оценки ${\widehat{\theta }}_0\in {ℝ}^d$, и для выбираемых или задаваемых последовательностей положительных чисел $\left\{{\alpha }_n\right\}, \left\{{\beta }_n^{+}\right\}$ и $\left\{{\beta }_n^{-}\right\}$ с помощью пробного одновременного возмущения {∆_n} определим шаг итерации:

$\begin{array}{l}{x}_{2n}={\widehat{\theta }}_{2n-2}+{\beta }_n^{+}{\Delta }_n, x_{2n-1}={\widehat{\theta }}_{2n-2}-{\beta }_n^{-}{\Delta }_n,\\ {\widehat{\theta }}_{2n-1}={\widehat{\theta }}_{2n-2},\\ y_{2n}=F\left(x_{2n},w_{2n}\right)+v_{2n}, y_{2n-1}=F\left(x_{2n-1},w_{2n-1}\right)+v_{2n-1},\\ {\widehat{\theta }}_{2n}={\widehat{\theta }}_{2n-1}-\frac{{\alpha }_n}{{\beta }_n^{+}+{\beta }_n^{-}}{\mathcal{K}}_n\left({\Delta }_n\right)\left(y_{2n}-y_{2n-1}\right),\end{array}$ (3)

где ∆_n, n = 1, 2, ... — наблюдаемая (задаваемая или контролируемая пользователем) последовательность независимых случайных векторов из ${ℝ}^d$ с известными функциями распределения P_n(·), $K_n\left(\cdot \right):{ℝ}^d\to {ℝ}^d$ — задаваемые пользователем вектор-функции (ядра), удовлетворяющие вместе с P_n(·) условиям

$\int {\mathcal{K}}_n\left(x\right)P_n\left(dx\right)=\mathrm{0,}\int {\mathcal{K}}_n\left(x\right)x^T{P}_n\left(dx\right)=I$, (4)

$\underset{n}{\sup }\int {||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)<\infty , n=\mathrm{1,2,}\dots$. (5)

Следующие предположения будут использоваться для формулировки основного результата.

Предположение 1. Функция f(·) — сильно выпуклая, т. е. имеет единственный минимум в ${ℝ}^d$ в некоторой точке θ = θ(f(·)) и

$<x-\theta ,\nabla f\left(x\right)>\ge \mu {||x-\theta ||}^2\forall x\in {ℝ}^d$

с некоторой постоянной μ > 0. Здесь и далее $<x,y>:={\sum }_{i=1}^d{x}_i{y}_i$ — скалярное произведение $x,y\in {ℝ}^d$.

Предположение 2. Условие Липшица на градиент функции F(·, w)

$||\nabla F\left(x_1,w\right)-\nabla F\left(x_2,w\right)||\le A||x_1-x_2||$

с некоторой постоянной $A>\mu \forall w\in {ℝ}^p,\forall x_1,x_2\in {ℝ}^d$ .

Предположение 3. $\forall x\in {ℝ}^d$ функции F(x, ·) и ∇_xF(x, ·) равномерно на  ограничены.

Пусть ${\overline{v}}_n=v_{2n}-v_{2n-1}, {\overline{w}}_n=\left(\begin{array}{l}{w}_{2n}\\ w_{2n-1}\end{array}\right)$.

Предположение 4. О равномерной ограниченности помех наблюдения ${\overline{v}}_n$:

∀n ≥ 1, если ${\overline{v}}_n$ случайно, то $\mathbb{E}\left\{{\overline{v}}_n^2\right\}\le {\sigma }_v^2$, иначе ${\overline{v}}_n$ ограничены: $\left|{\overline{v}}_n\right|\le {\sigma }_v$.

Предположение 5. Условия о взаимной независимости помех ${\overline{v}}_n$, возмущений ${\overline{w}}_n$ и пробных возмущений ∆_n:

∀n ≥ 1 случайный вектор ∆_n не зависит от ${\overline{w}}_n$, случайные векторы ${\overline{w}}_n$, ∆_n не зависят от ${\overline{w}}_1,\dots ,{\overline{w}}_{n-1}$; если $\left\{{\overline{v}}_n\right\}$ — случайные величины, то ${\overline{w}}_n$, ∆_n также не зависят от ${\overline{v}}_1,\dots ,{\overline{v}}_n$.

3. АНАЛИЗ СХОДИМОСТИ ПОСЛЕДОВАТЕЛЬНОСТИ ОЦЕНОК

Для анализа сходимости оценок алгоритма (3) используется метод из [18], аналогичный второму методу Ляпунова в теории устойчивости. В качестве функции Ляпунова выберем

$V\left({\widehat{\theta }}_{2n-2}\right)=\frac{1}{2}{||{\widehat{\theta }}_{2n-2}-\theta ||}^2$. (6)

Перечислим основные условия теорем 1—3 из [18], выполнение которых надо проверить.

Условие А. Итеративный процесс Y_n, задающий направление изменения оценки, имеет марковский характер, т. е. распределение случайного вектора Y_n зависит только от ${\hat{\theta }}_{2n-2}$ и n:

$Y_n=G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)$.

Для алгоритма (3) имеем

$\mathbb{E}\left\{Y_n\right\}=\mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\frac{y_{2n}-y_{2n-1}}{{\beta }_n^{+}+{\beta }_n^{-}}\right|{\mathcal{F}}_{n-1}\}$.

Условие Б. $V\left({\widehat{\theta }}_{2n-2}\right)$ — неотрицательна, $\inf V\left({\widehat{\theta }}_{2n-2}\right)=\mathrm{0,} V\left({\widehat{\theta }}_{2n-2}\right)$ — дифференцируема, а ее градиент удовлетворяет условию Липшица:

$||\nabla V\left(x\right)-\nabla V\left(\theta \right)||\le L||x-\theta ||$.

Условие В. Условие псевдоградиентности:

$<\nabla V\left({\widehat{\theta }}_{2n-2}\right), \mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}>\ge {\delta }_{n}V\left({\widehat{\theta }}_{2n-2}\right)-{\gamma }_n, {\delta }_n>\mathrm{0,} {\gamma }_n\ge 0$.

Для алгоритма (3) с учетом выбранной в виде (6) функции Ляпунова получается следующее выражение:

$<\nabla V\left({\widehat{\theta }}_{2n-2}\right),\mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}> =<{\widehat{\theta }}_{2n-2}-\theta ,\mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\frac{{\displaystyle y_{2n}-y_{2n-1}}}{{\displaystyle {\beta }_n^{+}+{\beta }_n^{-}}}\right|{\mathcal{F}}_{n-1}\}>$.

Учитывая вид y_2n, y_2n–1 и x_2n, x_2n–1, перепишем $\mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}$ в виде

$\mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}=\mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\frac{F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}{\Delta }_n,w_{2n}\right)+v_{2n}-F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}{\Delta }_n,w_{2n-1}\right)-v_{2n-1}}{{\beta }_n^{+}+{\beta }_n^{-}}\right|{\mathcal{F}}_{n-1}\}$.

Так как в силу предположения 5 вектор ∆_n не зависит от v_n, то

$\mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\left(v_{2n}-v_{2n-1}\right)\right|{\mathcal{F}}_{n-1}\}=\int {\mathcal{K}}_n\left(x\right)P_n\left(dx\right)\mathbb{E}\{\left(v_{2n}-v_{2n-1}\right)\left|{\mathcal{F}}_{n-1}\right\}$.

Далее из (4) следует, что первый сомножитель в последней формуле равен нулю, а значит, и

$\mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\left(v_{2n}-v_{2n-1}\right)\right|F_{n-1}\}=0$.

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

$\mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}=\frac{1}{{\beta }_n^{+}+{\beta }_n^{-}}\mathbb{E}\{{\mathcal{K}}_n\left({\Delta }_n\right)F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}{\Delta }_n,w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}{\Delta }_n,w_{2n-1}\right)|{\mathcal{F}}_{n-1}\}$. (7)

Воспользовавшись дважды формулой Тейлора, перепишем выражение под знаком математического ожидания:

$\begin{array}{c}\frac{{\beta }_n^{+}}{{\beta }_n^{+}+{\beta }_n^{-}}\nabla f\left({\widehat{\theta }}_{2n-2}\right)+\frac{{\beta }_n^{+}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left({\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)\right)dt{P}_n\left(dx\right)P_w\left(dw\right)+\\ +\frac{{\beta }_n^{-}}{{\beta }_n^{+}+{\beta }_n^{-}}\nabla f\left({\widehat{\theta }}_{2n-2}\right)-\frac{{\beta }_n^{-}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left(\begin{array}{c}{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-\\ -{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)\end{array}\right)dt{P}_n\left(dx\right)P_w\left(dw\right).\end{array}$

Оценим два слагаемых с интегралами по модулю:

$\begin{array}{c}\left|\begin{array}{c}\frac{{\beta }_n^{+}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left({\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)\right)dt P_n\left(dx\right)P_w\left(dw\right)+\\ +\frac{{\beta }_n^{-}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left({\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{-}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)\right)dt P_n\left(dx\right)P_w\left(dw\right)\end{array}\right|\le \\ \le \left|\frac{{\beta }_n^{+}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left({\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)\right)dt P_n\left(dx\right)P_w\left(dw\right)\right|+\end{array}$ (8)

$\begin{array}{c}+\left|\frac{{\beta }_n^{-}}{{\beta }_n^{+}+{\beta }_n^{-}}\iint {\mathcal{K}}_n\left(x\right)x^T{\int }_0^1\left({\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)\right)dt P_n\left(dx\right)P_w\left(dw\right)\right|\le \\ \le \frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}\int \int ||{\mathcal{K}}_n\left(x\right)||||x||A||x||P_n\left(dx\right)P_w\left(dw\right)\le C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}.\end{array}$

Подставляем получившееся в (8) выражение в (7):

$<{\widehat{\theta }}_{2n-2}-\theta , \mathbb{E}\left\{{\mathcal{K}}_n\left({\Delta }_n\right)\frac{y_{2n}-y_{2n-1}}{{\beta }_n^{+}+{\beta }_n^{-}}\right|{\mathcal{F}}_{n-1}\}>\ge <{\widehat{\theta }}_{2n-2}-\theta ,\nabla f\left({\widehat{\theta }}_{2n-2}\right)>-C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}||{\widehat{\theta }}_{2n-2}-\theta ||$,

Так как

$2C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}||{\widehat{\theta }}_{2n-2}-\theta ||\le {\left(C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}\right)}^2+{||{\widehat{\theta }}_{2n-2}-\theta ||}^2$,

то

$\begin{array}{c}<\nabla V\left({\widehat{\theta }}_{2n-2}\right),\mathbb{E}\left\{G_n\left({\widehat{\theta }}_{2n-2},{\overline{w}}_n\right)\right\}>\ge <{\widehat{\theta }}_{2n-2}-\theta ,\nabla f\left({\widehat{\theta }}_{2n-2}\right)>-\frac{1}{2}{\left(C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}\right)}^2-\frac{1}{2}{||{\widehat{\theta }}_{2n-2}-\theta ||}^2\ge \\ \ge \left(2\mu -1\right)\frac{1}{2}{||{\widehat{\theta }}_{2n-2}-\theta ||}^2-\frac{1}{2}{\left(C_1\frac{{\left({\beta }_n^{+}\right)}^2+{\left({\beta }_n^{-}\right)}^2}{{\beta }_n^{+}+{\beta }_n^{-}}\right)}^2.\end{array}$ (9)

Условие Г. Условие на G_n(·, ·):

$\mathbb{E}\left\{{||G_n\left({\overline{w}}_n,x\right)||}^2\right\}\le {\sigma }_n^2+{\tau }_{n}V\left(x\right), {\sigma }_n\ge \mathrm{0,} {\tau }_n\ge 0$.

Учитывая ограниченность вектор-функций ${\mathcal{K}}_n\left(\cdot \right)$ и компактность их носителя, последовательно выводим

$\begin{array}{c}\mathbb{E}\left\{\frac{{(y_{2n}-y_{2n-1})}^2}{4{\beta }_n^{+}+{\beta }_n^{-}}{||{\mathcal{K}}_n\left({\Delta }_n\right)||}^2|{\mathcal{F}}_{n-1}\right\}\le \frac{1}{2}\underset{x}{\sup }{\left(x\right)}^2{\mathcal{K}}_n\mathbb{E}\{v_{2n-1}^2+v_{2n}^2|{\mathcal{F}}_{n-1}\}+\iiint {\left(\begin{array}{c}F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}x,w_{2n}\right)-\\ -F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}x,w_{2n-1}\right)\end{array}\right)}^2\times \\ \times {||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)\le C_7{\beta }_n^2\left({||{\widehat{\theta }}_{2n-2}-\theta ||}^2+{\beta }_n^2\right)+C_8{\xi }_n^2=C_7{\beta }_n^2{||{\widehat{\theta }}_{2n-2}-\theta ||}^2+C_8{\xi }_n^2+o\left({\beta }_n^2\right),\end{array}$ (10)

использовав ограниченность вектор-функций ${\mathcal{K}}^n\left(\cdot \right)$, компактность их носителя и неравенство

$\begin{array}{c}\left|F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}x,w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}x,w_{2n-1}\right)\right|\le \left|F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}x,w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)\right| + \\ +\left| F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}x,w_{2n-1}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)\right|+\left|F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)\right|,\end{array}$

где C_i, i = 1, 2, ... — некоторые положительные константы.

Для разности применим дважды формулу Тейлора:

$\begin{array}{c}F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}x,w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}x,w_{2n-1}\right)=F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)+<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right),{\beta }_n^{+}x>-\\ -F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)-<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right),{\beta }_n^{-}x>.\end{array}$ (11)

Добавив и отняв ${\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)$ и ${\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)$, получаем

$\begin{array}{c}=F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)+<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right), {\beta }_n^{+}x>-\\ -<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right), {\beta }_n^{-}x>+\\ +<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right), {\beta }_n^{+}x>-<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right), {\beta }_n^{-}x>.\end{array}$ (12)

Оценим скалярные произведения

$$\begin{gathered} <{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right), {\beta }_n^{+}x>\le ||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||||{\beta }_n^{+}x||, \\ <{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right), {\beta }_n^{-}x>\le ||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||||{\beta }_n^{-}x||, \end{gathered}$$

$$\begin{gathered} 〈{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right), {\beta }_n^{+}x〉\le ||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||||{\beta }_n^{+}x||, \\ 〈{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right), {\beta }_n^{-}x〉\le ||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||||{\beta }_n^{-}x||. \end{gathered}$$

В итоге получаем оценку для (12):

$\begin{array}{c}F\left({\widehat{\theta }}_{2n-2}+{\beta }_n^{+}x,w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2}-{\beta }_n^{-}x,w_{2n-1}\right)\le F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)+\\ +||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}+t{\beta }_n^{+}x,w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||||{\beta }_n^{+}x||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2}-t{\beta }_n^{-}x,w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||||{\beta }_n^{-}x||+\\ +||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||||{\beta }_n^{+}x||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||||{\beta }_n^{-}x||.\end{array}$

Подставив получившуюся оценку в (10), последовательно выводим

$$\begin{gathered} \mathbb{E}\left\{\frac{{\left(y_{2n}-y_{2n-1}\right)}^2}{4{\beta }_n^{+}+{\beta }_n^{-}}{||{\mathcal{K}}_n\left({∆}_n\right)||}^2|{\mathcal{F}}_{n-1}\right\}\le \\ \le \frac{1}{2}\underset{x}{sup}{\mathcal{K}}_n{\left(x\right)}^2\mathbb{E}\left\{v_{2n-1}^2-v_{2n}^2|{\mathcal{F}}_{n-1}\right\}+ \\ +\int \int \int (F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)-F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}+t{\beta }_n^{+}x, w_{2n}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||||{\beta }_n^{+}x||+ \end{gathered}$$

$$\begin{gathered} +||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}+t{\beta }_n^{-}x, w_{2n-1}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||||{\beta }_n^{-}x||+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||||{\beta }_n^{+}x||+ \\ +||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||||{\beta }_n^{-}x||{)}^2{||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)= \\ =\frac{1}{2}\underset{x}{sup}{\mathcal{K}}_n{\left(x\right)}^2\mathbb{E}\left\{v_{2n-1}^2-v_{2n}^2|{\mathcal{F}}_{n-1}\right\}+ \end{gathered}$$

$$\begin{gathered} +\int \int \int (F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)-F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}+t{\beta }_n^{+}x, w_{2n}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||||{\beta }_n^{+}x||+ \\ +||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}+t{\beta }_n^{-}x, w_{2n-1}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||||{\beta }_n^{-}||+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||||{\beta }_n^{+}||+ \\ +||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||||{\beta }_n^{-}x||{)}^2{||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)\le \end{gathered}$$ (13)

$$\begin{gathered} \le \frac{1}{2}\underset{x}{sup}{\mathcal{K}}_n{\left(x\right)}^2\mathbb{E}\left\{v_{2n-1}^2-v_{2n}^2|{\mathcal{F}}_{n-1}\right\}+ \\ +\int \int \int (F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)-F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)+(A||t||{\beta }_n^{+}||x||{\beta }_n^{+}+A||t{\beta }_n^{-}x||||{\beta }_n^{-}||+ \\ +||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||||{\beta }_n^{+}||+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||||{\beta }_n^{-}||)||x||{)}^2\times \end{gathered}$$

$$\begin{gathered} {||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)\le \\ \le \frac{1}{2}\underset{x}{sup}{\mathcal{K}}_n{\left(x\right)}^2\mathbb{E}\left\{v_{2n-1}^2-v_{2n}^2|{\mathcal{F}}_{n-1}\right\}+ \\ \int \int \int (F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)-F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)+(A||x||\left({{\beta }_n^{+}}^2+{{\beta }_n^{-}}^2\right)+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||{\beta }_n^{+}+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||{\beta }_n^{-})||x||{)}^2{||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)\le {\sigma }_n^2 \end{gathered}$$

в силу ограниченности ${\mathcal{K}}_n$ и компактности их носителя. Распишем разность

$F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)$ (14)

в виде

$F\left(\theta ,w_{2n}\right)+<{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>-F\left(\theta ,w_{2n-1}\right)-<{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>$.

Добавив и отняв ${\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)$ и ${\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)$, получаем

$\begin{array}{c}=F\left(\theta ,w_{2n}\right)-F\left(\theta ,w_{2n-1}\right)+<{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>-\\ -<{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>+\\ +<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>-<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>.\end{array}$

Оценим скалярные произведения:

$\begin{array}{l}<{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>\le \\ \le ||{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||||{\widehat{\theta }}_{2n-2}-\theta ||,\\ <{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right)>-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>\le \\ \le ||{\nabla }_{x}F|\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right)-{\nabla }_x|F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||||{\widehat{\theta }}_{2n-2}-\theta ||,\end{array}$

$\begin{array}{l}<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>-<{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right),\left({\widehat{\theta }}_{2n-2}-\theta \right)>\le \\ \le ||{\widehat{\theta }}_{2n-2}-\theta ||\left(||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||\right),\end{array}$

Получили оценку для (14) в виде

$$\begin{gathered} F\left({\widehat{\theta }}_{2n-2}, w_{2n}\right)-F\left({\widehat{\theta }}_{2n-2}, w_{2n-1}\right)\le \\ \le F\left(\theta , w_{2n}\right)-F\left(\theta , w_{2n-1}\right)+||{\widehat{\theta }}_{2n-2}-\theta ||(||{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||+ \\ +||{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||+ \\ +||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||). \end{gathered}$$

Подставим получившееся выражение в (13):

$$\begin{gathered} \mathbb{E}\left\{\frac{{\left(y_{2n}-y_{2n-1}\right)}^2}{4{\beta }_n^{+}+{\beta }_n^{-}}{||{\mathcal{K}}_n\left({∆}_n\right)||}^2|{\mathcal{F}}_{2n-2}\right\}\le \\ \le \frac{1}{2}\underset{x}{sup}{\mathcal{K}}_n{\left(x\right)}^2\mathbb{E}\left\{v_{2n-1}^2-v_{2n}^2|{\mathcal{F}}_{2n-2}\right\}+ \\ +(F\left(\theta , w_{2n}\right)-F\left(\theta , w_{2n-1}\right)+||{\hat{\theta }}_{2n-2}-\theta ||(||{\nabla }_{x}F\left(\theta +t\left({\hat{\theta }}_{2n-2}-\theta \right), w_{2n}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||+ \end{gathered}$$ (15)

$$\begin{gathered} +||{\nabla }_{x}F\left(\theta +t\left({\hat{\theta }}_{2n-2}-\theta \right), w_{2n-1}\right)-{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||+ \\ ||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||)+{(A||x||\left({{\beta }_n^{+}}^2+{{\beta }_n^{-}}^2\right)+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n}\right)||{\beta }_n^{+}+||{\nabla }_{x}F\left({\hat{\theta }}_{2n-2}, w_{2n-1}\right)||{\beta }_n^{-})||x||)}^2{||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right). \end{gathered}$$

Введем обозначения:

$$\begin{gathered} a=F\left(\theta ,w_{2n}\right)-F\left(\theta ,w_{2n-1}\right)+\left(\begin{array}{c}A||x||\left({{\beta }_n^{+}}^2+{{\beta }_n^{-}}^2\right)+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||{\beta }_n^{+}+\\ +||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||{\beta }_n^{-}\end{array}\right)||x||, \\ \begin{array}{c}b=||{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||+\\ +||{\nabla }_{x}F\left(\theta +t\left({\widehat{\theta }}_{2n-2}-\theta \right),w_{2n-1}\right)-{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n}\right)||+||{\nabla }_{x}F\left({\widehat{\theta }}_{2n-2},w_{2n-1}\right)||,\\ {\left(a+||{\widehat{\theta }}_{2n-2}-\theta ||b\right)}^2=a^2+ab||{\widehat{\theta }}_{2n-2}-\theta ||+b^2{\left(||{\widehat{\theta }}_{2n-2}-\theta ||\right)}^2.\end{array} \end{gathered}$$

Так как

$\begin{array}{c}2||{\widehat{\theta }}_{2n-2}-\theta ||\le 1+{||{\widehat{\theta }}_{2n-2}-\theta ||}^2,\\ ||{\widehat{\theta }}_{2n-2}-\theta ||\le 0.5+0.5{||{\widehat{\theta }}_{2n-2}-\theta ||}^2,\end{array}$

то

${\left(a+||{\widehat{\theta }}_{2n-2}-\theta ||b\right)}^2\le a^2+ab\left(0.5+0.5{||{\widehat{\theta }}_{2n-2}-\theta ||}^2\right)+b^2{\left(||{\widehat{\theta }}_{2n-2}-\theta ||\right)}^2=a^2+0.5ab+(0.5ab+b^2){||{\widehat{\theta }}_{2n-2}-\theta ||}^2$.

После подстановки в (15) получаем оценку

$\begin{array}{c}\mathbb{E}\left\{\frac{{\left(y_{2n}-y_{2n-1}\right)}^2}{4{\beta }_n^{+}+{\beta }_n^{-}}{||{\mathcal{K}}_n\left({\Delta }_n\right)||}^2|{\mathcal{F}}_{n-1}\right\}\le \frac{1}{2}\underset{x}{\sup }{K}_n{\left(x\right)}^2\mathbb{E}\{v_{2n-1}^2+v_{2n}^2|{\mathcal{F}}_{n-1}\}+\\ +\iiint \left(a^2+0.5ab+\left(0.5ab+b^2\right){||{\widehat{\theta }}_{2n-2}-\theta ||}^2\right)\times {||{\mathcal{K}}_n\left(x\right)||}^2{P}_n\left(dx\right)P_w\left(d{w}_{2n}\right)P_w\left(d{w}_{2n-1}\right)\le C_{\tau }V\left(x\right)+C_{\sigma }\end{array}$