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

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

$F(x)=f(x)+\Psi (x),$

где $\Psi (x)=\sum _{i=1}^{n}\Psi _{i}(x^{(i)}),x\in R^{N}$ разложен на $n$ блоков переменных/координат: $x=(x^{(1)},\dots ,x^{(n)})$ и $\Psi _{1},\dots ,\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;\Psi (x)=\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|$
2. $N=N_{1}+N_{2}+\dots +N_{n};\Psi (x)=\sum _{i=1}^{n}\|x^{(i)}\|_{2}$, где $x^{(i)}\in R^{N_{i}}$ and $\|\cdot \|_{2}$ является стандартной евклидовой нормой.

Алгоритм

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

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

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

Гладкость: Под гладкостью мы понимаем следующее: мы предполагаем, что градиент $f$ покоординатно непрерывен по Липшицу с константами $L_{1},L_{2},\dots ,L_{n}$. То есть, мы предполагаем, что

$|\nabla _{i}f(x+he_{i})-\nabla _{i}f(x)|\leqslant L_{i}|h|,$

для любого $x\in R^{n}$ и $h\in R$, где $\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}}}\nabla _{i}f(x)$ 
    end for

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

Поскольку на итерациях алгоритма образуются случайные вектора, сложность следует отражать в числе итераций, необходимых для получения приближённого решения с высокой вероятностью. В статье Ричтарика и Такача было доказано, что если $k\geqslant {\tfrac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\tfrac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)$, где $R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|y-x^{*}\|_{L}:f(y)\leqslant f(x)\}$, $f^{*}$ является оптимальным решением ($f^{*}=\min _{x\in R^{n}}\{f(x)\}$), $\rho \in (0,1)$ является уровнем доверительной вероятности, а $\epsilon >0$ является желаемой точностью, то $Prob(f(x_{k})-f^{*}>\epsilon )\leqslant \rho$.

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

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

$f(x)={\tfrac {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,\quad x_{0}=\left({\begin{array}{cc}0&0\end{array}}\right)^{T}$

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

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

Можно естественным образом расширить алгоритм с просто координат на блоки координат. Предположим, что мы имеем пространство $R^{5}$. Это пространство имеет 5 координатных направлений, а именно ${\begin{aligned}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{aligned}}$

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

См. также

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