{
  "abstract": "We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an $L$-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most $D_Y$, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most $Δ$. The target accuracy $\\varepsilon$ is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter $1/(2L)$. Under an unbiased stochastic first-order oracle with variance at most $σ^2$ and mean-square smoothness, we prove the lower bound $Ω\\!\\left(L^2D_YΔ\\varepsilon^{-3}+L^3D_Y^2Δσ^2\\varepsilon^{-6}\\right)$. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter $μ>0$ and condition number $κ:=L/μ$, we obtain $Ω\\!\\left(LΔ\\sqrtκ\\,\\varepsilon^{-2}+LΔκσ^2\\varepsilon^{-4}\\right)$ under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant $\\bar L$, we obtain $Ω\\!\\left(LΔ\\sqrtκ\\,\\varepsilon^{-2}+Δ\\bar Lσκ^{3/2}\\varepsilon^{-3}\\right)$. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.01662",
  "author_total": 2,
  "authors": [
    {
      "name": "Jiayi Song"
    },
    {
      "name": "Zi Xu"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/cmc5p5r2c5qt6.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.01662",
  "fulltext_url": null,
  "id": "cmc5p5r2c5qt6",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.01662",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "stat.ML"
    ],
    [
      "openalex",
      "1702|Stochastic Gradient Optimization Techniques"
    ]
  ],
  "openalex": "W7215972262",
  "pdf_url": "https://arxiv.org/pdf/2610.01662",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-01",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/cmc5p5r2c5qt6.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:26:07Z",
      "native_id": "2610.01662",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.01662"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:stat.ML",
      "subfield": "statistics"
    }
  ],
  "title": "Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization",
  "title_text": "Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization",
  "type": "preprint",
  "updated_at": "2026-11-05T15:20:35Z",
  "url": "https://research.draconitic.com/paper/cmc5p5r2c5qt6",
  "venue": "arXiv",
  "versions": []
}