350. Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity
Invited abstract in session WC-6: Advances in monotone inclusions and related methods, stream Methods for non-/monotone inclusions and their applications.
Wednesday, 10:05 - 11:20Room: M:H
Authors (first author is the speaker)
| 1. | Ahmet Alacaoglu
|
| University of British Columbia | |
| 2. | Donghwan Kim
|
| KAIST | |
| 3. | Stephen Wright
|
| Computer Science, University of Wisconsin - Madison |
Abstract
In this talk, we revisit the analysis of inexact Halpern and Krasnosel'skii-Mann (KM) iterations for solving constrained and stochastic min-max problems. First, we relax the inexactness requirement on the computation of the resolvent in Halpern iteration. Second, we analyze the stochastic KM iteration with the multilevel Monte-Carlo estimator which allows obtaining almost-unbiased samples of the resolvent. We present the consequences of these results in the case of constrained and stochastic convex-concave min-max problems. Then, we apply our developments to solve constrained nonconvex-nonconcave min-max problems either satisfying (i) $\rho$-cohypomonotonicity or (ii) the assumption of the existence of a solution to the $\rho$ weak Minty Variational inequality. Our results help go beyond the existing barrier of $1/(2L)$ for the upper bound of $\rho$ parameter (that roughly determines the level of nonconvexity in the problem) in the literature of first-order algorithms for these problems. We extend this upper bound to $1/L$ while preserving the optimal first-order complexity for both deterministic and stochastic versions of the problem.
Keywords
- SS - Advances in Nonlinear Optimization and Applications
- Complementarity and variational problems
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers