Теоретическое исследование методов координатного спуска

Я готовлю некоторые учебные материалы по эвристике для оптимизации и изучаю методы координатного спуска. Здесь настройка представляет собой многовариантную функцию которую вы хотите оптимизировать. f имеет свойство, ограниченное какой-либо одной переменной, его легко оптимизировать. Таким образом, спуск координат происходит путем циклического перемещения по координатам, фиксации всех, кроме выбранной, и минимизации по этой координате. В конце концов, улучшения замедляются, и вы прекращаете работу.$f$$f$

Мой вопрос: есть ли теоретическое исследование методов координатного спуска, которое говорит о скоростях сходимости и свойствах которые делают метод эффективным, и так далее? Очевидно, я не ожидаю полностью общих ответов, но ответы, которые освещают случаи, когда эвристика преуспевает, были бы полезны.$f$

Кроме того: метод чередующейся оптимизации, используемый для -средств, можно рассматривать как пример спуска координат, а алгоритм Фрэнка-Вольфа, похоже, связан (но не является прямым примером структуры)$k$

(Редактировать заметки: я реорганизовал это после того, как взбесился на всю длину.)

Литература по координатному спуску может быть немного трудно отследить. Вот несколько причин для этого.

1. Многие из известных свойств координатных методов отражены в теоремах зонтиков для более общих методов спуска. Ниже приводятся два примера этого: быстрая сходимость при сильной выпуклости (справедливо для любого наискорейшего спуска) и общая сходимость этих методов (обычно приписываемая Зоутенджку).$l^p$

2. Наименование не является стандартным. Даже термин «крутой спуск» не является стандартным. Вы можете успешно погуглить любые термины «спуск по циклическим координатам», «спуск по координатам», «Gauss-Seidel», «Gauss-Southwell». использование не соответствует.

3. Циклический вариант редко получает особое упоминание. Вместо этого обычно обсуждается только лучший выбор координат. Но это почти всегда дает циклическую гарантию, хотя и с дополнительным фактором $n$ (числом переменных): это происходит потому, что большинство анализов конвергенции выполняются путем нижнего ограничения улучшения одного шага, и вы можете игнорировать дополнительные координаты. Также кажется сложным сказать что-то общее о том, что циклический покупает вас, поэтому люди просто лучше всего координируют свои действия, и обычно можно проверить фактор.$n$

Оцените при сильной выпуклости. В простейшем случае ваша целевая функция сильно выпуклая. Здесь все варианты градиентного спуска имеют скорость . Это доказано в книге Бойда и Ванденберге. Доказательство сначала дает результат для градиентного спуска, а затем использует эквивалентность нормы, чтобы дать результат для общего$\mathcal O(\ln (1/\epsilon))$ градиентного спуска.$l^p$

Ограничения. Без сильной выпуклости вы должны начать быть немного осторожнее. Вы ничего не сказали об ограничениях, и, следовательно, в целом, инфимум может быть недостижимым. Я кратко скажу на тему ограничений, что стандартный подход (с методами спуска) состоит в том, чтобы проецировать на свой набор ограничений каждую итерацию, чтобы поддерживать выполнимость, или использовать барьеры для накатывания ограничений в вашу целевую функцию. В случае с первым, я не знаю, как он играет с координатным спуском; в последнем случае он отлично работает с координатами спуска, и эти барьеры могут быть сильно выпуклыми.

Точнее говоря, к методам координат, а не к проецированию, многие люди просто заставляют обновление координат поддерживать осуществимость: это, например, в точности соответствует алгоритму Франка-Вольфа и его вариантам (т. Е. Его использованию для решения SDP).

Я также кратко отмечу, что алгоритм SMO для SVM можно рассматривать как метод спуска координат, при котором вы обновляете две переменные одновременно и поддерживаете технико-экономическое ограничение, пока вы это делаете. В этом методе выбор переменных является эвристическим, и поэтому гарантии на самом деле являются просто циклическими гарантиями. Я не уверен, если эта связь появляется в стандартной литературе; Я узнал о методе SMO из заметок курса Эндрю Нга и нашел их довольно чистыми.

$n$

$\mathcal O(\ln(1/\epsilon))$

Есть несколько недавних результатов по координатному спуску, я видел материал по arXiv. Кроме того, у luo & tseng есть несколько новых статей. но это главное.

$\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$$g$$(a_i)_1^m$$\lambda$$\exp(1/\epsilon^2)$$\mathcal O(1/\epsilon)$

Вопрос с точными обновлениями. Кроме того, очень часто бывает, что у вас нет закрытой формы обновления одной координаты. Или точное решение может просто не существовать. Но, к счастью, существует множество методов поиска строк, которые получают в основном те же гарантии, что и точное решение. Этот материал можно найти в стандартных текстах по нелинейному программированию, например, в упомянутых выше книгах Берцекаса или Носедаля и Райта.

Посмотрите на ваш второй абзац: когда они работают хорошо. Во-первых, многие из вышеупомянутых анализов для градиента работают для координатного спуска. Так почему бы не всегда использовать координаты спуска? Ответ заключается в том, что для многих задач, где применимо градиентное спуск, вы также можете использовать методы Ньютона, для которых можно доказать превосходную сходимость. Я не знаю, как получить преимущество Ньютона с помощью координатного спуска. Кроме того, высокая стоимость методов Ньютона может быть уменьшена с помощью обновлений Quasinewton (см., Например, LBFGS).

$l^0$$k$$k$$k$$k$$f$ которые позволяют быструю конвергенцию и хорошую разреженность (соответствует названию).

Предлагаю посмотреть здесь, мы проделали некоторую работу в этой области:

http://arxiv.org/abs/1107.2848

ура

Питер

Мы только что опубликовали статью по arXiv ( http://arxiv.org/abs/1201.1214 ), в которой доказываются общие нижние оценки для «статистических алгоритмов» для задач оптимизации, причем каждая «задача» имеет свою собственную нижнюю границу в зависимости от ее различные свойства.

Спуск по координатам (и почти все остальное, что мы можем придумать) можно рассматривать как статистический алгоритм в нашей структуре, так что, надеюсь, у этой статьи есть некоторые результаты, которые будут вам интересны.

Обратите внимание, что при оптимизации «скорость сходимости» обычно означает асимптотическое поведение. То есть ставка распространяется только на окрестности оптимальных решений. В этом смысле Ло и Ценг доказали линейную скорость сходимости для некоторых не сильно выпуклых целевых функций в статье «О сходимости метода координатного спуска для выпуклой дифференцируемой минимизации».

Не асимптотическая скорость сходимости, известная как «сложность итерации», как правило, более полезна для ограничения числа итераций алгоритмов минимизации. Для сильно выпуклых целевых функций итерационная сложность методов циклического координатного спуска уже показана в Границах ошибок Луо и Ценга и анализе сходимости возможных методов спуска: общий подход, если используется глобальная граница ошибки. Для не сильно выпуклых задач у нас есть несколько новых результатов в Сложности итерации возможных методов спуска для выпуклой оптимизации, В частности, мы показали сложность итераций для методов циклического координатного спуска в таких задачах, как двойственная форма SVM и методы Гаусса-Зейделя. Кроме того, результаты также охватывают другие возможные методы спуска, включая градиентный спуск и друзей.