# Introduction to Robust Statistics II

## Speaker:

## Institution:

## Time:

## Host:

## Location:

# Introduction to Robust Statistics I

## Speaker:

## Institution:

## Time:

## Host:

## Location:

# A new proof of Friedman's second eigenvalue theorem with strong implications

## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

In 2004 J. Friedman wrote a ~100 page paper proving a conjecture of Alon which stated that random d-regular graphs are nearly optimal expanders. Since then, Friedman's result has been refined and generalized in several directions, perhaps most notably by Bordenave and Collins who in 2019 established strong convergence of independent permutation matrices (a massive generalization of Friedman's theorem), a result that led to groundbreaking results in spectral theory and geometry.

In this talk I will present joint work with C. Chen, J. Tropp and R. van Handel, where we introduce a new proof technique that allows one to convert qualitative results in random matrix theory into quantitative ones. This technique yields a fundamentally new approach to the study of strong convergence which is more flexible and significantly simpler than the existing techniques. Concretely, we're able to obtain (1) a remarkably short of Friedman's theorem (2) a quantitative version of the result of Bordenave and Collins (3) a proof of strong convergence for arbitrary stable representations of the symmetric group, which constitutes a substantial generalization of the result of Bordenave and Collins.

# Online Ordered Ramsey Numbers

## Speaker:

## Institution:

## Time:

## Host:

## Location:

The Ramsey number of graphs G1 and G2, the smallest N so that any red/blue coloring of the N-clique contains either a red G1 or a blue G2, is one of the most studied notions in combinatorics. We study a related process called the online ordered Ramsey game, played between two players, Builder and Painter. Builder has two graphs, G1 and G2, each of which has a specific ordering on its vertices. Builder starts with an edgeless graph on an ordered vertex set (the integers) and attempts to build either an ordered red copy of G1 or an ordered blue copy of G2 by adding one edge at a time. When Builder adds an edge, Painter is required to decide, at the time of creation, whether an edge is red or blue. Ramsey’s Theorem tells us that Builder can eventually win; their objective is to do so using the minimum number of turns, and Painter’s objective is to delay them as long as possible. The ***online ordered Ramsey number*** of G1 and G2 is the number of turns taken when both players play optimally.

Online ordered Ramsey numbers were introduced by Perez-Gimenez, P. Pralat, and West in 2021. In this talk we will discuss their relation to other types of Ramsey numbers and present some results on the case when at least one of G1,G2 is sparse.

(Joint work with Emily Heath, Grace McCourt, Hannah Sheats, and Justin Wisby)

# Random permutations using GEPP

## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

Gaussian elimination with partial pivoting (GEPP) remains the most used dense linear solver. For a *nxn* matrix *A*, GEPP results in the factorization *PA = LU* where *L* and *U* are lower and upper triangular matrices and *P* is a permutation matrix. If *A* is a random matrix, then the associated permutation from the *P* factor is random. When is this a uniform permutation? How many disjoint cycles are in its cycle decomposition (which equivalently answers how many GEPP pivot movements are needed on *A*)? What is the longest increasing subsequence of this permutation? We will provide some statistical answers to these questions for select random matrix ensembles and transformations. For particular butterfly permutations, we will present full distributional descriptions for these particular statistics. Moreover, we introduce a random butterfly matrix ensemble that induces the Haar measure on the full 2-Sylow subgroup of the symmetric group on a set of size 2ⁿ.

# MCMC, variational inference, and reverse diffusion Monte Carlo

## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

I will introduce some recent progress towards understanding the scalability of Markov chain Monte Carlo (MCMC) methods and their comparative advantage with respect to variational inference. I will fact-check the folklore that "variational inference is fast but biased, MCMC is unbiased but slow". I will then discuss a combination of the two via reverse diffusion, which holds promise of solving some of the multi-modal problems. This talk will be motivated by the need for Bayesian computation in reinforcement learning problems as well as the differential privacy requirements that we face.

# Online differential privacy

## Speaker:

## Institution:

## Time:

## Location:

We present a polynomial-time algorithm for online differentially private synthetic data generation. For a data stream within the hypercube [0,1]^d and an infinite time horizon, we develop an online algorithm that generates a differentially private synthetic dataset at each time t. This algorithm achieves a near-optimal accuracy bound in the 1-Wasserstein distance.

# Extreme Eigenvalues of a Random Laplacian Matrix

## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

The extreme eigenvalues of a random matrix have been important objects of study since the inception of random matrix theory and also have a variety of applications. The Laplacian matrix is the workhorse of spectral graph theory and is the key player in many practical algorithms for graph clustering, network control theory and combinatorial optimization. In this talk, we discuss the fluctuations of the extreme eigenvalues of a random Laplacian matrix with gaussian entries. The proof relies on a broad set of techniques from random matrix theory and free probability. We will also describe some recent progress on a broader class of random Laplacian matrices.

This is joint work with Andrew Campbell and Sean O'Rourke.

# Concentration Inequalities and Moment Bounds for Self-Adjoint Operators with Heavy tails

## Speaker:

## Speaker Link:

## Institution:

## Time:

## Host:

## Location:

We present Fuk-Nagaev - type inequality for the sums of independent self-adjoint operators. This bound could be viewed as an extension of the well known “Matrix Bernstein” inequality to the case of operators with heavy-tailed norms. As a corollary, we deduce Rosenthal moment inequality that improves upon the previously known versions even in the scalar case. Finally, we will discuss applications of these bounds to the covariance estimation problem.