Лекция 7 (часть 2). Безградиентные методы и их приложения

1. Стохастические и детерминированные постановки. Русский метод для детерминированных постановок (в пространствах небольших размерностей). В стохастических постановках важно число обращений к оракулу за реализацией (одной и той же) функции в нескольких точках. Обсуждение принципиальной разности между одной и двумя точками. Пример Ю.Е. Нестерова, когда в “жизни" возникают такие задачи.
2. Конструкция сглаживания функции по шару (А.С. Немировский, Flaxman–Kalai–McCahan).
3. Получение с помощью конструкции сглаживания для задач стохастической оптимизации оценки скоростей сходимости для безградиентных методов на базе МЗС / МДУ в гладком случае. Обсуждение выбора нормы, в которой задается шар.
4. Перенесение результатов на случай неточного оракула (в том числе перенесение оценок метода SIGMA на безградиентные методы). Отдельно рассмотрение гладкого случая и негладкого. В отличие от спусков по случайному направлению для негладких задач с шумом рандомизация на евклидовым шаре в безградиентном методе уже может быть не оптимальной при решении задач выпуклой оптимизации на симплексе.
5. Метод двойственного сглаживания Б.Т. Поляка в форме Duchi–Jordan–Wainwright–Wibisono. Неустойчивость метода к ошибкам оракула.
6. Приложение прямого быстрого градиентного метода с неточным оракулом к web-поиску.
7. Глобальная оптимизация и монотонный симметричный марковский поиск (Некруткин–Тихомиров). Markov Chain Monte Carlo Revolution и состоятельность оценок максимального правдоподобия. Пример P. Diaconis’а. Глобальная оптимизация и simulated annealing. Генетические алгоритмы.
8. Задача об обнаружении сигнала на фоне не случайных помех (Фишер–Граничин–Поляк). Обобщения конструкции Фишера.
Литература:
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
- Cerf R. Asymptotic convergence of genetic algorithms // Adv. Appl. Prob. 1998. V. 30. no. 2. P. 521–550. http://www.math.u-psud.fr/~cerf/papers/gae.pdf Spall J.C. Introduction to stochastic search and optimization: estimation, simulation and control. Wiley, 2003.
-Граничин О.Н., Поляк Б.Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003.
- Diaconis P. The Markov chain Monte Carlo revolution // Bulletin (New Series) of the AMS. 2009. V. 49. № 2. P. 179–205. http://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf
- Flaxman A.D., Kalai A.T., McCahan H.B. Online convex optimization in the bandit setting: gradient descent without a gradient // Proceedings of the 16th annual ACM-SIAM symposium on Discrete Algorithms. 2005. P. 385–394. http://research.microsoft.com/en-us/um/people/adum/publications/2005-Online_Convex_Optimization_in_the_Bandit_Setting.pdf
- Zhigljavsky A., Zilinskas A. Stochastic global optimization. Springer Optimization and Its Applications, 2008.
-Agarwal A., Dekel O., Xiao L. Optimal algorithms for online convex optimization with multi-point bandit feedback // Proceedings of 23-d Annual Conference on Learning Theory. 2010. P. 28–40.
-Nesterov Yu. Random gradient-free minimization of convex functions // CORE Discussion Paper 2011/1. 2011. http://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2011_1web.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
-Протасов В.Ю. Как найти минимум выпуклой функции по ее значениям. ТМШ, 2013. http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=7251
-Duchi J.C., Jordan M.I., Wainwright M.J., Wibisono A. Optimal rates for zero-order convex optimization: the power of two function evaluations // e-print, 2013. arXiv:1312.2139
-Belloni A., Liang T., Narayanan H., Rakhlin A. Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions // e-print, 2015. arXiv:1501.07242
-Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Безградиентные прокс-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе // Автоматика и телемеханика. 2016. arXiv:1412.3890
-Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. arxiv:1411.4218
- Bogolubsky L., Dvurechensky P., Gasnikov A., Gusev G., Nesterov Yu., Raigorodskii A., Tikhonov A., Zhukovskii M. Learning supervised PageRank with gradient-free optimization methods // ICML-2016. (submitted) arXiv:1411.4282