PACM Colloquium

Fall 2017

PACM Colloquium: Walking within growing domains: recurrence versus transience

Speaker: 
Amir Dembo, Stanford University
Date: 
Sep 18 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

When is simple random walk on growing in time d-dimensional domains recurrent? For domain growth which is independent of the walk, we review recent progress and related universality conjectures about a sharp recurrence versus transience criterion in terms of the growth rate. We compare this with the question of recurrence/transience for time varying conductance models, where Gaussian heat kernel estimates and evolving sets play an important role. 

We also briefly contrast such expected universality with examples of the rich behavior encountered when monotone interaction enforces the growth as a result of visits by the walk to the current domain's boundary.

This talk is based on joint works with Ruojun Huang, Vladas Sidoravicius and Tianyi Zheng.

PACM Colloquium: Polynomial Optimization and Dynamical Systems

Speaker: 
Amir Ali Ahmadi, Princeton University
Date: 
Sep 25 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

In recent years, there has been a surge of exciting research activity at the interface of optimization (in particular polynomial, semidefinite, and sum of squares optimization) and the theory of dynamical systems. In this talk, we focus on two of our current research directions that are at this interface. In part (i), we propose more scalable alternatives to sum of squares optimization and show how they impact verification problems in control and robotics. Our new algorithms do not rely on semidefinite programming, but instead use linear programming, or second-order cone programming, or are altogether free of optimization. In particular, we present the first Positivstellensatz that certifies infeasibility of a set of polynomial inequalities simply by multiplying certain fixed polynomials together and checking nonnegativity of the coefficients of the resulting product.

In part (ii), we introduce a new class of optimization problems whose constraints are imposed by trajectories of a dynamical system. As a concrete example, we consider the problem of optimizing a linear function over the set of initial conditions that forever remain inside a given polyhedron under the action of a linear, or a switched linear, dynamical system. We present a hierarchy of linear and semidefinite programs that respectively lower and upper bound the optimal value of such problems to arbitrary accuracy. 

Amir Ali Ahmadi ( http://aaa.princeton.edu/ ) is an Assistant Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Department of Computer Science. Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ''Computing and Optimization’’) has received the 2017 Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers. Amir Ali is also the recipient of a number of best-paper awards, including the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 2013-2015. 

PACM Colloquium

Speaker: 
Yuval Peres - Microsoft Research
Date: 
Oct 2 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA

PACM Colloquium

Speaker: 
Veit Elser, Cornell University
Date: 
Oct 9 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA

PACM & CSML Joint Colloquium: Methods of network comparison

Speaker: 
Sofia Olhede, University College London
Date: 
Oct 16 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

The topology of any complex system is key to understanding its structure and function. Fundamentally, algebraic topology guarantees that any system represented by a network can be understood through its closed paths. The length of each path provides a notion of scale, which is vitally important in characterizing dominant modes of system behavior. Here, by combining topology with scale, we prove the existence of universal features which reveal the dominant scales of any network. We use these features to compare several canonical network types in the context of a social media discussion which evolves through the sharing of rumors, leaks and other news. Our analysis enables for the first time a universal understanding of the balance between loops and tree-like structure across network scales, and an assessment of how this balance interacts with the spreading of information online. Crucially, our results allow networks to be quantified and compared in a purely model-free way that is theoretically sound, fully automated, and inherently scalable.

This work is joint with Patrick Wolfe.

Sofia is a professor of Statistics, an honorary professor of Computer Science and a senior research associate of Mathematics at University College London. She joined UCL in 2007, before which she was a senior lecturer of statistics (associate professor) at Imperial College London (2006-2007), a lecturer of statistics (assistant professor) (2002-2006), where she also completed her PhD in 2003 and MSci in 2000. She has held three research fellowships while at UCL: UK Engineering and Physical Sciences Springboard fellowship as well as a five-year Leadership fellowship, and now holds a European Research Council Consolidator fellowship. Sofia has contributed to the study of stochastic processes; time series, random fields and networks. She is on the ICMS Programme Committee since September 2008, a member of the London Mathematical Society Research Meetings Committee,  a member of the London Mathematical Society Research Policy Committee and an associate Editor for Transactions in Mathematics and its Applications. Sofia is also a member of the Royal Society and British Academy Data Governance Working Group, and the Royal Society working group on machine learning.

PACM & CSML Joint Colloquium: Mean estimation: median-of-means tournaments

Speaker: 
Gábor Lugosi, ICREA & Pompeu Fabra University, Spain
Date: 
Oct 23 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

One of the most basic problems in statistics is how to estimate the expected value of a distribution, based on a sample of independent random draws. When the goal is to minimize the length of a confidence interval, the usual empirical mean has a sub-optimal performance, especially for heavy-tailed distributions. In this talk we discuss some estimators that achieve a sub-Gaussian performance under general conditions. The multivariate scenario turns out to be more challenging. We present an estimator with near-optimal performance. We also discuss how these ideas extend to regression function estimation.

The talk is based on joint work with Shahar Mendelson (Technion, Israel), Luc Devroye (Mcgill University, Canada), Matthieu Lerasle (CNRS, France) and Roberto Imbuzeiro Oliveira (IMPA, Brazil).

Gabor Lugosi is an ICREA Research Professor at the Pompeu Fabra University in Barcelona, Spain where he has been since 1996. He received his PhD in Electrical Engineering from the Hungarian Academy of Sciences in 1991. His research interests include the theory of machine learning,  combinatorial statistics, inequalities in probability, random graphs and random structures, and information theory.

PACM Colloquium

Speaker: 
Cesare Tronci, University of Surrey, Guilford, UK
Date: 
Nov 6 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA

PACM Colloquium

Speaker: 
Cyrill Muratov, NJ Institute of Technology
Date: 
Nov 20 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA

PACM Colloquium

Speaker: 
Jens Eggers, Bristol University
Date: 
Nov 27 2017 - 4:00pm
Event type: 
PACM Colloquium
Room: 
214 Fine Hall
Abstract: 

TBA