Лекция 4 (часть 1). Стохастическая оптимизация и ее приложения

1. Стохастическая оптимизация (СО). SAA vs SA. Примеры задач. Рандомизация в стохастической оптимизации (бутстреп).
2. МЗС со стохастическим оракулом. Равномерная ограниченность (в вероятностных категориях) последовательности, генерируемой методом.
3. Мартингальное неравенство Азума–Хефдинга и вероятности больших уклонений.
4. Связь Математической статистики и СО.
5. Связь Статистической теории обучения и СО.
6. Сложность итерации (игра на небольшом увеличении числа итераций и существенном удешевлении стоимости каждой итерации). Рандомизированные методы. Неравенство Маркова, процедура амплификации и их роль в получении оценок вероятностей больших отклонений рандомизированных методов. Примеры приложения к задачам Huge-scale оптимизации (метод рандомизации суммы, рандомизация при умножении матрицы на вектор из единичного симплекса, рандомизация согласно вектору градиента).
7. Седловые задачи (седловое/лежандрово представление задач) и рандомизированные методы. Нижняя оценка для числа операций в задаче поиска равновесия в антагонистической матричной игре (нужно сосчитать не менее половины элементов матрицы) и рандомизированный (рандомизация при KL-проектировании на симплекс) сублинейный алгоритм Григориадиса–Хачияна. Состоятельность по Ханнану этого алгоритма и его онлайн интерпретация. Рандомизированный МЗС для той же задачи. Приложение описанных методов к задаче PageRank. MCMC для задачи PageRank и его интерпретация.
8. Рандомизация и разреженность в задачах huge-scale оптимизации. Привнесение рандомизации в детерминированную конструкцию Ю.Е. Нестерова решения разреженных huge-scale задач.
Литература:
- Juditsky A., Polyak B. Acceleration of stochastic approximation by averaging // SIAM Journal on Control and Optimization. 1992. V. 7. № 4. P. 838–855. http://www.eduwww.us/research/keren/doc/poljud92.pdf
- Sridharan K. Learning from an optimization viewpoint. PhD Thesis, Toyota Technological Institute at Chicago, 2011. http://ttic.uchicago.edu/~karthik/thesis.pdf
- Nesterov Y.E. Subgradient methods for huge-scale optimization problems // CORE Discussion Paper 2012/2. 2012. https://mipt.ru/dcam/upload/ae5/SGMHugeScale-arph2hev1tz.PDF
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf
- Shapiro A., Dentcheva D., Ruszczynski A. Lecture on stochastic programming. Modeling and theory. MPS-SIAM series on Optimization, 2014. http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=7740 http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=7741
- Rakhlin A., Sridharan K. Statistical Learning Theory and Sequential Prediction // e-print, 2015. http://stat.wharton.upenn.edu/~rakhlin/book_draft.pdf
- Spokoiny V. http://arxiv.org/pdf/1410.0347v5.pdf; http://arxiv.org/pdf/1507.05034.pdf
- Hazan E. Introduction to online convex optimization // e-print, 2015. http://ocobook.cs.princeton.edu/OCObook.pdf
- Гасников А.В., Дмитриев Д.Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank // ЖВМ и МФ. Т. 55. № 3. 2015. С.355–371. arXiv:1410.3120
- Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц // Труды МФТИ. 2015. Т. 7. № 4. С. 74–94. arXiv:1508.07607
- Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. arXiv:1506.00293 Аникин А.С., Гасников А.В., Горнов А.Ю., Максимов Ю.В. О рандомизированном методе зеркального спуска для решения разреженных задач выпуклой оптимизации огромных размеров // Труды МФТИ. 2016. Т. 8. arXiv:1602.00594
- Lin Xiao http://research.microsoft.com/en-us/people/lixiao/
- George Lan http://www.ise.ufl.edu/glan/publications/
- Peter Richtárik http://www.maths.ed.ac.uk/~richtarik/
- Nathan Srebro http://ttic.uchicago.edu/~nati/
- Shai Shalev-Shwartz http://www.cs.huji.ac.il/~shais/