RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Стохастический анализ в задачах
26 марта 2016 г. 11:00–15:00, г. Москва, МЦНМО (Большой Власьевский пер., 11, ауд. 401, проход свободный)
 


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

А. В. Гасниковab

a Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
b Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва

Количество просмотров:
Эта страница:143
Youtube Video:





Аннотация: 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/

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018