Fast adaptive by constants of strong-convexity and Lipschitz for gradient first order methods

Работа посвящена построению эффективных и применимых к реальным задачам методов выпуклой оптимизации первого порядка, то есть использующих только значения целевой функции и ее производных.При построении используется быстрый градиентный метод OGM-G, который является оптимальным по оракульной сложности (числу вычислений градиента целевой функции), но при запуске требует знания констант сильной выпуклости и Липшица градиента для вычисления количества шагов и длины шага, требуемых для достижения заданной точности.Данное требование усложняет практическое использование метода.Предлагаются адаптивный по константе сильной выпуклости алгоритм ACGM, основанный на рестартах OGM-G с обновлением оценки константы сильной выпуклости, и адаптивный по константе Липшица градиента метод ALGM, в котором применение рестартов OGM-G дополнено подбором константы Липшица с проверкой условий гладкости, используемых в методе универсального градиентного спуска.При этом устраняются недостатки исходного метода, связанные с необходимостью знания данных констант, что делает возможным практическое использование.Доказывается, что оценки сложности построенных алгоритмов являются оптимальными с точностью до числового множителя.Для проверки полученных результатов проводятся эксперименты на модельных функциях и реальных задачах машинного обучения.