Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems

Guangzeng Xie, Luo Luo, Yijiang Lian, Zhihua ZhangICML 2020 · OpenReview

Minimax optimization—finding a "saddle point" where one variable minimizes a function while another maximizes it—is the mathematical engine behind Generative Adversarial Networks (GANs), robust optimization, and reinforcement learning. In the modern machine learning landscape, these objective functions are typically formulated as a finite sum of $n$ individual components, representing individual data points.

To handle massive datasets, practitioners rely on stochastic or incremental algorithms that process one component at a time rather than computing the full gradient. While the upper bounds (the performance of existing algorithms) are well-documented, the lower bounds—the absolute minimum number of iterations any algorithm must take to reach a solution—have remained elusive. Previous lower bound analyses either ignored the finite-sum structure entirely or focused solely on simple minimization, neglecting the complex "tug-of-war" dynamics of minimax problems.

This paper establishes the first tight lower complexity bounds for stochastic first-order algorithms solving finite-sum convex-concave minimax problems, providing a fundamental theoretical "speed limit" for this crucial class of optimization.

Constructing the "Hardest" Problem

To prove a lower bound, the authors analyze algorithms that interact with the problem via a Proximal Incremental First-order Oracle (PIFO). This oracle allows an algorithm to pick one component of the sum and receive its gradient or perform a proximal operation, which accounts for the function's local geometry.

The researchers constructed a "hard" objective function specifically designed to be as difficult as possible for any PIFO-based algorithm. Their key innovation is a novel partitioning strategy:

  1. They begin with Nesterov’s classic tridiagonal matrix, a standard mathematical tool for proving lower bounds in minimization.
  2. They partition the rows of this matrix into $n$ distinct groups.
  3. This structure forces any incremental algorithm to "wait" until it randomly samples the specific component required to make progress on the next dimension of the problem.

By analyzing the probability of sampling these specific components, the authors mathematically bounded how slowly an algorithm's knowledge of the solution space can expand. This demonstrated that the difficulty of finite-sum minimax problems is dictated not just by the "condition number" (the skew of the function) but also by a fundamental sampling bottleneck. Furthermore, because the bounds hold even for the powerful PIFO oracle, it proves that having access to proximal information does not fundamentally bypass this bottleneck.

The Theoretical Speed Limits

The paper establishes lower bounds for three primary optimization regimes, where $n$ is the number of components, $L$ is smoothness, $\mu$ is strong convexity, and $\epsilon$ is the desired accuracy:

  1. Strongly-Convex-Strongly-Concave: The complexity is at least $\Omega\left((n + \frac{L}{\mu}) \log(1/\epsilon)\right)$. This confirms that the computational cost scales linearly with both the data size and the condition number. Notably, this lower bound matches the performance of the existing Stochastic Primal-Dual Coordinate (SPDC) algorithm for certain bilinear problems, proving that SPDC is mathematically optimal in those specific scenarios.
  2. Convex-Strongly-Concave: The complexity is at least $\Omega\left(n + \frac{R_x L}{\sqrt{\mu \epsilon}}\right)$.
  3. General Convex-Concave: The complexity is at least $\Omega\left(n + \frac{L R_x R_y}{\epsilon}\right)$.

These results provide a rigorous theoretical benchmark against which all future stochastic minimax algorithms must be measured.

Open Questions and Future Directions

While this work lays a critical theoretical foundation, it also highlights several exciting frontiers for future research:

  • The $\sqrt{n}$ Gap: In the general strongly-convex-strongly-concave case, a gap of $\sqrt{n}$ remains between this paper's lower bound and the best-known upper bounds for general functions (which often scale with $\sqrt{n}L/\mu$). It remains an open question whether the lower bound can be tightened further, or if an undiscovered, more efficient algorithm exists that can close this gap.
  • Algorithm Discovery: For the general convex-concave cases, no current stochastic algorithm reaches the newly established lower bounds. This strongly suggests that there is still significant room for innovation in algorithm design.
  • The Non-Convex Frontier: The current analysis is strictly limited to convex-concave functions. Because many modern machine learning applications—most notably GANs—are highly non-convex, extending these lower bounds to the non-convex regime represents a major, highly anticipated next step for the field.

Summary updated

Abstract

This paper studies the lower bound complexity for minimax optimization problem whose objective function is the average of $n$ individual smooth convex-concave functions. We consider the algorithm w...
BibTeX
@inproceedings{xie2020lower,
  author = {Guangzeng Xie and Luo Luo and Yijiang Lian and Zhihua Zhang},
  title = {{Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=CS9XN-x1wvA},
}
Figure