|
ЧИСЛЕННЫЕ МЕТОДЫ И ОСНОВЫ ИХ РЕАЛИЗАЦИИ
Ускоренные адаптивные по константам сильной выпуклости и Липшица для градиента методы первого порядка
Н. В. Плетневab a Московский физико-технический институт,
Россия, 141701, г. Долгопрудный, Институтский пер., д. 9
b Вычислительный центр им. А. А. Дородницына Российской академии наук Федерального
исследовательского центра «Информатика и управление» Российской академии наук,
Россия, 119333, Москва, ул. Вавилова, 40
Аннотация:
Работа посвящена построению эффективных и применимых к реальным задачам методов выпуклой оптимизации первого порядка, то есть использующих только значения целевой функции и ее производных. При построении используется быстрый градиентный метод OGM-G, который является оптимальным по оракульной сложности (числу вычислений градиента целевой функции), но при запуске требует знания констант сильной выпуклости и Липшица градиента для вычисления количества шагов и длины шага, требуемых для достижения заданной точности. Данное требование усложняет практическое использование метода. Предлагаются адаптивный по константе сильной выпуклости алгоритм ACGM, основанный на рестартах OGM-G с обновлением оценки константы сильной выпуклости, и адаптивный по константе Липшица градиента метод ALGM, в котором применение рестартов OGM-G дополнено подбором константы Липшица с проверкой условий гладкости, используемых в методе универсального градиентного спуска. При этом устраняются недостатки исходного метода, связанные с необходимостью знания данных констант, что делает возможным практическое использование. Доказывается, что оценки сложности построенных алгоритмов являются оптимальными с точностью до числового множителя. Для проверки полученных результатов проводятся эксперименты на модельных функциях и реальных задачах машинного обучения.
Ключевые слова:
быстрый градиентный метод, адаптивность по константе сильной выпуклости, адаптивность по константе Липшица градиента.
Поступила в редакцию: 19.05.2020 Исправленный вариант: 03.09.2021 Принята в печать: 03.09.2021
Образец цитирования:
Н. В. Плетнев, “Ускоренные адаптивные по константам сильной выпуклости и Липшица для градиента методы первого порядка”, Компьютерные исследования и моделирование, 13:5 (2021), 947–963
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm927 https://www.mathnet.ru/rus/crm/v13/i5/p947
|
Статистика просмотров: |
Страница аннотации: | 84 | PDF полного текста: | 43 | Список литературы: | 21 |
|