Research map / Optimization / Nonconvex and smooth optimization
Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a PIFO (proximal incremental first-order oracle) algorithm instead of full-gradient/exact-prox deterministic methods for finite-sum strongly-convex-strongly-concave minimax | finite-sum minimax problem with n components · strongly-convex-strongly-concave, L-smooth components | PIFO query complexity to reach epsilon-saddle point | No clear effect |
| Lower-bound construction partitions Nesterov's tridiagonal matrix into n groups; the lower bound for strongly-convex-strongly-concave finite-sum problems is Omega(n + L/mu) log(1/eps) | PIFO lower bound · strongly-convex-strongly-concave finite-sum minimax | PIFO queries lower bound | No clear effect |
| Lower bound for convex-strongly-concave finite-sum case: Omega(n + R_x L / sqrt(mu eps)) PIFO queries | PIFO lower bound · convex-strongly-concave finite-sum minimax | PIFO queries lower bound | No clear effect |
| Lower bound for general convex-concave finite-sum case: Omega(n + L R_x R_y / eps) queries | PIFO lower bound · general convex-concave finite-sum minimax | queries lower bound | No clear effect |
| Known upper bound O(n + sqrt(n) L/mu) log(1/eps) for IFO/PIFO leaves a sqrt(n) gap to the lower bound in general strongly-convex-strongly-concave case | existing algorithms (Palaniappan & Bach 2016; Luo et al. 2019) · strongly-convex-strongly-concave finite-sum minimax | query complexity gap | No clear effect |
| SPDC (stochastic primal-dual coordinate) matches the lower bound on a specific bilinear problem with mu_x = mu_y/n = mu | SPDC (Zhang & Xiao 2017) · specific bilinear finite-sum strongly-convex-strongly-concave case | PIFO query complexity | No clear effect |
Closest papers by meaning
- Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization (NeurIPS 2021 · similarity 0.94)
- Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness (NeurIPS 2021 · similarity 0.91)
- The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization (NeurIPS 2022 · similarity 0.91)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.90)
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization (NeurIPS 2024 · similarity 0.89)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.