The major contributions of this paper are that it proves the global convergence of BP(Theorem 1.3) and VI(Theorem 1.2) on ferromagnetic Ising model with a specific initialization, i.e., to initialize variables to be 1. The proof of Theorem 1.2 is based on the fact that the mean-field free energy function, i.e., \Phi(x) is concave on the set S obtained by the update rule, and then we can use Holder's inequality to expand the \Phi(x*) - Phi(x_t) and get the upper bounds. The proof of Theorem 1.3 is based on the fact that the norm of \Phi(v)'s gradient is less than 1(Lemma 3.2), and the properties of variable \mu sandwiched between v 0 and final v T(Lemma 3.5 and Lemma F.1). Other minor contributions include that it provides examples to empirically show the convergence(appendix G) and it shows how to use ellipsoid method to optimize the beliefs(appendix H). I have to admit that I am not familiar with this area, so can only go through a part of the proof, and I am not able to evaluate the originality and quality of this work.

This paper deals with the computation of Nash Equilibria in competitive two-player games where the x player is minimizing a function f(x,y) and the y player is minimizing a function g(x,y) . Such problems arise in a wide variety of domains, notably in training GANs, and there has been much recent interest in developing algorithms for solving such problems. Gradient Descent Ascent (GDA) is a natural candidate algorithm for finding Nash Equilibrium, but it will provably oscillate or diverge even in simple settings. As such, many recent works have modified GDA or proposed different algorithms or schemes to guarantee convergence. This paper proposes a new algorithm called Competitive Gradient Descent (CGD), which updates each player's iterates by adding the Nash Equilibrium of a regularized bilinear approximation of the game at the current iterates. CGD requires Hessian-vector products, making it a second-order algorithm.

Overall, the reviewers appreciated the novelty and simplicity of the algorithm. The paper is also well written and the methods are well motivated. In terms of content for revision: The lack of discussion around Newton-style approximation and dropping of diagonal terms in the Jacobian was raised again the discussions (see updated reviews). Additionally, we also sought an expert reviewer during discussions. The additional reviewer included below: ---- Additional review: The paper proposes an interesting new method for solving games Min_x F(x,y) Min_y G(x,y) which is, in general, different from running online gradient descent on x and y in parallel, or other existing methods.

Summary and Contributions: Trust Region Newton Algorithm (TRON) is the most efficient solver for L2 regularized primal problems e.g. Due to the complex and sequential nature of this algo., its past performance boosts have largely been driven by shared memory multi-core systems. This paper demonstrates significant speedups in the training time of TRON solver compared to multithreaded implementations by using GPU specific optimization principles. The authors apply specific optimizations on sparse representation (LR training) and dense representation problems (SVM training) to generate significant speedups in their training time using GPUs. Specifically, for sparse feature representation datasets and LR loss function, the authors prescribe optimizations that minimize sequential dependence of CPU/GPU execution on each other by assuming all conditional branches evaluate in favor of the high-compute operations that can be run pre-emptively on the GPU.

The algorithm itself is a straightforward combination of Epoch-SGD for minimization and the well-known gradient-descent-ascent method for minimax problem. At the heart of the analysis is a new lemma that relates the duality gap to some distance measures between two points.

The main result in the paper extends a classical result of Hazan et al to a O(1/T) convergence bound for the duality gap of non-smooth strongly convex-strongly concave min-max problem (instead of the objective gap), proposing a min-max adaptation of the algorithm (Epoch-GDA). They also provide a related bound for finding approximate stationary points in weakly convex-strongly concave problems. Overall the reviewers found the contribution to be a significant and challenging extension over the existing result of Hazan et al. with specific challenges to be overcome in the duality gap version. The authors are strongly recommended to make the promised revisions in the rebutttal as they will embellish the paper.

POS-AUTHOR FEEDBACK I thank the authors for their feedback and clarifications. I have increased my score based on those answers, and trusting that the promised modifications will appear in the final version. I would strongly encourage to make the release of the code as easy to use as possible, ideally with plugins for major platforms. This would not only increase citations, but have a direct impact in a number of use-cases ORIGINAL REVIEW This paper addresses the softmax bottleneck problem: resolving it has shown to significantly improve results when the output is over a large space (eg: NLP). However, current solutions are very costly.

This paper proposes techniques to deal with the softmax bottleneck problem. Pros • Experimental results show strong performances in language modeling and machine translation. Cons • Writing of the paper can be further enhanced by making it self-contained. The paper represents solid work. There are clarity issues pointed out by the reviewers.

Summary and Contributions: Update after the author response: I want to thank the authors for clarifying how exactly KL between prior and approximate posterior is calculated in VI set-up. Usually, an "interesting" inductive bias / prior distribution is formulated in the original combinatorial space X rather than utility space U. Hence, I believe it would be beneficial for the potential reader if this limitation is mentioned explicitly in the paper. The paper is concerned with the task of estimating the gradient of the following form: d E_{X p_\theta}[L(X)] / d\theta. Where X represents a combinatorial object (e.g. This loss is ubiquitous in variational inference approach to latent variable models with structured latent variables.

All three referees are very positive about this paper and support accept. Please follow Reviewer 4's additional comments to clarify how the KL term is calculated in the revision.