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

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

где разложен на блоков переменных/координат: и являются (простыми) выпуклыми функциями.

Пример (декомпозиция блоков): Если и , можно выбрать и .

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

  1. , где and является стандартной евклидовой нормой.

Алгоритм

править

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

 

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

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

 

для любого   и  , где   означает частную производную по переменной  .

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

    // Рандомизированный координатный спуск
    Input:   // стартовая точка
    Output:  
    set x := x_0
    for k := 1, ... do
        // обновляем координату   случайно 
          
    end for

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

править

Поскольку на итерациях алгоритма образуются случайные вектора, сложность следует отражать в числе итераций, необходимых для получения приближённого решения с высокой вероятностью. В статье Ричтарика и Такача[2] было доказано, что если  , где  ,   является оптимальным решением ( ),   является уровнем доверительной вероятности, а   является желаемой точностью, то  .

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

править

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

 

 

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

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

Можно естественным образом расширить алгоритм с просто координат на блоки координат. Предположим, что мы имеем пространство  . Это пространство имеет 5 координатных направлений, а именно  

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

См. также

править

Примечания

править
  1. Nesterov, 2010, с. 341–362.
  2. Richtárik, Takáč, 2011, с. 1–38.

Литература

править
  • Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization. — 2010. — Т. 22, вып. 2. — С. 341–362. — doi:10.1137/100802001.
  • Peter Richtárik, Martin Takáč. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. — 2011. — Т. 144, вып. 1–2. — С. 1–38. — doi:10.1007/s10107-012-0614-z. — arXiv:1107.2848.