Interested Article - Координатный спуск

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

Описание

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

,

итерация определяет из путём итеративного решения задач оптимизации от одной переменной

для каждой переменной вектора для от 1 до .

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

При осуществлении линейного поиска на каждой итерации получаем

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

Процесс работы алгоритма продемонстрирован ниже.

Дифференцируемый случай

В случае непрерывной дифференцируемости функции F алгоритм координатного спуска можно изложить кратко как :

  • Выбираем начальный вектор x .
  • Пока не будет достигнут уровень сходимости или не будет сделано фиксированное число итерации:
    • Выбираем индекс i из промежутка от 1 до n .
    • Выбираем размер шага α .
    • Заменяем на .

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

Ограничения

Координатный спуск имеет две проблемы. Одна из них заключается в наличии негладкой функции от нескольких переменных. Рисунок показывает, что итерации координатного спуска могут упереться в нестационарную точку , если кривые уровня функции не гладкие. Предположим, что алгоритм оказался в точке (-2, -2) . Тогда имеется два направления, параллельные осям, по которым следовало бы делать очередной шаг. Они показаны красными стрелками. Однако любой шаг в этих двух направлениях приведёт к росту значения функции (предполагается, что решается задача минимизации), так что алгоритм не сделает ни одного шага, хотя два шага вместе привели бы алгоритм ближе к оптимуму. Хотя данный пример показывает, что координатный спуск не обязательно приводит к оптимальному решению, можно показать формальную сходимость при нормальных условиях .

Другая проблема – трудности в распараллеливании. Поскольку природа координатного спуска заключается в цикле по направлениям и минимизации функции по каждому координатному направлению, координатный спуск не является очевидным кандидатом для распараллеливания. Недавние исследования показали, что распараллеливание можно использовать для координатного спуска при некоторых специальных приёмах .

Приложения

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

См. также

Примечания

  1. , с. 3–34.
  2. . Дата обращения: 6 февраля 2022. 6 февраля 2022 года.
  3. , с. 187–208.
  4. , с. 1745–1759.
  5. , с. 166–175.
  6. , с. 2:1–2:12.
  7. , с. 534–548.
  8. , с. 161–175.
  9. , с. 4526–4544.
  10. , с. 963–72.
  11. , с. 408.
  12. , с. 1064.
  13. , с. 341–362.

Литература

  • Stephen J. Wright. Coordinate descent algorithms // Mathematical Programming. — 2015. — Т. 151 , вып. 1 . — doi : . — arXiv : .
  • Spall J. C. Cyclic Seesaw Process for Optimization and Identification // Journal of Optimization Theory and Applications. — 2012. — Т. 154 , вып. 1 . — doi : .
  • Zheng J., Saquib S. S., Sauer K., Bouman C. A. Parallelizable Bayesian tomography algorithms with rapid, guaranteed convergence // IEEE Transactions on Image Processing. — 2000. — Т. 9 , вып. 10 . — ISSN . — doi : . — Bibcode : . — .
  • Fessler J. A., Ficaro E. P., Clinthorne N. H., Lange K. Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction // IEEE Transactions on Medical Imaging. — 1997. — Т. 16 , вып. 2 . — ISSN . — doi : . — .
  • Xiao Wang, Amit Sabne, Sherman Kisner, Anand Raghunathan, Charles Bouman, Samuel Midkiff. . — Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. — New York, NY, USA: ACM, 2016. — ISBN 9781450340922 . — doi : .
  • Ken Sauer, Charles Bouman. // IEEE Transactions on Signal Processing. — 1993. — Февраль ( т. 41 , вып. 2 ). — doi : . — Bibcode : .
  • Zhou Yu, Jean-Baptiste Thibault, Charles Bouman, Ken Sauer, Jiang Hsieh. // IEEE Transactions on Image Processing. — 2011. — Январь ( т. 20 , вып. 1 ). — doi : . — Bibcode : . — .
  • Jean-Baptiste Thibault, Ken Sauer, Charles Bouman, Jiang Hsieh. // Medical Physics. — 2007. — Ноябрь ( т. 34 , вып. 11 ). — doi : . — Bibcode : . — .
  • Canutescu A.A., Dunbrack R.L. Cyclic coordinate descent: A robotics algorithm for protein loop closure. // Protein Science. — 2003. — Т. 12 , вып. 5 . — doi : . — . — PMC .
  • Hsieh C. J., Chang K. W., Lin C. J., Keerthi S. S., Sundararajan S. A dual coordinate descent method for large-scale linear SVM // Proceedings of the 25th international conference on Machine learning - ICML '08. — 2008. — ISBN 9781605582054 . — doi : .
  • Hsieh C. J., Dhillon I. S. Fast coordinate descent methods with variable selection for non-negative matrix factorization // . — 2011. — ISBN 9781450308137 . — doi : .
  • Yurii Nesterov. // SIAM J. Optim.. — 2012. — Т. 22 , вып. 2 . — doi : .
  • Bezdek J. C., Hathaway R. J., Howard R. E., Wilson C. A., Windham M. P. // Journal of Optimization Theory and Applications. — Kluwer Academic/Plenum Publishers, 1987. — Т. 54 , вып. 3 . — P. 471–477. — doi : .
  • Dimitri P. Bertsekas,. Nonlinear Programming. — Second Edition. — Belmont, Massachusetts: Athena Scientific, 1999. — ISBN 1-886529-00-0 .
  • Zhiquan Luo, Tseng P. // Journal of Optimization Theory and Applications. — Kluwer Academic/Plenum Publishers, 1992. — Т. 72 , вып. 1 . — P. 7–35. — doi : . .
  • TongTong Wu, Kenneth Lange. Coordinate descent algorithms for Lasso penalized regression // The Annals of Applied Statistics. — Institute of Mathematical Statistics, 2008. — Т. 2 , вып. 1 . — P. 224–244. — doi : . — arXiv : . .
  • Peter Richtarik, Martin Takac. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function // Mathematical Programming. — Springer, April 2011. — Т. 144 , вып. 1–2 . — P. 1–38. — doi : . — arXiv : .
  • Peter Richtarik, Martin Takac. Parallel coordinate descent methods for big data optimization // ArXiv:1212.0873. — December 2012. — arXiv : .
Источник —

Same as Координатный спуск