Quick links

CS Department Colloquium Series

Towards a Unified Approach to Average-Case Algorithm Design

Date and Time
Thursday, April 13, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Mark Braverman

Pravesh Kothari
Solving non-convex optimization problems on probabilistic models of inputs lies at the heart of foundational algorithmic challenges arising in high-dimensional statistical data analysis, beyond-worst-case combinatorial optimization, cryptography, and statistical physics.

In this talk, I will present a new method for average-case algorithm design that relies on a concrete polynomial time meta-algorithm called the sum-of-squares method. This method yields substantially improved and often nearly optimal guarantees for a wide range of problems.

I will focus on the impact of this method on two prominent areas of average-case algorithm design:

1) High-dimensional statistical estimation, where this method has led to efficient algorithms for classical data analysis tasks that provably tolerate adversarial data corruption while incurring minimal possible error. The resulting applications range from new robust estimators in high dimensions for basic tasks such as computing mean, covariance, and moments of data to more sophisticated tasks such as regression, clustering, sparse recovery, and fitting mixture models. Most recently, this theory led to the first efficient algorithm for robustly learning a high-dimensional mixture of Gaussians. This resolves a central open question in the area, which has a history going back to a famous work of Pearson from 1894. 

2) Beyond worst-case combinatorial optimization, where this method has led to new efficient algorithms that escape worst-case hardness while avoiding "overfitting" to brittle properties of any specific random model. Most recently, this line of work resulted in a resolution of longstanding open questions of finding optimal algorithms for "smoothed" models of k-SAT and "semirandom" models of Max-Clique. 

Taken together, these results suggest a unified theory for average-case algorithm design that not only makes substantial progress on long open foundational challenges but also brings a conceptual unity to algorithm design that we had never anticipated.

Bio: Pravesh Kothari is an Assistant Professor of Computer Science at Carnegie Mellon University since September 2019. Before joining CMU, he was a postdoctoral Research Instructor jointly hosted by Princeton University and the Institute for Advanced Study from 2016-19. He obtained his Ph.D. in 2016 from the University of Texas at Austin. Kothari's recent work has focused on algorithm design for problems with statistical inputs. It is also the subject of his recent monograph "Semialgebraic Proofs and Efficient Algorithm Design". His research has been recognized with a Simons Award for graduate students in Theoretical Computer Science, a Google Research Scholar Award, an NSF CAREER Award, and an Alfred P. Sloan Research Fellowship.  


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.
 

Towards Intelligent Data Systems

Date and Time
Monday, April 17, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
Kai Li

Yao Lu
From single-box databases, data systems are evolving into multi-tenant compute and storage platforms that host not only structured data analytics but also AI workloads and AI-enhanced system components. The result of this evolution, which I call an “intelligent” data system, creates new opportunities and challenges for research and production at the intersection of machine learning and systems.

Key considerations in these systems include efficiency and cost, ML support and a flexible runtime for heterogeneous jobs. I will describe our work on query optimizers both for AI and aided by AI. For ML inference workloads over unstructured data, our optimizer injects proxy models for queries with complex predicates leading to a many-fold improvement in processing time; for query optimization in classic data analytics, our pre-trained models summarize structured datasets, answer cardinality estimation calls, and avoid the high training cost in recent instance-optimized database components. I will also describe our query processor and optimizer that enable and accelerate ML inference workflows on hybrid/IoT cloud. These efforts, combined with a few missing pieces that I will outline, contribute to better data systems where users can build, deploy, and optimize data analytics and AI applications with ease.

Bio: Yao Lu is a researcher at the Data Systems group, Microsoft Research Redmond. He works at the intersection of machine learning and data systems towards improved data and compute platforms for cloud machine learning, as well as using machine learning to improve current data platforms. He received his Ph.D. from the University of Washington in 2018.


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.
 

In Pursuit of Visual Intelligence

Date and Time
Tuesday, April 25, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Jia Deng & Kai Li

Kaiming He
Last decade's deep learning revolution in part began in the area of computer vision. The intrinsic complexity of visual perception problems urged the community to explore effective methods for learning abstractions from data. In this talk, I will review a few major breakthroughs that stemmed from computer vision. I will discuss my work on Deep Residual Networks (ResNets) that enabled deep learning to get way deeper, and its influence on the broader artificial intelligence areas over the years. I will also review my work on enabling deep learning to solve complex object detection and segmentation problems in simple and intuitive ways.

On top of this progress, I will introduce recent research on learning from visual observations without human supervision, a topic known as visual self-supervised learning. I will discuss my research that contributed to shaping the two frontier directions on this topic. This research sheds light on future directions. I will discuss the opportunities for self-supervised learning in the visual world. I will also discuss how the research on computer vision may continue influencing broader areas, e.g., by generalizing self-supervised learning to scientific observations from nature.

Bio: Kaiming He is a Research Scientist Director at Facebook AI Research (FAIR). Before joining FAIR in 2016, he was with Microsoft Research Asia from 2011 to 2016. He received his PhD degree from the Chinese University of Hong Kong in 2011, and his B.S. degree from Tsinghua University in 2007. His research areas include deep learning and computer vision. He is best-known for his work on Deep Residual Networks (ResNets), which have made significant impact on computer vision and broader artificial intelligence. He received several outstanding paper awards at top-tier conferences, including CVPR, ICCV, and ECCV. He received the PAMI Young Researcher Award in 2018. His publications have over 400,000 citations. 


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.
 

Socially Responsible and Factual Reasoning for Equitable AI Systems

Date and Time
Thursday, April 20, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Olga Troyanskya

Saadia Gabriel
Understanding the implications underlying a text is critical to assessing its impact. This requires endowing artificial intelligence (AI) systems with pragmatic reasoning, for example to infer that the statement “Epidemics and cases of disease in the 21st century are “staged”” relates to unfounded conspiracy theories. In this talk, I discuss how shortcomings in the ability of current AI systems to reason about pragmatics leads to inequitable detection of false or harmful language. I demonstrate how these shortcomings can be addressed by imposing human-interpretable structure on deep learning architectures using insights from linguistics.

In the first part of the talk, I describe how adversarial text generation algorithms can be used to improve model robustness. I then introduce a pragmatic formalism for reasoning about harmful implications conveyed by social media text. I show how this pragmatic approach can be combined with generative neural language models to uncover implications of news headlines. I also address the bottleneck to progress in text generation posed by gaps in evaluation of factuality. I conclude with an interdisciplinary study showing how content moderation informed by pragmatics can be used to ensure safe interactions with conversational agents, and my future vision for development of context-aware systems.

Bio: Saadia Gabriel is a PhD candidate in the Paul G. Allen School of Computer Science & Engineering at the University of Washington, advised by Prof. Yejin Choi and Prof. Franziska Roesner. Her research revolves around natural language processing and machine learning, with a particular focus on building systems for understanding how social commonsense manifests in text (i.e. how do people typically behave in social scenarios), as well as mitigating spread of false or harmful text (e.g. Covid-19 misinformation). Her work has been covered by a wide range of media outlets like Forbes and TechCrunch. It has also received a 2019 ACL best short paper nomination, a 2019 IROS RoboCup best paper nomination and won a best paper award at the 2020 WeCNLP summit. Prior to her PhD, Saadia received a BA summa cum laude from Mount Holyoke College in Computer Science and Mathematics.


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.
 

Enabling Self-sufficient Robot Learning

Date and Time
Tuesday, April 4, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Szymon Rusinkiewicz

Rika Antonova
Autonomous exploration and data-efficient learning are important ingredients for helping machine learning handle the complexity and variety of real-world interactions. In this talk, I will describe methods that provide these ingredients and serve as building blocks for enabling self-sufficient robot learning.

First, I will outline a family of methods that facilitate active global exploration. Specifically, they enable ultra data-efficient Bayesian optimization in reality by leveraging experience from simulation to shape the space of decisions. In robotics, these methods enable success with a budget of only 10-20 real robot trials for a range of tasks: bipedal and hexapod walking, task-oriented grasping, and nonprehensile manipulation.

Next, I will describe how to bring simulations closer to reality. This is especially important for scenarios with highly deformable objects, where simulation parameters influence the dynamics in unintuitive ways. The success here hinges on finding a good representation for the state of deformables. I will describe adaptive distribution embeddings that provide an effective way to incorporate noisy state observations into modern Bayesian tools for simulation parameter inference. This novel representation ensures success in estimating posterior distributions over simulation parameters, such as elasticity, friction, and scale, even for scenarios with highly deformable objects and using only a small set of real-world trajectories.

Lastly, I will share a vision of using distribution embeddings to make the space of stochastic policies in reinforcement learning suitable for global optimization. This research direction involves formalizing and learning novel distance metrics on this space and will support principled ways of seeking diverse behaviors. This can unlock truly autonomous learning, where learning agents have incentives to explore, build useful internal representations and discover a variety of effective ways of interacting with the world.

Bio: Rika is a postdoctoral scholar at Stanford University and a recipient of the NSF/CRA Computing Innovation Fellowship. Rika completed her Ph.D. work on data-efficient simulation-to-reality transfer at KTH. Earlier, she obtained a research Master's degree from the Robotics Institute at Carnegie Mellon University. Before that, Rika was a software engineer at Google, first in the Search Personalization group, then in the Character Recognition team (developing open-source OCR engine Tesseract).


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.

Reinforcement Learning from Static Datasets: Algorithms, Analysis and Applications

Date and Time
Tuesday, March 28, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Jia Deng

Aviral Kumar
Typically, reinforcement learning (RL) methods rely on trial-and-error interaction with the environment from scratch to discover effective behaviors. While this sort of paradigm has the potential to discover good strategies, this paradigm also inhibits RL methods from collecting enough experience or training data in real-world problems where active interaction is expensive (e.g., in drug design) or dangerous (e.g., for robots operating around humans). My work develops approaches to alleviate this limitation: how can we learn policies to effectively make decisions entirely from previously-collected, static datasets in an offline manner? In this talk, I will discuss challenges that appear in this kind of offline reinforcement learning (offline RL) and develop algorithms and techniques to address these challenges. I will then discuss how my approaches for offline RL and decision-making have enabled us to make progress in real-world problems such as hardware accelerator design, robotic manipulation, and computational chemistry. Finally, I will discuss how we can enable offline RL methods to benefit from generalization capabilities offered by large and expressive models, similar to supervised learning.

Bio: Aviral Kumar is a final year Ph.D. student at UC Berkeley. His research focuses on developing effective and reliable approaches for (sequential) decision-making. Towards this goal, he focuses on designing reinforcement learning techniques to static datasets and on understanding and applying these methods in practice. Before his Ph.D., Aviral obtained his B.Tech. in Computer Science from IIT Bombay in India. He is a recipient of the C.V. & Daulat Ramamoorthy Distinguished Research Award, given to 1 PhD student in EECS at Berkeley for outstanding contributions to a new area of research in computer science, Facebook Ph.D. Fellowship in Machine Learning and Apple Scholars in AI/ML Ph.D. Fellowship. 


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.

Responsible Machine Learning through the Lens of Causal Inference

Date and Time
Tuesday, April 11, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Aleksandra Korolova

Amanda Coston
Machine learning algorithms are widely used for decision-making in societally high-stakes settings from child welfare and criminal justice to healthcare and consumer lending. Recent history has illuminated numerous examples where these algorithms proved unreliable or inequitable. In this talk I show how causal inference enables us to more reliably evaluate such algorithms’ performance and equity implications. 

In the first part of the talk, I demonstrate that standard evaluation procedures fail to address missing data and as a result, often produce invalid assessments of algorithmic performance. I propose a new evaluation framework that addresses missing data by using counterfactual techniques to estimate unknown outcomes. Using this framework, I propose counterfactual analogues of common predictive performance and algorithmic fairness metrics that are tailored to  decision-making settings. I provide double machine learning-style estimators for these metrics that achieve fast rates & asymptotic normality under flexible nonparametric conditions. I present empirical results in the child welfare setting using data from Allegheny County’s Department of Human Services.

In the second half of the talk, I propose novel causal inference methods to audit for bias in key decision points in contexts where machine learning algorithms are used. A common challenge is that data about decisions are often observed under outcome-dependent sampling. I develop a counterfactual audit for biased decision-making in settings with outcome-dependent data.  Using data from the Stanford Open Policing Project, I demonstrate how this method can identify racial bias in the most common entry point to the criminal justice system: police traffic stops. To conclude, I situate my work in the broader question of governance in responsible machine learning. 

Bio:  Amanda Coston is a PhD student in Machine Learning and Public Policy at Carnegie Mellon University. Her research investigates how to make algorithmic decision-making more reliable and more equitable using causal inference and machine learning. Prior to her PhD, she worked at Microsoft, the consultancy Teneo, and the Nairobi-based startup HiviSasa. She earned a B.S.E from Princeton in computer science with a certificate in public policy.  Amanda is a Meta Research PhD Fellow,  K & L Gates Presidential Fellow in Ethics and Computational Technologies, and NSF GRFP Fellow, and has received several Rising Star honors.


This seminar is cosponsored by the Center for Information Technology Policy and the department of Computer Science.

To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.

Foundation Models for Robust Machine Learning

Date and Time
Tuesday, April 18, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Tom Griffiths

Ananya Kumar
Machine learning systems are not robust—they suffer large drops in accuracy when deployed in different environments from what they were trained on. In this talk, I show that the foundation model paradigm—adapting models that are pretrained on broad unlabeled data—is a principled solution that leads to state-of-the-art robustness. I will focus on the key ingredients: how we should pretrain and adapt models for robustness. (1) First, I show that contrastive pretraining on unlabeled data learns transferable representations that improves accuracy even on domains where we had no labels. We explain why pretraining works in a very different way from some classical intuitions of collapsing representations (domain invariance). Our theory predicts phenomena on real datasets, and leads to improved pretraining methods. (1) Next, I will show that the standard approach of adaptation (updating all the model's parameters) can distort pretrained representations and perform poorly out-of-distribution. Our theoretical analysis leads to better methods for adaptation and state-of-the-art accuracies on ImageNet and in applications such as satellite remote sensing, wildlife conservation, and radiology.

Bio: Ananya Kumar is a Ph.D. candidate in the Department of Computer Science at Stanford University, advised by Percy Liang and Tengyu Ma. His work focuses on representation learning, foundation models, and reliable machine learning. His papers have been recognized with several Spotlight and Oral presentations at NeurIPS, ICML, and ICLR, and his research is supported by a Stanford Graduate Fellowship.


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.
 

Towards Efficient and Reliable Machine Learning for Natural Language Processing (and Beyond)

Date and Time
Monday, March 27, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Karthik Narasimhan

Adam Fisch
In this talk, I will introduce work on fundamental techniques for building and deploying effective natural language processing (NLP) systems that are also efficient and reliable. Specifically, I will address three interconnected challenges for modern machine learning in NLP: how to quickly adapt foundation models to new tasks with limited data, how to dynamically reconfigure large architectures for more efficient computation, and how to develop powerful theoretical tools for rigorous, yet practical, uncertainty quantification. To conclude, I will highlight a number of my future research directions, as well as extensions to interesting applications beyond natural language.

Bio: Adam Fisch is a PhD candidate at MIT working with Regina Barzilay and Tommi Jaakkola, and a recipient of an NSF Graduate Research Fellowship. His research centers around principled methods for efficient and reliable machine learning systems that work effectively in realistic scenarios, and has appeared in top-tier venues such as *ACL, ICLR, ICML, and NeurIPS. Adam also served as a co-instructor for the tutorial on Uncertainty Estimation for NLP at COLING 2022, and as a co-organizer of the Machine Reading for Question Answering workshops at EMNLP 2019 and 2021. Prior to MIT, Adam was a research engineer at Meta (Facebook) AI Research for two years, and studied mechanical engineering as an undergraduate at Princeton University.


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.

Collaborative, Communal, & Continual Machine Learning

Date and Time
Monday, March 20, 2023 - 12:30pm to 1:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Danqi Chen

Colin Raffel
Pre-trained models have become a cornerstone of machine learning thanks to the fact that they can provide improved performance with less labeled data on downstream tasks. However, these models are typically created by resource-rich research groups that unilaterally decide how a given model should be built, trained, and released, after which point it is never updated. In contrast, open-source development has demonstrated that it is possible for a community of contributors to work together to iteratively build complex and widely used software. This kind of large-scale distributed collaboration is made possible through a mature set of tools including version control and package management. In this talk, I will discuss a research focus in my group that aims to make it possible to build machine learning models in the way that open-source software is developed. Specifically, I will discuss our preliminary work on merging multiple models while retaining their individual capabilities, patching models with cheaply-communicable updates, designing modular model architectures, and tracking changes through a version control system for model parameters. I will conclude with an outlook on how the field will change once truly collaborative, communal, and continual machine learning is possible.

Bio: Colin Raffel is an Assistant Professor at UNC Chapel Hill and a Faculty Researcher at Hugging Face. His work aims to make it easy to get computers to do new things. Consequently, he works mainly on machine learning (enabling computers to learn from examples) and natural language processing (enabling computers to communicate in natural language). He received his Ph.D. from Columbia University in 2016 and spent five years as a research scientist at Google Brain.


To request accommodations for a disability please contact Emily Lawrence, emilyl@cs.princeton.edu, at least one week prior to the event.

Follow us: Facebook Twitter Linkedin