Session: Online Learning and Optimization over Symmetric Cones
Chair: Antonios Varvitsiotis
Cluster: Conic and Semidefinite Optimization
Talk 1: SEMIDEFINITE NETWORK GAMES: MULTIPLAYER MINIMAX AND COMPLEMENTARITY PROBLEMS
Speaker: Constantin Ickstadt
Abstract: Network games provide a powerful framework for modeling agent in- teractions in networked systems, where players are represented by nodes in a graph, and their payoffs depend on the actions taken by their neighbors. Extending the framework of network games, in this work we introduce and study semidefinite net- work games. In this model, each player selects a positive semidefinite matrix with trace equal to one, known as a density matrix, to engage in a two-player game with every neighboring node. The player’s payoff is the cumulative payoff acquired from these edge games. Network semidefinite games are of interest because they provide a simplified framework for representing quantum strategic interactions. Initially, we focus on the zero-sum setting, where the sum of all players’ payoffs is equal to zero. We establish that in this class of games, Nash equilibria can be characterized as the projection of a spectrahedron. Furthermore, we demonstrate that determining whether a game is a semidefinite network game is equivalent to deciding if the value of a semidefinite program is zero. Beyond the zero-sum case, we characterize Nash equilibria as the solutions of a semidefinite linear complementarity problem.
Talk 2: Symmetric Cone Eigenvalue Optimization: Expressivity and Algorithms through Equilibrium Computation
Speaker: Jiaqi Zheng
Abstract: We investigate eigenvalue optimization problems over symmetric cones, a broad generalization of the matrix eigenvalue optimization problems. We show that symmetric cone eigenvalue optimization problems are highly expressive, capable of modeling a wide range of problems including nearest point problems, the fastest mixing Markov processes, robust regression, and computing the diameter of a convex set. From an algorithmic perspective, we show that these problems can be reformulated as two-player zero-sum or common-interest games over symmetric cones, enabling us to design algorithms for solving them through the lens of equilibrium computation. We implement these algorithms and assess their effectiveness in the aforementioned applications.
Talk 3: Optimistic Online Learning for Symmetric Cone Games
Speaker: Anas Bakarat
Abstract: Optimistic online learning algorithms have led to significant advances in equilibrium computation, particularly for two-player zero-sum games, achieving an iteration complexity of O(1/ϵ) to reach an ϵ-saddle point. These advances have been established in normal-form games, where strategies are simplex vectors, and quantum games, where strategies are trace-one positive semidefinite matrices. We extend optimistic learning to symmetric cone games (SCGs), a class of two-player zero-sum games where strategy spaces are generalized simplices—trace-one slices of symmetric cones. A symmetric cone is the cone of squares of a Euclidean Jordan Algebra; canonical examples include the nonnegative orthant, the second-order cone, the cone of positive semidefinite matrices, and their direct sums—all fundamental to convex optimization. SCGs unify normal-form and quantum games and, as we show, offer significantly greater modeling flexibility, allowing us to model applications such as distance metric learning problems and the Fermat-Weber problem. To compute approximate saddle points in SCGs, we introduce the Optimistic Symmetric Cone Multiplicative Weights Update algorithm and establish an iteration complexity of O(1/ϵ) to reach an ϵ-saddle point. Our analysis builds on the Optimistic Follow-the-Regularized-Leader framework, with a key technical contribution being a new proof of the strong convexity of the symmetric cone negative entropy with respect to the trace-one norm—a result that may be of independent interest.
