Statistics and Data Science Seminar

Abstract

This talk will introduce three new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning:

• Given an initial n point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n points with comparable worst-case integration error across a reproducing kernel Hilbert space.
• If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases.
• Finally, Compress++ converts any unbiased quadratic-time thinning algorithm into a near-linear-time algorithm with comparable error.

Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich:

• Kernel Thinning (arXiv:2105.05842)
• Optimal Thinning of MCMC Output (arXiv:2005.03952)
• Generalized Kernel Thinning (arXiv:2110.01593)
• Distribution Compression in Near-linear Time (arXiv:2111.07941)
• Compress Then Test: Powerful Kernel Testing in Near-linear Time (arXiv:2301.05974)

Bio

Lester Mackey is a Principal Researcher at Microsoft Research, where he develops machine learning methods, models, and theory for large-scale learning tasks driven by applications from climate forecasting, healthcare, and the social good. Lester moved to Microsoft from Stanford University, where he was an assistant professor of Statistics and, by courtesy, of Computer Science. He earned his PhD in Computer Science and MA in Statistics from UC Berkeley and his BSE in Computer Science from Princeton University. He co-organized the second place team in the Netflix Prize competition for collaborative filtering; won the Prize4Life ALS disease progression prediction challenge; won prizes for temperature and precipitation forecasting in the yearlong real-time Subseasonal Climate Forecast Rodeo; and received best paper, outstanding paper, and best student paper awards from the ACM Conference on Programming Language Design and Implementation, the Conference on Neural Information Processing Systems, and the International Conference on Machine Learning. He is a 2023 MacArthur Fellow, a Fellow of the Institute of Mathematical Statistics, an elected member of the COPSS Leadership Academy, and the recipient of the 2023 Ethel Newbold Prize.

Abstract:
In this talk, we will discuss recent progress on mathematical analysis of flow based generative models, which is a highly successful approach for learning a probability distribution from data and generating further samples.
We will talk about some recent results in convergence analysis of diffusion models and related flow-based methods. In particular, we established convergence of score-based diffusion models applying to any distribution with bounded 2nd moment, relying only on a $L^2$-accurate score estimates, with polynomial dependence on all parameters and no reliance on smoothness or functional inequalities. We will also discuss convergence analysis of flow-based generative models based on tools from optimal transportation, viewing the forward process as a proximal gradient descent under Wasserstein metric.

Bio:
Jianfeng Lu is a Professor of Mathematics, Physics, and Chemistry at Duke University. Before joining Duke University, he obtained his PhD in Applied Mathematics from Princeton University in 2009 and was a Courant Instructor at New York University from 2009 to 2012. He works on mathematical analysis and algorithm development for problems and challenges arising from computational physics, theoretical chemistry, materials science, high-dimensional PDEs, and machine learning. He is a fellow of AMS. His work has been recognized by a Sloan Fellowship, a NSF Career Award, the IMA Prize in Mathematics and its Applications, and the Feng Kang Prize.

Abstract:
Many important machine learning problems can be formulated as highly constrained convex optimization problems. One important example is metric constrained problems. In this paper, we show that standard optimization techniques can not be used to solve metric constrained problems.

To solve such problems, we provide a general active set framework, called Project and Forget, and several variants thereof that use Bregman projections. Project and Forget is a general purpose method that can be used to solve highly constrained convex problems with many (possibly exponentially) constraints. We provide a theoretical analysis of Project and Forget and prove that our algorithms converge to the global optimal solution and have a linear rate of convergence. We demonstrate that using our method, we can solve large problem instances of general weighted correlation clustering, metric nearness, information theoretic metric learning and quadratically regularized optimal transport; in each case, out-performing the state of the art methods with respect to CPU times and problem sizes.

Joint work with Rishi Sonthalia (UCLA)

Bio:
Anna Gilbert is the John C. Malone Professor of Mathematics and Professor of Statistics & Data Science, working in the Department of Electrical Engineering at Yale University, with previous positions at the University of Michigan and AT&T Labs-Research.
She has received several awards, including a Sloan Research Fellowship (2006), an NSF CAREER award (2006), the National Academy of Sciences Award for Initiatives in Research (2008), the Association of Computing Machinery (ACM) Douglas Engelbart Best Paper award (2008), the EURASIP Signal Processing Best Paper award (2010), and the SIAM Ralph E. Kleinman Prize (2013).
She received an S.B. degree from the University of Chicago and a Ph.D. from Princeton University, both in Mathematics.  Her research interests include analysis, probability, discrete mathematics, and algorithms. She is especially interested in randomized algorithms with applications to harmonic analysis, signal and image processing, and massive datasets.

Abstract:
In 1948, Shannon used a probabilistic argument to prove the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various branches of discrete mathematics involved. In particular, the special case of the erasure channel was settled in 2015 by Kudekar at al., relying on Bourgain-Kalai’s sharp threshold theorem for symmetric monotone properties. The case of error channels remained however unsettled, due in particular to the property being non-monotone and the absence of techniques to obtain fast local error decay (despite Reeves-Pfister’s result on a vanishing local error). In this talk, we provide a proof of the general conjecture. The proof circumvents the use of Bourgain-Kalai’s theorem by establishing first a “weak threshold” property that relies solely on symmetries. The proof then proceeds with a new boosting framework for coding, improving the weak local error to a strong global error by relying on sunflower structures (as in Erdős-Rado 1960). Joint work with Colin Sandon.

Bio:
Emmanuel Abbé received his Ph.D. degree from the EECS Department at the Massachusetts Institute of Technology (MIT) in 2008, and his M.S. degree from the Department of Mathematics at the Ecole Polytechnique Fédérale de Lausanne in 2003. He joined EPFL in 2018 as a Full Professor, jointly in the Mathematics Institute and the School of Computer and Communication Sciences, where he holds the Chair of Mathematical Data Science. He is the recipient of the Foundation Latsis International Prize, the Bell Labs Prize, the NSF CAREER Award, the Google Faculty Research Award, the Walter Curtis Johnson Prize, the von Neumann Fellowship from the Institute for Advanced Study, the IEEE Information Theory Society Paper Award, and a co-recipient of the Simons-NSF Mathematics of Deep Learning Collaborative Research Award.

Abstract: In this talk, we revisit classical results in the theory of statistical aggregation, focusing on the transition from global complexity to a more manageable local one. The goal of aggregation is to combine several base predictors to achieve a prediction nearly as accurate as the best one, without assumptions on the class structure or target. Though studied in both sequential and statistical settings, they traditionally use the same “global” complexity measure. We highlight the lesser-known PAC-Bayes localization enabling us to prove a localized bound for the exponential weights estimator by Leung and Barron, and a deviation-optimal localized bound for Q-aggregation. Finally, we demonstrate that our improvements allow us to obtain bounds based on the number of near-optimal functions in the class, and achieve polynomial improvements in sample size in certain nonparametric situations. This is contrary to the common belief that localization doesn’t benefit nonparametric classes. Joint work with Jaouad Mourtada and Tomas Vaškevičius.

—-

Bio: Nikita Zhivotovskiy is an Assistant Professor in the Department of Statistics at the University of California Berkeley. He previously held postdoctoral positions at ETH Zürich in the department of mathematics hosted by Afonso Bandeira, and at Google Research, Zürich hosted by Olivier Bousquet. He also spent time at the Technion I.I.T. mathematics department hosted by Shahar Mendelson. Nikita completed his thesis at Moscow Institute of Physics and Technology under the guidance of Vladimir Spokoiny and Konstantin Vorontsov.

Abstract:

We consider the Error-in-Operator (EiO) problem of recovering the source x signal from the noise observation Y given by the equation Y = A x + ε in the situation when the operator A is not precisely known. Instead, a pilot estimate hat{A} is available. The study is motivated by Hoffmann & Reiss (2008), Trabs (2018) and by recent results on high dimensional regression with random design; see e.g., Tsigler, Bartlett (2020) (Benign overfitting in ridge regression; arXiv:2009.14286) Cheng, and Montanari (2022) (Dimension free ridge regression; arXiv:2210.08571), among many others. Examples of EiO include regression with error-in-variables and instrumental regression, stochastic diffusion, Markov time series, interacting particle systems. New approach is suggested which allows to obtain finite sample nearly sharp accuracy guarantees and incorporate the smoothness of the signal x and the operator A in a rather general form.

Bio:
Vladimir Spokoinyi received his PhD from the Department of Mechanics and Mathematics of the Lomonosov Moscow State University and did his Habilitation on “Statistical Experiments and Decisions: Asymptotic Theory” at the Humboldt University of Berlin. He is the head of the research group “Stochastic Algorithms & Nonparametric Statistics” of the Weierstrass Institute for Applied Analysis & Stochastics and Professor at the Humboldt University of Berlin. Spokoinyi’s main research interests lie in adaptive nonparametric smoothing and hypothesis testing, high dimensional data analysis and nonlinear time series, with applications to financial and imaging sciences. He is IMS Fellow and 2011 recipient of one of the multimillion-dollar Mega-grant projects awarded by the Russian government. 

Abstract:

We consider estimation of parameters defined as linear functionals of solutions to linear inverse problems. Any such parameter admits a doubly robust representation that depends on the solution to a dual linear inverse problem, where the dual solution can be thought as a generalization of the inverse propensity function. We provide the first source condition double robust inference method that ensures asymptotic normality around the parameter of interest as long as either the primal or the dual inverse problem is sufficiently well-posed, without knowledge of which inverse problem is the more well-posed one. Our result is enabled by novel guarantees for iterated Tikhonov regularized adversarial estimators for linear inverse problems, over general hypothesis spaces, which are developments of independent interest.

Paper: arxiv.org/pdf/2307.13793.pdf

Bio:

Vasilis Syrgkanis is an Assistant Professor of Management Science and Engineering and (by courtesy) of Computer Science and Electrical Engineering at Stanford University. Prior to that he was a Principal Researcher at Microsoft Research, New England, where he was co-leading the project on Automated Learning and Intelligence for Causation and Economics (ALICE). He received his Ph.D. in Computer Science from Cornell University in 2014, under the supervision of Prof. Eva Tardos and spent two years at Microsoft Research, New York as a postdoctoral researcher. His research addresses problems at the intersection of machine learning, causal inference, economics, statistics and theoretical computer science. His work has received several awards, such as best paper awards at the 2015 ACM Conference on Economics and Computation (EC’15), the 2015 Annual Conference on Neural Information Processing Systems (NeurIPS’15) and the Conference on Learning Theory (COLT’19),  the Bodossaki Distinguished Young Scientist award and an Amazon Research award.

Abstract:

The low-degree polynomial framework has emerged as a versatile tool for probing the computational complexity of statistical problems by studying the power and limitations of a restricted class of algorithms: low-degree polynomials. Focusing on the setting of hypothesis testing, I will discuss some extensions of this method that allow us to tackle finer-grained questions than the standard approach.

First, for the task of detecting a planted clique in a random graph, we ask not merely when this can be done in polynomial time O(n^c), but seek the optimal exponent c as a function of the clique size. To this end, we consider algorithms that make non-adaptive edge queries and then apply a low-degree test, and we determine the number of queries required. This is joint work with Jay Mardia and Kabir Verchand.

Second, in the spiked Wigner model with any iid spike prior, we seek the precise optimal tradeoff curve between type I and type II error rates. Conditional on an appropriate strengthening of the “low-degree conjecture,” we show that tests based on the spectrum achieve the best possible tradeoff curve among poly-time algorithms, while exponential-time non-spectral tests can do better. This is joint work with Ankur Moitra.

Bio:

Alex Wein received his PhD from MIT Mathematics in 2018 supervised by Ankur Moitra. He is now an Assistant Professor of Mathematics at UC Davis. His research spans theoretical computer science, statistics, probability, and data science, with an emphasis on understanding the computational complexity of high-dimensional statistical inference. He is a recipient of the 2018 Charles W and Jennifer C Johnson Prize from MIT, and the 2023 Sloan Research Fellowship.

Abstract:

In this talk, we will present highlights from some of the work we have been doing in distributed inference under information constraints, such as privacy and communication. We consider basic tasks such as learning and testing of discrete as well as high dimensional distributions, when the samples are distributed across users who can then only send an information-constrained message about their sample. Of key interest to us has been the role of the various types of communication protocols (e.g., non-interactive protocols vs interactive protocols, etc). We will also discuss some recent results on estimation of discrete distributions with user level information constraints, where multiple samples per user are available at each user.

This talk is based on works with Clement Canonne, Yuhan Liu, Ziteng Sun, and Himanshu Tyagi.

Bio:

Jayadev Acharya is an associate professor in Electrical and Computer Engineering at Cornell University. He has a PhD from UCSD and was a postdoc at MIT. He is broadly interested in problems at various intersections of information theory, statistical inference, algorithms, and machine learning. He received a best paper award at ALT 2020, a best paper honorable mention at ICML 2017, and the Jack Wolf student paper award at ISIT 2010.

Abstract:
In this talk, I will argue that it is sometimes possible to learn, with techniques originated from bandits, the “hints” on which learning-augmented algorithms rely to improve worst-case performances. We will describe this phenomenon, the combination of online learning with competitive analysis, on the example of stochastic online scheduling. We shall quantify the merits of this approach by computing and comparing non-asymptotic expected competitive ratios (the standard performance measure of algorithms)

Bio:
Vianney Perchet is a professor at the Centre de recherche en économie et statistique (CREST) at the ENSAE. Mainly focusing on the interplay between machine learning and game theory, his themes of research are at the junction of mathematics, computer science and economics. The spectrum of his interest ranges from pure theory  (say, optimal rates of convergence of algorithms) to pure applications (modeling user behavior, optimisation of recommender systems, etc.) He is also a part-time principal researcher in the Criteo AI Lab, in Paris, working on efficient exploration in recommender systems.