|
СЕМИНАРЫ |
Стохастический анализ в задачах
|
|||
|
Лекция 9 (часть 2). Разреженные задачи Huge-scale оптимизации А. В. Гасниковab a Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл. b Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва |
|||
Аннотация: 1. Метод условного градиента и линейный минимизационный оракул (Франк–Вульф (ФВ)). В каких случаях (на каких множествах) метод оптимальный (оценки Немировского–Гузмана). 2. Разреженность метода ФВ, возникающая в случае оптимизации на симплексе. Пример G. Lugosi для LASSO. 3. Сочетание разреженности метода ФВ с разреженностью матрицы при минимизации квадратичного функционала на симплексе. Приложение к задаче PageRank. 4. Об эффективности линейного минимизационного оракула и динамическом программировании. Приложение к седловым задачам. Приложения метода ФВ к различным задачам композитной оптимизации. 5. О связи наличия эффективного линейного минимизационного оракула и возможности сжатия задачи путем перехода к двойственной. Пример поиск равновесного распределения потоков в транспортных сетях. 6. Truss Topology Design. 7. ПГМ с l1-нормой (альтернативное понимание (при сепарабельных ограничениях): неускоренный покомпонентный метод с выбором максимальной компоненты) при оптимизации на симплексе, на неотрицательном ортанте. Пример квадратичный функционал, функционал S-класса. Приложение к задаче PageRank. 8. Разреженность и рандомизация в задачах huge-scale оптимизации (продолжение). Литература: - Nesterov Yu., Shpirko S. http://www.optimization-online.org/DB_FILE/2012/08/3590.pdf - Jaggi M. Revisiting Frank–Wolfe: Projection-free sparse convex optimization // Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. https://sites.google.com/site/frankwolfegreedytutorial/ - 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 Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization // Journal of Complexity. 2015. arXiv:1307.5001 - Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization // Math. Program. Ser. B. 2015. http://www2.isye.gatech.edu/~nemirovs/ccg_revised_apr02.pdf - Cox B., Juditsky A., Nemirovski A. Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators on domains given by linear minimization oracles // e-print, 2015. arXiv:1506.02444 http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=11955 - Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц // Труды МФТИ. 2015. Т. 7. № 4. С. 74–94. arXiv:1508.07607 - Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. arXiv:1506.00293 - Аникин А.С., Гасников А.В., Горнов А.Ю., Максимов Ю.В. О рандомизированном методе зеркального спуска для решения разреженных задач выпуклой оптимизации огромных размеров // Труды МФТИ. 2016. Т. 8. arXiv:1602.00594 - Аникин А.С., Гасников А.В., Горнов А.Ю., Максимов Ю.В. О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации // e-print, 2016. arXiv:1602.01124 |