А.В. Гасников (МФТИ). Мини-курс. Лекция 9. Распределенная оптимизация

Лекция 9. Общие заключительные замечания по курсу. Оптимальные алгоритмы распределенной оптимизации. Регуляризирующие свойства метода сопряженных градиентов (по А.С. Немировскому). Условие Поляка-Лоясиевича и решение систем нелинейных уравнений. Самосогласованные барьеры для неотрицательного ортанта и конуса неотрицательно определенных матриц. Выразимость большого числа задач выпуклой оптимизации посредством задач линейного программирования с конусными ограничениями (на базе конуса неотрицательно определенных матриц). Методы внутренней точки (Нестеров-Немировский). Квазиньютоновские методы ((L)BFGS). Оптимизационные пакеты. Распределенная оптимизация - для функционалов вида суммы (централизованная и децентрализованная). Матрица Лапласа коммуникационного графа. Построение двойственной задачи и ускоренные методы ее решения для гладких сильно выпуклых задач (распределенная интерпретация). Сведение к гладкому сильно выпуклому случаю всех случаев с помощью регуляризации прямой и(или) двойственной задачи. Оценка нормы двойственного решения. Сравнение случаев, когда доступен оракул, выдающий градиент прямого функционала и двойственного. Обобщение на случай стохастических оракулов. Описание способа получения оптимальных распределенных алгоритмов в негладком случае с помощью двойственной регуляризации седлового представления задачи и слайдинга Лана. 1 лекция - https://www.youtube.com/watch?v=ObqoK2J_db4 2 лекция - https://www.youtube.com/watch?v=wsq74WZvdDA 3 лекция - https://www.youtube.com/watch?v=sgoxQrJvZTY 4 лекция - https://www.youtube.com/watch?v=7XIRfV7CG8U 5 лекция - https://www.youtube.com/watch?v=1OHxD-lG_jE 6 лекция - https://www.youtube.com/watch?v=uTvErcqG7V4 7 лекция - https://www.youtube.com/watch?v=JhWMjF2Sor8 8 лекция - https://www.youtube.com/watch?v=uZmYqjwdZ9w Литература 1. Немировский А.С. О регуляризующих свойствах метода сопряжённых градиентов на некорректных задачах”, Ж. вычисл. матем. и матем. физ., 26:3 (1986), 332–347. - URL: http://www.mathnet.ru/links/d419c3cfb4dbe429b446fbc33dfc26ce/zvmmf4030.pdf 2. Nemirovski A.S. Information-based complexity of linear operator equations // J. of Complexity, 8 (1992), pp. 153–75. - URL: https://core.ac.uk/download/pdf/82348454.pdf 2. Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. – Philadelphia: SIAM, 2015. – URL: http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf Chapters 2-4 3. Bubeck S. Convex optimization: algorithms and complexity // Trends in Machine Learning. – 2015. – V. 8, N 3–4. – P. 231–357. – URL: https://arxiv.org/pdf/1405.4980.pdf Chapter 5 4. Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximal-gradient methods under the Polyak-Lojasiewicz condition // arXiv.org e-Print archive. 2016. - URL: https://arxiv.org/pdf/1608.04636.pdf 5. Lan G., Lee S., Zhou Y. Communication-efficient algorithms for decentralized and stochastic optimization // arXiv.org e-Print archive. 2017. – URL:https://arxiv.org/pdf/1701.03961.pdf 6. Uribe C.A., Lee S., Gasnikov A., Nedic A. Optimal algorithms for distributed optimization // arXiv.org e-Print archive. 2017. – URL:https://arxiv.org/pdf/1712.00232.pdf (основной источник) 7. Kim D., Fessler J.A. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions // arXiv.org e-Print archive. 2018. – URL: https://arxiv.org/pdf/1803.06600.pdf 8. Гасников А.В. Современные численные методы оптимизации. Универсальный градиентный спуск. – М.: МФТИ, 2018. – 166 с. – URL: https://arxiv.org/pdf/1711.00394.pdf (основной источник) 9. https://neos-server.org/neos/ Много интересного можно найти в нашей группе ВК: Последние события в нашем аккаунте Инстаграм: #гасников #майкоп #кмцагу