Рандомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска
Автор: Аникин А.С., Гасников А.В., Горнов А.Ю.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика, вычислительная техника и упровление
Статья в выпуске: 1 (29) т.8, 2016 года.
Бесплатный доступ
В работе исследуются различные рандомизации метода зеркального спуска для задач huge-scale оптимизации с разреженной структурой. В качестве одного из примеров приложения приводится задача PageRank.
Huge-scale оптимизация, рандомизация, метод зеркального спуска, разреженность, оценки вероятностей больших уклонений
Короткий адрес: https://sciup.org/142186111
IDR: 142186111
Список литературы Рандомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска
- Nesterov Y.E. Subgradient methods for huge-scale optimization problems//CORE Discussion Paper 2012/2. 2012
- Nesterov Yu., Shpirko S. Primal-dual subgradient method for huge-scale linear conic problem//Optimization online. 2012. http://www.optimization-online.org/DB_FILE/2012/08/3590.pdf
- Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц//Труды МФТИ. 2015. Т. 7, № 4. С. 74-94. arXiv:1508.07607
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом//Труды МФТИ. 2016. Т. 8 (в печати). arxiv:1411.4218
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print, 2014. arXiv:1407.1537
- Nesterov Y. Primal-dual subgradient methods for convex problems//Math. Program. Ser. B. 2009. V. 120(1). P. 261-283
- Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, I, II. In: Optimization for Machine Learning/eds. S. Sra, S. Nowozin, S. Wright. MIT Press, 2012
- Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики//Математическое моделирование. 2016. Т. 28 (в печати). arXiv:1506.00293
- Nesterov Yu. New primal-dual subgradient methods for convex optimization problems with functional constraints//International Workshop «Optimization and Statistical Learning». 2015, January 11-16. France. Les Houches. http://lear.inrialpes.fr/workshop/osl2015/program.html
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979
- Назин А.В., Поляк Б.Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank//Автоматика и телемеханика. 2011. № 2. C. 131-141
- Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов//Труды МФТИ. 2016. Т. 8 (в печати). arXiv:1508.02182
- Аникин А.С., Двуреченский П.Е., Гасников А.В., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях//ЖВМ и МФ. 2016. Т. 56 (подана). arXiv:1602.01686
- Никайдо Х. Выпуклые структуры и математическая экономика. М.: Мир, 1972
- Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank//ЖВМ и МФ. 2015. Т. 55, № 3. С. 355-371
Статья научная
