Accelerated Bregman gradient methods for relatively smooth and relatively Lipschitz continuous minimization problems

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We propose some accelerated methods for solving optimization problems under the condition of relatively smooth and relatively Lipschitz continuous functions with inexact oracle. We consider the problem of minimizing a convex, differentiable, and relatively smooth function relative to a reference convex function. The first proposed method is based on a similar triangles method with inexact oracle, which uses a special triangular scaling property of the Bregman divergence used. The other proposed methods are non-adaptive and adaptive (tuning to the relative smoothness parameter) accelerated Bregman proximal gradient methods with inexact oracle. These methods are universal in the sense that they apply not only to relatively smooth but also to relatively Lipschitz continuous optimization problems. We also introduce an adaptive intermediate Bregman method, which interpolates between slower but more robust non-accelerated algorithms and faster but less robust accelerated algorithms. We conclude the paper with the results of numerical experiments demonstrating the advantages of the proposed algorithms for the Poisson inverse problem.

About the authors

Oleg S.. Savchuk

Moscow Institute of Physics and Technology, Dolgoprudny, Russia; V. I. Vernadsky Crimean Federal University, Simferopol, Russia; Innopolis University, Innopolis, Russia

Email: oleg.savchuk19@mail.ru

Mohammad Soud Alkousa

Innopolis University, Innopolis, Russia

Email: m.alkousa@innopolis.ru

Andrei Igorevich Shushko

Moscow Institute of Physics and Technology, Dolgoprudny, Russia

Email: shushko.ai@phystech.edu; shushko.and@gmail.com

Aleksandr A.. Vyguzov

Moscow Institute of Physics and Technology, Dolgoprudny, Russia; Innopolis University, Innopolis, Russia

Email: avyguzov@yandex.ru

Fedor Sergeevich Stonyakin

Moscow Institute of Physics and Technology, Dolgoprudny, Russia; V. I. Vernadsky Crimean Federal University, Simferopol, Russia; Innopolis University, Innopolis, Russia

Email: fedyor@mail.ru
Candidate of physico-mathematical sciences, Associate professor

Dmitry Arkad'evich Pasechnyuk

Ivannikov Institute for System Programming of the Russian Academy of Sciences, Research Center for the Trusted Artificial Intelligence, Moscow, Russia

Email: pasechnyuk2004@gmail.com
without scientific degree, no status

Alexander Vladimirovich Gasnikov

Moscow Institute of Physics and Technology, Dolgoprudny, Russia; Ivannikov Institute for System Programming of the Russian Academy of Sciences, Research Center for the Trusted Artificial Intelligence, Moscow, Russia; Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia

Email: gasnikov@yandex.ru
ORCID iD: 0000-0002-7386-039X
Scopus Author ID: 15762551000
ResearcherId: L-6371-2013
Doctor of physico-mathematical sciences, Associate professor

References

  1. C. L. Atwood, “Optimal and efficient designs of experiments”, Ann. Math. Statist., 40:5 (1969), 1570–1602
  2. A. Auslender, M. Teboulle, “Interior gradient and proximal methods for convex and conic optimization”, SIAM J. Optim., 16:3 (2006), 697–725
  3. H. H. Bauschke, J. Bolte, M. Teboulle, “A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications”, Math. Oper. Res., 42:2 (2017), 330–348
  4. A. Beck, First-order methods in optimization, MOS–SIAM Ser. Optim., 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society (MOS), Philadelphia, PA, 2017, xii+475 pp.
  5. A. Beck, M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems”, SIAM J. Imaging Sci., 2:1 (2009), 183–202
  6. A. Ben-Tal, A. Nemirovski, Lectures on modern convex optimization. Analysis, algorithms, and engineering applications, MPS/SIAM Ser. Optim., 2, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Programming Society (MPS), Philadelphia, PA, 2001, xvi+488 pp.
  7. J. Bergstra, Y. Bengio, “Random search for hyper-parameter optimization”, J. Mach. Learn. Res., 13 (2012), 281–305
  8. M. Bertero, P. Boccacci, G. Desiderà, G. Vicidomini, “Image deblurring with Poisson data: from cells to galaxies”, Inverse Problems, 25:12 (2009), 123006, 26 pp.
  9. L. Bogolubsky, G. Gusev, A. Raigorodskii, A. Tikhonov, M. Zhukovskii, P. Dvurechenskii, A. Gasnikov, Yu. Nesterov, “Learning supervised pagerank with gradient-based and gradient-free optimization methods”, NIPS {'}16: Proceedings of the 30th conference on neural information processing systems, Adv. Neural Inf. Process. Syst., 29, Curran Associates Inc., Red Hook, NY, 2016, 4914–4922
  10. L. Bottou, F. E. Curtis, J. Nocedal, “Optimization methods for large-scale machine learning”, SIAM Rev., 60:2 (2018), 223–311
  11. Gong Chen, M. Teboulle, “Convergence analysis of a proximal-like minimization algorithm using Bregman functions”, SIAM J. Optim., 3:3 (1993), 538–543
  12. I. Csiszar, “Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems”, Ann. Statist., 19:4 (1991), 2032–2066
  13. O. Devolder, F. Glineur, Yu. Nesterov, Intermediate gradient methods for smooth convex problems with inexact oracle, CORE Discussion Paper 2013/17, CORE, UCL, Louvain-la-Neuve, 2013, 47 pp.,
  14. O. Devolder, F. Glineur, Yu. Nesterov, “First-order methods of smooth convex optimization with inexact oracle”, Math. Program., 146:1-2, Ser. A (2014), 37–75
  15. R.-A. Dragomir, Bregman gradient methods for relatively-smooth optimization, PhD thesis, Univ. Toulouse 1 Capitole, 2021, ix+126 pp.,
  16. P. Dvurechensky, A. Gasnikov, “Stochastic intermediate gradient method for convex problems with stochastic inexact oracle”, J. Optim. Theory Appl., 171:1 (2016), 121–145
  17. F. Hanzely, P. Richtarik, Lin Xiao, “Accelerated Bregman proximal gradient methods for relatively smooth convex optimization”, Comput. Optim. Appl., 79:2 (2021), 405–440
  18. D. Kamzolov, P. Dvurechensky, A. V. Gasnikov, “Universal intermediate gradient method for convex problems with inexact oracle”, Optim. Methods Softw., 36:6 (2021), 1289–1316
  19. J. Kiefer, J. Wolfowitz, “Optimum designs in regression problems”, Ann. Math. Statist., 30:2 (1959), 271–294
  20. Haihao Lu, “ ‘Relative continuity’ for non-Lipschitz nonsmooth convex optimization using stochastic (or deterministic) mirror descent”, INFORMS J. Optim., 1:4 (2019), 288–303
  21. Haihao Lu, R. M. Freund, Yu. Nesterov, “Relatively smooth convex optimization by first-order methods, and applications”, SIAM J. Optim., 28:1 (2018), 333–354
  22. Yu. Nesterov, “Gradient methods for minimizing composite functions”, Math. Program., 140:1, Ser. B (2013), 125–161
  23. Yu. Nesterov, “Universal gradient methods for convex optimization problems”, Math. Program., 152:1-2, Ser. A (2015), 381–404
  24. Yu. Nesterov, Lectures on convex optimization, Springer Optim. Appl., 137, 2nd ed., Springer, Cham, 2018, xxiii+589 pp.
  25. Yu. Nesterov, “Implementable tensor methods in unconstrained convex optimization”, Math. Program., 186:1-2, Ser. A (2021), 157–183
  26. Yu. Nesterov, “Inexact accelerated high-order proximal-point methods”, Math. Program., 197:1, Ser. A (2023), 1–26
  27. F. Stonyakin, M. Alkousa, A. Titov, O. Savchuk, A. Gasnikov, “Adaptive algorithms for relatively Lipschitz continuous convex optimization problems”, Pure Appl. Funct. Anal., 8:5 (2023), 1505–1526
  28. F. Stonyakin, A. Tyurin, A. Gasnikov, P. Dvurechensky, A. Agafonov, D. Dvinskikh, M. Alkousa, D. Pasechnyuk, S. Artamonov, V. Piskunova, “Inexact model: a framework for optimization and variational inequalities”, Optim. Methods Softw., 36:6 (2021), 1155–1201
  29. M. Teboulle, “A simplified view of first order methods for optimization”, Math. Program., 170:1, Ser. B (2018), 67–96
  30. Yi Zhou, Yingbin Liang, Lixin Shen, “A simple convergence analysis of Bregman proximal gradient algorithm”, Comput. Optim. Appl., 73:3 (2019), 903–912

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2025 Savchuk O.S., Alkousa M.S., Shushko A.I., Vyguzov A.A., Stonyakin F.S., Pasechnyuk D.A., Gasnikov A.V.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».