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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Рандомизированный (блочный) координатный спуск — алгоритм оптимизации, популяризованный Нестеровым (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.