Optimistic Online Learning in Symmetric Cone Games
Authors: Anas Barakat
Wayne Lin
John Lazarsfeld
Antonios Varvitsiotis
Venue: Accepted by TMLR ()

Abstract: 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, projection-free updates over any symmetric cone and achieves a $\tilde{\mathcal{O}}(1/\epsilon)$ iteration complexity for computing $\epsilon$-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.

Published in Transactions on Machine Learning Research (03/2026)
Optimistic Online Learning in Symmetric Cone Games
Anas Barakat
Singapore University of Technology and Design
Wayne Lin
wayne woyne_linntBeeeeeeeeeeee lin.@suud.edu..
Singapore University of Technology and Design
John Lazarsfeld
john lazarsfeld@sutld.ccll edu.
Singapore University of Technology and Design
Antonios Varvitsiotis
antonios@sutld.ede
Singapore University of Technology and Design
Centre for Quantum Technologies, National University of Singapore Archimedes/ Athena Research Center
Reviewed on OpenReview: https: // openreview. net/ forum? id- RQjuE20306
Abstract
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 symmetric cone). This framework unifies wide spectrum of settings, including normal-form games (simplex strategios), 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 Up- dates (OSCMWU). Unlike prior methods tailored to specific geomet.ries, OSCMWU provides closed-form updates over any symmetric cone and achieves ((1/e) iteration complexity for computing e-saddle points. Our analysis builds the Optimistic Follow-tho- Reglav-hi--eggllrzzzdd Leader framework and hinges on 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.
1 Introduction
Problems such as distance metric learning (e.g. Weinberger & Saul (2009)), adversarial training of quan- tum generative models (Dallaire- DDallarr-Demmers & Killoran, 2018; Chakrabarti et al., 2019), and facility location optimization (Brimberg, 1995; Xue & 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 geometric constraints.
While this shared structure suggests the potential for unified solution methods, existing algorithms remain highly fragmented, oflen tailored to specific geometries in special structured problems. For instance, distance metric learning can be solved using the Frank- Wolfe algorithm (Ying Li, 2012) or Nesterov's smoothing algorithm (Nesterov, 2007); quantum zero-sum games can be tackled using the Matrix Multiplicative Woights Update algorithm (Jain & Watrous, 2009: Jain et al., 2022); the celebrated Fermat- Weber facility location problem can be solved using interior point methods (Xue & Ye, 1997). This fragmented landscape of

---

Published in Transactions on Machine Learning Research (03/2026)
algorithms and analyses calls for the design of broadly applicable algorithms for equilibrium learning in structured games.
In this work, we present a unified algorithmic framework for equilibriu learning in such problems by introducing a rich and expressive class of games we call Symmetric Cone Games (SCGs). In SCGs, each player's strategy set a generalized simplex- the set of trace-one elements symmetric cone, i.e., the cone of squares of Euclidean Jordan Algebra (EJA). This abstraction includes many familiar structures including the simplex (trace-one slice of the nonnegative orthant), the spectraplex (tracc-one slice of the PSD cone), the second-order cone (trace-one e ball), and products of these cones. As consequence, Symmetric Cone Games notably generalize several well-known classes: Normal-form games, where strategies lic in simplices; Quantum games, where strategies are density matrices (PSD, trace-one); continuous games with Euclidean geometry structure where strategies live in e balls or second-order cones.
While we define SCGs in the general multi-player sctting, we focus on the foundational case of two-player zero-sum SCGs, which unily and extend a variely of structured optimization problems in machine learning and game theory. Concretely, we study the following min-max problem:
min max f(r,y), sEdx, DEAR,
(1)
where Aki, Ax, are generalized simplices over symmetric cones K1, KC₂ respectivcly, and f is convex-concave. This general formulation accommodates rich structured domains such PSD cones (spectral information), second-order cones (geometric norms), and their products. We illustrate this generality through concrete applications including distance metric learning (as simplex spectraplex game), facility location (as a second- order cone game).
To solve such problems, we introduce a new online first-order learning algorithm-Optimite Optimistic Symmetric Cone Multiplicative Weights Update (OSCMWU) for computing approximate saddle points in SCGs. This closed-form update method operates over any symmetric cone, does not require a Euclidean projection onto the symmetric cone and can be run online and independently by each player. OSCMWU recovers the Optimistic Multiplicative Weights Update (OMWU) algorithm for simplex games (Syrgkanis et al., 2015) and its matrix variants for spectraplex domains (Vasconcelos el al., 2023) as particular cases. In two-player SCGs, the algorithm achieves O(1/E) iteration complexity for reaching an E-saddle point, improving over the prior (11/²)) bound for vanilla SCMWU (Canyakmaz et al., 2023). Conceptually, OSCMWU is an (OFTRL) with a cone-specific entropy regularizer. A
instance of Optimistic key technical ingredient in our analysis is the following strong convexity result: We prove that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm. This generalizes known results for the simplex and spectraplex to arbitrary symmetric concs, leveraging the algebraic structure of Euclidean Jordan algebras (Faraut & Korányi, 1994). We believe this result and its proof, based on a novel data processing inequality, may be of independent interest to the learning and optimization communities.
We illustrate the versatility of our framework by applying OSCMWU two representative SCGs, showcasing its generality, simplicity, and robust convergence across different cone geometries.
In summary, our main contributions are follows:
A unifying class of structured convex games. We introduce Symmetric Cone Games (SCGs), a general class that subsumes numerous existing settings under a single abstraction, including normal-form, quantum, and continuous games with Euclidean ball strategy spaces.
An online lcarning algorithm. We propose OSCMWU, an optimistic algorithm that operates over any symmetric cone and can be run independently by each player in an SCG. The method yields closed- form updates via the exponential map and is well-suited for streaming, adversarial, or interactive learning scenarios modern machine learning. In two-player SCGs, OSCMWU guarantees a (11/e) iteration com- plexity to reach an e-saddle point. This result improves over the O(1/e²) result established in Canyakmaz et. al. (2023).
2

---

Published in Transactions on Machine Learning Research (03/2026)
A strong convexity result. We establish that the symmetric cone negative entropy is strongly convex with respect to the trace-one norm. This generalizes classical results for the simplex and spectraplex to all symmetric cones and plays a key role in the regret analysis of our method.
Applications. We apply OSCMWU to solve SCGs arising in structured prediction (distance metric learning), spatial optimization problems (facility location), and hybrid cone optimization, demonstrating the versatility of our unified framework beyond classical game settings.
Our theoretical results point toward broader unification of structured ouline game-theoretic learning meth- ods and their application to diverse domains. Proofs and extended related work are deferred to the appendix.
2 Preliminaries: Euclidean Jordan Algebras, Symmetric Cones, and Entropy
In this section, we introduce our notations and define symmetric cones. We rely on the formalism of Euclidean Jordan algebras that we briefly review. We refer the reader to Appendix B for additional background and examples, and Faraut & Korányi (1994) for a more detailed exposition.
(Euclidean) Jordan algebras. Let. J be a finite dimensional vector space equipped with a bilinear product o J J J. The pair (J,o) forms a Jordan algebra if for all x, y J, y = y o and 2² a (x x (x2 yy) where x² = Fo.. x. We assume throughout this paper that the Jordan algebra (J.o) (simply denoted by J) has an identily element, iee. there exists E J s.l. cox = roe = x for every x E J. A Jordan algebra over IR is said to be Euclidean if it is equipped with an associative inner product (:-), i.c. for all x, N. E J. (x o 2) = (v, o z). Throughout this work, we will simply denote a Euclidean Jordan algebra (EJA in short) (J, o, (c) J.
Symmetric concs. A cone K. in an inner product space is said to be symmetric if is self-dual and homogeneous. Notably, any symmetric cone is the cone of squares {x o x E J] of some EJA J (see Faraut & Korányi (1994) Theorem III.3.1) Table 2 in Appendix B.3 summarizes some relevant examples.
Jordan frames and spectral decomposition. An clement p E I s.t. pop p is called an idempotent in J. It is a primilive idempotent if it is nonzero and cannot be written as a sum of two nonzero idempotents. A Jordan frame is a finite set (qI....,hh gr) of primitive idempotents in J s.t. qi o = 0 if i + j and Σ q: = e where e is the unit element of J and r is the rank of the EJA, see Appendix B.2. If J is an EJA with rank r, then for every E J, there exists a Jordan frame (q1.-.. ........grr .9) and AI.... Ar E R s.t. E degi- The scalars (Ai)sses are called the eigenvalues of x, and are uniquely determined up to multiplicities. (See e.g. Faraut & Korányi (1994) Theorem 111.1.2 for this so-called type-ll spectral decomposition.) This decomposition generalizes the usual spectral decomposition of Hermitian matrix into rank-one projectors.
Trace, inner product, dual norms, trace p-norms. The trace map tr : J + R is equal to the sum of eigenvalues, Lee, tr(x) = Σx= Aj for every x E J. The bilinear mapping (x, + tr(x y) is positive definite, symmetric and associative (see e.g. Faraut & Korányi (1994), Prop. III.4.1). We use the notation (x, v) tr(x e y) for this canonical inner product. If E is a finiteddimensional real space, we denote its dual by Ex and we will write (y.x) for the pairing between E E and y E E*, For any given norm || | defined on the space E, we use the standard definition of the dual norm || I 1|- for every u E E* by ||~||- = suppul|sz (u, v) where (. is the previously defined pairing, Finally, for any æ E J, its trace norm is defined by ||=llep = E [x) when 0 < and || maxigigr [Mx(z)) (A())) when p == co, where (A(()))sisr> are the eigenvalues of ar The trace-p norms were first introduced and proven to be norms for all p E [1, oo] by Tao et al. (2014), and Gowda (2019) proved that the trace-p and trace-q norms are dual to each other for all p.g E [1, oo] satisfying + =.
Symmetric cone negative entropy. Given the EJA J and its cone of squares K. the negative entropy mapping Lent int(KC) + IR is defined for every x int(K) by:
Pent = tr(x o lnx) = Σ A In de:
(SCNE)
3

---

Published in Transactions on Machine Learning Research (03/2026)
where Ei=1 drg; int(KC) is the spectral decomposition of and In int(K) J is the Löwner extension of the scalar logarithm function defined by In = -Ei= In(As) for any x E int(XC). Note that the last expression is well defined since X; > 0 for every Sirr as E int(K).. Similarly, the exponential mapping exp: J + int(K)) defined by exp(x) = (xp(A)) q:
3 Symmetric Cone Games
Symmetric cone games (SCGs) are multi-player games in which each player selects strategies from a gen- eralized simplex, defined as the trace-one slice of symmetric cone. This structure captures broad class of structured learning and optimization and convex programs over cones under a unified theoretical framework. Formally, if (J,o) is an EJA of rank r and IC its cone of squares, we define the generalized simplex:
classical and quantum games, metric learning,
DK {a K. tr(x) = 1}.
(2)
i.c. the trace-one slice of K. Note that Ax is convex compact set. Table illustrates how SCGs subsume well-known domains including normal-form games, quantum games, and games with Euclidean geometry.
Table 1: Examples of Generalized simplices
Symmetric Cone IC
Generalized Simplex Ac
Nonnegative orthant RR
Simplex
A {i E R E.= 2 =1]
Real PSD symmetric matrices S"
Spectraplex
Ag = {X E S Tr(X) 1}
PSD Hermitian matrices H.
Spectraplex
A (X H (r(X) 1}
Sccond-order cone L
Ball?
ALg = 2)
||0||| S 1
This spectraplex is the set of density matrices and is commonly used in quantum computation and quantum games, e.g. Gutoski Watrous (2007); Jain & Watrous (2009). 2 We call
ball here with slight abuse since it is the set of ($) and not only
We consider a game setting with a finite number of players N == (1,... a strategy x; from a generalized simplex Ax, associated to a symmetric cone KG (which is a closed convex subset of dinite-dimensional EJA J.). We denote the space of all joint strategies by := IheN Ak. S J == ILEN J.. We recall the standard notation payoff (or utility, reward) function u, X + E which will be assumed to be concave and differentiable' w.r.t. its ith variable. Under this assumption, we introduce the payoff vector as follows: Vo E X, m(x) (m;(z))ieN mz(x)= = Vz, (4(2,,,_)); vi N.
Fach player E N selects
(r2) for any joint strategy x E X' Each player i W has
At each time step f, cach player i E N observes their payoff vector m = m,(x') where xf E X is the joint strategy the players. Then player receives the payoff uz(x*) and computes their next strategy at Ax,-
The playerwise regret associated to sequence (xf) of player i's strategies after T steps is given by:
Ti (T) sup Σ (x( - aL), VieN. zEAx, t=1
(3)
We assume that cach player's payoff vector Lipschitz- under the trace norm.
Assumption 1. Vz,y V N, 0, (x)))=x==- m.(yy)lur,o L111 yllu..
This smoothness assumption on the payoff vectors is common in the literature, see e.g. Farina et al. (2022a); Mertikopoulos et al. (2024) (Assumption 1). Notably, we observe that if the game multilincar and the abso- lute value of the utility wxxx) is bounded by Li, then Assumption holds (see Proposition 23 in Appendix F). In the next section, we discuss further examples of SCGs where Assumption 1 is satisfied.
For differentiabllity, the utility functions can seen to defined over the FJA. J. which is an open set.
4

---

Published in Transactions on Machine Learning Research (03/2026)
3.1 Examples of SCGs
We now discuss examples that illustrate how SCGs instantiate key classes of games.
Example 1 (Finite normal-form games). Each player E V selects an action from a finite set A, and their payoff' function in : A + R is defined over the product space A == IheN A. Each player may choose actions randomly according to a probability distribution x; = (araa E A(A,) where A(A,) is the simplex. The payoff functions are extended as multilinear functions u, : ILL ((A)) - R defined by (a1,"'.,,,) Note that in this setting mx(x) = (x) = (u: (u=(a,,=i))aE where u,(a,,=i)) := En iEA _ "al,u,
(x(x:) A (a))(a) where Za = Ilew Fi,a; is the probability of the joint action
and A-t == II Ag. Assumption 1 is satisfied for bounded payoff functions (see e.g. the proof of Theorem 4 in Syrgkanis et al. (2015)).
Example 2 (Convex games with ball strategy sets). Consider the second-order (Lorentz) cone L = {x x) E R x R=-1; | S z1}. The associated generalized simplex (see Table 1) is the affine slice Aug = {(2 8) E R² : | S 2 1] which is (via projection onto ž) affinely isomorphic to the Euclidean ' ball {T E R=-1 1512 S 4)- A convex game with l2 ball constraints is then specified by strategy sets X; Au; and payoff functions u, X == I1, X3 + R that are concave in I; for each fixed z-1 and continuously differentiable on X' (see, e.g., Rosen (1965) for concave games). We provide two concrete examples of games with Euclidean lz ball strategy sets: (a) Fixed-budget vote allocation in social choice, where an agent allocates a vote vector 22 E R4 subject to a quadratic budget constraint || < B, (see, e.g., Goorgescu et al. (2024)); (b) Beamforming in wireless communications, where each transmitter chooses a beamforming vector 2, under a power constraint ||>: S P, (see, e.g., Larsson & Jorswieck (2008, section III).. More generally, Euclidean balls are canonical compact convex strategy sets, a standard assumption in convex game theory; see, e.g., Facchinei & Kanzow (2010).
Example 3 (PSD matrix games). In this case, each player controls PSD matrix variable (e.g. a signal covariance matrix) and each strategy space is the set of trace-one PSD matrices (Asz). These matrix games find applications in wireless communication networks for the competitive maximization of mutual information in interfering networks (Arslan et al., 2007; Scutari et al., 2008; Mertikopoulos & Moustakas, 2015; Majlesinasab el. al., 2019).
Example (Quantum games). The strategies of the players are quantum states represented by density matrices, i.. elements of the spectraplex Agg. and the utility is given by the expected value of a measurement on the joint state, i.e., the inner product of Hermitian observable with an element in the tensor product space. If the players are playing separately, their joint state is a product state, and the utility function is multilinear in each player's individual strategy space. We refer the reader to Gutoski & Watrous (2007); Jain & Watrous (2009); Vasconcelos et al. (2023); Lin et al. (2024).
3.2 Representative Applications of SCGs
We now illustrate how diverse problems across machine learning and optimization fit naturally within our framework of SCGs. Each of the following examples is a convex-concave min-max game over generalized simplices derived from symmetric cones.
Application 1: Distance Metric Learning via Spectraplex Games. Distance metric learning aims to learn a Mahalanobis distance that pulls similar examples closer while pushing dissimilar ones apart. Consider dataset {atlissNn where 2, E Rd. For any pair (i.z), we define the matrix X1, == (z, 21) - x,y"² E Rdxd. The Mahalanobis distance induced by any PST) matrix M E Sd is defined by da == (I; 2TyTT 22) (Xi,,M for any pair (y), Denote by S and D the index sets of similar and dissimilar pairs respectively, i.e. (i,j) E S if (Iz,²;) is a pair of similar data points. Ying & Li (2012) propose to maximize the minimal squared distances between dissimilar pairs while controlling the
We the same notation u; the previous section with slight abuse of notation, to consistent with the standard payoff notation for normal I- form games in game theory.
5

---

Published in Transactions on Machine Learning Research (03/2026)
sum of squared distances between similar pairs:
max
min (X,, M)
Me31
TED
(4)
s.t.
(Ks, M) 1
where Xs == ==E X1 E 8 Using duality, this problem is shown in Ying & Li (2012) (Theorem 1) to be equivalent to the convex concave saddle-poois point problem:
Σ Eatt,, x) ,x;= 1/112xx0 ,xx:=x5'/2 xx/22xX5112 WED
min max READ 1 LYEA!
(5)
the matrix Xs is supposed to be invertible, - = {uERD, : 20, ErED", = [D] is the number of pairs. This is SCG over simplex and a spectraplex. More broadly, in cimplex-spectrapee games player plays a probability simplex vector x and player 2 plays a real symmetric, trace-1, PSD matrix Y, giving rise to the (bi-affine) min-max game:
min max f(z,Y) (Y, ({x)( + (6,z) (C,Y), #EA YEAg!
(6)
where A: : R + 3d is the linear map given by A(x) Σx= 2;A, for some A e 3d. Problem (6) captures wide range of problems including some constant trace semi-defiitte programming problems and maximum eigenvalue minimization problems.
The sum-of- norms problem, also known as the Fermat Fermat-Weber location problem, arises in transportation, logistics, and communications (see e.g. Brimberg (1995); Xue & Ye (1997) and the references therein). It seeks to minimize the sum of Euclidean distances (or residual norms) to given targets. Its general form is:
Application 2: Facility Location Optimization via Second-Order Cone Games.
min g(x) = Σ sEC
| Are Balla
1=1
where = fo E Rd ||ا|| E (1, 1.. ( .P), A, E Rmxd by E T
s R) 1l2 is the standard Euclidean norm of Rd and for all
We now reformulate problem (7) min-max problem involving second-order cone decision variables. We introduce a few useful notations. Define A, == (0, A E I))+1)xd and b, := (0, b7) E Rm=+ Now, recall that for any (s, z) e 1d11, the two eigenvalues x are |=||=||e 2 and the largest eigenvalue is therefore s+ || Now, using this fact together with the variational characterization of the maximal eigenvalue we can write,
by further introducing Ā := (Af, .., AT)) and b. = (bT ... ..)))) E TP, the objective function as
T
P
g(x) = Σ
Amax (A,x b,) = max (v. Ar b) yEAR
(8)
where J= dd+l and Jo the product EJA. We now observe that C equivalent (1/2,z/22)) e 44 (11/2,z)) Rd+1, || S 1/2) Combining this with (8) and using the change of variable ā (2R) we obtain that problem (7) is equivalent to:
min x= (1/2,8)EA atL WE
max f(ā,y),
(9)
Ang
where f(x,y) y) :=
(b,9) A 2R(0 A). This min-max formulation fits directly within the SCG framework, where both player strategy sets are generalized simplices derived from sccond-order cones.
II other words, Amax is the support function of the generalized simplex, here: Amax(1) max (v.
Recall here that Ang is the trace-one slice of the second-order cone L tr((t, x)) 2 for any (t)z) E I.
6

---

Published in Transactions on Machine Learning Research (03/2026)
4 Optimistic Symmetric Cone Multiplicative Weights Updates
In this section, we present our Optimistic Symmetric Cone Multiplicative Weights Update (OSCMWU) algorithm. The iterates of this algorithm evolve in a generalized simplex. We aim for a single algorithm that applies uniformly across all symmetric cone domains (e.g,, simplices, spectraplexes, 12-balls, etc.), avoiding projections and offering closed-form updates via the exponential map. To our knowledge, no such general- purpose algorithm has been proposed before. First we describe the online convex optimization (OCO) setting to set the stage (see e-g. Shalev-Shwartz (2012)).
Online symmetric cone optimization. At each time step t, decision maker chooses an element of the generalized simplex Ax. i.c. a trace-one element x' of a symmetric cone K. and receives payoff f*xx" where / Ax + R is a concave differentiable gain function. 5 The decision maker then receives as feedback the vector m' == (x'). Note that m' E EJ = J, where J is K'ss associated EJA. This setting has been recently considered in Canyakmaz et al. (2023) in the particular case of linear payoffs, i.e where the payoff function ft is linear: for all t 2 0. (x²') = (m' xx²) where m' E J is the observed payoff vector.
Optimistic Follow The Regularized Leader. In view of our analysis, we will present our optimistic mul- tiplicative updale algorithm as an instance of the general framework of Optimistic Rollow-The- Meallo--Th--egulariiinn Regularizedd Leader (OFTRL) in online learning. Consider any strongly convex regularizer & int((C) + R. As introduced and studied in e.g. Rakhlin & Sridharan (2013a;b); Syrgkanis et al. (2015), (OFTRL) with step size n > 0 can be written as follows over the generalized simplex Ac with x argmin ((x) and for all t 2 0, zEdx
(
x. 1+
-arggax
Σ m* -m+t,a , ,2/
-0())
(OFTRL)
dEAR
where (m') is a prodictor sequence, typically m++1= = m². Note that setting m = 0 in (OFTRI) results in the celebrated FTRL algorithm.
regularizer (Ø = Dent) as defined in (SCNE), obtain our algorithm. The algorithm updates sequence of weights (w") accumulating the payoff vectors with an additional optimistic term which is given by the adaplive predictor sequence (mt). SCNE yields closed-form updates via the EJA exponential and trace normalization to map weights into the generalized simplex.
Using SCNE
Optimistic Symmetric Cone Multiplicative Weights Updates
w11 = 17 Σ Emt + m ) attl= (r(exp(w(t1))
exp(w*+1)
(OSCMWU)
for all t 2 1, where (m²) is a predictor sequence, typically m ml.
The particular case where m = 0 corresponds to the SCMWU algorithm studied in Canyakmaz et al. (2023). When K= = S variants of our optimistic algorithm with matrix updates have been recently intro- duced and ana analyzed in Vasconcelos et al. (2023) for quantum zero-sum games.
Remark 2. While the terminology of "maltiplicative weights' is clearly justified for the standard simplex, it is less relevant in our more general setting because the exponential of a sum of EJA elements not equal the producl of the eaponentials in general. Therefore the exponential in the update of the decision variable r0t1 cannot be split. Nevertheless, we stick to this terminology as (a) it has already been used for the particular case of the matriz multiplicative weight algorithum and (b) it highlights the link between our general algorithm and its popular particular case instances.
Remark 3. (Exponential computation) Depending the cone, the eoponential map can be made explicil in closed form and computed (or approzimated). For instance, this computation is straightforward for the case of the nonnegative orthant and the second-order cone whereas it is a more expensive operation for the PSD cone. We provide a detailed discussion in Appendiz B.4, In the PSD case, our algoritim could also
We adopt here the (concave) utility maximization convention like in games rather than the (convex) loss one OCO.
7

---

Published in Transactions on Machine Learning Research (03/2026)
be enhanced by using randomization techniques used for matrix multiplicative weights algorithms for solving large semidefinile programs (Baes et al., 2013; Curmon et al,, 2019; Yurtsever et al., 2021), we leave this for future work.
Proposition 4. For any symmetric cone K,, the iterates of (OSCMWU) coincide with the iterates of (OFTRL) with the symmetric cone negative entropy regularizer ( = 4 Pent).
5 Regret Analysis and Average Iterate Convergence Guarantees
5.1 Individual Regret Bound and Strong Convexity of Symmetric Cone Negative Entropy
The iterates of (OFTRL) satisty the so-called regret bounded by variation in utilities (RVU) property introduced in Syrgkanis et al. (2015).
Proposition 5. The sequence (x') generated by (OFTRL) with m m' Ax for all t and regularizer & that is I-strongly conver w.r.t. norm || satisfies for any T 2 1, for any AK.
T
R + Σ ml m 112 ((0)
T
-
x
112
1
4n
where R SUPZEAR (xx) inf inf ((x), -1- is the dual norm and (:--) the EJA inner producl.
Remark 6. The constant R in the regret bound of Proposition 5 implicitly captures the performance depen- dence on the complexity of the decision space Ax. When the regularizer & is the negative symmetric cone entropy ( = 2 een)), note that R S. Inr where r is the rank of the EJA. In particular, when K. = E or St or H = n. When K. = = (second-order cone), r = 2. Notably, the dependence of the regrel on the complerity of the decision space is logarithmic.
Application to (OSCMWU). Our goal now is to obtain the regret bound of Proposition for our (OSCMWU) algorithm. Recall now from Proposition that (OSCMWU) can be seen as an (OFTRL) algorithm using the SCNE regularizer Pent. Therefore, our main challenge to obtain to establish the strong convexity of the SCNE w.r.t. the trace-1 norm. This is one of our key contributions which requires many technical developments relying heavily on the theory of EJAs The symmetric cone negative entropy is 1-strongly convex w.r.t. the trace-1 norm on the interior of the generalized simplex.
regret guarantee is
Theorem 7. (Strong converity of the symmetric cone negative entropy). Let (J,o) be an EJA and let K. be its cone of squares. Then for all x, y E int(Ax)) De (z.y) y) 2 -1ll - yllir.1 where we recall that Pent is the symmetric cone negative entropy, i.e. Pen((x) = tr(x in x)) for all E int(IC), and De the Bregman divergence (x, tr(x l x lny + y y-x)) x).
We contribute new proof which relies on using data processing inequality for the specific case of diagonal mapping" in general EJAs followed by application ion of Pinsker's inequality (see Eq. (19) in Appendix C.3 for the core step of the proof). We prove in particular that the diagonal mapping can be written as a convex combination of EJA automorphisms and we combine this result with the known joint convexity of the relative entropy for EJAs (Faybusovich, 2016) to obtain the desired inequality. We defer the complete proof to Appendix C.3. An alternative proof for strong convexity can rely on the celebrated duality between strong convexity and strong smoothness (w.r.t. arbitrary norms) which is used to lower bound the Hessian of the negative entropy, corollary 6.4.5 19292 in Baes (2006) leading to the same strong convexity constant (equal to 1) as in Theorem 7.
Remark 8. Theorem 7 recovers special cases the strong converily of the negative entropy w.r.t. the one norm for the probability simplex and the trace one slice of PSD cones in the optimization (see e.g. Proposition 5.1 in Beck & Teboulle (2003)) and (quantum) information theory literatures (see e.g. Yu (2013)).
Remark 9. Chen & Pan (2010, Lemma 3.2.c) shows that the SCNE is strictly convex on the symmetric cone (see also Canyakmaz al. (2023, Lemma 2.1 (ū))). We show that the SCNE strongly conver with respect to the trace norm, which is a stronger result.
6See appendix for more details the Bregman divergence.
7his is the mapping associating to symmetric matrix its diagonal the EJA symmetric matrices.
8

---

Published in Transactions on Machine Learning Research (03/2026)
5.2 Sum of Regrets Bound in Symmetric Cone Games
In this section we leverage our strong convexity result for the SCNE (Theorem 7) to provide regret guarantees in SCGs. We start by deriving a constant bound on the sum of regrets of players using (OSCMWU) and the OFTRL framework. Then, we focus on two-player zcro-sum SCGs to solve our min-max problem (1) and find an approximate saddle point using the regret guarantees.
If each player runs (OSCMWU), then the sum of regrets of all players is bounded by a constant. The analysis relies on using the RVU bound in Proposition Using Assumption 1, we follow the analysis of Syrgkanis et al. (2015) which is valid for any (OFTRL) algorithm with strongly convex regularizer w.r.t. any norm (when all players run the same algorithm) to obtain the following result.
Theorem 10. Let Assumption 1 hold and let each player i E N runs (OSCMWU) for T rounds on their strategy space Dx, with a fixed positive stepsize 17 = 1/ N EN L?) and set ||- = 11- Then the sum N 1= Ro) N == 17, where ri(T) is the i-th player's 's individual regrel defined in (3) and R2 = SuP ((x) infxEAr, ((x).
of regrets is bounded as: ra)))((T) S 2
2E
5.3 Application to Two- Player Zero-Sum Symmetric Cone Games We consider now the min-max problem:
min max f(z, y)
(10)
=EDx, WEAK2
where Ti x J22 -> IR is convex-coneave and differentiable, K2 are arbitrary symmetric cones and Axy Ax, their associated generalized simplices.
We employ well-known results in the online learning literature to obtain an approximate saddle point for the min-max problem using two uncoupled online learning players (sce c.g. section 5 in Fround & Schapire (1999), sections 7.1-3 in Cesa-Bianchi & Lugosi (2006) and sections 11.1-2 in Orabona (2019)) and the regret guarantees of Theorem 10. Specifically, we use the link between the sum of individual players' regrets, the so-called duality gap in min-max problems, and the suboptimality gaps for each one of the dual min-max and max-min problems. For the convenience of the reader, record the result use in Theorem 20 in Appendix D.2 and provide complete proof. Note that this result (Theorem 20) is independent from any specific algorithm used and applies to generalized simplices.
We combine this result (Theorem 20) with our regret guarantees obtained in Theorem 10 for (OSCMWU) to solve our saddle point problem (10) of interest for which the generalized min-max theorem holds. To state our result, we respectively define the duality gap d(z. 9) and the suboptimality gaps d, dz)), dz( for the min and max dual problems for any (z,7)= Ax, Ax2 as follows:
d(z. D) == max f(2, y) min f(x, yEAK,
(11)
zEAx
di dz( max f(z. v) - - dz(()) =- min ae
f(x, V),
(12)
yEAK2
where o² is the min-max value of the zero-sum game, i.e. max minzeAK, f(x. y).
min maxy6ax, f(x,)) w)
Theorem 11. Consider a two--payer symmelric cone game selling (N = =2 and assume that the game is zero-sum (ug = -u1 = =f). Let Assumption 1 hold and suppose that both players run (OSCMWU) with stepsize =
L3)) for T (0ars+tnraa//21322)) rounds where e > 0 is any desired accuracy
and r; ran, = 1,2. Then the average iterate sequences (īr), (Tr) defined by ie = + + x' Ür I E salisfy for T 2 1, 0 & d(ōr, .T) S e, S (āT) Se and 0 S dz(ūT) Se. Moreover (TT.ūr) is an e-saddle point of the min-mar problem (10), i.e. for all (x,y) E Ak, x AK,, f(ār.V) - E S f(iT, VT) S f(x, +e. (x..
T
Theey need not be the same for all players, see the consequence on the regret with the dependence on Rd.
9

---

Published in Transactions on Machine Learning Research (03/2026)
The dependence the complexity of the strategy spaces is logarithmic in the rank of the underlying EJAs (see remark 6). Theorem 11 improves over the ((1/s²) iteration complexity that can be achieved using the SCMWU algorithm proposed by Canyakmaz et al. (2023). Our analysis deviates from the SCMWU regret analysis developed in Canyakmaz et al. (2023). In particular, we leverage our general SCG sctting, rely on the OFTRL framework and the strong convexity of SCNE to establish our result.. In the special case where K. = K2 = H4, a similar improvement has been established for quantum zero-sum games Vasconcelos et al. (2023) using different optimistic mirror-prox like analysis (Nemirovski, 2004) via variational inequality perspective and several variants of optimistic matrix updates.
6 Applications to Min-Max Problems: Metric Learning and Facility Location
In this section, we discuss how to use our unified methodology, our optimistic online algorithm (OSCMWU) and its resulting iteration complexity in the two special min-max applications discussed earlier. Unlike prior work that designs domain-specific solvers, we use the same (OSCMWU) algorithm in all cases. To our knowledge, OSCMWU is the first optimistic algorithm applicable across all symmetric cones SCGs.
6.1 Simplex-Spectrapler Games (e.g. Metric Learning)
Iteration complexity of (OSCMWU). In the game (6), given that x, Y are played, the players re- spectively observe the gain vectors my mz Y) = -v,f(r, Y) = (Y) - b = A()); b, and m2(x, Y) = f Y) = A(x) +C E, A4A; + C where here A"" denotes the adjoint operator of A. We have L1 L2 max; Ailler.o and R ln m, R₂ In Thus, by Theorem 11, to obtain an e-saddle point of the min-max problem it suffices for both players to run (OSCMWU) with stepsize 17 1/(2 max, || (r,)) for T>
1(lu mllamllaoo d) max: ||All iterations.
Simulations. We consider an instance of the metric learning application (Application 1 in section 3.2) using the Tris dataset (Fisher, 1936) (d= 4) loaded via scikit-learn (Pedregosa et al., 2011). We standardize the features, sample |S| 400 similar (same-label) pairs and [D] 400 dissimilar (different-label) pairs. We then solve the resulting simplex spectraplex game (5) by running SCMWU and its optimistic variant (OSCMWU) for T' = 9000 iterations with stepsizes The = -Ty = 20 starting from a random initialization. We report the duality gap of the average itcrates as defined in (11) on a log scale. The plotted curves in Figure 1 correspond to the average over independent seeds (which resample S, D and the initialization) and the shaded area is + one standard deviation. Figure 1 shows a slight advantage for (OSCMWU)) compared its non-optimistic counterpart SCMWU.
SCNWU
10
OSCMMU
10
Duality SMP
10-4
4000
5000
8000
Figure 1: Duality gap of the average iterates versus number iterations for OSCMWU and SCMWU for a distance metric-learning application on the Iris dataset (mean + std over 5 seeds).
Prior work. In contrast to prior work, we use single algorithm (OSCMWU) for all our applications of SCGs. Existing literature proposes algorithms which are tailored to specific applications. Problem (5) can
10

---

Published in Transactions on Machine Learning Research (03/2026)
be solved using the smoothing technique (Nesterov, 2007) in (1/e) iterations and square root logarithmic dependence on the dimension d. Our iteration complexity is similar. Both methods require full eigenvalue decomposition per iteration. This per-iteration cost can be significantly reduced using techniques such as rank sketches (Baes et al., 2013; Carmon et al., 2019) while koeping a similar total number of iterations. Ying & Li (2012) proposed a Frank- Frank-Wolle method using the smoothing lechnique which only requires to compute the largest eigenvector of a matrix at cach iteration which costs ((P) runtime and improves over the per- iteration cost of full eigenvalue decomposition. However, their algorithm requires O(1/<²) iterations. We also refer the reader to Garber & Hazan (2016) for further improvements for solving instances of the general problem (6) with approximation algorithms running in sublinear time in the size of the data. The problem can also be solved very efficiently and with high precision using interior-point methods but their per-iteration cost becomes prohibitive for large scale problems for which first-order methods are preferred.
6.2 Second-Order Cone Min-Max Games (e.g. Fermat-Weber Problem)
Iteration complexity of (OSCMWU). For this problem, it can be immediately seen that m2(2, y) - =ff v) = A' y, (2 m,,,, y) = yz, L2 = max; |ililtroo and R = In (I) = In 2, R₂ = plnppaannnnpee (n(raa((T.. = pln2. By Theorem 11, in
(2. y) = Aø - b. It follows that the Lipschitz constants satisfy L1
order to obtain an e-saddle point suffices for both players to run (OSCMWU) with stepsize 1) = 2T. for T 1(p+1)4m2 iterations.
Simulations. We consider a synthetic instance of the Fermat-Weber (sum-of-norms)) problem described in application 1 in section 3.2, in dimension d = 20 with 50 target points and constraint radius R = 5. For each seed, we generate an instance B = {6, Vo C g by sampling i..dd Gaussian directions, normalizing each sample, and then scaling each b, to have a random norm uniformly distributed in [0.5R, 1.5R). We solve the associated second-ordee--cone min-max game (9) by rumning SCMWU and its optimistic variant (OSCMWU) for T 10000 iterations with constant stepsizes Th = Fly = 7 x 10-2. In Figure 2, we report (i) the primal objective g(ū.) as defined in (7) evaluated at the average iterate 7,, and (ii) the duality gap computed at the averaged iterates (Ze, Mo) as in (11), plotted on logarithmic scale. The curves correspond to the mean over 5 seeds, and the shaded region indicates + one standard deviation. The resulting two-panel plot shows that the objective function decreases and stabilizes as expected and the duality gap vanishes as shown in Theorem 11 with an advantage for (OSCMWU) compared to SCMWU.
200
CSC VIN1
OSCVINII
275
270
100
OR 2133
200
255
290
285
500
3500 152
1000
2250
1750
2000
2002
4266
6000
8320
10320
Number termsion
Figure 2: (Left) Objective function values of the average iterates (Right) Duality gap of the average iterates for OSCMWU and SCMWU for facility location problem (mean + std over 5 seeds).
Online facility location variant. We now consider an online variant of the facility location problem introduced in section 3.2. Consider a sequential setting in which demands arrive over lime (streaming demand) and the decision maker must update the facility location on the fly. At each round t = 1, 2.2..... T, a new point b, E Id and a lincar map A, E Rmxd are revealed after the learner has committed to a location 2, E C = {a Rd || < R}. The instantancous incurred loss is g( == ||A by bell2. Similarly section 3.2, we define online saddle-point. loss fe v) = (Arā - be, 9) for any F (1/2, x/(2R)) e
11

---

Published in Transactions on Machine Learning Research (03/2026)
Autui y E Antti, where A, 2R(0 Ad), A. (0,4,) and by (0,b)). Running (OSCMWU)) online corresponds to updating 2, using the first-order feedback -V y1) A y and updating y using Vyfa D1) Āạ by. In the experiment of Figure 3, consider setting with d radius R = 1, and horizon T = 20000. The data stream (Ar, be) is generated from temporally correlated (predictable) process: A, = A is sampled once with i..dd standard Gaussian entries and then rescaled so that ||Al|2 = 1, while b, E æd follows an AR(1) recursion b, pb,-1 + /1-
10,
p² E with ~ ((0,021 (here 0.6, 0.12), followed by normalization enforcing ||6,|12 1. We run SCMWU and (OSCMWU) with the same constant stepsizes 1/2- = fly = 10 from the interior initialization (1/2,0.... .0) A We report the time-scaled sum of regrets (ri(t) + r2(t))/t (mean + one standard deviation over 5 independent seeds, which resample the entire stream), as defined and bounded in Theorem 10. Figure 3 shows that the time-scaled sum of regrets vanishes for both (OSCMWU) and SCMWU, with an advantage for OSCMWU in this predictable online learning selting.
10R
SCMWU
OSCMWU
Time scated sum of
10"4
2500
5000
7500
10000
12500
15000
17500
20000
Round
Figure 3: Time-scaled of regrets for OSCMWU and SCMWU for online facility location problem (mean + std over 5 seeds).
Prior work. The sum-of-norms problem can be solved using an exlension of the smoothing technique of Nesterov to EJAs studied in Baes (2006) (section 6.5 p.194) with a mumber iterations of the order O(1/e) and a (mdd)) per-iteration cost. (OSCMWU) enjoys similar guarantoes (sce the straightforward computa- tion of the exponential for the second-order cone case Appendix B.4). For comparison, the interior point method of Xue & Ye (1997) requires fewer iterations ((/pllog(mxx,, |bb l/c) + log a function of the desired accuracy but requires much higher per-iteration cost O(m's pmn2). We note that none of the previous methods is online. In contrast to our method, they are offline methods tailored for this particular problem.
For more general hybrid SC min-max games with product of cones of different types (SOC, SDP), see appendix E.
7 Conclusion
We introduced the class of Symmetric Cone Games (SCGs) which unifies variety of multi-player games with structured strategy spaces, including normal-form, quantum and geometric settings. SCGs provide principled foundation for structured game-theoretic learning, bridging spectral and geometric optimization in unified framework. We proposed OSCMWU, universal optimistic online lcarning algorithm with closed- form updates, and established convergence guarantees for equilibrium computation in two-player zero-sum SCGs. Our framework paves the way for more unified approaches to structured game-theoretic learning exploiting the structure of stratogy spaces beyond simplices or generic convex scts. Promising directions for future work include extending beyond symmetric cones, tackling non-zero-sum games, and developing scalable implementations for high-dimensional and low-rank settings for the case of the PSD cone.
12

---

Published in Transactions on Machine Learning Research (03/2026)
Acknowledgments
We thank the anonymous reviewers for their valuable foodback, which helped improve the mamuscript.
This work supported by the MOE Tier 2 Grant (MOF--22F22022--0013) Ministry of Education Singapore (SRG ESD 2024 174), the CQT++ Core Research Funding Grant (SUTD) (RS-NRCQT-00002), and partially by Project MIS 5154714 of the National Recovery and Resilience Plan, Greece 2.0, funded by the European Union under the NextGeneration Program.
References
Farid Alizadeh and Donald Goldfarb. Second-order cone programming. Mathematical programmingg 95(1): 3 3-51, 2003. 19
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia. Spectral sparsification and regret minimization beyond matrix multiplicative updates. In Proceedings of the Jorly-seventh anaual ACM symposium on Theory of computing, pp. 237-245, 2015. 18
Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach semidefinite programs. Journal of the ACM (JACM), 63(2):1-35, 2016. 18, 21
Sanjeev Arora, Elad Hazan, and Satyen Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In 46th Annual IEEE Symposium on Foundalions of Computer Science (FOCS'05), pp. 339-3 348. IEEE, 2005. 18
Sanjeev Arora, Flad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of computing, 8(1):121 11,,1,,111,,,,, 2012. 18
Gurdal Arslan, M Fatih Demirkol, and Yang Song. Equilibrium efficiency improvement in MIMO interference systems: A docentralized stream control approach. IEEE Transactions on Wireless Communications, 6 (8):2984-28) 2993, 2007. 5
Michel Baes. Spectral functions and smoothing techniques Jordan algebras. Catholic Universily of Louvain. Ph. D Thesis, 2006. 8, 12
Michel Baes, Michael Burgisser, and Arkadi Nemirovski. randomized mirror-prox method for solving structured large-scale matrix saddle-point problems. SIAM Journal on Optimization, 23(2):934 962, 2013. 8, 11,
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, (33):1677177,, 2003.
Rajendra Bhatia. Matris analysis, volume 169. Springer Science & Business Media, 2013. 23
Jack Brimberg. The Fermat Feemat-Webber location problem revisited. Mathematical programming, 71:71-70 76, 1995.
1, 6
Iladda Canyakmaz, Wayne Lin, Georgios Piliouras, and Antonios Varvitsiotis. Multiplicative updates for online convex optimization over symmetric cones. Xiviv preprinl arXin:2307.03136. 2023. 2, 7, 8, 10, 18,
Yair Carmon, John C Duchi, Sidford Aaron, and Tian Kevin. A rank-1 sketch for matrix multiplicative weights. In Conference Learning Theory, pp. 580 623. PMLR, 2019. 11, 18, 19
Nicolo Cisa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
9
Shouvanik Chakrabarti, Huang Yiming, Tongyang Li, Soheil Feizi, and Xiaodi Wu. Quantum wasserstein generative adversarial networks. Advances in Neural Information Processing Systems, 32, 2019.
13

---

Published in Transactions on Machine Learning Research (03/2026)
Jein-Shan Chen and Shaohua Pan. An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming. Compulational Oplimization and Applications, 47(3):477-499) 2010. 8
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pp. 6-1. JMLR
Workshop and Conference Procoedings, 2012. 18
Pierro-Luc Callaire-Demers and Nathan Killoran. Quantum generative adversarial networks. Physical Review A, 9811)24, 2018. 1
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero- sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium Discrete Algorithms, рp. 235 254. SIAM, 2011. 18
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27644-27616, 2021. 18
Alexandre d' d'Aspremont and Noureddine El Karoui. stochastic smoothing algorithm for semidefinite programming. SIAM Journal on Optimization, 24(3):1138 1177, 2014. 19
Francisco Facchinei and Christian Kanzow. Generalized nash equilibrium problems. Annals of Operations
Research, 175:1) 211, 2010. 5
Jacques Faraut and Adam Korányi. Analysis on symmetric cones. Oxford university press, 1994. 2, 3, 24, 26
Gabricle Farina, Toannis Anagnostides, Haipeng Luo, Chung- Wei Lee, Christian Kroer, and Thomas Sand- holm. Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems, 35:39076 -90069,-9,,,,-- 2022a. 4, 18
Gabriele Farina, Chung-Wae Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In International Conference on Machine Learning, pp. 6337-6357. PMLR, 2022b. 18
Leonid Faybusovich. E. Lieb convexity inequalities and noncommutative Bernstein inequality in jordan- algebraic sctting. Theoretical Mathematics & Applications, vol.6, no.2, 1-35, 2016. 8, 23, 27
Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of eugenics, 7(2): 179 188, 1936. 10
Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Gomes and Economic Behavior, (9(1))):79 103, 1999. 9, 29
Dan Garber and Elad Hazan. Sublinear time algorithms for approximate semidefinite programming. Math- ematical Programming, 158:329-361 361, 2016. 11
Laura Georgescu, James Fox, Anna Gautier, and Michael Wooldridge. Fixed-budget and multiple-issuc quadratic voting. orXiv preprint arXiv:249.00600 2024. 5
M Sectharama Gowda. Positive and doubly stochastic maps, and majorization in Euclidean Jordan algebras. Linear Algebru and ils Applications, 528:40-B0 61, 2017. 23, 27
M Seetharama Gowda. A Hölder type inequality and an interpolation theorem in Euclidean Jordan algebras.
Journal of Mathematical Analysis and Applications, 474(1):244-28)) 263,, 2019. 3
Gus Gutoski and John Watrous. Toward general theory of quantum games. In Proceedings of the thirty-
ninth annual ACM symposium on Theory of computing, pp. 565 574, 2007. 4, 5
Rahul Jain and John Watrous. Parallel approximation of non-interactive zero-sum quantum games. In 2009 24th Annual IEFE Conference on Compulational Complenity, pp. 243-253. TEFE, 2009. 4, 5
14

---

Published in Transactions on Machine Learning Research (03/2026)
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay,, and John Watrous. QIP = PSPACE. Journal of the ACM, Volume 58, Issue 6, Article No.: 30, Pages 1 27, 58(6), December 2011. 18
Rahul Jain, Georgios Piliouras, and Ryann Sim. Matrix multiplicative weights updales in quantum zero- sum games: Conservation laws & recurrence. Advances in Neural Information Processing Systems, 35: 4123-4135, 2022. 1
Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. Advances in Neural Information. Processing Systems, 36, 2024. 19
Erik G Larsson and Eduard A Jorswieck. Competition versus cooperation on the miso interference channel. IEEE Journal on selected oreas in Communications, 26(7):1059 1069, 2008. 5
Wayne Lin, Georgios Piliouras, Ryann Sim, and Antonios Varvitsiotis. No-regret learning and equilibrium computation in quantum games. Quantum, 8:1569, 2024.
Nahidsadat Majlesinasab, Farzad Yousefian, and Mohammad Javad Feizollahi. A first-order method for monotone stochastic variational incqualities on semidefinite matrix spaces. In 2019 American Control Conference (ACC), pp. 169-174 174. TEFE, 2019. 5
Panayolis Mertikopoulos and Aris L Moustakas. Learning in an uncertain world: MIMO covariance matrix optimization with imperfect feedback. IEFE Transactions on Signal Processing, (1(1):5-18, 18, 2015. 5
Panayotis Mertikopoulos, Ya-Ping Hsieh, and Volkan Cevher. A unilied stochastic approximation framework for learning in games. Mathematical Programming, 203(1):559 609, 2024. 4
Arkadi Nemirovski.
with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-255) 2511 2004. 10
Yurii Nesterov. Smoothing technique and its applications in semidefinite optimization. Mathematical Pro- grammiing 110(2):245 259, 2007. 1, 11
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXic:1912.1322 2019.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825 0-2225-2830, 2011. 10
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond timo-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. Advances Neural Information Processing Systems, 35:22258 -22269, 2022. 18
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Conference on Learning Theory, pp. 993 1019. PMLR, 2013a.
Sasha Rakhlin and Karthik Sridharan.
Optimization, learning, and games with predictable sequences. Ad- vances in Neural Information Processing Systems, 26, 2013b. 7, 18
J Ben Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica:
Journal of the Econometric Society, pp. 534, 1965. 5
Gesualdo Scutari, Daniel P Palomar, and Sergio Barbarossa. Competitive design of multiuser MIMO systems based game theory; A unified view. IEEE Journal on Selected Areas in Communications,, 26(7):1089 1103, 2008. 5
Shai Shwarr-S Online learning and online convex optimization. Foundations and Trends in Machine Learning, 122):107-194 2012. 7
Sherman. crov-con,, 1 &iintyy regularization, and undirected multicommoditt flow. In Proceedings of
the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 452 06204 2017. 19
15

---

Published in Transactions on Machine Learning Research (03/2026)
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. Aduances in Newral Information. Processing Systems, 28, 2015. 2, 5, 7, 8, 9, 18, 22, 28
Tao, Lingchen Kong, Ziyan Luo, and Naihua Xiu. Some majorization inequalities in Euclidean Jordan algebras. Linear Algebra and Its Applications, 461:92-122. 122, 2014.
Koji Tsuda, Gunnar Rätsch, and Manfred К Warmuth. Matrix exponentiated gradient updates for on-line learning and bregman projection. Journal of Machine Learning Research, ((Jm))9995 1018, 2005, 18
Francisca Vasconcelos, Haamanouil-Vasiliiinn iouras, and Michael I Jordan. A quadratic speedup in finding Nash equilibria of quantum zero-sum games. Quanlum Techniques in Machine Learning Conference 2023, arXiv:2311. 10859, 2023. 2, 5, 7, 10, 18, 31
Mataakis-Gkarakkonnii Panayotis Mertikopoulos, Georgios Pil-
Manfred K Warmuth and Dima Kuzmin. Online variance minimization. In International conference compulational learning theory, pp. 514-528 Springer, 2006. 18
Manfred K Warmuth and Dima Kuzmin. Online variance minimization. Machine learning, 87(1):1-33 32, 2012. 18
Kilian Q Weinberger and Lawrence K Saul. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(2), 2009.
Guoliang Xue and Yinyu Ye. An efficient algorithm for minimizing sum of Euclidean norms with applica- tions. SIAM Journal on Optimization, 7(4):1017-1036, 1997. 1, 6, 12
Yiming Ying and Peng Li. Distance metric learning with eigenvalue optimization. Journal of Machine Learning Research, 13(1):1-26, 2012. 1, 5, 6, 11
Yao-Liang Yu. The strong convexity of von neumann's entropy. Unpublished note, pp. 15, 2013. 8
Alp Yurtsever, Joel A Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. Scalable semidefinite programming, SIAM Journal on Mathematics of Data Science, 3(1):171-200, 2021. 8, 19
Renbo Zhao. Convergence rate analysis of the multiplicative gradient mothod for PET-type problems. Operalions Research Lellers, 51(1):26 32, 2023. 18
Jiaqi Zheng and Tiow-Seng Tan. Approximation algorithms for smallest intersecting balls. arXiv preprint 2rXiv:2406. 11369, 2024. 18
Jiaqi Zheng, Antonios Varvitsiolis, Tiow-Seng Tan, and Wayne Lin. A primal-dual framework for symmetric cone programming, arXiv preprint 00112775,091177 2024. 18
16

---

Published in Transactions on Machine Learning Research (03/2026)
Contents
Introduction
1
Preliminaries: Euclidean Jordan Algebras, Symmetric Cones, and Entropy
3
3 Symmetric Cone Games
4
3.1 Examples of SCGs
5
3.2 Representative Applications of SCGs
5
Optimistic Symmetric Cone Multiplicative Weights Updates
7
5 Regret Analysis and Average Iterate Convergence Guarantees
8
5.1
Individual Regret Bound and Strong Couvexity Symmetric Cone Negative Entropy
5.2 Sum of Regrets Bound Symmetric Cone Games
9
5.3 Application to Two-Player Zero-Sun Symmetrie Cone Games
9
Applications to Min-Max Problems: Metric Learning and Facility Location
6.1
Simplex-Spectraplex Games (e.g. Metrie Learning)
10
6.2 Recond-Ordes Cone Min-Max Games (e.g. Fermat- Weber Problem)
11
7
Conclusion
12
A Related Work
18
B Background on Symmetric Cones and EJAs
19
B.1 Definition of symmetric cones
B.2 Rank of an EJA
B.3 Examples of symmetric cones and their corresponding F.JAs
19
B.4 Exponential computation in (OSCMWU)
20
B.5 Trace-p norms
21
B.6 Bregman divergence of the symmetric cone negative entropy
21
C Proofs for Section 4
21
C.1 Proof of Proposition
21
C.2 Proof of Proposition
22
C.3 Proof of Theorem Strong convexity of the SCNE
22
D Proofs for Section 5.2
28
D.1 Proof of Theorem 10
28
D.2 Min-Max Games
28
17

---

Published in Transactions on Machine Learning Research (03/2026)
E More General Hybrid Symmetric Cone Min-Max Games
30
F Games with Multilinear Utilities
30
F.1 Smoothness of payoff vectors for multilinear games
30
F.2 Choi map for EJAs
31
G Technical Lemmas
32
A Related Work
Multiplicative weight updates. The Multiplicative Weights Update (MWU) algorithm has a long history percolating several fields including game theory, online learning, optimization, machine learning and computer science. We refer the reader to Arora et al. (2012) for a nice survey. Beyond its classical form over the probability simplex, extensions to more complex structures- suchh as the Matrix Multiplicative Weights Update (MMWU) for density matrices (Tsuda et al., 2005; Warmuth & Kuzmin, 2006; 2012; Arora & Kale, 2016)-have broadened its applicability to semi-defiitte programming (Arora et al., 2005; Arora & Kale, 2016), quantum computing (Jain al., 2011) and graph sparsification (Allen-Zhu et al., 2015). Carmon et al. (2019) proposed rank-one sketch methods for the matrix multiplicative weight method to reduce the expensive compulational cost of a full matrix exponentiation while preserving the MMWC regret guarantees. We refer the reader to the discussion therein for more details regarding this line of work. Canyakmaz et al. (2023) introduced the symmetric cone multiplicative weights update algorithm (SCMWU) for online learning over the trace-one slice of symmetric cone. (SCMWU) unifies the different ver- sions of multiplicative weights updates algorithms mentioned above. Our (OSCMWU) algorithm enhances (SCMWU) with additive optimistic term in the weights sequence. Zhao (2023) analyzed the multiplicative gradient method for an optimization problem in which the objective function is neither Lipschitz nor smooth.
Optimistic online learning. A key performance measure in online learning and game theory regret. For min-max problems for which the min-max theorem holds, it is well-known that if the average regret is bounded above by e, then the time-averaged iterate (z, y) an e-saddle point. In worst-case contexts in which the environment is modeled in fully adversarial way, average regret typically vanishes at the rate of O(T-1/2), a bound known to be light. However, this worst-case analysis is too pessimistic when players adopt predictable algorithms in games. In these settings, optimistic learning algorithms have achieved significant improvements, reducing average regret rates to O(T in both two-player zero-sum games and multi- normal-form games (Daskalakis et al., 2011; Chiang et al., 2012; Rakhlin & Sridharan, 2013b; Syrgkanis et al., 2015; Daskalakis et al., 2021). These impactful advances have been established for games where strategies lie in the standard simplex (Daskalakis et al., 2021; Piliouras et al., 2022) and extended to general convex subsets of the Euclidean space (Syrgkanis et al., 2015; Farina et al., 2022a) and polyhedral convex games (Farina et al., 2022b). Recently, Vasconcelos et al. (2023) showed that improved rates can also be achieved in the case of zero-sum quantum games using several different optimistic matrix multiplicative weight (OMMWU) algorithms, some of which can be seen as a particular case of our (OSCMWU) algorithm instantiated with the PSD cone. Our analysis in this work is different as it relies on the OFTRL framework rather than the optimistic mirror prox viewpoint and holds for arbitrary symmetric cones.
Symmetric cone programming using SCMWU. Recent works (Zheng et al., 2024; Zheng & Tan, 2024) used the Symmetric Cone Multiplicative Weights Update (SCMWU) to solve specific Symmetric Cone Programs (SCPs) via binary scarch, where in each step of the binary scarch min-max problem is solved approxinately in order to solve the approximate feasibility problem (of the intersection of the feasible set and the sublevel set of the objective function). In the specific problems tackled by both of those works, the stratogy space of the min-max game the trace-one slice of symmctric cone on one side (where the strategy is updated using SCMWU) and a convex set on the other (where the strategy is played by an oracle). Thus, while their method for solving SCPs uses SCMWU in game-playing framework, it is not
18

---

Published in Transactions on Machine Learning Research (03/2026)
easily amenable to the speedup that optimistic methods enjoy due to there being stability guarantees for the iterates in the convex set (played by an oracle). They are, however, able to handle different sets of problems since additional constraints (that are not just trace constraints) can be handled by the oracle. Thus, while their work related, we regard their method and applications as parallel to those we present in this work.
Applications of symmetric the semidefinite programming (SDP) and second-order cone programming (SOCP) literatures. For instance, problem (6) has been studied in the SDP literature with special emphasis on designing efficient first-order methods for large scale problems using different randomization techniques (Baes et al., 2013; Yurtsever et al., 2021; Aspremonn & El Karoui, 2014; Carmon et al., 2019). num-of-norms problems have been discussed for instance in Alizadeh Goldfarb (2003) (sco section 2.2). Other norm minimization problems such as maximum norm minimization also fit our symmetric cone game sctting and we can use (OSCMWU) similarly. Nevertheless, our symmetric cone game selting captures arbitrary cone examples beyond the special cases of the simplex-spectraplex or second-order cone games we consider for illustrating the expressiveness of the class of symmetric cone games. Besides the applications we consider, Jambulapati & Tian (2024) have considered box-simplex games as well as sox-spectraplex games and proposed faster first-order algorithms relying on area convexity (Sherman, 2017).
games. Some of our applications have been extensively studied in
B Background on Symmetric Cones and EJAs
B.1 Definition of symmetric cones
Definition 12. (Symmetric cone) Let (V, (V))(),)) be an inner product space. A cone K C V is symmetric if:
K. is self-dual, i.e. K = where K = tu E V x) 2 0, Ya E K. is the dual cone.
K. is homogeneous, iee. for any u E int(K), there exists an invertible linear map T s.t. T(u) = and T(K)- = K.
B.2 Rank of an EJA
The minimal polynomial of an element E I is the monic polynomial p E R[xx] of minimum degree for which p(x) = 0, and the degree of an clement x E I is the degree of its minimal polynomial. The rank of Jordan algebra is the maximum degree of its elements.
B.3 Examples of symmetric cones and their corresponding EJAs
The nonnegative orthant RT. The corresponding EJA is R" equipped with Jordan product yoy- (0I....,,,,n,) and the identity element is the all-ones vector e Ln. The rank of this EJA is n, and the spectral decomposition of æ E R" is x = Σ, I.e; where e; is the standard i-th basis vector. The trace of x E R" then the sum of its components, ie., tr(x) = E. Di, and the canonical EJJ. inner product is the Fuclidean inner product (z. y) tr(x y) Σ, rilli-
The second-order cone L (also known as the Lorentz cone). This is the set {x: = (01, σ) E R || & }. and its corresponding E.AA is Ldd, i.c., the set I8" equipped with the Jordan product goy- (i 7. + 81 where (I1, F). y (y1, 7) RR Ra-1 and we use x to denote Σn=1 2.0. The identity element is e 1l) The rank of this EJA is 2, and the spectral decompasition of a point (s, 1 is
(s, = (s + (| + (s ||0112) 4-
(13)
where 0= =
The trace given by tr((s, x)) = 2s and the canonical EJA inner product is twice the Euclidean inner product, i.e.,
2 -1==
(x, v) = 2x y-
19

---

Published in Transactions on Machine Learning Research (03/2026)
(These are the conventions use in this work; it should be noted that some sources choose to scale the Jordan product by factor of 1 to remove the factor of 2 from the expressions of the trace and the EJA v2
inner product.)
The PSD cone 84, Le., the set of n x a symmetric positive semidefinite matrices with real entries. The corresponding E.JA is S", the set of n x symmetric matrices with real entries, equipped with the Jordan product
XoY +X 2
(14)
ie. the symmetrized matrix product. The identity element is the identity matrix e Ln The rank of this EJA is n, the spectral decomposition the usual spectral decomposition for symmetric matrices, and the trace the usual matrix trace. The EJA inner product the Hilbert-Schmidt inner product (X tr(X o Y)= tr(XY).
The set H of X n Hermitian PSD matrices with complex entries. The corresponding EJA is the of Hermitian matrices with complex entries, equipped with the Jordan product (14). The relevant properties the same for $7 above.
Product cones. Any Cartesian product of the above symmetric cones is also a symmetric cone, and the corresponding EJA is the product of their corresponding FJAs. The identity element of this EJA is the product of identity elements, and the spectral decomposition of element is the product of the spectral decompositions of its components. The rank/ ttace of an element is simply the sum of the manks/traces of its components.
Table 2: Examples of Euclidean Jordan Algebras and the corresponding Symmetric Cones
Inner product (x, 3)
Jordan product
EJA J
Cone of squares IC
roy
Euclidean space (R.)
E Fayl
nonnegative orthant (RR.)
Real sym. matrices
($")
tr(zy)
1 [ yz) t
PSD cone"
(S
Jordan spin algebra² (L*)
t
2.3/ (x 21 y. 112)& second-order cone
(L
This is the set of real symmetric positive semidefinite matrices. 2 This is the set R Ra-1, This cone is the set L. (at = (x1,4) E R x RR-1 ||>||| S #1), and is also known as the Lorentz cone. # This is the coordinatewise product vector, a.k.a. the Hadamard Schur product. I The product used here the standard matrix product. Here = (21,5), y = (v1, D) E B Rn- We use & ÿ to denote Σ 5.9i-
B.4 Exponential computation in (OSCMWU)
In this section, we briefly discuss the computation of the exponential of an element x E J where J is an EJA. We provide comments on a case by case basis.
Euclidean space R., In this case, the exponential computation is straightforward and consists in comput- ing the exponential of each one of the coordinates, i.e. for vector IR.", exp(x) (exp(r:))==I,..>> Rd.
Jordan spin algebra LL. Given the spectral decomposition (13) which is easy to compute in time linear in the dimension n, we obtain
exp((s, z)) = exp (s + ||~||~) 9+ + exp (s | (2) g-
(15)
Therefore the computation of the exponential is straightforward
20

---

Published in Transactions on Machine Learning Research (03/2026)
Real symmetric matrices S". In this case, the computation of the matrix exponential is more expensive and can be performed (approximately) in much as (nn²) time for a matrix (the notation O() hides polylogarithmic factors in n and in 1/e where e refers to the accuracy of the solution) by computing an cigenvalue decomposition of the symmetric matrix and exponentiating the cigenvalues. We refer the reader section in Arora Kale (2016) for more details and potential improvements for faster matrix exponentiation.
Product EJAs. In this more general setting, the exponential can be computed separately for each one of the EJAs.
B.5 Trace-p norms
Theorem 13. The trace-co norm || = max, [1)(1)] is the dual norm of the trace-1 norm | Σj
Proof. Recall that the dual norm IIrII,,,,, sup ull.,, ((0,z)). We shall prove separately that I Iaaller,o and ||- S ||
(2) For given with spectral decomposition E, Asgi, let k argmax, 1y that ||0 |del and set = sign(Ae)gs- Since e, share the Jordan frame {az}, we have
(0.x) = tr(ū o x)) = sign( {x = Dell = |1
Since | 1, we then have ||=||,,, = sl 1.., =1 (w x>) 2 ||
(<) For given I we have | max, (z)), thus
| Ix x IK |arller,
(16)
where we use the generalized inequality 3x y for x, y E J to denote that y- E K. Then, by self-duality of the symmetric cone, we can take the inner product of the incquality chain (16) with any E Ax to give
- -1|=|ler,oo S (v, < ||
Vo E Ax.
i.e, supeeAe [0, x)) S || Finally, by Lemma 26 we have
sup | I|
[(,,x)] sup KV, | veAx
B.6 Bregman divergence of the symmetric cone negative entropy
Let Φ C R be continuously differentiable and strictly convex function defined the convex set C. The Bregman divergence D& (z, associated with & for the points y, E C is the difference between the value of & at and the first-order Taylor expansion of F around y evaluated at y, i.c., Dz v) ((x) - k(y) v - y) The Bregman divergence associated to the SCNE Pent defined above is given by D (x, = tr(x o In x o Iny + - æ)) for every x, E int(K).
C Proofs for Section 4
C.1 Proof of Proposition
The proof follows similar lines as Lemma 4.1 in Canyakmaz et al. (2023) showing the equivalence between (non-optimistic) SCMWU and FTRL.
WWe the fact that (0,e) tr(vor) tr(e) for all E Ag-
21

---

Published in Transactions on Machine Learning Research (03/2026)
C.2 Proof of Proposition 5
This result echoes Proposition 7 in Syrgkanis et al. (2015) which relies on the combination of Theorem 19 (a regret bound) and Lemma 20 (a stability result) therein. Both these results hold in our setting as the proof follows the exact same lines upon replacing the inner product by the EJA inner product, the pair of dual norms (Il ||- I|+) by dual norms defined on the EJA and the simplex A (S,) (where S is a finite strategy space for player their context) by the generalized simplex Ax. We do not reproduce the proof here for conciseness.
C.3 Proof of Theorem 7: Strong convexity of the SCNE
We provide a detailed proof. The reader familiar with EJAs might directly check Eq. (19) and the proof of the data processing inequality for the diagonal mapping (Theorem 14). Let K. be the cone of squares associated to EJA J and denote by its rank. Let z, E K s.t. tr(x) tr(y) 1. There exists Jordan frame fq: hiigr and scalars (Sshrsigr s.t. x z-y Ei= Xg We further suppose without loss of generality that ||@:l| = so that the Jordan frame is an orthonormal basis of a subspace of the EJA J. We will use the canonical inner product provided by the trace throughout this proof.
Consider the following mapping:
T: J+J
2 (l2.d)
(17)
We first observe that (I)) S in)(K)) and (x(T(x)) = tr(TTt)) = 1. In other words, the mapping is trace preserving and maps the interior of the cone subset of the same cone. In particular, this ensures that the Bregman divergence between the points (ax) and T(y) is well-defined as this will be useful in the rest of the proof. We provide brief proof of the simple aforementioned facts:
Let x E ik), we prove that T(x) E int(KC). Since x E K. = K* (by definition of a symmetric cone), it follows that for any z E KC, (z, 2 0. Moreover, for every S i S r.q. = o² E K. Therefore (I, q.) > 0 and the incquality is strict since x E int((C) in*)
Observe that tr(T(x)) (z, tr (q:) (z, (c. Σ q.) (5. tr(x) = 1, where we have used the linearity of the trace, the definition of a Jordan frame and the canonical inner product ((:-) = tr(- -)).
We also define the mapping:
J - R"
4 ((x,)))ssir.
(18)
We now have the following set of inequalities:
1 l1(x)) 1
Do(r.y) ())
Do(T()),T(V)) =I.(u<))lu(V))
u(v))l (d) 21110 vIl
(19)
(b)
where (a) follows from the projection inequality (see Theorem 14 below for statement).. (b) stems from
writing D& (T))),T())) ( q:)q;, (i q:)q;) and the spectral definition of the Bregman di- vergence in terms of the eigenvalues of and y in the Jordan frame {a)) (c) is an application of Pinsker's
D&
inequality in the Euclidean space IR" using the definition of the mapping u, (d) follows from using the definition of the linear mapping and writing:
[|u()) u(y)ll = ||u( y) = Σ [r y, 9:)l = [[( - g))le,,1 = || vllur,
(20)
1=1
22

---

Published in Transactions on Machine Learning Research (03/2026)
where the last inequality follows from observing that
T(x y)
Σ q.r y)q:
Σ N = Σ Arl..999
A1q: = y.
(21)
Note that we have used here the decomposition of - y, the definition of a Jordan frame and the fact that the Jordan frame consists of normalized idempotents. Note also that the above identity T(x ((z-y) y) precisely why have considered the Jordan frame associated with y from the beginming of the proof. Theorem 14 (Projection incquality). Let J be simple rank-r EJA and let K. be its cone of squares. Let (4: be a Jordan frume. Define
y is
T: J-J
(22)
Then for every 2, y E int(KC,
D& (T(T)) (z(
(23)
Proof. The idea of the proof is to write the diagonal operator T as convex combination of automorphisms of the Jordan algebra and then use the joint convexity of the relative entropy function shown in Corollary 3.4 8 in Faybusovich (2016) to obtain the desired inequality. Before providing the proof for EJAs, we provide first some motivation for the proof based on a proof of the special case of the EJA of real symmetric matrices. The reader familiar with such a proof might skip item (i).
(i) Motivation and intuition. Our proof is inspired from some known observations made in Problems II.5.4II.5.5 in Bhatia (2013). Consider the following 3 3 block matrices
An
A12
A13
T 0 0
T
0
0
=
A21
Aga
A23
1 U-
0
0
, U2
0
- 0
(24)
A31
Ag2
A33/
-1)
0
1
where 1 are identity matrices with dimensions compatible with the blocks of the matrix A. It follows from simple computations that
An
A12
0
1 (A+ = A21
A22
0
(25)
Ag3
Similarly, if we apply the same treatment the 2 non-zero block of the matrix A,
AAu
0
0
C2(A) 1
=
A22
0
(26)
0
Ag3
We have obtained the diagonal block of A from the initial matrix A by applying so-called pinching operations. In particular, observe that U? U3 I. This implics that C3 is an average of automorphisms and so is C2 by composition of automorphisms. By combining (25) and (26), can simply write the diagonal blocks of A convex combination of automorphisms (of the EJA of symmetric matricos here). We will use the same strategy in the more general seiting of EJAs in what follows. This generalization is partly inspired from Example 9 in Gowda (2017), especially for considering the quadratic representation to generalize the operations above of the type UL However, this aforementioned example is not concerned with the diagonal mapping and does not address our question interest.
(ii) The diagonal mapping is a convex combination of EJA automorphisms.
First, recall the Peirce decomposition theorem which will be crucial in our proof.
Note that this step the proof does require fact that the EJA simple.
23

---

Published in Transactions on Machine Learning Research (03/2026)
Theorem 15 (Peirce Decomposition in EJAs, e.g. Faraut & Korányi (1994)). Let J be EJA with rank and (er,"",, er) a Jordan frome of J For i,j E (1,,., ;r), we define the eigenspaces:
Ja = 1z E J. z0e; = =
(27)
Jij = fx E J xo - -x=xoes). i i
(28)
Then the space I is the orthogonal direct sum of the subspaces Ty (i S j) Purthermore,
Jop Ti 5 Ta + Tjj.
(29)
Jij Jyk S Ja if i
(30)
Ju o Jkl = {0} if (k. =
(31)
Then we can write any x E I as:
Σ
Jij
Tijz
(32)
1StSJSr
KEKjSr
where o; E IR and Fig E Tij. This is the so-called Peirce decomposition of x E J associated with the Jordan frame {e1, ,er.
We now define for every
w = -2e, = El + - -jj +j+1 + +... +r
(33)
where is the unit element of the EJA, Ei=1 eg. Observe that w/ e for every j {1, .r. We further introduce the quadratic representation P of the EJA (see e.g. section IT. 3 in Faraut & Korányi (1994)) which is the map defined for every E J by:
P. := :2=2([w)> I(w²),
(34)
where L(w) is the linear map of I defined by L(w)x wo Using this definition, it follows that for every J,
(r( = 2w o (w x) w² or.
(35)
As for the connection with the case of the algebra of symmetric matrices, notice here that for an associative algebra and a Jordan product z o = (xy + yxx, then (a( = wow. We now recursively define a sequence of operators (C+)2sh5r+1 as follows:
C,+1(1) = x, EJ,
(36)
Cx-1 2 (c((x) + Pas (Ca(x))) Yk E (3, r.....++ J.
(37)
1r
(38)
The following proposition provides a closed form expression of the pinching operations defined above. In the case of the E.JA of symmetric matrices, each pinching operation Cs sets the last row and column coefficients of the symmetric matrix (except the the diagonal) to zero, see (25)-(26) for an illustration.
Proposition 16. Vr 2 vl E (-1,0,
2}, Va E J, C, (() = - E Eisiek Tik-
Proof. We prove this result by induction on I. The base case follows from observing that for l = -1, we have Cz-((x)= = (z) = for all x E J by definition of Cr+1 in (36). Suppose now that the result holds for some E 1,,, 1,,....... 3}:
C-((s)=
Σ
Σ
Fik
(39)
24

---

Published in Transactions on Machine Learning Research (03/2026)
By the recursive definition of the operator (1++1) have for every z E J,
1 (Cr-1(z) Pu. (c. (Cr-1(z)))
C--(+1)(x)=
(40)
where we recall that Wi (1+11 = 6 -2y-(141) Since by definition,
Pa., ain) (Cr- (1+1( (1--(1+1) o Cr-1(z)) - (z)
we have in view of (40) that for every x E J
Cr-(+1)(x) (1-(111) (wr-1++)) Cr-((x))
(41)
We now compute ()-(1+)(()) starting with the following term:
(y+(1+1) o (x)
(1+1)
-- Σ
Σ
Lisk
(42)
11ickk
(
(1+1) o
Iiei + Σ
Vij Σ Σ
(43)
kir-l1sick
(c)
(1+1)
IjCi +
Pik
(44)
1=1
R=
Isick
kmr- Tsick
(-(1-1
(d)
(e-
20, (0,-11+1))
Σ Izli +
Lik
(45)
k=2
Isick
(-(++)
(-(++)
DíC;
Σ
Σ Isick
Tik
- (1-1))---1111 (1+1)
Σ
Σ 1sick
e- o Takk (46)
where (a) follows from using the closed form of (x-1(z) in (39), (b) stems from using the Peirce decomposition of w.r.t. (e1,-.. , (c) from rewriting the second term of the Peirce decomposition, (d) uses the dcfinition of (1-(111) and simplifies the previous difference of sums. Finally, the last equality uses the distributiiityy of
the Jordan product o over the addition in the EJA and the fact that {ei, ,,, is Jordan frame.
We now simplify the last sum in the expression above. Observe that i < (in particular i + k)) and for k < r- (1+1), we have (I+))) k] 0. By the orthogonality properties of the Peirce decomposition (see (31)), it follows that (--(11) o Zak 0 for k < r (1 1). The only remaining term in the sum is the term for k r (1+ 1), i.e,
(1+1)
Σ
Σ ISick
Cr-(1+1)
Fik
Σ 12irr-(1+1)
Cr-(1+1) (1rr
By definition of J(,--(+1) in the Peirce decomposition (see Theorem 15, (28)), we have 02, 2 (++r-(1+1) Combining this with (47) and (46), we obtain
r- (1+2)
w,-(+1) o Cx)((z) x.e, 2x, (01 +
Zzk.
(47)
2=
Isick
To proceed with our computation, observe now that
(y-(1=1) (wir-(++1) o cr-((z)) wr-(1+1) o Cr-1( 2e,-((+1) (wy-(++1) cr-1(2))
(48)
25

---

Published in Transactions on Machine Learning Research (03/2026)
We compute the last term in the previous identity using (47) follows:
r-
Cr-(++1) o (141 Cr-r(x)) c--(1-1)
Σ s,c, (411(41-)-0)
Σ
Σ
Iitk
k= 1sick
r-
Σ
=1-((41))7-((41) - 2x, (1-1))rrr--1111)
cr-(1+1) o 2ik
k=2
Tsick
= --11-(4116--(111
(49)
where the last identity from observing that (y-(1+1) Fik = for every 2 r- 2 by the orthogonality properties of the Peirce decomposition (see (31)). Overall, combining (41), (47), (48) and (49), we obtain
again
(1+2)
Cr-((t))()=
Tee +
Σ
Tik =
Σ
Tik
(50)
Igick
This concludes the proof.
7
Corollary 17. The diagonal mapping coincides with C2.
Proof. Sct I = r- in Proposition 16 and recall the Peirce decomposition:
tae + Σ xz =
Σ
Iik
(51)
icj
k=21skkk
Proposition 18. For all l E (0, "0, 1}, Cr+1-k is a conver combination of automorphisms.
Proof. We prove this result by induction. The base case k follows from the fact that C,+1 defined the identity operator, (36). Suppose now that C++1-k is convex combination of automorphisms for some & (....., r 2}. Hence, there exist sequence of nonnegative reals (A)isisn s.t. Σ A and a sequence of EJA automorphisms (di)isisn (where is unknown integer here that will not be further specified) s.t. Cx+1- = Ei= No. Using the recursive definition of C,+1- we have for every x E J,
(++1-((41(()) =
2 (C++1-((x)) + Parti-ce (C++1-A(1))
Σ Enrh(to))
(xxx(x)) + -Prrti-(AA)
2
A Pa
(((z)
+
2 Pu (oi(x)),
(52)
2
1=1
where we have used the linearity of the operator Pa,-1-044)" To conclude, note that P. Pacti- is an automorphism by Proposition I1.4.4, p. 37 in Faraut & Korányi (1994) since w² wf+1- e. Moreover, the composition of two automorphisms is yet another automorphism since the set of F.JA antomorphisms is a group for the composition. Therefore for every E (I,...,,i) nn, the composition Par41-(441) di is an automorphism. This concludes the proof.
Corollary 19. The diagonal mapping is conver combination of aulomorphisms.
Proof. Combining Corollary 17 and Proposition 18 (with & r r- 1) gives the result..
26

---

Published in Transactions on Machine Learning Research (03/2026)
(iii) Using joint convexity of the relative entropy and properties of automorphisms. Using the joint convexity of the relative entropy shown in Corollary 3.4 p. 8 in Faybusovich (2016), we can write:
(e((()),T(w) = D2 (oo
S Σ x,Do(((()))0()))
(53)
We now conclude the proof by showing that D (o(0)()). = Dz.x., y) for any 1 ssis n. We note that the previous quantity is well-defined as the cone of squares of an EJA is invariant under any automorphism of an EJA. We now use the definition of the relative entropy and the fact that every automorphism also doubly stochastic map. In particular it is trace preserving. We have
(o(0) (v))) = (z( o (,(x)) 0z(z) o (n) + 2.()) - dx()))
= tr():(z) o In (x))) - tr((:(z) o In (v)(())) + (r() - tr(o:(z))
tr():()) o (x)) - tr((:(z) o (v)) + tr(y) tr(x).
(54)
We now show that for any x E K, and any automorphism & of the EJA,
In (nd(() <(Inxr).
(55)
To see this, observe that there exists a Jordan frame {41,-. gr) stt. x= =E= \x(2), where {A(x)) are the eigenvalues of x. Then by definition In x = Ei=1 In(A(())) By linearity of Φ we have x(nx) Σi= In In(A{()))((g)) Since & is an algebra automorphism, it maps Jordan frames to Jordan frames (see e.g. Gowda (2017)). Therefore, (δ(q)),.. ... "((())))) is also a Jordan frame. As a consequence, we can also write o(I Ei= In(Ax())))(g)) We have shown that d(I((z) In(ó(z)).
We now conclude the proof by combining (54) with the identity we have just established by observing that: (x( o In (b)) = tr(),(x) o. (In(v))) = tr(oi(z In y)) tr(xr o In
(56)
where the first equality follows from (55), the second by definition of an automorphism and the last by the fact that an automorphism is trace preserving. Similarly, we have tr(()(ar) o In (x)) = tr(x o In
We have shown that D+ (., (x, and hence from (53) the desired inequality.
Some comments are in order regarding the proof of this theorem.
About the particular case of the Jordan spin algebra L R x RT -,, 2 3. We provide some comments about the proof of Theorem 14 when the EJA is the Jordan spin algebra, the limitations of this proof and difficulties to generalize it to (even simple) EJAs. This motivates our specific treatment focused on the properties of the diagonal mapping. The diagonal operator T' is doubly stochastic mapping, i.e, a linear map which is positive, unital (maps the unit element to the unit element) and trace preserving. We refer the reader to e.g. Gowda (2017) for more background and example 7 therein for the aforementioned fact. Then we can use Theorem 9, P. 57 in Gowda (2017) stating that DS(L") Here conv denotes the convex hull, (Tt( is the set of automorphisms of L (Jordan) algebra automorphism Φ any v, E I and DS(L") is the set of doubly stochastic mappings. Using this result together with the fact that T' E DS,L"), it follows that T E conv(Aut(L")) and hence there exist a family of nonnegative scalars (Aihsssn s.t. Σn A = 1 and a family of automorphisms ( (di)sign of the E.JA s.t. T = Σ X The rest of the proof follows the same lines as the proof for the general case of EJAs using joint convexity of the relative entropy.
conv(Aut(L"))
I being invertible lincar transformation satisfying Φ(x y) d(x) Φ(y) for
The fact that DS(L") = conv(Aut(L")) only holds for the Jordan spin algebra. For instance it is not true for the simple algebra all 3 x 3 complex Hermitian matrices (see Example 11 in Gowda (2017); see also example 10 therein for another counterexample). There a weaker pointwise version for any simple EJA, i.c., DS(J)z conv(Aut( for any simple EJA J and any J, see Theorem in Gowda (2017). This result is not sufficient. for our purposes to invoke the joint convexity of the relative entropy as this
27

---

Published in Transactions on Machine Learning Research (03/2026)
would only give different convex decompositions for T(x), T(y) depending z, E J. Nevertheless, we only need decomposition of the diagonal mapping as convex combination of automorphisms and this is precisely the result we show in the proof above with a decomposition of the mapping which does not depend on the point we evaluate the diagonal map in.
Proofs for Section 5.2
D.1 Proof of Theorem 10
The proof follows similar lines as the proof of Theorem 4 in Syrgkanis al. (2015). We provide here complete proof for our setting of symmetrie cone games under Assumption 1. First, it follows from Proposition 5 that the regret rT(T") of each player i E N satisfies
R 17
T
T
S
mm m 11
10 2 11.
(57)
4n
The main task now consists in controlling the second term in the above bound using our smoothness as- sumption and use the negative term. Using assumption 1 and the definition of the payoff vectors, we have
mm m m| |m,(x*) mn(a"'/1)1 S Lill=* - x'
1ag 21
(58)
where the last inequality follows from Lemma 25 (note that the last norm the norm defined the EJA Jz). Then it follows from the bound (58) and Jensen's inequality that
N
|| -mm 112 S NLE
Σ
2
(59)
We observe in this bound that the payoff vector variations of player are bounded by the strategy variations of all the players. Therefore to control this error we will be summing up the regret bounds over all players in view of using the negative terms induced by each player in the individual regret. bounds to balance the error. Summing up (57) and using (59), we obtain
N (T) <
N nN
N
T
Σ
11 R
+
| - 13 11
(60)
17
4n
1=1
1=1
1=1
Setting 17 1/ 1 N N L7) concludes the proof.
D.2 Min-Max Games
Theorem 20. Consider a two-player symmetric cone game setting (N = 2). Assume that the game is zero-sum (U2 -1 f). Then the following statements hold:
The min-max theorem holds, i.e. min max f(z, 9) max min f(z, y) = v²
BEAK, VEAK,
sEAK,
The duality gap is bounded by the sum of regrets, i.e. for any sequences (x*), (v'), the average sequences (Fr), (ūr) defined by TT Et x. ET y' satisfy for T > 1.
0 < d(ār, TT) = max () min f(a, TT) < (T( + (2 yE
(61)
zEAx,
T
where F1,72 F2 the regrets incurred by players 1 and 2 respectively.
28

---

Published in Transactions on Machine Learning Research (03/2026)
The suboptimality gaps for the min and maz dual problems are bounded by the sum of regrets, e.e. di (Trrr = max ((TT, u) v² and d2(ūr) == =² yEAK₂
min (r) solisfy: sEAK,
0 0 (id((TT) < (I( + (T(
(T( + (I)
0 S d2(UT) <
(62)
T
T
The point (Tr,ür) Dx, Ax2 is an tr())
approrimate saddle point, i.e. for every (r,y) e
Dx, AK21
f(āT. v) ri(TT +r((T) S f((r (r) S f(x, + (T) + rT(
(63)
T
T
Proof. (i) follows from the generalized von Neumann min-max theorem upon noticing that A Ax, are convex compact sets and f is convex w.r.t. its first argument and concave w.r.t. its second argument, see e.g. section in Freund & Schapire (1999) for an online learning algorithmic proof. We then have the chain of inequalities:
(2(
min max f(I,y) (2( #EAR, yEAx,
(64)
T
T
f(rr, r2(
1 max yEAK2
(65)
T
1
Σ
f(0'vv)
T2(
max y
T
T
1=1
Σ ((,1,0)
Σ f(x,8')+ (T)
T
min =EDR1
T
T
t=1
f(z, vr) + (T(
S min =EAx,
(66)
T
I max min f(x, v) + (T) yeAx, #EAx,
T
= v + (T) T
(67)
Comparing the expressions in lines (65) and (66) immediately gives the bound on the duality gap in (ii)
while comparing (65) with (67) and (64) with (66) give the bounds on the suboptimality gap in (Hii).
Finally, comparing (65) and (66) again (or just taking the result in (ii) tells us that
max f(āT, y) r2(T) < min f(x, (T) rI( rEAx,
(68)
yεAk₃
Since the right-hand-side of (68) is lower bound to f(ār, (T) ri(T) we have
max f(Tr, y) (T) + r2( < f(ār.ūr).
(69)
yε
T
i.e. that ūr is an (1(T))22()) approximate best response to ãт. On the other hand, since the left-hand-side of (68) is an upper bound to f(rr. (r) - ra(2) we have
f(ZT,yT) < min f(r, + (T) + (2 zeax,
(70)
T
29

---

Published in Transactions on Machine Learning Research (03/2026)
ie. that Fy is an +r()) -aprrssimae best response to fr. Putting (69) and (70) together gives us (iv)
(i.e. that (TT, is an (r())aa(T) approximate saddle point).
E More General Hybrid Symmetric Cone Min-Max Games
We consider here bilinear min-max games over the most generalized simplexes (OSCMWU) can handle. Since bilinear utilities can be characterized by linear functions over the tensor product space, we express the min-max problem using tensor product notation for symmetry between players:
min max (z, x @ v)
(71)
=EAx, yEAK2
where KG = x Th= T. is the cone squares of the EJA J1 = R x Ih= T. and K₂ = I da. is the cone squares of the EJA Ji = S x xII,-t Ldz,, 2 ZE 8. is the "game tensor", and similarly to the case of quantum games we can obtain the gradients of the players' utilities with respect to their own strategies: m1(x, y) = - tra (z o (er X v)). m2( y) = tr, (z o (ar @ ez)) where 61, are the identity elements of J1, T2 respectively. See appendix below for a derivation of this and the definition of the partial trace functions tri, lrg. Then, if the utilities are bounded, i.e,, maxхEAx, wEAx, (2, y)l < for some L 0, then we have the Lipschitz constants L1, S L. Assumption 1 holds (by Proposition 23 using Assumption 21 which is satisfied, see Appendix F below for more details). Finally, we have R In(rank(Ji)) In(n1 + 2m1) ) and similarly that R2 = In(nz + 2m2), so by Theorem 11, in order to obtain an e-saddle point of (71) it suffices for both players to (OSCMWU) with stepsize 1) = 2L for T > 4(In(n: +2m1)+ +I(mn=+ 2mz))) iterations.
+
F Games with Multilinear Utilities
In this section we present some technical results specific to games with multilinear utilitios.
F.1 Smoothness of payoff vectors for multilinear games
In our multilinear game setting, we follow the notation of the main part but replace Assumption with the following assumption on the utilities X' + R:
Assumption 21. Each payoff function u, X J, J, R is multilinear and satisfies [u,(x)] L, vz X.
The bound on each [x)] in Assumption 21 has natural interpretation that the payoffs that each player can obtain are bounded. Proposition 23 allows us to convert this into lipschitz bound on the payoff vectors. We first have the following technical lemma:
Lemma 22. Let KI,...,K,, be the comes of squares of EJAs II,..., In respectively, and suppose that ue 1= Jn + IR is mullilinear with (ux(x)) < La Vx E I1 AK,- Then for any j E [r]] the linear function ul u(.,z-;) J, - R. satisfies
Li.
Proof. This follows directly from Lemma 26:
[|u( (4(((,=-))ller...
max ll?
lus (1) max
x-)= S Li-
This then gives us the following bound on [m] -m1--11 in terms of Ez -
Proposition 23. Suppose that the game satisfies Assumption 21 and is played repeatedly that at time player i 's strategy is given by x². Fix the norm ||-11 = Il-l) Then for each player and time t, we have the following bound:
I m m1llll < L Σ
|o - 2 1-
30

---

Published in Transactions on Machine Learning Research (03/2026)
Proof. We first observe that, for given # j and Vx, Ac,, z-jj [[g Are, and time
ua(2,, 2J. x-1 - u, 25 x xz-5))] - Lillaj - =--'1l
(72)
by Lemma 22 and Assumption 21. We thus have
(1) x-1)) ij) - us( u5(; x xz-1i))1_ , = max Mi(Is TJ, x. un (1 25 اأ=-يع 11al1==1
max (t. x31)) us (xs ا meAx
I Li|lzo - 2
where the second equality follows from Lemma 26 and the fact that us is multilinear, and the inequality and use SMS for 1 S h to denote the tuple
follows from (72). Finally, index the j + by j1, f2. ..2.....,....................... in In-1
(o)))-. -. We have
||mm - ml- = (1u4((;==+) uz( ,r(,
ll. S
Tu ||
-
1, jfi
Σ
1 x5
1=1
where the inequality follows from Lemma 22.
F.2 Choi map for EJAs
Utility functions Ti x J2 IK that multilinear the product/direct space also be charac- terized by linear functions the tensor product space, iee,
JI 2 J2 R
(73)
& y (2,
for some 'game tensor' J1 @ J2- (We write this section for two players for simplicity of notation, but it can easily be extended to the multiplayer case.)
To obtain from this characterization the gradient of a with respect to, say, the z-player, we use an extension of the Choi-Jamiolkowski isomorphism, which corresponds quantum states with quantum channels, to EJAs The Choi Jamiotkowski isomorphism has been similarly used to compute gradients in quantum games, see egg, Vasconcelos al. (2023).
To do this, define the lincar map (which depends the game tensor defined in (73)) by
+ J2 + F1,
(74)
+ urz (a (er &
where the partial trace function on J1 8 Jz with respect to Tz defined by
tr : J1 2 J2 + Jr:
(75)
x ② - tr(y)æ
and e₁ is the identity element in Jr. The following proposition then says that the gradient of a utility function (characterized by game tensor according to (73)) with respect to x is simply +z())-
Proposition 24. Given game tensor J1 & Jz, define O in (74). Then the following holds:
(z. 2 v) (z, (v)))
(76)
Proof. Let U....,, Ur, be basis for Ji and wi...., Wrz be basis for Jz. Then {op & wyheefnl is basis for Jn @ Jz, and we can write
Σ 255(1 wy)
31

---

Published in Transactions on Machine Learning Research (03/2026)
for some 2ij R. We then have
(a, Oz(2))
(z, tre (zo (e1 @ ())))
Ziy 2 w2) (er 2 )n))
Σ
3g lrz
if
Σ
2s (v @ (wy o 01))
2, tT2
ij
2
Bzy tr2 (v; (wy o v))
Σ Ziy tr(wy y)us
24j (1), x) (wz, 8) Σ
Σ Zij (u; X Wj, 0
Σ Zif4s 2 Wj 28
(z, x @ vy)
G
Technical Lemmas
Lemma 25. Let J == I1 Ji be the product Euclidean Jordan Algebra of EJAs Js and let - be the
norm induced by the EJA inner product (r,)),, on each one of the EJA Js, i.e. for = (II, IN) e
J, |0013 = EiEv || where || = x;) Then for every x = ( EN) E I S
Σe |
EEE 11, S (EieN ||>,ll.,) ) where the last inequality follows from noticing that all the terms in the left hand side are contained in the expansion of the square the right hand side of the inequality.
Proof. An immediate proof stems from obsorving that || =
Here is an alternative proof using the fact that || I1.7 is a norm. Using the triangular inequality and the definition of the inner product on the product of EJAss:
|| = [x .......... , = [|(2, 0, 0) + (2, 0, ... .0) + + (0. ... x,
S [1 0, ... 0)Il, [1 x2, 0,... ,0), +... 11(0, ... 0, Nl)ls
n
|
(77)
Lemma 26. Let J an EJA and its cone of squares. If h: J + IR a linear function, then we have
|x(x)] = max [/(xx)).11 11
max || l..1
aEAx
11 Maxima attained since [M(=)] is continuous and both {ar E J. || 1} and Ag are compact.
32

---

Published in Transactions on Machine Learning Research (03/2026)
Proof. Let V² max all,,, [b(x))- Since D for E J | 1), need only prove that maxxEax [h(x)) 2 e².
Note that [hxx)l max (h(x), -h())) so
max max -h(x)) max |=
max h(x), max -h(s) ||ller, m1
-h(a)) ||=ll,,, =1
(78)
Without loss of generality
assume that o* max -1 h(x), since if it is instead the case that x* = max] =1 -((x) then we could simply have taken -h as our linear function instead." 12 The maximum of h(x) over {i J || = 1 is attained at some x²; let E3 deq; be its spectral decomposition. Since X; = sign()):, we have
x² = Σ A.q = Σ Ael sign(A.)
L.e., x² is convex combination of {sigm(Ae) (since E, =1 Then, since each sign(A:)g also lies in for J || 1} and x² is the maximizer of the linear function h(x) over {x E I || 1}, we have
v' = h(x²) = h(sign(A)g))
vé: : | # 0.
Now pick any : [A * 0.
gs E Ax and satisfies [h(q:) = (X:):(()<)q:) = v² Therefore we have
max [h(x)] 2 [M(g)] = v".
12i... define g(x) == -(()). We then want to show that max| =lla,, [g(x)) max.eax g(x)), we are the case that
=1 max
[g(x)) |a g(x).
33


Reviews:
[{"review_id": "7PcIRrBwPd", "reviewer": "Reviewer_Bggv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a unified framework for symmetric cone games, in which players’ strategies lie in the generalized simplex of a symmetric cone. This formulation subsumes several well-studied game classes, including normal-form games, positive semidefinite (PSD) matrix games, and quantum games.\n\nTo solve these games, the authors propose a single online, projection-free algorithm — OSCMWU —which can be viewed as a variant of the Optimistic Follow-the-Regularized-Leader method. The convergence analysis hinges on establishing strong convexity of the negative entropy map over symmetric cones. This step is technically demanding and relies heavily on tools from Euclidean Jordan algebra. Under smooth convex utilities, the authors derive a convergence rate on the order of $1/\\varepsilon$, which explicitly reflects the complexity of the strategy space through the rank of the Euclidean Jordan algebra associated with the cone. In particular, the a logarithmic dependency on the rank is achieved. \n\n**Strengths and Weaknesses**\n\nStrengths :\n1. The paper is fairly well-written and easy to follow.\n2. The unifying framework is of practical interest and the existence of a general algorithm which specializes along various classes of symmetric cone games is an important contribution. \n\nWeaknesses:\n1. The only two applications considered are already tackled by Nesterov smoothing with similar performances. It would be interesting to have alternative applications that stress the “online” aspect of the algorithm proposed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The main technical contribution of the paper is the establishment of the strong convexity of the negative entropy over general symmetric cones. The proof proceeds by lower bounding the negative entropy between two elements by the entropy of their respective projections onto a Jordan frame (the projection is called a Diagonal operator). The authors then show that the negative entropy between these projected elements can itself be lower bounded by the trace-1 norm of the difference between the original elements. The key projection inequality relies on a nice inductive argument, which decomposes the Diagonal operator into a convex combination of automorphisms that commute with the logarithmic map associated with the underlying EJA. These developments are technically sound and accurate. The other contributions (regret bounds and complexity rate) follow from standard argument from the online convex optimization literature.", "audience_yn": "Yes", "audience_explanation": "I believe this paper is of general interest as it offers a unifying framework for solving a diverse class of games using the same general method. The rates derived are able to capture the complexity of the ambiant strategy space (via the rank of the EJA associated to the symmetric cone).", "requested_changes": "Here are minor changes to address :\n* Page 2 : Optimistic Symmetric Cone Multiplicative Weights “Update”\n* Page 3 : Does the proof of Baes (2006) present the same constants regarding the strong convexity of the negative entropy. Is so, this should be stated.\n* Page 22 - Theorem 14 : The Jordan frame $\\{e_1,…, e_r\\}$ is introduced twice, making the statements slightly confusing.\n* Equations (41) and (49) : $i < j$\n* Page 24 - Below equation (50) : $w_{r+1 - (k+1)} ^2 = e$", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "USKYIFZR5o", "reviewer": "Reviewer_3Twb", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper formulates a class of multi-player games named symmetric cone games (SCGs), where each player's strategy lies in a generalized simplex. Furthermore, they provide several examples included in SCGs. Particularly for two-player zero-sum SCGs, this paper proposes an online learning algorithm called optimistic symmetric cone multiplicative weights updates (OSCMWU). For the regret analysis of the proposed method, the authors provide the result on the strong convexity of the symmetric cone negative entropy with respect to the trace-one norm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Although I could not read most of the proof in the appendix due to time limitations, the equations and analyses appear rigorous.\n\nHowever, I felt the discussion of related work was slightly unclear, particularly regarding [1], though this relates to the main contribution of this paper. I believe that discussing the difference from [1] about the following is required:\n- Regarding the strong convexity shown in Theorem 7, Lemma 2.1 of [1], which is partially from [2], shows a related result for the (strict) convexity. I think that the difference should be explicitly discussed.\n- The problem setup itself is similar. However, this similarity with [1] is discussed only briefly in Section 4 (and the appendix). I believe that a more comprehensive comparison is required regarding, e.g., the differences in the scope of the problem setup and the above convexity analysis, though the improvement in the regret analysis has already been discussed.\n\n[1] Ilayda Canyakmaz, Wayne Lin, Georgios Piliouras, Antonios Varvitsiotis, Multiplicative Updates for Online Convex Optimization over Symmetric Cones\n\n[2] Jein-Shan Chen · Shaohua Pan, An entropy-like proximal algorithm and the exponential multiplier method for convex symmetric cone programming\n\nPost rebuttal --------\n\nMy concern is resolved by the revision.", "audience_yn": "Yes", "audience_explanation": "The problems discussed in this paper relate to a wide range of applications, as discussed in Section 3.\nTherefore, I believe that there is an audience who is interested in this line of study.", "requested_changes": "- Please add the discussion for the related work described above.\n- In Section 1, the following sentence is written. I think that ``applying OSCMWU'' can cause confusion since it can be read as the authors will show experimental results. Please consider rephrasing this expression.\n>We illustrate the versatility of our framework by applying OSCMWU to two representative SCGs, showcasing its generality, simplicity, and robust convergence across different cone geometries.\n\n- In Eq. (3), there is $u\\_i^t$. Is this a typographical error of $u_i$? Please fix or add a definition of this.\n\n- Regarding Example 1 in Section 3.1, there is an abuse of notation with respect to $u_i$. Moreover, I think that the function of $a\\_i$ and $x\\_{- i}$, $u\\_i (a\\_i, x\\_{-i})$, is not defined. Please add the explanation.\n\n- Example 2 is not informative. Please add mathematical definitions or citations, or please delete it.\n\n- Many examples are shown in Sections 3.1 and 3.2. Do these examples satisfy the assumption of the proposed method's analysis? Or, do these examples just demonstrate the broadness of the problem definition? Anyway, please consider explicitly describing this point.\n\n- Regarding the paragraph right after Theorem 7, I could not understand the message of this paragraph since a similar statement is discussed in the following paragraph. Please consider rephrasing these two successive paragraphs.\n\n### Minor points\n- There are several inconsistent uses of font type. In particular, subscripts in $\\| \\cdot \\|\\_{\\rm tr}$ are often italic. Please recheck the entire paper.\n- In the first paragraph of Section 3.2, ``machine learning'' is capitalized. Please consider making it lowercase.", "broader_impact_concerns": "N/A", "additional_comments": "- The authors claim that the proposed method is projection-free and its updates are closed-form. Although I think that these are benefits regarding computational efficiency, there is no experimental validation of this benefit. Furthermore, the authors note that existing methods have computational complexity almost identical to that of the proposed method for two specific applications, as discussed in Section 6. Therefore, I currently understand that the merit of the proposed framework is only the versatility and ability to support online learning.\n- To be honest, I felt that the construction of Sections 4 and 5 was strange. First, since their titles are similar, I could not imagine any difference in the contents of these sections from the titles alone. Second, although Section 4 starts with the sentence ``we present our ... algorithm,'' the regret analysis is also partially discussed in Section 4 (mainly in Section 5). I think the construction, where Sections 4 and 5 focus on the proposed algorithm and regret analysis, respectively, is easier to follow.\n- Why didn't you provide the experimental result? Is there any limitation regarding computational complexity? (I ask this since ``developing scalable implementations'' is listed as future work.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "ufb7BFWXTw", "reviewer": "Reviewer_YWN9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a unified framework called Symmetric Cone Games (SCGs) for online learning over any generalized simplex (the trace-one slice of a symmetric cone), which has a wide range of applications in various settings like normal-form games and quantum games. To compute the approximate Nash equilibrium of any two-player zero-sum SCG, the authors proposed an online algorithm called Optimistic Symmetric Cone Multiplicative Weights Updates (OSCMWU) based on the Optimistic Follow-the-Regularized-Leader (OFTRL) framework, where the Symmetric Cone Negative Entropy (SCNE) is added as a regularizer. By using the strong convexity of the SCNE with respect to the trace-one norm, which is newly proved in this paper, the authors have shown that OSCMWU can achieve an $\\widetilde{O}(\\epsilon^{-1})$ complexity for computing $\\epsilon$-saddle points.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The reviewer finds that detailed proofs are provided for all theoretical results presented in this paper. However, the paper's quality can be potentially improved by adding a few numerical experiments to justify the effectiveness of the proposed OSCMWU algorithm.", "audience_yn": "Yes", "audience_explanation": "Overall, this paper studies and proposes an interesting framework for online learning over generalized simplexes. Regarding the theoretical results proved in the paper, to the best of the reviewer's knowledge, this is the first work that proves the strong convexity of the Symmetric Cone Negative Entropy (SCNE) with respect to the trace-one norm. Hence, this work will be of interest to TMLR's audience.", "requested_changes": "Below is a list of changes that the authors need to take into consideration:\n\n(1) The reviewer wonders whether it is appropriate to describe the proposed algorithm (OSCMWU) as being \"projection-free\". A more description might be that the algorithm doesn't involve any Euclidean projection onto the symmetric cone. However, under the OFTRL framework, the proposed algorithm does contain an implicit Bregman projection via the exponential-and-normalize step. Therefore, the authors might need to consider whether the description needs to be slightly modified here. \n\n(2) Regarding the applicability of Assumption 1, would it be possible for the authors to briefly discuss how the Lipschitz constants scale like in the Examples (normal-form games, PSD matrix games, quantum games) of the SCGs?", "broader_impact_concerns": "Since this paper is mainly a theoretical work in online learning, the reviewer doesn't think there is any related concern on the work's ethical implications.", "additional_comments": "NA", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)