### Big Data Conference 2023

On August 31-Sep 1, 2023 the CMSA will host the ninth annual Conference on Big...

Read More
Opens in a new window
Opens an external site
Opens an external site in a new window

On August 31-Sep 1, 2023 the CMSA will host the ninth annual Conference on Big...

Read MoreOn May 16 – May 19, 2023 the CMSA hosted a four-day workshop on GRAMSIA:...

Read MoreOn March 21, 2023, the CMSA will host the fourth annual Ding Shum Lecture, given...

Read MoreBig Data Conference 2023

«

»

Sun | Mon | Tue | Wed | Thu | Fri | Sat | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

April | 1 | 2 - Member SeminarCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**Member Seminar****Speaker:**Aghil Alaee**Title:**Toroidal Positive Mass Theorem**Abstract:**In this talk, we review the positive mass conjecture in general relativity and prove a toroidal version of this conjecture in an asymptotically hyperbolic setting.
| 3 - ColloquiaCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**Speaker:**Xin Guo, UC Berkeley**Title:**Generative Adversarial Networks (GANs): An Analytical Perspective**Abstract:**Generative models have attracted intense interests recently. In this talk, I will discuss one class of generative models, Generative Adversarial Networks (GANs). I will first provide a gentle review of the mathematical framework behind GANs. I will then proceed to discuss a few challenges in GANs training from an analytical perspective. I will finally report some recent progress for GANs training in terms of its stability and convergence analysis. - Probability SeminarCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**Probability Seminar****Speaker:**Boris Hanin (Princeton)**Title:**Random Neural Networks**Abstract:**Fully connected neural networks are described two by structural parameters: a depth L and a width N. In this talk, I will present results and open questions about the asymptotic analysis of such networks with random weights and biases in the regime where N (and potentially L) are large. The first set of results are for deep linear networks, which are simply products of L random matrices of size N x N. I’ll explain how the setting where the ratio L / N is fixed with both N and L large reveals a number of phenomena not present when only one of them is large. I will then state several results about non-linear networks in which this depth-to-width ratio L / N again plays a crucial role and gives an effective notion of depth for a random neural network.
| 4 - General Relativity SeminarCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**General Relativity Seminar****Speaker:**Vitor Cardoso, IST, Lisbon and The Niels Bohr Institute, Copenhagen**Title:**Testing GR with GWs**Abstract:**One of the most remarkable possibilities of General Relativity concerns gravitational collapse to black holes, leaving behind a geometry with light rings, ergoregions and horizons. These peculiarities are responsible for uniqueness properties and energy extraction mechanisms that turn black holes into ideal laboratories of strong gravity, of particle physics (yes!) and of possible quantum-gravity effects. I will discuss some of the latest progress in tests of General Relativity with black holes.
| 5 - Quantum Matter20 Garden Street, Cambridge MA 02138
**Quantum Matter Seminar****Speaker:**Sona Najafi (IBM Quantum)**Title:**Detecting central charge in a superconducting quantum processor**Abstract:**Physical systems at the continuous phase transition point exhibit conformal symmetry rendering local scaling invariance. In two dimensions, the conformal group possesses infinite generators described by Virasoro algebra with an essential parameter known as a central charge. While the central charge manifests itself in a variety of quantities, its detection in experimental setup remains elusive. In this work, we utilize Shannon-Renyi entropy on a local basis of a one-dimensional quantum spin chain at a critical point. We first use a simulated variational quantum eigen solver to prepare the ground state of the critical transfer field Ising model and XXZ model with open and periodic boundary conditions and perform local Pauli X and Z basis measurements. Using error mitigation such as probabilistic error cancellation, we extract an estimation of the local Pauli observables needed to determine the Shannon-Renyi entropy with respect to subsystem size. Finally, we obtain the central charge in the sub-leading term of Shannon-Renyi entropy.
| 6 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

7 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures**There will be three lectures on Thursday, May 11, 2023, which are open to the public. Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new.
| 8 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures**There will be three lectures on Thursday, May 11, 2023, which are open to the public. Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new.
| 9 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures**There will be three lectures on Thursday, May 11, 2023, which are open to the public. Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new.
| 10 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures** Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new. - New Technologies in Mathematics Seminar
**New Technologies in Mathematics Seminar****Speaker:**Dmitry Krotov, IBM Research – Cambridge**Title:**Modern Hopfield Networks for Novel Transformer Architectures**Abstract:**Modern Hopfield Networks or Dense Associative Memories are recurrent neural networks with fixed point attractor states that are described by an energy function. In contrast to conventional Hopfield Networks, which were popular in the 1980s, their modern versions have a very large memory storage capacity, which makes them appealing tools for many problems in machine learning and cognitive and neurosciences. In this talk, I will introduce an intuition and a mathematical formulation of this class of models and will give examples of problems in AI that can be tackled using these new ideas. Particularly, I will introduce an architecture called Energy Transformer, which replaces the conventional attention mechanism with a recurrent Dense Associative Memory model. I will explain the theoretical principles behind this architectural choice and show promising empirical results on challenging computer vision and graph network tasks.
| 11 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures** Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new. - Active Matter SeminarJefferson Hal Room 256, 17 Oxford Street, Cambridge MA 02138
**Active Matter Seminar****Speaker**: Sahand Hormoz, Harvard Medical School, Dana-Farber Cancer Institute**Title:**Insights from single cell lineage trees**Abstract:**In this talk, I will discuss two recent projects from my lab that involve lineage trees of cells (the branching diagram that represents the ancestry and division history of individual cells). In the first project, we reconstructed the lineage trees of individual cancer cells from the patterns of randomly occurring mutations in these cells. We then inferred the age at which the cancer mutation first occurred and the rate of expansion of the population of cancer cells within each patient. To our surprise, we discovered that the cancer mutation occurs decades before diagnosis. For the second project, we developed microfluidic ‘mother machines’ that allow us to observe mammalian cells dividing across tens of generations. Using our observations, we calculated the correlation between the duration of cell cycle phases in pairs of cells, as a function of their lineage distance. These correlations revealed many surprises that we are trying to understand using hidden Markov models on trees. For both projects, I will discuss the mathematical challenges that we have faced and open problems related to inference from lineage trees. - General Relativity Seminar
**General Relativity Seminar****Speaker:**Aghil Alaee, Clark University**Title:**Positivity of Static quasi-local Mass in general relativity**Abstract:**In this talk, we review results on the PMT of quasi-local masses and prove the positivity of static quasi-local masses with respect to the AdS and AdS Schwarzschild spacetimes. - Probability Seminar1 Oxford Street, Cambridge MA 02138
**Probability Seminar****Speaker:**Giorgio Cipolloni (Princeton)**Title:**How do the eigenvalues of a large non-Hermitian random matrix behave?**Abstract:**We prove that the fluctuations of the eigenvalues converge to the Gaussian Free Field (GFF) on the unit disk. These fluctuations appear on a non-natural scale, due to strong correlations between the eigenvalues. Then, motivated by the long time behaviour of the ODE \dot{u}=Xu, we give a precise estimate on the eigenvalue with the largest real part and on the spectral radius of X.**Location:**Science Center Room 232 - More events
- WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures** Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new. - Active Matter SeminarJefferson Hal Room 256, 17 Oxford Street, Cambridge MA 02138
**Active Matter Seminar****Speaker**: Sahand Hormoz, Harvard Medical School, Dana-Farber Cancer Institute**Title:**Insights from single cell lineage trees**Abstract:**In this talk, I will discuss two recent projects from my lab that involve lineage trees of cells (the branching diagram that represents the ancestry and division history of individual cells). In the first project, we reconstructed the lineage trees of individual cancer cells from the patterns of randomly occurring mutations in these cells. We then inferred the age at which the cancer mutation first occurred and the rate of expansion of the population of cancer cells within each patient. To our surprise, we discovered that the cancer mutation occurs decades before diagnosis. For the second project, we developed microfluidic ‘mother machines’ that allow us to observe mammalian cells dividing across tens of generations. Using our observations, we calculated the correlation between the duration of cell cycle phases in pairs of cells, as a function of their lineage distance. These correlations revealed many surprises that we are trying to understand using hidden Markov models on trees. For both projects, I will discuss the mathematical challenges that we have faced and open problems related to inference from lineage trees. - General Relativity Seminar
**General Relativity Seminar****Speaker:**Aghil Alaee, Clark University**Title:**Positivity of Static quasi-local Mass in general relativity**Abstract:**In this talk, we review results on the PMT of quasi-local masses and prove the positivity of static quasi-local masses with respect to the AdS and AdS Schwarzschild spacetimes. - Probability Seminar1 Oxford Street, Cambridge MA 02138
**Probability Seminar****Speaker:**Giorgio Cipolloni (Princeton)**Title:**How do the eigenvalues of a large non-Hermitian random matrix behave?**Abstract:**We prove that the fluctuations of the eigenvalues converge to the Gaussian Free Field (GFF) on the unit disk. These fluctuations appear on a non-natural scale, due to strong correlations between the eigenvalues. Then, motivated by the long time behaviour of the ODE \dot{u}=Xu, we give a precise estimate on the eigenvalue with the largest real part and on the spectral radius of X.**Location:**Science Center Room 232
- Workshop
| 12 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
The CMSA will be hosting a **Workshop on Global Categorical Symmetries**from May 7 – 12, 2023Participation in the workshop is by invitation. **Public Lectures** Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138 Note: The public lectures will be held in-person only.**2:00 – 2:50 pm****Speaker:**Kantaro Ohmori (U Tokyo )**Title:**Fusion Surface Models: 2+1d Lattice Models from Higher Categories**Abstract:**Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.**3:00 – 3:50 pm****Speaker:**David Jordan (Edinburgh)**Title:**Langlands duality for 3-manifolds**Abstract:**Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.**3:50 – 4:30 pm****Tea/Snack Break****4:30 – 5:30 pm****Speaker:**Ken Intriligator (UCSD)**Colloquium****Title:**QFT Aspects of Symmetry**Abstract:**Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new. - Quantum Matter
**Quantum Matter Seminar****Speaker:**Carolyn Zhang (U Chicago)**Title:**Anomalies of (1+1)D categorical symmetries**Abstract:**We present a general approach for detecting when a fusion category symmetry is anomalous, based on the existence of a special kind of Lagrangian algebra of the corresponding Drinfeld center. The Drinfeld center of a fusion category $A$ describes a $(2+1)D$ topological order whose gapped boundaries enumerate all $(1+1)D$ gapped phases with the fusion category symmetry, which may be spontaneously broken. There always exists a gapped boundary, given by the \emph{electric} Lagrangian algebra, that describes a phase with $A$ fully spontaneously broken. The symmetry defects of this boundary can be identified with the objects in $A$. We observe that if there exists a different gapped boundary, given by a \emph{magnetic} Lagrangian algebra, then there exists a gapped phase where $A$ is not spontaneously broken at all, which means that $A$ is not anomalous. In certain cases, we show that requiring the existence of such a magnetic Lagrangian algebra leads to highly computable obstructions to $A$ being anomaly-free. As an application, we consider the Drinfeld centers of $\mathbb{Z}_N\times\mathbb{Z}_N$ Tambara-Yamagami fusion categories and recover known results from the study of fiber functors.
| 13 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

14 | 15 - Member SeminarCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**Member Seminar****Speaker:**Gabriel Wong**Title:**Quantum information and extended topological quantum field theory**Abstract:**Recently, ideas from quantum information theory have played an important role in condensed matter and quantum gravity research. Most of these applications focus on the entanglement structure of quantum states, and the computation of entanglement measures such as entanglement entropy has been an essential part of the story. In this talk, we will address some subtleties that arise when trying to define entanglement entropy in quantum field theory and quantum gravity. In particular, we will explain why extended topological field theory provides a useful framework to define and compute entanglement entropy in a continuous system. Time permitting, we will explain some recent applications of these ideas in low dimensional quantum gravity and to topological string theory.
| 16 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
On May 16 – May 19, 2023 the CMSA hosted a four-day workshop on **GRAMSIA: Graphical Models, Statistical Inference, and Algorithms**. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA. This workshop was organized by David Gamarnik (MIT), Kavita Ramanan (Brown), and Prasad Tetali (Carnegie Mellon).The purpose of this workshop is to highlight various mathematical questions and issues associated with graphical models and message-passing algorithms, and to bring together a group of researchers for discussion of the latest progress and challenges ahead. In addition to the substantial impact of graphical models on applied areas, they are also connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal is to highlight and deepen these mathematical connections. **Location:**Room G10, CMSA, 20 Garden Street, Cambridge MA 02138**Speakers:**- Jake Abernethy (Georgia Tech)
- Guy Bresler (MIT)
- Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
- Lester Mackey (Microsoft Research New England)
- Theo McKenzie (Harvard)
- Andrea Montanari (Stanford)
- Elchanan Mossel (MIT)
- Yury Polyanskiy (MIT)
- Patrick Rebeschini (Oxford)
- Subhabrata Sen (Harvard)
- Devavrat Shah (MIT)
- Pragya Sur (Harvard)
- Alex Wein (UC Davis)
- Yihong Wu (Yale)
- Sarath Yasodharan (Brown)
- Horng-Tzer Yau (Harvard)
- Christina Lee Yu (Cornell)
- Ilias Zadik (MIT)
**Schedule:****Tuesday, May 16, 2023**9:00 am *Breakfast*9:15 – 9:30 am Introductory remarks by organizers 9:30 – 10:20 am Subhabrata Sen (Harvard) **Title:**Mean-field approximations for high-dimensional Bayesian regression**Abstract:**Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. The Naive Mean-Field (NMF) approximation is the simplest version of this strategy—this approach approximates the posterior in KL divergence by a product distribution. There has been considerable progress recently in understanding the accuracy of NMF under structural constraints such as sparsity, but not much is known in the absence of such constraints. Moreover, in some high-dimensional settings, the NMF is expected to be grossly inaccurate, and advanced mean-field techniques (e.g. Bethe approximation) are expected to provide accurate approximations. We will present some recent work in understanding this duality in the context of high-dimensional regression. This is based on joint work with Sumit Mukherjee (Columbia) and Jiaze Qiu (Harvard University).10:30 – 11:00 am *Coffee break*11:00 – 11:50 am Elchanan Mossel (MIT) **Title:**Some modern perspectives on the Kesten-Stigum bound for reconstruction on trees.**Abstract:**The Kesten-Stigum bound is a fundamental spectral bound for reconstruction on trees. I will discuss some conjectures and recent progress on understanding when it is tight as well as some conjectures and recent progress on what it signifies even in cases where it is not tight.12:00 – 2:00 pm Lunch 2:00 – 2:50 pm Christina Lee Yu (Cornell) **Title:**Exploiting Neighborhood Interference with Low Order Interactions under Unit Randomized Design**Abstract:**Network interference, where the outcome of an individual is affected by the treatment assignment of those in their social network, is pervasive in many real-world settings. However, it poses a challenge to estimating causal effects. We consider the task of estimating the total treatment effect (TTE), or the difference between the average outcomes of the population when everyone is treated versus when no one is, under network interference. Under a Bernoulli randomized design, we utilize knowledge of the network structure to provide an unbiased estimator for the TTE when network interference effects are constrained to low order interactions among neighbors of an individual. We make no assumptions on the graph other than bounded degree, allowing for well-connected networks that may not be easily clustered. Central to our contribution is a new framework for balancing between model flexibility and statistical complexity as captured by this low order interactions structure.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Theo McKenzie (Harvard) **Title:**Spectral statistics for sparse random graphs**Abstract:**Understanding the eigenvectors and eigenvalues of the adjacency matrix of random graphs is fundamental to many algorithmic questions; moreover, it is related to longstanding questions in quantum physics. In this talk we focus on random models of sparse graphs, giving some properties that are unique to these sparse graphs, as well as some specific obstacles. Based on this, we show some new results on spectral statistics of sparse random graphs, as well as some conjectures.4:40 – 6:30 pm Lightning talk session + welcome reception **Wednesday, May 17, 2023**9:00 am *Breakfast*9:30 – 10:20 Ilias Zadik (MIT) **Title:**Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem**Abstract:**Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992.10:30 – 11:00 *Coffee break*11:00 – 11:50 Florent Krzakala (Ecole Polytechnique Federale de Lausanne) **Title:**Are Gaussian data all you need for machine learning theory?**Abstract:**Clearly, no! Nevertheless, the Gaussian assumption remains prevalent among theoreticians, particularly in high-dimensional statistics and physics, less so in traditional statistical learning circles. To what extent are Gaussian features merely a convenient choice for certain theoreticians, or genuinely an effective model for learning? In this talk, I will review recent progress on these questions, achieved using rigorous probabilistic approaches in high-dimension and techniques from mathematical statistical physics. I will demonstrate that, despite its apparent limitations, the Gaussian approach is sometimes much closer to reality than one might expect. In particular, I will discuss key findings from a series of recent papers that showcase the Gaussian equivalence of generative models, the universality of Gaussian mixtures, and the conditions under which a single Gaussian can characterize the error in high-dimensional estimation. These results illuminate the strengths and weaknesses of the Gaussian assumption, shedding light on its applicability and limitations in the realm of theoretical statistical learning.12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Andrea Montanari (Stanford) **Title:**Dimension free ridge regression**Abstract:**Random matrix theory has become a widely useful tool in high-dimensional statistics and theoretical machine learning. However, random matrix theory is largely focused on the proportional asymptotics in which the number of columns grows proportionally to the number of rows of the data matrix. This is not always the most natural setting in statistics where columns correspond to covariates and rows to samples. With the objective to move beyond the proportional asymptotics, we revisit ridge regression. We allow the feature vector to be high-dimensional, or even infinite-dimensional, in which case it belongs to a separable Hilbert space and assume it to satisfy a certain convex concentration property. Within this setting, we establish non-asymptotic bounds that approximate the bias and variance of ridge regression in terms of the bias and variance of an ‘equivalent’ sequence model (a regression model with diagonal design matrix). Previously, such an approximation result was known only in the proportional regime and only up to additive errors: in particular, it did not allow to characterize the behavior of the excess risk when this converges to 0. Our general theory recovers earlier results in the proportional regime (with better error rates). As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum. Finally, we analyze the overparametrized near-interpolation setting and obtain sharp ‘benign overfitting’ guarantees.[Based on joint work with Chen Cheng] 3:00 – 3:50 pm Yury Polyanskiy (MIT) **Title:**Recent results on broadcasting on trees and stochastic block model**Abstract:**I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q>2 uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT). 4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Alex Wein (UC Davis) **Title:**Is Planted Coloring Easier than Planted Clique?**Abstract:**The task of finding a planted clique in the random graph G(n,1/2) is perhaps the canonical example of a statistical-computational gap: for some clique sizes, the task is statistically possible but believed to be computationally hard. Really, there are multiple well-studied tasks related to the planted clique model: detection, recovery, and refutation. While these are equally difficult in the case of planted clique, this need not be true in general. In the related planted coloring model, I will discuss the computational complexity of these three tasks and the interplay among them. Our computational hardness results are based on the low-degree polynomial model of computation.By taking the complement of the graph, the planted coloring model is analogous to the planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.**Thursday, May 18, 2023**9:00 *Breakfast*9:30 – 10:20 Guy Bresler (MIT) **Title:**Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs**Abstract:**There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. We develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. As a concrete instance of our general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). Joint work with Chenghao Guo and Yury Polyanskiy.10:30 – 11:00 *Coffee break*11:00 – 11:50 Sarath Yasodharan (Brown) **Title:**A Sanov-type theorem for unimodular marked random graphs and its applications**Abstract:**We prove a Sanov-type large deviation principle for the component empirical measures of certain sequences of unimodular random graphs (including Erdos-Renyi and random regular graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropy functionals. As a corollary, we establish a variational formula for the annealed pressure (or limiting log partition function) for various statistical physics models on sparse random graphs. This is joint work with I-Hsun Chen and Kavita Ramanan.12:00 – 12:15 pm 12:15 – 2:00 pm *Group Photo**Lunch*2:00 – 2:50 pm Patrick Rebeschini (Oxford) **Title:**Implicit regularization via uniform convergence**Abstract:**Uniform convergence is one of the main tools to analyze the complexity of learning algorithms based on explicit regularization, but it has shown limited applicability in the context of implicit regularization. In this talk, we investigate the statistical guarantees on the excess risk achieved by early-stopped mirror descent run on the unregularized empirical risk with the squared loss for linear models and kernel methods. We establish a direct link between the potential-based analysis of mirror descent from optimization theory and uniform learning. This link allows characterizing the statistical performance of the path traced by mirror descent directly in terms of localized Rademacher complexities of function classes depending on the choice of the mirror map, initialization point, step size, and the number of iterations. We will discuss other results along the way.3:00 – 3:50 pm Pragya Sur (Harvard) **Title:**A New Central Limit Theorem for the Augmented IPW estimator in high dimensions**Abstract:**Estimating the average treatment effect (ATE) is a central problem in causal inference. Modern advances in the field studied estimation and inference for the ATE in high dimensions through a variety of approaches. Doubly robust estimators such as the augmented inverse probability weighting (AIPW) form a popular approach in this context. However, the high-dimensional literature surrounding these estimators relies on sparsity conditions, either on the outcome regression (OR) or the propensity score (PS) model. This talk will introduce a new central limit theorem for the classical AIPW estimator, that applies agnostic to such sparsity-type assumptions. Specifically, we will study properties of the cross-fit version of the estimator under well-specified OR and PS models, and the proportional asymptotics regime where the number of confounders and sample size diverge proportional to each other. Under assumptions on the covariate distribution, our CLT will uncover two crucial phenomena among others: (i) the cross-fit AIPW exhibits a substantial variance inflation that can be quantified in terms of the signal-to-noise ratio and other problem parameters, (ii) the asymptotic covariance between the estimators used while cross-fitting is non-negligible even on the root-n scale. These findings are strikingly different from their classical counterparts, and open a vista of possibilities for studying similar other high-dimensional effects. On the technical front, our work utilizes a novel interplay between three distinct tools—approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Yihong Wu (Yale) **Title:**Random graph matching at Otter’s threshold via counting chandeliers**Abstract:**We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq\to\infty and the edge correlation coefficient ρ satisfies ρ^2>α≈0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. This is joint work with Cheng Mao, Jiaming Xu, and Sophie Yu, available at https://arxiv.org/abs/2209.12313**Friday, May 19, 2023**9:00 *Breakfast*9:30 – 10:20 Jake Abernethy (Georgia Tech) **Title:**Optimization, Learning, and Margin-maximization via Playing Games**Abstract:**A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, including optimization, learning, and margin-maximiation problems. Along the way we will encounter a number of novel tools and rediscover some classical ones as well.10:30 – 11:00 *Coffee break*11:00 – 11:50 Devavrat Shah (MIT) **Title:**On counterfactual inference with unobserved confounding via exponential family**Abstract:**We are interested in the problem of unit-level counterfactual inference with unobserved confounders owing to the increasing importance of personalized decision-making in many domains: consider a recommender system interacting with a user over time where each user is provided recommendations based on observed demographics, prior engagement levels as well as certain unobserved factors. The system adapts its recommendations sequentially and differently for each user. Ideally, at each point in time, the system wants to infer each user’s unknown engagement if it were exposed to a different sequence of recommendations while everything else remained unchanged. This task is challenging since: (a) the unobserved factors could give rise to spurious associations, (b) the users could be heterogeneous, and (c) only a single trajectory per user is available.We model the underlying joint distribution through an exponential family. This reduces the task of unit-level counterfactual inference to simultaneously learning a collection of distributions of a given exponential family with different unknown parameters with single observation per distribution. We discuss a computationally efficient method for learning all of these parameters with estimation error scaling linearly with the metric entropy of the space of unknown parameters – if the parameters are an s-sparse linear combination of k known vectors in p dimension, the error scales as O(s log k/p). En route, we derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality. Based on a joint work with Raaz Dwivedi, Abhin Shah and Greg Wornell (all at MIT) with manuscript available here: https://arxiv.org/abs/2211.08209 12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Lester Mackey (Microsoft Research New England) **Title:**Advances in Distribution Compression**Abstract:**This talk will introduce two new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning: 1. Given an initial n-point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n-points with comparable worst-case integration error across a reproducing kernel Hilbert space. 2. If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases. These tools are especially well-suited for tasks that incur substantial downstream computation costs per summary point like organ and tissue modeling in which each simulation consumes 1000s of CPU hours. Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Horng-Tzer Yau (Harvard) **Title:**On the spectral gap of mean-field spin glass models.**Abstract:**We will discuss recent progress regarding spectral gaps for the Glauber dynamics of spin glasses at high temperature. In addition, we will also report on estimating the operator norm of the covariance matrix for the SK model.**Moderators:**Benjamin McKenna, Harvard CMSA & Changji Xu, Harvard CMSA
| 17 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
On May 16 – May 19, 2023 the CMSA hosted a four-day workshop on **GRAMSIA: Graphical Models, Statistical Inference, and Algorithms**. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA. This workshop was organized by David Gamarnik (MIT), Kavita Ramanan (Brown), and Prasad Tetali (Carnegie Mellon).The purpose of this workshop is to highlight various mathematical questions and issues associated with graphical models and message-passing algorithms, and to bring together a group of researchers for discussion of the latest progress and challenges ahead. In addition to the substantial impact of graphical models on applied areas, they are also connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal is to highlight and deepen these mathematical connections. **Location:**Room G10, CMSA, 20 Garden Street, Cambridge MA 02138**Speakers:**- Jake Abernethy (Georgia Tech)
- Guy Bresler (MIT)
- Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
- Lester Mackey (Microsoft Research New England)
- Theo McKenzie (Harvard)
- Andrea Montanari (Stanford)
- Elchanan Mossel (MIT)
- Yury Polyanskiy (MIT)
- Patrick Rebeschini (Oxford)
- Subhabrata Sen (Harvard)
- Devavrat Shah (MIT)
- Pragya Sur (Harvard)
- Alex Wein (UC Davis)
- Yihong Wu (Yale)
- Sarath Yasodharan (Brown)
- Horng-Tzer Yau (Harvard)
- Christina Lee Yu (Cornell)
- Ilias Zadik (MIT)
**Schedule:****Tuesday, May 16, 2023**9:00 am *Breakfast*9:15 – 9:30 am Introductory remarks by organizers 9:30 – 10:20 am Subhabrata Sen (Harvard) **Title:**Mean-field approximations for high-dimensional Bayesian regression**Abstract:**Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. The Naive Mean-Field (NMF) approximation is the simplest version of this strategy—this approach approximates the posterior in KL divergence by a product distribution. There has been considerable progress recently in understanding the accuracy of NMF under structural constraints such as sparsity, but not much is known in the absence of such constraints. Moreover, in some high-dimensional settings, the NMF is expected to be grossly inaccurate, and advanced mean-field techniques (e.g. Bethe approximation) are expected to provide accurate approximations. We will present some recent work in understanding this duality in the context of high-dimensional regression. This is based on joint work with Sumit Mukherjee (Columbia) and Jiaze Qiu (Harvard University).10:30 – 11:00 am *Coffee break*11:00 – 11:50 am Elchanan Mossel (MIT) **Title:**Some modern perspectives on the Kesten-Stigum bound for reconstruction on trees.**Abstract:**The Kesten-Stigum bound is a fundamental spectral bound for reconstruction on trees. I will discuss some conjectures and recent progress on understanding when it is tight as well as some conjectures and recent progress on what it signifies even in cases where it is not tight.12:00 – 2:00 pm Lunch 2:00 – 2:50 pm Christina Lee Yu (Cornell) **Title:**Exploiting Neighborhood Interference with Low Order Interactions under Unit Randomized Design**Abstract:**Network interference, where the outcome of an individual is affected by the treatment assignment of those in their social network, is pervasive in many real-world settings. However, it poses a challenge to estimating causal effects. We consider the task of estimating the total treatment effect (TTE), or the difference between the average outcomes of the population when everyone is treated versus when no one is, under network interference. Under a Bernoulli randomized design, we utilize knowledge of the network structure to provide an unbiased estimator for the TTE when network interference effects are constrained to low order interactions among neighbors of an individual. We make no assumptions on the graph other than bounded degree, allowing for well-connected networks that may not be easily clustered. Central to our contribution is a new framework for balancing between model flexibility and statistical complexity as captured by this low order interactions structure.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Theo McKenzie (Harvard) **Title:**Spectral statistics for sparse random graphs**Abstract:**Understanding the eigenvectors and eigenvalues of the adjacency matrix of random graphs is fundamental to many algorithmic questions; moreover, it is related to longstanding questions in quantum physics. In this talk we focus on random models of sparse graphs, giving some properties that are unique to these sparse graphs, as well as some specific obstacles. Based on this, we show some new results on spectral statistics of sparse random graphs, as well as some conjectures.4:40 – 6:30 pm Lightning talk session + welcome reception **Wednesday, May 17, 2023**9:00 am *Breakfast*9:30 – 10:20 Ilias Zadik (MIT) **Title:**Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem**Abstract:**Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992.10:30 – 11:00 *Coffee break*11:00 – 11:50 Florent Krzakala (Ecole Polytechnique Federale de Lausanne) **Title:**Are Gaussian data all you need for machine learning theory?**Abstract:**Clearly, no! Nevertheless, the Gaussian assumption remains prevalent among theoreticians, particularly in high-dimensional statistics and physics, less so in traditional statistical learning circles. To what extent are Gaussian features merely a convenient choice for certain theoreticians, or genuinely an effective model for learning? In this talk, I will review recent progress on these questions, achieved using rigorous probabilistic approaches in high-dimension and techniques from mathematical statistical physics. I will demonstrate that, despite its apparent limitations, the Gaussian approach is sometimes much closer to reality than one might expect. In particular, I will discuss key findings from a series of recent papers that showcase the Gaussian equivalence of generative models, the universality of Gaussian mixtures, and the conditions under which a single Gaussian can characterize the error in high-dimensional estimation. These results illuminate the strengths and weaknesses of the Gaussian assumption, shedding light on its applicability and limitations in the realm of theoretical statistical learning.12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Andrea Montanari (Stanford) **Title:**Dimension free ridge regression**Abstract:**Random matrix theory has become a widely useful tool in high-dimensional statistics and theoretical machine learning. However, random matrix theory is largely focused on the proportional asymptotics in which the number of columns grows proportionally to the number of rows of the data matrix. This is not always the most natural setting in statistics where columns correspond to covariates and rows to samples. With the objective to move beyond the proportional asymptotics, we revisit ridge regression. We allow the feature vector to be high-dimensional, or even infinite-dimensional, in which case it belongs to a separable Hilbert space and assume it to satisfy a certain convex concentration property. Within this setting, we establish non-asymptotic bounds that approximate the bias and variance of ridge regression in terms of the bias and variance of an ‘equivalent’ sequence model (a regression model with diagonal design matrix). Previously, such an approximation result was known only in the proportional regime and only up to additive errors: in particular, it did not allow to characterize the behavior of the excess risk when this converges to 0. Our general theory recovers earlier results in the proportional regime (with better error rates). As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum. Finally, we analyze the overparametrized near-interpolation setting and obtain sharp ‘benign overfitting’ guarantees.[Based on joint work with Chen Cheng] 3:00 – 3:50 pm Yury Polyanskiy (MIT) **Title:**Recent results on broadcasting on trees and stochastic block model**Abstract:**I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q>2 uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT). 4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Alex Wein (UC Davis) **Title:**Is Planted Coloring Easier than Planted Clique?**Abstract:**The task of finding a planted clique in the random graph G(n,1/2) is perhaps the canonical example of a statistical-computational gap: for some clique sizes, the task is statistically possible but believed to be computationally hard. Really, there are multiple well-studied tasks related to the planted clique model: detection, recovery, and refutation. While these are equally difficult in the case of planted clique, this need not be true in general. In the related planted coloring model, I will discuss the computational complexity of these three tasks and the interplay among them. Our computational hardness results are based on the low-degree polynomial model of computation.By taking the complement of the graph, the planted coloring model is analogous to the planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.**Thursday, May 18, 2023**9:00 *Breakfast*9:30 – 10:20 Guy Bresler (MIT) **Title:**Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs**Abstract:**There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. We develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. As a concrete instance of our general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). Joint work with Chenghao Guo and Yury Polyanskiy.10:30 – 11:00 *Coffee break*11:00 – 11:50 Sarath Yasodharan (Brown) **Title:**A Sanov-type theorem for unimodular marked random graphs and its applications**Abstract:**We prove a Sanov-type large deviation principle for the component empirical measures of certain sequences of unimodular random graphs (including Erdos-Renyi and random regular graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropy functionals. As a corollary, we establish a variational formula for the annealed pressure (or limiting log partition function) for various statistical physics models on sparse random graphs. This is joint work with I-Hsun Chen and Kavita Ramanan.12:00 – 12:15 pm 12:15 – 2:00 pm *Group Photo**Lunch*2:00 – 2:50 pm Patrick Rebeschini (Oxford) **Title:**Implicit regularization via uniform convergence**Abstract:**Uniform convergence is one of the main tools to analyze the complexity of learning algorithms based on explicit regularization, but it has shown limited applicability in the context of implicit regularization. In this talk, we investigate the statistical guarantees on the excess risk achieved by early-stopped mirror descent run on the unregularized empirical risk with the squared loss for linear models and kernel methods. We establish a direct link between the potential-based analysis of mirror descent from optimization theory and uniform learning. This link allows characterizing the statistical performance of the path traced by mirror descent directly in terms of localized Rademacher complexities of function classes depending on the choice of the mirror map, initialization point, step size, and the number of iterations. We will discuss other results along the way.3:00 – 3:50 pm Pragya Sur (Harvard) **Title:**A New Central Limit Theorem for the Augmented IPW estimator in high dimensions**Abstract:**Estimating the average treatment effect (ATE) is a central problem in causal inference. Modern advances in the field studied estimation and inference for the ATE in high dimensions through a variety of approaches. Doubly robust estimators such as the augmented inverse probability weighting (AIPW) form a popular approach in this context. However, the high-dimensional literature surrounding these estimators relies on sparsity conditions, either on the outcome regression (OR) or the propensity score (PS) model. This talk will introduce a new central limit theorem for the classical AIPW estimator, that applies agnostic to such sparsity-type assumptions. Specifically, we will study properties of the cross-fit version of the estimator under well-specified OR and PS models, and the proportional asymptotics regime where the number of confounders and sample size diverge proportional to each other. Under assumptions on the covariate distribution, our CLT will uncover two crucial phenomena among others: (i) the cross-fit AIPW exhibits a substantial variance inflation that can be quantified in terms of the signal-to-noise ratio and other problem parameters, (ii) the asymptotic covariance between the estimators used while cross-fitting is non-negligible even on the root-n scale. These findings are strikingly different from their classical counterparts, and open a vista of possibilities for studying similar other high-dimensional effects. On the technical front, our work utilizes a novel interplay between three distinct tools—approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Yihong Wu (Yale) **Title:**Random graph matching at Otter’s threshold via counting chandeliers**Abstract:**We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq\to\infty and the edge correlation coefficient ρ satisfies ρ^2>α≈0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. This is joint work with Cheng Mao, Jiaming Xu, and Sophie Yu, available at https://arxiv.org/abs/2209.12313**Friday, May 19, 2023**9:00 *Breakfast*9:30 – 10:20 Jake Abernethy (Georgia Tech) **Title:**Optimization, Learning, and Margin-maximization via Playing Games**Abstract:**A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, including optimization, learning, and margin-maximiation problems. Along the way we will encounter a number of novel tools and rediscover some classical ones as well.10:30 – 11:00 *Coffee break*11:00 – 11:50 Devavrat Shah (MIT) **Title:**On counterfactual inference with unobserved confounding via exponential family**Abstract:**We are interested in the problem of unit-level counterfactual inference with unobserved confounders owing to the increasing importance of personalized decision-making in many domains: consider a recommender system interacting with a user over time where each user is provided recommendations based on observed demographics, prior engagement levels as well as certain unobserved factors. The system adapts its recommendations sequentially and differently for each user. Ideally, at each point in time, the system wants to infer each user’s unknown engagement if it were exposed to a different sequence of recommendations while everything else remained unchanged. This task is challenging since: (a) the unobserved factors could give rise to spurious associations, (b) the users could be heterogeneous, and (c) only a single trajectory per user is available.We model the underlying joint distribution through an exponential family. This reduces the task of unit-level counterfactual inference to simultaneously learning a collection of distributions of a given exponential family with different unknown parameters with single observation per distribution. We discuss a computationally efficient method for learning all of these parameters with estimation error scaling linearly with the metric entropy of the space of unknown parameters – if the parameters are an s-sparse linear combination of k known vectors in p dimension, the error scales as O(s log k/p). En route, we derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality. Based on a joint work with Raaz Dwivedi, Abhin Shah and Greg Wornell (all at MIT) with manuscript available here: https://arxiv.org/abs/2211.08209 12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Lester Mackey (Microsoft Research New England) **Title:**Advances in Distribution Compression**Abstract:**This talk will introduce two new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning: 1. Given an initial n-point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n-points with comparable worst-case integration error across a reproducing kernel Hilbert space. 2. If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases. These tools are especially well-suited for tasks that incur substantial downstream computation costs per summary point like organ and tissue modeling in which each simulation consumes 1000s of CPU hours. Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Horng-Tzer Yau (Harvard) **Title:**On the spectral gap of mean-field spin glass models.**Abstract:**We will discuss recent progress regarding spectral gaps for the Glauber dynamics of spin glasses at high temperature. In addition, we will also report on estimating the operator norm of the covariance matrix for the SK model.**Moderators:**Benjamin McKenna, Harvard CMSA & Changji Xu, Harvard CMSA
| 18 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
On May 16 – May 19, 2023 the CMSA hosted a four-day workshop on **GRAMSIA: Graphical Models, Statistical Inference, and Algorithms**. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA. This workshop was organized by David Gamarnik (MIT), Kavita Ramanan (Brown), and Prasad Tetali (Carnegie Mellon).The purpose of this workshop is to highlight various mathematical questions and issues associated with graphical models and message-passing algorithms, and to bring together a group of researchers for discussion of the latest progress and challenges ahead. In addition to the substantial impact of graphical models on applied areas, they are also connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal is to highlight and deepen these mathematical connections. **Location:**Room G10, CMSA, 20 Garden Street, Cambridge MA 02138**Speakers:**- Jake Abernethy (Georgia Tech)
- Guy Bresler (MIT)
- Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
- Lester Mackey (Microsoft Research New England)
- Theo McKenzie (Harvard)
- Andrea Montanari (Stanford)
- Elchanan Mossel (MIT)
- Yury Polyanskiy (MIT)
- Patrick Rebeschini (Oxford)
- Subhabrata Sen (Harvard)
- Devavrat Shah (MIT)
- Pragya Sur (Harvard)
- Alex Wein (UC Davis)
- Yihong Wu (Yale)
- Sarath Yasodharan (Brown)
- Horng-Tzer Yau (Harvard)
- Christina Lee Yu (Cornell)
- Ilias Zadik (MIT)
**Schedule:****Tuesday, May 16, 2023**9:00 am *Breakfast*9:15 – 9:30 am Introductory remarks by organizers 9:30 – 10:20 am Subhabrata Sen (Harvard) **Title:**Mean-field approximations for high-dimensional Bayesian regression**Abstract:**Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. The Naive Mean-Field (NMF) approximation is the simplest version of this strategy—this approach approximates the posterior in KL divergence by a product distribution. There has been considerable progress recently in understanding the accuracy of NMF under structural constraints such as sparsity, but not much is known in the absence of such constraints. Moreover, in some high-dimensional settings, the NMF is expected to be grossly inaccurate, and advanced mean-field techniques (e.g. Bethe approximation) are expected to provide accurate approximations. We will present some recent work in understanding this duality in the context of high-dimensional regression. This is based on joint work with Sumit Mukherjee (Columbia) and Jiaze Qiu (Harvard University).10:30 – 11:00 am *Coffee break*11:00 – 11:50 am Elchanan Mossel (MIT) **Title:**Some modern perspectives on the Kesten-Stigum bound for reconstruction on trees.**Abstract:**The Kesten-Stigum bound is a fundamental spectral bound for reconstruction on trees. I will discuss some conjectures and recent progress on understanding when it is tight as well as some conjectures and recent progress on what it signifies even in cases where it is not tight.12:00 – 2:00 pm Lunch 2:00 – 2:50 pm Christina Lee Yu (Cornell) **Title:**Exploiting Neighborhood Interference with Low Order Interactions under Unit Randomized Design**Abstract:**Network interference, where the outcome of an individual is affected by the treatment assignment of those in their social network, is pervasive in many real-world settings. However, it poses a challenge to estimating causal effects. We consider the task of estimating the total treatment effect (TTE), or the difference between the average outcomes of the population when everyone is treated versus when no one is, under network interference. Under a Bernoulli randomized design, we utilize knowledge of the network structure to provide an unbiased estimator for the TTE when network interference effects are constrained to low order interactions among neighbors of an individual. We make no assumptions on the graph other than bounded degree, allowing for well-connected networks that may not be easily clustered. Central to our contribution is a new framework for balancing between model flexibility and statistical complexity as captured by this low order interactions structure.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Theo McKenzie (Harvard) **Title:**Spectral statistics for sparse random graphs**Abstract:**Understanding the eigenvectors and eigenvalues of the adjacency matrix of random graphs is fundamental to many algorithmic questions; moreover, it is related to longstanding questions in quantum physics. In this talk we focus on random models of sparse graphs, giving some properties that are unique to these sparse graphs, as well as some specific obstacles. Based on this, we show some new results on spectral statistics of sparse random graphs, as well as some conjectures.4:40 – 6:30 pm Lightning talk session + welcome reception **Wednesday, May 17, 2023**9:00 am *Breakfast*9:30 – 10:20 Ilias Zadik (MIT) **Title:**Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem**Abstract:**Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992.10:30 – 11:00 *Coffee break*11:00 – 11:50 Florent Krzakala (Ecole Polytechnique Federale de Lausanne) **Title:**Are Gaussian data all you need for machine learning theory?**Abstract:**Clearly, no! Nevertheless, the Gaussian assumption remains prevalent among theoreticians, particularly in high-dimensional statistics and physics, less so in traditional statistical learning circles. To what extent are Gaussian features merely a convenient choice for certain theoreticians, or genuinely an effective model for learning? In this talk, I will review recent progress on these questions, achieved using rigorous probabilistic approaches in high-dimension and techniques from mathematical statistical physics. I will demonstrate that, despite its apparent limitations, the Gaussian approach is sometimes much closer to reality than one might expect. In particular, I will discuss key findings from a series of recent papers that showcase the Gaussian equivalence of generative models, the universality of Gaussian mixtures, and the conditions under which a single Gaussian can characterize the error in high-dimensional estimation. These results illuminate the strengths and weaknesses of the Gaussian assumption, shedding light on its applicability and limitations in the realm of theoretical statistical learning.12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Andrea Montanari (Stanford) **Title:**Dimension free ridge regression**Abstract:**Random matrix theory has become a widely useful tool in high-dimensional statistics and theoretical machine learning. However, random matrix theory is largely focused on the proportional asymptotics in which the number of columns grows proportionally to the number of rows of the data matrix. This is not always the most natural setting in statistics where columns correspond to covariates and rows to samples. With the objective to move beyond the proportional asymptotics, we revisit ridge regression. We allow the feature vector to be high-dimensional, or even infinite-dimensional, in which case it belongs to a separable Hilbert space and assume it to satisfy a certain convex concentration property. Within this setting, we establish non-asymptotic bounds that approximate the bias and variance of ridge regression in terms of the bias and variance of an ‘equivalent’ sequence model (a regression model with diagonal design matrix). Previously, such an approximation result was known only in the proportional regime and only up to additive errors: in particular, it did not allow to characterize the behavior of the excess risk when this converges to 0. Our general theory recovers earlier results in the proportional regime (with better error rates). As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum. Finally, we analyze the overparametrized near-interpolation setting and obtain sharp ‘benign overfitting’ guarantees.[Based on joint work with Chen Cheng] 3:00 – 3:50 pm Yury Polyanskiy (MIT) **Title:**Recent results on broadcasting on trees and stochastic block model**Abstract:**I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q>2 uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT). 4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Alex Wein (UC Davis) **Title:**Is Planted Coloring Easier than Planted Clique?**Abstract:**The task of finding a planted clique in the random graph G(n,1/2) is perhaps the canonical example of a statistical-computational gap: for some clique sizes, the task is statistically possible but believed to be computationally hard. Really, there are multiple well-studied tasks related to the planted clique model: detection, recovery, and refutation. While these are equally difficult in the case of planted clique, this need not be true in general. In the related planted coloring model, I will discuss the computational complexity of these three tasks and the interplay among them. Our computational hardness results are based on the low-degree polynomial model of computation.By taking the complement of the graph, the planted coloring model is analogous to the planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.**Thursday, May 18, 2023**9:00 *Breakfast*9:30 – 10:20 Guy Bresler (MIT) **Title:**Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs**Abstract:**There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. We develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. As a concrete instance of our general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). Joint work with Chenghao Guo and Yury Polyanskiy.10:30 – 11:00 *Coffee break*11:00 – 11:50 Sarath Yasodharan (Brown) **Title:**A Sanov-type theorem for unimodular marked random graphs and its applications**Abstract:**We prove a Sanov-type large deviation principle for the component empirical measures of certain sequences of unimodular random graphs (including Erdos-Renyi and random regular graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropy functionals. As a corollary, we establish a variational formula for the annealed pressure (or limiting log partition function) for various statistical physics models on sparse random graphs. This is joint work with I-Hsun Chen and Kavita Ramanan.12:00 – 12:15 pm 12:15 – 2:00 pm *Group Photo**Lunch*2:00 – 2:50 pm Patrick Rebeschini (Oxford) **Title:**Implicit regularization via uniform convergence**Abstract:**Uniform convergence is one of the main tools to analyze the complexity of learning algorithms based on explicit regularization, but it has shown limited applicability in the context of implicit regularization. In this talk, we investigate the statistical guarantees on the excess risk achieved by early-stopped mirror descent run on the unregularized empirical risk with the squared loss for linear models and kernel methods. We establish a direct link between the potential-based analysis of mirror descent from optimization theory and uniform learning. This link allows characterizing the statistical performance of the path traced by mirror descent directly in terms of localized Rademacher complexities of function classes depending on the choice of the mirror map, initialization point, step size, and the number of iterations. We will discuss other results along the way.3:00 – 3:50 pm Pragya Sur (Harvard) **Title:**A New Central Limit Theorem for the Augmented IPW estimator in high dimensions**Abstract:**Estimating the average treatment effect (ATE) is a central problem in causal inference. Modern advances in the field studied estimation and inference for the ATE in high dimensions through a variety of approaches. Doubly robust estimators such as the augmented inverse probability weighting (AIPW) form a popular approach in this context. However, the high-dimensional literature surrounding these estimators relies on sparsity conditions, either on the outcome regression (OR) or the propensity score (PS) model. This talk will introduce a new central limit theorem for the classical AIPW estimator, that applies agnostic to such sparsity-type assumptions. Specifically, we will study properties of the cross-fit version of the estimator under well-specified OR and PS models, and the proportional asymptotics regime where the number of confounders and sample size diverge proportional to each other. Under assumptions on the covariate distribution, our CLT will uncover two crucial phenomena among others: (i) the cross-fit AIPW exhibits a substantial variance inflation that can be quantified in terms of the signal-to-noise ratio and other problem parameters, (ii) the asymptotic covariance between the estimators used while cross-fitting is non-negligible even on the root-n scale. These findings are strikingly different from their classical counterparts, and open a vista of possibilities for studying similar other high-dimensional effects. On the technical front, our work utilizes a novel interplay between three distinct tools—approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm Yihong Wu (Yale) **Title:**Random graph matching at Otter’s threshold via counting chandeliers**Abstract:**We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq\to\infty and the edge correlation coefficient ρ satisfies ρ^2>α≈0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. This is joint work with Cheng Mao, Jiaming Xu, and Sophie Yu, available at https://arxiv.org/abs/2209.12313**Friday, May 19, 2023**9:00 *Breakfast*9:30 – 10:20 Jake Abernethy (Georgia Tech) **Title:**Optimization, Learning, and Margin-maximization via Playing Games**Abstract:**A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, including optimization, learning, and margin-maximiation problems. Along the way we will encounter a number of novel tools and rediscover some classical ones as well.10:30 – 11:00 *Coffee break*11:00 – 11:50 Devavrat Shah (MIT) **Title:**On counterfactual inference with unobserved confounding via exponential family**Abstract:**We are interested in the problem of unit-level counterfactual inference with unobserved confounders owing to the increasing importance of personalized decision-making in many domains: consider a recommender system interacting with a user over time where each user is provided recommendations based on observed demographics, prior engagement levels as well as certain unobserved factors. The system adapts its recommendations sequentially and differently for each user. Ideally, at each point in time, the system wants to infer each user’s unknown engagement if it were exposed to a different sequence of recommendations while everything else remained unchanged. This task is challenging since: (a) the unobserved factors could give rise to spurious associations, (b) the users could be heterogeneous, and (c) only a single trajectory per user is available.We model the underlying joint distribution through an exponential family. This reduces the task of unit-level counterfactual inference to simultaneously learning a collection of distributions of a given exponential family with different unknown parameters with single observation per distribution. We discuss a computationally efficient method for learning all of these parameters with estimation error scaling linearly with the metric entropy of the space of unknown parameters – if the parameters are an s-sparse linear combination of k known vectors in p dimension, the error scales as O(s log k/p). En route, we derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality. Based on a joint work with Raaz Dwivedi, Abhin Shah and Greg Wornell (all at MIT) with manuscript available here: https://arxiv.org/abs/2211.08209 12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm Lester Mackey (Microsoft Research New England) **Title:**Advances in Distribution Compression**Abstract:**This talk will introduce two new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning: 1. Given an initial n-point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n-points with comparable worst-case integration error across a reproducing kernel Hilbert space. 2. If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases. These tools are especially well-suited for tasks that incur substantial downstream computation costs per summary point like organ and tissue modeling in which each simulation consumes 1000s of CPU hours. Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm Horng-Tzer Yau (Harvard) **Title:**On the spectral gap of mean-field spin glass models.**Abstract:**We will discuss recent progress regarding spectral gaps for the Glauber dynamics of spin glasses at high temperature. In addition, we will also report on estimating the operator norm of the covariance matrix for the SK model.**Moderators:**Benjamin McKenna, Harvard CMSA & Changji Xu, Harvard CMSA
| 19 - WorkshopCMSA, 20 Garden Street, Cambridge, MA 02138 USA
**GRAMSIA: Graphical Models, Statistical Inference, and Algorithms**. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA. This workshop was organized by David Gamarnik (MIT), Kavita Ramanan (Brown), and Prasad Tetali (Carnegie Mellon).**Location:**Room G10, CMSA, 20 Garden Street, Cambridge MA 02138**Speakers:**- Jake Abernethy (Georgia Tech)
- Guy Bresler (MIT)
- Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
- Lester Mackey (Microsoft Research New England)
- Theo McKenzie (Harvard)
- Andrea Montanari (Stanford)
- Elchanan Mossel (MIT)
- Yury Polyanskiy (MIT)
- Patrick Rebeschini (Oxford)
- Subhabrata Sen (Harvard)
- Devavrat Shah (MIT)
- Pragya Sur (Harvard)
- Alex Wein (UC Davis)
- Yihong Wu (Yale)
- Sarath Yasodharan (Brown)
- Horng-Tzer Yau (Harvard)
- Christina Lee Yu (Cornell)
- Ilias Zadik (MIT)
**Schedule:****Tuesday, May 16, 2023**9:00 am *Breakfast*9:15 – 9:30 am Introductory remarks by organizers 9:30 – 10:20 am **Title:**Mean-field approximations for high-dimensional Bayesian regression**Abstract:**Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. The Naive Mean-Field (NMF) approximation is the simplest version of this strategy—this approach approximates the posterior in KL divergence by a product distribution. There has been considerable progress recently in understanding the accuracy of NMF under structural constraints such as sparsity, but not much is known in the absence of such constraints. Moreover, in some high-dimensional settings, the NMF is expected to be grossly inaccurate, and advanced mean-field techniques (e.g. Bethe approximation) are expected to provide accurate approximations. We will present some recent work in understanding this duality in the context of high-dimensional regression. This is based on joint work with Sumit Mukherjee (Columbia) and Jiaze Qiu (Harvard University).10:30 – 11:00 am *Coffee break*11:00 – 11:50 am **Title:**Some modern perspectives on the Kesten-Stigum bound for reconstruction on trees.**Abstract:**The Kesten-Stigum bound is a fundamental spectral bound for reconstruction on trees. I will discuss some conjectures and recent progress on understanding when it is tight as well as some conjectures and recent progress on what it signifies even in cases where it is not tight.12:00 – 2:00 pm Lunch 2:00 – 2:50 pm **Title:**Exploiting Neighborhood Interference with Low Order Interactions under Unit Randomized Design**Abstract:**Network interference, where the outcome of an individual is affected by the treatment assignment of those in their social network, is pervasive in many real-world settings. However, it poses a challenge to estimating causal effects. We consider the task of estimating the total treatment effect (TTE), or the difference between the average outcomes of the population when everyone is treated versus when no one is, under network interference. Under a Bernoulli randomized design, we utilize knowledge of the network structure to provide an unbiased estimator for the TTE when network interference effects are constrained to low order interactions among neighbors of an individual. We make no assumptions on the graph other than bounded degree, allowing for well-connected networks that may not be easily clustered. Central to our contribution is a new framework for balancing between model flexibility and statistical complexity as captured by this low order interactions structure.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm **Title:**Spectral statistics for sparse random graphs**Abstract:**Understanding the eigenvectors and eigenvalues of the adjacency matrix of random graphs is fundamental to many algorithmic questions; moreover, it is related to longstanding questions in quantum physics. In this talk we focus on random models of sparse graphs, giving some properties that are unique to these sparse graphs, as well as some specific obstacles. Based on this, we show some new results on spectral statistics of sparse random graphs, as well as some conjectures.4:40 – 6:30 pm Lightning talk session + welcome reception **Wednesday, May 17, 2023**9:00 am *Breakfast*9:30 – 10:20 **Title:**Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem**Abstract:**Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992.10:30 – 11:00 *Coffee break*11:00 – 11:50 **Title:**Are Gaussian data all you need for machine learning theory?**Abstract:**Clearly, no! Nevertheless, the Gaussian assumption remains prevalent among theoreticians, particularly in high-dimensional statistics and physics, less so in traditional statistical learning circles. To what extent are Gaussian features merely a convenient choice for certain theoreticians, or genuinely an effective model for learning? In this talk, I will review recent progress on these questions, achieved using rigorous probabilistic approaches in high-dimension and techniques from mathematical statistical physics. I will demonstrate that, despite its apparent limitations, the Gaussian approach is sometimes much closer to reality than one might expect. In particular, I will discuss key findings from a series of recent papers that showcase the Gaussian equivalence of generative models, the universality of Gaussian mixtures, and the conditions under which a single Gaussian can characterize the error in high-dimensional estimation. These results illuminate the strengths and weaknesses of the Gaussian assumption, shedding light on its applicability and limitations in the realm of theoretical statistical learning.12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm **Title:**Dimension free ridge regression**Abstract:**Random matrix theory has become a widely useful tool in high-dimensional statistics and theoretical machine learning. However, random matrix theory is largely focused on the proportional asymptotics in which the number of columns grows proportionally to the number of rows of the data matrix. This is not always the most natural setting in statistics where columns correspond to covariates and rows to samples. With the objective to move beyond the proportional asymptotics, we revisit ridge regression. We allow the feature vector to be high-dimensional, or even infinite-dimensional, in which case it belongs to a separable Hilbert space and assume it to satisfy a certain convex concentration property. Within this setting, we establish non-asymptotic bounds that approximate the bias and variance of ridge regression in terms of the bias and variance of an ‘equivalent’ sequence model (a regression model with diagonal design matrix). Previously, such an approximation result was known only in the proportional regime and only up to additive errors: in particular, it did not allow to characterize the behavior of the excess risk when this converges to 0. Our general theory recovers earlier results in the proportional regime (with better error rates). As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum. Finally, we analyze the overparametrized near-interpolation setting and obtain sharp ‘benign overfitting’ guarantees.[Based on joint work with Chen Cheng] 3:00 – 3:50 pm **Title:**Recent results on broadcasting on trees and stochastic block model**Abstract:**I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q>2 uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT). 4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm **Title:**Is Planted Coloring Easier than Planted Clique?**Abstract:**The task of finding a planted clique in the random graph G(n,1/2) is perhaps the canonical example of a statistical-computational gap: for some clique sizes, the task is statistically possible but believed to be computationally hard. Really, there are multiple well-studied tasks related to the planted clique model: detection, recovery, and refutation. While these are equally difficult in the case of planted clique, this need not be true in general. In the related planted coloring model, I will discuss the computational complexity of these three tasks and the interplay among them. Our computational hardness results are based on the low-degree polynomial model of computation.By taking the complement of the graph, the planted coloring model is analogous to the planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.**Thursday, May 18, 2023**9:00 *Breakfast*9:30 – 10:20 **Title:**Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs**Abstract:**There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. We develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. As a concrete instance of our general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). Joint work with Chenghao Guo and Yury Polyanskiy.10:30 – 11:00 *Coffee break*11:00 – 11:50 **Title:**A Sanov-type theorem for unimodular marked random graphs and its applications**Abstract:**We prove a Sanov-type large deviation principle for the component empirical measures of certain sequences of unimodular random graphs (including Erdos-Renyi and random regular graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropy functionals. As a corollary, we establish a variational formula for the annealed pressure (or limiting log partition function) for various statistical physics models on sparse random graphs. This is joint work with I-Hsun Chen and Kavita Ramanan.12:00 – 12:15 pm 12:15 – 2:00 pm *Group Photo**Lunch*2:00 – 2:50 pm **Title:**Implicit regularization via uniform convergence**Abstract:**Uniform convergence is one of the main tools to analyze the complexity of learning algorithms based on explicit regularization, but it has shown limited applicability in the context of implicit regularization. In this talk, we investigate the statistical guarantees on the excess risk achieved by early-stopped mirror descent run on the unregularized empirical risk with the squared loss for linear models and kernel methods. We establish a direct link between the potential-based analysis of mirror descent from optimization theory and uniform learning. This link allows characterizing the statistical performance of the path traced by mirror descent directly in terms of localized Rademacher complexities of function classes depending on the choice of the mirror map, initialization point, step size, and the number of iterations. We will discuss other results along the way.3:00 – 3:50 pm **Title:**A New Central Limit Theorem for the Augmented IPW estimator in high dimensions**Abstract:**Estimating the average treatment effect (ATE) is a central problem in causal inference. Modern advances in the field studied estimation and inference for the ATE in high dimensions through a variety of approaches. Doubly robust estimators such as the augmented inverse probability weighting (AIPW) form a popular approach in this context. However, the high-dimensional literature surrounding these estimators relies on sparsity conditions, either on the outcome regression (OR) or the propensity score (PS) model. This talk will introduce a new central limit theorem for the classical AIPW estimator, that applies agnostic to such sparsity-type assumptions. Specifically, we will study properties of the cross-fit version of the estimator under well-specified OR and PS models, and the proportional asymptotics regime where the number of confounders and sample size diverge proportional to each other. Under assumptions on the covariate distribution, our CLT will uncover two crucial phenomena among others: (i) the cross-fit AIPW exhibits a substantial variance inflation that can be quantified in terms of the signal-to-noise ratio and other problem parameters, (ii) the asymptotic covariance between the estimators used while cross-fitting is non-negligible even on the root-n scale. These findings are strikingly different from their classical counterparts, and open a vista of possibilities for studying similar other high-dimensional effects. On the technical front, our work utilizes a novel interplay between three distinct tools—approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.4:00 – 4:30 pm *Coffee break*4:30 – 5:20 pm **Title:**Random graph matching at Otter’s threshold via counting chandeliers**Abstract:**We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq\to\infty and the edge correlation coefficient ρ satisfies ρ^2>α≈0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. This is joint work with Cheng Mao, Jiaming Xu, and Sophie Yu, available at https://arxiv.org/abs/2209.12313**Friday, May 19, 2023**9:00 *Breakfast*9:30 – 10:20 **Title:**Optimization, Learning, and Margin-maximization via Playing Games**Abstract:**A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, including optimization, learning, and margin-maximiation problems. Along the way we will encounter a number of novel tools and rediscover some classical ones as well.10:30 – 11:00 *Coffee break*11:00 – 11:50 **Title:**On counterfactual inference with unobserved confounding via exponential family**Abstract:**We are interested in the problem of unit-level counterfactual inference with unobserved confounders owing to the increasing importance of personalized decision-making in many domains: consider a recommender system interacting with a user over time where each user is provided recommendations based on observed demographics, prior engagement levels as well as certain unobserved factors. The system adapts its recommendations sequentially and differently for each user. Ideally, at each point in time, the system wants to infer each user’s unknown engagement if it were exposed to a different sequence of recommendations while everything else remained unchanged. This task is challenging since: (a) the unobserved factors could give rise to spurious associations, (b) the users could be heterogeneous, and (c) only a single trajectory per user is available.12:00 – 2:00 pm *Lunch*2:00 – 2:50 pm **Title:**Advances in Distribution Compression**Abstract:**This talk will introduce two new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning: 1. Given an initial n-point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n-points with comparable worst-case integration error across a reproducing kernel Hilbert space. 2. If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases. These tools are especially well-suited for tasks that incur substantial downstream computation costs per summary point like organ and tissue modeling in which each simulation consumes 1000s of CPU hours. Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich.3:00 – 3:30 pm *Coffee break*3:30 – 4:20 pm **Title:**On the spectral gap of mean-field spin glass models.**Abstract:**We will discuss recent progress regarding spectral gaps for the Glauber dynamics of spin glasses at high temperature. In addition, we will also report on estimating the operator norm of the covariance matrix for the SK model.**Moderators:**Benjamin McKenna, Harvard CMSA & Changji Xu, Harvard CMSA
| 20 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

21 | 22 | 23 | 24 | 25 | 26 | 27 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

28 | 29 | 30 | 31 | June | June | June |