Стохастический анализ в задачах 5 марта 2016 г. 15:00–17:30, г. Москва, Занятие будет на территории НИУ ВШЭ (Мясницкая, 20, ауд. 101, для прохода необходимо один раз заранее (до 12 февраля) написать письмо (тема письма “курс Гасникова”) Инне Юрьевне Корольковой ikorolkova@hse.ru)
Лекция 3 (часть 2). Базисные численные методы на множествах простой структуры
Аннотация:
1. Прямой градиентный метод Канторовича–Поляка (ПГМ). Прямой-прокс градиентный метод. Прямой-прокс градиентный метод с неточным оракулом и метод зеркального спуска. Равномерная ограниченность последовательностей, генерируемых методами (особенности ПГМ в случае выбора не евклидовой нормы).
2. Метод зеркального спуска Немировского–Юдина (МЗС) и метод двойственных усреднений Ю.Е. Нестерова (МДУ) (второй метод Ляпунова).
3. Игра на выборе прокс-структуры, исходя из множества (простой структуры). Примеры (шары, симплекс, прямое произведение симплексов).
4. Метод сопряженных градиентов и метод тяжелого шарика (первый метод Ляпунова).
5. Быстрый градиентный метод (БГМ) Ю.Е. Нестерова (в форме Allen-Zhu–Oreсchia: выпуклая комбинация ПГМ и МЗС, в геометрической форме S. Bubeck’a). Равномерная ограниченность последовательности, генерируемой методом.
6. Метод регуляризации А.Н. Тихонова (приведение выпуклой задачи к сильно выпуклой). Выбор параметра регуляризации. Техника рестарта по параметру. Оптимальный выбор параметра рестарта. Получение оценок в сильно выпуклом случае с помощью рестарт техники по расстоянию от текущего положения до решения из методов, не настроенных на сильную выпуклость. Непрерывность ПГМ по параметру сильной выпуклости.
7. Непрерывные аналоги численных методов. Интерпретация методов.
8. Структурная оптимизация. Концепция заглядывания в “черный ящик”. Композитная оптимизация. Пример LASSO. Метод двойственного сглаживания Ю.Е. Нестерова для задач с простым лежандровым представлением.
Литература:
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf
- Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
- Boyd S., Vandenberghe L. Convex optimization. Cambridge University Press, 2004.
http://stanford.edu/~boyd/cvxbook/
- Nesterov Y. Smooth minimization of non-smooth function // Math. Program. Ser. A. 2005. V. 103. № 1. P. 127–152.
http://luthuli.cs.uiuc.edu/~daf/courses/Optimization/MRFpapers/nesterov05.pdf
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013.
http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.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
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent // e-print, 2014. arXiv:1407.1537
- 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
- Гасников А.В., Лагуновская А.А., Морозова Л.Э. О связи имитационной логит динамики в популяционной теории игр и метода зеркального спуска в онлайн оптимизации на примере задачи выбора кратчайшего маршрута // Труды МФТИ. 2015. Т. 7. № 4. С. 104–113. arXiv:1511.02398
Wibisono A., Wilson A.C. On accelerated methods in optimization // e-print, 2015. arXiv:1509.03616
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. arxiv:1411.4218
Обратная связь: