Лекция 6 (часть 1). Покомпонентные методы и спуски по направлению

1. Быстрый покомпонентный метод (обобщение конструкции Allen-Zhu–Oreсchia: выпуклая комбинация покомпонентных вариантов ПГМ и МЗС). Наследование основных свойств. Например, равномерная ограниченность (в вероятностных терминах) генерируемой методом последовательности. Перенесение результатов на сильно выпуклый случай с помощью рестарт техники.
2. Получение оценок скорости сходимости. Обсуждение тезиса: покомпонентные методы улучшают (в смысле общего числа арифметических операций) свои полноградиентные аналоги, заменяя (в оценках) константу Липшица градиента по худшему направлению на некоторую среднюю константу Липшица. Чуть более точно, заменяют максимальное собственное значения матрицы Гессе функционала задачи на среднее арифметическое всех собственных значений (сумма всех собственных значений = следу матрицы Гессе). Все это может уменьшить значение константы Липшица (используемой в оценке) в число раз, пропорциональное размерности пространства, в котором происходит оптимизация. Пример минимизации квадратичной неотрицательно определенной функции с равномерно заполненной числами от 1 до 2 матрицей.
3. В каких случаях покомпонентные методы сохраняют свое основное свойство (см. п. 2) на разреженных задачах? Сепарабельные функционалы со скрытой аффинно-разреженной структурой (назовем этот класс задач S), возникающие в задачах машинного обучения (например, SVM) и в задачах моделирования компьютерных / транспортных сетей (например, в задаче восстановления матрицы корреспонденций по потокам на линках или задачи поиска равновесий в транспортных сетях). Адаптивная настройка покомпонентных методов на константы Липшица частных производных функции (по разным направлениям). Композитные покомпонентные методы. Блочно-покомпонентные методы. Пример приложения (поиск равновесия в модели стабильной динамики, переписанной в форме Нестерова–Дорна). Обсуждение на какие множества не сепарабельной структуры возможно перенесение покомпонентных методов. Контрпример с минимизацией параболоида на внутренности симплекса в R^2.
4. Прямо-двойственность покомпонентных методов. Как это сочетается с разреженностью задачи? Обсуждение тезиса: двойственные покомпонентные методы для задач S класса порождают почти все известные (учитывающие гладкость постановки) методы рандомизации суммы. Когда лучше использовать прямой, а когда двойственный покомпонентный метод для композитных задач S класса? Пример PageRank.
5. Параллельные и распределенные вычисления. Использование покомпонентных методов.
6. Концентрация меры на шарах в различных нормах. Приложение к получению методов (и оценок скоростей их сходимости) спуска по (случайному) направлению исходя из рандомизированного МЗС.
7. Спуски по направлению для задач стохастической оптимизации на различных множествах простой структуры. Геометрическая интерпретация. Исследование оптимальности рандомизации (при выборе случайного направления) на евклидовом шаре (сфере) в независимости от выбора прокс-структуры в МЗС.
8. Перенесение оценок метода SIGMA (в условиях шума случайной и неслучайно природы) на покомпонентные методы и спуски по (случайному) направлению.
Литература:
-Bertsekas D.P., Tsitsiklis J.N. Parallel and distributed computation: Numerical methods. Prentice Hall, 1989. http://www.mit.edu/~jnt/parallel.html
-Ledoux M. Concentration of measure phenomenon. Providence, RI, Amer. Math. Soc., 2001 (Math. Surveys Monogr. V. 89).
-Nedic A., Ozdaglar A. Cooperative distributed multi-agent optimization. In Convex optimization in signal processing and communications (D.P. Palomar and Y.C. Eldar, eds.). Cambridge University Press, 2010. https://asu.mit.edu/sites/default/files/documents/publications/Dist-chapter.pdf
-Nesterov Y.E. Efficiency of coordinate descent methods on large scale optimization problem // SIAM Journal on Optimization. 2012. V. 22. № 2. P. 341–362. http://www1.se.cuhk.edu.hk/~sqma/SEEM5121_Spring2015/Nesterov-CD-2012.pdf
-Boyd S., Parikh N., Chu E., Peleato B., Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers // Foundations and Trends in Machine Learning. 2011. V. 3(1). P. 1–122. http://stanford.edu/~boyd/papers.html
-Fercoq O., Richtárik P. Accelerated, parallel and proximal coordinate descent // e-print, 2013. arXiv:1312.5799 Qu Z., Richtarik P. Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity // e-print, 2014. arXiv:1412.8060
-Гасников А.В., Двуреченский П.Е., Камзолов Д.И. Градиентные и прямые методы с неточным оракулом для задач стохастической оптимизации // Динамика систем и процессы управления. Труды Международной конференции, посвящено 90-летию со дня рождения академика Н.Н. Красовского. Екатеринбург, 15 – 20 сентября 2014. Издательство: Институт математики и механики УрО РАН им. Н.Н. Красовского (Екатеринбург), 2015. С. 111–117. arXiv:1502.06259
-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 Wright S.J. Coordinate descent algorithms // e-print, 20015. arXiv:1502.04759
-Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Безградиентные прокс-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе // Автоматика и телемеханика. 2016. arXiv:1412.3890
-Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом // Труды МФТИ. 2016. Т. 8. arxiv:1411.4218
-Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов // Труды МФТИ. 2016. Т. 8. arXiv:1508.02182
-Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. arXiv:1506.00293
- Richtárik P. http://www.maths.ed.ac.uk/~richtarik/