A novel catalyst scheme for stochastic minimax optimization

• 成果类型: Article; Early Access
• 署名作者: Lan, Guanghui; Li, Yan
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02309-x
• 发表日期: 2026-01-12
• 关键词: Minimax optimization; Accelerated proximal point; iteration complexity; Sample Complexity; PROXIMAL EXTRAGRADIENT METHOD; variational-inequalities; CONVERGENCE; algorithms

摘要

This paper presents a proximal-point-based catalyst scheme for simple first-order methods applied to convex minimization and convex-concave minimax problems. In particular, for smooth and (strongly)-convex minimization problems, the proposed catalyst scheme, instantiated with a simple variant of stochastic gradient method, attains the optimal rate of convergence in terms of both deterministic and stochastic errors. For smooth and strongly-convex-strongly-concave minimax problems, the catalyst scheme attains the optimal rate of convergence for deterministic and stochastic errors up to a logarithmic factor. To the best of our knowledge, this reported convergence seems to be attained for the first time by stochastic first-order methods in the literature. We obtain this result by designing and catalyzing a novel variant of stochastic extragradient method for solving smooth and strongly-monotone variational inequality, which may be of independent interest.