Семинары: А. В. Гасников, Лекция 8. Стохастическая онлайн оптимизация

СЕМИНАРЫ


Стохастический анализ в задачах 16 апреля 2016 г. 11:00, г. Москва, Занятие будет на территории НИУ ВШЭ (Мясницкая, 20, ауд. 513, для прохода необходимо один раз заранее (до 12 февраля) написать письмо (тема письма “курс Гасникова”) Инне Юрьевне Корольковой ikorolkova@hse.ru)

Лекция 8. Стохастическая онлайн оптимизация А. В. Гасников^ab ^a Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва ^b Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
https://www.youtube.com/watch?v=1IY0M30P5hs Аннотация: 1. МЗС / метод двойственных усреднений и (стохастическая) онлайн оптимизация. 2. Сильно выпуклый случай. Оценки вероятностей больших уклонений. 3. Взвешивание экспертов. Экспоненциальное взвешивание. Следование за возмущенным лидером. Бустинг. Предсказание последовательностей. Предсказания и игры. Теоретико-игровая интерпретация теории вероятностей. 4. Агрегирующие алгоритмы. Онлайн регрессия. 5. Многорукие бандиты. Стохастические. Враждебные. Стохастическо-враждебные. 6. Нелинейные (стохастические) одноточечные и двуточечные (многоточечные) бандиты. 7. Контекстуальные бандиты. Предсказание на основе частичной информации. 8. Самообучающиеся системы. Обучение нейронных сетей. Алгоритмы кластеризации. EM-алгоритм. Обучение с подкреплением и динамическое программирование. Алгоритм Q-обучения. Алгоритм Dyna. Пример задачи из области составления расписания обслуживания для многоканальной системы массового обслуживания. Литература: - Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006. http://www.ii.uni.wroc.pl/~lukstafi/pmwiki/uploads/AGT/Prediction_Learning_and_Games.pdf - Николенко С.И., Тулупьев А.Л. Самообучающиеся системы. М.: МЦНМО, 2009. - Shalev-Shwartz S. Online learning and online convex optimization // Foundation and Trends in Machine Learning. 2011. V. 4. № 2. P. 107–194. http://www.cs.huji.ac.il/~shais/papers/OLsurvey.pdf - Sridharan K. Learning from an optimization viewpoint. PhD Thesis, Toyota Technological Institute at Chicago, 2011. http://ttic.uchicago.edu/~karthik/thesis.pdf - Bubeck S., Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems // Foundation and Trends in Machine Learning. 2012. V. 5. № 1. P. 1–122. http://arxiv.org/pdf/1204.5721.pdf - Hopcroft J., Kannan R. Computer Science Theory for the Information Age. E-print, 2012. https://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/book-toc.pdf - Вьюгин В.В. Математические основы теории машинного обучения и прогнозирования. М.: МЦНМО, 2013. http://www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=6238 - Rakhlin A., Sridharan K. Statistical Learning Theory and Sequential Prediction // e-print, 2015. http://stat.wharton.upenn.edu/~rakhlin/book_draft.pdf - Hazan E. Introduction to online convex optimization // e-print, 2015. http://ocobook.cs.princeton.edu/OCObook.pdf - Andersen A., Spokoiny V. Two convergence result for an alternation maximization procedure // e-print, 2015. arXiv:1501.01525 - Гасников А.В., Нестеров Ю.Е., Спокойный В.Г. Об эффективности одного метода рандомизации зеркального спуска в задачах онлайн оптимизации // ЖВМ и МФ. Т. 55. № 4. 2015. С. 55–71. arXiv:1410.7719 - Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2015. http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf - Гасников А.В., Крымова Е.А., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи // Автоматика и Телемеханика. 2016. arXiv:1509.01679