Description:

Wednesday / CS Seminar
January 22nd / 12:00 PM
Hybrid / Mudd 3514

Speaker
Ankit Garg, Microsoft Research India

Talk Title
Arithmetic circuits: lower bounds, learning and applications

Abstract
Arithmetic circuits are a natural model for computing polynomials via the basic operations of addition and multiplication. One of the fundamental open problems in this area is of proving lower bounds, i.e. finding an explicit polynomial that cannot be computed by polynomial sized arithmetic circuits (aka the VP vs VNP problem). While the question of proving lower bounds for general arithmetic circuits is still open, there has been remarkable progress in proving lower bounds for restricted classes of arithmetic circuits. Another important problem in this area is that of learning arithmetic circuits: given a polynomial (via query or black box access), output a small arithmetic circuit computing it (if one exists). This problem is hard in the worst case. I will present a meta framework for learning arithmetic circuits in the non-degenerate case using lower bound methods. We instantiate and implement this meta framework for various classes of arithmetic circuits. Then I will talk about extending the algorithms to the noisy setting as well as surprising and remarkable applications to classical problems in machine learning such as subspace clustering and mixtures of Gaussians. This is based on joint works with Pritam Chandra, Neeraj Kayal, Kunal Mittal, Chandan Saha and Tanmay Sinha.

Biography
Ankit Garg is a Senior Researcher at Microsoft Research India since July 2018. Prior to this, he was a Postdoctoral Researcher at Microsoft Research New England from 2016 - 2018. He completed his PhD in 2016 from Princeton University under the supervision of Prof Mark Braverman. His research has spanned several areas of theoretical computer science such as communication complexity, arithmetic complexity, optimization, mixture models and optimization. Several of his research papers have been published in top conferences in computer science such as STOC, FOCS, CCC, NeuRIPS and QIP, and recognized by Simons award for graduate students in theoretical computer science and a Siebel scholarship.

Research/Interest Areas
Theoretical Computer Science, Algorithms, Computational Complexity Theory

---
Zoom: https://northwestern.zoom.us/j/92525649422?pwd=N6DlLBx6RRAtrar8vk27te6cjmzqXP.1
Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=4d9fd60c-89e5-48f6-bbdb-b261015638de
DEI Minute: tinyurl.com/cspac-dei-minute

Description:

Friday / CS Seminar
January 24th / 12:00 PM
Hybrid / Mudd 3514

Speaker
Meena Jagadeesan, UC Berkeley

Talk Title
Steering Machine Learning Ecosystems of Interacting Agents

Abstract

"Modern machine learning models—such as LLMs and recommender systems—interact with humans, companies, and other models in a broader ecosystem. However, these multi-agent interactions often induce unintended ecosystem-level outcomes such as clickbait in classical content recommendation ecosystems, and more recently, safety violations and market concentration in nascent LLM ecosystems. 

In this talk, I discuss my research on characterizing and steering ecosystem-level outcomes. I take an economic and statistical perspective on ML ecosystems, tracing outcomes back to the incentives of interacting agents and to the ML pipeline for training models. First, in LLM ecosystems, we show how analyzing a single model in isolation fails to capture ecosystem-level performance trends: for example, training a model with more resources can counterintuitively hurt ecosystem-level performance. To help steer ecosystem-level outcomes, we develop technical tools to assess how proposed policy interventions affect market entry, safety compliance, and user welfare. Then, turning to content recommendation ecosystems, we characterize a feedback loop between the recommender system and content creators, which shapes the diversity and quality of the content supply. Finally, I present a broader vision of ML ecosystems where multi-agent interactions are steered towards the desired algorithmic, market, and societal outcomes."

Biography
Meena Jagadeesan is a 5th year PhD student in Computer Science at UC Berkeley, where she is advised by Michael I. Jordan and Jacob Steinhardt. Her research investigates multi-agent interactions in machine learning ecosystems from an economic and statistical perspective. She has received an Open Philanthropy AI Fellowship and a Paul and Daisy Soros Fellowship.

Research/Interest Areas
Artificial Intelligence, Machine Learning, Economics and Computation
---
Zoom: https://northwestern.zoom.us/j/92665903240?pwd=YGOjSzB0Pxk4oDvRsVBbA0auFIvH0p.1
Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=408ccd84-8bf4-409a-b995-b261015654c8
DEI Minute: tinyurl.com/cspac-dei-minute

Description:

Monday / CS Seminar
January 13th / 12:00 PM
Hybrid / Mudd 3514

Speaker
TBA

Talk Title
TBA

Abstract
TBA

Biography
TBA

Research/Interest Areas
TBA
---
Zoom: TBA
Panopto: TBA
DEI Minute: tinyurl.com/cspac-dei-minute

Description:

Friday / CS Seminar
January 31st / 12:00 PM
Hybrid / Mudd 3514

Speaker
Daniel Halpern, Harvard University

Talk Title
Why AI Needs Social Choice

Abstract
In many modern AI paradigms, we encounter tasks reminiscent of social choice theory: collecting preferences from individuals and aggregating them into a single joint outcome. However, these tasks differ from traditional frameworks in two key ways: the space of possible outcomes is so enormous that we can only hope to collect sparse inputs from each participant, and the outcomes themselves are often highly complex. This talk explores these challenges through two case studies: Polis, a platform for democratic deliberation (https://arxiv.org/abs/2211.15608), and Reinforcement Learning From Human Feedback (RLHF), a method for fine-tuning LLMs to align with societal preferences (https://arxiv.org/pdf/2405.14758). In both cases, the focus is on evaluating existing methods through an axiomatic lens and designing new methods with provable guarantees.

Biography
Daniel Halpern is a final-year PhD student at Harvard University advised by Ariel Procaccia. He is supported by an NSF Graduate Research Fellowship and a Siebel Scholarship. His research broadly sits at the intersection of algorithms, economics, and artificial intelligence. Specifically, he considers novel settings where groups of people need to make collective decisions, such as summarizing population views on large-scale opinion aggregation websites, using participant data to fine-tune large language models, and selecting panel members for citizens’ assemblies. In each, he develops practical and provably fair solutions to aggregate individual preferences.

---
Zoom: https://northwestern.zoom.us/j/96824870974?pwd=QfxpsRpfWcDlx4TXPswbAd8X4Dqhyb.1
Panopto: https://northwestern.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=2159520b-1d46-4ece-ba17-b268017475c6
DEI Minute: tinyurl.com/cspac-dei-minute

Description:

Monday / CS Seminar
January 13th / 12:00 PM
Hybrid / Mudd 3514

Speaker
TBA

Talk Title
TBA

Abstract
TBA

Biography
TBA

Research/Interest Areas
TBA
---
Zoom: TBA
Panopto: TBA
DEI Minute: tinyurl.com/cspac-dei-minute