Statistical estimation under algebraic constraints: total positivity

Speaker: 

Elina Robeva

Institution: 

MIT

Time: 

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

Host: 

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

Speaker: 

Asaf Ferber

Institution: 

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

Speaker: 

Nick Cook

Institution: 

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

Speaker: 

Farbod Shokrieh

Institution: 

University of Copenhagen

Time: 

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

Host: 

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

Speaker: 

Ying Cui

Institution: 

University of Southern California

Time: 

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

Host: 

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

Speaker: 

Wencai Liu

Institution: 

University of California, Irvine

Time: 

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

Host: 

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.

Can Analysis "See" Algebra? Classifying Von Neumann Algebras Using Groups

Speaker: 

Rolando De Santiago

Institution: 

UCLA

Time: 

Tuesday, November 20, 2018 - 11:00am to 12:00pm

Host: 

Location: 

RH 340N

This talk is aimed (mostly) at undergraduate students. 

Abstract: In the 1930’s and 1940’s, Murray and von Neumann developed a theory of operators on Hilbert spaces, which heuristically may be thought of as infinite matrices acting on infinite dimensional vector spaces. Their works include a procedure which starts with an infinite group, a discrete object, and generates a von Neumann algebra, an analytic object which is a continuous analog to the n × n matrices. Much of the active research in this field has been generated by the following question: are structural properties of groups able to classify the resulting algebras? Obtaining a satisfactory resolution to this problem has been surprisingly difficult since standard group invariants are often not invariants of the algebras. We give a brief survey of the evolution of this problem, the surprising broader impacts including the emergence Jones polynomial, and the recent rapid progress in this classification program due to the advent of S. Popas deformation/rigidity theory. We close by describing recent developments in this program which have been made by my collaborators and myself. 

 

About the speaker: Rolando de Santiago is currently an Assistant Adjunct Professor and a UC Presidential Postdoctoral Fellow at UCLA working under S. Popa. His work is in the classification of type II1 von Neumann algebras, a subfield of functional analysis, and his research interests extend into group theory, topology, fractal geometry, and mathematical physics. He was born and raised up in the South-Eastern part of Los Angeles with 6 of his siblings. He spent 27 years studying at numerous public institutions including Pasadena City College and Cal Poly Pomona. After approximately 8 years of undergraduate work, he finally earned his B.S. in Mathematics. He completed his Masters in Mathematics at Cal Poly Pomona shortly thereafter. His mentors at Cal Poly, J. Rock and R. Wilson, strongly suggested that he pursue his Ph.D. After a significant amount of convincing, he threw all his belongings into a U-Haul, moved to Iowa City, and started grad school at the University of Iowa. He worked under of I. Chifan, the advisor who would help his launch his research career.

You may RSVP here:  https://docs.google.com/forms/d/e/1FAIpQLScYrvrod7lMjOBmMt3Hhz4YSZmqjdOEKmHIsTg70pa4FpQOSA/viewform

 

Rigidity and classification in group von Neumann algebras

Speaker: 

Rolando de Santiago

Institution: 

UCLA

Time: 

Tuesday, November 20, 2018 - 3:00pm to 4:00pm

Host: 

Location: 

RH 306

The works of F. Murray and J. von Neumann outlined a natural method to associate a von Neumann algebra to a group. Since then, an active area of research seeks to investigate which structural aspects of the group extend to its von Neumann algebra.  The difficulty of this problem is best illustrated by Conne's landmark result which states all ICC amenable groups give rise to isomorphic von Neumann algebras.  In essence, standard group invariants are not typically detectable for the resulting von Neumann algebra.  When the group is non-amenable, the situation may be strikingly different. 

This talk surveys advances made in this area, with an emphasis on the results stemming from Popa's deformation/rigidity theory.  I present several instances where elementary group theoretic properties, such as direct products, can be recovered from the algebra.  We will also discuss recent progress made by Ben Hayes, Dan Hoff, Thomas Sinclair and myself in the case where the underlying group has positive first $\ell^2 $-Betti number.  We will explore the relationship between s-malleable deformations of von Neumann algebras and $\ell^2 $ co-cycles which lays the foundation for our work. 

Pages

Subscribe to RSS - Special Colloquium