Research map / Learning theory and algorithms / Sample complexity
Linear Lower Bounds and Conditioning of Differentiable Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Include the minimum coupling spectral bound μ12 in the condition number | Domino lower bound for two-player games · Two-player games, including bilinear games | condition-number expressivity | Helped |
| Generalize p-SCLI to games with nonsymmetric Jacobians | p-SCLI-n lower-bound framework · n-player quadratic games | coverage of game settings | Helped |
| Use the improved domino bound | Two-player games with block spectral bounds · Two-player games | condition-number information | Helped |
| Use the p-SCLI-2 framework rather than the improved domino bound | 2-SCLI-2 methods satisfying the two-step linear span assumption · Two-player games | rate lower bound | Mixed |
Closest papers by meaning
- Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.89)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.88)
- Solving Zero-Sum Convex Markov Games (ICML 2025 · similarity 0.87)
- Thresholds for sensitive optimality and Blackwell optimality in stochastic games (NeurIPS 2025 · similarity 0.87)
- Expected Variational Inequalities (ICML 2025 · similarity 0.87)
- Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.