2023/11/06 by Guanghui Lan, Yan Li, Lan, Guanghui +1 · 4 citations
Computer Science · Engineering · Mathematics · #Applied mathematics #Computer science #Convergence (economics) #Convex optimization #FOS: Mathematics #Logarithm #Mathematical analysis #Mathematical optimization #Mathematics #Minification #Minimax #Monotone polygon #Optimization and Control (math.OC) #Optimization and Variational Analysis #Rate of convergence #Regular polygon #Scheme (mathematics) #Simple (philosophy) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Stochastic optimization
paper · pdf · doi:10.48550/arxiv.2311.02814
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.