Talks

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

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

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

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

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.

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.  

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

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

Online allocation problems with resource constraints are central problems in revenue management and online advertising. In these problems, requests arrive sequentially during a finite horizon and, for each request, a decision maker needs to choose an action that consumes a certain amount of resources and generates reward. The objective is to maximize cumulative rewards subject to a constraint on the total consumption of resources. In this talk, we consider a data-driven setting in which the reward and resource consumption of each request are generated using an input model that is unknown to the decision maker. We design a general class of algorithms that attain good performance in various input models without knowing which type of input they are facing. In particular, our algorithms are asymptotically optimal under independent and identically distributed inputs as well as various non-stationary stochastic input models, and they attain an asymptotically optimal fixed competitive ratio when the input is adversarial. Our algorithms operate in the Lagrangian dual space: they maintain a dual multiplier for each resource that is updated using online algorithms, such as, online mirror descent and PI controller. Our proposed algorithms are simple, fast, robust to estimation errors, and do not require convexity in the revenue function, consumption function and action space, in contrast to existing methods for online allocation problems. The major motivation of this line of research is the applications to budget pacing in online advertising.

We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well-studied problems like the Adwords problem, online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case of online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.