mlsanityData to 14 Oct 2026

Optimistic Online Learning in Symmetric Cone Games

arXiv 2504.03592 ↗First posted 4 Apr 2025math.OC cs.GT cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We introduce symmetric cone games (SCGs), a broad class of multi-player games where each player's strategy lies in a generalized simplex (the trace-one slice of a symmetric cone). This framework unifies a wide spectrum of settings, including normal-form games (simplex strategies), quantum games (density matrices), and continuous games with ball-constrained strategies. It also captures several structured machine learning and optimization problems, such as distance metric learning and Fermat-Weber facility location, as two-player zero-sum SCGs. To compute approximate Nash equilibria in two-player zero-sum SCGs, we propose a single online learning algorithm: Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU). Unlike prior methods tailored to specific geometries, OSCMWU provides closed-form updates over any symmetric cone and achieves a tildeO(1/ε) iteration complexity for computing ε-saddle points. Our analysis builds on the Optimistic Follow-the-Regularized-Leader framework and hinges on a key technical contribution: We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm. This result extends known results for the simplex and spectraplex to all symmetric cones, and may be of independent interest.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 71 references that are in the map. First posted on arXiv 4 Apr 2025.

Builds on

23 of 71 references.

References · 23

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  2. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  4. 2018Quantum generative adversarial networkscited by 128
  5. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  6. 2019Scalable Semidefinite Programmingcited by 36
  7. 2019Quantum Wasserstein Generative Adversarial Networkscited by 33
  8. 2022Near-Optimal No-Regret Learning Dynamics for General Convex Gamescited by 25
  9. 2022A unified stochastic approximation framework for learning in gamescited by 23
  10. 2021Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Updatecited by 20
  11. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  12. 2015Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updatescited by 14
11 more
  1. 2022Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrencecited by 6
  2. 2023No-Regret Learning and Equilibrium Computation in Quantum Gamescited by 5
  3. 2023A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Gamescited by 4
  4. 2023Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizationscited by 3
  5. 2019A Rank-1 Sketch for Matrix Multiplicative Weightscited by 2
  6. 2024A Primal-Dual Framework for Symmetric Cone Programmingcited by 2
  7. 2018A First-order Method for Monotone Stochastic Variational Inequalities on Semidefinite Matrix Spacescited by 1
  8. 2021Convergence Rate Analysis of the Multiplicative Gradient Method for PET-Type Problemscited by 1
  9. 2023Multiplicative Updates for Online Convex Optimization over Symmetric Conescited by 1
  10. 2024Approximation Algorithms for Smallest Intersecting Ballscited by 1
  11. 2024Fixed-budget and Multiple-issue Quadratic Votingcited by 1

Built on by

Not cited yet.