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

1. Оптимальный промежуточный (стохастический) градиентный метод (с неточным оракулом) SIGMA, как выпуклая комбинация БГМ и двойственного градиентного метода.
2. Операции с алгоритмами. Рассмотрение рестарт техники в сильно выпуклом случае для SIGMA. Процедура mini-batching’а для уменьшения дисперсии стохастического градиента. Процедура регуляризации (напоминание). Применение SIGMA к композитным постановкам. Композитный подход – как способ перенесения части (аддитивной) сложности в постановке задачи в итерацию (без увеличения числа итераций из-за потенциально плохих свойств композита). Пример применения композитного подхода (в сильно выпуклом и в не сильно выпуклом случаях) к задаче восстановления матрицы корреспонденций по замерам потоков на линках (ребрах) в большой компьютерной сети (Minimal Mutual Information Model). О сложности итерации в этом примере и переходе в сильно выпуклом случае к решению на каждой итерации соответствующей двойственной задачи.
3. Нетривиальность ускоренных рандомизированных методов или зачем нужно заглядывать в структуру доказательства получения оценок скоростей сходимости методов? Получение в сильно выпуклом гладком случае из оценок для SIGMA оценок для неускоренных покомпонентных методов и неускоренных методов рандомизации суммы.
4. Прямо-двойственность методов по Ю.Е. Нестерову и по А.С. Немировскому. Восстановление приближенного решения прямой задачи по накопленной методом последовательности при решении двойственной задачи прямо-двойственным методом. О контроле зазора двойственности в качестве критерия останова метода. Сочетание с техникой рестартов в случае неизвестных параметров, необходимых методу для работы. Примеры (поиск равновесий в различных транспортных моделях).
5. Техника регуляризации двойственной задачи (с рестартом по параметру регуляризации) для возможности восстановления решения прямой задачи, как альтернатива прямо-двойственному подходу. Пример задачи ЭЛП.
6. Суперпозиция методов 1 (min max вариант). Пример ускоренного алгоритма для задачи с лежандровым сильно выпуклым представлением, построенного на базе суперпозиции БГМ для внутренней задачи (приближенного вычисления функции и ее градиента из лежандрова представления) и БГМ в концепции неточного оракула для внешней задачи. Пример задачи ЭЛП и ее обобщения. В частности рассмотрение задач минимизации сепарабельных функционалов (вида суммы, где k-е слагаемое зависит только от k-й компоненты вектора x) при аффинных ограничениях (такие задачи приводятся с помощью принципа множителей Лагранжа к лежандрову представлению).
7. Суперпозиция методов 2 (min min вариант). Универсальный градиентный метод Ю.Е. Нестерова с неточным оракулом. Примеры приложения (поиск равновесия в многостадийной модели транспортных потоков, поиск барицентра Вассерштейна). Обсуждение тезиса: если задачу можно эффективно решить (пусть даже приближенно) по части переменных, заморозив остальные, то исходя из этого, надо строить численный метод. Сопоставление с композитным подходом.
8. О критериях останова методов и подборе неизвестных параметров. Соображения размерности и П-теорема. Адаптивность методов (априорно неизвестна желаемая точность по функции, с которой хотим решить задачу) и плата за адаптивность.
Литература:
- Nesterov Y. Primal-dual subgradient methods for convex problems // Math. Program. Ser. B. 2009. V. 120(1). P. 261–283. http://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2005_67.pdf
- Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure // Mathematics of Operation Research. 2010. V. 35. № 1. P. 52–78. http://www2.isye.gatech.edu/~nemirovs/MOR_AccuracyCertificates.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
- Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads // Proceedings of International conference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
- Гасников А.В., Гасникова Е.В., Двуреченский П.Е., Ершов Е.И., Лагуновская А.А. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков // Труды МФТИ. 2015. Т. 7. № 4. С. 114–128. arXiv:1505.07492
- Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийных транспортных моделях // Труды МФТИ. 2015. Т. 7. № 4. С. 143–155. arXiv:1506.00292 https://mipt.ru/upload/medialibrary/ffe/143-155.pdf
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. arxiv:1411.4218
- Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования // ЖВМ и МФ. 2016. Т. 56. № 4. arXiv:1410.7719
- Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. arXiv:1506.00293
- Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды МФТИ. 2016. Т. 8. arXiv:1508.02182
- Dvurechensky P., Gasnikov A. Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle // Journal Optimization Theory and Applications. 2016. (submitted) arXiv:1411.2876
- Аникин А.С., Гасников А.В., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации простых сильно выпуклых функционалов при аффинных ограничениях // ЖВМ и МФ. 2016. Т. 56. arXiv:1602.01686