Convergence Rate Bounds for the Mirror Descent Method: IQCs, the Popov Criterion and Bregman Divergence

Material type: 記事

Author: Li, Mengmouほか

Publisher: -

Publication date: 2025-01

Material Format: Paper

Journal name: Automatica 171

Publication Page: p.111973-

View All

Notes on use

Note (General)：: 出版タイプ： NAThis paper presents a comprehensive convergence analysis for the mirror descent (MD) method, a widely used algorithm in convex optimization. ...

Holdings of Libraries in Japan

This page shows libraries in Japan other than the National Diet Library that hold the material.

List of Cooperating Institutions and Databases

Please contact your local library for information on how to use materials or whether it is possible to request materials from the holding libraries.

other

Tokyo Tech Research Repository
Paper
You can check the holdings of institutions and databases with which Institutional Repositories DataBase(IRDB)(Institutional Repository) is linked at the site of Institutional Repositories DataBase(IRDB)(Institutional Repository).
Tokyo Tech Research Repository

Bibliographic Record

You can check the details of this material, its authority (keywords that refer to materials on the same subject, author's name, etc.), etc.

Paper

Material Type: 記事
Title: Convergence Rate Bounds for the Mirror Descent Method: IQCs, the Popov Criterion and Bregman Divergence
Author/Editor: Li, Mengmou
畑中, 健志
Hatanaka, Takeshi
Author Heading: Li, Mengmou
畑中, 健志
Hatanaka, Takeshi
Publication Date: 2025-01
Publication Date (W3CDTF): 2025
Periodical title: Automatica
No. or year of volume/issue: 171
Volume: 171
Pages: 111973-
Subject Heading: Mirror descent method
Bregman divergence function
Convergence rate
Popov criterion
Integral quadratic constraints
Linear matrix inequalities
Target Audience: 一般
Note (General): 出版タイプ： NA
This paper presents a comprehensive convergence analysis for the mirror descent (MD) method, a widely used algorithm in convex optimization. The key feature of this algorithm is that it provides a generalization of classical gradient-based methods via the use of generalized distance-like functions, which are formulated using the Bregman divergence. Establishing convergence rate bounds for this algorithm is in general a non-trivial problem due to the lack of monotonicity properties in the composite nonlinearities involved. In this paper, we show that the Bregman divergence from the optimal solution, which is commonly used as a Lyapunov function for this algorithm, is a special case of Lyapunov functions that follow when the Popov criterion is applied to an appropriate reformulation of the MD dynamics. This is then used as a basis to construct an integral quadratic constraint (IQC) framework through which convergence rate bounds with reduced conservatism can be deduced. We also illustrate via examples that the convergence rate bounds derived can be tight.
identifier:oai:t2r2.star.titech.ac.jp:50726999
Related Material (DOI): 10.1016/j.automatica.2024.111973
https://doi.org/10.1016/j.automatica.2024.111973
Data Provider (Database): 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）
https://irdb.nii.ac.jp
Original Data Provider (Database): 東京科学大学 : 東京科学大学リサーチリポジトリ(T2R2)