Learning to Control Safety-Critical Systems
Adam Wierman (California Institute of Technology)
3301 - 3312 of 19364 Results
Format results
Near-Optimal No-Regret Learning for General Convex Games
Gabriele Farina (Carnegie Mellon University)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:22100050Relativity - Lecture 221014
PIRSA:22100077The 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
Learning to Control Safety-Critical Systems
Adam Wierman (California Institute of Technology)Making use of modern black-box AI tools such as deep reinforcement learning is potentially transformational for safety-critical systems such as data centers, the electricity grid, transportation, and beyond. However, such machine-learned algorithms typically do not have formal guarantees on their worst-case performance, stability, or safety and are typically difficult to make use of in distributed, networked settings. So, while their performance may improve upon traditional approaches in “typical” cases, they may perform arbitrarily worse in scenarios where the training examples are not representative due to, e.g., distribution shift, or in situations where global information is unavailable to local controllers. These represent significant drawbacks when considering the use of AI tools in safety-critical networked systems. Thus, a challenging open question emerges: Is it possible to provide guarantees that allow black-box AI tools to be used in safety-critical applications? In this talk, I will provide an overview of a variety of projects from my group that seek to develop robust and localizable tools combining model-free and model-based approaches to yield AI tools with formal guarantees on performance, stability, safety, and sample complexity.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.08742Bootstrapping 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:22100050Relativity - Lecture 221014
PIRSA:22100077The 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.13692Local 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=3924687Optimal 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