SILO: A scalable method to exploit screening in Gaussian process models with noise
2024-01-31 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Chris Geoga

Towards a new toolbox of optimal statistical primitives
2024-02-05 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Abstract: Given society’s increasing reliance on data, its collection and processing into useful information is a technical problem of growing focus, and perhaps paradoxically, a critical bottleneck in many data science and machine learning applications. My research focuses on designing algorithms that push the limits of both statistical efficiency and computational efficiency. In particular, my work tackles the divide between the theory and practice of data science, which exists even for the most basic statistical problems including mean and (co)variance estimation. Conventional methods such as the sample mean, while supported by theoretical results under strong assumptions, are often brittle in the presence of extreme data points. To counter such deficiencies, practitioners often use ad-hoc and unprincipled “outlier removal” heuristics, revealing a marked gap between the theory and practice even for these fundamental problems.
In this talk, I will describe my work towards building a new toolbox of optimal statistical primitives, bridging the theory-practice divide. I will specifically highlight 3 works: A) constructing a statistically-optimal and computationally-efficient 1-dimensional mean estimator, whose estimation error is optimal even in the leading multiplicative constant, under bare minimum distributional assumptions, B) a rather different but also optimal mean estimator for the “very high-dimensional” regime, and C) a recent result on robustly clustering Gaussian mixtures based on their covariances even in the presence of adversarial data corruption. To conclude the talk, I will discuss my vision for the new theory and toolbox, serving as a blueprint for my long-term future research.
Bio: Jasper Lee is a postdoctoral research associate at the University of Wisconsin-Madison, mentored by Ilias Diakonikolas in the Department of Computer Sciences, and also affiliated with the Institute for Foundations of Data Science. He completed his PhD at Brown University, advised by Paul Valiant.
His research interests are broadly in the foundations of data science, aiming to design practical, data-efficient and computationally-efficient algorithms for a variety of statistical applications.
His work is partially supported by a Croucher Fellowship for Postdoctoral Research.

SILO: Universality in High-Dimensional Statistics
2024-02-07 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Rishabh Dudeja

Policy Optimization with Compatible Mirror Approximation
2024-02-09 13:30 - 14:30 (America/Los_Angeles) | Zoom
Speaker Bio: Zhihan is a fourth-year PhD student in the Paul G. Allen School of Computer Science & Engineering at University of Washington, advised by Prof. Maryam Fazel. His research interests are broadly in statistics, optimization and machine learning.

Abstract: We propose Compatible Mirror Policy Optimization (CoMPO), a framework that incorporates general function approximation into policy mirror descent methods. In contrast to the popular approach of using the $L_2$ norm to measure function approximation errors (regardless of the mirror map), CoMPO uses the Bregman divergence induced by the specific mirror map for policy projection. Such a compatibility bridges the gap between theory and practice: not only does it achieve fast linear convergence with general function approximation, but it also includes several well-known practical methods as special cases, immediately providing them strong convergence guarantees.

Theoretical exploration of foundation model adaption methods
2024-02-12 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Speaker: Kangwook Lee

SILO: Theoretical Exploration of Foundation Model Adaptation Methods
2024-02-14 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Kangwook Lee

Offline Multi-task Transfer RL with Representational Penalization
2024-02-16 13:30 - 14:30 (America/Los_Angeles) | CSE (Allen) 403
Speaker Bio: Avinandan is a second year PhD student, advised by Maryam Fazel and Lillian Ratliff. His interests are in sequential learning and game theory.

Abstract: We study the problem of representational transfer in offline Reinforcement Learning (RL), where a learner has access to episodic data from a number of source tasks collected a priori, and aims to learn a shared representation to be used in finding a good policy for a target task. Unlike in online RL where the agent interacts with the environment while learning a policy, in the offline setting there cannot be such interactions in either the source tasks or the target task; thus multi-task offline RL can suffer from incomplete coverage.We propose an algorithm to compute pointwise uncertainty measures for the learnt representation, and establish a data-dependent upper bound for the suboptimality of the learnt policy for the target task. Our algorithm leverages the collective exploration done by source tasks to mitigate poor coverage at some points by a few tasks, thus overcoming the limitation of needing uniformly good coverage for a meaningful transfer by existing offline algorithms. We complement our theoretical results with empirical evaluation on a rich-observation MDP which requires many samples for complete coverage. Our findings illustrate the benefits of penalizing and quantifying the uncertainty in the learnt representation.

A good score does not lead to a good generative model
2024-02-19 12:30 - 13:30 (America/Chicago) | WID 1145, 330 N Orchard Street, Madison, WI, 53715, United States
Speaker: Sixu Li
Abstract: Score-based Generative Models (SGMs) is one leading method in generative modeling, renowned for their ability to generate high-quality samples from complex, high-dimensional data distributions. The method enjoys empirical success and is supported by rigorous theoretical convergence properties. In particular, it has been shown that SGMs can generate samples from a distribution that is close to the ground-truth if the underlying score function is learned well, suggesting the success of SGM as a generative model. We provide a counter-example in this paper. Through the sample complexity argument, we provide one specific setting where the score function is learned well. Yet, SGMs in this setting can only output samples that are Gaussian blurring of training data points, mimicking the effects of kernel density estimation. The finding resonates a series of recent finding that reveal that SGMs can demonstrate strong memorization effect and fail to generate. This is joint with Shi Chen and Qin Li.

SILO: Foundations of Real-World Reinforcement Learning
2024-02-21 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Jeongyeol Kwon

GumbelSpec Sampling for Accelerating LLM Inference
2024-02-23 13:30 - 14:30 (America/Los_Angeles) | CSE (Allen) 403
Bio: Tianxiao Shen is a postdoctoral scholar at the University of Washington, working with Yejin Choi and Zaid Harchaoui. Her research interests lie in natural language processing and machine learning, in particular developing models and algorithms for efficient, accurate, diverse, flexible and controllable text generation. She received her PhD from MIT, advised by Regina Barzilay and Tommi Jaakkola. Before that, she did her undergrad at Tsinghua University.

Abstract: We propose GumbelSpec sampling, a novel algorithm that leverages smaller language models to accelerate inference of large language models without changing their output distribution. Central to our approach is the application of the Gumbel-Softmax technique to convert the stochastic decoding process into a deterministic process by integrating independently sampled Gumbel noise. Employing the same set of Gumbel noise, we perform beam search on the smaller model to generate multiple candidate short continuations, and then utilize tree-based attention to efficiently verify them in parallel using the larger model. GumbelSpec sampling significantly improves upon previous rejection sampling based speculative decoding methods by increasing the token acceptance rate by 1.7x-2.2x and achieving an additional speedup of 1.2x-1.5x. This results in a total speedup of 1.5x-2.6x compared to traditional autoregressive decoding.

Prelimit coupling and steady-state convergence of constant-stepsize nonsmooth contractive SA
2024-02-26 12:30 - 13:30 (America/Chicago) | WID 1145, 330 N Orchard Street, Madison, WI, 53715, United States
Speaker: Yixuan Zhang

Abstract:
Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA.

SILO: Reinforcement Learning with Robustness and Safety Guarantees
2024-02-28 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Dileep Kalathil, TAMU

IFDS Ideas Forum Double Header
2024-03-04 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Speaker 1: Puqian Wang
Robustly Learning Single-Index Models via Alignment Sharpness
Abstract: We study the problem of learning Single-Index Models under the L_2^2 loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximation to the optimal loss, that succeeds under a range of distributions (including log-concave distributions) and a broad class of monotone and Lipschitz link functions. This is the first efficient constant factor approximate agnostic learner, even for Gaussian data and for any nontrivial class of link functions. Prior work for the case of unknown link function either works in the realizable setting or does not attain constant factor approximation. The main technical ingredient enabling our algorithm and analysis is a novel notion of a local error bound in optimization that we term alignment sharpness and that may be of broader interest.

Speaker 2: Lisheng Ren
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
Abstract: The talk focuses on the complexity of Non-Gaussian Component Analysis (NGCA) in the Statistical Query (SQ) model. The NGCA has been a useful problem framework for obtaining SQ hardness for a variety of statistical problems. In particular, it was previously known that for any univariate distribution $A$ satisfying certain conditions, distinguishing between a standard multivariate Gaussian and a distribution that behaves like $A$ in a random hidden direction and like a standard Gaussian in the orthogonal complement, is SQ-hard. This required 1) $A$ matches many low-order moments with a standard Gaussian, and (2) the chi-squared norm of $A$ with respect to the standard Gaussian is finite, where the chi-squared restriction is needed for technical reasons. In this talk, we will present the new result that shows the Condition (2) above is indeed not necessary.

SILO: Online Learning Guided Quasi-Newton Methods: Improved Global Non-asymptotic Guarantees
2024-03-06 12:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Aryan Mokhtari, UT

Low-Rank Structures in Optimal Transport
2024-03-08 13:30 - 14:30 (America/Chicago) | CSE (Allen) 403
Bio: Meyer Scetbon is currently a Research Scientist at Microsoft Research. He completed his PhD at Institut Polytechnique de Paris, advised by M. Cuturi. He did, as a visiting student, his MS theses UW and Technion, on kernel-based viewpoints on deep neural networks advised by Z. Harchaoui, and end-to-end signal and image denoising advised by M. Elad, respectively.

Abstract: Optimal transport (OT) plays an increasingly important role in machine learning (ML) to compare probability distributions. Yet, it poses, in its original form, several challenges when used for applied problems: (i) computing OT between discrete distributions amounts to solving a large and expensive network flow problem which requires a supercubic complexity in the number of points; (ii) estimating OT using sampled measures is doomed by the curse of dimensionality. These issues can be mitigated using an entropic regularization, solved with the Sinkhorn algorithm, which improves on both statistical and computational aspects. While much faster, entropic OT still requires a quadratic complexity with respect to the number of points and therefore remains prohibitive for large-scale problems. In this talk, I will present new regularization approaches for the OT problem, as well as its quadratic extension, the Gromov-Wasserstein (GW) problem, which impose low-rank structures on the admissible couplings. This results in the development of new algorithms that enjoy a linear complexity both in time and memory with respect to the number of points, enabling their applications in the large-scale setting where millions of points need to be compared. Additionally, I will show that these new regularization schemes have better statistical performances compared to the entropic approach, that they naturally interpolate between the Maximum Mean Discrepancy (MMD) and OT, and that they offer general clustering methods for arbitrary geometry.Website: <https://meyerscetbon.github.io/_pages/publications/>

Towards Plurality: Learning from Diverse Human Preferences
2024-03-11 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Speaker: Ramya Vinayak

Abstract:
Large pre-trained models trained on internet-scale data are often not ready for safe deployment out of the box. They are heavily fine-tuned and aligned using large quantities of human preference data. When we want to align an AI/ML model to human preference or values, it is worthwhile to ask whose preference and values we are aligning it to? Recently, the limitations of current approaches due to their inherent uniformity assumption have been highlighted and the need for plurality – capturing the diversity in human preferences and values – is getting recognized as an important challenge to address. While alignment from human preferences has currently become a very active area of research, it is worthwhile to note that there is rich literature on learning preferences from human judgements using comparison queries. It plays a crucial role in several applications ranging from cognitive and behavioral psychology, crowdsourcing democracy, surveys in social science applications, and recommendation systems. However, the models in the literature often focus on learning average preference over the population due to the limitations on the amount of data available per individual and also assume the knowledge of the metric or way humans judge similarity and dissimilarity.
In this talk, I will discuss some recent results that focus on how we can reliably capture diversity in preferences while pooling together data from individuals. In particular, I will talk about fundamental questions in two directions: (1) Simultaneous metric and preference learning where the goal is to learn an unknown shared metric from preference queries while the preferences are diverse and also unknown. (2) Learning distribution of preferences over a population with a single comparison query per individual.
Bio:
Ramya Korlakai Vinayak is an assistant professor in the Dept. of ECE and affiliated faculty in the Dept. of Computer Science and the Dept. of Statistics at the UW-Madison. Her research interests span the areas of machine learning, statistical inference, and crowdsourcing. Her work focuses on addressing theoretical and practical challenges that arise when learning from heterogeneous data from people. Prior to joining UW-Madison, Ramya was a postdoctoral researcher in the Paul G. Allen School of Computer Science and Engineering at the University of Washington. She received her Ph.D. in Electrical Engineering from Caltech. She obtained her Masters from Caltech and Bachelors from IIT Madras. She is a recipient of the Schlumberger Foundation Faculty of the Future fellowship from 2013-15, and an invited participant at the Rising Stars in EECS workshop in 2019. She is the recipient of NSF CAREER Award 2023-2028.

SILO: Unsupervised Learning: Validation beyond Visualization
2024-03-13 12:30 (America/Chicago) | Researchers’ Link, 330 N Orchard St, Madison, WI, 53715, United States
Marina Meila, UWash

Optimized Decision Making via Active Learning of Stochastic Hamiltonians
2024-03-15 13:30 - 14:30 (America/Los_Angeles) | CSE (Allen) 403
Speaker: Prof. Chandrajit Bajaj , UT Austin
Abstract: A Hamiltonian represents the energy of a dynamical system in phase space with coordinates of position and momentum. The Hamilton’s equations of motion are obtainable as coupled symplectic differential equations. In this talk I shall show how optimized decision making (action sequences) can be obtained via a reinforcement learning problem wherein the agent interacts with the unknown environment to simultaneously learn a Hamiltonian surrogate and the optimal action sequences using Hamilton dynamics, by invoking the Pontryagin Maximum Principle. We use optimal control theory to define an optimal control gradient flow, which guides the reinforcement learning process of the agent to progressively optimize the Hamiltonian while simultaneously converging to the optimal action sequence. Extensions to stochastic Hamiltonians leading to stochastic action sequences and the free-energy principle shall also be discussed. This is joint work with Taemin Heo, Minh Nguyen.

IFDS Ideas Forum Double Header
2024-03-18 12:30 - 13:30 (America/Chicago) | WID 1145, 330 N Orchard Street, Madison, WI, 53715, United States
Karan Srivastava

Harit Vishwakarma: “Confidence functions for auto-labeling”

SILO:
2024-03-20 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Chao Gao, U Chicago

SILO:
2024-04-03 12:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Devavrat Shah, MIT

SILO:
2024-04-10 12:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
CMU, Weina Wang

SILO:
2024-04-17 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Zachary Lubberts, UVA

SILO: Generalized Tensor Decompositions: Algorithms and Applications
2024-04-24 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
David Hong, UDel

SILO:
2024-05-01 12:30 - 13:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Sam Hopkins, MIT

SILO:
2024-05-08 12:30 (America/Chicago) | Orchard View Room, 330 N. Orchard Street, 3rd Floor NE, Madison, Wisconsin, 53715, United States
Max Raginsky, UIUC
