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

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

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

где Ψ ( x ) = ∑ i = 1 n Ψ i ( x ( i ) ) , x ∈ R N {displaystyle Psi (x)=sum _{i=1}^{n}Psi _{i}(x^{(i)}),xin R^{N}} разложен на n {displaystyle n} блоков переменных/координат: x = ( x ( 1 ) , … , x ( n ) ) {displaystyle x=(x^{(1)},dots ,x^{(n)})} и Ψ 1 , … , Ψ n {displaystyle Psi _{1},dots ,Psi _{n}} являются (простыми) выпуклыми функциями.

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

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

n = N ; Ψ ( x ) = ‖ x ‖ 1 = ∑ i = 1 n | x i | {displaystyle n=N;Psi (x)=|x|_{1}=sum _{i=1}^{n}|x_{i}|}

N = N 1 + N 2 + ⋯ + N n ; Ψ ( x ) = ∑ i = 1 n ‖ x ( i ) ‖ 2 {displaystyle N=N_{1}+N_{2}+dots +N_{n};Psi (x)=sum _{i=1}^{n}|x^{(i)}|_{2}} , где x ( i ) ∈ R N i {displaystyle x^{(i)}in R^{N_{i}}} and ‖ ⋅ ‖ 2 {displaystyle |cdot |_{2}} является стандартной евклидовой нормой.

Алгоритм

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

min x ∈ R n f ( x ) , {displaystyle min _{xin R^{n}}f(x),}

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

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

| ∇ i f ( x + h e i ) − ∇ i f ( x ) | ⩽ L i | h | , {displaystyle | abla _{i}f(x+he_{i})- abla _{i}f(x)|leqslant L_{i}|h|,}

для любого x ∈ R n {displaystyle xin R^{n}} и h ∈ R {displaystyle hin R} , где ∇ i {displaystyle abla _{i}} означает частную производную по переменной x ( i ) {displaystyle x^{(i)}} .

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

// Рандомизированный координатный спуск Input: x 0 ∈ R n {displaystyle x_{0}in R^{n}} // стартовая точка Output: x {displaystyle x} set x := x_0 for k := 1, ... do // обновляем координату i ∈ { 1 , 2 , … , n } {displaystyle iin {1,2,dots ,n}} случайно x ( i ) = x ( i ) − 1 L i ∇ i f ( x ) {displaystyle x^{(i)}=x^{(i)}-{frac {1}{L_{i}}} abla _{i}f(x)} end for

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

Поскольку на итерациях алгоритма образуются случайные вектора, сложность следует отражать в числе итераций, необходимых для получения приближённого решения с высокой вероятностью. В статье Ричтарика и Такача было доказано, что если k ⩾ 2 n R L ( x 0 ) ϵ log ⁡ ( f ( x 0 ) − f ∗ ϵ ρ ) {displaystyle kgeqslant { frac {2nR_{L}(x_{0})}{epsilon }}log left({ frac {f(x_{0})-f^{*}}{epsilon ho }} ight)} , где R L ( x ) = max y max x ∗ ∈ X ∗ { ‖ y − x ∗ ‖ L : f ( y ) ⩽ f ( x ) } {displaystyle R_{L}(x)=max _{y}max _{x^{*}in X^{*}}{|y-x^{*}|_{L}:f(y)leqslant f(x)}} , f ∗ {displaystyle f^{*}} является оптимальным решением ( f ∗ = min x ∈ R n { f ( x ) } {displaystyle f^{*}=min _{xin R^{n}}{f(x)}} ), ρ ∈ ( 0 , 1 ) {displaystyle ho in (0,1)} является уровнем доверительной вероятности, а ϵ > 0 {displaystyle epsilon >0} является желаемой точностью, то P r o b ( f ( x k ) − f ∗ > ϵ ) ⩽ ρ {displaystyle Prob(f(x_{k})-f^{*}>epsilon )leqslant ho } .

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

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

f ( x ) = 1 2 x T ( 1 0 , 5 0 , 5 1 ) x − ( 1 , 5 1 , 5 ) x , x 0 = ( 0 0 ) T {displaystyle f(x)={ frac {1}{2}}x^{T}left({egin{array}{cc}1&0{,}5{,}5&1end{array}} ight)x-left({egin{array}{cc}1{,}5&1{,}5end{array}} ight)x,quad x_{0}=left({egin{array}{cc}0&0end{array}} ight)^{T}}

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

Можно естественным образом расширить алгоритм с просто координат на блоки координат. Предположим, что мы имеем пространство R 5 {displaystyle 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 {displaystyle {egin{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 координат.