| Title: |
Fast Optimistic Gradient Descent Ascent (OGDA) Method in Continuous and Discrete Time. |
| Authors: |
Boţ, Radu Ioan1 (AUTHOR) radu.bot@univie.ac.at, Csetnek, Ernö Robert1 (AUTHOR) robert.csetnek@univie.ac.at, Nguyen, Dang-Khoa1,2 (AUTHOR) dang-khoa.nguyen@univie.ac.at |
| Source: |
Foundations of Computational Mathematics. Feb2025, Vol. 25 Issue 1, p163-222. 60p. |
| Subject Terms: |
*DYNAMICAL systems, *HILBERT space, *EQUATIONS, *ALGORITHMS, *MONOTONE operators |
| Abstract: |
In the framework of real Hilbert spaces, we study continuous in time dynamics as well as numerical algorithms for the problem of approaching the set of zeros of a single-valued monotone and continuous operator V. The starting point of our investigations is a second-order dynamical system that combines a vanishing damping term with the time derivative of V along the trajectory, which can be seen as an analogous of the Hessian-driven damping in case the operator is originating from a potential. Our method exhibits fast convergence rates of order o 1 t β (t) for ‖ V (z (t)) ‖ , where z (·) denotes the generated trajectory and β (·) is a positive nondecreasing function satisfying a growth condition, and also for the restricted gap function, which is a measure of optimality for variational inequalities. We also prove the weak convergence of the trajectory to a zero of V. Temporal discretizations of the dynamical system generate implicit and explicit numerical algorithms, which can be both seen as accelerated versions of the Optimistic Gradient Descent Ascent (OGDA) method for monotone operators, for which we prove that the generated sequence of iterates (z k) k ≥ 0 shares the asymptotic features of the continuous dynamics. In particular we show for the implicit numerical algorithm convergence rates of order o 1 k β k for ‖ V (z k) ‖ and the restricted gap function, where (β k) k ≥ 0 is a positive nondecreasing sequence satisfying a growth condition. For the explicit numerical algorithm, we show by additionally assuming that the operator V is Lipschitz continuous convergence rates of order o 1 k for ‖ V (z k) ‖ and the restricted gap function. All convergence rate statements are last iterate convergence results; in addition to these, we prove for both algorithms the convergence of the iterates to a zero of V. To our knowledge, our study exhibits the best-known convergence rate results for monotone equations. Numerical experiments indicate the overwhelming superiority of our explicit numerical algorithm over other methods designed to solve monotone equations governed by monotone and Lipschitz continuous operators. [ABSTRACT FROM AUTHOR] |
|
Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Academic Search Complete |
|
Full text is not displayed to guests. |
Login for full access.
|
