Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics
Authors: Deep Patel
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Venue: NeurIPS 2025 spotlight ()
Keywords: game theory
min-max optimization
neural networks
learning theory
Primary area: theory
TL;DR: We provide the first convergence guarantees and overparameterization bounds for alternating gradient methods in a special class of nonconvex-nonconcave zero-sum games where both the players are shallow neural networks.

Abstract: Many emerging applications—such as adversarial training, AI alignment, and robust optimization—can be framed as zero-sum games between neural nets, with von Neumann–Nash equilibria (NE)  capturing the desirable system behavior. While such games often involve non-convex non-concave objectives, empirical evidence shows that simple gradient methods frequently converge, suggesting a hidden geometric structure. In this paper, we provide a theoretical framework that explains this phenomenon through the lens of \emph{hidden convexity} and \emph{overparameterization}. We identify sufficient conditions spanning initialization, training dynamics, and network width—that guarantee global convergence to a NE in a broad class of non-convex min-max games. To our knowledge, this is the first such result for games that involve two-layer neural networks. Technically, our approach is twofold: (a) we derive a novel path-length bound for alternating gradient-descent-ascent scheme in min-max games; and (b) we show that games with hidden convex–concave geometry reduce to settings satisfying two-sided Polyak–Łojasiewicz (PL) and smoothness conditions, which hold with high probability under overparameterization, using tools from random matrix theory.

Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics
Deep Patel and Hanmanouil-Vasieeie Vlatakis-Gkaragkounis
Department of Computer Science
University of Wisconsin-Madison {dbpatel5, vlatakis)@wisc. edu
Abstract
Many emerging applications- as adversarial training, Al alignment, and be framed as zero-sum games between neural nets, with von Neumann-Nash equilibria (NE) capturing the desirable system behavior: While such games often involve non-convex non-concave objectives, empirical evidence shows that simple gradient methods frequently converge, suggesting a hidden geometric structure. this paper, we provide a theoretical framework that explains this phenomenon through the lens of hidden convexity and overparameterizaatin.. We identify sufficient conditions conditions-spanning initialization, training dynamics, and network width-that guarantee global convergence to NE in broad class of non-convex min-max games. To our knowledge, this the first such result for games that involve two-layer neural networks. Technically, (a) we derive a novel path-length bound for the alternating gradient descent descent-ascent ascent scheme in min-max games; and (b) we show that the reduction from hidden con- vex-concave geometry to two-sided Dalyak-Lojasiewicc (PL) min-max condition hold with high probability under overparamettrrization, using tools from random matrix theory.
robust optimization
approach is twofold:
Introduction
At the Nobel Symposium marking the centennial of Game Theory [31, 83), key challenge was posed:
the development of systematic theory for non-convex games
spurred by the rapid growth of deep learning in incentive-aware multi-agent systems [104, 130]. Indeed, many influential modern Al systems built upon the fusion of foundational game-theoretic paaciples--prticulaar zero-sum games-with with the expressive capacity of neural networks. Notable examples include generative adversarial networks (GANs) [51], robust reinforcement learning [89], adversarial attacks [117], domain-invariant representation learning [44], distributionally robust optimization[77, 123], and multi-agent environments featuring natural language interactions, such as AI safety debates between large language models and verifier- crifier-prover prover systems [56, 16]. In these settings, the game-theoree theoretic framework provides natural and interpretable objective- typically an equilibrium solution endowed with strong normative appeal, such as the celebrated von Neumann minimax points [48] and Nash-Ras Rosen equilibria [80, 94].
At the same time, much of the remarkable progress at the intersection of deep learning and game theory stems from the capacity of deep models to operate effectively in environments with large, often continuous, state and action spaces. Iconic examples include Go [103], autonomous driving [102]. Texas Hold' fomd'em poker [15], and real-time strategy games such as StarCraft through AlphaStar [112].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Tackling such large-scale decision-men making problems has necessitated the combination of expressive architectures with catrrioonpppoiimtiiioooo based learning, replacing high-dimensional reward/value functions and strategy/policy spaces with trainable surrogates. Hence, these surrogates act as flexible intermediaries, enabling generalization across complex environments without exhaustive enumeration of action spaces, While theoretical focus has largely remained on linear approximators [121, 26), it is the nonlinear models- as kernels and deep neural networks-which in practice dramatically expand representational power [67, 58], allowing richer strategic behaviors. Thus, agents' policies are encoded through powerful approximators, and equilibrium learning unfolds through iterative parameter tuning (see Figure 1).
Ingus
Hiälen
Outpa
Output
Hidden
Input
Layer
Lavests)
Luyer
Layer
Figure 1: Illsstaatoon of a maze environment where each agent reason over space of action sequences. Instead of explicitly constructing and searching the full decision tree, a neural network implicitly encodes both the value of paths and the policy for navigation, learning an effective strategy dynamically without ever uncovering the complete structure of the maze.
Despite the empirical success, algorithms with provable convergence guarantees remain scarce. This unsurprising given that even in finite games, strong computational hardness results [22, 23, 32, 87] and dynamic impossibility theorems [78, 53, 52, 116. 46, 47] pose significant barriers. Notably, even in two-player zero-sum games whenee classical theory guarantees existence and efficient computation of minimax points via I.P duality [ [19] or optimistic first-order methods [120, 5]-these assurances collapse when modern deep-learning architectures, with their inherent non-convexity, are introduced [34, 10, 6]. Specifically: global solution concepts (e.g., von Neumann minimax, Nash equilibria) may fail exist; (ti) even when they do, tandem gradient-based methods often suffer from instability, cycling, or divergence, resulting in poor solutions. [33, 75, 35, 113].
Thus, the best hope for mitigating the practical impact of these worst-case hardness results lies in focusing on structured subclasses of games. It remains plausible that broad families non- concave games- rich enough to capture multi-agent interactions aammit tractable local or global equilibria.
Hidden convexity: promising direction. One compelling approach along this path is the emerging theory of hidden convex games [114, 79, 115, 99, 29]. simplest form, two players interact zero-sum game Loss Player,). but control only high-dimensions parameters 0, 6, through mappings Player, + (.pg()) and Player, + Map These mappings are smooth and known, allowing gradient-bas based training, but typically not efficiently invertible, reflecting the practical irreversibility of neural architectures. Consequently, while the latent game preserves convex-concave structure, the optimization landscape Loss( M Mapp. Map3) over control variables becomes highly non-convex [see 99, p. 26]. Although not every non-convex game admits such a structure, many practical applications naturally fit within this framework (see Appendix B). Rank collapse: the fragility of hidden convexity. A major criticism of the hidden convexity paradigm relies critically on the assumption that the Jacobian of the agents' mappings maintain uniformly bounded singular values throughout training. practice, such uniform bounds often fail, as real-world architectures may suffer from rank collapse or mear-singular behavior during optimization (see, e.g., [101, 43, 37]), undermining theoretical guarantees. When such degeneracies arise, convergence rates can deteriorate exponentially, and worst-case bounds may become vacuous. Even if Jacobian well-conditioning is achieved by random initialization, there are no assurances that it will be preserved as training evolves.
via a convex-concaa
These limitations underscore the need for explicit, open-box conditions-beyond abstract hidden mappings-tha explain the empirical success of efficient training in large-scale min-max settings. Whilst hidden convexity provides significant insights about these systems, it does not answer fundamental behavioral question:
Can appropriate architectural design, initialization protocols, and training dynamics jointly ensure efficient convergence in large-scale neural min-max gumes?
2

---

1.1 Setting and Main Contribution
Motivated by the above challenges, we provide- to the best of our knowledge the first quantitative convergence guarantees addressing the central question (*) under minimal assumptions. Formally, given input datasets Dr and DG, and latent strategy spaces Sp and Sg, we consider the hidden min-max problem
min BER
max LD(Fo.Go) (o) $ER"
RRb where Fa : R - (d)((S)) and G R44 + Rdim(Se) are smooth mappings parameterized by
O and (e.g.. neural network weights). While our results extend beyond, focus on well-studied [127] separable latent minmax objectives of the form
- LD(F,G) = (F) - 1- (G),,,
(1)
where D = (Dp, 1Dp,Dol DG) and 1,"" 11 De the individual components are strongly convex and smooth, and 1 the coupling component- is smooth bilinear. As convergence metric, we adopt the Nash gap (also known as the Nikaido-Isoda duality gap [82]):
DG (0, == max LD Fo, G - min LD LD(For Go);
or
and say that (0, .) is an c-saddle (or c-approximate minimax or Nash equilibrium) if C. Sc.
Remarks. Replacing players' actions with neural nets-iee., Fg = NNo(-) and G. (N renders the end-to-end landscape highly non-convex, although the latent game L remains con- vex-concave. The separable structure naturally unifies several hidden zero-sum regimes: when I2 vanishes, it recovers separable coonngly-covee-coneee
games; when I and 13 vanish, it reduces to bilinear games [114]; and when both components are present. it captures regularized games (c.g., Tikhonov- or cerroy-reggulrized settings), recently used in hidden min-max frameworks, including team and zero-sum Markov games [59, 60]. We discuss concrete examples in Section and Appendix B. In these settings, regularization plays critical role in stabilizing dynamics and mitigating chaotic behaviors, both empirically ([see 99, p. 26]) and theoretically (cf. [115, pp. 7-8], [59]). Before enumerating our techincal contributions, we highlight a key result addressing (*)):
Informal Theorem (Theorem 3.8). There exists a decentralized, gradient-base based method (eq. (Alt- GDA)) that computes, with high probability under suitable Gaussian random initialization, an e-approximate Nash equilibrium for any e 0 in broad class of hidden corvex-concave zero-sum games, where each player's 's strategy is parameterized by sufficiently wide two-layer neural network.
The number of iterations required scales
o (poty poly width, widtha n dinput
L3
x log (2)
x
where width widthy are the hidden layer widths, the number of training samples, dinpus is the input dimension, L is the smoothness constant, and μ is the strong convexity modulus of the latent objective.
This guarantee holds provided the network width1,2 = (0(2 dayse
converse byproduct: input-optimization games. We also uncover new convergence guarantee in related but distinct setting: optimizing directly over inputs when the neural network mappings are fixed. This perspective is motivated both by adversarial example generation through min-max formulations (see Section 2, Appendix B & [117)) and by empirical results of [99] for solving normal form zero-sum games using optimizptin at random fixed neural network haapings-witheee theoretical justification of non-singularity of spectrum trajectory. Formally, the goal is to find input vectors Allie TBob) that implement a Nash equilibrium:
min EDp #aaEDo
max L (Fo (T(ooh))
for some convex-concave function L. typically referred as attack's 's loss [117]. In this regard, we for- mally establish that Algorithm AltGDA converges to an c-Nash equilibrium with iteration complexity Ô ( log (+)) under high-probabilitty guarantees (Theorem 3.5). To the best of our knowledge, this provides the first open-box, provable convergence result for input-optimization attacks based on randomly initialized overparameterized neural networks, matching and theoretically explaining the experimental observations of [99] and [117].
3

---

1.2 Challenges and Our Approach: Bridging Overparameterization with Strategic Learning
Back to minimization. The optimization of min-max objectives- eespecallly structured con-convex games- has been extensively studied (for an appetizer see Appendix A. 1.A-2. and references therein). However, the dynamics of gradient-based methods in games where players are parameterized by neural networks remain far less understood. In minimization of training loss, powerful lens for analyzing the success of gradient descent (GD) is the theory of overparameterization and the Neural Tangent Kernel (NTK). In the infinite-width limit, GD converges provided the NTK's smallest eigenvalue remains bounded away from zero. For finite-width networks, convergence proofs typically hinge two ingredients: (i) good NTK conditioning at initialization, and (ii) negligible drift of the NTK during training [85, 27, 13, 106], ensuring that an underlying Polyak-Lojasievinn (PL) condition is maintained.
or
The spectrum path. Even simple hidden zero-sum games, where players are parameterized by two-layer neural networks with smooth activations, can cause vanilla GDA to diverge arbitrarily [114]. Although Pł.-based convergence for minimization has been understood since the classical works of Polyak and F.jasieeiczz [90, 73], analogous results for min-max optimization have only recently emerged [124, 125, 60]. More recently, hidden convexity has been shown to imply a PL structure- both in minimization [41] and in min-max games [60]. However, this reduction to Pł-condition reveals key technical obstacle: hidden convexity alone cannot safeguard convergence if the Jacobians of the players' mappings suffer from near-singularttis--i.... if the least singular value approaches zero. this regime, the effective Pt-modulus degenerates, the gradient dominance property and convergence guarantees break down. Thus, the evolution of singular values under the employed learning dynamics becomes central challenge.
Extending to Games:
In this work, we adopt the alternating gradient descent-ascent (AIGDAA) method, which mirrors natural sequential play between agents. From a technical standpoint, alternation proves crucial: simultaneous one-timescale GDA (SimGDA) may diverge both in case of hidden convex games [114] and two-sided-PL. games [124]. Additionally, alternation has been explored as an acceleration and stabilization tool for min-max optimization [66, 128].
AItGDA Path Length: Hence, our first central technical contributions is a tight control of the path length of AltGDA iterates (Lemma 3.3). We show that AltGDA trajectories remain confined within a bounded region around initialization, preventing severe deterioration of hidden convex-concave structure (e.g., Jacobian conditioning). While path-length bounds are relatively straightforward in minimization- by directly unrolling GD iterations-in min-max problems, the alternating structure introduces significant complications for such ad-hoc analysis. To eircumvent this, we employ a carefully designed potential function-a weighted interpolation between the two players' Nash gaps- by [124], which may be of independent interest.
Beyond bounding the trajectory, two additional challenges arise relative to standard supervised learning:
In games, neural networks output distributions over actions or more generally higher-dimensional vectors, unlike scalar labels in classification tasks. Estimating the singular value spectrum of such vector-output neural networks is more subtle. To address this, we arrive at Lemma 3.7, by adapting techniques from [106] which essentially combines Hermite expansions of hidden layer outputs, first-order Taylor series expansion and Lipschitzness of Jacobians, and high-probabee probability concentration bounds for random Gaussian matrices.
Output Dimension:
Average-Cass Case Analysis of Input Min-Max Games: A similar approach is employed for input- optimization games, where the roles of inputs and weights are reversed. From a worst-case perspective, there exist constructions leading to rank-deficient Jacobians and failure of GDA due to convergence to spurious local optima [114], our analysis takes an average-cas view. Specifically, we show that min-max input attacks, solved via AliGDA, succeed with high probability when the neural network mappings are randomly sampled with Gaussian initializations (Theorem 3.5).
Unlike many prior works, which rely on the non-linear least squares structure of supervised losses to control dynamics [106, 69, 70], we allow general separable latent objectives combining strongly convex regularizers and bilinear couplings. This more general setting requires significantly stronger control on the optimization trajectory and leads fundamentally different overparameterization scaling, namely l(n²) compared to 2(n) in pure minimization settings (Theorem 3.8)
General Loss Structures:

---

2
Preliminaries
We begin by introducing the standard notions of smoothness and Lipschitz continuity that will be used throughout this work. All norms are taken to be the Euclidean (62) norm unless otherwise stated.
Lipschitz Continuity, Smoothness, and Strong Convexity. Let ʃ R2 + I be differen- tiable function. We say that f is T.y-Lipschhtz continuous and y-mooth if there exist constants Tof, b > 0 such that
(S(u) [(w)] s 1.5lIu vll,
Vs(())l s Tvyllu- - [V[(w)
Vu, E Rd.
Moreover, f is j-sttronlyy convex if there exists such that
f(u) 2 f() + (Vf()). u- - a) /1 u||?,
Vu, v E Rd.
Similarly, for parametrized mapping (e.g., the neural network) Ma(x) Rd - TRd with parameters E TR. af we say Mg is -mooth (w.r.t. 0) at fixed input x: if
Vo Va (x)) S BM 0'1,
v0.0' E ERM
(2)
max
where max (-) denotes the largest singular value and (a))(() is the Jacobian of Ma(x) with respect 0.
Finite-Sample Parametrized Min-Max Setting. Then, we unroll the general hidden con- vex-coneave model (TD to the fimite-sample empirical risk minimization (ERM) setting, assuming access to a (possibly labeled) dataset D (Dr, Dc) = ((I,.)) of size n. Formally, we
consider the following optimization problem:
max CD(Fe, G&) == (PF(F)) (Dr.Da) (Fa, Go) (Go),
min O ((
(o)
df²) Rdim(SF) and Go d00) - (d)( are smooth functions
where the mappings Fg parametrized by and @ (e.g., neural networks). The individual components and the bilinear coupling expand as:
(Fo) = Eielpen Lyv, Fo(z:)), 13 (Go) = Eje(pall Glu, Go(zz)), 1 (D (Pr.Do)(Fo,CO Eie[pr1 Ejel Poll Fo(z;)) A(a,, Fy Ur U1 GT(())
where for each sample pair cig (x ( Vj); the coupling matrix Alr, ( encodes interactions between players.
Blanket Assumptions on the Loss and Coupling Terms. We impose the following structural assumptions the loss components and bilinear couplings appearing in the finite-sample min-max objective (o).
Assumption 2.1 (Smoothness, Hidden Strong Convexity, and Gradient Control).
(i) Smoothness: Each sample-wise individual loss fly. Map,.. (x)) is differentiable and L-smooth with respect to Map... (x).
iii Coupling Structure: Each bilinear coupling matrix A(x;, Fy Vos yj) is known, fixed, and has bounded operator norm.
(iii) Hidden Strong Convexity: Each sample-wise individual loss Ely, Map,, (x)) is strongly
convex with respect to the neural network output h. Gradient Growth Condition: There exist constants A A2, Ag 0 such that for all dd
(iv)
and E y, the (latent) gradient of each loss E(y, h) satisfies:
V ((yy)))) A)ll < A1|lA|| + Ag diam + Ag-
Remark 2.2. Item (i) ensures the applicability of gradient- based methods, while Items (i)- imply that the overall loss Lo is (Lc, L -mmoth and (no, -aidd-d-----stongge constants determined by the structure and A(-). For standard strongly convex losses (e.g., MSE, logistic loss, cross-entropy with (grreullarization) the gradient with respect to the network output
convex-concave, with
5

---

is controlled as in Item (iv) by an affine function of the output norm, with the leading coefficient proportional the strong convexity modulus, A = O(u).
Neural Network and Training Data Model.
Definition 2.3 (Two-layer Neural Network). We consider two-layer neural networks (often referred to as shallow networks). Specifically, such a network is defined by:
1((x) = MaPu=(W,,,s) = W. vb (w1%) x)
where x E Rd T(th)
E R44 xdd") wh/h) E " xa!") and 1p R - IR is an activation function
applied coordinate-wise.
Assumption 2.4 (Properties of the Two-layer Neural Network), We assume:
h(-) is wwce-differrnttabbe and 34 -moshhhth with respect to (W("), w(()).
& is twice-differentiable with (0)) O, bounded first and second derivatives (Lmmxx Fmaxx) and finite Hermite norm || < oo-
The training data (X, Y) E TR xn x Rd xn satisfies |
Vi E [n]] and [
maxx
(w?h)) hh) ) O
Mimax
for all k Zzo²
Although we assume the activation function z to be twice seieenntiiblethhreeeh excluding non- smooth activations such as ReLU results naturally extend to smooth approximations like the Gaussian Error Linear Unit (GeLU) [55] and the softplus function [39], which have been shown empirically perform comparably even better than ReLU in several settings [12. 40J. The performance of gradient-base bbase training depends critically on the geometry of the training data. A standard proxy for data diversity is the well-conditioning of sample matrix X (with input vectors as rows), under standard random designs such as isotropic or nub-Gaussian inputs [86, 110, 111, 95].
Assumption 2.5 (Spectral Properties of the Data Matrix). Let X Raxd denote the data matrix whose rows H; satisfy ||æ:||2 = 1 for all i. We assume that the number of samples satisfies n 2 d, and that X is "generic" in the sense that mmin (X**) = 22(1 and Xmax(X) = O (000v (Vn/d). where n is the number of samples and d is the ambient input dimension.
For fair comparison with the minimization literature, in the main body of the paper we adopt the data genericity assumption. Interested readers can refer to appendix for fine-grained width bounds.
Solution concept. Note that while our min-max objective LD Fo, G&) is not convex convex-concave in Fg, Go. it is (strongly) convex-concave in the outputs of Fa and Go, i.e., hidden strongly- convex-concave. Our analysis leverages precisely this hidden structure. Specifically, [41, Proposition 2] states that if ming [() ( = F H (0)) and F is strongly convex while H is a smooth map (e.g., neural net), then satisfies the Pł.conndition Thus, hidden strong convexity implies PL-condition, even for nonconvex objectives. Utilizing this along with [30, Proposition of 4.1], we can define PL-moduli for our min-max objective in terms of the smallest singular values of the neural network Jacobians:
'Controlling the gradient growth is critical for non-asymptotic overparameterization bounds, as it ensures that iterates remain within regions where hidden convexity persists. A detailed discussion and examples deferred to Appendix
"This is needed for upper bound on maximum singular value of h's Jacobian.
1 'Given random Gaussian initialization and ensuring that iterates never leave a finite-rade raatee- ball around initialization, we can safely assume the maximum singular value is bounded from above for all iterates k. *Moreover, we expect that the smoothness assumption can be relaxed. Since AltGDA includes subgradient variant, our analysis could likely extended to (almost) smooth activations such as ReLU, by carefully treating the measure- zero set of non non- differentiability points. We leave this technical refinement to future work, as the core phenomena should remain qualitatively unchanged.
"amax (X) = O(yn/d) w.h.p. when, for e.g., has i.i.d. A/ 1) entries [86, Section IL.A]. For an arbitrary, fixed X, Fmax (X) |||||a 2 & ||] = V (:: ||ax||2 = 1 i). See Remark G.5 in Appendix G. 'The assumption 2 d ensures that X is sufficiently tall avoid rank deficiency and the minimum singular value of the Khatri- Rao product mmiu (X*) serves as natural measures of the dataset's well-conditioning Intuitively, Assumption 2.5 reflects that the dataset covers the input space sufficiently uniformly, ensuring that no direction is either too collapsed or too amplified. Such a balance is critical for achieving stable optimization dynamics and avoiding pathological trap into lower-dimensional subspaces during training.

---

Fact 2.6 (Reduction to Two-Sided PE-condition [41, 30]). The loss function Cp satisfies two-sided Polyak- Lojasiewicz (PL) condition with parameters Hgg (V and Mo (V (G&) where mmin() ()) denotes the smallest singular value of the corresponding Jacobian mappings.
This reduction resolves several challenges inherent to general eemoonvex-nnnconcaae min-max problems. First, it unifies several optimality gradient maationaity-whie
global minimax, saddle point, and in general settings, need not coincide. For formal definitions see Appendix E. In the case where the objective satisfies two-sided Dolyak-E.ojssewiie (Pt.) condition, these notions become equivalent even at their e-approximate versions. We formalize this via the following lemma:
Lemma 2.7 (Lemma 2.1 in [124], Appendix C in [60]). If the objective function f satisfies the two-sided PE-condition, then all three notions in Definition E.1 are equivalent:
E 6- -Saddle Point) > e (Global Min-Max) - c (Stationon Point) 2= 20
Second, discussed in the introduction, saddle points may not exist in general noncon- vex-nonconcave problems. Therefore, we explicitly adopt the following benign' assumption:
Assumption 2.8 (Existence of Saddle Points). The objective function L(0, Φ) admits at least one saddle point. Moreover, for any fixed ø. min [(6, 6) has a non-empty solution set and a finite minimum value. Similarly, for any fixed 0, max L( Φ) has non-empty solution set and a finite maximum value.
Examples of hidden neural min-max optimization. Due to space limitations, we defer a com- prehensive list of examples and references to Appendix B. To build intuition, we present below two representative bilinear examples that highlight the key structural differences. We broadly distinguish two principal types of ML-driven min-max problems
Network Optimization: Problems where optimization is performed over neural network parame- ters given fixed dataset (training weights). This setting captures tasks such generative modeling or robust adversarial reinforcement learning.
Example
min max Fa(x)) (z))
8 Φ
Problems where network parameters are fixed (e.g., random initialization), and optimization occurs over the input space (e-g.. adversarial perturbations). This corresponds to input-driven optimization problems such as adversarial attack design.
Input Optimization:
Example:
min max (Fe(IA)))) AG Alkk TBAEDG
3 Our Results
Alternating Gradient Descent-Ascent (AlGGAA) proceeds by sequentially updating the parameters of the min-player 0 and the max-player o, leveraging the most recent gradient information at each step. The updates take the form:
(( = g(--1) VoLD(0(L-) 1((--)))
(00) = 1(1-1) + no V (O(()), ((e-1) (AlIGDA)
where n1, No 0 denote the respective step sizes.
Our analysis builds upon the framework of Yang, Kiyavash, and He [124], which guarantees log(1/A convergence under two-sided PL condition. In our setting, the PL moduli depend on the smallest singular values aiin of the Jacobians VaFa and VoGG, which must remain bounded away from zero throughout the optimization trajectory (Fact 2.6). This dependence is critical, as both the PL. constants and the step sizes in AltGDA scale inversely with omin-
"This assumption mild in our setting for two reasons: In generative tasks such as GANs, the existence a saddle point corresponds to operating in the realization regime, where the generator can fully match the data distribution [51].
Following Gidel et al. [48], if the parameter spaces for 0 and are bounded, saddle point existence can be guaranteed by classical minimax theorems. While we not explicitly constrain the parameter spaces, our analysis shows that the iterates of the Alternating GDA (AlIGDA) method remain contined within a bounded region. Thus, we can effectively assume boundedness without loss of generality.
7

---

Hence, we first establish that, under suitable random initialization and sufficient overparameteriza tion, the initialization satisfies min (VoFo, min (V, 2 cB with high probability (see Lem- mas 3.4 and 3.7). Furthermore, by smoothness of the neural mappings, there exists Fuclidean ball B((,, Φo), R) within which the singular values of the Jacobians remain well-conditioned, i... min B > O. The radius is given by R Hi 3 == min (3F,8c) 8.). This result parallels Lemma 1 of Song et al. [106], adapted here to the alternating min-max setting.
where Hlac := max { (1 m1aa)) } and
23
However, the optimization trajectory could, in principle, leave this region. To prevent this, we analyze the path length of AltGDA using Yang. Kiyavash, and He [124]'s Lyapunov potential function, rather than directly unrolling the sterates-whicl would be analytically cumbersome due to alternation:
Definition 3.1 (Lyapunov Potential [124]). For a max objective function, L(0, Φ). we define the Lyapunov potential at time as P. (max; [(2,, 6) L("", )²)) + (max, C(O, ox) [(O,, oc)). (Note that the choice A will not affect our conclusions about overparameterization in this paper.)
Lemma 3.2 (Theorem 3.2 in [124]). Suppose the min-max objective function [(0, () is L s-mothh
ng
and satisfies the two-sided PÉ-condition with (pa, po). Then we run AlIGDA with тje 1816
and ne L.e' then ||0++1 Bell + l| - lell S /ac//2/Pp where constants a and c (0. 1) depend only on Lvc, Ha, Hb and Po the Lyapunov potential at time t 0. (Please refer Remark E.5 for the exact expressions for a and c.)
1.
By way of contradiction, let T denote the first iteration such that (0r, dr) & B((Oo, oo), R). We will show that, with high probability, the AltGDA trajectory remains within this ball by proving that its total path length is strietly less than R.
Indeed, AltGDA path length satisfies: ((T) & ETD (110+1 Bell +1 - @ell) S 1 VP
Therefore, it suffices to show that vPo S R/2 with high probability. The following lemma provides an upper bound on Po in terms of the gradient norms:
Lemma 3.3 (Upper Bound on Initial Potential Po). Suppose the min min-max objective L(0, Φ) is Le- Lipschitz and satisfies a two-sided PL condition with constants (na, (a).. Then the initial Lyapumov
potential Po & L (C1 [|VoL(fo do)1 + C2 : /V Φo)]l) where C1,C2 = = (Tc//g))
It is clear that bounding Po requires controlling the gradient norms at initialization, which- our neural setting requirrss bounding both the output norm and the spectral norm max the Jacobian via the chain rule. Lemmas 3.4. G.2 and 3.7 provide these bounds under standard overparameterizztioo and Lipschitz stability conditions. As a result, we obtain Po I KR² for some constant x < 1 determined by the network width. Thus, with sufficient overparameterization, the iterates remain confined within the well-conditioned region ((fo. do), R).
Interestingly, this analysis not only ensures that the iterates stay within region where the PE- condition holds, but also reveals beneficial side effect: since the potential function captures a weighted average of Nash gaps and is monotonically decreasing, small initial value of Po implies that the initialization is already mildly close to equilibrium. Consequently, both convergence and geometric stability are maintained throughout training.
3.1 Input-Optimization Min-Max Games
Here, we consider the input-optimization game between two neural networks F& and Go in hidden bilinear objective with æzregulariization defined as follows for a given payoff matrix, A:
[ Φ) F AG( + & [F(()) 1
(3)
2
This game has been proposed by [114] and experimentally analyzed by [99]. Here, Fo and Go are defined similar to Definition 2.3 as F(0) w (( and G(d) w (W x) but with parameters 0, ó as inputs and randomly initalized w(th (0 w/(a) N'00, (ot.)) E (1, 2} along with differentiable activation function &b (e.g. GeLUU.. Therefore, the partial derivatives w.r.t. 0 and o will be as follows:
Vef Φ) (VoFe) AG( + +e(VoF)) F(0)
8

---

= -(
(4)
Using these and Lemma 3.3, we can now bound Po as follows:
= [+) (eLcC10max (0SeCCCmxx(VVFo,, + L + (A) GoG)))
+ [[))( (LeCiomax (aammaaxaammmaaa (A)omax (V + =02 + X) (V Vo)G
(5)
Since we want to stay within the ball ( oo), R), we can ensure Po = RR² by controlling each term in Equation (5) accordingly that ultimately yields Theorem 3.5. For this, we would additionally need to prove Lemma 3.4 as stated below. (Please see Appendix F for proof).
Lemma 3.4. Consider neural network Fg F(0) W (W as defined above. Say ib
is the GeLU activation function, d(²) 2 256 max do))
(F) ) and of O
Then, w.p 2 1 - -50)d
(i) the singular values of the Jacobian Fe are bounded as
Juin (VFFo) Ω (01.F 02.F d( and T (ooF)) O (01.F 02, 02.F o2))
(6)
(û) F(O) is 3m-smooth where 3F θ (oi, F2 (d (8/2)))))
Theorem 3.5. Consider two neural networks F(0), G( as defined in Lemma 3.4 above. For the
regularized hidden bilinear min-max objective L(G, Φ) as defined in Equation 3 above, AltGDA
reaches E-saddle point w.p. 2 1 - -Q(d"")) if (0o. Φ0) and standard deviations oF and Og,G.
A {1 are chosen such that dt.F/G O (1d1)(1/d1)) ):
Fmax
To our knowledge, this is the first fine-grained result for overparametrized networks that establishes an O(1) approxiate minimax solution for the hidden bilinear setting originally proposed by Vlatakis- Gkaragkounis, Flokas, and Piliouras [114].
3.2 Neural-Parameters Min-Max Games
Now we analyse the case of Perame-Parsmeters Min-Max Games described in Section In particular, when both players are two-layer neural networks, through Lemma 3.7, with high probability the Jacobians non-singular for random Gaussian initializations which ensures that the II games with such networks will satisfy 2-sided Pt--ondition with high probability. Consequently, given appropriate initialization conditions for the networks (Assumption 3.6, Equation (9)), just like in Section 3.1, we can show that AltGDA converges to the saddle point by ensuring Po = klt via requiring both the networks to have at least cubic overparameterization (Theorem 3.8).
Initialization Scheme 3.6 (Random Initialization). We consider the following initialization scheme for two-layer neural network, F, as defined in Definition 2.3:
(w((") )o- o(
(WL )o NN00,0,,11
Lemma 3.7 (Lemma 3 & Appendix E.1-E.4 in [106]). Suppose that a two-layer neural network,
T"> [v((a) S [v(ra)) s r"a))(a)), F. as defined in Definition 2.3, satisfies Assumption 2.4 and T" respectively for all 0
1, and some constants T2, Then whh.p. the neural network
(i) Jacobian has following bounds its singular values
Onin (o) 52 (of.ee a(F)) and Fmax (VoF)= (dfr V aiF)
(8)
(ii is Bp-smooth with 3F 22 (X) + VmmxxXxmx) where Xmax supy T (V). Theorem 3.8 A Games with AltGDA). Suppose there are two two-layer neural networks, hgg 90
as defined in Definition 2.3 which satisfy Assumption 2.4 and r" (=)(((a) I [WTaa) I (")) respectively for all a, and Φn randomly initialized as in initialization Scheme 3.6 with (0I,F, o2,F) and (ai,a, 02,0), respectively, which satisfy
< 1, and some constants Tı, T2. Suppose the network parameters dg
O1. O2.F Z
and 01G 02 S
(9)
d (F)
d(

---

and suppose that the hidden layer widths a and d for the two networks F and G satisfy
d-= =
n2 110 do
and = 11 n G
(10)
where the datasets (Dr, DG) for both the players are assumed to be of size n. Then II game correspond to an (po. Ho (ee-He)-HSCE H-SCSCC min-max objective as defined in Equation I satisfying Assumption 2.1 and AlIGDA with appropriate fixed step-sizes nj, 1/o (see Lemma E.7) converges to the saddle point (0", ,6)) exponentially fast with high probability.
We refer the reader to Appendix for the proof of Theorem 3.8, and exact expressions for failure probabilities and various quantities stated in both Lemma 3.7 and Theorem 3.8
4 Conclusion & Future Directions
We provide the first convergence guarantees and overparameterization bounds for alternating gradient methods in input games and hidden (strongly) convex-concave neural games. Our analysis tightly links optimization trajectory control with spectral stability, ensuring convergence to near-equilibrium. If the reader would like to look beyond the technicalities around the non-asymprotic bounds, our proof techniques offer several insights for practitioners:
Interpretation of min and Exploration: The smallest singular value of the network Jacobian, Fmin, controls how well the model explores the strategy space. When miin A3 O, certain strategies remain unexplored, indicating convergence to spurious subspaces. Our analysis ties this directly to the degree of overparameterizztion
Data Geometry and Regions of Attraction: Our results show that overparameterized networks initialized with sufficiently diverse data are more likely to fall into regions where o mmin 0, ensuring stable convergence under AlGGDA, While computing min per iteration is impractical, the connection offers design insights for data and architecture.
Table 1: Comparison between our paper and common practice
Our paper
In practice
Type of Neural Network
1-hidden-layer, fully collecc
Typically deep networks, not neces- sarily fully-connected (e.g., resid- ual or convolutional layers)
Training Algorithm
AltGDA
Not necessarily AltGDA / mainly double-loop
Network Initialization
Gaussian
Similar (e.g., He, Xavier, or LeCun initializations)
(with variance constraints)
Going beyond the neural networks and training regimes considered in this paper (see Table for summary) is an important future direction. Among these, the assumption on AltGDA is arguably the most benign. In non-convexxnnon-coneaa practice, double-loop methods (e.g., approximate best-response oracles) are often used for safety, while AltGDA serves as more parallelizable and simpler single-loop alternative. Similarly, the Gaussian initialization is closely aligned with popular schemes like He or Xavier. The main gap lies in the architecture: practical models are often very deep with fixed-width layers. While recent work has begun to explore overparameterization in deep networks for minimization tasks, our paper focuses on a more analytically tractable setting explicitly avoiding the NTK regime to provide non-asymptotic analysis for 1-hidden-Bee layer networks in a game- theoretic context. We view relaxing and extending these assumptions
min-max optimization, stabilization is essential. In
promising direction for future work.
Another natural next step understand how these techniques extend to non-differentiable activation functions (such as ReLU) or scale to multi-player and non-zero-sum settings especially in structured environments like polyhedral games, which share connections with extensive-form games. For instance, exploring the analogy between two-sided PE-conditions (for two-player games) and hypo- monotonicity in multi-agent operator theory may allow us to transfer and generalize some of the intuition and techniques from our current setting. We hope our work and these possible future directions open up rich and technically deep avenues for developing gradient- based methods tailored for structured, non-monotone multiplayer games. (See also Appendix I.)
10

---

References
[1] Jacob Abernethy, Kevin A Lai, and Andre Wibisono. "Last-iterate convergence rates for min-max optimization". In: arXiv preprint arXiv:1906.02000 (2019).
[2] Sravanti Addepalli et al. "Scaling adversarial training to large perturbation bounds". In: European Conference on Computer Vision. Springer. 2022, pp. 301-316.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. "A convergence theory for deep learning via over-vveraaee vver-paraeterization"" In: International conference on machine learning. PMLR. 2019,
Pp. 242-252.
[4] Dario Amodei et al. "Concrete problems in Al safety". In: arXiv preprint arXiv:1606.06566 (2016).
[5] Toannis Anagnostides and Tuomas Sandholm. "Convergence of log(1/E) for Gradient-Basee Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis". In: arXiv preprint arXiv:2410.21663 (2024).
[6] Toannis Anagnostides et al. "The Complexity of Symmetric Equilibria in Min-Max Optimiza- tion and Team Zero-Sum Games". In: arXiv preprint arXiv:2502. 08519 (2025).
[7] James P Bailey, Gauthier Gidel, and Georgios Piliouras. "Finite regret and cycles with fixed step-size via alternating gradient descent-ascent" In: Conference Learning Theory. PMLR. 2020, pp. 391-407.
[8] Anas Barakat, Ilyas Fatkhullin, and Niao He. "Reinforcement learning with general utilities: Simpler variance reduction and large state-action space". In: International Conference on Machine Learning. PMLR. 2023, pp. 1753-1800.
[9] Aharon Ben-Tal and Marc Teboulle. "Hidden convexity in some nonconvex quadratically constrained quadratic programming". In: Mathematical Programming 72.1 (1996), pp. 51-63.
[10] Martino Bernasconi et al. "On the Role of Constraints in the Complexity of Min-Max Optimization". In: arXiv preprint arXiv:2411.03244 (2024).
[11] Aditya Bhaskara et al. "Descent with Misaligned Gradients and Applications to Hidden Convexity". In: The Thirteenth International Conference on Learning Representations.
[12] Koushik Biswas et al. "SMU: smooth activation function for deep networks using smoothing maximum technique". In: arXiv preprint arXiv:21 1.04682 (2021).
[13] Simone Bombari, Mohammad Hossein Amani, and Marco Mondelli. "Memorization and optimization in deep neural networks with minimum overetaaramttrriiation""""" In: Advances in Neural Information Processing Systems 35 (2022), pp. 7628-7640.
[14] Andrew Brock, Jeff Donahue, and Karen Simonyan. "Large Scale GAN Training for High Fidelity Natural Image Synthesis". In: International Conference on Learning Representations. 2019. URL: https: opw.//eeneeviieeeeeeeeeeeeeeeeee net/ formforum? idd add-Bixssj099
[15] Noam Brown and Tuomas Sandholm. "Solving imperfect-informatte games via discounted regret minimization". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 01. 2019, pp. 1829-1836.
[16] Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. "Scalable Al safety via doubly- efficient debate"". In: arXiv preprint arXiv:2311.141 (2023).
[17] Sébastien Bubeck and Mark Sellke. "A universal law of robustness via isoperimetry". In: Advances in Neural Information Processing Systems 34 (2021), pp. 28811-28827
[18] Qi Cai et al. "On the global convergence of imitation learning: A case for linear quadratic regulator". In: arXiv preprint arXiv:1901.00 036774 (2019).
[19]
Yang Cai al. "Zero-sum polymatrix games: A generalization of minmax". In: Mathematics of Operations Research 41.2 (2016), pp. 648-655.
[20] Lesi Chen, Boyuan Yao, and Luo Luo. "Faster stochastic algorithms for minimax optimization under polyak-(VI.. ojasiewicz condition". In: Advances Neural Information Processing Systems 35 (2022), pp. 13921-13932.
[21] Robert S Chen et al. "Robust optimization for non-convex objectives". In: Advances in Neural Information Processing Systems 30 (2017).
[22] Xi Chen and Xiaotie Deng. "3-Nash is PPAD-complete". In: Electronic Colloquium on Computational Complexity. Vol. 134. Citeseer. 2005, pp. 2-29.
[23] Xi Chen, Xiaotie Deng, and Shang-Hua Teng. "Settling the complexity of computing two- player Nash equilibria", In: Journal of the ACM (JACM) 56.3 (2009), pp. 1-57.
11

---

[24]
Xin Chen et al. "Efficient algorithms for a class of stochastic hidden convex optimization and its applications in network revenue management", In: Operations Research (2024).
[25] Zhang Chen et al. "Over-parameterizatie and Adversarial Robustness in Neural Networks: An Overview and Empirical Analysis". In: arXiv preprint arXiv:2406. 10090 (2024).
[26] Zixiang Chen, Dongruo Zhou, and Quanquan Gu. "Almost optimal algorithmms for two-player markov games with linear function approximation". In: arXiv preprint arXiv:2102.0740k 1.2
(2021), p. 3.
[27] Lenaic Chizat, Edouard Oyallon, and Francis Bach. "On lazy training in differentiable programming". In: Advances in neural information processing systems 32 (2019).
[28] Jacob W Crandall et al. "Cooperating with machines". In: Nature communications 9.1 (2018),
p.
233.
[29]
Ryan D'Orazio et al. "Solving hidden monotone variational inequalities with surrogate losses". In: arXiv preprint arXiv:2411.05222 (2024).
[30] Ryan D'Orazio et al. "Solving hidden monotone variational inequalities with surrogate losses". In: The Thirteenth International Conference on Learning Representations. 2025.
URL:
net/teruum www.orommmmdd2220000. 42X2a30EVV
[31]
Constantinos Daskalakis. "Non-concave games: A challenge for game theory's 's next 100
years". In: Cowles Preprints (2022).
[32]
Constantinos Daskalakis, Paul W Goldberg, and Christos Papadimitriou. "The complexity of computing Nash equilibrium". In: Communications of the ACM 52.2 (2009), pp. 89-97.
[33]
Constantinos Daskalakis and Ioannis Panageas. "The limit points of (optimistic) gradient descent in min-max optimization". In: Advances in neural information processing systems 31 (2018).
[34] Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. "The complexity of constrained min-max optimization". In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, pp. 1466-1478.
[35] Constantinos Daskalakis et al. "Training gans with optimism". In: arXiv preprint arXiv:1711.0014 (2017).
[36]
VF Dem' yanov and AB Pevnyi. "Some estimates in minimax problems", In: Cybernetics 8.1 (1972), pp. 116-123.
[37] Yihe Dong, (iean-Baptise Cordonnier, and Andreas Loukas. "Attention is not all you need: pure attention loses rank doubly exponentially with depth". In: Proceedings of the 38th International Conference on Machine Learning. Ed. by Marina Meila and Tong Zhang. Vol. 139. Proceedings of Machine Learning Research. PMLR, 18-24 Jul 2021, pp. 2793- mlr. pwwss/vve3e https/////////////1e// dong2la. html.
2803. URL:
[38] Simon Du al. "Gradient descent finds global minima of deep neural networks". In: Interna- tional conference on machine learning. PMLR. 2019, pp. 1675-1685,
[39] Charles Dugas et al. "Incorporating second-order functional knowledge for better option pricing". In: Advances in neural information processing systems 13 (2000).
[40] Stefan Elfwing, Eiji Uchibe, and Kenji Doya. "Sigmoid-weighter linear units for neural network function approximation in reinforcement learning.. In: Neural networks 107 (2018),
pp. 3-11.
[41] Ilyas Fatkhullin, Niao He, and Yifan Hu. "Stochastic optimization under hidden convexity".
In: arXiv preprint arXiv:2401. 00108 (2023).
[42]
Qi Feng and J George Shanthikumar. "Supply and demand functions in inventory models". In: Operations Research 66.1 (2018), pp. 77-91.
[43] Ruili Feng et al. "Rank Diminishing in Deep Neural Networks". In: Advances in Neural Information Processing Systems. Ed. by S. Koyejo et al. Vol. 35. Curran Associates, Inc., 2022, pp. 33054-33065 URL: htwp:::tp:///tett p/tpceed///rooooeiiigg neurips cc / paper faaper_filee files/ / (oper/2022/fivv ottp://000221ieecccc6fof07771772 /BBc://000001788777722aaeeee1e11 Paaper/rrtb-aapeee--oeerrrreeee Conference, pdf.
[44] Yaroslav Ganin et al. "Domain-adversart training of neural networks". In: Journal of machine learning research 17.59 (2016), pp. 1-35.
[45] Ruiqi Gao et al. "Convergence of adversarial training in overparametrized neural networks".
In: Advances in Neural Information Processing Systems 32 (2019).
12

---

[46] Angeliki Giannou, Emmanouil Vasileios Vatakis-Gkaragken and Panayotis Mertikopou- los. "Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information". In: Conference on Learning Theory. PMLR. 2021, pp. 2147-2148
[47] Angeliki Giannou, Emmanouil- Vasileios Vlatakis-Gkaragknn Gkaragkounis, and Panayotis Mertikopou- los. "On the rate of convergence of regularized learning in games: From bandits and uncer- tainty to optimism and beyond". In: Advances in Neural Information Processing Systems 34 (2021), pp. 22655-22666.
[48] Gauthier Gidel et al. "A limited-capacity minimax theorem for non-convex games or: How i learned to stop worrying about mixed-nash and love neural nets". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2021, pp. 2548-2555 2556..
[49]
Gauthier Gidel et al. "A variational inequality perspective on generative adversarial networks". In: arXiv preprint arXiv:1802 10551 (2018).
[50] Gauthier Gidel et al. "Negative momentum for improved game dynamics". In: The 22nd International Conference on Artificial Intelligence and Statistics. PMLR. 2019, pp. 1802- 1811.
[51] Ian J Goodfellow et al. "Generative adversarial nets". In: Advances in neural information processing systems 27 (2014).
[52] Sergiu Hart and Andreu Mas-Colell. "Stochastic uncoupled dynamics and Nash equilibrium". In: Games and economic behavior 57.2 (2006), pp. 286-303.
[53] Sergiu Hart and Andreu Mas-Colell. "Uncoupled dynamics do not lead to Nash equilibrium".
In: American Economic Review 93.5 (2003), pp. 1830-1836.
[54]
Elad Hazan et al. "Provably Efficient Maximum Entropy Exploration", In: International Conference on Machine Learning (ICML). 2019.
[55] Dan Hendrycks and Kevin Gimpel. "Gaussian error linear units (gelus)". : In: arXiv preprint arXiv: 1606 084 15 (2016).
[56] Geoffrey Irving, Paul Christiano, and Dario Amodei. "AI safety via debate". In: arXiv preprint arXiv: /805.00999 (2018).
[57] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural tangent kernel: Convergence and generalization in neural networks". In: Advances in neural information processing systems 31 (2018).
[58]
Chi Jin, Qinghua Liu, and Tiancheng Yu. "The power of exploiter: Provable ageett rl in large state spaces". In: International Conference on Machine Learning. PMLR. 2022,
pp. 10251-10279.
[59] Fivos Kalogiannis, Jingming Yan, and Ioannis Panageas. "Learning Equilibria in Adversarial Team Markov Games: A
Heeenvee--iddee--oneeeee Min-Max Optimization Problem". In: The Thirty-eighti Annual Conference on Neural Information Processing Systems.
[60]
Fivos Kalogiannis et al. "Solving Zero-Sum Convex Markov Games", In: Proceedings of the 42nd International Conference on Machine Learning (ICML). Poster presentation. PMLR. 2025.
[61] Tero Karras et al. "Progressive Growing of GANs for Improved Quality, Stability, and Variation".. In: International Conference on Learning Representations. 2018. URL: https: // //openreview www.teeeeeeeeee wete/ooumm/aa wwrfororrdoooooooooooorroor dd-tm:999HHk.......
[62] Seth Karten, Andy Luu Nguyen, and Chi Jin. "PokéChamp: an Expert-level Minimax Lan- guage Agent". In: Forty-second International Conference on Machine Learning, 2025. URL: httpa://openrevieee net. wowooroidmdmniiiiii
[63] Ivan Kobyzev, Simon JD Prince, and Mareus A Brubaker. "Normalizing flows: An introduc- tion and review of current methods".. In: IEEE transactions on pattern analysis and machine intelligence 11 (2020), pp. 3964-3979.
[64] Galina M Korpelevich. "The extragradient method for finding saddle points and other prob- lems". In: Matecon 12 (1976), pp. 747-756.
[65] Ilya Kuruzov et al. "Gradient-Type Methods For Decentralized Optimization Problems With Polyak- f ojasiewicz Condition Over Time- Varying Networks". In: arXiv preprint
arXiv:2210.0338 00.0000 (2022).
[66] Jaewook Lee, Hanseul Cho, and Chulhee Yun. "Fundamental benefit of alternating updates in minimax optimization". In: arXiv preprint arXiv:2402.10475 (2024).
13

---

[67] Chris Junchi Li et al. "Learning two-player markov games: Neural function approximation and correlated equilibrium". In: Advances in Neural Information Processing Systems 35 (2022), pp. 33262-33274.
[68] Qihang Lin et al. "Solving wakky--covex--eakkyycoooeee
saddle-point problems succes- sive strongly monotone variational inequalities". In: arXiv 2018 (2018).
[69] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. "Loss landscapes and optimization in over- parameterized non-linear systems and neural networks". In: Applied and Computational Harmonic Analysis 59 (2022): pp. 85-116.
[70] Chaoyue Liu, Libin Zhu, and Misha Belkin. "On the linearity of large non-linear models: when and why the tangent kernel is constant". In: Advances in Neural Information Processing Systems 33 (2020). pp. 15954-15964.
[71] Zehua Liu et al. "Convergence Analysis of Randomized SGDA under NC-PL Condition for Stochastic Minimax Optimization Problems". In: arXiv preprint arXiv:2307.13880 (2023).
[72] Roi Livni, Shai Shalev-Shwarzz, and Ohad Shamir. "On the computational efficiency of training neural networks". In: Advances in neural information processing systems 27 (2014).
[73] Stanislaw Lojasiewicz. "Une propriété topologique des sous-ensembles analytiques réels".
In: Les équations aux dérivées partielles 117.87-89 (1963).
[74] B. Martinet. "Régularisation d' d'inéquations variationnelles par approximations successives".
In: ESAIM: Mathematical Modelling and Numerical Analysis Modélisation Mathématique
et Analyse Numérique (1970).
[75] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. "Cycles in ad- versarial regularized learning". In: Proceedings of the twenty-ninth annual ACM-SIAL symposium on discrete algorithms. SIAM. 2018, pp. 2703-2717.
[76] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. "The numerics of gans". In: Advances in neural information processing systems 30 (2017).
[77] Paul Michel, Tatsunori Hashimoto, and Graham Neubig. "Modeling the Second Player in Distributionally Robust Optimization". In: International Conference on Learning Representa- http//frumiddddDDeaeee
tions. 2021. URL: https: http:://ppeeeeieeeeeeee
[78] Jason Milionis et al. "An impossibility theorem in game dynamics". In: Proceedings of the National Academy of Sciences 120.41 (2023), e2305349120.
[79] Andjela Mladenovic et al. "Generalized natural gradient flows in hidden
games and gans". In: International Conference on Learning Representations. 2021.
[80] John F Nash. "Non-cooperative games". In: The Foundations of Price Theory Vol 4. Routledge, 2024, pp. 329-340.
[81]
Yurii Nesterov and Boris T Polyak. "Cubic regularization of Newton method and its global performance". In: Mathematical programming 108.1 (2006), pp. 177-205.
[82]
Hukukane Nikaidô and Kazuo Isoda. "Note non-cooperative convex games". In: (1955). Nobel Symposium: One Hundred Years of Game Theory. Stockholm, Sweden. Organized by Jorgen Weibull, Roger Myerson, Yukio Koriyama, Tommy Andersson, and Mark Voorneveld. Dec. 2021.
[83]
[84]
Maher Nouiehed et al. "Solving a class of nonvconvex min-mat max games using iterative first order methods". In: Advances in Neural Information Processing Systems 32 (2019).
[85] Samet Oymak and Mahdi Soltanolkotabi. "Overparameterizee nonlinear learning: Gradient descent takes the shortest path?" In: International Conference on Machine Learning. PMLR. 2019, pp. 4951-4960.
[86] Samet Oymak and Mahdi Soltanolkotabi. "Toward moderate overparameteriizaton Global convergence guarantees for training shallow neural networks". In: IEEE Journal on Selected
Areas in Information Theory 1.1 (2020), pp. 84-105.
[87] Christos H Papadimitriou, Emmanouil- Vasileios Vlatakis- Sanakis-Gkaragkounii, and Manolis Zam- petakis. "The computational complexity of multi-player concave games and Kakutani fixed points". In: arXiv preprini urXiv:2207.075:
(2022).
[88]
Alan Le Pham et al. "The Effect of Model Size on Worst-Group Generalization". In: NeurIPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications. 2021. URL: https: https:://pente //op:////eeereviee..oomo net/ fatee/fouee weaet//ffrmmiddddde
1hhoeqo.
[89] Lerrel Pinto et al. "Robust adversarial reinforcement learning". In: International conference
machine learning. PMLR. 2017, pp. 2817-2826.
14

---

[90] Boris Teodorovich Polyak. "Gradient methods for minimizing functionals". In: Zhurnal vychislitel noi matematiki matematicheskko fiziki 3.4 (1963), pp. 643-653.
[91] Leonid Denisovich Popov. "A modification of the Arrow-Hurwitz method of search for saddle points". : In: Mat. Zamerki 28.5 (1980), pp. 777-784.
[92] Qi Qian al. "Robust optimization over multiple domains". In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. 01. 2019, pp. 4739-4746.
[93] R. Tyrrell Rockafellar. "Monotone operators and the proximal point algorithm".. . In: SIAM Journal on Control and Optimization 14.5 (1976), pp. 877-898.
[94] J Ben Rosen. "Existence and uniqueness of equilibrium points for concave n-person games". In: Econometrica: Journal of the Econometric Society (1965), pp. 520-534.
[95] Mark Rudelson and Roman Vershynin. "Smallest singular value of a random rectangular matrix". In: Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 62.12 (2009), pp. 1707-1739.
[96] Stuart Russell, Daniel Dewey, and Max Tegmark. "Research priorities for robust and benefi- cial artificial intelligence". In: Al magazine 36.4 (2015), pp. 105-114.
[97] Itay Safran and Ohad Shamir. "Depth-width tradeoffs in approximating natural functions with neural networks". In: International conference on machine learning. PMLR. 2017, pp. 2979-2987.
[98]
Itay Safran and Ohad Shamir. "On the quality of the initial basin overspecified neural networks". In: International Conference Machine Learning. PMLR. 2016, pp. 774-782. [99] losif Sakos al. "Exploiting hidden structures in non-convex games for convergence to Nash equilibrium". In: Advances in Neural Information Processing Systems 36 (2023), pp. 66979- 67006.
[100] Axel Sauer, Katja Schwarz, and Andreas Geiger. "Stylegan-xl: Scaling stylegan large diverse datasets". In: ACM SIGGRAPH 2022 conference proceedings. 2022, pp- 1-10. [101] Hanie Sedghi. Vineet Gupta, and Philip M Long. "The singular values of convolutional
layers". In: arXiv preprint arXiv: 10408 (2018).
[102] Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. "Safe, multi-agent, reinforce- ment learning for autonomous driving". In: arXiv preprint 11110:1610 (2016). [103] David Silver et al. "Mastering the game of go without human knowledge", In: nature 550.7676
(2017), pp. 354-359.
[104] Rachael Hwee Ling Sim et al. "Collaborative machine learning with incentive- model rewards". In: International conference on machine learning. PMLR. 2020, pp. 8927-8936.
[105] Aman Sinha, Hongseok Namkoong, and John C Duchi. "Certifiable Distributional Ro- bustness with Principled Adversarial Training. CoRR, Abs/1771..00571" In: arXiv preprint
arXiv: 10571 (2017).
[106] Chachwan Song al. "'Sbqquadratic overparameterizztion for shallow neural networks". In:
Advances in Neural Information Processing Systems 34 (2021), pp. 11277-11259.
[107] Ronald J Stern and Henry Wolkowicz. "Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations". In: SIAM Journal on Optimization 5.2 (1995), pp. 286-313,
[108] Richard Sutton, Csaba Szepesvári, and Hamid Reza Maei. "A convergent (n) algorithm for off- off-policy temporal-differens learning with linear function approximation". In: Advances in neural information processing systems 21.21 (2008), pp. 1609-1616.
[109] Kiran K Thekumparampil et al. "Efficient algorithms for smooth minimax optimization". In:
Advances in neural information processing systems 32 (2019).
[110] Roman Vershynin. Higl-ddmensional probability: An introduction with applications data science. Vol. 47. Cambridge university press, 2018.
[111] Roman Vershynin. "Spectral norm of products of random and deterministic matrices". In: Probability theory and related fields 150.3 22011), pp. 471-509.
[112] Oriol Vinyals et al. "Grandmaster level in StarCraft II using multi-agent reinforcement learning". In: nature 575.7782 (2019), pp. 350-354.
[113] Emmanouil- Vasileios Vlatakis-Gle Gkaragkounis, Lampros Flokas, and Georgios Piliouras.
"Chaos persists in large-scale multi-agent learning despite adaptive learning rates". In: arXiv preprint arXiv:2306. 010022 (2023).
15

---

[114] Emmanouil- Vasileios Vlatakis Vlatakis-Gkaragee Gkaragkounis, Lampros Flokas, and Georgios Piliouras. "Poincaré recurrence, cycles and spurious equilibria in cradient-descent-asee for non-convex non non-concave zero-sum games". In: Advances in Neural Information Processing Systems 32
(2019).
[115]
Vlatakis-Gkaragkommn Gkaragkounis, Lampros Flokas, and Georgios Piliouras. "Solv- ing min-max optimization with hidden structure via gradient descent ascent". In: Advances in Neural Information Processing Systems 34 (2021), pp. 2373-2386.
Emmanouil- Vasileios Vlatakis-
[116]
Emmannuil-Vasilcoos Vasileios YataaissGGaaagkoommi et al. "No-regret learning and mixed nash equilibria: They do not mix". In: Advances Neural Information Processing Systems 33 (2020), pp.
[117] Jingkang Wang al. "Adversarial attack generation empowered by min-mat optimization". In: Advances in Neural Information Processing Systems 34 (2021), pp. 16020-16033.
[118] Ruosong Wang, Dean P Foster, and Sham M Kakade. "What are the statistical limits of offline RL with linear function approximation?" In: arXiv preprint arXiv:2010. / 1895 (2020).
[119] Yifei Wang, Jonathan Lacotte, and Mert pilanci. "The hidden convex optimization landscape of regularized two-layer relu networks: an exact characterization of optimal solutions". In: International Conference on Learning Representations. 2021.
[120] Chen-Yu Yu Wei et al. "Linear last-iterate convergence in constrained saddle-point optimization".
In: arXiv preprint arXiv:2006.0951 07 (2020).
[121] Qiaomin Xie et al. "Learning zero-sum simultaneous-mont move markov games using function approximation and correlated equilibrium". In: Conference on learning theory. PMLR. 2020, pp. 01774-6882.
[122]
Zi Xu et al. "Zeroth-Order Alternating Gradient Descent Ascent Algorithms for A Class of Mincomvex-Nonconcaan Minimax Problems". In: Journal of Machine Learning Research 24.313 (2023), pp. 1-25. URL: http://jmlr. org httppaapprsssae/ee v////224/2/2//2222 1518 html.
[123] Songkai Xue and Yuckai Sun. "Distributionally Robust Performative Prediction". In: Ad- vances Neural Information Processing Systems 38 (2024).
[124] Junchi Yang, Negar Kiyavash, and Niao He. "Global convergence and variance reduction for class of nonconvex-nonconean minimax problems". In: Advances in Neural Information Processing Systems 33 (2020), pp. 1153-1165.
[125] Junchi Yang et al. "Faster single-loop algorithms for minimax optimization without strong concavity". In: International Conference Artificial Intelligence and Statistics. PMLR. 2022, pp. 5485-5517.
[126] Donghao Ying et al. "Policy-based primal-dual methods for convex constrained Markov decision processes". In: Proceedings of the AAAI Conference on Artificial Intelligence 37 (2023), pp. 10963-10971.
[127] Angela Yuan et al. "Optimal extragradient- brasedd algorithms for stochastic variational inequal- ities with separable structure". In: Advances in Neural Information Processing Systems 36 (2023), pp. 33338-33351.
[128] Guodong Zhang et al. "Near-optimal local convergence of alternating gradient descent- ascent for minimax optimization". In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 7659-7679.
[129] Junyu Zhang et al. "Variational policy gradient method for reinforcement learning with general utilities". In: Advances in Neural Information Processing Systems 33 (2020), pp. 4572-4583.
[130] Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. "Multi-agent reinforcement learning: A selective overview of theories and algorithms".. In: Handbook of reinforcement learning and control (2021), pp. 321-384.
[131] Siqi Zhang and Niao He. "On the convergence rate of stochastic mirror descent for nonsmooth nonconvex optimization". In: arXiv preprint arXiv: fttv::/00004775 (2018).
[132] Yi Zhang al. peraeeearaeetrrizeed adversarial training: An analysis overcoming the curse of dimensionality".. In: Advances in Neural Information Processing Systems 33 (2020), pp. 679- 688.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper's 's main claims, as stated in the abstract and introduction, accurately reflect the technical contributions and scope of the work. In particular, the abstract highlights the development of convergence guarantees for large-scale neural min-max games, while the introduction motivates the focus on hidden convex-concave structures, separable objectives, and data aata-dependent mappings. These themes are consistently developed throughout the paper, culminating in formal theorems and empirical examples that substantiate the claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Any assumption used has been discussed together with the description of the underlying model.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
17

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All necessary proofs are included.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
18

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips. public/guides////e
wereiisssssooolllooooooo oonoolicy) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///eerrpp.ee/ee//ee cc http:/pllc/tthccsssiiieee
Answer: [Yes]
Justification: NeurIPS Code of Ethics has been preserved
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
The paper includes discussion about the societal impact of the performed work
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https http://ips.ce/oooeeeeeeeeeeeeeee cctc//m/meerrrccee22///////// for what should or should be described.
23

---

Broader Impact.
This work advances the theoretical foundations for training large-scale multi-agent systems via gradient-based methods in hidden non-convex environments. Providing reliable convergence guar- antees in such settings critical step toward the safe and stable deployment of multi-agen technologies, with applications ranging from distributed control and autonomous systems to robust economic mechanisms, cybersecurity infrastructures, and collaborative Al development. Beyond immediate engineering benefits, our results contribute to the fundamental understanding of strategic learning in non-convex environments, offering the potential for more predictable, transparent, and verifiable AI behavior.
From a broader societal perspective, these theoretical advances can support the design of Al systems that align more closely with human values, improve multi-agent coordination, and enhance resilience against adversarial attacks. Applications may include improving the robustness of distributed decision- making, facilitating fairer negotiation frameworks, and enabling safer autonomous cooperation among heterogeneous agents. In doing so, this work contributes to the vision of Al systems that are not only powerful but also trustworthy and beneficial (ef. [4, 96]).
However, we also recognize that the same techniques enabling reliable convergence could be leveraged in ways that carry risks. In particular, stronger convergence in competitive environments may be exploited construct highly optimized agents for adversarial purposes, including strategic market manipulation, automated disinformation campaigns, or autonomous decision-making systems deployed without adequate oversight alignment with human norms, Further, the scalability of multi-agent learning could amplify systemic biases or create emergent behaviors that are difficult to predict control (cf. [28]).
Accordingly, while this work advances foundational goals in strategic machine learning. it also underscores the need for careful evaluation of downstream applications. Future research should emphasize robustness checks, fairness assessments, and human-centered design principles to ensure that strategic learning systems contribute positively societal welfare. In particular, collaborations across technical, ethical, and policy disciplines will be crucial to anticipate and mitigate potential negative consequences as these technologies scale and proliferate.
24

---

Appendix Contents
Further Discussion Prior Work
26
A.1
Optimization with Hidden Structures
26
A.2
Simultaneous, Alternating, and Extrapolated Dynamics in Convex-Concave Max Optimization
Concave Min-
26
A.3
Overparamettrizzttoon in Learning Dynamics: From Minimization to Games
27
A.4 Some Empirical Studies Demonstrating Need of Larger Neural Networks for Zero- Sum Games
28
Examples/Applications based on hidden min-max games
29
B.1 Neural Min-Max Games
29
B.2
Distributionally Robust Optimization
30
B.3 Inpur-Optimization Min-Max Games
30
Demonstrating Empirical Validity of Main Result for Input Games
32
Controlling the Gradient Growth: Bounds and Examples for Different Loss Functions
33
Proofs about two-sided PE & AltGDA
34
F Proofs for Input-Optimizattion Min-Max Games
40
G Proof's for Ceurae-Parameters Min-Max Games
46
H Clarifications
51
H.I Smoothness on variables or Map
H.2 Refined Upper Bound Expression for Lyapunov Potential Po
51
H.3 Random Initialization: How restrictive results?
52
Discussion & Future Work
53
1.1
Deep Learning Perspective:
53
I.2 Game Theory Perspective:
54
25

---

A Further Discussion in Prior Work
A.1 Optimization with Hidden Structures
Hidden convexity has offered a pathway global convergence even in otherwise nonconvex problems. Early developments include the use of hidden convexity in the analysis of cubic regularization for Newton's method [81], which achieved global rates under suitable curvature conditions. Extending such frameworks to non- non-smooth or stochastic optimization, however, remains an open challenge. More recently, hidden convexity has been exploited across wide range of applications, including reinforcement learning [54, 129, 126]. generative modeling [63], supply chain management [42, 24), and neural network training [1] Further, [11] studied optimization via biased stochastic oracles, developing algorithms with Ō(c-2) or Ō(c33) iteration complexity, depending on the oracle's 's stability, and recovering new results for hidden convex problems as an application. Prior to its adoption in game theory, policy gradient methods in reinforcement learning have leveraged hidden convexity to establish global convergence guarantees [129, 8). often relying on variance-reduced estimators or large-batch assumptions. Relatedly, hidden convexity also played a crucial role in quadratic optimization problems [9, 107], revealing convex-like structures within certain nonconvex programs.
Turning to min-max optimization, hidden convexity has proven essential for addressing the limitations of classical algorithms. Vlatakis- SiaakkisGGaraakounii. Flokas, and Piliouras [1]4] demonstrated that even benign-looking hidden zero-sum games can exhibit cyclic behaviors or divergence when trained via vanilla gradient descent-ascent (GDA). Motivated by such failures, Vlatakis Gaaaiiis--aaraaouiiii Flokas, and Piliouras [115] introduced the formal concept of hidden-coneed hidden-concave games, providing the first convergence guarantees for GDA in nonconvex min-max settings under suitable structural conditions such as strict or strong hidden convexity. Parallel research on non-monotone variational inequalities has developed continuous-time flows that exploit hidden convexity- structures to ensure global convergence [79]. Extending these ideas, Sakos al. [99] provided a fully discrete-time algorithm along with provable guarantees for stability and convergence in hidden convex games-filling filling important gap compared to previous continuous titiiuuuuu-tmme results. Moreover, recent work has investigated preconditioned algorithms for hidden monotone variational inequalities, including Newton-type approaches [29]. Further discussions [29] have clarified under which conditions both the latent variable space and the control space can be bounded, while maintaining uniform lower bounds on the singular values of the players' Jacobians, critical requirement for robust convergence guarantees.
A.2 Simultaneous, Alternatinent and Extrapolated Dynamies in Convex-Coneave Min-Max Optimization
Min-max optimization algorithms have long-standing history, dating back to the original proximal point methods for variational inequality problems Martinet [74] and Rockafellar [93]. Below we present some
A.2.1 The classic regime
To set the stage, consider the classical min-max problem of the form min, max, f(z y). a funda- mental template across optimization and game theory. The most natural extension of gradient descent to such settings the gradient descent-uscent (GDA) method [36], which iteratively updates x to decrease and to increase f. GDA comes in two flavors: simultaneous (Sim-GDA), where x and y are updated in parallel, and alternating (Alt-GDA), where updates occur sequentially.Howw despite its simplicity, even in basic examples such as the bilinear game min, max, æy. Sim-GDA exhibits unbounded divergence, while Alt-GDA produces bounded but non-convergent iterates that circulate indefinitely [7, 49, 50, 128).
settings, vanilla GDA fails guarantee convergence. In
These deficiencies have led to the development of refined algorithms designed to stabilize min max dynamics, including Extta-Grradeen methods [64], Optimistic Gradient Descent [91], and negative momentum variants [50]. Many of these methods achieve accelerated rates compared to plain GDA, particularly under smoothness and convexity assumptions. Nevertheless, the bulk of this literature focuses predominantly on Sim-GDA-typp algorithms, largely due to their analytical tractability.
26

---

Yet, in many real-world machine learning applications, particularly adversarial training scenarios like GANs, alternating updates more naturally model the dynamics: the generator and discriminator adjust sequentially based on each other's i output. Empirical studies [51, 76] suggest that Alt-GDA often converges faster than Sim-GDA. Despite these observations, the theoretical foundations explaining the advantages of alternation remain relatively underdeveloped. A notable advancement toward understanding this phenomenon was provided by Zhang et al. [128], who analyzed local convergence rates under strong convexity-concavij (SCSC) and smoothness assumptions. Their results show that, locally, Alt-GDA achieves iteration complexity ((k) compared to the slower Ō(x²) of Sim- GDA, where k = L/ denotes the condition number. Nonetheless, these results are limited to local convergence- i... after the iterates are already sufficiently close to saddle point-and and do not capture the full global behavior. More recently, further refinements have been developed combining extrapolation techniques with alternation to achieve nearly optimal condition number dependence [66].
A.2.2 The Pł.-Regime and Nonconvex Min-Max Problems
Research has also intensified on extending convergence guarantees beyond convex-coneave settings to munconvex-nonconees games [105, 21, 92, 109, 68, 1]. The majority of these early works often focused on settings where the objective is nonconvex in æ but concave in y, and proposed algorithms that either solve inner maximizations exactly or rely on strong assumptions (e.g.. Minty Variational Inequalities [68]). Others, such as Abernethy, Lai, and Wibisono [1], introduced Hamiltonian-tye -type information. Recently, Nouiehed et al. methods for nearly bilinear problems but relied on second-orde
[84] studied a class of minimax problems where the objective only satisfies a one-sided PÊ-condition and introduced the GDmax algorithm, which takes multiple ascent steps at every iteration. However in our case (i) we consider the two-sided Pf.-condition which guarantees global convergence; (ii) we consider AlGDDA which takes one ascent step at every iteration. Another closely related work is [18] The authors considered a specific application in generative adversarial imitation learning with linear quadratic regulator dynamics. This is a special example that falls under the two-sided PÊ-condition.
In contrast, a major breakthrough in capturing global convergence via first-order methods was provided by Yang, Kiyavash, and He [124]. They introduced the concept of two-sided (PL) inequalities for wonooneee--onnncawve min-max games, showing that alternating GDA (AlIGDA) converges globally at linear rate under this structure. Furthermore, they designed a variance-reduced stochastic AltGDA method for finite-sum objectives, achieving faster convergence. Building on this, subsequent works have refined the framework: Xu et al. [122] proposed a zeroth-order variant, Liu et al. [71] analyzed randomized stochastic accelerations, and Chen, Yao, and Luo [20] integrated Spider techniques to improve stochastic convergence rates under PL-conditions. Extensions to more adaptive and multi-step alternating schemes were explored by Kuruzov et al. [65], aiming to further optimize the dynamics in hidden convex-concan games. At the same time [124] presented a case where simultaneous GDA will diverge from the equilibrium while AltGDA converges to the equilibrium.
Dolyak-Lojasievn
A.3
Overparameterriaation in Learning Dynamics: From Minimization to Games
A.3.1 Minimizing training loss
The phenomenon of overparameterzzatonn---ee neural networks possess far more parameters than the apparent complexity of the target function-has profoundly influenced the theoretical understanding of modern machine learning. Farly works rigorously explored how, despite the non-convexity of the training landscape, overparameterization enables gradient- methods to converge global optima [98, 38, 3]. Notably, these studies typically required substantial overparameterization, often polynomial in the size of the training data or model complexity. However, empirical observations [72, 97] suggest that even modest increases in network somtt-esmeiines adding just a few neurons can suffice for successful training, motivating a closer study of mild overparameterizaatio..
can
pivotal theoretical lens for understanding this success is the Neural Tangeni Kernel (NTK) frame- work [57]. In the infinite-width limit, training dynamics linearize, and gradient descent effectively follows a kernelized gradient flow determined by the NTK, which remains nearly constant throughout training. Thus, convergence can be ensured if the NTK is rell-condiiionedd-ppciiiie
if its
27

---

minimum eigenvalue remains bounded away from zero. At finite but large widths, convergence analyses typically require proving two properties: (i) the NTK well-conditioned initialization, and (ii) it remains stable during training [85, 27, 13].
Recent works have sharpened the quantitative understanding of this regime. For instance, Song et al. [106] demonstrated that network width of approximately (n2)/) suffices for global convergence at linear rates, improving previous state-of-the-arr requirements. In parallel, studies such as [13] established NTK lower bounds that allow optimization with few as Q(vn) neurons, bridging optimization and memorization capabilities. Yet, most of these developments operate within mini- mization frameworks- fitting labels or adversarially robust losses [17]. The transition from minimization to games (c.g., adversarial training, multi-agent learning) brings new challenges.
A.3.2 Adversarial Losses and MARL
In adversarial learning, recent works have analyzed overparameterizee adversarial training primarily from a minimization perspective, focusing on robustness against worst-case perturbations rather than strategic interactions between agents [132, 45, 25]. While robust losses (and closer to our setting) induce non-convexity, the optimization target remains a minimizer rather than a saddle point.
In multi-agent and game- theoretic settings, the literature is comparatively sparser. Policy approx- imation in multi-agent reinforcement learning (MARL) typically relies on either tabular or linear architectures [118, 108), and extending sample-efficient learning rich function classes like neural networks remains a frontier. A notable contribution in this direction is the work of Jin, Liu, and Yu [58]. which introduced the Multi-Agent Bellman Eluder (BE) dimension as a complexity measure for MARL, enabling sample-efficient learning of Nash equilibria in high- sigh-dimmnsionall spaces. In the con- text of Markov Games, Li et al. [67] studied Nash equilibria computation using kernel-basee function approximation, highlighting the difficulties of exploration and generalization in -ige-iimensionl,, non-convex settings.
Despite these advances, a comprehensive theory connecting overparameterization, NTK stability, and global convergence in multi-agent games remains largely undeveloped. Key questions include:
How does overparameterization affects the conditioning of multi-agent dynamics?
whether can alternating optimization (as opposed to simultaneous updates) exploit NTK-like stability, and how regularization architectural choices influence convergence in strategic environments?
Our work contributes to this growing effort by combining insights from the large-scale network mapppings perspective with recent advances in hidden convexity and PL conditions for noncon- vex-nonconcave optimization. In particular, even strategic modeld via hidden nonvex-concave games-admit global convergence guarantees with simple gradient-based methods, provided the trajectory stays within controlled neighborhood of initialization where the Jacobians remain well-conditioned.
highlight that under mild overparameterizattin,
A.4 Some Empirical Studies Demonstrating Need of Larger Neural Networks for Zero-Sum Games
Since our work pertains to estimating the amount of overparameterization needed in neural networks for solving various zero-sum games, highlight some of the works in various applied min-max contexts adversarial training, GANs, DRO, and neural agents which show that larger, overparam- eterized neural networks lead to improved convergence and performance. For instance, in case of adversarial training, Addepalli et al. [2] show improved robustness and performance in adversarial training with larger models. few other works [61, 14, 100] empirically demonstrate how using larger architectures in GANs improve the training stability, and the quality and variation of generated images. In the realm of LLM Language agents, Karten, Nguyen, and Jin [62] show improved performance using GPT-4.0 as opposed to smaller L.MSs. In the case of DRO, Pham et al. [88] show that bigger neural networks may yield better worst-group generalization.
While our main results (Theorem 3.8) concerning neural games may largely be seen to be of theoretical interest without an empirical component attached we refer interested readers Appendix C for experimental validity of our main results concerning the input games (Theorem 3.5).
28

---

B Examples/Applications based on hidden min-max games
In the following, we present a series of examples illustrating instances of hidden convex- min-max optimization in neural network- based settings. We distinguish between two main types of problems:
Problems where the optimization is performed over the parameters of the neural networks, given fixed dataset (training over network weights).
Problems where the network parameters fixed (randomly initialized), and the optimiza- tion is performed over the input space (input-optimization games).
B.1 Neural Min-Max Games
We begin by illustrating two canonical examples of inpud-optimization games that naturally fall within the hidden sauvex-concar min-max framework. Both examples demonstrate settings where neural network mappings induce structured, but hidden, convexity and concavity, which can be exploited for provable convergence.
Example B.1 (Generative Adversarial Networks (GANs)). Generative Adversarial Network (GAN) formulates a two-player minimax game where the generator Gg seeks to produce samples that resemble reference distribution Pústu while the discriminator D& attempts to distinguish generated samples from real data. The corresponding min-max problem reads:
min max
(0, == Ex-pon [log Do(x)) + Ea-po [log(1 - Ds((r)))
Assuming that both Pdata and admit densities and that the support of pe lies within the support of Pdatu- one can reformulate the problem via a latent conve--concave structure. The min-max formulation arises naturally as the generator seeks to minimize the ability of the discriminator to distinguish real from fake samples, while the discriminator simultaneously maximizes its classification performance, thus modeling an adversarial dynamic between two competing objectives. Specifically, considering a distribution p(x, x²) that samples either a real or generated point, the loss can be decomposed as:
L (D' ) == log D(x) + p'(x') log(1 - D(x'), Pdaca(x')
which is jointly convex in p' and concave D. Consequently,
(0, )=,"")>> [L (oo(
exhibiting the GAN training objective as a hidden convex-concave game.
Example B.2 -Domain-nvvriint Representation Learning (DIRL)). Domain adaptation aims train models that generalize across different domains, despite distribution shifts between training (source) and deployment (target) environments. popular approach [44] involves learning representations that are: (i) predictive of labels in the source domain, and (ii) invariant to the domain classifier distinguishing source versus target samples. This leads to the following min-max problem:
min max L8 Pe [e(fo, (ge, (x)), (z)), v)] AlE (eT (ge,
(90, (z))
0g Uy'
where: (i) ge, is the feature extractor, (ii) fa, is the label predictor, (ii) fb,. the domain classifier, (iv) denotes the classification loss, and (v) Psoance Pmix are the source and mixed domain distribu- tions, respectively. When the loss function is convex with respect the neural mappings, the hidden convex-concave structure becomes apparent, fitting naturally into our theoretical framework.
Example B.3 (Robust Adversarial Reinforcement Learning (RARL)). One of the major challenges in reinforcement learning (RL. is the difficulty of training agents under realistic conditions, often due to costly data collection or limited availability of real-world environments. To address these challenges, Pinto et al. [89] proposed adversarial training framework wherein learner agent and an adversary play against each other by solving the following min-max optimization problem:
min max Eggrp, wpo (t), a aRownng 8,
Σ
rl (s., az)
Og
29

---

where: (i) Me, is the learner's policy network, (ii) ve, is the adversary's 's policy network, (iii) rl denotes the reward function, and (iv) p is the initial state distribution.
In this setup, the learner seeks to maximize its expected reward, while the adversary perturbs the environment dynamies minimize the learner's performance. Such adversarial modeling captures different sources of uncertainty: either unknown variations in the underlying Markov Decision Process (MDP), or deliberate adversarial attacks aiming to degrade the policy (e.g., disturbances in robotic control tasks or adversarial inputs in sensor-based systems). Hidden convex-concan structures can naturally arise when suitable regularizations or smooth policy parameterizations are enforced.
Example B.4 (Adversarial Example Generation (AEG)). In an Adversarial Example Generation (AEG) setting, the goal is to generate adversarial perturbations that cause misclassification by fixed classifier fe- Formally, given clean samples (It, y) ~ Pdata- a perturbation generator Ga seeks to find an adversarial input x' satisfying a distortion constraint (e.g., || 2'looo S E) that maximizes the classification loss. The underlying min max optimization is:
min max 0
(O, Ø) == (B(e'.))<p [0(o('))
where denotes the cross-entropy loss. Here, the generator (adversary) maximizes the classification loss while the classifier seeks to minimize it. Under appropriate conditions the neural network mappings and smoothness the loss, the adversarial game admits a hidden convex-concave structure that can be exploited for convergence analysis.
B.2 Distributionally Robust Optimization
In many machine learning applications, models are trained under the assumption that data drawn from fixed but unknown distribution. However, real-world deployment often leads distribution shifts (e.g., label noise, adversarial perturbations, or changing environments), which can severely degrade performance. A principled way address this issue is through Distributionally Robust Optimization (DRO) [77, 123]. where the model is trained to perform well against the worst-case distribution within a prescribed uncertainty The corresponding min-max optimization problem reads:
ØRo E arg min max (()))) (((hg(z)) (2),
PEP
where: (i) he is the predictive model parameterized by 0, (i) E is loss function (c.g., cross-entropy), (iii) P is an uncertainty set containing distributions representing expected perturbations. Hidden convexity emerge when E is convex in the model outputs and the uncertainty set P is suitably structured.
Example B.5 (Parametric Distributionally Robust Optimization (Parametric-DRO)) While classical DRO assumes that the uncertainty set P is specified manually, identifying appropriate P is often challenging, especially at large deployment scales. To overcome this, Michel, Hashimoto, and Neubig [77] proposed modeling the worst-case distribution using parameterized generative model qu-
The resulting parametric DRO problem reads:
go y) (()(()))))) Two (x, y)
min vi K KT(as 190g) )S
max
E ((x.))~
where: (i) hi is the predictor network, (ii) qu models the perturbed distribution, (iii) 4% approximates the empirical distribution via maximum likelihood, (iv) controls the size of the KL-divergence ball around qu This formulation transforms the DRO problem into min-max optimization between the model parameters 9 and the perturbation parameters vi, both parameterized via neural networks, framework under appropriate regularization. Observe
fitting naturally into the hidden that by Pinsker's inequality we get that KL-ddivergence over -norr..
B.3 Input-Optimization Min-Max Games
A recurring structure in adversarial and robust optimization tasks involves optimizing over input spaces rather than model parameters. Based on Wang al. [117] we describe three prominent examples of such input-optimizattion games below:
30

---

Example B.6 (Ensemble Attack over Multiple Models), Given K machine learning models {M 1 the goal find a universal perturbation ó that simultaneously fools all models. The corresponding input-optimization game reads:
2 211u - 1/K 1/
min max WEP
wt
where encodes the relative difficulty of attacking each model, and 7 is regularization parameter. Example B.7 (Universal Perturbation over Multiple Examples), Here, given set of examples {(zy, y/ 3- the objective is find a perturbation that simultaneously fools all of them. The optimization problem becomes:
min max Σ w. f(; v:.
? 2ll 1/ 2
This mirrors the ensemble attack setup, but focuses on perturbing multiple inputs under a fixed model M.
Example B.8 (Adversarial Attack over Data Transformations). Consider robustness against transfor- mations (e.g., rotations, translations) applied to the inputs. Given categories of transformations {p:} the optimization reads:
7 ||w 1/K WrEapp [f(t(xo + 8); yo. (o.30.M) M)]
min max SEX WEP
2
where / denotes random transformation sampled from pt. When w 1/K, this recovers expecaation-overttaaffoaaaal (EOT) setup.
Observe that under a convex loss function f with respect to the neural mapping M(1, + 8) (i.e., hidden convexity in 8), and given that appears linearly in both the bilinear coupling and the individual regularization term of separable framework of Section 1.1, the structure fits naturally within our hidden results are stated for unconstrained min-max optimization, there are two standard ways to extend our analysis to constrained settings:
conecvee framework. Albeit careful reader might observe that our main
First, by employing the two-proximal-PL. framework developed in Kalogiannis et al. [60]-an improvement over the earlier formulation of Yang, Kiyavash, and He [124]-our convergence guarantees naturally generalize to simple constraint sets, such as balll for perturbations and simplices for the mixture weights w.
Alternatively, the constraints be incorporated directly into the objective through suit- able Lagrangian penalty terms, thereby reducing the constrained min-max problem to an unconstrained form amenable
techniques.
Unified Perspective. Across these examples, input-optimization problems naturally exhibit saddle- point structure, blending adversarial robustness objectives with min-max optimization techniques. They provide concrete and practically motivated instances where hidden convexity can be exploited ensure convergence guarantees for training and robustness analysis.
31

---

C Demonstrating Empirical Validity of Main Result for Input Games
We consider hidden game of Rock-Paper-Saiie activations) are playing the game of the Rock-Papee Kock-Paper-Sciisonn we use random Gaussian initializations for both the neural network players as described in Theorem 3.5 to define our input game of Rock-Paper- PPaper-Scissoos, and if we use AltGDA for finding min-max optimal strategies for both these neural network players, then the players indeed reach the e-Nash equilibrium. In particular, both the neural network players control 5-dimensional vectors 0, Φ E R and output a latent strategy that lies the 2-dimensional simplex, A2. Both the players are optimizing the regularized bilinear bilinear objective:
where 1-hidden layer neural networks (GeLU
We will see here (empirically) that, if
() F(O)" AG( e/21 1/3 - -/311(()))13(11111))) 1
where (1/3, 1/3, T/3)" indicates the (unique) e-mixed strategy Nash equilibrium for both the players
0 -1
and A 10- 11
1 is the payoff matrix* for the Jock-Paper-Scisson game.
Since the actual strategies of the two neural network players (0, Φ)) lie IR we can't 't visualize those. However, we visualize their strategies in the latent space, i.e., in the 2-dimensional simplex instead. Figure 2 below illustrates the AltGDA trajectories for both the players (step-size 0.01, maximum number of steps 100, 000). As we can see, both the trajectories converge the e-Nash equilibrium of the hidden game.
Player 1 (@)
Player 2 (Φ)
P
P
S
R
S
R
Initial
Final
Equilibrium
Figure 2: trajectory of AltGDA in an lg-regularized hidden game of Rock-Paper-Seissonn These trajectories correspond to each player's 's strategies in the latent space (2-dimensional simplex).
'A scaling factor of 10 was used in the payoff matrix to ensure that the gradients are not too small for the AltGDA updates.
32

---

D Controlling the Gradient Growth: Bounds and Examples for Different Loss Functions
Controlling the gradient growth is critical for non-asymptotic overparameterization bounds, as it ensures that iterates remain within regions where hidden convexity persists. Below, we provide detailed discussion about this bound for some commonly-used loss functions.
Mean-Squared Error (MSE) Loss: One of the most commonly used losses and is suitable
for regression tasks. For given labelled data point (z. y) where I E X and y V/ if the predictor function parameterized by parameters @ is defined as h == h(z; 0), we see that the MSE loss can be defined as:
1
Ely, h)) 2 1Iv h1l2
(11)
Vul(u,)) h y
(12)
VR bill S ||Al|| + |vll
(13)
||||| diam())
(14)
V hill S A |/Al + Aydiam())) + As
(15)
where A1 = A2 = and A3 = 0. More generally, if we had E(y. h)) l L1 we
would get A3 and A A2 1a where μ is also the hidden-strong convexity modulus.
Logistic Loss: Commonly used in binary classification, where y {0, 1). and the prediction h = h(x;; 0) E IR is passed through the sigmoid function. The logistic loss is defined as:
Ely, h) -y yyloo (h) (1 log(1 (h)), where oh) I+e-h
(16)
Vxlly, ((h) yy +|Vaely, S
(17)
(18)
Since the gradient is always in the interval 11, we can take A = 0, A2 = 0, A3 = 1. The logistic loss is strongly convex over compact domains or when regularized.
Squared Hinge Loss: Used in support vector machines (SVMs) with margin- based formulation. For y E {-1,1} and prediction h = h(2; 0) E R:
fly, 2 max (0, yh)²
(19)
vul(y,)) { [-v(1 - -yh,, if yh < 1
(20)
(0,
otherwise
VV A)]l S 2|yi|hh| + < 2||h|| diam()")
(21)
Thus, we can choose constants Aj = 2, A2 = A, = 0. Note: the hidden strong convexity
applies within the active region yh < 1, and regularization term often ensures global strong convexity.
Cross-Entropp with re-reuularizttion: For multi-class classification with softmax outputs h E RR, target y E A k-1 (probability simplex):
fly, hi) Σ yk log
e
1111
A
(22)
Σ chi
v h) softmax (h) - Xh.
(23)
V hi]l < [|softmax(h) wll - A|llll < 2 + A|ll
(24)
So the gradient norm is bounded by A₁ X, Ag = 0, Ag = 2. The &g term ensures strong convexity with modulus X.
33

---

E Proofs about two-sided PL & AIGGDA
We begin by recalling the definitions of unconstrained continuous min-max optimality conditions of problem:
min max L(0, ())
+
Definition E.1 (Global Optima). We define three equivalent notions of optimality:
1. (0", o*) is a global minimax, if for any (0, o): _(0", ,0) z C( Φ²) S max C(0,0)
2. (0", Ø²) is a saddle point, if for any (6, o): ( .9) E C 1 0()
3. (0", (b*) a stationary point, if for any (0, +): VoL(0" x0) = v x5) =
Thanks to gradient dominance of PL conditions, it is possible to prove the equivalence of these notions under two-sided PL condition. Observe that this reduction is crucial since gradient-based methods provide safely just stationary point while the other two notions are global and non-trivially verifiable.
Lemma E.2 (Lemma 1 in [124], Appendix C in [60]). If the objective function L. satisfies the two-sided PL condition, then all three notions Definition E. I are equivalent:
c (Saddle Point)
e >
(Global Min-Max) =
(Stationary Point)
Ve
Before we present the following lemma, we provide some intuition: This result characterizes the behavior of the optimization trajectory under hidden convex-concave structure, establish- ing a critical link between parameter dynamics and convergence guarantees. The lemma will formalize how small distortions in the hidden geometry impact the optimization path based on parameters a.c.
Lemma 3.2 (Theorem 3.2 [124]). Suppose the min-max objective function C(0, Φ) is c and satisfies the two-sided Pt-condition with (po,)e) Then if we run AltGDA with иj0 181
and no = T then |0++1 - 0ell + - S /act/2/PP where constants and e (0, 1) depend only on Lvc, Ha, Pig and Po is the Lyapumov potential at time t = 0. (Please refer to Remark E.5 for the exact expressions for and c.)
In most existing works on nonconvex-nonconeee optimization, smoothness is typically defined directly with respect to the optimization parameters. However, given our focus on fine-grained analysis of neural min max games, it is equally important provide similarly fine-grained treatment of upper bounds involving the geometry the neural maps.
Although a neural network is, in practice, highly smooth function, global Lipschitz continu- ity is incompatible with strong convexity in unconstrained domains. Nonetheless, within bounded region- -uchhuuhhhh as the ball of radius where our iterates remain localloclll Lipschitz- ness can be rigorously characterized. The following lemma formalizes this bounds for both maximizer & minimizer neural network:
Lemma E.3 Lipsh--siss for smooth loss function). Let Fo and Go be neural network mappings such that they are 3p and Ba smooth as defined in Definition 2.3, Now let (0o, Φn) be such that Jacobian singular values for both the networks are strictly positive and bounded from above and below, Pln < (( ( S Vin and 1l
(F)
(G) S oVV S v Suppose the
stationary pointfor for min-max objective L(Fo, Go) as defined in Assumption 2.1 also lies in the ball, (0", (0*,)*) B((O0. do), R). Then there exists an R >> O such that V(0, Φ) E B((O,, Φo), R), we have
max VVVG, C(Fo, Go)ll, max 1| C(Fo. G&) S Loe BEB(0,,I1)
(25)
(E
where we denote the upper bound as an 'active' Lipschitz constant Lagt
L = 4.5L% (..5svcmmaax// (va V/c (G)
(26)
34

---

Proof. Using Lemma I of Song et al. [106] as discussed in Section 3, if we choose R = Mic. where
Mlae == max (F)
} and B == min (fr, 8a), then we see that for V(0, Φ) E BB(00, Qo); R),
1/
we have
(F)
(F)
Mlu
I Omiu (VFF)) I max (VFF)) -
3 Jac
2
2 (G)
(G)
Pjac
S m (vGG)) S max VvG S
32 Juc
2
2
And by Lemma (Appendix C) of Song et al. [106], we see that both the mapping F's and Go are
Lipschitz-continuonn in the ball (((b), Φu), R). That is, v(0, o), (6', d') ((0b, Φu), R), we have the following:
(F)
31/
|I - Foll -
|0
01|
(27)
2
3/ Jac
(G)
[|G - Go 11
1100 6'll
(28)
2
where o max (V. S Dhs
(F) and (V S
Vacc
(G)
Without loss of generality, we prove for the case of Fg mapping as the same argument works for the Go mapping as well. We can observe the following for any (0, Φ) E B((0, Φo), R)):
max | F. ((Fo, Gb)l = V ((F', G+)ll + RE
max (EB((
1VF,((FF Gb) - FF C(Fo. Go)ll
W V F. (FFo Gb)ll + LVc max || FBoll 8'EB(%,.R)
3
(F)
< 1r, Go)ll +
Iuc
max D'E
1100 - 8'11
2
(: By (2.))
3 (F)
R
I Go)ll +
2
(F) 3L R
= IVr Go) - [F,,(FE,,GGr Go
(29)
2
=0
where the last equality holds true because (0', (²) a stationary point for the min-max objective C(Fo, Go) and the Jacobian for F is non-singular as (0", o²) E B((O0, (()), R) by assumption. That
is,
0 = VoL(Fo. Gx) = (VoFo.) FF C(Fe. F.. Go)
(30)
0 (( VF, V G
(V T FIIV Go
(31)
0- C(Fo G (:. Fg. non-singular)
(32)
Thus, continuing from Equation (29), we have that that for any (0, E B((O,, 60), R):
(F)
3Lv c/cc R
max (E
FF, Go)ll < FF, C(Fes: Go) C(Fo.
2
< Lv Fo. + |/ Go-ll) + 3L CLvc (F) R
(:: L is I=g--smoth))
(33)
3 Inc
(F)
3l (G)
3 3L
(F)
R
110.
-0-1 +
1100 -0 +
Inc
2
2
(:: By Equations (27), (28))
(34)
3 max Inc , 110
< अ max ( 1uc 1 R +
(G)
2
= 4.5Lve max 1/c R
(F) (G)
(35)
35

---

To establish convergence guarantees under hidden convex-concave structure, it is essential to demonstrate that sufficient overparameterization yields a favorable initialization. Specifically, we show that: (i) the initialization lies close saddle point (in terms of gradient norm), and (ii) the optimization path remains within a region where the neural Jacobians have well-conditioned singular spectra. The latter will be ensured via path length argument.
The following lemma provides key component in this direction: it connects the initial value of the Lyapunov potential used in AltGDA (a weighted version of the Nash gap) to the gradient norms of both neural players. In subsequent lemmas, we will show that with high probability, and under sufficient width, this leads to the iterates remaining inside manifold that preserves PL-condition throughout training.
well-conditioned-Jccbbb
Lemma E.4 (Upper Bound on Initial Potential Po; Lemma 3.3 in Main Text). Let Fg and G& be neural network mappings such that they are By and ßG smooth as defined in Definition 2.3. Now let (0o. Φo) be such that Jacobian singular values for both the networks are strictly positive and bounded from above and below, ( I a (V S v!T and p S (Go S v/ou Suppose the min-max objective [(6, 6) is (Pg. Ho) -HSCSC. Then the initial Lyapumov potential Po can be bounded from above as:
Po V (1( F. [(F.: Gool)
|VL[ Φ0)1
(o (F))
1
[1V F. C(Fo, Goo))
3F
VoL(Bo. do)1
(36)
21
+ +(++A)
Goo))
11
VV Φo)1
(G)
(1+ 11 C(Fo Gov)) T1 Ba
V Φ C(., o0)l
(u)
Proof. Using Lemma 1 of Song al. [106] discussed in Section 3, if we choose R Aiee
where
2
(F)
[G)] ] and B == min [3p, $c). then we see that for ((0, Φ) E B((o, Φ0), R).
Mlac == max MMac . Mice
we have
(F)
(F)
min (Vele) S max (Vo1)) S
2
2
Pinc
(G)
< minn GV)Gg) S max (V Gv)Gg) v
3
2
2
And by Lemma (Appendix C) of Song al. [106], we see that both the mapping Fo and G are Lipschitz-continnuus/ in the ball B((O,, Φo), Rt). That is, v(0, の), (0', Φ') E ((0,, Φo), Rt), we have the following:
(F)
FFa Farll 5
lsc
110
0'1
(37)
31 (G)
||G Go 5
|10 ø'll
(38)
2
where maxx max (Vol'o.) S Ine and max (VoGoo) S (.)
(F)
Since L is (No, Us) -HSCSC, it satisfies 2-sided PL-condition with PL-moduli as per Fact 2.6. Thus, we can obtain the following bound for Wo:
Wo = L(0o; 8" (6o) - L(O0,
(39)
< (Va, C(Fr, Goo)) T (Go - G((o)) (: hidden concavity)
(40)
< [[Va,L(Poo Goo || [[G - Gool
(41)
< C(Fo,, G 1|. (IV,G roll + _G (00) - -2oll
(42)
2
36

---

(:: G& is sm-sth)hh)
- ((F Gou))
Jac
(0)
(0)) -boll +
_a (00 -Qall?
(43)
2
(: (Voo())) 1 $1/000 (p))
$ a.. C(Fo.. [(Fov Gov)) 11 Vaac
(G)
2
V ((06)))(0)) C(0o, ou)
V po
po(uin)
12
3g (C(00, x (06)) L(oo: obo))
(44)
Holuia
(:: quadratic growth condition and Fact 2.6)
1
Wo < C(Fo Goo)) Vie
|I
V 60)
n (G)y2 y2
+ +l(V,, ((Fo, Goo))
Bc
|V 20)
(45)
2p
(1
(using PÉ--conitionn and Fact 2.6)
Similarly, for Un we can say that:
Un = C(ou. o² (9o)) - C(B",
(46)
I C(Ou, o² ((o)) L(0", 000 (:: L(0", .0) L(0", ,6" Vo)
(47)
I C(0o: o" (0o) - C(0 (on), 2n) (:00 on) 2 ((0)(())))) Φn))
(48)
C(Bo. o² (8o)) L(Ou, Φu) + L(00, L( (du), 20)
(49)
Noticing that ! is exactly equal to Wo and following similar arguments we used for Wo to get upper bound for but with hidden convexity instead, we obtain the following for Ug:
Un < || G. C(Fo, Gom)) T
|1 v/
1
|V Φn)1
+
Goo)) 111))1111111 3c
|| V C(0, 20)1
(50)
2n (14
(0))+
+ II(V Po C(Fo. Goo)) (F)
VoL(on øn)
no
(
(F))²
1
I(VF, Goo)) " BF
VoL(6o, do)1
By combining the upper bounds obtained for Up and Wo. we get the following upper bound on the initial potential Po:
Po < II(V F, C(Fos: Goo))
VVL do)1l
(F))²
+ C. Goo))
3F
V do)ll
(F))11
2
(1
+(1+ [[[Vo, Gæv))
(G)
1
1VV do)1l
(G)
+ -1++A) A) ([VVo,L(Po) Goo))
Bo
|V
2p
(c))
37

---

Remark E.5 (Path length bound for AlIGDA), We know from Lemma 3.2 that the AltGDA path length satisfies:
V2a1
((T)
(10,+1 - -8el + 1-10041-0000 -
- 1 VV
Vo
(51)
2=
1 + Vc 2a
2/201 1-c
VPo
VPo (:0E (0.1))
(52)
1-c c
where 01, L, and e are defined as
01 2(1 +
20(1 + L ) L + 201
(53)
H4
1
L= Ivc +
(54)
c= 1
(55)
36( 36(Lvc)3
Now, say we define T to be the first time instant when (0r,er) & BB(O,, Φn), R) for an appropriate R >> O. And now, say, start with appropriate (On, Φo) such that {(T) < R. A sufficient condition to ensure this would be to find (fo, Φb) and a corresponding radius R > such that
2/201
V
Po
R
(56)
1-c C
On
R²
Po <
(57)
(1 c)2
8
12961 pgu
R²
Po
<
(58)
8
Remark E.6 (Simplification of on for AlIGDA Path Length Bound). For the case of (po, Pb)) HSCSC and Leg-smooth (w.rt. (0, Φ)) min-max objective function & and for learning rates fjo =
cop? ot min (VoGoo) and 17-- = Lee with 0 < ca. Co S 1, we can simplify a₁ defined above in Equation
Go_
18L
(53) for AliGDA path length bound as follows:
2(1 + DELLL
20(1+ + mEL + 201
01
1000 min' (V.
Mgoiin (V&Goo)
(59)
20 cou 2 Φ min VoGoo)
20c 4 20 G (V&Goo)
(60)
(18)² L2 2000 No
min (oFe.))
182 2 C
In fact,
12961 18ng
01 simplifies to the following:
12961
19g
a1
pg min (VeFe, Jo (VeGou)
e0
(61)
Palgo min (o Fo, Jo C (V)
Lemma E.7 (Simplified AltGDA path length bound condition). Consider the premise as defined in Lemma 3.2 for Ho)-HSS-SSCSC and -mooth min-mac objective with learning rates nh 1o12//1822 and no = ca/ Lve with co. Co E 10, along with the premise of Lemma E.4. Let T be the first time instant when (OT, ΦT) & B((O,, do), R) for an appropriate R > 0. Then to ensure (1), E (00,, 6o), R) VL S T as discussed in Remark E.5 (Equation (58)), the following is sufficient condition:
R22
O Goo Ml + IIV of C(F GoD S
(62)
38

---

given that and co are chosen such that:
1
and
cΦ 1
(63)
/4 4. Ag B
where
(1 IV (1+ [(F6) Goo)ll) (1 8 cuee)) (1+
1 (1( )
1
Ao
(1+ VV Gæo )l)
((1 80L (n) (1+
(1 + BLF
1 ( (p
(1+ + 80L
nBt (ulte)))))
(1+
I 2 (ui
1
(
and
B$ [1+ C(Fe: Gov)ll) Go))::
(1+
1 (w ( ) (1+
1
(1+
M Mo(uban 10ya)) (1+
1
1 (a (c))
(1+
(+
(1+ (1+ Vo G Go (1 100L=2200 (10) (1+ - 36)
) (1+ (L+88063))
(1+
1+
p (1 (
(H (c))s
Proof. By choosing ca and es as specified above and using observations from Remark E.6 (Equation (61)), sufficient condition to ensure the iterates never leave as derived in Remark E.5 (Equation (58) can be further simplified as follows:
1296L palu
R Po
ai
2g. 2
80c 2
R
Po <
1 0b min Fo oa min
(V Go)) Pallar min
min (Vo Fo, )oz min (V Go
R²
Till CoCo,, @l) T2 C(C, d0 + T3lIV & C(bo. d0)1 I. C(b,, @0)
8
where T} are coefficients of the gradient norms as per Equations (61) and (58). Notice that both T2 and 744 contain of and per our choice of ca. că contains (Fi, and (FF, terms which can help absorb one of the powers of the gradient norms [VoL(Fo, Goo II or [V Goo)ll in terms corresponding to T₃ and Ta. This will help constructing (as shown below) a simpler sufficient condition that would require only the norm of the loss' gradient w.r.t. parameters 0, ø to be small. Furthermore, by construction, co I 1/2, Gs = 1. Therefore, we have that Ti < 1 Vi E [4]. Combining all of the above, what we require for ensuring iterates never leave the ball of radius as follows:
R
Vo Go IV Co God &
(64)
8
Remark E.8 (Local-smoottness constant). If the iterates (0,,d.) Vi stay within the ball (((0, do), R). by invoking H.3, we can use the local-Lipschitz constant derived Lemma E.3 along with the smoothness of the neural network maps (3r, obtain the exact value of the smoothness constant for the HSCSC and smooth loss as L LE max{3p. Bc).
39

---

F Proofs for Input-Optimization Min-Max Games
The following result characterizes the lower and upper bounds on the singular values of the Jacobian for the case of Input-Optimization Min-Max Games. In particular, bring out the dependence of these lower and upper bounds on the size of the hidden layer, at² and dfe) and variances for random Gaussian initializations of the neural network layers, for (f") he([3]
and for hkE(2), for both the players F and G. Computing the lower bound on singular values important as it's used in defining the radius around the initial parameters to ensure the neural network Jacobian remains non-singular within the entire ball. Moreover, these lower and upper bounds will be helpful in determining set of sufficient conditions on the variances for ensuring the AltGDA trajectory reaches the saddle point.
Lemma F.1 (Lemma 3.4 in Main Paper). Consider a neural network F with parameters 8 E Rd defined as F(0)= w((F),
(F) (W((F)) where w B x (k E (1,2)), (W(F))ss ~ NO0 (o) (P) (2) Vi,j. (W2 (P) )aa ~ (1, ())) Vk, and to is the GeLU activation function with π
de 2 25 d( 2 256d2 and (oj F) accat"1lo11
Then the minimum singular value of
the Jacobian V Fo is lower bounded as
(P)
CafeF)
min
Tinia(aol VoFo)
02
2 0i
11
101l
(65)
16
2
(FF)
c- =2 The maximum singular value of Fo is upper bounded as
w.p 2 1 - 2e-
05
max Xmax(Vol (VoFo) <3.470| (F) ( (F)
(66)
F
w.p. 2 2e
Proof. By Theorem 4.6.1 in [110], we get w.p. 2 1 - 2e 2e-
0 ((F) 4(V a +t)) s mwin (w $ Tmax (W(F)) S of +4(y +t)). (67)
+
By choosing t = VV ((()), we get w.p. 1 (f/
(F) 1 5V ( - /v/d s min (W/F)) < max
-
m (W(F)) S So (F)
(
(F)
2V [
3 ((F)
+ + (68)
If we set d 2, we get
2 ((
4v d
(FF) 2 4 V (F
(69)
and
3
4v d
- 1 V d
V
(70)
2
(FF)
Therefore, we get that w.p. 2 1 - 26
tr,
(F)
7 (F)) V ( s min (W(F)) S max ( < o / v
0
(71)
For the case of ( because we have dlf) < oif),, we will use analogous reasoning as that for
(i(F)) above for ( T with t = 1/2 3/ (T) which yields w.p. 2 1 - 2e +
(()))
(F) 2 dfF) AV
1v/p7) db²)) s σ min ((W:())T)) mmin (wi (F)
(72)
40

---

S max (W2 mmax((W2
max s 2 s (2 (V + +4VogT)
(73)
Then, by setting af 2 256dg F), we get
1 (F) di min (W) S mmxx (W(F))
7 (F)
/
(F) dfFt)
4
Note that the Jacobian for the neural network F(O) can be computed as
VoF = 00 = W 2
aF(O)
(z)) = ( (WW
(74)
dz
where 2 = 0 0 and (w( 0) = diag( ((W 0)), &' (WW (o))) Therefore, we
can compute the minimum and maximum singular values for this Jacobian F& by looking at its
operator norm: FoVl = ( (W Then, by properties of the operator norm, we that
V 2 min (W2²²) ( ( (W(P)
(75)
VoFoll < max (W2
(2) (W (F((F)))
0) |ax (W(F)
(76)
This further tells us that
min (oFF)) 2 minl (W!P*) 0 min (W 0) min (W((e))
(77)
P) maxx Fe) S max (W2 ) max (V (W 0)) max (W(())
(78)
We can further simplify these lower and upper bounds for the Jacobian singular values by noting that since T (W/FF)) is diagonal matrix, m ( (W((P)))
(x())) and min isisa(
Froax(M(( (W((( (P))) = max ('(2)) where 2, = (W( 0) Vi v (siSa(
Fmax
Now, notice that = mhat==((Fob) O'0,00~ (10001117111111111110111
(1)) - Using the fact that GeLU's derivative, di
w/, is Leg-Lipschitz with Ly SuP (x)) = (0) -7 (Gp is standard normal PDF), can appeal to concentration inequality for Lipschitz functions of Gaussian random variables and infer for
0 < E < 1/2:
Piami (W( > c| Plv:: ( (W(
(PW (F) 00))) > <))4
(79)
(P( (1)))) 1/2 c 1/2>>-1/2))) 1/2)
(80)
(P(#'((1)))) (0)) Flw'((W( (F) 0)11 c 1 1/2))41")
(81)
(: (WW(((( E((W{F)) 0) (((((((()))))) + (
(82)
(1p, are standard normal PDF & CDF, resp.)
(83)
(1/2-0)² (F 1511112
222 26f
(84)
(:: P(b((() 1/2-t] s) 111111101 choose = 1/2 - c)
(8.5)
= cd(") (if we set = 1/2 - (a (T) |10|| Ca(e1 /TT)
(86)
Therefore, as long as we have (0(7)/2
have w.p. 2 e --af" cafe) ) that
4Ca( 1op1"
caf
6 mmin (W(())))
of l1
(87)
π
Combining all of this, we can say w.p.
2 21-25 20
#
ca(f
we have:
T Mmin (oFF)) >
(F) [F) (F)
02 d
16
=
2
1
o
(F)
l0ll
Cdf F)
(88)
41

---

And w.p. 2 2- a
.FF) we have: max (Volo) <
? 7
-1.1301 02 < 3.4701 0g d
(F) (F)
(F) (F)
where we used the fact that max 1 (x) v'' 1.1289.
Before we present the following lemma, provide some intuition: In addition the previous lemma for high probability lower and upper bounds on singular values of the neural network Jacobian, are smooth or not. Towards that, the following result proves that it is so and provides the exact smoothness constant. Computing this smoothness constant is important for another reason: It is used in defining the radius around the initial parameters to ensure the neural network Jacobian remains non- singular within the entire ball.
also need check whether the networks in input-optimization games
Lemma F22 (Lemma 3.4 in Main Paper). Consider a neural network F with parameters 0 E RR&"
the neural network F is $y-smooth where as defined in Lemma F.I above. Then, w.p. 2 1 2e c
3F
32
Proof. In order to prove that F is 3p-smooth, we need to show that Equation 2 holds true. For 8, 8' E Rd we write
Vole VoFoll & [| v(w 0') Ii
(89)
< | (F) Taay || - w [lll] 1I ( of is Tup Lipschitz)
(90)
L W
||| (F) |1|e ('|1[W((211
(91)
- + Omax (0aax(VoF voFe) 5
0 max (W maa (w(F)) 0'll
(92)
/2T
where Luy
for derivative of GeLU activation function. Using Lemma F.1 results for singular
V2x
values of the random matrices ((FF) and W!P), we get that w.p. 1 2e 4
343(a) (F) 220 (2)
maxx Vo VoFo) s
32v2m 2m 110 0'
(93)
The result the main paper offers an average-case analysis under Gaussian sampling with variance scaled as poly(1/d,). Here, provide more detailed version that explicitly states the assumptions and technical conditions required to ensure convergence to equilibrium. While the high-level complexity perspective remains unchanged, we believe this finer analysis may be of independent interest, particularly for applications adversarial attack design.
Theorem F.3 (Theorem 3.5 in Main Paper). Consider two neural networks F, G with parameters
0 e 18% and & e 12 respectively, as defined in Lemma F.l above. Then for the e-regularized
bilinear min-max objective C(O, Φ) as defined in Equation (3) with the neural networks F' and G defined above, alternating pradient-descent-are ascent with appropriate fixed learning rates T]S 1i (see
(0)
Lemma F.7) reaches the desired saddle point w.p. 2 1 4e - -C
Ca
(C are some universal constants) if the initial parameters (0o, Φ0) and standard deviations o and
(G) Is (1,2) are chosen such that:
k
(o (1
& (0
π
(94)
4Cd (F 1012
42

---

(of (o) (02)) .100
11001
π
(95)
1 --100 (o) (o(")))110) 1100| |V Cata
8 (d F )3.
(0) (0(10)) (02 (0))2 |1001
π
(96)
E (d) G)) 33.5 (3)5
1 - (0100) 1000 IV
6 (0)) ((0) (F) yo (F)) 11101
π
(97)
o max (d) (2.)
1 - (o Cafe
( ((0 (c) 1800 ( 1o
π
(98)
1/2 (o) ( | ca
max (d)
Proof. Since C(0, Φ) is chidensssoogyyyoooeeesseeyyooon. by Fact 2.6 also satisfies the
sided Pł.-condition with (fo onin Fo) pe e o (V&G&)) w.p. 2 1 2e -e- C we can utilise path-length bound as derived in Lemma 3.2 which leaves us with controlling the potential Po for ensuring convergence to the saddle point. Thus, computing loss gradients (Equation (4)) and using the sufficient condition for ensuring iterates do not leave the ball B((O,, Φo), R) (where
R max max(ric (C))
defined in Section 3) thus ensuring non-singular Jacobian inside the ball for both the neural networks (Lemma E.7), we require the following:
min[3p.3c]
[F(())]] (5o (oFFs.) + max ( V )o
Ri2
+| +olG( (Fmax Momnx(VoRF) (Vo m + ed (VoGoo)) z
(99)
8
Thus, we want
(3.47c01 100 [|]]F(((00))+33111 (G) (G) (0) ( (A))]I((0)]]
(P) (P)
02
mmax
+(3.470 (F) (F) d( o m (A))- ||G(,)]] + (3.47c0) 02 d
(G) (G) (G) ||G()|])) x 8
R²
(100)
(:: C'xxa (o.Fo.) < 3.47o (F) (F) ( o max (voGoo) < 3.470 (G)
02 (()))
Therefore, we want the following to hold true:
1. (3.47601 02 ((2)) s R²
(P) (F) (P)
32
2. (3.470 max (A) (G) (C)
d( F(b))) s 5 02
3. (3.47o (A)o
P) (F) P2)
02 >)]
4. (3.4760 (0)
(G)
( ( (0) & R²
Since |[o()))]| S omax (w
(F) jo max (F( we can use Lemma F.1 for maximum singular
values of (F(F) and the following calculation for upper bounding (Ww(()))
( 0))1 S / aatt) max (w
(F) 8)a)
(101)
P(lo(w(( 0)| > 4 < PLy d max (w 0)² > []
(102)
43

---

Also, Plmax ((W1 0).1 > 1 s 2d 1200_
(103)
(::(()) S Vz, (F) 1
(())))
(104)
Plmax [(w] 0):1 > f 8
(105)
(Set 6 = 2d,e =2/122,, = -CCii
(106)
PIya d max ((w()))) 0),1 s C'o > >1
(107)
Thus, for ensuring 1.) holds, we will demand the following: (3.47c0
(Coof")100ola(+))
x
n² 32
This will yield the following sufficient condition on dj (F) and o2 i
R
(o) (02 & 195cC' ||0u ())5
(108)
By definition the radius R 2 Lipschitzness constant for Jacobian of network F from Lemmas F.1-F.2, we obtain:
Substituting the lower bound for minimum singular value and
28.
(o )4 2 )) -16ol
π
2 S
(109)
{ - (ol )10011l ( caf
8 s- (3.5
Analogous reasoning with 2
x 20
for ensuring 4.) holds true in case of G(do) gives us a similar
condition on o1 (c) and (c),
(0 (0)) (0, (0, (0 |000
π
(110)
1/2 (6) (1 cdf
8
(d)
3.5
(
For ensuring 2.), by Lemmas F1--F2 and using R
z
we see that we need
23
(3.470
(A)o (A)) (0) (o) (()) Vo
02
(c'o
S
nta 32
which yields the fol-
lowing sufficient condition:
(3.470| (000))1)))) (oo+) ) (cr0(911061l(tt))
Ra 320 max (A))
S
(111)
(1 FF)2
(112)
1 1280max (A)57
2
(2)
>100o|
Cdl
Fmax (A)(o(
(113)
By Lemma F.1 - F.2)
(G) (G)
02 [(0) 10,
(F) (F) 1100
(114)
max (d)
(o (0( |106||| cafe
44

---

Similarly, for ensuring 3.), we see that we need max (P) (P) d
(oogi)
(G)
V (a(())
(coo9")loolld"))) ك
R² 32
which yields the following sufficient conditions when we use R 2 Hi:;
2%
o [((0 (1) 00 (c)) 1
π
(115)
max (d) y2.
1/2 (a (01 11o0ll Cdf
(116)
(P)
Thus, w.p. 1 - 4e 64 1e
e Cdl Cdd stay within ball around the random
initializations (B Φu), R) thereby ensuring min-max objective satisfies 2-sided Pł.condition. By Lemma 3.2, given that have chosen appropriate fixed learning rates per Lemma E.7, now guaranteed to reach the saddle point.
45

---

G Proofs for Neural-Parameters Min-Max Games
The following lemma establishes a sharp connection between the spectral properties of the input data and the initial conditioning of the neural network's ' Jacobian, highlighting how data diversity directly influences the minimum singular value at initialization.
Lemma G.1 (Lemma 3.7 in Main Paper; Lemma & Appendix E.I-E.4 in [106]). Suppose
that two-layer neural network, Fg, as defined in Definition 2.3, satisfies Assumption 2.4 and 7 [b)) (T(a] T"*) respectively for all 0 < and some constants T1, r2-
Then the neural network Jacobian for a random Gaussian initialization dp ((W1)) Jos (W) )o) has the following lower bounds on its smallest singular value w.p. (p1 + P2):
(F) Pia 2 (of (ol (z
(P) min (x**)
(117)
We have the following upper bound its largest singular value w.p. 2 -p1 p3 pa):
Vuc 2 02 Uma max (X) d + (of V( (2) +2))))222dd))) + 0 (X)
(F)
(F)
(of ( yr lool V (1
(118)
And the smoothness constant for the neural network can be computed as
BF = max (X) + "maxxXmax)
(119)
where Xmaa = (! max (W: Here {aits denote Hermite expansion coefficients correspond-
ing to ((x)))))x)) 89 > 0 PAj E [4], p1 = (d(F))-Chsd
-Okid + (d| - for universal con-
2
stant C with sufficiently large k Riz D2 = cxp
(E[Ma))
where
40ja mmax
2 max (X ( val of
Mo (XXT ((XT((W())) Do) X).). Ps = exp (ox)))))))))))))))))))))))))))))
620 (E[Mol)
&
Vinaa o2 max (X 1X) 1² V d(0h) log dly)
p4 cf for universal constant C:.
Before present the following lemma, offer context and motivation: In input- optimization games, the gradient norm structure naturally arises from the formulation of hidden bilinear zero-sum games. In more general settings, the relevant properties detailed in Appendix D. The lemma below demonstrates that, under appropriate initialization and sufficient overparameterization. the neural network output remains bounded from above in terms of spectral properties of the data matrix with high probability. This property will play critical role in ensuring that the optimization trajectory remains confined within the well-conditioned region (the ball).
Lemma G.2 (Lemma 3.7 in Main Paper; Neural network output is bounded w.h.p.; Appendix E.5 in (106)). Consider a neural network Fg with parameters 0 (W/(F) w:fFl) as defined Lemma above, Suppose randomly initialize the neural network at 0g by choosing o (F) and o such that
(F)
(F)
(F)
02
V
1i d
Then w.p. 2 2 - Ps, the neural network output at this random initialization Og for the given training data Dp (as described in Assumption 2.4) is bounded from above as follows:
|F (DF) S o
(120)
where P1 = (d((F))OOhdd + ((F))-Ckzdy? for universal constant with sufficiently large K1, l2.
83 0, and ps- e -68 for some universal constant C.
46

---

Theorem G.3 (Theorem 3.8 in Main Paper, HSCSC Games with AltGDA), Suppose there are two two-layer neural networks, Fo. Go as defined in Definition 2.3 which satisfy Assumption 2.4 and Thh ((((a S (((aa) I ( respectively for all 0 < < 1, and some constants Tı, P2- Suppose the network parameters Og and dn are randomly initialized as Assumption 3.6 with (o) , ,02 (F) (F)) and (o) (G)
,022), ( respectively, which satisfy
and do d
02
S
(121)
( d
d(a)
and suppose that the hidden layer widths d and ( for the two networks and G satisfy
n2 & d s
n (G)
d = = P0 d(
M
(122)
where the datasets (Dp, DG) for both the players are assumed to be of size n. Then Alternating procedure with appropriate fixed learning rates to. ne (see Lemma F.7) for an (jo- Pg3-HSCSC and l cmmoohh min-max objective LD Fo, Go) as defined in Equation I satisfying Assumption 2. converges to the saddle point (0" (0)) exponentially fast with probability at least (p1 + P2 + P3 + P4 + ps) (p) + 22 + P's + + +P') (Here, the failure probabilities Pj 's and p/ are defined for networks Fa and Go, respectively, as per Lemmas G.I-G.2).
Proof. If we randomly initialize the neural network at 8g =(W((²) )o, (W( )o) per the stated initialization scheme in Assumption 3.6 with Equation (121), we have by Lemma G.2 that w.p.
p1 Ps:
Fe (DF)ll & ōzk1 k (X)
(123)
where Pt. Ps are as defined in Lemma G.2. Analogous reasoning gives similar bound for the output of initialization condition for the neural network Gs with data Da-
Since our min-max objective LD Fo, G&) is separable as defined in Equation 1, can start by rewriting the bilinear component 12 (Fa, Ga) (F)( A(Ga(Da)) Firstly, we can compute the gradients for the min-max objective as follows given data D = (Dv, Da):
VOLD(Fo, Go)
(124)
= (V PF (VoP((()) (Da)
(125)
V VoLD(Fo, Go) (G) (Fo, (V,G, ( AFr(Dr)
(126)
=-(VoGG(DG)) (VV (V==
(127)
By Assumption 2. (iv on the gradient norm of strongly- functions, triangle inequality, and submultiplicativity of operator norm, can say that the gradient norms of our separable min-max objective can be upper bounded as follows:
VIooD G&) < (( (A (F, 1 (()) + A1())
+I((o.F((rr)) TII
(128)
(F (V (P, ( diam() A(()))
Since L(0, is htwphhiiee-ssrrneloooooeextetooe 2-sided Pt-condition with (u4 - (VoFo), ne o2 min! (V)Gs)) Pł-moduli w.p. 2 Pt p2 (where pI, P2 as defined in Lemma G. Thus we can utilise path-length bound as derived in Lemma 3.2 which leaves with controlling the potential Po for ensuring convergence the saddle point. Given the loss gradients above (Equation (128)) and using the sufficient condition for ensuring
by Fact 2.6 it also satisfies the
iterates do not leave the ball B( (((o, Φo). R) (where R = max( (F) (c)
as defined in Section 3) thus min(Pr.fc)
47

---

ensuring non-singular Jacobian inside the ball for both the neural networks (Lemmma E.7), we require the following:
(D)) (F% (DF)ll + A diam())(F)) + Al 1/
+ +I((VoFo (Dr)) "Ill ||ll (Do)
+I(VVGoo (D6)) (DV)) (4 | (D&)ll + 22 diam() + 1/
13
R
+l(VoGoo (PG)) I| (Dr)
In order to ensure the above, we will demand the following:
1. T1 < 32
2. T: <
8²
32
3. T3
4.
T4
R²
32
We will show arguments for the case the 'min' player (neural network F5) here. Exactly the same arguments provide the analogous result for the 'max' player (neural network Go).
For ensuring (1.)-(4), we will use the fact that max ( (DF)) S (F) Fmax ( (Dc)) S UJe
(G) (G) Lemma G.1 for upper bounds (F) and Vac and smoothness constants for two-layer neural
networks along with the upper bounds on neural network outputs for and G as derived above in Lemma G.2.
Thus, a sufficient condition for ensuring 1.) would be use R
and see that w.p. 2 - P1 20p
P2 P3 Ps the following holds (assuming |cal is sufficiently large s.t. |co l + 52) 52)
becomes the dominating term in Jac (F)
(F)
a (kolV/ (1 62)(((())
hgh max (X) + 1 diam())()) + A(
S 32
Piu
2,3
(LHS)
(LHS)= < (a (F( (1 (1) ( (X
(By Lemma G.1)
(129)
2( (X)) (1mmx + Vmax Xmax )2
(lcol 2 + m2 ma (1'max + Vmnax Xmaax) ) (A(F) 8yh2 K2o (X))2
(o (2) (1 (,)3(ct((t))3) o (X++)
(130)
(1col + 52)m) (amax (X)) ( + Vi Xmaxx ) (A(F) dzki k2d (X))²
d
(af 2))2222 ( (tl)) )o (Xt+)
(131)
.4 2E(C,, (ct)22)
((A(()))
max (X)
(132)
0 minn (X
48

---

where 61 - max(ki, Co = f61, d2 83, 81), and
E(Ca, L, v. (c))20)) (1co12 I + 62)) (pmax + Vmax Xmax) (0zk)
(0) ( ) (1 ((1)(( (11)2)
Here, as per our Assumption 2.4 on the data and arguing along the lines of Section 2.1 in Oymak and Soltanolkotabi [86], when we use the fact that m
Fi min (X*1)
= (dg
1
and n = ) where / 2 200 we get that:
(n..nn.nne (4( =
n nn. 3.
n ng
d -ー = á
(133)
)3.
In the second equality above, used the observation from Appendix D that A1 (()) where is the strong-convexity modulus. Thus, the amount of overparamettriiztion we need for network F9 is follows:
(F) ( da
(134)
Analogous reasoning for ensuring (3.) with R 2
Mis
gives us w.p. 1 - p/ p/2 P/z
p44
Pls:
23
dit > E(Lc, C,t, v, 14 (( [mxx (X)
(135)
min (X*t)
Using arguments from Oymak and Soltanolkotabi [86] as done above for the case of 1.), we get similar cubic overparameterization bound for the 'max' player, Go. as well:
d (1())))))
(136)
We get the following w.p. 2 1 - (v' + pb)) - (p1 + P2 + Ps + P1) by similar reasoning above for (F)
ensuring 2.) holds along with using R
23r
(P)
lcoly (1 + + max (A) (8ghg K max (X)) x
1
Miae
32
2
(LHS)
(LHS) 2 (0) ( (1 81) (1)(c//t)) ( on (X
(By Lemma G.1)
(137)
2(O (x))² + Vmax Xinax) )2
(1) 2 (lcol (1 + 62)n) (amax (x)) + )4 0 (
(8g4g (X))²
() 2r (1 -,))((4/((t)) ti (X*1)
(138)
d Z E(A, 1h, (4)220
no max (X)
(139)
min (X*t)
Again, using arguments from Oymak and Soltanolkotabi [86] above, we get a similar cubic overpa- rameterization bound for the 'min' player, Fo, as above:
d d( 2(n²)
F)
(140)
Applying reasoning analogous to that for ensuring (2.) to the case of ensuring (4.) holds, by using
R 2 ((())
we get w.p. 2 1 (pr + ps) - (p) + p/2 + p's + pk)):
20G
( Z E(A,Lc. C2, t', v. (2)22)
Rio max (X)
(141)
min (X+t)
For a matrix W E mxn and Zz1, the Khatri- Rao product is denoted as #** E Bm''x with its j-th column defined vector(wy @ @ w;) E gm where @ denotes Kronecker product.
In practice typically has (d) ())) for 2 2.
49

---

Finally, was done for the case of ensuring 1.), 3.) and 4.) above, we once again arguments from Oymak and Soltanolkotabi [86] for spectral properties of the training data DD and get similar cubic overparameterizztion bound for the 'max' player, Go. as well:
do 12(22)
(142)
Thus, w.p. 2 -1 pp) (pI + P2 ps + Pa), we stay within a ball around the random initializations (((bu, (u). R.) thereby ensuring min-max objective satisfies 2-sided Pł-condition. By Lemma 3.2, given that we have chosen appropriate fixed learning rates as per Lemma E.7, we are now guaranteed to reach the saddle point.
Remark G.4. The proof above requires activation function to not be an odd function for ensuring cD + O.
Remark G.5 (Effects of assumption about max (X) on amount of overparamettrriaaion)) As noted in the footnote pertaining to mmax (X) for the data matrix X in Assumption 2.5, if all we know about the data matrix is that it's row-normalized and that it's not random matrix (e.g. random Gaussian matrix), then we can conclude that max ((vn) Using this bound on the maximum singular value of the data matrix instead, we can conclude from Equations (132), (135), (139), and (141) that
df [((=))
(143)
d i((n²)
(144)
Since we have n = (d (t 2 2) in practice for the MIN player Fe (analogously, n = ( for the MAX player G2), we can conclude that the amount of overparameterization needed for both the players is more than the cubic overparameterization when the data matrix is, for example, an i.i.d. random Gaussian matrix:
d 50(n(+1/1)
(145)
( (G) 00(n+11/4 40
(146)
50

---

H
Clarifications
H.1 Smoothness on variables or Map
In the main paper, state the following assumption regarding the objective function:
Assumption H.1 (Smoothness, Hidden Strong Convexity, and Gradient Control).
ii) Smoothness: Each sample-wise loss E(y, h Map (x)) is differentiable and L-smooth with respect to h.
(ii) Coupling Structure: Each bilinear coupling matrix A(r,, Ty. Mo) known, fixed, and has bounded
operator norm.
(iii) Hidden Strong Convexity: Each sample wise loss E(y, h Map (z)) is strongly convex with respect
to the neural network output h.
(iv)
Gradient Growth Condition: There exist constants A1; A2, Ag such that for all RRd and
E V, latent gradient each loss satisfies:
[VV & Ai|| + A2 d)am()) + As.
To compute the smoothness of the composition E(y, Map.. (x:) with respect to w, we invoke the following classical result"!. !I,
Lemma H.3 (Composition Smoothness, adapted from Proposition 2(c) in [131]). Let :R R be a closed, convex function that is ---locally-Lipschee To E Rd and R > 0 and let Ik + Rd be an Lg -mooohh function. Then, the composition f o is L Lg Lgg in the Euclidean ball B(xo: R).
a Euclidean ball B(oo, R) for some fixed
H.2 Refined Upper Bound Expression for Lyapunov Potential Po
For clarity and presentation purposes, the main paper presents simplified yet qualitatively uppae bound on the initial potential Po. In appendix, we provide the precise formulation that captures the correct dependence constants and exponents. For completeness, restate both results below:
The key distinction in the refined expression lies in the appearance of additional quadratic terms. As we show in the accompanying proof, these higher-order contributions can be effectively controlled through suitable initialization and appropriately chosen step sizes. Thus, the improved bound yields tighter theoretical insight without compromising practical applicability.
This adaptation is necessary, as a function cannot simultaneously be globally Lipschitz (bounded gradients) and strongly convex (increasing gradient norm) in the unconstrained setting. However, under sufficient overparameterization and appropriate random initialization, we show that the AltGDA iterates remain within bounded region where these properties hold locally. Thus, our assumption local Lipschitzness latent loss, the induced smoothness and the hidden strong convexity within Euclidean ball is both theoretically consistent and empirically valid.
Remark H.2.
51

---

Main Paper Version:
Lemma 3.3 (Upper Bound on Initial Potential Po). Suppose the min- max objective C(),0) is Le-Lipschitz and satisfies a two-sided PL con- dition with constants (uo:He) Then the initial Lyapunov potential Po S Le ( + C2 VVV where C1, C2 @ (Lc/P0)-
Appendix Version (Refined):
Lemma E.4 (Upper Bound on Initial Potential Po: Lemma 3.3 in Main Text), Let F& and G be neural network mappings such that they are 3p and fG smooth as defined in Definition 2.3. Now let (fa, Φu) be such that Jacobian singular values for both the networks are strictly positive and bounded from above and
below, ( S (V. I Vluc and ( S o G S v/c)) Suppose the min-max objective L(0,0) 6) is (Ho, -HSSSC Then the initial Lyapunov potential Po can be bounded from above as:
Po S (1( F2 C(Fo: Goo))
Jac
(F)
VoL((0, Φ0)1
no (u
1I
3F
Vooo 2o)l
(36)
2 (1)))))
+ +(1+ (1+ ||||[ll C(Fo, G
(G)
VV do)1
Ma(
(G))
+ +1 + A) (1[Vo. L(Fo. Goo)) 11 BG
Vo Coo( 20)l
2p (1
(
H.3 Random Initialization: How restrictive are our results?
We note the following for both the input games and neural games regarding random initializations:
1. Neural Games: Our main result (Theorem 3.8) assumes commonly used initialization scheme (e.g., He or LeCun), with the only additional requirement being that the variances satisfy Equation (9) in the main text. Of course, bridging the gap between practice and theory, it remains an interesting open question whether the current polynomial overparameterization requirement can be reduced to linear. However, we note that prior to our work there were no existing theoretical results connecting initialization schemes with convergence guarantees in neural min-max games.
2. Input Games:
In this setting, our results are even less restrictive regarding initialization. Specifically, we show that if the neural networks are randomly initialized from a standard Gaussian distribution, then AltGDA can compute the min-max optimal inputs. As dis- cussed above, this an average-case result, in the spirit of smoothed analysis. While it is theoretically expected that there exist neural architectures encoding hard min-max landscapes- potentially close to PPAD-hard instances practice, our result suggests that a randomly initialized neural min max game is tractable under AltGA.
52

---

I Discussion & Future Work
This work initiates principled framework for understanding optimization in hidden convex-coneave concave min-max games, a setting central to the theory and practice of modern machine learning. By bridging overparameterization with spectral geometry and alternating dynamics, we show how convergence and equilibrium stability can emerge from architectural design and initialization. Beyond offering first non-asymptotic guarantees for such hidden structures, our analysis reveals the potential of min-max learning as structured alternative to unconstrained overfitting. We hope these insights inspire a broader rethinking of how optimization, architecture, and strategic interaction coalesce in scalable intelligent systems.
In this last section, we reflect on our overparameterization bounds in comparison to known results from single-agent minimization, and outline promising directions for future research.
While our analysis shares surface-level similarities with techniques from classical minimization prob- lems, there are crucial structural differences. In the single-agent case, convergence is often guaranteed by showing that the Neural Tangent Kernel (NTK) remains well-conditioned near initialization, and that the loss is already small-a zero-order property.
By contrast, computing a Nash equilibrium in min-mat setting is inherently more subtle: the solution concept first & second-order. Rather than merely minimizing loss, we seek to simultancously drive the gradients of both players to zero while respecting their opposing saddle-point nature of equilibrium. Consequently, our notion being "close to optimality" requires the initialization yield not only small gradient norms but also a geometric alignment between the descent and ascent directions. This structural gap underpins the difference in overparameterization requirements between the single-agent and multi-agent cases.
catptrrnnn the
These insights naturally give rise to several open questions from deep learning and game theory point of view:
I.1 Deep Learning Perspective:
Sharper Overparameterization Bounds:
-Can tighten the width-depth trade-offs for hidden min-max games, especially in non- bilinear or partially observable regimes?
Our results suggest that overparameterrizatio smooths the optimization landscape in simple bilinear games, but the precise scaling with respect to hidden-layer width and depth in nonlin- ear architectures remains unclear. A possible direction is to characterize phase transitions in convergence when width exceeds a critical threshold that depends on the spectral complexity or curvature of the game operator.
Beyond Width and Smoothness:
How does the depth of the architecture influence convergence in hidden games? Can we extend current results to networks with non-smooth activations such as ReLU, using tools beyond seadient-Lipschiin analysis?
Smoothness assumptions simplify the analysis but obscure the behavior of realistic neural dynamics. We could instead exploit techniques from non-smooth dynamical systems and proximal envelope theory to handle non-smooth losses.
Another open question is whether depth induces implicit averaging effects similar to stochastic smoothing, thereby stabilizing the dynamics in min-max training.
Structural Guarantees in Multi-Agent PE Games:
What the necessary structural properties of multi-agent PL-type games that ensure con- vergence to a unique Nash equilibrium? The challenge lies in extending single-agent Pt. conditions multi-agent systems where gradients interact. Are there generalized Pt. inequali- ties that capture cross-agent monotonicity?
Investigating block-wise coupled PE. structures could reveal when independent gradient updates mimic joint gradient descent-ascent in strongly monotone regimes.
53

---

Computational Complexity:
What is the inherent hardness of solving hidden convex games with overparameter-
ized models? Can we characterize tractable subclasses?
The inversion injectivity verification of neural networks is known to be NP- or coNP. complete even for ReLU architectures (see, e.g.. the 25LT paper "Complexity of Injec- rivity and Verification of ReLU Neural Networks" "). How do such barriers propagate to the equilibrium computation problem when game payoffs are defined implicitly through network mappings?
The overparameterized setting often introduces implicit convexification, Can we formalize when this leads to provable polynomial- convergence when training remains PPAD or NP-hard?
From Neural Networks to Transformers:
What explains the observed differences in scaling laws between overparameterized feedfor- ward networks and attention-based architectures in game-theoretic learning? Could these insights inform AI alignment and debate frameworks?
Transformers introduce dynamic reweighting of information through attention, which may alter the effective conditioning of the game Jacobian.
Understanding how self-attention layers modify optimization stability and expressivity could illuminate why Transformers exhibit faster equilibration or better robustness to adversarial perturbations.
Beyond Full Gradient Feedback:
Much of the current analysis, including ours, assumes full gradient information. It remains an open and critical question whether similar benefits of overparameterization persist under bandit or partial-information settings.
A natural direction is to extend existing results to stochastic feedback or condit-gradient estimators using variance-controlle or mirror-descent methods.
Another fundamental question: does overparameterizztion implicitly reduce the variance of policy-gradient estimators by averaging across redundant feature paths?
1.2 Game Theory Perspective:
CCE with Neural Parametrizations (Normal-Form)
Representutional question: For class of neural correlating devices go(z) that map public randomness z to joint actions, characterize when the induced set of implementable distributions is dense in the CCE polytope. What overparameterization (width/depth) suffices for e-dense coverage uniformly across n-player games with bounded payoffs?
Optimization Calibration: Standard no-regret dynamics imply convergence to CCE in the tabular case. With function approximation (shared neural critics/policies), give conditions (e.g., uniform stability, gradient-calibration bounds) under which the averaged joint play converges to an e-CCE at rates that improve with network width (via better optimization landscapes) without blowing up statistical complexity.
Implicit bias: In the overparameterized (NTK) regime, training to minimize regret surrogates biases the joint distribution toward low-complexity mixtures. Can we quantify the implicit regularization toward "simple" CCEs (few extreme points in support) as a function width, depth, and training dynamies?
CCE in Extensive-Fore Games (EFG): EFCE, CEFCE, NFCCE via Nets.
Sequential structure: Compare neural parameterizations for NFCCE (normal-form coarse CCE), (ii) EFCE (extensive-form CE), and (iii) CEFCE (coarse EFCE), Give width/depth conditions under which sequence-form constraints (flow and realization-plan consistency) can be enforced by differentiable layers with projection or Lagrangian penalties.
Counterfactual losses: Can counterfactual regret minimization with neural policies/critics be shown to converge to EFCE/CEFCE when critics are overparameterized but trained with regu- larized Bellman residuals? Identify structural conditions (perfect recall, bounded branching, Lipschitz counterfactual values) that guarantee Õ(1/VT) exploitability while using batched, partial counterfactual feedback.
54

---

Abstraction without tears: Overparameterizee policies can represent rich information
strategies directly. Develop "learned abstraction" bounds: when does deep policy with atten- tion over histories match the exploitability of hand-crafted abstractions, and what width/depth yields e-FFCE support recovery?
Markoy (Stochastic) Games: Stationary CCE and Overparameterized Crities.
Stationary CCE: Define a stationary CCE as a joint policy with a correlating signal that is time-consistent across states. Give conditions under which joint no-regret learning with overparameterized Q-rritics converges (in Cesàro average) to an E-stationary CCE, with rates that depend on mixing/conceetrabiiiiy constants and the critic class capacity.
Depth helps bootstrapping: Hypothesis: deeper critics reduce the Bellman residual floor achievable by gradient methods, improving optimization error; width controls realizability.
Provide a decomposition of the CCE gap into Approximation (FQ) + Optimization
Statistical data), and bound each term function of network depth/width and explo- ration coverage.
Temporal correlation: Analyze how correlating devices that are cate-dependent (learned correlation) interact with Markovian dynamics. When does (few bits per step) suffice for e-CCE in ergodic MGs?
correlation
Overparameterization vs. Hallman-Eluude (BE) / Bellman Rank Complexity.
Function-claas lens: Let Fo be the Q-function class realized by network in the linearized (NTK) regime. Its eluder dimension equals the feature dimension for linear classes; for deep nets, the effective eluder dimension depends width, depth, and implicit regularization. Con- jecture: with proper norm control (weight decay/early stopping), the effective BE dimension scales like the stable rank of the induced features, not the raw parameter count.
Sample complexity for S-CCE: In two-player zero-sum Markov games with realizable Q" E Fq. the sample complexity to reach s-CCE under fitted Q-type updates should scale as
Ô BE (ind + 1og(1/6)).
(1-
for small integer p depending on the algorithm (e.g., P E {2,3)), assuming standard concentrabillyy/mixing Overparameterizztion per se does not hurt if the BE dimension is controlled by implicit/explicit regularization.
Width-complexitt trade: Identify regimes where increasing width improves optimization (faster approach to 0*) while keeping BE-dimension nearly constant via margin- or path-norm constraints, yielding strictly better sample trade-offs.
Transformers vs. MLPs: Attention layers can implement dynamic state-action feature selection, potentially lowering the BE dimension for tasks with sparse predictive structure (long-range range but low "intrinsic" rank). Formalize when attention reduces BE-dim relative to equally wide MLPs, explaining empirical scaling differences in Markov game benchmarks.
Bandit/Partial Information Extensions:
Bandit CCE: For fortmalafomm//Mroooo games with bandit feedback, derive e-CCE rates when both policies and correlating devices are neural. Key ingredient:
gradient surrogates (e.g., doubly-robust control-variates) to keep estimation error compatible with bounded BE dimension.
Information complexity of correlation: Quantify the information budget (bits of correlation, episodes of exploration) required to learn e-CCE as function of BE dimension and mixing: relate to communication complexity of implementing the equilibrium.
Conclusion. Our study sheds new light on the geometry of overparameterized min-max optimization by establishing the first precise convergence guarantees in hidden bilinear games. We demonstrate how overparameterizzatio not only facilitates convergence but also implicitly regularizes the optimization landscape, ensuring robustness through well-conditioned spectral structure. Crucially, we bridge the gap between neural initialization and equilibrium computation, revealing that convergence in adversarial training is governed by deeper geometric principles. These insights open new avenues for understanding and designing scalable multi-agent learning systems, and we believe they mark significant step toward principled foundations for modern generative and strategic AI.
55


Reviews:
[{"review_id": "KK9fwLNB9D", "reviewer": "Reviewer_Pjht", "summary": "This paper studies the convergence of Alternating Gradient Descent-Ascent algorithm to NEs in min-max games, while both players' strategies are shallow and wide neural networks with randomly initialized network weights.", "questions": "1. In line 190, how to interpret $(\\mathcal{D} _F, \\mathcal{D} _G) = \\{(x _i,y _i)\\} _{i=1}^n$? My understanding is $\\mathcal{D} _F = \\{x _i\\} _{i=1}^n$ and $\\mathcal{D} _G = \\{y _i\\} _{i=1}^n$. Is my understanding correct?\n(Side note: If my understanding is correct, I suggest the authors simplify the notations used in many expressions, e.g., $i\\in [|\\mathcal{D} _F|]\\Rightarrow i\\in[n]$, $I _1^{\\mathcal{D} _F} \\Rightarrow I _1$ since $\\mathcal{D} _F$ is a fixed constant in this paper. The current notations are bit complex and redundant.)\n2. In line 192, what is $\\mathcal{S} _F, \\mathcal{S} _G$? In line 196, it suggests that $\\mathcal{S} _F, \\mathcal{S} _G$ are the (finite) sets of pure strategy of some underlying game, but it should then have that the image of $F _\\theta$ is $\\Delta(\\mathcal{S} _F)$. On other hand, if $\\mathcal{S} _F, \\mathcal{S} _G$ are the continuous strategy sets (also corresponding to a subset of Euclidean space of some dimension), then how to interpret $\\mathbb{R}^{|\\mathcal{S} _F|\\times|\\mathcal{S} _G|}$ in line 196?\n3. In line 194, what is the domain of the loss function $l(y,h)$?\n4. Assumption 2.1 (i) in line 203 makes me confused. In the expression $l(y, Map _w(x))$, it seems that $Map _w$ is a neural network with weight $w=(W _1, W _2)$ in later analysis in line 219-220. Why does it make sense to directly assume the behavior of function $l$ over network weight $w$? I think a better choice is to assume the upper bound of $W _1, W _2$ and the smoothness of $l(y,h)$ on $h$ separately. The smoothness of $l$ on $w$ might then follows directly.\n5. In Assumption 2.1 (iv) in line 210. It seems that $\\mathcal{Y}$ (consequently $\\mathrm{diam}(\\mathcal{Y})$) is fixed, so $A _2 \\mathrm{diam}(\\mathcal{Y}) + A _3$ can be treated together as a constant. Is my understanding correct?\n6. In line 212, it is unclear that $\\mathcal{L} _{\\mathcal{D}}$ is convex-concave at which sense. It seems that $\\mathcal{L} _{\\mathcal{D}}(F _\\theta, G _\\phi)$ is convex in $F _\\theta$ by assumption (iii), but it is highly unlikely that $\\mathcal{L} _{\\mathcal{D}}(F _\\theta, G _\\phi)$ is convex on $\\theta$, since $\\theta$ is network weights and there is no condition guaranteeing the convexity of loss function $l$ over network weight $\\theta$.\n7. Similar to question 4, in line 223. Why does it make sense to assume the smoothness condition of $h(x)$ over network parameters $W _1^{(h)}, W _2^{(h)}$?\n8. What is the Hermite norm defined in line 225? \n9. What is the meaning of $(W _2^{(h)}) _k$ in line 227?\n10. In Fact 2.6 in line 243, why does loss function $\\mathcal{L} _{\\mathcal{D}}$ satisfy PL condition? This statement is unclear to me, with same reason described as question 6.\n11. In line 257, note that $\\min _\\theta \\mathcal{L}(\\theta, \\phi)$ depends soly on $\\phi$, so the expression $\\theta \\mapsto \\min _\\theta \\mathcal{L}(\\theta, \\phi)$ does not make sense.\n12. In line 291-300, Lemma 3.1 makes sense only when $c < 1$, yet the authors give no further clarifications on the range of $c$.\n13. In line 293, what is the expression of $P _0$?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n\nThe problem is well-motivated and interesting. The technical results are solid. (I have not checked the correctness of proofs in appendix, since I'm not familiar with these theories.)\n\n**Weaknesses**:\n\nI do not find any weaknesses regarding the theoretical results of this paper.\nActually, I feel confused about many notations and assumptions made in this paper, consequently hard to evaluate the value of this paper. These concerns are listed at **Questions** section below. I would consider to increase my evaluation if these concerns could be addressed.", "was_revised": true, "final_justification": "This paper provides theoretical understanding of the hidden convex-concave games of neural networks, showing that with over-parameterization, proper initialization, and a gradient-ascent-descent algorithm, the NE can be approximated within polynomial complexity.\nThe results provide a theoretical foundation for algorithms that aim at finding an NE of two networks with opposite loss functions. The techniques are solid as far as I can tell. Based on the above points, I recommend an accept.", "rebuttal": "First of all, we sincerely thank the reviewer for the helpful comments and questions, which we believe will contribute to a more favorable and clearer evaluation of our work.\n\n### Questions:\n\n> **Q1.** In line 190, how should we interpret $(D_F, D_G) = ((x_i, y_i))_{i=1}^n$? My understanding is that D_F = (x_i) for i = 1 to n and D_G = (y_i) for i = 1 to n. Is this correct?  \n> *Side note:* If so, I suggest simplifying several notations, e.g., i in [size of D_F] becomes simply i in [n], and I_1 superscript D_F becomes I_1, since D_F is fixed throughout the paper. The current notation feels a bit complex and redundant.\n\n\nThank you for pointing this out—this is an important clarification. Unlike in classical game dynamics (e.g., min-max games like $x^T A y$ where x and y are strategies), here $D_F$ and $D_G$ represent datasets. \nThe notation $(D_F, D_G) = ((x_i, y_i)$ for $i = 1$ to $n$) follows machine learning conventions, where each $(x_i, y_i)$ is a data-label pair. Specifically, we partition the dataset into two parts: \n$D_F = ((x_j, y_j)$ for $j=1$ to $n_1)$ and $D_G = ((x_k, y_k)$ for $k=1$ to $n_2)$ with $n_1 + n_2 = n$. Each player receives their own set of training pairs.\n\n\n> **Q2.** About strategy-space notation (lines 192 & 196)\n\nThank you for pointing out this typo. Indeed, $S_F$ and $S_G$ refer to general strategy sets, which are not necessarily finite—they may be continuous subsets of Euclidean space. Therefore, the expression in Line 196 should be interpreted more generally as a function defined over $S_F \\times S_G$, or $\\mathbb{R}^{\\text{dim}(S_F) \\times \\text{dim}(S_G)}$. We acknowledge this mismatch and revise the notation accordingly to avoid confusion.\n\n> **Q3.** The domain of the loss function $l(y,h)$?\n\nAccording to our adopted notation, the domain of the loss function $l(\\cdot, \\cdot)$ when using a neural network $h$ for predictions is $\\mathbb{R} \\times \\mathbb{R}^{d_2}$.\n\n> **Q4 & Q7.** Why assume smoothness of $l(y, \\text{Map}_w(x))$ and $h(x)$ with respect to weights $w = (W_1, W_2)$ directly?\n\nWe agree that one could instead assume smoothness in the network output $h = \\text{Map}_w(x)$ and separately constrain $W_1, W_2$. However, we adopt the unconstrained formulation to align with the standard setup in overparameterized optimization and to keep the analysis consistent with AltGDA, which is designed for unconstrained min-max problems. Adapting techniques from constrained settings (e.g., [1]) using proximal PL is a promising future direction.\n\nWe emphasize that $h_\\theta(x)$ is a smooth operator (e.g., a neural network). Consistent with the overparameterization literature (e.g., [1], [2]), we assume differentiable activation functions. Smoothness helps define a trust region around initialization where the Jacobian of $h_\\theta$ remains non-singular. This enables us to define a meaningful radius $R = \\mu_{\\text{Jac}} / (2 \\beta_h)$ where optimization dynamics behave well. ReLU networks are non-smooth only on a measure-zero set. Extending to non-smooth activations using tools like Clarke subgradients (e.g., [3]) is a valuable direction.\n\n> **Q5, Q8, Q9, Q11–Q13.**\n\n**Q5.** Yes, your understanding is correct. We stated it this way for completeness.\n\n**Q8.** Using Gaussian random initialization, the Hermite norm helps bound the singular values of $h$'s Jacobian. For $\\phi: \\mathbb{R} \\to \\mathbb{R}$, the Hermite norm is \n$ ||\\phi|| = \\sqrt{ \\sum_{i=0}^\\infty c_i^2 }$, where \n$c_i = \\langle \\phi, q_i \\rangle = \\frac{1}{\\sqrt{2\\pi}} \\int \\phi(x) q_i(x) \\exp(-x^2/2) dx$, and $q_i$ is the $i$-th Hermite polynomial.\n\n**Q9.** It denotes $W_2$ at iteration $k$ of AltGDA. That is, if $\\theta$ is optimized, $\\theta_k$ denotes the parameters at step $k$.\n\n**Q11.** We revised to: *$\\min_\\theta L(\\theta, \\phi)$ has a non-empty solution set and a finite optimal value (and analogously for fixed $\\theta$).*\n\n**Q12.** We elaborate the expression and valid range for $c \\in (0,1)$ in Remark D.5. We will move this to the main text for clarity.\n\n**Q13.** We use the same Lyapunov potential $P_t$ as Yang et al. (2020), but now state it clearly:\n\n$P_t := \\left( \\max_{\\phi} \\mathcal{L}(\\theta_t, \\phi) - \\mathcal{L}(\\theta^\\star, \\phi^\\star) \\right) + \\lambda \\left( \\max_{\\phi} \\mathcal{L}(\\theta, \\phi_t) - \\mathcal{L}(\\theta_t, \\phi_t) \\right)$\n\nwith $\\lambda = 1/10$, $t = 0$. The choice of $\\lambda$ does not affect our conclusion that $\\tilde{\\Omega}(n^3)$ overparameterization suffices.\n\n\n\n> **Q6 & Q10.** Hidden Neural Games and PL-condition\n\nWe agree that $L_D$ is **not** convex–concave in weights $\\theta$ and $\\phi$. Rather, it is strongly convex–concave in the outputs of $F_\\theta$ and $G_\\phi$, i.e., **hidden convex–concave**. This is central to our framework: the objective is nonconvex–nonconcave in parameter space but becomes tractable when viewed compositionally. Our analysis exploits this hidden structure.\n\nWe will clarify Fact 2.6:  \nBy Proposition 2 of Fatkhullin et al. [4], if $f(\\theta) = F(H(\\theta))$ and $F$ is strongly convex while $H$ is a smooth map (e.g., a neural net), then $f$ satisfies the Polyak–Łojasiewicz condition. Thus, hidden strong convexity implies PL, even for nonconvex objectives. Our contribution is to make this connection explicit in the min-max setting.\n\nMoreover, Proposition 4.1 of D’Orazio et al. [5] gives a precise PL constant depending on the smallest singular value of $H$'s Jacobian. If $H$ is close to an invertible, well-conditioned map, the PL modulus is preserved.\n\nHence, even though $L_D$ is nonconvex in parameters, it satisfies the PL condition due to its compositional nature—an insight at the heart of our analysis.\n\n\n---\n\n**References:**\n\n[1] Kalogiannis et al., *Solving Zero-Sum Convex Markov Games*, ICML 2025\n\n[2] Song et al., *Subquadratic Overparameterization for Shallow NNs*, NeurIPS 2021\n \n[3] Zou & Gu, *Improved Analysis of Overparameterized DNNs*, NeurIPS 2019\n\n[4] Fatkhullin et al., *Stochastic Optimization under Hidden Convexity*, arXiv:2401.00108\n\n[5] D’Orazio et al., *Hidden Monotone VIs via Surrogate Losses*, ICLR 2025\n\n---\n\nWe thank you for your thoughtful feedback. We hope our clarifications improve the accessibility of the paper.\n\nHaving clarified our notation, here we repeat our central message: when two neural networks interact via simple game dynamics, their weights can be trained to find the Nash equilibrium. Our analysis identifies both the scale and strategy of initialization required. To our knowledge, this is the first work to connect overparameterization to min-max optimization in hidden or non-convex domains.\n\nWe also chose our abstraction and notation to move beyond standard $\\ell_2$-based objectives, aiming to support generalization to broader loss landscapes. We hope this clarifies our intentions and supports a higher evaluation."}, {"review_id": "6PxrMS6MgU", "reviewer": "Reviewer_tXT3", "summary": "The authors consider models for zero-sum games between neural networks, characterizing scenarios such as adversarial training, alignment and robust optimization, with an equilibrium formulation of the stable desirable system behavior. Generally, when the game objective are non-convex non-concave  there is no guarantee that simple gradient methods would converge to the equilibrium, however in practice there have been many cases where such a convergence does occur. This led the researchers to speculate that there is some underlying structure in the system, leading them to build a theoretical framework for analyzing this, considering the system initialization, the dynamics and “hidden convexity”.", "questions": "You make several assumptions regarding the neural models and training regime. Could you summerize these is a short form, and discuss which of these are similar to the practical use-case and which of these actually different?", "limitations": "The work is theoretical in nature (based on previous empirical evidence).", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 4, "strengths_and_weaknesses": "The key result in the paper is a characterization of properties that lead to convergence to an equilibrium in a class of such games (with 2 layer neural networks). The characterization is based on path length bounds for alternating gradient descent/ascent. \n\nOverall, I find the topic of the paper very interesting. The overall structure of competing neural nets has received a huge amount of attention in the ML literature, leveraging foundations and inspirations from game theory. However, the theoretical foundations lagged behind the successful empirical results. In short, game theorists were surprised with the success of simple alternative methods, that they expected to simply orbit rather than converge. Overall I think the class of games tackled here require making non-trivial assumptions on the neural nets and training procedure that are still perhaps far from the actual networks used in practice. Hence, this results narrow that gap between theory and practice, but does not eliminate it. Still, a very interesting result overall. \n\nCouple of comments: \n\nCan you add a table of know results regarding convergence properties from the game theory (I know here you tackle 2 player zero sum games, but what is known about broader classes? Also perhaps discuss polynomial time computation of equilibria and why it could not be used here, and processes such as fictitious play). This would better place the paper in the context of background work. \n\nI think a better exposition of PL is warranted; you do address it, but I think this needs to be expanded.\n\nI think a table with examples (and citations) for games where empirical convergence is observed would make for a better presentation of the empirical inspiration for this work. Also, maybe you could have a discussion of cases where such convergence does not occur\n\nOverall, good paper - my suggestions are mostly around presentation.", "was_revised": true, "final_justification": "Good paper, I stand by my rating,", "rebuttal": "We sincerely thank you for your enthusiastic review and thoughtful presentation-related comments.\n\nWhile we already provide an extended discussion in the related work section, we agree that a more structured comparison would be helpful. In the final version, we plan to include a summary table covering works on 2-player min-max problems under various structural assumptions—concave, monotone, quasi-strongly monotone, weak Minty, hypomonotone, and cocoercive—under both full and bandit feedback. This will better position our contributions relative to the literature, especially in connection to AltGDA and the two-sided PŁ-condition.\n\nWe also plan to clarify our assumption regarding polynomial-time computation. Indeed, one might suggest solving the latent convex–concave game and then inverting the network to recover parameters approximating the optimal strategy. However, this poses two key challenges:\n\n1. **Inversion of neural networks is NP-complete in the worst case**, making it impractical to expect practitioners to solve the latent convex–concave game and then invert the network to recover the corresponding parameters. While overparameterization may theoretically improve tractability and mitigate the brittleness of the inversion step, our focus is to understand and justify the empirical success of training dynamics (such as AltGDA) in structured nonconvex–nonconcave settings—without requiring explicit solution of the latent game.\n\n2. **Games with exponentially large action spaces** make exact solution intractable. In these cases, neural networks (or other function approximators) offer a succinct and practical way to learn high-quality strategies.\n\nThis modeling perspective strengthens both the theoretical and practical relevance of our framework.\n\nAdditionally, in the appendix, we cite empirical studies showing the effectiveness of gradient methods on large neural networks—many of which fall under our model. In the final version, we also aim to include visualizations from our own experiments. For interested reviewers, similar experiments appear in prior works [1–6].\n\nFinally, we acknowledge the theoretical intractability of computing Nash equilibria and the PPAD-hardness even under smoothed complexity. Naturally, examples exist where GDA-based methods fail—several such failure modes in nonconvex–nonconcave min-max settings have been documented in [7–9]. On the other hand, the complexity of unconstrained min-max optimization remains an open question in complexity theory—specifically, whether it is computationally equivalent to solving NASH (PPAD), KKT (CLS), or lies somewhere in between these complexity classes. Clarifying this would yield a more universal understanding of the power and limitations of oracle-based methods like GDA.\n\n**References:**\n\n[1] Mladenovic et al., Generalized natural gradient flows in hidden convex-concave games and GANs, ICLR 2022\n\n[2] Vlatakis-Gkaragkounis et al., Solving min-max optimization with hidden structure via gradient descent ascent, NeurIPS 2021\n\n[3] Sakos, et al., Exploiting hidden structures in non-convex games for convergence to Nash equilibrium, NeurIPS 2023\n\n[4] Song et al., Neural-network-based synchronous iteration learning method for multi-player zero-sum games, Neurocomputing 2017\n\n[5] Lei et al., SGD Learns One-Layer Networks in WGANs, ICML 2020\n\n[6] Wu et al., Using CNN for solving two-player zero-sum games, Expert Systems with Applications 2022\n\n[7] Kalogiannis et al., Towards convergence to Nash equilibria in two-team zero-sum games, ICLR 2023\n\n[8] Jin et al., What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?, ICML 2020\n\n[9] Yang et al., Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems, NeurIPS 2020\n\nWe greatly appreciate your support for our paper and would be happy to address any further questions or clarifications you may have.\n\n### Questions:\n> You make several assumptions regarding the neural models and training regime. Could you summarize these in a short form, and discuss which of these are similar to the practical use-case and which of these actually different?\n\nIn the table below, we summarize the assumptions regarding the neural networks and training regime:\n\n\n|  | Our paper | In practice |\n| -------- | -------- | -------- |\n| Type of Neural Network | 1-hidden-layer, fully-connected | Typically deep networks, not necessarily fully-connected (e.g. Residual or convolutional layers) |\n| Training Algorithm | AltGDA | Not necessarily AltGDA / Mainly Double-loop |\n| Network Initialization | Gaussian (with variance constraints) | Similar (e.g. He, Xavier, or LeCun initializations) \n\nAmong these, the assumption on AltGDA is arguably the most benign. In non-convex/non-concave min-max optimization, stabilization is essential. In practice, double-loop methods (e.g., approximate best-response oracles) are often used for safety, while AltGDA serves as a more parallelizable and simpler single-loop alternative. Similarly, the Gaussian initialization is closely aligned with practical heuristics like He or Xavier. The main gap lies in the architecture: practical models are often very deep with fixed-width layers. Theoretical understanding of why such architectures succeed remains an super interesting open question. While recent work has begun to explore overparameterization in deep networks for minimization tasks, our paper focuses on a more analytically tractable setting—explicitly avoiding the NTK regime to provide a non-asymptotic analysis for 1-hidden-layer networks in a game-theoretic context. We view relaxing and extending these assumptions as a promising direction for future work."}, {"review_id": "MgqJgpj2Vv", "reviewer": "Reviewer_F1FN", "summary": "The paper considers hidden convex/concave games parametrized by 2-player neural networks. More precisely, the authors consider a data set $D = (D_x, D_y ) =  ( x_i , y_i )_{i=1}^n$ and  the following min-max game\n\n$sum_{i=1}^n = \\ell( G_\\theta(x_i,y_i ) , G_w(x_i,y_i )$\nwhere $G_z,G_w$ are the 2-layer NNs.\n\nThe authors consider the case where the function $\\ell(\\cdot,\\cdot)$ is convex/concave. In fact they consider a more special case where $\\ell(\\cdot,\\cdot)$ is strongly convex/strongly while admiting an additional bilinear term. The authors establish that *Alternating Gradient Descent/Ascent* converges to a min-max equilibrium $(w^\\star,z^\\star)$ in polynomial number of steps.\n\nOn the technical level the authors leverage a recent result of Yang et al. establishing convergence results for Alternating GDA in zero-sum game satisfying the *two-sided PL condition*. In a nutshell, the authors show that with a suitable initialization of the  weights the two-sided PL condition will be satisfied. Following techniques from the Neural Tangent literature, the authors then establish that the trajectory of Alt GDA remain sufficiently close to the initial weights. In this way they are able to establish the fact that two sided PL condition is always satisfied and derive a final convergence result.", "questions": "1. In line 194 you write $I_{1}^{D_F}(F_\\theta):= \\sum_{i \\in [|D_F|]} \\ell_{i} (y_i , F_\\theta(y_i)) = \\sum_{j \\in [|D_G|]} \\ell_{j} (y_j , F_\\theta(y_j))$. Do you mean $\\ell(x_i,y_i)$? is it a typo? Otherwise I do not understand why the loss term changes with the example.\n\n2. Also find a bit unintuitive the fact that the data set $D = (D_F,D_G)$ is separated between the two players. Could you provide some more details or an illustrative example on the coupling matrix $A(x_i,x_j,y_i,y_j)$?\n\n3. What if the function $I_2$ is convex/concave instead of bilinear?\n\n4. Do your results transfer in case of noisy gradients?\n\n5. Have you experimentally evaluated your claims in simple hidden convex/concave games e.g. Rock-Paper-Scissors parametrized by two DNNs?\n\n6. I think there is small typo in 304 ($P_0$ two times).", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\nI think that this a very interesting paper considering a very interesting and important setting. Identifying classes of non-convex/non-concave games that circumvent the intractability results of Daskalakis et al. but at the same time remain relevant to real-world setting is a very important research direction. The paper provides solid convergence results in the class of hidden convex/concave games which I believe is a very interesting first step towards the aforementioned direction. The authors have made an excellent job in providing specific example in Appendix B motivating the class of hidden convex/concave markov games.\n\nAt the technical level, the authors transfer the techniques coupled the techniques devellopped in the overparametrization literature with recent results concerning min-max optimization to establish their convergence results. The basic challenge consisted of establishing that along the trajectory of Alt GDA the two-sided PL conditions are satisfied. The paper seems to admit deep technical depth. That being said, I did not check the correctness of the proofs in the appendix.\n\n**Weaknesses**\n\nOne of weakness of the papers concerns the presentation and the verification of the theoretical claims. I want to remark that this is to an extend justified due to 9 page limit and the technical nature of the paper. However I really believe that more discussion would be helpful concerning the various set of assumptions presented along the paper. Another probably weak point concerns the fact that the authors consider a bilinear + strongly convex/concave setting limiting the applicability of the results. Finally no experimental evaluations are presented. I believe that the providing some experimental verification of the theoretical claims even in toy examples (e..g RPS played by two NNs) would add value to the paper.", "was_revised": true, "final_justification": "After the author-reviewer discussion i am very confident on the significance of the paper's results and thus i recommend acceptance.", "rebuttal": "We would like to sincerely thank the reviewer for their thoughtful and encouraging comments regarding our research direction, and for the time and care dedicated to reading even the appendix sections. Below we address the points raised.\n\n### On Experiments\n\nSince the focus of our work is on building the theoretical foundations of training dynamics in hidden convex–concave games, we chose not to burden the 9-page main paper with additional experimental sections. That said, we appreciate the reviewer's interest, and we have conducted new experiments to support our claims. Unfortunately, due to the recent note discouraging inclusion of new content in the rebuttal, we are unable to include them here. We will be excited to incorporate them in the final version, with illustrative ML- and game-friendly examples (e.g., neural networks playing RPS-style games).\n\nWe also note that related works in the hidden convex–concave literature and NNs in Zero-sum games (see, e.g., [1–6]) already contain visualizations of this kind, which we view as further support of the framework's relevance.\n\n### On Assumptions and Applicability\n\n\nExtending our answer to Reviewer `tXT3` (score: 5 - accept), we agree that a more detailed discussion of the assumptions will improve clarity. The table below contrasts our setup with what is typically observed in practice:\n\n|                          | **Our Paper**                                           | **In Practice**                                                                         |\n|--------------------------|---------------------------------------------------------|------------------------------------------------------------------------------------------|\n| **Type of Neural Network** | 1-hidden-layer, fully-connected, smooth activations     | Typically deep networks; not necessarily fully-connected (e.g., ResNets, CNNs)           |\n| **Training Algorithm**     | AltGDA                                                  | Mainly double-loop methods (e.g., approximate best-response oracles); not always AltGDA  |\n| **Initialization**         | Gaussian with variance constraints                      | Similar heuristics (e.g., He, Xavier, or LeCun initializations)                          |\n\nAmong these, the assumption on AltGDA is arguably the most benign. Stabilization is essential in nonconvex–nonconcave min-max settings. While double-loop methods are often used in practice, AltGDA provides a simpler, parallelizable single-loop alternative.\n\nSimilarly, Gaussian initialization aligns well with common initialization schemes. The main divergence lies in the network architecture: practical models are often very deep with fixed-width layers. Understanding their theoretical behavior remains an open and fascinating question. Recent works have begun to study overparameterization in deep networks for minimization tasks, but our focus here is on a more tractable regime—avoiding the NTK limit—to deliver a non-asymptotic analysis of 1-hidden-layer networks in game-theoretic settings. Relaxing these assumptions remains a rich direction for future work.\n\nGoing beyond smooth activations is also possible, though technically more demanding. Extending the analysis to non-smooth activations (e.g., using Clarke subdifferentials or related tools—see [8]) is indeed a compelling path forward.\n\n---\n\nOn the other hand, some properties in our setup are not assumptions but **structural features of the model**. Much of the existing overparameterization literature focuses on $\\ell_2$ regression. In contrast, we chose to target a broader family of problems, motivating structural conditions like smoothness, gradient growth, and Lipschitz continuity not as limiting assumptions but as general-enough properties that support a wide class of objectives.\n\nRegarding the **separable min-max setting**, we note that it is the dominant structure in most Euclidean game formulations. While one could generalize to a setting where the $I_1$ and $I_3$ components follow a non-quadratic drift, this would introduce significantly more complexity. We agree that this is a valuable and interesting theoretical direction, and we would be happy to include it among the open problems in the final version.\n\nLastly, we clarify that the **composition of a strongly convex function with a smooth well-conditioned map** (e.g., KŁ or PŁ structure) is not an assumption but rather a mathematical fact—what we call *hidden convexity*. This underlies many of the observed phenomena in both minimization and min-max settings.\n\n---\n\nWe will revise the main text to better motivate our structural choices and position them within the broader context of min-max optimization and overparameterization literature.\n\nAlthough our current setting focuses on bilinear + strongly convex–concave games, we view it as a meaningful and foundational step. Our broader aim is to help identify tractable nonconvex–nonconcave games that remain algorithmically relevant in practical machine learning, and we believe our framework contributes in this direction.\n\nOnce again, thank you for your engagement and generous feedback. We truly appreciate your support and look forward to further developing this line of research.\n\n### Additional questions about the manuscript\n\n> 1. In line 194 you write $I_{1}^{D_{F}}(F_{\\theta}) := \\sum_{i\\in[|D_{F}|]} \\ell_{i}\\bigl(y_{i},F_{\\theta}(y_{i})\\bigr) = \\sum_{j\\in[|D_{G}|]} \\ell_{j}\\bigl(y_{j},F_{\\theta}(y_{j})\\bigr)$. Do you mean $\\ell(x_{i},y_{i})$? Is it a typo? Otherwise I do not understand why the loss term changes with the example.\n\nIn Line 194 we wrote the min-max objective in more generality. However, for our analysis we specifically use losses $\\ell$ and $\\ell'$ for the MIN and MAX players, respectively. In practice as well (as highlighted with examples in Appendix B), we see this being the case. If one were to use different losses for every example (for both the players), one would have to instead work with the minimum PL-modulus of these losses in our analysis.\n\n> 2. I also find it a bit unintuitive that the data set $D=(D_{F},D_{G})$ is split between the two players. Could you provide more details or an illustrative example of the coupling matrix $A(x_{i},x_{j},y_{i},y_{j})$?\n \nRegarding the splitting of the data, we have stated our result assuming an equal split for ease of presentation. However, no step in our analysis is limited or constrained by the fact that the datasets have been split.\n\nFor an example of the coupling matrix, consider the example B.7 in Appendix B for input-games. Here, the coupling matrix $A$ is independent of data: $A(x_i,x_j,y_i,y_j) = \\delta_{ij}$.\n\n> 3. What happens if the function $I_{2}$ is convex/concave instead of bilinear?\n\nIf $I_2$ is convex-concave such that it satisfies the gradient growth bound condition (Assumption 2.1 (iv)) just like how we assumed so for $I_1$ and $I_3$, our results would carry over.\n\n> 4. Do your results still hold in the presence of noisy gradients?\n\nFor literature in the *minimization* setting, there are known overparameterization bounds in the presence of noisy gradients (see, e.g., [7, 8]). So, we would speculate that our results which are for the *min-max* case in the presence of `full-feedback` could be extended to the case of `noisy gradients`. We leave this as an interesting direction for future work.\n\n> 6. I think there is a small typo in line 304 ($P_{0}$ appears twice).\n\nThank you for pointing out the typo.\n\n**References:**\n\n[1] Mladenovic et al., Generalized natural gradient flows in hidden convex-concave games and GANs, ICLR 2022\n\n[2] Vlatakis-Gkaragkounis et al., Solving min-max optimization with hidden structure via gradient descent ascent, NeurIPS 2021\n\n[3] Sakos, et al., Exploiting hidden structures in non-convex games for convergence to Nash equilibrium, NeurIPS 2023\n\n[4] Song et al., Neural-network-based synchronous iteration learning method for multi-player zero-sum games, Neurocomputing 2017\n\n[5] Lei et al., SGD Learns One-Layer Networks in WGANs, ICML 2020\n\n[6] Wu et al., Using CNN for solving two-player zero-sum games, Expert Systems with Applications 2022\n\n[7] Song et al., Subquadratic Overparameterization for Shallow NNs, NeurIPS 2021.\n\n[8] Zou & Gu, Improved Analysis of Overparameterized DNNs, NeurIPS 2019."}, {"review_id": "m1eJStFz3L", "reviewer": "Reviewer_Xm4L", "summary": "This paper investigates the training dynamics of two-player, zero-sum games where players' strategies are represented by two-layer neural networks. The work aims to explain the empirical success of gradient-based methods in these non-convex non-concave settings. The authors provide a theoretical framework based on \"hidden convexity\" and overparameterization to establish convergence guarantees for the AltGDA algorithm. The core of their analysis involves deriving a path-length bound for the algorithm's iterates and showing that a two-sided PL condition holds with high probability under sufficient overparameterization.", "questions": "- The assumptions O(n^3) widh requirement appear to distance the paper's findings from current deep learning practices. Could you provide a more compelling argument for the relevance of these results to practitioners?\n\n- The paper focuses exclusively on two-player zero-sum games. Do you see a clear path to extending your framework to more complex settings, or are they fundamental issues?", "limitations": "The paper does acknowledge its limitations and potential societal impacts, which is good. However, the combination of requiring very wide two-layer networks and smooth activations, means the results are quite far from how neural networks are used in practice.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is well-written. The authors do a good job of motivating the problem and outlining their approach.\n- The contribuations of this work could have impact on modern machine learning, with relevance to GANs, adversarial robustness, and multi-agent systems.\n\n**Weakness**\n\n- The required network width of O(n^3) is extremely high.  This cubic scaling with the number of samples makes the result largely of theoretical interest.\n\n- The fact that the paper’s guarantees hold only for two-layer networks is a major practical limitation and extending these results to deep networks remains a challenge for future research.\n\n- The paper is purely theoretical, and there’s a big gap betwen its assumptions and how things actually work in practice. It really needs some experiments to show whether the overparmeterize networks are required, or to check if things break down when those conditions aren’t met. Without any empirical evidence, the results are abstract.", "was_revised": true, "final_justification": "- My initial criticism of the bound was likely too harsh without the context the authors have provided from the literature. \n- They also provided insights from the theoretical analysis.\n- As mentioned in the original review there is a gap between the theory and current practice but I have a more positive view of the paper's contribution.", "rebuttal": "We would like to sincerely thank the reviewer for engaging with our submission. Although the overall assessment was borderline-negative, we appreciate that you acknowledged both the relevance of the problem and the clarity of the draft.\n\nWhile one might note that this paper was **submitted to the theory track**—and thus expect more tolerance for foundational results—we recognize the importance of bridging theoretical insights with practical implications. We would like to highlight that, to the best of our knowledge, this work provides the **first overparameterization condition** for solving a broad class of **unconstrained min-max optimization problems** that arise in modern machine learning. Importantly, our result gives a *sufficient* condition, not a necessary one. Investigating whether the $\\widetilde{\\Omega}(n^3)$ bound is tight or improvable remains a compelling direction for future work.\n\n### Comparison with Previous Work \n\nIt’s worth recalling that the first overparameterization bounds for minimization problems were of the order $\\Omega(n^8 L^{12})$ (see table at the end of our resposne). It is natural that the complexity of the problem increases in game settings (with more than one player), and we currently lack a complete understanding of how such complexity scales. Hence, we see our work as the initial stepping stone in this research journey. As for experiments, we do plan to include them in the final version, but also note that several empirical results already exist in related literature (please see our detailed response to Reviewer `F1FN`).\n\nThat said, we understand that a practitioner might find it difficult to extract immediate actionable insights from the current theoretical guarantees alone. Therefore, beyond the asymptotic bounds and technical derivations, we outline below a few **practical takeaways** that our proof techniques reveal:\n\n---\n\n### Practical Insights for Practitioners\n\n\n1. **Interpretation of $\\sigma_{\\min}$ and Exploration**:  \n   The smallest singular value of the network's Jacobian, $\\sigma_{\\min}$, governs how well the model explores the strategy space. If $\\sigma_{\\min}$ is near zero, certain regions of the space may be entirely unexplored—indicating convergence to spurious subspaces. This provides a novel geometric interpretation of poor learning dynamics in games.\n\n2. **Data Geometry and Regions of Attraction**:  \n   The region where $\\sigma_{\\min} > 0$ is critical for guaranteeing convergence of AltGDA. Our results offer intuition into how *data selection and spread* affect optimization. While computing $\\sigma_{\\min}$ at each iteration for each candidate point is impractical, our findings imply that *overparameterization*, together with sufficiently diverse data, increases the likelihood of initialization inside a favorable region of attraction.\n\n---\n\nThese insights are, of course, intuitive and can stand on their own. What makes our contribution notable is that our proof *relies critically* on these properties to establish formal guarantees.\n\n\n\n\n### Beyond Two-Player Zero-Sum Games\n\n> **Do you see a clear path to extending your framework to more complex settings, or are there fundamental issues?**\n\nThis is an excellent and very insightful question. As is implicit throughout the paper, our results build upon several recent tools from the *hidden convex–concave* and *two-sided PŁ* literature, which we combined with insights from overparameterization theory to address general ML tasks within the two-player zero-sum setting.\n\nThe natural next step is to understand how these techniques scale to **multi-player** and **non-zero-sum** settings—especially in structured environments like **polyhedral games**, which share connections with extensive-form games.\n\nCurrently, we are working on the first steps towards this goal. Specifically, we are developing **gradient-based methods tailored for structured, non-monotone multiplayer games**. A key idea we are exploring is the analogy between *two-sided PŁ-conditions* (for two-player games) and **hypo-monotonicity** in multi-agent operator theory. This connection may allow us to transfer and generalize some of the intuition and techniques from our current setting.\n\nIf this optimization foundation holds, we aim to investigate how the core components of our analysis—such as **gradient path bounds** and their link to **network width and depth**—can be extended to games with more than two players. While this direction lies beyond the scope of the current submission, we believe it opens up a rich and technically deep avenue for future work.\n\nThank you again for raising this forward-looking and foundational question.\n\n\nOnce again, thank you for your careful reading and constructive criticism. We hope this clarifies the motivation and broader impact of our work, and we welcome further feedback or suggestions.\n\n--- \nBelow we provide a summary of some of the literature on overparameterization conditions derived for the case of minimizing $L_2$ loss function with shallow and deep neural networks (FCNN = Fully Connected Neural Network, $n$ = number of training samples, and $L$ = number of hidden layers).\n\n| Reference  | Model | Depth | Initialization | Activation | Width |\n|--------------------------------|-------------|----------|--------------------|-----------------|-------------------------|\n| Oymak and Soltanolkotabi (2020) | FCNN | Shallow | Standard Gaussian | ReLU | $\\Omega(n^2)$ |\n| Zou and Gu (2019) | FCNN | Deep | He | ReLU | $\\Omega(n^8 L^{12})$ |\n| Nguyen (2021) | FCNN | Deep | LeCun | ReLU | $\\Omega(n^3)$ |\n| Song et al. (2021) | FCNN | Shallow | He/LeCun | Smooth | $\\Omega(n^{3/2})$ |\n| Bombari et al. (2022) | FCNN | Deep | He/LeCun | Smooth | $\\Omega(\\sqrt{n})$ |                 |\n\n**References:**\n\n[1] Oymak and Soltanolkotabi (2020), Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks\n\n[2] Zou and Gou (2019), An improved analysis of training over-parameterized deep neural networks.\n\n[3] Nguyen (2021), On the proof of global convergence of gradient descent for deep relu networks with linear widths\n\n[4] Song et al. (2021), Subquadratic overparameterization for shallow neural networks\n\n[5] Bombari et al. (2022), Memorization and optimization in deep neural networks with minimum overparameterization."}, {"review_id": "5LiDsX8V8v", "reviewer": "Reviewer_njLz", "summary": "This paper investigates the problem of solving *neural min-max games* where the players are parameterized by neural networks (Network Optimization) or the strategies are the input of data (input Optimization). Specifically, the authors prove that if the players are parameterized by sufficiently wide two-layer neural networks, then under suitable initialization, the alternating Gradient Descent Ascent algorithm converges to the Nash equilibrium of the neural min-max games.", "questions": "My questions primarily concern how the settings and theoretical results in this paper reflect real-world training dynamics in min-max games. While the paper clearly focuses on theoretical contributions, I believe demonstrating that the theoretical phenomena (e.g., **overparameterization enabling convergence** and the **Gaussian initialization placing parameters near game equilibria**) have observable counterparts in practical applications would significantly enhance the paper's impact.\n\nIn particular, my questions include: \n\n* Beyond mathematical tractability, are there other reasons to focus on two-layer neural networks in neural min-max games? For example, is it possible to prove an analogy of universial approximation theorem for two-layer neural networks in min-max games?\n\n* How do the theoretical phenomena discussed above align with practical applications? If incorporating additional experiments is currently infeasible, could the authors provide references demonstrating these phenomena are indeed observed in real-world applications?\n\n* I also have a mild question regarding the claim in Lines 3-5: \"While such games often involve non-convex non-concave objectives, empirical evidence shows that simple gradient methods frequently converge...\" Could the authors provide references to specific empirical studies where gradient methods were observed to converge to equilibria in comparable experimental settings? To the best of my knowledge, unlike gradient methods in minimization problems, gradient descent-ascent is generally understood to have convergence limitations in real-world min-max games like GANs. \n\n\n**I would consider increasing my evaluation score if the paper included a substantive discussion of how the theoretical phenomena discovered in this work manifest in practical applications.** This could be achieved through either empirical validation demonstrating these phenomena in realistic training scenarios, or provide evidence of existing literature showing analogous behaviors in applied min-max optimization.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n\n* The problem of solving neural min-max games is novel and interesting. \n* The paper is well-written, particularly the introduction, which effectively motivates the general notation of neural min-max games.\n* The results establish an intriguing connection between overparameterization in minimization problems and min-max games, offering valuable theoretical insights.\n\n---\n## Weakness:\n\n* The current title suggests a broad investigation into how different architectures, initialization schemes, and training dynamics affect neural min-max game solving. However, the paper focuses narrowly on the convergence of alternating gradient descent ascent for two-layer neural networks. This discrepancy makes the title an inaccurate reflection of the paper’s actual contributions.\n\n\n* The motivation of studying two-layer neural networks is not very clear. In single-objective optimization, two-layer neural networks are well-motivated by the universal approximation theorem. However, the paper does not adequately explain why this architecture is particularly meaningful or relevant in the context of min-max games. A stronger theoretical or empirical justification would improve the motivation for this choice.\n\n* The paper lacks experimental results, making it unclear whether the theoretical findings align with practical scenarios. \n\n* The proof of the main result reveals that convergence relies critically on initializing the two-layer neural networks with Gaussian distributions, which places the parameters near equilibrium from the outset (Lines 311–315). This may restrictive and fails to reflect real-world scenarios. Moreover, the absence of numerical experiments further undermines the practical relevance of the theoretical findings. Without empirical validation, it remains unclear whether the proven convergence properties hold under more realistic conditions or whether they are merely an artifact of the idealized assumptions.", "was_revised": true, "final_justification": "This paper provides some interesting and novel theoretical results on the training dynamics of neural min-max games. However, there are no experiments to show whether these results are reflected in real-world scenarios, which makes the value of these theoretical results unclear. Thus, my final justification is borderline acceptable.", "rebuttal": "We sincerely thank the reviewer for their time and constructive feedback. We hope our response clarifies the contributions of the paper and addresses the concerns raised. We especially appreciate the reviewer's willingness to see the value in the theoretical study of overparameterization—even while raising thoughtful points about practical impact.\n\n---\n\n### Strengths\n\n> - The problem of solving neural min-max games is novel and interesting.  \n> - The paper is well-written, particularly the introduction, which effectively motivates the general notion of neural min-max games.  \n> - The results establish an intriguing connection between overparameterization in minimization problems and min-max games, offering valuable theoretical insights.\n\nWe are grateful for the positive assessment and appreciation of our presentation.\n\n---\n\n### On Title Suggestion\n\nThe reviewer suggested a more focused title. While we believe that both the abstract and introduction clearly frame the scope and avoid any overselling, we are happy to adopt a more targeted title such as:\n\n- *Solving Shallow Neural Min-Max Games: The Role of Overparameterization...*  \n- *The Role of Overparameterization in 1-Hidden-Layer Zero-Sum Neural Games...*\n\nWe note that such changes are typically accepted during the camera-ready/proceeding phase of the NeurIPS process.\n\n---\n\n### On the Use of Two-Layer Networks\nThe motivation for using two-layer neural networks stems indeed from their **universal approximation property (UAP)**. Informally, UAP asserts that two-layer networks can approximate any continuous function on a compact domain to arbitrary precision—purely as a matter of representational power. This property is **independent of the optimization algorithm** used and applies regardless of the learning task.\n\nThus, UAP holds in min-max games; two-layer networks can implement the Nash strategies of the hidden convex–concave game—*if* the right parameters can be found.\nThis leads to our main question:  \n> **How hard is it, from an optimization perspective, to find the parameters that realize such equilibrium strategies using a simple method like AltGDA?**\n\nWhile UAP ensures *existence*, our focus is on **computational tractability** and **algorithmic convergence**. We are not concerned with whether such a network *can represent* the solution (it can), but whether a natural learning dynamic—AltGDA—can **discover** it efficiently in practice.\n\nThis is particularly non-trivial since AltGDA is adversarial in nature (unlike cooperative optimization schemes), and even in structured games with bilinear coupling, the dynamics can become unstable. Hence, even for such structured games, we require $\\widetilde{\\Omega}(n^3)$ overparameterization to guarantee convergence to the Nash equilibrium under AltGDA.\n\nIn summary:  \n- UAP ensures representational power—two-layer networks can implement Nash strategies.  \n- Our contribution analyzes whether AltGDA can *find* those parameters, given large but practical overparameterization.  \n- This bridges expressivity with optimization, offering the first steps toward understanding learning in neural min-max games.\n\n---\n\n## Main Concern: Practical Impact of Overparameterization in Min-Max Games\n\n> **I would consider increasing my evaluation score if the paper included a substantive discussion of how the theoretical phenomena discovered in this work manifest in practical applications.**\n\nWe understand and value this concern. While our focus is theoretical (the primary area in our submission is THEORY), we aim below to provide both empirical context and intuitive takeaways from our results.\n\n---\n\n### Literature Showing Benefits of Larger Networks in Min-Max Settings\n\nIn several applied min-max contexts—adversarial training, GANs, DRO, and neural agents—larger networks have been shown to lead to improved convergence and performance:\n\n- **Adversarial training:** Addepalli et al. [1] show improved robustness and performance with larger models.\n- **GANs:** Karras et al. [2], Brock et al. [3], and Sauer et al. [4] demonstrate that larger architectures stabilize training and enhance image quality.\n- **LLM Language agents:** Karten et al. [5] (PokéChamp) show improved performance using GPT-4.0 versus smaller LLMs.\n- **DRO:** Pham et al. [6] show that bigger models may yield better worst-group generalization.\n\nThese results exemplify that while game dynamics can be reasonably unstable, if the model is enough large, this burden can be overpassed. \nInterestingly if the reader would like to sacrifice the technicalities around the non-asymptotic bounds our proof techniques offer several insights for practitioners:\n\n1. **Interpretation of $\\sigma_{\\min}$ and Exploration**  \n   The smallest singular value of the network Jacobian, $\\sigma_{\\min}$, controls how well the model explores the strategy space. When $\\sigma_{\\min} \\approx 0$, certain strategies remain unexplored, indicating convergence to spurious subspaces. Our analysis ties this directly to the degree of overparameterization.\n\n2. **Data Geometry and Regions of Attraction**  \n   Our results show that overparameterized networks initialized with sufficiently diverse data are more likely to fall into regions where $\\sigma_{\\min} > 0$, ensuring stable convergence under AltGDA. While computing $\\sigma_{\\min}$ per iteration is impractical, the connection offers design insights for data and architecture.\n\n**These insights are, of course, intuitive and can stand on their own.** What makes our contribution notable is that our proof *relies critically* on these properties to establish formal guarantees.\n\n---\n\n### On Experiments\nSince our submission was under the `THEORY` track, we focused the main paper on foundational results. We have conducted supporting experiments to include in the final version. Per NeurIPS policy, we exclude them here but will include them in the final version. \n\n**In response to the reviewer's request**, we also note that similar experiments appear in prior work ([1']–[6'] below) either in shallow or deep NNs, which provide visual and empirical support for our framework.\n\nWe hope this collective evidence serves as a strong preliminary justification of the practical relevance of our results.\n\n---\n\n### References (Literature on Overparameterization & Experiments)\n\n**Empirical Benefits of Bigger Models in Min-Max Learning**  \n[1] Addepalli et al., *Scaling Adversarial Training to Large Perturbation Bounds*, ECCV 2022\n\n[2] Karras et al., *Progressive Growing of GANs for Improved Quality, Stability, and Variation*, ICLR 2018\n \n[3] Brock et al., *Large Scale GAN Training for High Fidelity Natural Image Synthesis*, ICLR 2019\n\n[4] Sauer et al., *StyleGAN-XL: Scaling StyleGAN to Large Diverse Datasets*, SIGGRAPH 2022\n\n[5] Karten et al., *PokéChamp: an Expert-level Minimax Language Agent*, 2025\n\n[6] Pham et al., *The Effect of Model Size on Worst-Group Generalization*, NeurIPS 2021\n\n**Successful Gradient-Based Training in Shallow or Large Neural Zero-Sum Games**  \n[1'] Mladenovic et al., *Generalized Natural Gradient Flows in Hidden Convex–Concave Games and GANs*, ICLR 2022\n\n[2'] Vlatakis-Gkaragkounis et al., *Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent*, NeurIPS 2021\n \n[3'] Sakos et al., *Exploiting Hidden Structures in Non-Convex Games for Convergence to Nash Equilibrium*, NeurIPS 2023\n\n[4'] Song et al., *NN-Based Synchronous Iteration Learning for Multi-Player Zero-Sum Games*, Neurocomputing 2017\n\n[5'] Lei et al., *SGD Learns One-Layer Networks in WGANs*, ICML 2020\n\n[6'] Wu et al., *Using CNNs for Solving Two-Player Zero-Sum Games*, Expert Systems with Applications 2022\n\n---\n\n### Random Initialization – How Restrictive Are Our Results?\n\n1. **Network Optimization Min-Max Games**  \nOur main result (Theorem 3.7) assumes a commonly used initialization scheme (e.g., He or LeCun), with the only additional requirement being that the variances satisfy Equation (9) in our paper.  \n*Footnote:*  \nHe uses ($\\mathcal{N}(0, \\frac{2}{n_{\\text{in}}})$) for ReLU; LeCun uses $(\\mathcal{N}(0, \\frac{1}{n_{\\text{in}}}))$ for Sigmoid—both preserve variance and avoid vanishing gradients.\n\nOf course, bridging the gap between practice and theory, it remains an interesting open question whether the current polynomial overparameterization requirement can be reduced to linear. However, we note that—prior to our work—there were no existing theoretical results connecting initialization schemes with convergence guarantees in neural min-max games.\n\n2. **Input Optimization Min-Max Games**  \nIn this setting, our results are even **less restrictive** regarding initialization. Specifically, we show that if the neural networks are randomly initialized from a standard Gaussian distribution, then **AltGDA can compute the min-max optimal inputs**. As discussed in the main text, this is an *average-case result*, in the spirit of smoothed analysis. While it is theoretically expected that there exist neural architectures encoding hard min-max landscapes—potentially close to PPAD-hard instances—in practice, our result suggests that a **randomly initialized neural min-max game is tractable under AltGDA**. In fact, from our proof, one can further deduce that the **mean of the Gaussian initialization can be arbitrary**, thanks to the convergence properties of AltGDA. Thus, this result can be interpreted through the lens of **smoothed analysis**:  \n> Given a hard input neural min-max game, if one perturbs it with Gaussian noise (with inverse-polynomial variance), then AltGDA is provably able to find the optimal min-max input. The smaller the variance, the more brittle/rare are the hard instances for AltGDA.\n\nWe hope these clarifications address your concerns and provide a broader view of the theoretical and practical relevance of our work. Thank you again for your thoughtful review and engagement."}]

Author rebuttal:

Meta-review: The paper studies the convergence of zero-sum games between neural networks to equilibrium by exploiting a hidden convexity. This is a quite elegant result, knowing that the study of such, a priori,  non-convex non-concave problems, is hard that has many practical implications in machine learning, since it covers adversarial training, alignment and robust optimization.


I agree with the reviewers that this is a strong contribution that is a strong fit for NeurIPS, the authors are encouraged to include the suggestions made by the reviewers to the revised version.
Decision: Accept (spotlight)