Reproduce “The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Constantinos Daskalakis, Ioannis Panageas

Researchers at MIT systematically characterized the limit points of Gradient Descent/Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA) in general min-max optimization problems, demonstrating that both algorithms avoid unstable critical points for almost all initializations. The work established that GDA-stable points are a subset of OGDA-stable points, with this inclusion being strict in certain cases, and detailed how these stable points relate to local min-max solutions.

Key insights

  • Both GDA and OGDA dynamics, for almost all initializations, avoid converging to linearly unstable fixed points, ensuring that if they converge, it's to a stable state.
  • OGDA is "more stable" than GDA, meaning that any critical point GDA stabilizes is also stabilized by OGDA for small step sizes, and OGDA can stabilize points that GDA cannot.
  • The set of GDA-stable points is not fully aligned with local min-max solutions; GDA can stabilize points that are not local min-max, and some local min-max points may not be GDA-stable.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.