Координата против градиентного спуска

Мне было интересно, каковы разные варианты использования для двух алгоритмов, Coordinate Descent и Gradient Descent .

Я знаю, что у координатного спуска есть проблемы с негладкими функциями, но он используется в популярных алгоритмах, таких как SVM и LASSO.

Однако градиентный спуск, по-моему, используется более широко, особенно при возрождении ANN и для многих других задач машинного обучения.

Мой вопрос: какой тип проблем подходит для одной, но не для другой, и в этом отношении, что делает согласование по координатному спуску для SVM и LASSO, но подходит для градиентного спуска для ANN?

Как выбрать между двумя при выборе алгоритма оптимизации?

Я думаю, что обычно дело в том, насколько просто / легко определить градиент гладкой части функции и / или проксимального оператора штрафа.

Иногда гораздо проще найти точное решение проблемы в случае с одной единственной переменной (или блоком или переменными), чем вычислить его для всех переменных одновременно. В других случаях просто слишком дорого вычислять градиент по сравнению с отдельными производными. Кроме того, сходимость координатного спуска такая же, как для ista, $1/k^2$ , где $k$ - количество итераций, но иногда она может работать лучше по сравнению как с ISTA, так и с FISTA, см., Например, http: //statweb.stanford. Edu / ~ TIBS / сравнение.txt .

Такие вещи будут влиять на выбор спуска координат, например, ISTA / FISTA.

Спуск по координатам обновляет один параметр за раз, в то время как градиентный спуск пытается обновить все параметры одновременно.

Трудно точно указать , когда один алгоритм будет работать лучше, чем другой. Например, я был очень потрясен, узнав, что координатный спуск был для LASSO современным уровнем. И я был не единственным; см. слайд 17 .

С учетом сказанного, есть некоторые особенности, которые могут сделать проблему более корректируемой для координации спуска:

(1) Быстрые условные обновления. Если по какой-то причине проблема позволяет индивидуально оптимизировать параметры очень быстро, спуск по координатам может использовать это. Например, можно обновить некоторые параметры, используя только подмножество данных, что значительно снижает вычислительные затраты на эти обновления. Другой случай, если есть решение в закрытой форме для отдельного параметра, зависящее от значений всех других параметров.

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

К сожалению, для большинства задач (2) не выполняется, поэтому редко, когда спуск по координатам дает хорошие результаты по сравнению с альтернативными алгоритмами. Я считаю, что причина того, что он работает хорошо для LASSO, заключается в том, что есть много приемов, которые можно использовать для выполнения условия (1).

$\alpha$

Я понимаю, что это старый вопрос и на него есть очень хорошие ответы. Я хотел бы поделиться некоторым практическим личным опытом.

$k$

• Все вероятности должны быть положительными.
• Все элементы набора вероятностей должны суммировать до одного

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

Существует множество преобразований, которые вы можете применить к своей задаче, чтобы удовлетворить ограничения, чтобы обеспечить градиентный спуск. Тем не менее, если вы ищете самый простой и ленивый способ реализовать это, тогда вам нужно перейти к координатному спуску:

$p_i$

• $p_i^{k+1} = p_i^{k} - \eta \frac{\partial J}{\partial p_i}$
• $p_i = \min(\max(p_i,0),1)$
• $\mathbf{P}^{j+1} = \mathbf{P}^j \cdot \frac{1}{\sum_{i=1}^n p_i}$

Для таких, как я, которые работают в Python, это обычно означает, что я должен использовать дополнительный цикл for, который весьма негативно влияет на производительность. Градиентный спуск позволяет мне использовать Numpy, который оптимизирован по производительности. С его помощью можно получить очень хорошую скорость, однако это невозможно сделать с помощью координатного спуска, поэтому я обычно использую некоторую технику преобразования.

Таким образом, на самом деле вывод состоит в том, что спуск по координатам является самым простым вариантом для работы с очень строгими ограничениями, такими как параметр скорости в распределении Пуассона. Если он становится отрицательным, вы жалуетесь на код.

Я надеюсь, что это добавило немного понимания.