Рандомизированный координатный спуск

Рандомизированный (блочный) координатный спуск — алгоритм оптимизации, популяризованный Нестеровым (2010) и позднее дополненный Ричтариком и Такачем (2011). Первый анализ метода, когда он применяется к задаче минимизации гладкой выпуклой функции, был осуществлён Нестеровым (2010)Шаблон:Sfn. В анализе Нестерова метод следует применять к квадратичным возмущениям исходной функции с неизвестным поправочным коэффициентом. Ричтарик и Такач (2011) дали границы сложности итераций без такого требования, то есть метод применяется к целевой функции напрямую. Более того, они обобщили постановку к задаче минимизации сложной функции, то есть суммы гладкой функции и (возможно негладкой) выпуклой блочно-разделимой функции:

$F(x)=f(x)+\mathrm{\Psi }(x),$

где $\mathrm{\Psi }(x)=\sum _{i=1}^n{\mathrm{\Psi }}_i(x^{(i)}),x\in R^N$ разложен на $n$ блоков переменных/координат: $x=(x^{(1)},\dots ,x^{(n)})$ и ${\mathrm{\Psi }}_1,\dots ,{\mathrm{\Psi }}_n$ являются (простыми) выпуклыми функциями.

Пример (декомпозиция блоков): Если $x=(x_1,x_2,\dots ,x_5)\in R^5$ и $n=3$, можно выбрать $x^{(1)}=(x_1,x_3),x^{(2)}=(x_2,x_5)$ и $x^{(3)}=x_4$.

Пример (разделяемые блоки):

1. $n=N;\mathrm{\Psi }(x)=\Vert x{\Vert }_1=\sum _{i=1}^n|x_i|$
2. $N=N_1+N_2+\dots +N_n;\mathrm{\Psi }(x)=\sum _{i=1}^n\Vert x^{(i)}{\Vert }_2$, где $x^{(i)}\in R^{N_i}$ и $\Vert \cdot {\Vert }_2$ является стандартной евклидовой нормой.

Алгоритм

Рассмотрим задачу оптимизации

$\underset{x\in R^n}{\min }f(x),$

где $f$ является выпуклой и гладкой функцией.

Гладкость: Под гладкостью мы понимаем следующее: мы предполагаем, что градиент $f$ покоординатно непрерывен по Липшицу с константами $L_1,L_2,\dots ,L_n$. То есть, мы предполагаем, что

$|{\mathrm{\nabla }}_{i}f(x+h{e}_i)-{\mathrm{\nabla }}_{i}f(x)|⩽L_i|h|,$

для любого $x\in R^n$ и $h\in R$, где ${\mathrm{\nabla }}_i$ означает частную производную по переменной $x^{(i)}$.

Нестеров, Ричтарик и Такач показали, что следующий алгоритм сходится к оптимальной точке: Шаблон:Начало коробки

    // Рандомизированный координатный спуск
    Input: $x_0\in R^n$ // стартовая точка
    Output: $x$

    set x := x_0

    for k := 1, ... do
        // обновляем координату $i\in \{1,2,\dots ,n\}$ случайно 
        $x^{(i)}=x^{(i)}-\frac{1}{L_i}{\mathrm{\nabla }}_{i}f(x)$ 
    end for

Скорость сходимости

Поскольку на итерациях алгоритма образуются случайные вектора, сложность следует отражать в числе итераций, необходимых для получения приближённого решения с высокой вероятностью. В статье Ричтарика и ТакачаШаблон:Sfn было доказано, что если $k⩾\frac{2n{R}_L(x_0)}{ϵ}\log \left(\frac{f(x_0)-f^{*}}{ϵ\rho }\right)$, где $R_L(x)=\underset{y}{\max }\underset{x^{*}\in X^{*}}{\max }\{\Vert y-x^{*}{\Vert }_L:f(y)⩽f(x)\}$, $f^{*}$ является оптимальным решением ($f^{*}=\underset{x\in R^n}{\min }\{f(x)\}$), $\rho \in (0,1)$ является уровнем доверительной вероятности, а $ϵ>0$ является желаемой точностью, то $Prob(f(x_k)-f^{*}>ϵ)⩽\rho$.

Пример для конкретной функции

Рисунок ниже показывает как $x_k$ меняется по итерациям. Задача

$f(x)=\frac{1}{2}{x}^T\left(\begin{array}{cc}1& 0,5\\ 0,5& 1\end{array}\right)x-\left(\begin{array}{cc}1,5& 1,5\end{array}\right)x,x_0={\left(\begin{array}{cc}0& 0\end{array}\right)}^T$

Расширение для блоков координат

Разбиение координатных направлений на блоки координат

Можно естественным образом расширить алгоритм с просто координат на блоки координат. Предположим, что мы имеем пространство $R^5$. Это пространство имеет 5 координатных направлений, а именно $\begin{array}{c}{e}_1=(1,0,0,0,0{)}^T,\\ e_2=(0,1,0,0,0{)}^T,\\ e_3=(0,0,1,0,0{)}^T,\\ e_4=(0,0,0,1,0{)}^T,\\ e_5=(0,0,0,0,1{)}^T\end{array}$

в которых метод может двигаться. Однако можно сгруппировать некоторые координатные направления в блоки и мы можем иметь 3 блочных координатных направлений (см. рисунок) вместо 5 координат.

См. также

• Координатный спуск
• Градиентный спуск

Литература

• Шаблон:Статья
• Шаблон:Статья