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

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