Альтернированный градиентный спуск

Материал из MachineLearning.

Перейти к: навигация, поиск
Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Участник:Georgii Kvaratsкheliia 18 июля 2026

Промпт приводится полностью в Обсуждение:Альтернированный градиентный спуск


Содержание

Альтернированный градиентный спуск (англ. alternating gradient descent, также блочный координатный градиентный спуск, block coordinate gradient descent, BCGD) — семейство итеративных методов первого порядка для оптимизации функции, разбитой на блоки переменных, в которых на каждом шаге выполняется один (или несколько) шаг градиентного спуска по одному блоку переменных при фиксированных значениях остальных, после чего блоки меняются местами. Метод часто путают с более общим понятием альтернированной минимизации (alternating minimization, AM)[1] или блочным координатным спуском (block coordinate descent, BCD), в которых на каждом шаге блок минимизируется точно. Различие принципиально: точная блоковая минимизация гарантированно не увеличивает целевую функцию независимо от параметров, тогда как альтернированный градиентный спуск требует корректного выбора шага, но зато на порядки дешевле на итерацию, если точная подзадача не имеет замкнутого решения.

Метод лежит в основе ряда широко используемых инструментов анализа данных и машинного обучения: покоординатного спуска для регуляризованной линейной регрессии (Lasso, Elastic Net, пакет glmnet), алгоритма PALM для невыпуклой негладкой оптимизации (в том числе разреженной неотрицательной матричной факторизации), чередующегося обучения генератора и дискриминатора в генеративно-состязательных сетях (GAN), а также современных федеративных и распределённых алгоритмов восстановления матриц низкого ранга (AltGDmin).

Определение

Гладкий случай

Пусть переменная x=(x_1,\dots,x_N) разбита на N блоков, а f(x) — дифференцируемая функция, градиент которой по каждому блоку \nabla_i f липшицев с константой L_i. Альтернированный градиентный спуск порождает последовательность по правилу

x_i^{t+1} = x_i^{t} - \eta_i \, \nabla_i f\bigl(x_1^{t+1},\dots,x_{i-1}^{t+1},\, x_i^{t},\, x_{i+1}^{t},\dots,x_N^{t}\bigr), \qquad i = 1,\dots,N,

где шаг \eta_i \le 1/L_i выбирается так, чтобы гарантировать локальное убывание функции (по т. н. лемме о достаточном убывании для липшицева градиента). Порядок обновления блоков может быть циклическим (схема Гаусса — Зейделя, как выше), случайным (на каждой итерации выбирается один случайный блок) или жадным (выбирается блок с наибольшей нормой градиента — правило Гаусса — Саутвелла)[1].

Композитный (проксимальный) случай

На практике целевая функция часто имеет вид F(x) = f(x) + \sum_{i=1}^N g_i(x_i), где f гладкая, а g_i — негладкие, но «простые» покомпонентные слагаемые (например, \ell_1-регуляризация или индикатор ограничения). В этом случае градиентный шаг заменяется проксимальным градиентным шагом:

x_i^{t+1} = \operatorname{prox}_{\eta_i g_i}\bigl(x_i^{t} - \eta_i \, \nabla_i f(x^{t})\bigr),

где \operatorname{prox}_{\eta g}(z) = \arg\min_u \bigl\{ g(u) + \frac{1}{2\eta}\|u-z\|^2 \bigr\}. Именно эта схема была систематически изучена Ценгом и Юнем под названием «coordinate gradient descent method»[1] и стала стандартной формулировкой альтернированного градиентного спуска для негладких раздельных задач.

При N=1 метод вырождается в обычный (проксимальный) градиентный спуск; при точном решении подзадачи вместо одного шага метод превращается в точную альтернированную минимизацию — оба являются предельными случаями одной и той же схемы.

Мотивация: зачем нужен именно градиентный, а не точный блоковый шаг

  • Подзадача может не иметь замкнутого решения. Если f(x_i, x_{-i}) при фиксированных остальных блоках не является функцией специального вида (квадратичной, задачей проекции и т. п.), точная минимизация по блоку сама требует внутреннего итеративного решателя — например, блок весов одного слоя нейронной сети или блок параметров логистической регрессии. Один шаг градиентного спуска даёт почти бесплатный прогресс без вложенной оптимизации.
  • Разная кривизна по блокам. Если константы Липшица L_i сильно различаются между блоками (типичная ситуация для плохо обусловленных или разнородных по масштабу параметров), совместный градиентный спуск по всем переменным сразу с единым шагом \eta \le 1/\max_i L_i вынужден быть «осторожным» из-за самого жёсткого блока. Блоковая схема позволяет использовать собственный шаг \eta_i \le 1/L_i для каждого блока, эффективно устраняя эту проблему[1].
  • Дешевизна одной координаты градиента в «огромных» задачах. Для задач с очень большим числом переменных даже вычисление полного градиента может быть на порядки дороже, чем вычисление градиента по одному блоку (например, при разреженных данных или структурированных потерях). Рандомизированный покоординатный градиентный спуск был специально развит Нестеровым для таких «huge-scale» задач выпуклой оптимизации[1].
  • Плата за это — потеря автоматической монотонности. В отличие от точной блоковой минимизации, где убывание функции гарантировано геометрией подзадачи, при градиентном шаге функция убывает лишь при корректно подобранном шаге \eta_i \le 1/L_i; слишком большой шаг может привести к росту функции даже на одном блоке. Это главная практическая цена, которую платят за дешевизну итерации.

История

Общая идея блочной (покоординатной) оптимизации восходит к покоординатным схемам конца 1950-х годов, например к алгоритму Хилдрета для квадратичного программирования[1], а знаменитый контрпример Пауэлла (1973) показал, что даже точный циклический покоординатный спуск для гладких невыпуклых функций трёх и более переменных может не сходиться к стационарной точке[1] — этот результат заранее обозначил границы применимости и точных, и градиентных блоковых схем.

Специальная теория именно для градиентного (а не точного) блокового шага сформировалась в 2000-е — 2010-е годы. Ключевой работой стала статья Ценга и Юня (2009), которые предложили метод координатного градиентного спуска для суммы гладкой функции и раздельной негладкой части, доказали глобальную сходимость и — при выполнении локального условия липшицевой оценки погрешности (error bound) — линейную скорость сходимости без требования сильной выпуклости[1]. Ценг ранее (2001) также изучал сходимость блочного координатного спуска (в том числе для точных блоковых минимизаций) для недифференцируемых, но регулярных задач, заложив общую основу для последующих градиентных вариантов[1]. В 2012 году Нестеров дал систематический анализ рандомизированного покоординатного градиентного спуска для гладких и композитных выпуклых задач «огромного» масштаба, показав, в частности, что выбор блока с вероятностью, пропорциональной его константе Липшица, улучшает константу в оценке скорости сходимости[1]. Бек и Тетрушвили (2013) дополнили эту теорию строгим анализом циклического (а не только случайного) блочного координатного градиентного проецирования, установив глобальную сублинейную скорость сходимости и линейную — при сильной выпуклости[1].

Параллельно метод получил мощную невыпуклую теорию: алгоритм PALM (Proximal Alternating Linearized Minimization) Больте, Сабаха и Тебуля (2014) — это, по существу, альтернированный (проксимальный) градиентный спуск, для которого доказана глобальная сходимость всей последовательности к критической точке в невыпуклых негладких задачах при выполнении неравенства Куржики — Лоясевича, обобщающая более ранние результаты Аттуш, Больте, Редона и Свайтера[1][1][1]. В прикладной статистике метод приобрёл огромную популярность благодаря пакету glmnet Фридмана, Хасти и Тибширани (2010), реализующему (проксимальный) покоординатный спуск для путей регуляризации Lasso и Elastic Net[1]. В глубоком обучении неявным, но повсеместным примером альтернированного градиентного спуска стало обучение генеративно-состязательных сетей, где параметры дискриминатора и генератора обновляются попеременно шагами стохастического градиента по седловой (минимаксной) целевой функции[1]. Наконец, в 2020-е годы метод получил развитие в виде гибридных схем, сочетающих градиентный шаг по одному блоку с точной минимизацией по другому — таков алгоритм AltGDmin (Alternating Gradient Descent and Minimization) Васвани с соавторами (2021—2025) для федеративного и коммуникационно-эффективного восстановления матриц низкого ранга[1][1][1].

Сходимость

Выпуклый гладкий случай

Для циклического блочного координатного градиентного проецирования на выпуклой гладкой задаче Бек и Тетрушвили доказали глобальную сублинейную скорость сходимости O(1/k) по значению функции; при дополнительном условии сильной выпуклости — линейную (геометрическую) скорость сходимости[1].

Рандомизированный выбор блока

Для рандомизированного покоординатного градиентного спуска на выпуклых (и сильно выпуклых) задачах Нестеров установил ожидаемую скорость сходимости того же порядка, что и для полного градиентного спуска, но с константой, зависящей от суммы (а не максимума) блоковых констант Липшица L_i; при выборе блока с вероятностью, пропорциональной L_i, эта константа минимизируется, что часто даёт существенно лучшую практическую скорость по сравнению с циклическим порядком на плохо обусловленных задачах[1].

Жадный выбор блока

Альтернатива случайному выбору — жадное правило Гаусса — Саутвелла (выбор блока с наибольшей нормой частного градиента). Нутини, Ладраджи и Шмидт показали, что при определённых условиях регулярности (например, при ограниченности числа обусловленности по Гессе — Липшицу) жадный выбор доказуемо быстрее случайного, хотя требует вычисления или оценки градиентов по всем блокам на каждой итерации, что увеличивает стоимость итерации[1].

Композитные (проксимальные) задачи

Для суммы гладкой функции и раздельной негладкой части Ценг и Юнь доказали глобальную сходимость метода координатного градиентного спуска и, при выполнении локального липшицевого условия оценки погрешности, — линейную скорость сходимости; это условие выполняется, в частности, когда негладкая часть полиэдральна, а гладкая часть является (невыпуклой) квадратичной функцией или композицией сильно выпуклой функции с линейным отображением — класс, покрывающий задачи типа Lasso[1].

Невыпуклый негладкий случай

Для широкого класса полуалгебраических невыпуклых негладких задач машинного обучения алгоритм PALM обеспечивает сходимость всей последовательности итераций (а не только подпоследовательности) к критической точке функции, с явной оценкой скорости в терминах показателя неравенства Куржики — Лоясевича[1]. Это, по сути, наиболее сильная известная теоретическая гарантия для альтернированного градиентного спуска за пределами выпуклого случая.

Важная оговорка: седловые задачи

Все перечисленные гарантии относятся к задачам минимизации (пусть даже невыпуклым). Когда альтернированный градиентный спуск применяется к минимаксной (седловой) задаче — как при обучении GAN, где обновления дискриминатора и генератора имеют противоположные знаки цели, — классические аргументы о монотонном убывании единой функции неприменимы вовсе, поскольку такой единой функции, убывающей на обоих шагах, не существует. Сходимость в этом случае — предмет отдельной, существенно более сложной теории игр и седловой оптимизации, выходящей за рамки настоящей статьи[1].

Применения в машинном обучении

Регуляризованная линейная и логистическая регрессия (Lasso, Elastic Net)

Пакет glmnet и лежащий в его основе алгоритм используют циклический (проксимальный) покоординатный спуск для эффективного построения всего пути регуляризации Lasso и Elastic Net: для квадратичной функции потерь проксимальный шаг по одной координате имеет замкнутую форму мягкого порогового преобразования (soft-thresholding), что делает итерацию чрезвычайно дешёвой[1]. Это, пожалуй, самый массово используемый на практике инструмент, основанный на идее альтернированного градиентного/проксимального шага.

Матричная факторизация в рекомендательных системах

Для билинейной задачи R \approx UV^\top коллаборативной фильтрации существуют два принципиально разных способа оптимизации: точная альтернированная минимизация (Alternating Least Squares, ALS), решающая подзадачу по каждому фактору в замкнутой форме, и (стохастический) альтернированный градиентный спуск, обновляющий факторы небольшими шагами по отдельным наблюдениям. Корен, Белл и Волинский подробно обсуждают оба подхода как альтернативные стратегии оптимизации одной и той же целевой функции, отмечая, что стохастический градиентный вариант проще в реализации и часто быстрее на практике для очень больших разреженных наборов данных, тогда как ALS лучше параллелизуется и естественно работает с неявной обратной связью[1].

Разреженная неотрицательная матричная факторизация

Алгоритм PALM применяет линеаризованный (то есть градиентный, с проксимальной коррекцией на неотрицательность и разреженность) шаг к каждому из факторов W, H в задаче \min_{W\ge0,H\ge0}\|V-WH\|_F^2 + \lambda\|H\|_1, обеспечивая сходимость к критической точке — гарантию, которой не даёт классический мультипликативный алгоритм Ли и Сын[1].

Обучение генеративно-состязательных сетей

В стандартной формулировке GAN генератор G и дискриминатор D обучаются попеременными шагами стохастического градиента по минимаксной целевой функции \min_G \max_D \mathbb{E}\bigl[\log D(x)\bigr] + \mathbb{E}\bigl[\log(1-D(G(z)))\bigr][1]. Формально это альтернированный градиентный спуск (точнее, спуск-подъём) по двум блокам параметров, однако, как отмечено выше, седловой характер задачи означает, что классические гарантии монотонного убывания и сходимости, справедливые для задач минимизации, здесь не действуют напрямую — это одна из причин практической нестабильности обучения GAN.

Распределённое и федеративное восстановление матриц низкого ранга

Гибридная схема AltGDmin применяет один (проецированный) градиентный шаг к «глобальному» фактору матрицы низкого ранга — что требует передачи между узлами лишь компактных промежуточных величин, а не полных градиентов, — и точную минимизацию к «локальному» фактору, которая распадается на независимые дешёвые подзадачи по столбцам. Это позволяет достичь почти той же выборочной сложности, что и полностью точная альтернированная минимизация, при существенно меньшей коммуникационной стоимости — что критично для федеративного обучения[1][1][1].

Оптимизация «огромного масштаба»

Для линейных моделей с очень большим числом признаков (например, в задачах с миллионами разреженных признаков) рандомизированный покоординатный градиентный спуск позволяет работать напрямую с отдельными координатами градиента, избегая дорогостоящего вычисления полного градиента на каждой итерации — именно эта мотивация лежала в основе анализа Нестерова[1].

Ограничения и практические аспекты

  • Настройка шага. В отличие от точной альтернированной минимизации, где монотонное убывание не требует подбора параметров, альтернированный градиентный спуск требует знания (или оценки) блоковых констант Липшица L_i либо процедуры линейного поиска; неверно подобранный шаг может свести на нет теоретические гарантии.
  • Порядок обновления блоков. Циклический порядок прост в реализации, но в невыпуклом нерегулярном случае в принципе подвержен патологиям, аналогичным контрпримеру Пауэлла; случайный порядок допускает более чистую теорию сходимости в ожидании[1], а жадный порядок может быть быстрее по числу итераций ценой более дорогой итерации[1].
  • Экономия против точности за итерацию. Градиентный шаг всегда дешевле точной блоковой минимизации, но даёт меньший гарантированный прогресс за итерацию; выбор между «дорогой точной» и «дешёвой градиентной» блоковой схемой (или гибридом, как в AltGDmin) — инженерный компромисс, зависящий от того, насколько дорога подзадача и насколько ограничена коммуникация между вычислительными узлами.
  • Неприменимость классических гарантий к седловым задачам. Как показывает пример обучения GAN, при переходе от задач минимизации к минимаксным задачам стандартная теория сходимости альтернированного градиентного спуска (основанная на убывании единой целевой функции) не переносится автоматически и требует отдельного анализа.
  • Связь с проксимальными методами. Формально альтернированный градиентный спуск с проксимальной коррекцией негладкой части — это блочная версия проксимального градиентного метода; вся теория ускорения (моменты Нестерова, адаптивные шаги) для проксимального градиентного спуска в целом переносится на блочный случай с соответствующими оговорками.

См. также


Литература

  • Tseng P., Yun S. A coordinate gradient descent method for nonsmooth separable minimization // Mathematical Programming. — 2009. — Т. 117. — С. 387–423.
  • Beck A., Tetruashvili L. On the convergence of block coordinate descent type methods // SIAM Journal on Optimization. — 2013. — Т. 23. — № 4. — С. 2037–2060.
  • Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM Journal on Optimization. — 2012. — Т. 22. — № 2. — С. 341–362.
  • Wright S. J. Coordinate descent algorithms // Mathematical Programming. — 2015. — Т. 151. — № 1. — С. 3–34.
  • Bolte J., Sabach S., Teboulle M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems // Mathematical Programming. — 2014. — Т. 146. — С. 459–494.
  • Friedman J., Hastie T., Tibshirani R. Regularization paths for generalized linear models via coordinate descent // Journal of Statistical Software. — 2010. — Т. 33. — № 1. — С. 1–22.
  • Bertsekas D. P. Nonlinear Programming. — 2-е изд.. — Athena Scientific, 1999.
  • Beck A. First-Order Methods in Optimization. — SIAM, 2017.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D1%8C%D1%82%D0%B5%D1%80%D0%BD%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D1%83%D1%81%D0%BA»
Личные инструменты