Seminars and Colloquia by Series

TBA by Max Fathi

Series
High Dimensional Seminar
Time
Tuesday, December 3, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Max FathiMathematics Institute, Toulouse, France

TBA

Smoothed analysis of the least singular value without inverse Littlewood--Offord theory

Series
High Dimensional Seminar
Time
Wednesday, November 6, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Speaker
Vishesh JainMIT

We will discuss a novel approach to obtaining non-asymptotic estimates on the lower tail of the least singular value of an $n \times n$ random matrix $M_{n} := M + N_{n}$, where $M$ is a fixed matrix with operator norm at most $O(\exp(n^{c}))$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a random variable with mean 0 and variance 1. This has been previously considered in a series of works by Tao and Vu, and our results improve upon theirs in two ways: 

(i) We are able to deal with $\|M\| = O(\exp(n^{c}))$ whereas previous work was applicable for $\|M\| = O(\poly(n))$. 

(ii) Even for $\|M\| = O(poly(n))$, we are able to extract more refined information – for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(exp(-n^{c}))$, whereas even in the case when $N_n$ is an i.i.d. Bernoulli matrix, the results of Tao and Vu only give inverse polynomial singularity probability.  

 

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Series
High Dimensional Seminar
Time
Wednesday, October 23, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andre WibisonoGeorgia Tech

Sampling is a fundamental algorithmic task. Many modern applications require sampling from complicated probability distributions in high-dimensional spaces. While the setting of logconcave target distribution is well-studied, it is important to understand sampling beyond the logconcavity assumption. We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution on R^n under isoperimetry conditions. We show a convergence guarantee in Kullback-Leibler (KL) divergence assuming the target distribution satisfies log-Sobolev inequality and the log density has bounded Hessian. Notably, we do not assume convexity or bounds on higher derivatives. We also show convergence guarantees in Rényi divergence assuming the limit of ULA satisfies either log-Sobolev or Poincaré inequality. Joint work with Santosh Vempala (arXiv:1903.08568).

Regularity Decompositions for Sparse Pseudorandom Graphs

Series
High Dimensional Seminar
Time
Wednesday, October 16, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Gregory M BodwinGeorgia Tech

 A powerful method for analyzing graphs is to first apply regularity lemmas, which roughly state that one can partition the graph into a few parts so that it looks mostly random between the parts, and then apply probabilistic tools from there.  The drawback of this approach is that it only works in general when the input graph is very dense: standard regularity lemmas are trivial already for n-node graphs on "only" <= n^{1.99} edges.

In this work we prove extensions of several standard regularity lemmas to sparse graphs, which are nontrivial so long as the graph spectrum is not too far from that of a random graph.  We then apply our notion of "spectral pseudorandomness" to port several notable regularity-based results in combinatorics and theoretical computer science down to sparser graphs.

 

Joint work with Santosh Vempala.

 

Stochastic analysis and geometric functional inequalities

Series
High Dimensional Seminar
Time
Wednesday, October 9, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Masha GordinaUniversity of Connecticut

We will survey different methods of proving functional inequalities for hypoelliptic  diffusions and the corresponding heat kernels. Some of these methods rely on geometric methods such as curvature-dimension inequalities (due to Baudoin-Garofalo), and some are probabilistic  such as coupling, and finally some use structure  theory and a Fourier transform on Lie groups. This is based on joint work with M. Asaad, F. Baudoin, B. Driver, T. Melcher, Ph. Mariano et al.

Invertibility of inhomogenuous random matrices

Series
High Dimensional Seminar
Time
Wednesday, October 2, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Galyna LivshytsGeorgia Tech

We will show the sharp estimate on the behavior of the smallest singular value of random matrices under very general assumptions. One of the steps in the proof is a result about the efficient discretization of the unit sphere in an n-dimensional euclidean space. Another step involves the study of the regularity of the behavior of lattice sets. Some elements of the proof will be discussed. Based on the joint work with Tikhomirov and Vershynin.

John’s ellipsoid is not good for approximation

Series
High Dimensional Seminar
Time
Wednesday, September 18, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Han HuangGeorgia Tech

We study the subject of approximation of convex bodies by polytopes in high dimension.  

For a convex set K in R^n, we say that K can be approximated by a polytope of m facets by a distance R>1 if there exists a polytope of P m facets such that K contains P and RP contains K. 

When K is symmetric, the maximal volume ellipsoid of K is used heavily on how to construct such polytope of poly(n) facets to approximate K. In this talk, we will discuss why the situation is entirely different for non-symmetric convex bodies.

Pages