13 citations · 49 across the 32 of their papers we have counts for
35 papers
Where Should Learning Live? Regret Analysis for Text, Parameter, and Joint Adaptation
Jungtaek Kim, Jaden Park, Jongwon Jeong +2
Language-model systems can select prompts and parameter adapters repeatedly during deployment, using feedback to guide later choices. Earlier choices may change the context or envi…
Average-and Last-Iterate Lower Bounds for Optimistic Matrix Mirror-Prox in Quantum Zero-Sum Games
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Optimistic matrix mirror-prox (OMMP) computes -approximate Nash equilibria in quantum zero-sum games with an average-iterate guarantee [arXiv:2311.10859]. We…
On the Complexity of Finding Fixed Points for Set-Valued Contractions
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
We study the computational complexity of finding fixed points of set-valued contractions. We first formulate a computational problem for Nadler's fixed-point theorem, PROJECTED-NAD…
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis
We study adversarial multi-armed bandits with and without delayed feedback under a safety-aware goal: achieving minimax-optimal worst-case regret while keeping nearly constant regr…
No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis
We investigate the strategic surplus obtainable against a Follow-the-Regularized-Leader (FTRL) learner with constant step size in two-player zero-sum games played o…
Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene Vidal
From adversarial robustness to multi-agent learning, many machine learning tasks can be cast as finite-sum min-max optimization or, more generally, as variational inequality proble…
Learning Safely Without Knowing the World:COMPASS-Hedge
Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Online learning algorithms often face a fundamental trilemma: balancing regret guarantees between adversarial and stochastic settings and providing baseline safety against a fixed…
Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics
Deep Patel, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Many emerging applications - such as adversarial training, AI alignment, and robust optimization - can be framed as zero-sum games between neural nets, with von Neumann-Nash equili…
Breaking Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
Yiheng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
Quantum zero-sum games are bilinear saddle-point problems over density matrices. We study how their semidefinite geometry governs last-iterate convergence beyond existing $O(1/\var…
Solving Zero-Sum Convex Markov Games
Fivos Kalogiannis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Ian Gemp +1
We contribute the first provable guarantees of global convergence to Nash equilibria (NE) in two-player zero-sum convex Markov games (cMGs) by using independent policy gradient met…
Armada: Memory-Efficient Distributed Training of Large-Scale Graph Neural Networks
Roger Waleffe, Devesh Sarda, Jason Mohoney +3
We study distributed training of Graph Neural Networks (GNNs) on billion-scale graphs that are partitioned across machines. Efficient training in this setting relies on min-edge-cu…
Contracting with a Learning Agent
Guru Guruganesh, Yoav Kolumbus, Jon Schneider +4
Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions…
Exploiting hidden structures in non-convex games for convergence to Nash equilibrium
Iosif Sakos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +1
A wide array of modern machine learning applications - from adversarial models to multi-agent reinforcement learning - can be formulated as non-cooperative games whose Nash equilib…
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games
Francisca Vasconcelos, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos +2
Recent developments in domains such as non-local games, quantum interactive proofs, and quantum generative adversarial networks have renewed interest in quantum game theory and, sp…
Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Angeliki Giannou, Yudong Chen +1
For min-max optimization and variational inequalities problems (VIP) encountered in diverse machine learning tasks, Stochastic Extragradient (SEG) and Stochastic Gradient Descent A…
Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation
Yang Cai, Michael I. Jordan, Tianyi Lin +2
Equilibrium computation on Riemannian manifolds provides a unifying framework for numerous problems in machine learning and data analytics. One of the simplest yet most fundamental…
Chaos persists in large-scale multi-agent learning despite adaptive learning rates
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, Konstantinos Metaxas +1
Multi-agent learning is intrinsically harder, more unstable and unpredictable than single agent optimization. For this reason, numerous specialized heuristics and techniques have b…
Smoothed Complexity of SWAP in Local Graph Partitioning
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +1
We give the first quasipolynomial upper bound for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width…
Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
Ioannis Anagnostides, Fivos Kalogiannis, Ioannis Panageas +2
Adversarial team games model multiplayer strategic interactions in which a team of identically-interested players is competing against an adversarial player in a zero-sum game. Suc…
On the convergence of policy gradient methods to Nash equilibria in general stochastic games
Angeliki Giannou, Kyriakos Lotidis, Panayotis Mertikopoulos +1
Learning in stochastic games is a notoriously difficult problem because, in addition to each other's strategic decisions, the players must also contend with the fact that the game…
Efficiently Computing Nash Equilibria in Adversarial Team Markov Games
Fivos Kalogiannis, Ioannis Anagnostides, Ioannis Panageas +3
Computing Nash equilibrium policies is a central problem in multi-agent reinforcement learning that has received extensive attention both in theory and in practice. However, provab…
The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
Christos H. Papadimitriou, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Manolis Zampetakis
Kakutani's Fixed Point theorem is a fundamental theorem in topology with numerous applications in game theory and economics. Computational formulations of Kakutani exist only in sp…
First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces
Michael I. Jordan, Tianyi Lin, Emmanouil-Vasileios Vlatakis-Gkaragkounis
From optimal transport to robust dimensionality reduction, a plethora of machine learning applications can be cast into the min-max optimization problems over Riemannian manifolds.…
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
Daniel Hsu, Clayton Sanford, Rocco Servedio +1
We consider the well-studied problem of learning intersections of halfspaces under the Gaussian distribution in the challenging \emph{agnostic learning} model. Recent work of Diako…