Complexity bounds for finite-sum nonconvex strongly concave optimization

Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization

Machine Learning

Summary

Optimizing complex systems that involve both minimizing and maximizing objectives is important in many fields, but understanding how hard this task is can be tricky. The authors measure the number of steps needed to solve a specific type of problem where the minimizing side is nonconvex and the maximizing side is strongly concave, focusing on problems made up of many terms (finite sums). They provide nearly exact formulas for this complexity, showing both lower and upper limits. They also propose a new method for certain cases that matches their theoretical bounds, helping clarify what is possible when designing algorithms for these problems.

What this means in practice

  • For machine learning engineers: Design efficient algorithms for training models involving adversarial or game-theoretic setups with many data points and complex nonconvex structures.
  • For optimization software developers: Develop optimization tools that adapt query budgets optimally when solving large-scale minimax problems with varying condition numbers.

A theory result. No direct application yet.

Authors

Qihao Zhou

Abstract

We characterize, up to logarithmic factors, the minimax expected query complexity of finite-sum nonconvex-strongly-concave optimization under mean-squared averaged smoothness. For randomized zero-respecting incremental first-order algorithms, the complexity is $\tildeΘ(n+\min\{\sqrt{n}\,κ,n^{3/4}\sqrtκ\}\,LΔ\varepsilon^{-2})$ throughout $κ=L/μ\ge1$, under exact dual initialization and for $0<\varepsilon^2\le c_0LΔ$, where $c_0>0$ is universal. This characterization is our main result. A dual-chain construction provides the lower bound and matches the existing Catalyst upper bound for $κ\ge\sqrt{n}$. For $1\leκ\le\sqrt{n}$, we introduce recursive proximal descent-ascent (RPDA), which retains a recursive gradient estimator across proximal subproblems and attains $\tilde{O}(n+\sqrt{n}\,κLΔ\varepsilon^{-2})$ with a fixed query budget. Both upper bounds guarantee an expected squared primal gradient at most $\varepsilon^2$. Under individual smoothness, we also prove $Ω(n+\min\{κ,\sqrt{nκ}\}\,LΔ\varepsilon^{-2})$ for every $κ\ge1$. It matches the polynomial upper rate for a bilinear subclass when $κ\ge n$; the intermediate-condition-number gap remains open.
View PDFOpen arXiv