An implicit gradient-descent procedure for minimax problems

Understand

A game theory inspired methodology is proposed for finding a function's saddle points.

• While explicit descent methods are known to have severe convergence issues, implicit methods are natural in an adversarial setting, as they take the other player's optimal strategy into account.
• The implicit scheme proposed has an adaptive learning rate that makes it transition to Newton's method in the neighborhood of saddle points.
• Convergence is shown through local analysis and, in non convex-concave settings, thorough numerical examples in optimal transport and linear programming.