Случайный координатный спуск - Random coordinate descent

Метод рандомизированного (блочного) координатного спуска - это алгоритм оптимизации, популяризированный Нестеровым (2010) и Рихтариком и Такачем (2011). Первый анализ этого метода применительно к задаче минимизации гладкой выпуклой функции был выполнен Нестеровым (2010).^[1] В анализе Нестерова метод необходимо применить к квадратичному возмущению исходной функции с неизвестным масштабным коэффициентом. Richtárik and Takáč (2011) дают границы сложности итераций, которые этого не требуют, т. Е. Метод применяется непосредственно к целевой функции. Кроме того, они обобщают постановку задачи минимизации составной функции, то есть суммы гладкой выпуклой и (возможно негладкой) выпуклой блочно-разделимой функции:

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

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

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

Пример (блочно-разделимые регуляризаторы):

1. ${\displaystyle n=N;\Psi (x)=\|x\|_{1}=\sum _{i=1}^{n}|x_{i}|}$
2. ${\displaystyle N=N_{1}+N_{2}+\dots +N_{n};\Psi (x)=\sum _{i=1}^{n}\|x^{(i)}\|_{2}}$, куда ${\displaystyle x^{(i)}\in R^{N_{i}}}$ и ${\displaystyle \|\cdot \|_{2}}$ стандартная евклидова норма.

Алгоритм

Рассмотрим проблему оптимизации

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

куда ${\displaystyle f}$ это выпуклый и гладкая функция.

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

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

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

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

Алгоритм Ввод метода произвольного спуска координат: ${\displaystyle x_{0}\in R^{n}}$ // начальная точка Вывод: ${\displaystyle x}$    набор Икс : = x_0 за k := 1, ... делать        выбрать координату ${\displaystyle i\in \{1,2,\dots ,n\}}$, равномерно случайное обновление ${\displaystyle x^{(i)}=x^{(i)}-{\frac {1}{L_{i}}}\nabla f_{i}(x)}$     конец для

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

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

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

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

На следующем рисунке показано шоу ${\displaystyle x_{k}}$ в принципе развивается во время итераций.

${\displaystyle 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}}$

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

Блокирование направлений координат в направлениях блоков координат

Естественно, этот алгоритм можно распространить не только на координаты, но и на блоки координат. Предположим, что у нас есть пространство ${\displaystyle R^{5}}$. Это пространство имеет 5 координатных направлений, конкретно${\displaystyle 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 направления координат блока (см. Изображение).

Смотрите также

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

Рекомендации

1. Нестеров, Юрий (2010), "Эффективность методов координатного спуска в задачах оптимизации большого масштаба", SIAM Journal по оптимизации, 22 (2): 341–362, CiteSeerX  10.1.1.332.3336, Дои:10.1137/100802001
2. Richtárik, Питер; Такач, Мартин (2011), «Итерационная сложность рандомизированных методов блочно-координатного спуска для минимизации составной функции», Математическое программирование, серия A, 144 (1–2): 1–38, arXiv:1107.2848, Дои:10.1007 / s10107-012-0614-z