RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Стохастический анализ в задачах
23 апреля 2016 г. 13:00–15:00, г. Москва, МЦНМО (Большой Власьевский пер., 11, ауд. 401, проход свободный)
 


Лекция 9 (часть 2). Разреженные задачи Huge-scale оптимизации

А. В. Гасниковab

a Московский физико-технический институт (государственный университет), г. Долгопрудный Московской обл.
b Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва

Количество просмотров:
Эта страница:199
Youtube Video:





Аннотация: 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

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020