Research map / Learning theory and algorithms / Matrix and tensor methods
Variance Reduction for Matrix 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 |
|---|---|---|---|
| Use difference-based sampling in the variance-reduced primal-dual method | ℓ1-ℓ1 bilinear games · ℓ1-ℓ1 bilinear games | runtime: \Otil{\textup{nnz}(A) \cdot L \cdot \epsilon^{-1}} -> O\left(\textup{nnz}(A) + \frac{\sqrt{\textup{nnz}(A) (m + n)} \nor | Helped |
| Use difference-based variance reduction instead of the stochastic sublinear-time method | ℓ1-ℓ1 bilinear games · ℓ1-ℓ1 bilinear games | runtime: \Otil{(m + n) \cdot L^2 \cdot \epsilon^{-2}} -> O\left(\textup{nnz}(A) + \frac{\sqrt{\textup{nnz}(A) (m + n)} \norm{A}_{ | Helped |
| Use clipped difference-based sampling with local-norm analysis rather than the basic estimator (ablation) | ℓ2-ℓ1 bilinear games · ℓ2-ℓ1 bilinear games | centered estimator constant L: \sqrt{\sum_{j\in[n]}\|\aj\|^2_\infty} -> \norm{A}_{2\rightarrow\infty} | Helped |
| Clip the gradient estimate (ablation) | ℓ2-ℓ1 variance-reduced method · ℓ2-ℓ1 bilinear games | gradient-estimator boundedness | Helped |
| Use squared-difference sampling for both blocks | ℓ2-ℓ2 bilinear games · ℓ2-ℓ2 bilinear games | runtime | Mixed |
Closest papers by meaning
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.83)
- Efficient $\Phi$-Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games (NeurIPS 2024 · similarity 0.82)
- Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.82)
- Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.82)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · similarity 0.81)
- Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games (NeurIPS 2025 · similarity 0.81)
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.