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

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





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








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


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

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

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

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





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

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