Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929719847419904 |
|---|---|
| author | Zhao, Eric Chavdarova, Tatjana Jordan, Michael |
| author_facet | Zhao, Eric Chavdarova, Tatjana Jordan, Michael |
| contents | Variational inequalities (VIs) are a broad class of optimization problems encompassing machine learning problems ranging from standard convex minimization to more complex scenarios like min-max optimization and computing the equilibria of multi-player games. In convex optimization, strong convexity allows for fast statistical learning rates requiring only $Θ(1/ε)$ stochastic first-order oracle calls to find an $ε$-optimal solution, rather than the standard $Θ(1/ε^2)$ calls. This note provides a simple overview of how one can similarly obtain fast $Θ(1/ε)$ rates for learning VIs that satisfy strong monotonicity, a generalization of strong convexity. Specifically, we demonstrate that standard stability-based generalization arguments for convex minimization extend directly to VIs when the domain admits a small covering, or when the operator is integrable and suboptimality is measured by potential functions; such as when finding equilibria in multi-player games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20649 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity Zhao, Eric Chavdarova, Tatjana Jordan, Michael Machine Learning Optimization and Control Variational inequalities (VIs) are a broad class of optimization problems encompassing machine learning problems ranging from standard convex minimization to more complex scenarios like min-max optimization and computing the equilibria of multi-player games. In convex optimization, strong convexity allows for fast statistical learning rates requiring only $Θ(1/ε)$ stochastic first-order oracle calls to find an $ε$-optimal solution, rather than the standard $Θ(1/ε^2)$ calls. This note provides a simple overview of how one can similarly obtain fast $Θ(1/ε)$ rates for learning VIs that satisfy strong monotonicity, a generalization of strong convexity. Specifically, we demonstrate that standard stability-based generalization arguments for convex minimization extend directly to VIs when the domain admits a small covering, or when the operator is integrable and suboptimality is measured by potential functions; such as when finding equilibria in multi-player games. |
| title | Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicity |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2410.20649 |