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

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

Описание

править

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

 ,

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

 [2]

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

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

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

 

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

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

 

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

править

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

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

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

Ограничения

править

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

 

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

Приложения

править

Алгоритмы координатного спуска популярны ввиду их простоты, но то же свойство побуждает исследователей игнорировать их в пользу более интересных (более сложных) методов[1]. Ранние приложения оптимизации методом координатного спуска были в области компьютерной томографии[7], где метод показал быструю сходимость[8] и был использован для реконструкции изображений многослойной спиральной компьютерной томографии[9]. Алгоритм циклического координатного спуска был применён в предсказании протеиновой структуры[10]. Более того, рос интерес к применению координатного спуска с появлением задач большого размера в машинном обучении, где координатный спуск, как было показано, конкуррентен с другими методами, когда применяется к таким задачам, как обучение линейным методом опорных векторов[11] (см. LIBLINEAR[англ.]) и неотрицательное матричное разложение[12]. Методы привлекательны для задач, когда вычисление градиента невыполнимо, возможно потому, что требуемые данные распределены по компьютерным сетям[13].

См. также

править

Примечания

править
  1. 1 2 3 4 Wright, 2015, с. 3–34.
  2. Архивированная копия. Дата обращения: 6 февраля 2022. Архивировано 6 февраля 2022 года.
  3. Spall, 2012, с. 187–208.
  4. Zheng, Saquib, Sauer, Bouman, 2000, с. 1745–1759.
  5. Fessler, Ficaro, Clinthorne, Lange, 1997, с. 166–175.
  6. Wang, Sabne, Kisner, 2016, с. 2:1–2:12.
  7. Sauer, Bouman, 1993, с. 534–548.
  8. Yu, Thibault, Bouman, Sauer, 2011, с. 161–175.
  9. Thibault, Sauer, Bouman, Hsieh, 2007, с. 4526–4544.
  10. Canutescu, Dunbrack, 2003, с. 963–72.
  11. Hsieh, Chang, Lin, Keerthi, 2008, с. 408.
  12. Hsieh, Dhillon, 2011, с. 1064.
  13. Nesterov, 2012, с. 341–362.

Литература

править
  • Stephen J. Wright. Coordinate descent algorithms // Mathematical Programming. — 2015. — Т. 151, вып. 1. — doi:10.1007/s10107-015-0892-3. — arXiv:1502.04759.
  • Spall J. C. Cyclic Seesaw Process for Optimization and Identification // Journal of Optimization Theory and Applications. — 2012. — Т. 154, вып. 1. — doi:10.1007/s10957-012-0001-1.
  • 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 1057-7149. — doi:10.1109/83.869186. — Bibcode2000ITIP....9.1745Z. — PMID 18262913.
  • 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 0278-0062. — doi:10.1109/42.563662. — PMID 9101326.
  • Xiao Wang, Amit Sabne, Sherman Kisner, Anand Raghunathan, Charles Bouman, Samuel Midkiff. High Performance Model Based Image Reconstruction. — Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. — New York, NY, USA: ACM, 2016. — ISBN 9781450340922. — doi:10.1145/2851141.2851163.
  • Ken Sauer, Charles Bouman. A Local Update Strategy for Iterative Reconstruction from Projections // IEEE Transactions on Signal Processing. — 1993. — Февраль (т. 41, вып. 2). — doi:10.1109/78.193196. — Bibcode1993ITSP...41..534S.
  • Zhou Yu, Jean-Baptiste Thibault, Charles Bouman, Ken Sauer, Jiang Hsieh. Fast Model-Based X-ray CT Reconstruction Using Spatially Non-Homogeneous ICD Optimization // IEEE Transactions on Image Processing. — 2011. — Январь (т. 20, вып. 1). — doi:10.1109/TIP.2010.2058811. — Bibcode2011ITIP...20..161Y. — PMID 20643609.
  • Jean-Baptiste Thibault, Ken Sauer, Charles Bouman, Jiang Hsieh. A Three-Dimensional Statistical Approach to Improved Image Quality for Multi-Slice Helical CT // Medical Physics. — 2007. — Ноябрь (т. 34, вып. 11). — doi:10.1118/1.2789499. — Bibcode2007MedPh..34.4526T. — PMID 18072519.
  • Canutescu A.A., Dunbrack R.L. Cyclic coordinate descent: A robotics algorithm for protein loop closure. // Protein Science. — 2003. — Т. 12, вып. 5. — doi:10.1110/ps.0242703. — PMID 12717019. — PMC 2323867.
  • 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:10.1145/1390156.1390208.
  • Hsieh C. J., Dhillon I. S. Fast coordinate descent methods with variable selection for non-negative matrix factorization // Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. — 2011. — ISBN 9781450308137. — doi:10.1145/2020408.2020577.
  • Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems // SIAM J. Optim.. — 2012. — Т. 22, вып. 2. — doi:10.1137/100802001.
  • Bezdek J. C., Hathaway R. J., Howard R. E., Wilson C. A., Windham M. P. Local convergence analysis of a grouped variable version of coordinate descent // Journal of Optimization Theory and Applications. — Kluwer Academic/Plenum Publishers, 1987. — Т. 54, вып. 3. — P. 471–477. — doi:10.1007/BF00940196.
  • Dimitri P. Bertsekas,. Nonlinear Programming. — Second Edition. — Belmont, Massachusetts: Athena Scientific, 1999. — ISBN 1-886529-00-0.
  • Zhiquan Luo, Tseng P. On the convergence of the coordinate descent method for convex differentiable minimization // Journal of Optimization Theory and Applications. — Kluwer Academic/Plenum Publishers, 1992. — Т. 72, вып. 1. — P. 7–35. — doi:10.1007/BF00939948..
  • 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:10.1214/07-AOAS147. — arXiv:0803.3876..
  • 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:10.1007/s10107-012-0614-z. — arXiv:1107.2848.
  • Peter Richtarik, Martin Takac. Parallel coordinate descent methods for big data optimization // ArXiv:1212.0873. — December 2012. — arXiv:1212.0873.