Georgia Institute of Technology College of Sciences

A central goal in modern data science is to design algorithms for statistical inference tasks such as community detection, high-dimensional clustering, sparse PCA, and many others. Ideally these algorithms would be both statistically optimal and computationally efficient. However, it often seems impossible to achieve both these goals simultaneously: for many problems, the optimal statistical procedure involves a brute force search while all known polynomial-time algorithms are statistically sub-optimal (requiring more data or higher signal strength than is information-theoretically necessary). In the quest for optimal algorithms, it is therefore important to understand the fundamental statistical limitations of computationally efficient algorithms.

I will discuss an emerging theoretical framework for understanding these questions, based on studying the class of "low-degree polynomial algorithms." This is a powerful class of algorithms that captures the best known poly-time algorithms for a wide variety of statistical tasks. This perspective has led to the discovery of many new and improved algorithms, and also many matching lower bounds: we now have tools to prove failure of all low-degree algorithms, which provides concrete evidence for inherent computational hardness of statistical problems. This line of work illustrates that low-degree polynomials provide a unifying framework for understanding the computational complexity of a wide variety of statistical tasks, encompassing hypothesis testing, estimation, and optimization.

Quantum spin systems are many-body physical models where particles are bound to the sites of a lattice. These are widely used throughout condensed matter physics and quantum information theory, and are of particular interest in the classification of quantum phases of matter. By pinning down the properties of new exotic phases of matter, researchers have opened the door to developing new quantum technologies. One of the fundamental quantitites for this classification is whether or not the Hamiltonian has a spectral gap above its ground state energy in the thermodynamic limit. Mathematically, the Hamiltonian is a self-adjoint operator and the set of possible energies is given by its spectrum, which is bounded from below. While the importance of the spectral gap is well known, very few methods exist for establishing if a model is gapped, and the majority of known results are for one-dimensional systems. Moreover, the existence of a non-vanishing gap is generically undecidable which makes it necessary to develop new techniques for estimating spectral gaps. In this talk, I will discuss my work proving non-vanishing spectral gaps for key quantum spin models, and developing new techniques for producing lower bound estimates on the gap. Two important models with longstanding spectral gap questions that I recently contributed progress to are the AKLT model on the hexagonal lattice, and Haldane's pseudo-potentials for the fractional quantum Hall effect. Once a gap has been proved, a natural next question is whether it is typical of a gapped phase. This can be positively answered by showing that the gap is robust in the presence of perturbations. Ensuring the gap remains open in the presence of perturbations is also of interest, e.g., for the development of robust quantum memory. A second topic I will discuss is my research studying spectral gap stability.

URL for the talk: https://bluejeans.com/602513114/7767

The first part of the talk is devoted to robust algorithms for the k-means clustering problem where a quantizer is constructed based on N independent observations. I will present recent sharp non-asymptotic performance guarantees for k-means that hold under the two bounded moments assumption in a general Hilbert space. These bounds extend the asymptotic result of D. Pollard (Annals of Stats, 1981) who showed that the existence of two moments is sufficient for strong consistency of an empirically optimal quantizer. In the second part of the talk I discuss a dimension-free version of the result of Adamczak, Litvak, Pajor, Tomczak-Jaegermann (Journal of Amer. Math. Soc, 2010) for the sample-covariance matrix in log-concave ensembles. The proof of the dimension-free result is based on a duality formula between entropy and moment generating functions. Finally, I will briefly discuss a recent bound on an empirical risk minimization strategy in stochastic convex optimization with strongly convex and Lipschitz losses.

Link to the online talk: https://bluejeans.com/958288541/0675

Through the pioneering numerical computations of Fermi-Pasta-Ulam (mid 50s) and Kruskal-Zabusky (mid 60s) it was observed that nonlinear equations modeling wave propagation asymptotically decompose as a superposition of “traveling waves” and “radiation”. Since then, it has been a widely believed (and supported by extensive numerics) that “coherent structures” together with radiations describe the long-time asymptotic behavior of generic solutions to nonlinear dispersive equations. This belief has come to be known as the “soliton resolution conjecture”.  Roughly speaking it tells that, asymptotically in time, the evolution of generic solutions decouples as a sum of modulated solitary waves and a radiation term that disperses. This remarkable claim establishes a drastic “simplification” to the complex, long-time dynamics of general solutions. It remains an open problem to rigorously show such a description for most dispersive equations.  After an informal introduction to dispersive equations, I will survey some of my recent results towards understanding the long-time behavior of dispersive waves and the soliton resolution using techniques from both partial differential equations and inverse scattering transforms.