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

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

Автор: Аникин А.С., Гасников А.В., Горнов А.Ю.

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

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

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

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

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

Huge-scale оптимизация, разреженность, l1-норма, метод франк-вульфа

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

IDR: 142186134

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

  • Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц//Труды МФТИ. 2015. Т. 7, № 4. С. 74-94. arXiv:1508.07607
  • Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом//Труды МФТИ. 2016. -Т. 8, № 1. С. 41-91. arxiv:1411.4218
  • Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank//ЖВМ и МФ. 2015. Т. 54, № 3. C. 355-371. arXiv:1410.3120
  • Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print. 2014. arXiv:1407.1537
  • Jaggi M. Revisiting Frank-Wolfe: Projection-free sparse convex optimization//Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. https://sites.google.com/site/frankwolfegreedytutorial
  • Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов//Труды МФТИ. 2016. Т. 8, № 2 (в печати) arXiv:1508.02182
  • 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://www1.se.cuhk.edu.hk/~sqma/SEEM5121_Spring2015/Nesterov-CD-2012.pdf
  • Nesterov Y. E. Subgradient methods for huge-scale optimization problems//CORE Discussion Paper 2012/2. 2012. http://www.optimization-online.org/DB_FILE/2012/02/3339.pdf
  • Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads//e-print. 2015. arXiv:1508.00858
  • Гасников А.В., Гасникова Е.В., Двуреченский П.Е., Ершов Е.И., Лагуновская А.А. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков//Труды МФТИ. 2015. Т. 7, № 4. С. 114-128. arXiv:1505.07492
  • Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики//Математическое моделирование. 2016. Т. 28. (в печати) arXiv:1506.00293
  • 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
  • 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
  • Le Roux N., Schmidt M., Bach F. A stochastic gradient method with an exponential convergence rate for strongly-convex optimization with finite training sets//In Advances in Neural Information Processing Systems (NIPS). 2012. arXiv:1202.6258
  • Konecny J., Richtarik P. Semi-Stochastic gradient descent methods//e-print. 2013. arXiv:1312.1666
  • Konecny J., Liu J., Richtarik 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//In 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., Richtarik P., Zhang T. Randomized dual coordinate ascent with arbitrary sampling//e-print. 2014. arXiv:1411.5873
  • Lan G., Zhou Y. An optimal randomized incremental gradient methods//Technical Report, Department of Industrial and Systems Engineering, University of Florida, July 7, 2015, updated in October, 2015. http://www.ise.ufl.edu/glan/files/2015/10/OptRandom10-18.pdf
  • Lin Q., Lu Z., Xiao L. An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization//SIAM J. Optim. 2015. V. 25, N 4. P. 2244-2273. http://research.microsoft.com/pubs/228730/spdc_paper.pdf http://research.microsoft.com/pubs/258430/APCG_ERM_2015.pdf
  • Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization//Math. Program. Ser. B. 2015. V. 152. P. 75-112. http://www2.isye.gatech.edu/~nemirovs/ccg_revised_apr02.pdf
  • Nesterov Yu. Complexity bounds for primal-dual methods minimizing the model of objective function//CORE Discussion Papers. 2015/03. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2015_3web.pdf
  • Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования//ЖВМ и МФ. 2016. Т. 56, № 4. С. 523-534. arXiv:1410.7719
  • 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 Yu., Nemirovski A. On first order algorithms for 𝑙1/nuclear norm minimization//Acta Numerica. 2013. V. 22. P. 509-575. http://www2.isye.gatech.edu/~nemirovs/ActaFinal_2013.pdf
  • Lan G., Zhou Y. Conditional gradient sliding for convex optimization//SIAM J. Optim. 2015. http://www.ise.ufl.edu/glan/files/2015/09/CGS08-31.pdf
  • Lacost-Julien S., Jaggi M. On the Global Linear Convergence of Frank-Wolfe Optimization Variants//e-print. 2015. arXiv:1511.05932
  • Lacost-Julien S., Schmidt M., Bach F. A simpler approach to obtaining 𝑂(1/𝑡) convergence rate for the projected stochastic subgradient method//e-print. 2012. arXiv:1212.2002
  • Аникин А.С., Двуреченский П.Е., Гасников А.В., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации простых сильно выпуклых функционалов при аффинных ограничениях//ЖВМ и МФ. 2016. Т. 56. (подана) arXiv:1602.01686
  • Рябенький В.С. Введение в вычислительную математику. М.: Физматлит, 2008
  • Nemirovski A. Introduction to linear optimization//ISYE 661. Lecture Notes in Georgian Institute of Technology, 2012. http://www2.isye.gatech.edu/~nemirovs/OPTI_LectureNotes2015.pdf
  • Nocedal J., Wright S.J. Numerical Optimization. Springer, 2006
  • Spielman D. Algorithms, graph theory, and linear equations in Laplacian matrices//Proc. of the International Congress of Mathematicians. Hyderabad, India, 2010. P. 1-23. http://www.cs.yale.edu/homes/spielman/PAPERS/icm10post.pdf
  • Аникин А.С., Гасников А.В., Горнов А.Ю. Рандомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска//Труды МФТИ. 2016. Т. 8, № 1. С. 11-24. arXiv:1602.00594
  • Опойцев В.И. Устойчивые системы большой размерности//Автомат. и телемех. 1986. № 6. С. 43-49
  • Поляк Б.Т., Тремба А.А., Хлебников М.В., Щербаков П.С., Смирнов Г.В. Большие отклонения в линейных системах при ненулевых начальных условиях//Автомат. и телемех. 2015. № 6. C. 18-41
  • Saad Y. Iterative methods for sparse linear systems. SIAM, 2003. http://www-users.cs.umn.edu/~saad/books.html
  • Красносельский М.А., Крейн С.Г. Замечание о распределении ошибок при решении системы линейных уравнений при помощи итерационного процесса//УМН. 1952. Т. 7, № 4(50). С. 157-161
  • Бакушинский А.Б., Кокурин М.Ю. Итерационные методы решения некорректных операторных уравнений с гладкими операторами. М.: УРСС, 2002
  • Gower R., Richtarik P. Randomized Iterative Methods for Linear Systems//SIAM. J. Matrix Anal. & Appl. 2015. V. 36(4). P. 1660-1690. arXiv:1506.03296
  • Gower R., Richtarik P. Stochastic Dual Ascent for Solving Linear Systems//e-print. 2015. arXiv:1512.06890
  • Gower R., Richtarik P. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms//e-print. 2015. arXiv:1602.01768
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp