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

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





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








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


Лекция 2 (часть 3). Нижние оценки для численных методов решения задач (стохастической) выпуклой оптимизации

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

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

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





Аннотация: 1. Концепция сопротивляющегося оракула (цель – минимизировать число обращений к оракулу за градиентом/стохастическим градиентом/производной по направлению/значением функции и т.п.). Сложность общих задач оптимизации.
2. Сложность задач выпуклой оптимизации по Немировскому–Юдину (гладкие/негладкие; выпуклые/сильно выпуклые).
3. Концепция неточного оракула Нестерова–Деволдера–Глинёра. Сложность задач выпуклой оптимизации с неточным оракулом.
4. Сложность задач выпуклой оптимизации с оракулом, выдающим меньшую информацию о функции по сравнению с градиентом (например, только значение функции).
5. Сложность задач стохастической оптимизации.
6. Сложность задач онлайн оптимизации. Взвешивание экспертов. Многорукие бандиты.
7. Задача ЛП. Сложность симплекс метода. Пример Кли–Минти. Сложность в среднем (С. Смейл, Вершик–Спорышев). Smoothed complexity (Spielman–Teng).
8. Метод центра тяжести (и использование Hit and Run для его поиска), метод эллипсоидов. Битовая сложность. Полиномиальность задачи ЛП в битовой сложности (Л.Г. Хачиян). Сложность по Блюму–Шубу–Смейлу (проблема № 9 С. Смейла).
Литература:
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
- Complexity in numerical optimization. Eds. P. Pardalos. World Scientific Publishing, 1993.
- Смейл С. О проблемах вычислительной сложности. Математическое просвещение. Серия 3. Вып. 4. 1999. http://www.mccme.ru/free-books/matpros5.html
- Schrijver A. Theory of Linear and Integer Programming. John Wiley & sons, 1998. https://promathmedia.files.wordpress.com/2013/10/alexander_schrijver_theory_of_linear_and_integerbookfi-org.pdf
- Spielman D.A., Teng S.-H. Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time // Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (Hersonissos, Crete, Greece, July 6–8). ACM, New York, 2001. P. 296–305. http://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf
- 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.
- Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010. http://premolab.ru/pub_files/pub5/MnexoB89z7.pdf
- Agarwal A., Bartlett P.L., Ravikumar P., Wainwright M.J. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization // e-print, 2011. arXiv:1009.0571
- 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://www.princeton.edu/~sbubeck/SurveyBCB12.pdf
- Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013. http://www.ucllouvain.be/cps/ucl/doc/core/documents/coredp2011_70web.pdf
- Bubeck S. Convex optimization: algorithms and complexity // In Foundations and Trends in Machine Learning. 2015. V. 8. no. 3-4. P. 231–357. arXiv:1405.4980

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