This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.
翻译:本文介绍了一组以微小变异性(MVI)为特征的非混凝土的非混凝土问题。 与单色酮设置中的超梯度方法的现有结果不同,在微色酮设置中,再不可能采用递减的阶梯化。 这导致了各种办法,如增加每迭代的批量大小,但这种递增可能过于昂贵。 相反,我们提出的方法涉及两个阶梯化,每次迭代只需再进行一次甲骨文评估。 我们表明,可以保留一个固定的阶梯化,而仅采取第二个阶梯化以缩小,甚至在单色酮设置中也令人感兴趣。 几乎可以确定趋同,并且我们对这一组方案提供了统一的分析,其中含有已知的初色双混合梯度计算法的非线性概括。