The optimistic gradient method is useful in addressing minimax optimization problems. Motivated by the observation that the conventional stochastic version suffers from the need for a large batch size on the order of $\mathcal{O}(\varepsilon^{-2})$ to achieve an $\varepsilon$-stationary solution, we introduce and analyze a new formulation termed Diffusion Stochastic Same-Sample Optimistic Gradient (DSS-OG). We prove its convergence and resolve the large batch issue by establishing a tighter upper bound, under the more general setting of nonconvex Polyak-Lojasiewicz (PL) risk functions. We also extend the applicability of the proposed method to the distributed scenario, where agents communicate with their neighbors via a left-stochastic protocol. To implement DSS-OG, we can query the stochastic gradient oracles in parallel with some extra memory overhead, resulting in a complexity comparable to its conventional counterpart. To demonstrate the efficacy of the proposed algorithm, we conduct tests by training generative adversarial networks.

通过引入和分析一种名为Diffusion Stochastic Same-Sample Optimistic Gradient (DSS-OG)的新形式，我们解决了传统随机版本需要较大批次的问题，并在更一般的非凸Polyak-Lojasiewicz (PL)风险函数设置下，证明了它的收敛性和对大批次问题的更紧的上限，并将所提出的方法的适用性扩展到分布式场景。为了实现DSS-OG，我们可以通过一些额外的内存开销并行查询随机梯度的预言机，导致其复杂性与传统的方法相当。通过训练生成对抗网络的测试，我们展示了所提出算法的有效性。

最小最大问题的扩散随机优化