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

Лекция 9. Общие заключительные замечания по курсу. Оптимальные алгоритмы распределенной оптимизации. Регуляризирующие свойства метода сопряженных градиентов (по А.С. Немировскому). Условие Поляка-Лоясиевича и решение систем нелинейных уравнений. Самосогласованные барьеры для неотрицательного ортанта и конуса неотрицательно определенных матриц. Выразимость большого числа задач выпуклой оптимизации посредством задач линейного программирования с конусными ограничениями (на базе конуса неотрицательно определенных матриц). Методы внутренней точки (Нестеров-Немировский). Квазиньютоновские методы ((L)BFGS). Оптимизационные пакеты. Распределенная оптимизация - для функционалов вида суммы (централизованная и децентрализованная). Матрица Лапласа коммуникационного графа. Построение двойственной задачи и ускоренные методы ее решения для гладких сильно выпуклых задач (распределенная интерпретация). Сведение к гладкому сильно выпуклому случаю всех случаев с помощью регуляризации прямой и(или) двойственной задачи. Оценка нормы двойственного решения. Сравнение случаев, когда доступен оракул, выдающий градиент прямого функционала и двойственного. Обобщение на случай стохастических оракулов. Описание способа получения оптимальных распределенных алгоритмов в негладком случае с помощью двойственной регуляризации седлового представления задачи и слайдинга Лана. 1 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 1....   2 лекция -    • А.В. Гасников  (МФТИ). Мини-курс. Лекция 2...   3 лекция -    • А.В.  Гасников (МФТИ). Мини-курс. Лекция 3...   4 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 4....   5 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 5....   6 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 6....   7 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 7....   8 лекция -    • А.В. Гасников (МФТИ). Мини-курс. Лекция 8....   Литература 1. Немировский А.С. О регуляризующих свойствах метода сопряжённых градиентов на некорректных задачах”, Ж. вычисл. матем. и матем. физ., 26:3 (1986), 332–347. - URL: http://www.mathnet.ru/links/d419c3cfb...
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/82348...
2. Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. – Philadelphia: SIAM, 2015. – URL: http://www2.isye.gatech.edu/~nemirovs...
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/
____________ Много интересного можно найти в нашей группе ВК: https://vk.com/kavmatagu
Последние события в нашем аккаунте Инстаграм:   / kavmatagu   #гасников #майкоп #кмцагу