Optimistic Online Learning in Symmetric Cone Games

Weinberger and Saul [2009]), adversarial training of quantum generative models [Dallaire-Demers and Killoran, 2018, Chakrabarti et al., 2019], and facility location optimization [Brimberg, 1995, Xue and Ye, 1997] may seem unrelated at first glance. Yet, all of them can be formulated as two-player zero-sum games where each player optimizes over a structured, convex strategy space. These strategy spaces take a diversity of forms--probability simplices, trace-one positive semidefinite (PSD) matrices, and Euclidean balls--reflecting different algebraic or geometric constraints. While this shared structure suggests the potential for unified solution methods, existing algorithms remain highly fragmented, often tailored to specific geometries in special structured problems. For instance, distance metric learning can be solved using the Frank-Wolfe algorithm [Ying and Li, 2012] or Nesterov's smoothing algorithm [Nesterov, 2007]; quantum zero-sum games can be tackled using the Matrix Multiplicative Weights Update algorithm [Jain and Watrous, 2009, Jain et al., 2022]; the celebrated Fermat-Weber facility location problem can be solved using interior point methods [Xue and Ye, 1997]. This fragmented landscape of algorithms and analyses calls for the design of broadly applicable algorithms for equilibrium learning in structured games.