# Statistical estimation under algebraic constraints: total positivity

Elina Robeva

MIT

## Time:

Thursday, January 10, 2019 - 4:00pm to 5:00pm

## Location:

RH 306

My research focuses on studying models that depict complex dependencies between random variables. Such models include directed graphical models with hidden variables, discrete mixture models (which give rise to low rank tensors), and models that impose strong positive dependence called total positivity. In this talk I will give a brief overview of my work in these areas, and will particularly focus on the problem of density estimation under total positivity.

Nonparametric density estimation is a challenging statistical problem -- in general the maximum likelihood estimate (MLE) does not even exist! Introducing shape constraints such as total positivity allows a path forward. Though they possess very special structure, totally positive random variables are quite common in real world data and exhibit appealing mathematical properties. Given i.i.d. samples from a totally positive distribution, we prove that the MLE exists with probability one if there are at least 3 samples. We characterize the domain of the MLE, and give algorithms to compute it. If the observations are 2-dimensional or binary, we show that the logarithm of the MLE is a piecewise linear function and can be computed via a certain convex program. Finally, I will discuss statistical guarantees for the convergence of the MLE, and will conclude with a variety of further research directions.

# When combinatorics meets Littlewood-Offord theory

Asaf Ferber

MIT

## Time:

Friday, January 11, 2019 - 4:00pm to 5:00pm

## Location:

RH 306

Given an integer vector $a = (a_1,\dots,a_n)$, let $\rho(a)$ be the number of solutions to $a\cdot x=0$, with $x\in \{\pm 1\}^n$. In 1945, Erdos gave a beautiful combinatorial solution to the following problem that was posed by Littlewood and Offord: how large can $\rho(a)$ be if all the entries of $a$ are non-zero?

Following his breakthrough result, several extensions of this problem have been intensively studied by various researchers. In classical works, Erdos-Moser, Sarkozy-Szemeredi, and Halasz obtained better bounds on $\rho(a)$ under additional assumptions on $a$, while Kleitman, Frankl-Furedi, Esseen, Halasz and many others studied generalizations to higher dimensions. In recent years, motivated by deep Freiman-type inverse theorems from additive combinatorics, Tao and Vu brought a new view to this problem by asking for the underlying structural reason for $\rho(a)$ to be large --this is known as the Inverse Littlewood-Offord problem, which is a cornerstone of modern random matrix theory.

In this talk, we will discuss further extensions and improvements for both forward and inverse Littlewood-Offord problems where combinatorial tools and insights have proved to be especially powerful. We also present several applications in (discrete) matrix theory such as: a resilience' version of it, a non-trivial upper bound on the number of Hadamard matrices, an upper bound on  the number of $\pm 1$ normal matrices, and a unified approach for counting the number of singular $\pm1$ matrices from various popular models.

# Large deviations for sparse random graphs

Nick Cook

UCLA

## Time:

Monday, January 14, 2019 - 3:00pm to 4:00pm

## Location:

RH 306

Let $G=G(N,p)$ be an Erd\H{o}s--R\'enyi graph on $N$ vertices (where each pair is connected by an edge independently with probability $p$). We view $N$ as going to infinity, with $p$ possibly going to zero with $N$. What is the probability that $G$ contains twice as many triangles (triples of vertices with all three pairs connected) as we would expect? I will discuss recent progress on this infamous upper tail" problem, and more generally on tail estimates for counts of any fixed subgraph. These problems serve as a test bed for the emerging theory of \emph{nonlinear large deviations}, and also connect with issues in extending the theory of \emph{graph limits} to handle sparse graphs. In particular, I will discuss our approach to the upper tail problems via new versions of the classic regularity and counting lemmas from extremal combinatorics, specially tailored to the study of random graphs in the large deviations regime. This talk is based on joint work with Amir Dembo.

# Graphs in algebraic and arithmetic geometry

Farbod Shokrieh

## Institution:

University of Copenhagen

## Time:

Tuesday, January 22, 2019 - 4:00pm to 5:00pm

## Location:

RH 306

Graphs can be viewed as (non-archimedean) analogues of Riemann surfaces. For example, there is a notion of Jacobians for graphs. More classically, graphs can be viewed as electrical networks. I will explain the interplay between these points of view, as well as some recent application in arithmetic geometry.

# Modern Non''-Problems in Optimization: Applications to Statistics and Machine Learning

Ying Cui

## Institution:

University of Southern California

## Time:

Wednesday, January 23, 2019 - 4:00pm to 5:00pm

## Location:

RH 306

Classical continuous optimization starts with linear and nonlinear programming. In the past two decades, convex optimization (e.g., sparse linear regressions with convex regularizers) has been a very effective computational tool in applications to statistical estimations and machine learning. However, many modern data-science problems involve some basic `non’’-properties that are ignored by the convex approach for the sake of the computation convenience. These non-properties include the coupling of the non-convexity, non-differentiability and non-(Clarke) regularity. In this talk, we present a rigorous computational treatment for solving two non-problems: the piecewise affine regression and the feed-forward deep neural network. The algorithmic framework is an integration of the first order non-convex majorization-minimization method and the second order non-smooth Newton methods. Numerical experiments demonstrate the effectiveness of our proposed approach. Contrary to existing methods for solving non-problems which provide at best very weak guarantees on the computed solutions obtained in practical implementation, our rigorous mathematical treatment aims to understand properties of these computed solutions with reference to both the empirical and the population risk minimizations. This is based on joint work with Jong-Shi Pang, Bodhisattva Sen and Ziyu He.

# Universal arithmetical hierarchy of eigenfunctions for supercritical almost Mathieu operators

Wencai Liu

## Institution:

University of California, Irvine

## Time:

Tuesday, January 8, 2019 - 4:00pm to 5:00pm

## Location:

RH 306

The Harper's model is a tight-binding description of Bloch electrons on $\mathbb{Z}^2$ under a constant transverse magnetic field. In 1964, Mark Azbel predicted that both spectra and eigenfunctions of this model have self-similar hierarchical structure driven by the continued fraction expansion of the irrational magnetic flux. In 1976, the hierarchical structure of spectra was discovered numerically by Douglas Hofstadter, and was later observed in various experiments. The mathematical study of Harper's model led to the development of spectral theory of the almost Mathieu operator, with the solution of the Ten Martini Problem partially confirming the fractal structure of the spectrum.

In this talk, we will present necessary background and discuss the main ideas behind our confirmation (joint with S. Jitomirskaya) of  Azbel's second prediction of the structure of the eigenfunctions. More precisely, we show that the eigenfunctions of the almost Mathieu operators in the localization regime, feature self-similarity governed by the continued fraction expansion of the frequency. These results also lead to the proof of sharp arithmetic transitions between pure point and singular continuous spectra, both in the frequency and the phase, as conjectured in 1994.