SDEs for Minimax Optimization

Enea Monzio Compagnoni, Antonio Orvieto, Hans Kersting, Frank Norbert Proske, Aurelien Lucchi
2/19/2024
cs.LGmath.OC

No official code found. Best implementation: eneamc/MinimaxSDEs (3 stars, last commit 2024-02-07).

Abstract

Minimax optimization problems have attracted a lot of attention over the past few years, with applications ranging from economics to machine learning. While advanced optimization methods exist for such problems, characterizing their dynamics in stochastic scenarios remains notably challenging. In this paper, we pioneer the use of stochastic differential equations (SDEs) to analyze and compare Minimax optimizers. Our SDE models for Stochastic Gradient Descent-Ascent, Stochastic Extragradient, and Stochastic Hamiltonian Gradient Descent are provable approximations of their algorithmic counterparts, clearly showcasing the interplay between hyperparameters, implicit regularization, and implicit curvature-induced noise. This perspective also allows for a unified and simplified analysis strategy based on the principles of Itô calculus. Finally, our approach facilitates the derivation of convergence conditions and closed-form solutions for the dynamics in simplified settings, unveiling further insights into the behavior of different optimizers.

View on arXivView PDF

Code Implementations(1)

eneamc/MinimaxSDEsCommunity100%

Code to replicate results from the paper "SDEs for Minimax Optimization"

30Jupyter NotebookFeb 7, 20242 years ago

Similar Papers

Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements

85% match2023

Is Stochastic Gradient Descent Effective? A PDE Perspective on Machine Learning processes

85% match2025

Beyond Single-Model Views for Deep Learning: Optimization versus Generalizability of Stochastic Optimization Algorithms

84% match2024

Adaptive Step Sizes for Preconditioned Stochastic Gradient Descent

84% match2023

A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization

83% match2024

Learning rate adaptive stochastic gradient descent optimization methods: numerical simulations for deep learning methods for partial differential equations and convergence analyses

83% match1 repo12024

Cite this paper

@article{compagnoni2024sdes,
  title  = {SDEs for Minimax Optimization},
  author = {Enea Monzio Compagnoni and Antonio Orvieto and Hans Kersting and Frank Norbert Proske and Aurelien Lucchi},
  year   = {2024},
  eprint = {2402.12508},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2402.12508v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2402.12508.svg)](https://codeofpaper.com/paper/2402.12508)

Discussion