Reproducibility Challenge NeurIPS 2019 Report on "Competitive Gradient Descent"

Authors suggest their method is a natural generalization of gradient descent to the two-player scenario where the update is given by the Nash equilibrium of a regularized bilinear local approximation of the underlying game. It avoids oscillatory and divergent behaviors seen in alternating gradient descent. The paper proposes several experiments to establish the robustness of their method. This project aims at replicating their results. The paper provides a detailed comparison to methods based on optimism and consensus on the properties of convergence and stability of various discussed methods using numerical experiments and rigorous analysis. In order to understand these terms, comparison and proposed method and examine the results of the experiments, next section gives a necessary background of the original paper. 2 Background The traditional optimization is concerned with a single agent trying to optimize a cost function. It can be seen as min x R m f ( x). The agent has a clear objective to find ("Good local") minimum of f . Gradeint Descent (and its varients) are reliable Algorithmic Baseline for this purpose.