Near-Optimal No-Regret Learning for General Convex Games
Gabriele Farina (Carnegie Mellon University)
3337 - 3348 of 19185 Results
Format results
-
-
Bootstrapping N = 4 sYM correlators using integrability
Zahra Zahraee Perimeter Institute for Theoretical Physics
-
Quantum Field Theory I - Lecture 221014
Gang Xu Perimeter Institute for Theoretical Physics
PIRSA:22100050 -
Relativity - Lecture 221014
PIRSA:22100077 -
The Power of Adaptivity in Representation Learning: From Meta-Learning to Federated Learning
Sanjay Shakkottai (University of Texas at Austin) -
Local supersymmetry as square roots of supertranslations: A Hamiltonian study
Sucheta Majumdar École Normale Supérieure de Lyon (ENS Lyon)
-
Introduction to Quantinuum and TKET
Mark Jackson Paris Centre for Cosmological Physics (PCCP)
-
When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications
Rad Niazadeh (The University of Chicago Booth School of Business) -
Optimal Learning for Structured Bandits
Negin Golrezei (Massachusetts Institute of Technology) -
-
Entanglement Bootstrap and Remote Detectability
John McGreevy University of California, San Diego
-
-
Near-Optimal No-Regret Learning for General Convex Games
Gabriele Farina (Carnegie Mellon University)A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's regret after T repetitions grows polylogarithmically in T, an exponential improvement over the traditional guarantees within the no-regret framework. However, so far these results have only been limited to certain classes of games with structured strategy spaces---such as normal-form and extensive-form games. The question as to whether O(polylog T) regret bounds can be obtained for general convex and compact strategy sets---which occur in many fundamental models in economics and multiagent systems---while retaining efficient strategy updates is an important question. In this talk, we answer this in the positive by establishing the first uncoupled learning algorithm with O(log T) per-player regret in general convex games, that is, games with concave utility functions supported on arbitrary convex and compact strategy sets. Our learning dynamics are based on an instantiation of optimistic follow-the-regularized-leader over an appropriately lifted space using a self-concordant regularizer that is, peculiarly, not a barrier for the feasible region. Further, our learning dynamics are efficiently implementable given access to a proximal oracle for the convex strategy set, leading to O(loglog T) per-iteration complexity; we also give extensions when access to only a linear optimization oracle is assumed. Finally, we adapt our dynamics to guarantee O(sqrt(T)) regret in the adversarial regime. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret bounds either in terms of the dependence on the number of iterations or on the dimension of the strategy sets. Based on joint work with Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm. Paper link: https://arxiv.org/abs/2206.08742 -
Bootstrapping N = 4 sYM correlators using integrability
Zahra Zahraee Perimeter Institute for Theoretical Physics
In this talk we combine integrability and conformal bootstrap to learn about correlation functions of planar maximally supersymmetric Yang- Mills theory. Focusing on correlators of four stress-tensor multiplets, we first introduce a set of dispersive sum rules that are only sensitive to single-traces in the OPE expansion (this is advantageous because this data is available from integrability). We then construct combinations of the sum rules which determine one-loop correlators. Further, we discuss how to employ the sum rules in numerical bootstrap to nonperturbatively bound planar OPE coefficients. As an example, we show a nontrivial upper bound on the OPE coefficient of the Konishi operator outside the perturbative regime.
-
Quantum Field Theory I - Lecture 221014
Gang Xu Perimeter Institute for Theoretical Physics
PIRSA:22100050 -
Relativity - Lecture 221014
PIRSA:22100077 -
The Power of Adaptivity in Representation Learning: From Meta-Learning to Federated Learning
Sanjay Shakkottai (University of Texas at Austin)A central problem in machine learning is as follows: How should we train models using data generated from a collection of clients/environments, if we know that these models will be deployed in a new and unseen environment? In the setting of few-shot learning, two prominent approaches are: (a) develop a modeling framework that is “primed” to adapt, such as Model Adaptive Meta Learning (MAML), or (b) develop a common model using federated learning (such as FedAvg), and then fine tune the model for the deployment environment. We study both these approaches in the multi-task linear representation setting. We show that the reason behind generalizability of the models in new environments trained through either of these approaches is that the dynamics of training induces the models to evolve toward the common data representation among the clients’ tasks. In both cases, the structure of the bi-level update at each iteration (an inner and outer update with MAML, and a local and global update with FedAvg) holds the key — the diversity among client data distributions are exploited via inner/local updates, and induces the outer/global updates to bring the representation closer to the ground-truth. In both these settings, these are the first results that formally show representation learning, and derive exponentially fast convergence to the ground-truth representation. Based on joint work with Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sewoong Oh. Papers: https://arxiv.org/abs/2202.03483 , https://arxiv.org/abs/2205.13692 -
Local supersymmetry as square roots of supertranslations: A Hamiltonian study
Sucheta Majumdar École Normale Supérieure de Lyon (ENS Lyon)
In this talk, I will show that supergravity on asymptotically flat spaces possesses a (nonlinear) asymptotic symmetry algebra, containing an infinite number of fermionic generators. Starting from the Hamiltonian action for supergravity with suitable boundary conditions on the graviton and gravitino fields, I will derive a graded extension of the BMS_4 algebra at spatial infinity, denoted by SBMS_4. These boundary conditions are not only invariant under the SBMS_4 algebra, but lead to a fully consistent canonical description of the supersymmetries, which have well-defined Hamiltonian generators. One finds, in particular, that the graded brackets between the fermionic generators yield BMS supertranslations, of which they provide therefore “square roots”. I will comment on some key aspects of extending the asymptotic analysis at spatial infinity to fermions and on the structure of the SBMS_4 algebra in terms of Lorentz representations.
Zoom link: https://pitp.zoom.us/j/95951230095?pwd=eHIwUXB5SUkvd0IvZnVUN3JJMFE1QT09
-
Introduction to Quantinuum and TKET
Mark Jackson Paris Centre for Cosmological Physics (PCCP)
As a recent combination of two strong global leaders in quantum computing, Honeywell Quantum Solutions and Cambridge Quantum, Quantinuum integrates quantum hardware and software, including solutions for drug discovery, materials science, finance, and other applications. Quantinuum aims to be a center of gravity for quantum computing, supporting collaboration across the ecosystem. For this we have also developed “TKET”, an open-source architecture-agnostic quantum software stack and ‘best in class’ compiler. This enables our partners, collaborators and clients to effortlessly work across multiple platforms and tackle some of the most intriguing and important problems in quantum computing.
Bio: Dr. Mark Jackson is the Senior Quantum Evangelist at Quantinuum. He received his B.S. in Physics and Mathematics from Duke University and Ph.D. in Theoretical Physics from Columbia University. He then spent 10 years researching superstring theory and cosmology, co-authoring almost 40 technical articles. To promote the public understanding of science, he founded the science crowdfunding platform Fiat Physica and non-profit Science Partnership Fund. He is Adjunct Faculty at Singularity University and a Director of Astronomers Without Borders.
Zoom link: https://pitp.zoom.us/j/98433088425?pwd=UzgwcGpUYnBKNzJmMnQ1ZVNOdGVXZz09
-
When Matching Meets Batching: Optimal Multi-stage Algorithms and Applications
Rad Niazadeh (The University of Chicago Booth School of Business)In several applications of real-time matching of demand to supply in online marketplaces --- for example matching delivery requests to dispatching centers in Amazon or allocating video-ads to users in YouTube --- the platform allows for some latency (or there is an inherent allowance for latency) in order to batch the demand and improve the efficiency of the resulting matching. Motivated by these scenarios, I investigate the optimal trade-off between batching and inefficiency in the context of designing robust online allocations in this talk. In particular, I consider K-stage variants of the classic vertex weighted bipartite b-matching and AdWords problems in the adversarial setting, where online vertices arrive stage-wise and in K batches—in contrast to online arrival. Our main result for both problems is an optimal (1-(1-1/K)^K)-competitive competitive (fractional) matching algorithm, improving the classic (1 − 1/e) competitive ratio bound known for the online variants of these problems (Mehta et al., 2007; Aggarwal et al., 2011). Our main technique at high-level is developing algorithmic tools to vary the trade-off between “greedyness” and “hedging” of the matching algorithm across stages. We rely on a particular family of convex-programming based matchings that distribute the demand in a specifically balanced way among supply in different stages, while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degrees to be used as strictly concave regularizers of the maximum weight matching linear program to form these convex programs. By providing structural decomposition of the underlying graph using the optimal solutions of these convex programs and recursively connecting the regularizers together, we develop a new multi-stage primal-dual framework to analyze the competitive ratio of this algorithm. We extend our results to integral allocations in the vertex weighted b-matching problem with large budgets, and in the AdWords problem with small bid over budget ratios. I will also briefly mention a recent extension of these results to the multi-stage configuration allocation problem and its applications to video-ads. The talk is a based on the following two working papers: (i) "Batching and Optimal Multi-stage Bipartite Allocations", https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3689448 (ii) "Optimal Multi-stage Configuration Allocation with Applications to Video Advertising" https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3924687 -
Optimal Learning for Structured Bandits
Negin Golrezei (Massachusetts Institute of Technology)In this work, we study structured multi-armed bandits, which is the problem of online decision-making under uncertainty in the presence of structural information. In this problem, the decision-maker needs to discover the best course of action despite observing only uncertain rewards over time. The decision-maker is aware of certain structural information regarding the reward distributions and would like to minimize their regret by exploiting this information, where the regret is its performance difference against a benchmark policy that knows the best action ahead of time. In the absence of structural information, the classical upper confidence bound (UCB) and Thomson sampling algorithms are well known to suffer only minimal regret. As recently pointed out, neither algorithms are, however, capable of exploiting structural information that is commonly available in practice. We propose a novel learning algorithm that we call DUSA whose worst-case regret matches the information-theoretic regret lower bound up to a constant factor and can handle a wide range of structural information. Our algorithm DUSA solves a dual counterpart of the regret lower bound at the empirical reward distribution and follows its suggested play. Our proposed algorithm is the first computationally viable learning policy for structured bandit problems that has asymptotic minimal regret. -
Dynamic Spatial Matching and Applications
Yash Kanoria (Columbia University)Motivated by a variety of online matching markets, we consider demand and supply which arise i.i.d. in [0,1]^d, and need to be matched with each other while minimizing the expected average distance between matched pairs (the "cost"). We characterize the achievable cost scaling in three models as a function of the dimension d and the amount of excess supply (M or m): (i) Static matching of N demand units with N+M supply units. (ii) A semi-dynamic model where N+M supply units are present beforehand and N demand units arrive sequentially and must be matched immediately. (iii) A fully dynamic model where there are always m supply units present in the system, one supply and one demand unit arrive in each period, and the demand unit must be matched immediately. We show that, despite the matching constraint and uncertainty about the future, cost nearly as small as the distance to the nearest neighbor is achievable in all cases *except* models (i) and (ii) for d=1 and M = o(N). Moreover, the latter is the only case in models (i) and (ii) where excess supply significantly reduces the achievable cost. In papers with Omar Besbes, Akshit Kumar and Yilun Chen, we introduce application-inspired variants of model (ii) in which the distributions of supply and demand can be different, and generate new algorithmic and scaling insights. Links to papers: Paper 1, Paper 2 and Paper 3. -
Entanglement Bootstrap and Remote Detectability
John McGreevy University of California, San Diego
The Entanglement Bootstrap is a program to derive the universal properties of a phase of matter from a single representative wavefunction on a topologically-trivial region. Much (perhaps all) of the structure of topological quantum field theory can be extracted starting from a state satisfying two axioms that implement the area law for entanglement. This talk will focus on recent progress (with Bowen Shi and Jin-Long Huang) using this approach to prove remote detectability of topological excitations in various dimensions. This is an axiom of topological field theory. Two key ideas are a quantum avatar of Kirby's torus trick to construct states on closed manifolds, and the new concept of pairing manifold, which is a closed manifold associated with a pair of conjugate excitation types that encodes their braiding matrix. The pairing manifold also produces Verlinde formulae relating the S-matrix to the structure constants of a generalized symmetry algebra of flexible operators.
Zoom link: https://pitp.zoom.us/j/92633473610?pwd=eEhqR3BaQXljQm5ScHZvZm81N2FyZz09
-
On the Electron Pairing Mechanism of Copper-Oxide High Temperature Superconductivity
Seamus Davis Cornell University
The elementary CuO2 plane sustaining cuprate high temperature superconductivity occurs typically at the base of a periodic array of edge-sharing CuO5 pyramids. Virtual transitions of electrons between adjacent planar Cu and O atoms, occurring at a rate t/ℏ and across the charge-transfer energy gap E, generate ‘superexchange’ spin-spin interactions of energy J≈4t4/E3 in an antiferromagnetic correlated-insulator state. However, hole doping this CuO2 plane converts this into a very high temperature superconducting state whose electron-pairing is exceptional. A leading proposal for the mechanism of this intense electron-pairing is that, while hole doping destroys magnetic order it preserves pair-forming superexchange interactions governed by the charge-transfer energy scale E.
To explore this hypothesis directly at atomic-scale, we developed high-voltage single-electron and electron-pair (Josephson) scanning tunneling microscopy, to visualize the interplay of E and the electron-pair density nP in Bi2Sr2CaCu2O8+x. Changing the distance δ between each pyramid’s apical O atom and the CuO2 plane below, should alter the energy levels of the planar Cu and O orbitals and thus vary E. Hence, the responses of both E and nP to alterations in δ that occur naturally in Bi2Sr2CaCu2O8+x were visualized. These data revealed, directly at atomic scale, the crux of strongly correlated superconductivity in CuO2: the response of the electron-pair condensate to varying the charge transfer energy. Strong concurrence between these observations and recent three-band Hubbard model DMFT predictions for superconductivity in hole-doped Bi2Sr2CaCu2O8+x (PNAS 118, e2106476118 (2021)) indicate that charge-transfer superexchange is the electron-pairing mechanism (PNAS 119, 2207449119 (2022)).
Zoom link: https://pitp.zoom.us/j/95592484157?pwd=YU56Wno3WnBIUTlyaC9VSHJ3cGxZUT09