Альтернированная минимизация

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

(Различия между версиями)

Текущая версия

Альтернированная минимизация (англ. alternating minimization, AM; при числе блоков переменных $N>2$ также называется блочным координатным спуском, block coordinate descent, BCD) — семейство итеративных методов оптимизации, в которых на каждом шаге целевая функция точно минимизируется по одной группе переменных («блоку») при фиксированных значениях остальных блоков, после чего роли блоков меняются местами. Метод особенно эффективен для задач, невыпуклых по совокупности всех переменных, но выпуклых (и часто разрешимых в замкнутой форме) по каждому блоку в отдельности — такие функции называют бивыпуклыми (biconvex) при двух блоках и мультивыпуклыми (multiconvex) при большем их числе[1].

От родственного метода — альтернированного градиентного спуска, где вместо точной минимизации по блоку выполняется один (или несколько) шагов градиентного метода, — альтернированную минимизацию отличает ключевое свойство: монотонное убывание целевой функции гарантировано самой геометрией задачи и не требует подбора шага обучения. Плата за это — подзадача на каждом шаге должна быть точно разрешима, что накладывает структурные ограничения на класс решаемых задач. Настоящая статья посвящена именно точному блоковому шагу; читателя, которого интересует градиентный вариант и его отдельная теория сходимости, следует отправить к статье «Альтернированный градиентный спуск».

Идея точной блоковой минимизации лежит в основе многих базовых алгоритмов машинного обучения и анализа данных: метода k-means, EM-алгоритма, чередующихся наименьших квадратов (ALS) для рекомендательных систем, точных вариантов неотрицательной матричной факторизации, восстановления матриц низкого ранга, решения фазовой задачи и вычисления оптимального транспорта через алгоритм Синхорна.

Содержание

1 Формальная постановка
- 1.1 Двухблочный случай
- 1.2 N-блочный случай
2 Мотивация и геометрическая интуиция
3 История
4 Сходимость
5 Применения в машинном обучении и анализе данных
6 Ограничения и практические аспекты
7 См. также
8 Примечания
9 Литература

Формальная постановка

Двухблочный случай

Пусть требуется решить задачу

$\min_{x \in X,\, y \in Y} F(x,y)$

для функции $F: X \times Y \to \mathbb{R}$ . Альтернированная минимизация порождает последовательность $(x_t, y_t)$ по правилу

$x_{t+1} = \arg\min_{x \in X} F(x, y_t), \qquad y_{t+1} = \arg\min_{y \in Y} F(x_{t+1}, y).$

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

N-блочный случай

Обобщение на $N$ блоков $x=(x_1,\dots,x_N)$ задаётся циклом

$x_i^{t+1} = \arg\min_{x_i} \; F\bigl(x_1^{t+1},\dots,x_{i-1}^{t+1},\, x_i,\, x_{i+1}^{t},\dots,x_N^{t}\bigr), \qquad i=1,\dots,N,$

где уже обновлённые блоки используются немедленно (схема Гаусса — Зейделя); альтернативная схема Якоби использует во всех подзадачах значения блоков из предыдущей итерации целиком, что допускает параллельное обновление ценой более медленной сходимости.

Терминологическое замечание: исторически термин «альтернированная минимизация» закреплён за случаем $N=2$ — именно для двух распределений его вводили Чисар и Туснади[2], тогда как для $N\ge 3$ блоков в англоязычной литературе почти всегда говорят о block coordinate descent. Различие не только терминологическое: как показано ниже, свойства сходимости для $N=2$ и $N\ge3$ принципиально различаются.

Мотивация и геометрическая интуиция

Почему именно точная блоковая минимизация, а не совместная оптимизация по всем переменным сразу?

Подзадачи оказываются выпуклыми и разрешимыми в замкнутой форме. Классический пример — билинейная параметризация $M \approx UV^\top$ : функция $\|M-UV^\top\|_F^2$ невыпукла по паре $(U,V)$ совместно (что видно уже из неединственности решения с точностью до $U\to UQ,\ V\to VQ^{-\top}$ для обратимой $Q$ ), но при фиксированном $V$ строго выпукла и квадратична по $U$ , то есть решается через нормальные уравнения без вложенного итеративного цикла.
Монотонность — «бесплатное» следствие геометрии, а не выбора параметров. Поскольку каждый шаг — точный минимум по подмножеству переменных, значение функции не может возрасти:

$F(x_t,y_t) \ge F(x_{t+1}, y_t) \ge F(x_{t+1}, y_{t+1}) \ge \dots$

Если $F$ ограничена снизу, эта монотонно невозрастающая последовательность сходится к некоторому $F^*$ . В отличие от градиентного варианта, здесь не нужно оценивать константы Липшица или подбирать шаг — убывание гарантировано геометрией подзадачи. Важно, однако, что из сходимости значений не следует автоматически сходимость самих итераций к стационарной точке — это требует дополнительных условий регулярности (см. раздел «Сходимость»).

Геометрически метод удобно представлять как движение по «ступенькам» вдоль линий уровня $F$ . Частный, но принципиальный пример такой геометрии — метод чередующихся проекций фон Неймана для поиска точки в пересечении двух выпуклых множеств $C_1 \cap C_2$ : если положить $F(x,y)=\|x-y\|^2$ с ограничениями $x\in C_1$ , $y\in C_2$ , то альтернированная минимизация в точности сводится к попеременному проецированию $x_{t+1}=P_{C_1}(y_t)$ , $y_{t+1}=P_{C_2}(x_{t+1})$ [3].

История

Истоки метода восходят к методу чередующихся проекций фон Неймана (конец 1940-х годов)[3] и к покоординатным схемам конца 1950-х, например к алгоритму Хилдрета для квадратичного программирования[4].

Ключевой теоретический вклад внесла работа Имре Чисара и Габора Туснади 1984 года «Information geometry and alternating minimization procedures», формализовавшая метод на языке информационной геометрии: авторы доказали «трёхточечное свойство» (three-point property), гарантирующее сходимость при выпуклости обоих множеств, и показали, что классический EM-алгоритм Демпстера, Лэйрда и Рубина (1977) является частным случаем AM для минимизации дивергенции Кульбака — Лейблера между эмпирическим распределением данных и параметрическим семейством модели[2,5]. Годом ранее, в 1973 году, Майкл Пауэлл опубликовал контрпример, показавший, что точный циклический покоординатный спуск для гладких невыпуклых функций трёх и более переменных может не сходиться к стационарной точке, а «застревать» на предельном цикле, где градиент отделён от нуля[6] — этот результат на десятилетия обозначил границы применимости AM при $N\ge3$ .

С 2000-х годов теория обогатилась инструментами для негладких и невыпуклых задач: Ценг (2001) дал условия сходимости блочного координатного спуска для недифференцируемых, но регулярных задач[7], а серия работ Аттуш, Больте, Редона и Свайтера установила глобальную сходимость проксимальной альтернированной минимизации к критической точке через теорию неравенства Куржики — Лоясевича для широкого класса невыпуклых негладких задач[8,9]. Параллельно теоретическая информатика дала первые гарантии полиномиальной сходимости точной AM к глобальному минимуму для конкретных невыпуклых задач машинного обучения: восстановления матриц низкого ранга (Jain, Netrapalli, Sanghavi, 2013; Hardt, 2014) и фазовой задачи (Netrapalli, Jain, Sanghavi, 2013)[10,11,12]. В 2020-е годы у метода появились коммуникационно-эффективные гибриды с градиентным шагом (AltGDmin), которым посвящена отдельная статья «Альтернированный градиентный спуск»[13].

Сходимость

Монотонность и её пределы

Как отмечено выше, последовательность значений функции монотонно не возрастает и сходится к некоторому $F^*$ , если $F$ ограничена снизу. Из этого факта, однако, не следует ни сходимость самих итераций к точке, ни то, что предельная точка является хотя бы локальным минимумом совместной задачи.

Двухблочный выпуклый случай

Если $F$ совместно выпукла (а не только по каждому блоку в отдельности) и дифференцируема, блочная минимизация по двум блокам сходится к глобальному минимуму при мягких условиях компактности множества уровня[14].

N ≥ 3 блока: контрпример Пауэлла

Для $N\ge3$ блоков даже гладкая невыпуклая функция без ограничений может порождать циклический покоординатный спуск, не сходящийся к стационарной точке, — контрпример Пауэлла показывает именно это[6]. Достаточное условие, устраняющее патологию, — единственность блокового минимума на каждом шаге (строгая выпуклость подзадач) вместе с непрерывностью соответствующих отображений; при этих условиях любая предельная точка последовательности является стационарной для совместной задачи[14].

Невыпуклые негладкие задачи: неравенство Куржики — Лоясевича

Для широкого класса задач, включающего практически все функции потерь машинного обучения (полуалгебраические, аналитические функции), Аттуш, Больте, Редон и Свайтер доказали глобальную сходимость всей последовательности итераций проксимальной альтернированной минимизации к критической точке, используя неравенство Куржики — Лоясевича (KŁ)[8,9]. Эта теория — общая основа и для точного блокового шага, и для его линеаризованных (градиентных) вариантов, которым посвящена сибling-статья.

Локальная линейная сходимость к глобальному минимуму

Для ряда невыпуклых задач машинного обучения — восстановления матрицы низкого ранга по неполным или случайным линейным измерениям, фазовой задачи — доказана линейная (геометрическая) сходимость точной AM именно к истинному глобальному решению, а не просто к произвольной стационарной точке. Джайн, Нетрапалли и Сангхави (2013) первыми установили это для восстановления матриц при спектральной инициализации и условии некогерентности (incoherence)[10]; Хардт (2014) заметно ослабил требования к числу наблюдений, связав анализ AM со степенным методом вычисления сингулярных векторов[11]; Нетрапалли, Джайн и Сангхави (2013) дали аналогичный результат для фазовой задачи с гауссовыми измерениями[12]. Принципиальная особенность этих результатов: гарантия относится к конкретной задаче со специфичными вероятностными предположениями о данных, а не к произвольной невыпуклой AM «в общем случае».

Применения в машинном обучении и анализе данных

Метод k-means

k-means Ллойда — хрестоматийный пример точной AM с дискретным первым блоком: на шаге присвоения точки закрепляются за ближайшим центроидом (точная минимизация по дискретной переменной принадлежности кластеру), на шаге обновления центроиды пересчитываются как средние по кластеру (точная минимизация суммы квадратов расстояний по непрерывной переменной)[15,16]. Оба шага строго уменьшают суммарную внутрикластерную дисперсию, что даёт сходимость к локальному минимуму за конечное число итераций (число возможных разбиений конечно).

EM-алгоритм

Как показали Чисар и Туснади, EM-алгоритм — это AM для двойной минимизации дивергенции Кульбака — Лейблера: E-шаг точно минимизирует по «вспомогательному» распределению скрытых переменных, M-шаг — точно по параметрам модели[2,5].

ALS для рекомендательных систем

В коллаборативной фильтрации с матричной факторизацией $R\approx UV^\top$ задача

$\min_{U,V}\sum_{(i,j)\in\Omega}\bigl(R_{ij}-U_i^\top V_j\bigr)^2+\lambda\bigl(\|U\|_F^2+\|V\|_F^2\bigr)$

решается методом чередующихся наименьших квадратов (Alternating Least Squares, ALS): при фиксированном $V$ каждая строка $U_i$ находится в замкнутой форме

$U_i=\Bigl(\sum_{j:(i,j)\in\Omega}V_jV_j^\top+\lambda I\Bigr)^{-1}\sum_{j:(i,j)\in\Omega}R_{ij}V_j,$

и аналогично для $V_j$ . Именно точная (а не градиентная) разрешимость подзадачи сделала ALS одним из ключевых компонентов алгоритмов-победителей Netflix Prize благодаря естественной параллелизуемости независимых подзадач по строкам[17,18].

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

Для задачи $\min_{W\ge0,H\ge0}\|V-WH\|_F^2$ точный блоковый шаг реализуется методом ANLS (Alternating Nonnegativity-Constrained Least Squares): каждая подзадача — выпуклая задача с ограничениями неотрицательности, решаемая методом активного набора. В отличие от классических мультипликативных правил обновления Ли и Сын, которые дают лишь приближённое (не точное) блоковое убывание, ANLS обеспечивает точную блоковую минимизацию и, как правило, более надёжную сходимость к стационарной точке[19,20].

Восстановление матриц низкого ранга

Для восстановления неизвестной матрицы $X^\star=UV^\top$ низкого ранга по частичным наблюдениям (matrix completion) или случайным линейным измерениям (matrix sensing) точная AM с бивыпуклой параметризацией — один из наиболее изученных невыпуклых алгоритмов в теоретическом машинном обучении, с гарантиями полиномиальной и даже линейной сходимости к истинному решению при спектральной инициализации[10,11].

Фазовая задача

В фазовой задаче требуется восстановить вектор $x$ по измерениям модулей $y=|Ax|$ без информации о фазе. Классический алгоритм чередующихся проекций Джерчберга — Сакстона попеременно точно оценивает недостающую фазу и точно решает задачу наименьших квадратов относительно $x$ ; строгий анализ геометрической сходимости этой схемы для гауссовых измерений дали Нетрапалли, Джайн и Сангхави[12].

Оптимальный транспорт и алгоритм Синхорна

Энтропийно регуляризованная задача оптимального транспорта имеет гладкую вогнутую двойственную задачу по паре потенциалов $(f,g)$ ; алгоритм Синхорна, ставший стандартом благодаря вычислительной работе Кутюри (2013), — это точный блочный координатный подъём (alternating maximization) по этой двойственной паре, реализуемый как попеременное точное масштабирование строк и столбцов матрицы $K=\exp(-C/\varepsilon)$ [21].

Другие инженерные применения

Точная AM применяется и за пределами «классического» ML: например, в проектировании гибридных (аналого-цифровых) прекодеров для систем связи миллиметрового диапазона (mmWave MIMO) задача сводится к невыпуклой матричной факторизации с ограничениями постоянного модуля, решаемой попеременной точной минимизацией по цифровому и аналоговому прекодерам[22]. Более общая теория блочного координатного спуска для мультивыпуклых задач с приложениями к тензорным разложениям и восполнению тензоров дана Сюем и Инем[1].

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

Чувствительность к инициализации. Почти все интересные приложения AM в машинном обучении невыпуклы, и метод в общем случае сходится лишь к локальному минимуму или седловой точке; теоретические гарантии глобальной сходимости для матричной факторизации и фазовой задачи опираются на специальную спектральную инициализацию, а не на случайный старт[10,12].
Порядок обновления блоков. Циклический порядок обычно даёт более быструю практическую сходимость, чем параллельный (Якоби), но при $N\ge3$ блоках теоретически может не сходиться (контрпример Пауэлла); случайный выбор блока допускает более чистую теорию сходимости.
Стоимость точной подзадачи. Главное структурное ограничение точной AM — подзадача должна быть разрешима в замкнутой форме или очень дёшево (иначе выигрыш по сравнению с полной совместной оптимизацией теряется). Когда это не так, разумной альтернативой становится альтернированный градиентный спуск или гибридные схемы вроде AltGDmin, сочетающие точный шаг по одному блоку и градиентный — по другому; подробнее см. статью «Альтернированный градиентный спуск».
Соотношение с ADMM. Метод чередующихся направлений множителей (ADMM) можно рассматривать как AM, применённую к расширенному лагранжиану задачи с ограничениями типа равенства; в отличие от «чистой» AM, ADMM явно поддерживает двойственные переменные, что улучшает сходимость для задач со связывающими блоки ограничениями, но требует настройки штрафного параметра.

См. также

Примечания

Xu Y., Yin W. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion // SIAM Journal on Imaging Sciences. — 2013. — Т. 6, № 3. — С. 1758–1789.
Csiszár I., Tusnády G. Information geometry and alternating minimization procedures // Statistics & Decisions. — 1984. — Вып. Suppl. Issue 1. — С. 205–237.
Bauschke H. H., Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. — Springer, 2011. (глава о методе чередующихся проекций фон Неймана)
Hildreth C. A quadratic programming procedure // Naval Research Logistics Quarterly. — 1957. — Т. 4, № 1. — С. 79–85.
Dempster A. P., Laird N. M., Rubin D. B. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society: Series B. — 1977. — Т. 39, № 1. — С. 1–38. DOI:10.1111/j.2517-6161.1977.tb01600.x.
Powell M. J. D. On search directions for minimization algorithms // Mathematical Programming. — 1973. — Т. 4. — С. 193–201. DOI:10.1007/BF01584660.
Tseng P. Convergence of a block coordinate descent method for nondifferentiable minimization // Journal of Optimization Theory and Applications. — 2001. — Т. 109, № 3. — С. 475–494.
Attouch H., Bolte J., Redont P., Soubeyran A. Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka–Łojasiewicz inequality // Mathematics of Operations Research. — 2010. — Т. 35, № 2. — С. 438–457.
Attouch H., Bolte J., Svaiter B. F. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods // Mathematical Programming. — 2013. — Т. 137, № 1-2. — С. 91–129.
Jain P., Netrapalli P., Sanghavi S. Low-rank matrix completion using alternating minimization // Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC). — 2013. — С. 665–674. DOI:10.1145/2488608.2488693.
Hardt M. Understanding alternating minimization for matrix completion // Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS). — 2014. — С. 651–660. DOI:10.1109/FOCS.2014.75.
Netrapalli P., Jain P., Sanghavi S. Phase retrieval using alternating minimization // Advances in Neural Information Processing Systems 26 (NIPS 2013). — 2013. — С. 2796–2804.
Vaswani N. Efficient federated low rank matrix recovery via alternating GD and minimization: a simple proof // IEEE Transactions on Information Theory. — 2024. DOI:10.1109/TIT.2024.3365795.
Bertsekas D. P. Nonlinear Programming. — 2-е изд. — Athena Scientific, 1999.
Lloyd S. P. Least squares quantization in PCM // IEEE Transactions on Information Theory. — 1982. — Т. 28, № 2. — С. 129–137. DOI:10.1109/TIT.1982.1056489. (результат распространялся как техотчёт Bell Labs с 1957 года)
MacQueen J. Some methods for classification and analysis of multivariate observations // Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. — 1967. — Т. 1. — С. 281–297.
Koren Y., Bell R., Volinsky C. Matrix factorization techniques for recommender systems // Computer. — 2009. — Т. 42, № 8. — С. 30–37. DOI:10.1109/MC.2009.263.
Zhou Y., Wilkinson D., Schreiber R., Pan R. Large-scale parallel collaborative filtering for the Netflix prize // Algorithmic Aspects in Information and Management (AAIM). — 2008. — С. 337–348.
Lee D. D., Seung H. S. Learning the parts of objects by non-negative matrix factorization // Nature. — 1999. — Т. 401. — С. 788–791. DOI:10.1038/44565.
Kim H., Park H. Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method // SIAM Journal on Matrix Analysis and Applications. — 2008. — Т. 30, № 2. — С. 713–730.
Cuturi M. Sinkhorn distances: lightspeed computation of optimal transport // Advances in Neural Information Processing Systems 26 (NIPS 2013). — 2013. — С. 2292–2300. arXiv:1306.0895.
Yu X., Shen J.-C., Zhang J., Letaief K. B. Alternating minimization algorithms for hybrid precoding in millimeter wave MIMO systems // IEEE Journal of Selected Topics in Signal Processing. — 2016. — Т. 10. — С. 485–500.

Литература

Bertsekas D. P. Nonlinear Programming. — 2-е изд. — Athena Scientific, 1999.
Beck A. First-Order Methods in Optimization. — SIAM, 2017.
Bauschke H. H., Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. — Springer, 2011.
Csiszár I., Tusnády G. Information geometry and alternating minimization procedures // Statistics & Decisions. — 1984. — Вып. Suppl. Issue 1. — С. 205–237.
Jain P., Netrapalli P., Sanghavi S. Low-rank matrix completion using alternating minimization // STOC. — 2013. — С. 665–674.
Attouch H., Bolte J., Svaiter B. F. Convergence of descent methods for semi-algebraic and tame problems // Mathematical Programming. — 2013. — Т. 137. — С. 91–129.
Koren Y., Bell R., Volinsky C. Matrix factorization techniques for recommender systems // Computer. — 2009. — Т. 42, № 8. — С. 30–37.

Источник — «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%D0%B0%D1%8F_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»