CLS Hardness of 2D Min-Max Optimization with Product Constraints

1 Introduction

• Earlier PPAD-hardness for first-order Nash points used coupled constraints, while this paper studies product constraints.The cited prior work also establishes existence of first-order Nash equilibria for nonconvex, nonconcave objectives.Source: §1 · pp. 1–2
• For convex-concave objectives with compact constraints, solutions are guaranteed and can be computed by convex programming; smooth instances admit first-order methods.The paper contrasts this tractable setting with nonconvex, nonconcave min-max optimization.Source: §1 · p. 2
• The paper focuses on approximate GDA fixed points when both constraint sets are subsets of the real line, a setting the introduction identifies as an open question.It relates approximate first-order Nash conditions to approximate fixed points of the gradient descent-ascent map.Source: §1 · p. 2
• The paper establishes CLS-hardness with white-box access and an Ω(1/√ε) deterministic query lower bound with black-box access.The black-box oracle returns function and gradient values; white-box access gives a Turing machine computing them.Source: §1 · p. 2
• Prior tractable solution concepts resemble correlated equilibria and are described as bypassing the hardness result.The introduction also distinguishes this work from high-dimensional hardness results: its results hold in two dimensions for broader smooth objectives.Source: §1 · p. 3

2 Preliminaries

• The two-dimensional setting has one real variable per player, and white-box instances use rational inputs with exact function and gradient evaluation under an L-Lipschitz, M-smooth promise.The evaluation machine runs in polynomial time in its description length and the input bit length.Source: §2 · p. 4
• Unsafe GDA projects the two coordinates individually and can leave the constraint set, while safe GDA projects jointly; their fixed-point problems are computationally equivalent.The paper uses the unsafe map for a cleaner presentation.Source: §2 · p. 4
• EOPL asks for a non-isolated source or sink other than a distinguished source in an acyclic graph whose potential increases along directed paths.Its consistent circuit formulation is polynomial-time equivalent to standard EOPL, and EOPL characterizes CLS.Source: §2 · p. 5

3 Main Contributions

• The two-dimensional GDA fixed-point problem is CLS-hard, combining KKT-hardness techniques with the EOPL characterization of CLS.The proof compares its construction with prior approaches and introduces GDA-specific path gadgets and boundary analysis.Source: §3 · p. 6
• Every sufficiently accurate approximate GDA fixed point must lie in a region encoding an EOPL solution, including when projection is active near the boundary.The construction uses new path gadgets adapted to descent in x and ascent in y.Source: §3 · p. 6
• Ω(N) oracle queries are required in the worst case to find a 0.01-approximate GDA fixed point for a 100N-smooth instance on [0,N]^2.The lower bound applies to deterministic algorithms with access to function and gradient evaluation oracles.Source: §3 · p. 6

Taking Euclidean norms gives

• Ω(ε^-1/2) queries are required for an ε-approximate GDA fixed point on the unit square after rescaling the query lower bound.The rescaling preserves learning rate 1 and yields an O(1)-smooth function.Source: §3 · p. 6, Taking Euclidean norms gives · p. 7
• The query-rate tradeoff for first-order Nash points depends on normalization: constant smoothness gives Ω(ε^-1/3), while Ω(ε^-1/2) requires O(N) smoothness.The paper notes that first-order Nash points and approximate GDA fixed points need not have the same approximation accuracy.Source: Taking Euclidean norms gives · pp. 7–8

4 Proof Outline

• The geometric novelty is a class of hard functions that encodes End-Of-Potential-Line instances, while the complexity-theoretic reduction follows prior-work blueprints.The proof combines techniques from and [GHJ+22].Source: §4 · p. 8
• Each hard function follows a monotone path from the bottom-left tile through right-or-up moves to a sink, where the only constant-accuracy approximate GDA fixed point lies.The functions have Lipschitz constant L and smoothness M satisfying L, M ≳ N.Source: §4 · p. 8
• The construction assigns grid-point values through three colors and assembles six path gadgets for straight moves, turns, source, and sink.The gadget coloring also specifies gradient directions; their design is identified as a main contribution.Source: §4 · pp. 9–10
• Bicubic interpolation extends the grid-defined function to the continuous square, while the off-path environment uses black points and boundary-directed decreases.The construction first defines the function on the grid and fills the remaining region as environment.Source: §4 · pp. 9–10, Figure 1 · p. 9
• The proof must rule out spurious fixed points when GDA projections activate, since the KKT-based argument only handles points where projections are inactive.For inactive-projection points, GDA fixed points coincide with 2D KKT points; the active-projection cases require separate gadget analysis, including checking that interpolation introduces no fixed points.Source: §4 · p. 10

4.1 Query Lower Bound

• The monotone-path family also yields a query lower bound for deterministic algorithms computing approximate GDA fixed points.The passage refers to Section 6 for the statement and details.Source: §4.1 · p. 11

5.2 Step II: From Monotone Paths to Functions on Grids

• Each embedded instance yields a function whose approximate GDA fixed points correspond exactly to EOPL sinks and non-distinguished sources, with function values decreasing toward paths.Source: §5 · p. 11

5 CLS hardness of 2D Min-Max with Product Constraints

• Theorem 9 reduces EOPL to 2d-GDAFixedPoint, yielding white-box CLS-hardness because EOPL = CLS.The reduction uses polynomial-time evaluators for the function and its gradient and converts 0.01-approximate fixed points into EOPL solutions.Source: §5 · p. 11

5.1 Step I: Embedding EOPL in 2D Grid

• Potential-and-label ranks place vertices diagonally; padding reserves boundary space for the distinguished source, while edges route right then up as monotone paths.Source: §5.1 · p. 12

5.2.1 Defining the function values

• Three color regimes assign function values to grid points, with color 1 above color 0 and color 0 above color 2 by gaps of at least 10.Source: §5.2.1 · p. 14

5.2.2 Path gadgets, coloring of the grid, and monotone paths

• The construction uses 6 × 6 gadgets that encode grid-point function values and negative-gradient directions consistently with monotone paths.Source: §5.2.2 · p. 14

5.2.3 Path Formulation

• Path tiles form right-and-up routes whose endpoint fixed points represent valid EOPL solutions, while the distinguished input source is routed internally to avoid creating a solution.Source: §5.1 · p. 13, §5.2.3 · pp. 15–16

5.2.4 Handling Path Crossings

• Crossings between two paths are resolved by local rerouting that preserves the original solutions and introduces no new GDA fixed points.Source: §5.2.4 · p. 19
• The path-crossing rerouting connects the left entrance to the top exit and the bottom entrance to the right exit without adding an endpoint.Untraversed sub-squares, including isolated EOPL vertices, receive the background coloring.Source: §5.2.4 · p. 19

5.3 Extending the function to the continuous grid

• Bicubic interpolation yields a continuously differentiable function whose value and gradient are Lipschitz-continuous with constant Θ(N) on [0, N]^2.The construction interpolates each tile using corner values and derivatives.Source: §5.3 · p. 20

5.4 Correctness

• For ε = 0.01, good approximate GDA fixed points can occur only in sink or non-trivial source sub-squares, while bad points cannot be approximate fixed points.Bad points that are approximate fixed points would have to lie in the ε-outer layer, where the construction excludes them.Source: §5.4 · p. 22, §5.4.2 · p. 24

5.4.1 Analysis of Good Points

• Good points outside sink and non-trivial source sub-squares are not ε-approximate fixed points; the proof classifies other small squares into four configuration groups.Each group’s bicubic interpolant excludes interior ε-KKT points.Source: §5.4.1 · p. 22

5.4.2 Analysis of Non-Good Points

• Any bad point that is an ε-approximate GDA fixed point must lie in the ε-outer layer, but the construction has no such fixed points there.The boundary analysis checks the eight small squares in that layer.Source: §5.4.2 · p. 24

5.5 Completing the reduction

• The construction completes a polynomial-time reduction to 2D-GDAFixedPoint on [0, 1]^2 and recovers an EOPL solution from any solution of the constructed instance.The function and gradient evaluators, normalized instance, and recovery procedure have polynomial description length or running time.Source: §5.5 · p. 25

6 Query Lower Bound for Finding Fixed Points of GDA

• Every function in the hard family has 0.01-approximate GDA fixed points only in its sink sub-square.Source: §6 · p. 25
• For N > 145, every deterministic algorithm needs Ω(N) oracle queries in the worst case to find a 0.01-approximate GDA fixed point, even for 100N-smooth functions.Source: §6 · p. 26
• The adversary adaptively grows two monotone paths that agree at query points, with each function-and-gradient query simulable by at most four local tile queries.Source: §6 · p. 26
• Known-region queries leave the path unchanged; northeast queries forbid turns in that row and column, while track queries extend the path and redirect its track.Source: §6 · pp. 27–28
• After q ≤ K−7 queries, two completions can remain indistinguishable while having disjoint sets of 0.01-approximate GDA fixed points.The completions alter only unqueried tiles and use different sink squares.Source: §6 · p. 28

AI Disclosure

• The authors report completing the conceptual and technical work by December 2025 without AI assistance, then using AI to streamline writing, find typos, and verify proofs.Source: AI Disclosure · p. 28

A Proof of Lemma 28

• Bad points of the function associated with an EOPL instance are not ε-approximate GDA fixed points.Source: A Proof of Lemma 28 · p. 31
• The analysis uses local coordinates within each small square, but projection is onto the full domain [0, N]^2.Source: A Proof of Lemma 28 · p. 32
• A bad ε-approximate fixed point must be within ε of a domain boundary where projection is active.Source: A Proof of Lemma 28 · p. 32

A.1 Type 0 squares

• A type 0 square contains no ε-approximate GDA fixed point.Source: §A.1 · p. 32
• Type 0 squares lie along the left boundary and do not meet the bottom boundary.Source: §A.1 · p. 32, Figure 15 · p. 32
• A bad approximate fixed point would require projection at the left boundary, hence x ≤ 0.01; its projected vertical displacement is then at least 0.49 > ε.Source: §A.1 · p. 32

A.2 Type 1 squares

• A type 1 square contains no ε-approximate GDA fixed point.Source: §A.2 · p. 33
• Type 1 squares occur away from the left boundary, including at the bottom, top, and right boundaries, and in the interior.Source: §A.2 · p. 33, Figure 16 · p. 33
• In a type 1 square, f_x(x, y) ≥ 0.5, so the projected horizontal displacement is at least 0.5 > ε.Source: §A.2 · p. 33

• A type 2 square contains no ε-approximate fixed point of GDA.Source: §A.3 · p. 33
• For type 2 squares, the corner-value difference D is nonnegative under the value regimes of Section 5.2.1.D is the value at the blue bottom-right corner minus the value at the black top-left corner.Source: §A.3 · pp. 33–34
• Because the square does not meet the bottom boundary, its projected vertical displacement is at least 0.49, exceeding ε.The argument considers 0 ≤ x ≤ 0.01 and 0 ≤ y ≤ 1.Source: §A.3 · pp. 33–34

• A type 3 square contains no ε-approximate fixed point of GDA.Source: §A.4 · p. 34
• The argument concerns type 3 squares meeting the left boundary and restricts attention to x ≤ 0.01.Source: §A.4 · p. 34, Figure 18 · p. 34
• For y ≤ 0.5, the rightward displacement is at least 0.2; for y ≥ 0.5, the downward displacement is at least 0.45.The respective bounds follow from f_x ≤ −0.2 with at least 0.99 remaining to the right, or f_y ≤ −0.45 with at least half a unit below.Source: §A.4 · p. 34

• A type 4 square contains no ε-approximate fixed point of GDA.Source: §A.5 · p. 34
• The proof focuses on type 4 squares meeting the left boundary.Source: §A.5 · p. 34, Figure 19 · p. 35
• The corner-value regimes give 6f(1, 1) − 6f(0, 0) + 4.5 ≥ 0, and the argument considers x ≤ 0.01.Here f(0, 0) and f(1, 1) are the bottom-left and top-right corner values.Source: §A.5 · pp. 34–35
• For y ≤ 0.5, the upward displacement is at least 0.24; for y ≥ 0.5, the rightward displacement is at least 0.19.The bounds use f_y ≥ 0.24 with at least half a unit above, or f_x ≤ −0.19 with at least 0.99 remaining to the right.Source: §A.5 · p. 35

A.6 Type 5 squares

• Type 5 squares contain no ε-approximate fixed point of GDA; their projected vertical displacement is at least 0.45 because they do not meet the top boundary.Source: §A.6 · p. 35, Figure 20 · p. 35

A.7 Type 6 squares

• For type 6 squares, bottom-boundary projection cannot be active, while top-boundary projection gives displacement at least 1; a bad point would require the left boundary and x ≤ 0.01.At those points, the projected vertical displacement is at least 0.45 because the square does not meet the top boundary.Source: §A.7 · p. 36, Figure 21 · p. 36

A.8 Type 7 squares

• Type 7 squares contain no ε-approximate fixed point of GDA, and their eight cases complete the outer-layer proof.The square does not meet the top boundary, so projected vertical displacement is at least 0.45.Source: §A.8 · pp. 36–37, Figure 22 · p. 37
• The square [1, 2] × [0, 1] is outside the listed types but is directly checked to contain no approximate GDA fixed point.It has green left corners, black right corners, and four left-pointing arrows.Source: §A.8 · p. 37