Случайный спуск по координатам

Рандомизированный (блочный) метод спуска координат — это алгоритм оптимизации, популяризированный Нестеровым (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}}$ и $\|\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)|\leq L_{i}|h|,$

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

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

Algorithm Random Coordinate Descent Method    Input: $x_{0}\in R^{n}$ //starting point    Output: $x$    set x := x_0    for k := 1, ... do        choose coordinate $i\in \{1,2,\dots ,n\}$, uniformly at random        update $x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla _{i}f(x)$     end for

• « ←» означает присвоение . Например, « самый большой ← элемент » означает, что значение самого большого изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.

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

Поскольку итерации этого алгоритма представляют собой случайные векторы, результат сложности даст ограничение на количество итераций, необходимых для того, чтобы метод выдал приближенное решение с высокой вероятностью. Это было показано в что если $k\geq {\frac {2nR_{L}(x_{0})}{\epsilon }}\log \left({\frac {f(x_{0})-f^{*}}{\epsilon \rho }}\right)$, где $R_{L}(x)=\max _{y}\max _{x^{*}\in X^{*}}\{\|y-x^{*}\|_{L}:f(y)\leq f(x)\}$, $f^{*}$ оптимальное решение ( $f^{*}=\min _{x\in R^{n}}\{f(x)\}$), $\rho \in (0,1)$ это уровень доверия и $\epsilon >0$ точность цели,затем $Prob(f(x_{k})-f^{*}>\epsilon )\leq \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 координатных направлений, а именно $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}$в котором может двигаться метод случайного координатного спуска. Однако можно сгруппировать некоторые координатные направления в блоки, и вместо этих 5 координатных направлений мы можем иметь 3 блочных координатных направления (см. изображение).

См. также

• Координатный спуск
• Градиентный спуск
• Математическая оптимизация