PACM Colloquium
Spring 2018
PACM Colloquium: A Matrix Expander Chernoff BoundSpeaker: Nikhil Srivastava, UC Berkeley Date: Feb 5 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: The Matrix Chernoff Bound asserts that a sum of independent bounded random matrices concentrates around its mean. We prove a conjecture of Wigderson and Xiao, asserting that the same conclusion is true when the matrices are not independent, but sampled according to a random walk on a Markov chain with a spectral gap (i.e., an expander graph). This implies a blackbox derandomization of many applications of the matrix Chernoff bound. A key ingredient in the proof is a multimatrix extension of the GoldenThompson inequality, based on the work of Sutter et al., which relates the trace of the matrix exponential of a sum of many matrices to a the trace of the product of their exponentials. Joint work with Ankit Garg, Yin Tat Lee, and Zhao Song. 
CANCELLED: Joint PACMCSML ColloquiumSpeaker: David Blei, Columbia University Date: Feb 12 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: To be rescheduled at a later date. 
PACM Colloquium: Learning the learning rate in stochastic gradient descentSpeaker: Rachel Ward, University of Texas Date: Feb 19 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Finding a proper learning rate in stochastic optimization is an important problem. Choosing a learning rate that is too small leads to painfully slow convergence, while a learning rate that is too large can cause the loss function to fluctuate around the minimum or even to diverge. In practice, the learning rate is often tuned by hand for different problems at hand. Several methods have been proposed recently for automatic adjustment of the learning rate according to gradient data that is received along the way. We review these methods, and propose a simple method, inspired by reparametrization of the loss function in polar coordinates. We prove that the proposed method achieves optimal oracle convergence rates in batch and stochastic settings, but without having to know certain parameters of the loss function in advance. Rachel Ward is an Associate Professor of Mathematics in the Department of Mathematics at University of Texas at Austin and has been a member of the faculty since 2011. She is currently a visiting research scientist at Facebook AI Research. She received a PhD in Computational and Applied Mathematics at Princeton in 2009 and was a Courant Instructor at the Courant Institute, NYU, from 20092011. Her research interests span signal processing, machine learning, and optimization. She has received the Sloan research fellowship, NSF CAREER award, and the 2016 IMA prize in mathematics and its applications. 
PACM Colloquium: Statistical and Computational Limits for Submatrix Localization and Sparse Matrix DetectionSpeaker: Tony Cai, Wharton School  UPenn Date: Feb 26 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: In the conventional statistical framework, the goal is developing optimal inference procedures, where optimality is understood with respect to the sample size and parameter space. When the dimensionality of the data becomes large as in many contemporary applications, the computational concerns associated with the statistical procedures come to the forefront. A fundamental question is: Is there a price to pay for statistical performance if one only considers computable (polynomialtime) procedures? After all, statistical methods are useful in practice only if they can be computed within a reasonable amount of time. In this talk, we discuss the interplay between statistical accuracy and computational efficiency in two specific problems: submatrix localization and sparse matrix detection based on a noisy observation of a large matrix. The results show some interesting phenomena that are quite different from other highdimensional problems studied in the literature. Tony Cai is the Dorothy Silberberg Professor of Statistics at the Wharton School of the University of Pennsylvania. He is the recipient of the 2008 COPSS Presidents' Award, a Fellow and Medallion Lecturer of the Institute of Mathematical Statistics, and was a CoEditor for The Annals of Statistics (20102012). He is/was an associate editor for Journal of the Royal Statistical Society (Series B), Journal of American Statistical Association, and The Annals of Statistics. His current research interests include high dimensional statistics, statistical machine learning, largescale inference, and statistical decision theory. 
PACM ColloquiumSpeaker: Miranda HolmesCerfon, Courant Institute of Mathematical Sciences, NYU Date: Mar 26 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: TBA 
Joint PACM Colloquium/ORFE Wilks SeminarSpeaker: Marina Meila, University of Washington Date: Apr 2 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: TBA 
PACM ColloquiumSpeaker: Michael Bronstein, Università della Svizzera italiana (Switzerland), Tel Aviv University (Israel) Date: Apr 16 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: TBA 
Joint PACMEE ColloquiumSpeaker: Yury Polyanskiy, MIY Date: Apr 23 2018  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: TBA 
Fall 2017
PACM Colloquium: Walking within growing domains: recurrence versus transienceSpeaker: 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 ddimensional 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 SystemsSpeaker: 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 secondorder 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 bestpaper 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 20132015. 
PACM Colloquium: Trace reconstruction for the deletion channelSpeaker: Yuval Peres  Microsoft Research Date: Oct 2 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant probability $q$, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct $x$ with high probability? The best lower bound known is linear in $n$. Until recently, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis; this bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio). If the string $x$ is random and $q<1/2$, we can show a subpolynomial number of traces suffices by comparison to a biased random walk. (Joint works with Fedor Nazarov, STOC 2017 and with Alex Zhai, FOCS 2017). In very recent work with Nina Holden and Robin Pemantle, we removed the restriction $q<1/2$ for random inputs. Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 280 research papers and has coauthored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loève Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Mathematicians, and a plenary lecturer at the Mathematics Congress of the Americas in 2017. He has advised 21 Ph.D. students. In 2016 he was elected as a foreign associate to the U.S. National Academy of Sciences. 
PACM Colloquium: The reinvention of phase retrievalSpeaker: Veit Elser, Cornell University Date: Oct 9 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Phase retrieval, originally, was the idea of exploiting prior information in the reconstruction of a complexvalued signal when only its magnitude can be measured. The earliest and still most important application is the reconstruction of complex biomolecules from xray diffraction (magnitude) data taken from crystallized samples. Over the last few years, and in the applied math community, “phase retrieval” has become identified with a different problem: extending the reach of magnitudeonly data by expanding the set of “sensing vectors” used to interrogate the signal, and the design of algorithms that in the new setting can promise a successful reconstruction. This reinvention of phase retrieval is disappointing in two respects. First, owing to the extreme smallness of the xray/molecule interaction, the proposal of designed sensing vectors — in the main application of structural biology — is physically unfeasible. Second, the new algorithms designed for the new phase retrieval problem do not offer, in practice, significant advantages over older algorithms developed for the original problem, even as these do not come with a guarantee of success. 
PACM & CSML Joint Colloquium: Methods of network comparisonSpeaker: 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 treelike 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 modelfree 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 (20062007), a lecturer of statistics (assistant professor) (20022006), 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 fiveyear 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: medianofmeans tournamentsSpeaker: 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 suboptimal performance, especially for heavytailed distributions. In this talk we discuss some estimators that achieve a subGaussian performance under general conditions. The multivariate scenario turns out to be more challenging. We present an estimator with nearoptimal 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: Symmetry methods for quantum variational principles and expectation value dynamicsSpeaker: Cesare Tronci, University of Surrey, Guildford, UK Date: Nov 6 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Inspired by previous works by Kramer & Saraceno and Shi & Rabitz, this talk exploits symmetry methods for the variational formulation of different problems in physics and chemistry. First, I will use symmetry methods to provide new variational principles for the description of mixed quantum states, in various pictures including Schrödinger, Heisenberg, Dirac (interaction) and WignerMoyal. Then, after discussing Ehrenfest's meanfield model, I will modify its symmetry properties to provide a new variational principle for expectation value dynamics in general situations. Upon moving to the Hamiltonian approach, this construction provides a complete dynamical splitting between expectation values and quantum deviations. As we shall see, specializing to Gaussian states yields energy conserving variants of previous models from the chemistry literature. In the last part of the talk, I will discuss some of the geometric features emerging in coupled classicalquantum dynamics. Cesare obtained a Laurea in Nuclear Engineering in May 2004 at the Politecnico di Torino (Italy). Then, after spending two years (06/2003 – 05/2005) at CERN (Switzerland) working on microwave electronics under the direction of Ugo Amaldi (also at TU München and TERA Foundation), he moved to the Theoretical Division (in the former Plasma Theory Group) of the Los Alamos National Lab (LANL, USA), where he visited Giovanni Lapenta (now at KU Leuven, Belgium) for several months. In 10/2005, Cesare entered a PhD program at Imperial College, under the direction of Darryl Holm. In his thesis, he worked on geometric analogies between kinetic theory and porous media equations to model the aggregation of ferromagnetic nanoparticles. Between 2006 and 2007, he also spent two summers at LANL, working with Bruce Carlsten in the former International, Space & Response Division (High Power Electrodynamics Group). In 09/2008, Cesare joined the Mathematics Section of EPF Lausanne (Switzerland) as a research assistant in Tudor Ratiu’s group (Geometric Analysis). Since 01/2012, he is Lecturer (Assistant Professor) in the Department of Mathematics of the University of Surrey and have visited several institutions in Europe and North America. 
Joint CSML/PACM/EE Colloquium: Latent Variable Model, Matrix Estimation and Collaborative FilteringSpeaker: Devavrat Shah, Massachusets Institute of Technology Date: Nov 13 2017  4:30pm Event type: PACM Colloquium Room: Bowen Hall Auditorium Abstract: Estimating a matrix based on partial, noisy observations is prevalent in a variety of modern applications with recommendation system being a prototypical example. The nonparametric latent variable model provides canonical representation for such matrix data when the underlying distribution satisfies “exchangeability” with graphons and stochastic block model being recent examples of interest. Collaborative filtering has been a successfully utilized heuristic in practice since the dawn of ecommerce. In this talk, I will argue that collaborative filtering (and its variants) solve matrix estimation for a generic latent variable model with near optimal sample complexity. The talk is based on joint works with
Devavrat Shah is a Professor with the department of Electrical Engineering and Computer Science at Massachusetts Institute of Technology. His current research interests are at the interface of Statistical Inference and Stochastic Networks. His work has been recognized through career prizes including 2010 Erlang prize from the INFORMS Applied Probability Society and 2008 ACM Sigmetrics Rising Star Award. He is a distinguished young alumni of his alma mater IIT Bombay. 
PACM Colloquium: The mathematics of charged liquid dropsSpeaker: Cyrill Muratov, NJ Institute of Technology Date: Nov 20 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: In this talk, I will present an overview of recent analytical developments in the studies of equilibrium configurations of liquid drops in the presence of repulsive Coulombic forces. Due to the fundamental nature of Coulombic interaction, these problems arise in systems of very different physical nature and on vastly different scales: from femtometer scale of a single atomic nucleus to micrometer scale of droplets in electrosprays to kilometer scale of neutron stars. Mathematically, these problems all share a common feature that the equilibrium shape of a charged drop is determined by an interplay of the cohesive action of surface tension and the repulsive effect of longrange forces that favor drop fragmentation. More generally, these problems present a prime example of problems of energy driven pattern formation via a competition of longrange attraction and longrange repulsion. In the talk, I will focus on two classical models  Gamow's liquid drop model of an atomic nucleus and Rayleigh's model of perfectly conducting liquid drops. Surprisingly, despite a very similar physical background these two models exhibit drastically different mathematical properties. I will discuss the basic questions of existence vs. nonexistence, as well as some qualitative properties of global energy minimizers in these models, and present the current state of the art for this class of geometric problems of calculus of variations. Cyrill Muratov is Professor of Mathematical Sciences at New Jersey Institute of Technology. He received his M.Sc. in Applied Mathematics and Physics from Moscow Institute of Physics and Technology, followed by a Ph. D. in Physics from Boston University and postdoctoral training in Applied Mathematics at the Courant Institute. His main research interests lie in understanding the emergence of complexity from basic constitutive laws in problems of science and engineering, using a combination of rigorous mathematical analysis, formal asymptotics and numerical simulations.

PACM Colloquium: Two problems involving breakup of a liquid filmSpeaker: Jens Eggers, Bristol University Date: Nov 27 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Understanding the breakup of a liquid film is complicated by the fact that there is no obvious instability driving breakup: surface tension favors a film of uniform thickness over a deformed one. Here, we identify two mechanisms driving a film toward (infinite time) pinchoff. In the first problem, we show how the rise of a bubble is arrested in a narrow tube, on account of the lubricating film pinching off. In the second problem, breakup of a free liquid film is driven by a J. Eggers is a professor of Applied Mathematics at the University of Bristol. Dr. Eggers' career has been devoted to the understanding of selfsimilar phenomena. He has made fundamental contributions to our mathematical understanding of freesurface flows, in particular breakup and coalescence of drops. His work is instrumental in establishing the study singularities as a research field fluid dynamics and applied mathematics. With Marco Fontelos, he has recently published a book at Cambridge University Press, which presents a unifying view of singularities in Physics, Mathematics, and Engineering, and aims to make the subject accessible to a wider audience. He is a member of the Academy of Arts and Sciences in Erfurt, Germany, and a Fellow of the American Physical Society, and has been made a Euromech Fellow. Dr. Eggers' most recent work concerns the spatial structure of shock waves in compressible gas dynamics, and singularities in nonlinear elasticity. 
Phase Retrieval and systems of polynomial equationsSpeaker: Dan Ediden, University of Missouri Date: Dec 4 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: A signal vector can be easily reconstructed from a set of linear measurements such as the discrete Fourier transform. However, in many physical problems only the intensity, but not the phase, of the measurements can be obtained. From a mathematical perspective, the phase retrieval problem is to recover an unknown signal from the absolute values of a collection of measurements. This reconstruction problem has a long history in engineering and physics and arises in a variety of situations such as optics and speech recognition. In this talk we explain how, in many contexts, algebraic methods can be used to estimate the minimum number of phaseless measurements needed to recover generic signals. Dan Edidin is the Leonard Blumenthal Distinguished Professor of Mathematics at University of Missouri. Originally trained in algebraic geometry, he received his PhD from MIT under the supervision of Joe Harris and Steve Kleiman and was a postdoc at University of Chicago with Bill Fulton. His research interests are on problems related to group actions on algebraic varieties in both pure and applied mathematics. 
PACM Colloquium  Graphs, Dynamics, and RenormalizationSpeaker: Bernard Chazelle Date: Dec 11 2017  4:00pm Event type: PACM Colloquium Room: 214 Fine Hall Abstract: Nonlinear Markov chains are probabilistic models commonly used in physics, biology, and the social sciences. In "Markov influence systems," the transition probabilities of the chains may change as a function of the current state distribution. This talk will discuss a renormalization framework to help us analyze these systems. It allows us to show, for example,that Markov influence systems of the irreducible kind are almost surely periodic. I will place this work in the broader context of a research program whose main objective is to build new mathematical tools for "natural algorithms" and, more generally, outofequilibrium dynamics. Bernard Chazelle is Eugene Higgins Professor of Computer Science at Princeton University, where he has been on the faculty since 1986. His current research focuses on the “algorithmic nature” of living systems. A professor at the Collège de France in Paris in recent years as well as a member of the Institute for Advanced Study in Princeton, he received his PhD in computer science from Yale University in 1980. The author of the book, "The Discrepancy Method," he is a fellow of the American Academy of Arts and Sciences, the European Academy of Sciences, the Association for Computing Machinery, and the recipients of three BestPaper awards from SIAM. 