The reviewers have some concerns that the rebuttal didn't fully address but they all like the paper and agree that it should be accepted at NeurIPS.

I appreciate the author's taking time to respond to comments from my review. In particular I look forward to see similar techniques applied to multi-agent hidden network zero-sum games as per their response. The action space is given by finite vector spaces, and these map to a lower dimensional space via a smooth function. Payoffs are then zero-sum in this space. Although it is already known that gradient descent is difficult for games (even zero-sum games as those used), the authors show that even in this general dynamic the situation is just as dire.

Following the author response, consensus on acceptance was easily reached, on the grounds that the paper makes important contributions to gradient dynamics in certain zero-sum games which capture a restricted class of GANs. We encourage the authors to clarify the introduction/motivation to accurately reflect the results.

The title used for the paper is misleading since the rate O(epsilon {-2}) can only be achieved for a special class of non-convex concave min-max problems. More specifically, this rate is attained when using the algorithm to minimize the pointwise maximum of finite collection of non-convex functions. For general non-convex concave the rate is O(epsilon {-4}). This is clarified in the body of the paper, but the title is clearly misleading. It is not clear in the paper when this assumption (or even its relaxed replacement in the appendix) holds in practice.

Originally, the paper got three positive scores: 7,7,6, all with very high confidences. Basically, there was no critical issues raised by the reviewers, except suggesting the enhancement on experiments and clarifying some points. During discussion, all the reviewers agreed that the paper should be accepted and Reviewer #3 raised his/her score to 7. So all the reviewers reached a consensus. Thus the AC decided to accept the paper. However, the AC also have the following comments after a quick reading.

This has clarified some of my comments, and thus I have increased my score by one level. However, a negative aspect from the author response was the excuse given for the absence of a comparison against SVN; "the results we obtained were much worse than our methods and baselines, and hence did not investigate it further". To me this seems like a very obvious thing to include and discuss in the paper, lending strong support to the new method, so I am a bit suspicious about why it wasn't included. I hope the authors will include it in the revised manuscript, if accepted. Another reviewer commented on the lack of wall-time comparison, and again I feel that the authors did not give a valid excuse for omitting this information from the manuscript (the reader can, I think, be trusted to adjust for different computational setups and hardware when interpreting the wall-time data).

The reviewers felt that this submission represents an important contribution to the field. Please be sure to carefully review and address the concerns of all reviewers (e.g., introducing a comparison with SVNM and providing complete implementation details) in the revision.

Update: I read authors' responce RE:sampling rate does not tell the whole story - i was suggesting to add information about on average how many instances were used for each of the splits (because it is not equal to sampling rate * total dataset size). I am keeping my accept rating, hoping that authors do make the changes to improve the derivations/clarity in the final submission Summary: this paper is concerned with a common trick that a lot of GBDT implementation apply - subsampling instances in order to speed up calculations for finding the best split. The authors formulate the problem of choosing the instances to sample as an optimization problem and derive a modified sampling scheme that is aimed at mimicking the gain that would be assigned to a split on all the of the data by using a gain calculated only on a subsampled instances. The experiments demonstrate good results. The paper is well written and easy to follow, apart from a couple of places in derivations(see my questions).

The authors propose a non-uniform sampling strategy for stochastic gradient boosted decision trees. In particular, sampling probability of the training data is optimized towards maximizing the estimation accuracy of the splitting score of decision trees. The optimization problem allows an approximate closed-form solution. Experiment results demonstrate superior performance of the proposed strategy. The reviewers agree that the paper can not only help understand sampling within GBDT from a more rigorous perspective but also improve GBDT implementations in practice.

We focus on reducing communication overhead in multiplayer games, where frequently exchanging strategies between players is not feasible and players have noisy or outdated strategies of the other players. We introduce Decoupled SGDA, a novel adaptation of Stochastic Gradient Descent Ascent (SGDA). In this approach, players independently update their strategies based on outdated opponent strategies, with periodic synchronization to align strategies. For Strongly-Convex-Strongly-Concave (SCSC) games, we demonstrate that Decoupled SGDA achieves near-optimal communication complexity comparable to the best-known GDA rates. For weakly coupled games where the interaction between players is lower relative to the non-interactive part of the game, Decoupled SGDA significantly reduces communication costs compared to standard SGDA. Our findings extend to multi-player games. To provide insights into the effect of communication frequency and convergence, we extensively study the convergence of Decoupled SGDA for quadratic minimax problems. Lastly, in settings where the noise over the players is imbalanced, Decoupled SGDA significantly outperforms federated minimax methods.