Stable Nonconvex-Nonconcave Training: Inexact Krasnosel’ski˘ı-Mann iterations

Table of Links

Abstract & Introduction

Related work

Setup

Inexact Krasnosel’ski˘ı-Mann iterations

Approximating the resolvent

Last iterate under cohypomonotonicity

Analysis of Lookahea

Experiments

Conclusion & limitations

Acknowledgements & References

4 Inexact Krasnosel’ski˘ı-Mann iterations

We note that also the extragradient+ (EG+) method of Diakonikolas et al. (2021), which converges for cohypomonotone and Lipschitz problems, can be seen as a Krasnosel’ski˘ı-Mann iteration on an extragradient step

where λ ∈ (0, 1). We provide a proof of EG+ in Theorem G.1 which extends to the constrained case using the construction from Pethick et al. (2022) but through a simpler argument under fixed stepsize.

Essentially, the IKM iteration leads to a conservative update that stabilizes the update using the previous iterate. This is the key mechanism behind showing convergence in the nonmonotone setting known as cohypomonotonicity. Very generally, it is possible to provide convergence guarantees for IKM when the following holds (Theorem C.1 is deferred to the appendix due to space limitations).