О нетривиальности быстрых (ускоренных) рандомизированных методов

О нетривиальности быстрых (ускоренных) рандомизированных методов

Автор: Гасников А.В., Двуреченский П.Е., Усманова И.Н.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Информатика, вычислительная техника и упровление

Статья в выпуске: 2 (30) т.8, 2016 года.

Бесплатный доступ

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

Еще

Рандомизированные покомпонентные методы, быстрый градиентный метод, рандомизация суммы

Короткий адрес: https://sciup.org/142186136

IDR: 142186136

Список литературы О нетривиальности быстрых (ускоренных) рандомизированных методов

  • Bubeck S. Convex optimization: algorithms and complexity//In Foundations and Trends in Machine Learning. 2015. V. 8, N 3-4. P. 231-357. arXiv:1405.4980
  • Nesterov Y.E. Efficiency of coordinate descent methods on large scale optimization problem//SIAM Journal on Optimization. 2012. V. 22, N 2. P. 341-362.http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf
  • Fercoq O., Richtarik P. Accelerated, Parallel and Proximal Coordinate Descent//e-print, 2013. arXiv:1312.5799
  • Qu Z., Richtarik P. Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity//e-print, 2014. arXiv:1412.8060
  • Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Y., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads//Proceedings of International conference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
  • Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print, 2015. arXiv:1407.1537
  • Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013
  • Dvurechensky P., Gasnikov A. Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle//Journal Optimization Theory and Applications. 2016 (accepted). arXiv:1411.2876
  • Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом//Труды МФТИ. 2016. Т. 8, № 1. С. 41-91.arxiv:1411.4218
  • Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Безградиентные прокс-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе//Автоматика и телемеханика. 2016. arXiv:1412.3890
  • Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Y., Raigorodskii A., Tikhonov A., Zhukovskii M. Learning supervised PageRank with gradient-free optimization methods//e-print, 2014. arXiv:1411.4282
  • Ledoux M. Concentration of measure phenomenon. Providence, RI, Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89)
  • Rakhlin A., Shamir O., Sridharan K. Making gradient descent optimal for strongly convex stochastic optimization//ICML. 2012. arXiv:1109.5647
  • Juditsky A., Nesterov Y. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization//Stoch. System. 2014. V. 4, N 1. P. 44-80. arXiv:1401.1792
  • Hazan E., Kale S. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization//JMLR. 2014. V. 15. P. 2489-2512
  • Nesterov Yu. Random gradient-free minimization of convex functions//CORE Discussion Paper 2011/1. 2011; Found. Comput. Math. 2015 (accepted). http://uclouvain.be/cps/ucl/doc/core/documents/coredp2011_1web.pdf
  • Richt´arik P. http://www.maths.ed.ac.uk/∼richtarik/
  • Le Roux N., Schmidt M., Bach F. A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets//Advances in Neural Information Processing Systems (NIPS). 2012. arXiv:1202.6258
  • Johnson B., Zhang T. Accelerating stochastic gradient descent using predictive variance reduction//In Advances in Neural Information Processing Systems (NIPS). 2013. http://www.stat.rutgers.edu/home/tzhang/pubs.html
  • Konecny J., Richt´arik P. Semi-Stochastic gradient descent methods//e-print, 2013. arXiv:1312.1666
  • Konecny J., Liu J., Richt´arik P., Takac M. Mini-batch semi-stochastic gradient descent in the proximal setting//e-print, 2015. arXiv:1504.04407
  • Agarwal A., Bottou L. A lower bound for the optimization of finite sums//e-print, 2014.arXiv:1410.0723
  • Shalev-Shwartz S., Zhang T. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization//Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014. P. 64-72. arXiv:1309.2375
  • Zheng Q., Richt´arik P., Zhang T. Randomized dual coordinate ascent with arbitrary sampling//e-print, 2015. arXiv:1411.5873
  • Zhang T. http://www.stat.rutgers.edu/home/tzhang/
  • Lee Y.T., Sidford A. Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems//e-print, 2013. arXiv:1305.1922
  • Nesterov Yu.E. Structural Optimization: New Perspectives for Increasing Efficiency of Numerical Schemes//International conference «Optimization and Applications in Control and Data Science»on the occasion of Boris Polyak’s 80th birthday, Moscow, May, 2015. http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=11909
  • Nesterov Yu. Universal gradient methods for convex optimization problems//CORE Discussion Paper 2013/63. 2013. Math. Program. Ser. A. 2015. V. 152. P. 381-404. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2013_26web.pdf
  • Wright S.J. Coordinate descent algorithms//e-print, 2015. arXiv:1502.04759
  • Nesterov Yu., Shikhman V. Convergent subgradient methods for nonsmooth convex minimization//CORE Discussion Paper 2014/5. 2014. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2014_5web.pdf
  • Nesterov Y. Primal-dual subgradient methods for convex problems//Math. Program. Ser. B. 2009. V. 120(1). P. 261-283. http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2005_67.pdf
  • Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики//Математическое моделирование. 2016. Т. 28. arXiv:1506.00293
  • Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure//Mathematics of Operation Research. 2010. V. 35, N 1. P. 52-78. http://www2.isye.gatech.edu/∼nemirovs/MOR_AccuracyCertificates.pdf
  • Nesterov Yu. Gradient methods for minimizing composite functions//Math. Prog. 2013. V. 140, N 1. P. 125-161. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2007_76.pdf
  • Гасников А.В., Гасникова Е.В., Двуреченский П.Е., Ершов Е.И., Лагуновская А.А. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков//Труды МФТИ. 2015. Т. 7, № 4. С. 114-128. arXiv:1505.07492
  • Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийных транспортных моделях//Труды МФТИ. 2015. Т. 7, № 4. С. 143-155. arXiv:1506.00292; https://mipt.ru/upload/medialibrary/ffe/143-155.pdf
  • Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования//ЖВМ и МФ. 2016. Т. 56, № 4. С. 523-534. arXiv:1410.7719
  • Ким К., Нестеров Ю., Скоков В., Черкасский Б. Эффективные алгоритмы для дифференцирования и задачи экстремали//Экономика и математические методы. 1984. Т. 20. С. 309-318
  • Patrascu A. Efficient first order methods for sparse convex optimization. PhD Thesis. University Politehnica of Bucharest, 2015. http://acse.pub.ro/person/ion-necoara/
  • Nesterov Y. Smooth minimization of non-smooth function//Math. Program. Ser. A. 2005. V. 103, N 1. P. 127-152
  • Allen-Zhu Z., Qu Z., Richt?rik P., Yuan Y. Even faster accelerated coordinate descent using non-uniform sampling//e-print, December, 2015. arXiv:1512.09103
  • Nesterov Y. Stich S. Efficiency of accelerated coordinate descent method on structured optimization problems//CORE Discussion Papers 2016/03
  • Dunner C., Forte S., Takac M., Jaggi M. Primal-dual rates and certificates//e-print, 2016. arXiv:1602.05205
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp