A wide array of modern machine learning applications - from adversarial models to multi-agent reinforcement learning - can be formulated as non-cooperative games whose Nash equilibria represent the system's desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to equilibrium. Driven by this observation, our paper proposes a flexible first-order method that successfully exploits such "hidden structures" and achieves convergence under minimal assumptions for the transformation connecting the players' control variables to the game's latent, convex-structured layer. The proposed method - which we call preconditioned hidden gradient descent (PHGD) - hinges on a judiciously chosen gradient preconditioning scheme related to natural gradient methods. Importantly, we make no separability assumptions for the game's hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.
Paper
Similar papers
Peer review
Summary
This paper proposes a preconditioned hidden gradient descent to provide strong formal convergence guarantees in a general class of multi-agent settings which are referred to as call hidden monotone games. Theoretical analyses and synthetic experiments are also provided.
Strengths
1. The method seems novel to handle the proposed problem of hidden monotone games. 2. Theoretical analyses and synthetic experiments are also provided to demonstrate the effectiveness of the proposed method.
Weaknesses
1. Experiments on real-world datasets (e.g., MNIST or multi-agent reinforcement learning environments) are absent. 2. Experiments on adversarial generation, adversarial attack, and adversarial transfer learning are absent. 3. Computational complexity analyses are absent.
Questions
1. Is it feasible for this method to be applied to common neural networks, such as ResNet50, BERT, etc?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Yes.
Summary
It is known that a convergence guarantee exists for monotone games. However, most games are not monotone. This paper considers a new scenario where the monotone structure is presented in latent space. It then proposes the 'Preconditioned Hidden Gradient Dynamics' to design the preconditioned hidden gradient descent algorithm. It is demonstrated that the proposed algorithm will converge to the desired Nash equilibrium. The theoretical result is also verified using empirical experiments.
Strengths
Novelty: Existing works have shown the difficulties of finding the equilibrium in hidden-monotone games. Other results usually require additional assumptions on the structure. This work proposes a new perspective to design the preconditioned hidden gradient descent and solves the problem that has not been addressed before. Significance: Most of games are not monotone. Studying the hidden-monotone structure will significantly extend the existing literatures on monotone games, which makes me believe this work opens a new direction of the resarch. The positive result obtained in this work and the new design in the continous-flow will also help understanding on the hidden structure.
Weaknesses
This paper is very well-written. But it may lack some real-world examples to help the reader understand the importance of studying the hidden games.
Questions
This paper has mentioned many times "minimal assumptions" or "without additional assumptions". I am probably interested in how strong other assumptions are, such as separability or low-dimensionality assumptions. Do you have any simple examples saying these assumptions are not satisfied. Figure 1 is very helpful to understand the concept of hidden games. Do you have any practical example or real-world example that would have such Rock-Paper-Scissors hidden structure?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
This is a purely theoretical work so no negative impact.
Summary
The paper uses hidden structure to provide continuous time and algorithmic theoretical learning guarantees for certain non-convex games. Specifically, they provide Preconditioned Hidden Gradient Flow and its discrete-time variant Preconditioned Hidden Gradient Descent that can be proved to converge when analyzed under a specific Lyapunov function.
Strengths
The theoretical contribution of the paper is significant, compared to past work, the setting is significantly more general. The paper is very well presented, with figures explaining the basic theoretical ideas behind the paper. The theory is solid and rigorous, while I have not checked the proofs line by line, they seem to be correct. Furthermore, significant motivation is provided both visually and by argumentation for the proof strategies employed. Experiments are also provided, and in toy examples the algorithm is demonstrably better than alternatives. Overall, the paper solves an important problem in algorithmic game theory.
Weaknesses
I think this is a strong paper with a solid contribution. Some possible weaknesses: * A discussion of the relevance of the faithfulness assumption on the hidden map could be discussed. For instance, the experiments conducted seem to be on particular toy problems, it’s not immediately clear if there are large classes of problems with hidden structure that satisfy the given conditions. * The authors make an effort to present the ideas behind the proofs, which are the main contributions of the paper. Still, the presentation in the main body could benefit from a condensed roadmap of the proof strategy. While Section 4 contains main ideas, the overall picture was difficult to grasp. * The assumption on the representation map (e.g. faithfulness) is difficult to locate, the assumption could be made more explicit for ease of reading. * Experiments are limited to somewhat simple cases, an evaluation of PHGD on for instance GAN training or other relevant problems in practice could be a stronger empirical argument.
Questions
The examples mentioned in the experiment are interesting but also seem to be restricted to very specific cases. Are there larger classes of problems besides Examples 2.1, 2.2 that could be relevant in applications? For instance, has there been work on when neural network parameterization could satisfy the faithful map condition? While being possibly out of the scope of the main contribution of the paper, a discussion of these points could be interesting. As a possible limitation, is the implied access to the Jacobian of representation map standard in the literature? The paper mentions dimension reduction as a motivation of the representation map. It is not immediate to me that dimension reduction could be achieved while simultaneously preserving the faithfulness assumptions, due to topological considerations. A discussion of this point could be interesting. For instance, does the El Farol Bar game parameterization satisfy the faithfulness assumptions? *Minor questions:* Line 195 -> Is the message that $\mathbf{P}_i$ will be designed to achieve certain properties of was it defined before? Was not clear on the first read. Lines 177 - 189 -> The connection between the two paragraphs was not clear. Was NHGD shown to not require the mentioned assumptions? *Possible minor Typos:* Line 116: $\Theta$ -> $\Theta_i$? Line 164: For the Jacobian notation, should it depend on $\theta_i$ Line 172: Here, it is possible that the notation is confusing with the previous separation of the control variables of each player. As far as I understand, the individual coordinates of the controls of one player is meant here. Line 254: an closed -> a closed
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
No major limitations. As mentioned above: empirical validation could be extended to relevant problems in application.
Summary
The paper focuses on studying non-convex games with hidden structures, where latent variables can be seen as a function of control variables and are decoupled. The authors propose a discrete algorithm called Preconditioned Hidden Gradient Descent (PHGD) to exploit the hidden structure and achieve convergence to Nash equilibrium. The method establishes a connection with natural gradient methods through the selection of gradient preconditioning schemes. The paper provides the first discrete convergence analysis on hidden convex concave games and extends the separable assumption to a more general multi-player setting. Convergence is proven under minimal assumptions, both in deterministic and stochastic environments.
Strengths
- Originality: The paper introduces a novel algorithm, PHGD, to address non-convex games with hidden structure, providing the first discrete convergence analysis in this context. The connection established with natural gradient methods adds an original perspective to the research. - Quality: The paper demonstrates rigorous analysis by providing explicit convergence rates under minimal assumptions. It extends the previous work by considering a more general multi-player setting. - Clarity: The summary provided is clear and understandable, indicating good clarity in the paper. - Significance: The paper addresses an important problem by leveraging hidden structure in non-convex games, which has implications in various domains. The developed algorithm and its convergence properties contribute to the understanding and applicability of game theory.
Weaknesses
- Lack of diverse examples: The paper could benefit from including additional examples beyond the matching Pennis zero-sum game to illustrate the applicability of the proposed method in different settings. The example shown in this paper can be included within previous 1-dimensional assumptions presented Mladenovic et al. Are there significant instances that this paper covers while previous results do not? - Lack of comparison with existing methods: It would be helpful if the authors provided a more detailed explanation of the technical challenges associated with discrete analysis compared to continuous ones. For the continuous dynamics, does it reduces to the exact natural gradient flow in hidden convex-concave games in Mladenovic et al., - It seems that the faster convergence is at the expense of high computational complexity.
Questions
- Preconditioning method and its relation to natural gradient: The authors claim that "a judiciously chosen gradient preconditioning scheme bears an unexpected connection to natural gradient method". However, the connection has not been well explained in the main context. What is the literature of the preconditioning method? Why is the previous natural gradient approach not seen as preconditioning? - Technical difference in extending to the multi-dimensional case: What are the main technical differences or challenges encountered when extending the approach to the multi-dimensional case? - Minor issue regarding notation: In Line 195, where $P_i(\theta_i)$ appears before introducing what $P_i$ represents.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
4 excellent
Limitations
The limitations of this paper have not been addressed adequately.
Summary
This paper studies a hidden preconditioned stochastic gradient descent method for finding Nash equilibrium in games with hidden monotone structures. It demonstrates non-asymptotic convergence bound of the proposed algorithm. The complexity bound of the hidden monotone game matches that of monotone games. The topic is very interesting as it provides a way to handle non-monotone stochastic games, which motivates me to read in details. Overall, it is an interesting paper. However, the presentation quality needs serious improvement. It is hard to judge the correctness with so many typos.
Strengths
The motivation of the hidden gradient descent design is clear. The convergence rate result for hidden monotone stochastic games seems to be new and matches the optimal complexity bound for stochastic games.
Weaknesses
The presentation of the paper is poor with lots of typos. Without the Errata provided by the authors in the Appendix, when reading the main context for the first time, I found many mathematical mistakes. After reading the authors own corrections, there still remain many typos, making it hard to understand. The notation system is very confusing. I have tried my best to go through the proof. The overall idea seems correct but I cannot guarantee details. See more comments below. The examples used to motivate the problems seems to be too simple. Example 2.1 is too simple. Example 2.2, it is unclear why one does not first solve the bilinear problem and find a corresponding mapping, which is not even needed actually. The example provided in figure 1 does not really need a neural network to approximate the probability space. For Assumption 1, the paper claims that $\theta$ and $x$ does not need to be within the same space, i.e., the dimension of them can be different. I wonder if $\Theta$ is the whole space on $R^m$ and if $\mathcal{X}$ is the whole space on $R^d$. Please specify the conditions for the Jacobian has positive and finite minimal and maximum singular values when $m\not=d$. Please give more concrete examples when the Jacobian can be exactly computed as required in the PHGD algorithm. If the Jacobian can be exactly computed, why one does not solve the hidden problem to optimality first and then find a mapping from control to optimal decision directly? Missing literature: there exists some literature on hidden convex structures in optimization and reinforcement learning with non-asymptotic convergence guarantee. The hidden gradient descent also appears previously. See literature [1-2] and reference therein. [1] Zhang, Junyu, et al. "Variational policy gradient method for reinforcement learning with general utilities." Advances in Neural Information Processing Systems 33 (2020): 4572-4583. [2] Chen, Xin, et al. "Efficient Algorithms for Minimizing Compositions of Convex Functions and Random Functions and Its Applications in Network Revenue Management." arXiv preprint arXiv:2205.01774 (2022).
Questions
P2 Line 77, the "[]" should be deleted. P3 Line 99, Here $F$ is defined over $\theta$. $F$ is later defined over $x$. Making it super confusing. Although $F$ is represent $l$ here, later $f$ is also used to denote $l$. Another notation $L$ is used to denote the stochastic counterpart of $l$. And then $f$ is used to denote a stochastic counterpart of $L(\chi)$. Please read these notations to see how confusing they are. P5 Line 195, it is unclear why $P$ is defined over $\theta_i$ rather than $\theta$. P5 Lemma 1, what is a hidden smooth structure? What assumptions are exactly needed on $F$ and $\chi$ function to ensure the format of $P$. P6, in Lemma 2, I suppose $\chi(\theta)=x$ by definition? P6 Line 230, about the statement for the first moment is totally wrong. P6 Line 238 & 239, $f_i$ is previously defined for deterministic function. Now $f_i$ becomes a random function. What is exactly the algorithm that one should run? I suppose that one should run PHGD with $\hat g_{i,t}$ defined by $L$ rather than $f_i$ right? Line 308, there should be a space between "games" and "This". Lemma 6, the notation is broken. Equation (C.5j) missing 1/2 in the third line. There are many mismatch notations in the main context and the appendix.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
1 poor
Contribution
3 good
Limitations
The motivation for using the method is not adequately discussed. Some more explanation on the limitation of some assumptions is definitely welcomed.
Thank you for the response. Despite the readability issue caused by typos, I appreciate the technical novelty in the paper. With regard to point 16, it seems that the proposed method is most useful when one cannot control the decisions made in the latent monotone games. Otherwise, there is no point in learning from the control layer, as one can directly play a monotone game in the hidden latent space. In this regard, the examples provided do not support the motivation well enough.
First, we would like to sincerely thank you for your quick response and input. The first thing we would like to clarify is that, in line with the established literature on hidden games (see below for a representative list of references), the agents *do not play the hidden game directly*: the agents' decisions are their control variables, not the latent variables. The latent variables merely represent a modeling abstraction and are best thought of as virtual/auxiliary variables that capture a certain structure in the players' payoff functions. In this regard, identifying a solution in terms of latent variables is not meaningful from the players' viewpoint unless they can also find the control/decision variables that realize said solution. We should also note that this model is not due to our paper but is the standard model for hidden games in the literature, see references [1-4] below. Given that this is an established model in the literature, the main focus of our paper was to develop a suite of learning algorithms and tools that would allow the effective solution of such problems. As for additional instances/examples of our model, another interesting class of problems that can be cast in the framework of hidden games is that of team zero-sum games [5], where there exist two competing teams of agents. For each possible outcome of the game, the payoffs of all members within a single team are equal to each other and represent the payoff of the team. The sum of the payoffs of two teams is equal to zero. Several variations of these models have been the object of recent study [6-8] and they readily fall within a hidden game framework where the space of latent variables is the set of (mixed extensions) of the strategy outcomes of each team. We hope that the above clarifies further the positioning of our work in the existing literature on hidden games. We thank you again for your input and please let us know if you have any further questions. > [1] Vlatakis et al. Poincare recurrence, cycles and spurious equilibria in gradient-descent-ascent for non-convex non-concave zero-sum games. (NeurIPS 2019) > [2] Flokas et al. Solving min-max optimization with hidden structure via gradient descent ascent. (NeurIPS 2021) > [3] Mladenovic et al. Generalized natural gradient flows in hidden convex-concave games and gans. (ICLR 2021) > [4] Pattathil et al. Symmetric (optimistic) natural policy gradient for multi-agent learning with parameter convergence. (AISTATS 2023) > [5] Schulman et al. The duality gap for two-team zero-sum games. Games and Economic Behavior (2019) > [6] Anagnostides et al. Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games. (EC 2023). > [7] Kalogiannis et al. Teamwork makes von Neumann work: Min-max optimization in two-team zero-sum games. (ICLR 2023) > [8] Kalogiannis et al. Efficiently Computing Nash Equilibria in Adversarial Team Markov Games. (ICLR 2023)
Thanks for the clarification. I have read all responses and will raise the score to 5. I believe serious efforts need to be made in order to improve the presentation quality and correct all typos but the merit of the paper is also clear.
Thank you for your continued input and for upgrading your score, we will update our manuscript according to your detailed suggestions and remarks. Regards, The authors
Thanks for the clarifications. Regarding the matter of dimension reduction: Assumption 1 still requires that the Jacobian has singular values lower bounded away from zero. By the inverse function theorem then we can find (at least) a neighborhood where the representation map is locally continuous bijection to the image of the neighborhood, implying an open neighborhood of the parameter space and the latent space is homeomorphic and has the same dimension. In fact, in the example given by the authors, the linear map would have non-empty nullspace (implying a 0 singular value for the Jacobian). Or am I missing something?
Thanks for your follow-up, we understand now the source of the confusion! To make things absolutely clear, consider first as an example the linear transformation $J\colon\mathbb{R}^2 \to \mathbb{R}$ with matrix $$ J = \begin{matrix}(1 & 2)\end{matrix} $$ The singular values of $J$ are defined either as the eigenvalues of $J^\top J$ or as the eigenvalues of $JJ^\top$, depending on convention. In the former convention, the singular values of $J$ are $\sqrt{5}$ and $0$, in the latter there is only one, $\sqrt{5}$. The latter convention is more parsimonious for linear transformations that are surjective, so this is the convention we tacitly employed throughout (precisely because the regime of interest is when $m \geq d$). [When there is danger of confusion, the latter convention is sometimes referred to as "thin singular value decomposition" in the literature] With this in mind, the relevant part of Assumption 1 reads more explicitly as $$ \sigma_{\min}^2 \leq \mathrm{eig}(J_\theta J_\theta^\top) \leq \sigma_{\max}^2 $$ so there is no issue if $m>d$: in this case, $J_\theta \colon \mathbb{R}^m \to \mathbb{R}^d$ is surjective (or, equivalently, $J_\theta$ has full rank as a matrix). In particular, the inverse function theorem *does not apply* for $m>d$ (since $J_\theta$ cannot be injective if it is surjective and $m>d$), but the *implicit* function theorem does, and it implies that $\chi$ locally looks like a projection (in suitable coordinates around the point under study). We hope this clears things up. To avoid any risk of ambiguity or confusion and make things more explicit, we will restate Assumption 1 directly in terms of the eigenvalues of $J_\theta J_\theta^\top$. Thank you again for the follow-up - and please let us know if you have any further questions! Kind regards, The authors
Thank you very much for the clarification and the explicit statement of Assumption 1.
Response
Thank you for the detailed examples! My concerns have been well addressed. I've also gone through comments from other reviewers, but none raised any new concerns for me. So I will maintain my positive rating.
Thank you for your rebuttal. I believe the contribution of this work is good, but there is still room for improvement in its presentation. I will raise my score to 5.
Thank you for your positive re-evaluation, we will update our paper according to your detailed input and remarks. Regards, The authors
Decision
Accept (poster)