research
∙
09/21/2023
Smooth Nash Equilibria: Algorithms and Complexity
A fundamental shortcoming of the concept of Nash equilibrium is its comp...
share
research
∙
07/22/2023
The Sample Complexity of Multi-Distribution Learning for VC Classes
Multi-distribution learning is a natural generalization of PAC learning ...
research
∙
07/05/2023
Jailbroken: How Does LLM Safety Training Fail?
Large language models trained for safety and harmlessness remain suscept...
research
∙
06/26/2023
Improved Bayes Risk Can Yield Reduced Social Welfare Under Competition
As the scale of machine learning models increases, trends such as scalin...
research
∙
06/05/2023
Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents
In this paper, we introduce a generalization of the standard Stackelberg...
research
∙
03/08/2023
Smoothed Analysis of Sequential Probability Assignment
We initiate the study of smoothed analysis for the sequential probabilit...
research
∙
02/21/2023
A Unifying Perspective on Multi-Calibration: Unleashing Game Dynamics for Multi-Objective Learning
We provide a unifying framework for the design and analysis of multi-cal...
research
∙
02/20/2023
Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty
In online marketplaces, customers have access to hundreds of reviews for...
research
∙
02/06/2023
Stochastic Minimum Vertex Cover in General Graphs: a 3/2-Approximation
Our main result is designing an algorithm that returns a vertex cover of...
research
∙
10/22/2022
On-Demand Sampling: Learning Optimally from Multiple Distributions
Social and real-world considerations such as robustness, fairness, socia...
research
∙
08/30/2022
Competition, Alignment, and Equilibria in Digital Marketplaces
Competition between traditional platforms is known to improve user utili...
research
∙
08/19/2022
Learning in Stackelberg Games with Non-myopic Agents
We study Stackelberg games where a principal repeatedly interacts with a...
research
∙
05/26/2022
Communicating with Anecdotes
We study a communication game between a sender and receiver where the se...
research
∙
02/17/2022
Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
In this paper, we study oracle-efficient algorithms for beyond worst-cas...
research
∙
03/04/2021
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning
In recent years, federated learning has been embraced as an approach for...
research
∙
02/16/2021
Smoothed Analysis with Adaptive Adversaries
We prove novel algorithmic guarantees for several online problems in the...
research
∙
11/03/2020
Maximizing Welfare with Incentive-Aware Evaluation Mechanisms
Motivated by applications such as college admission and insurance rate d...
research
∙
10/10/2020
Noise in Classification
This chapter considers the computational and statistical aspects of lear...
research
∙
06/17/2020
Smoothed Analysis of Online and Differentially Private Learning
Practical and pervasive needs for robustness and privacy in algorithms h...
research
∙
10/04/2019
The Disparate Equilibria of Algorithmic Decision Making when Individuals Invest Rationally
The long-term impact of algorithmic decision making is shaped by the dyn...
research
∙
06/06/2019
Toward a Characterization of Loss Functions for Distribution Learning
In this work we study loss functions for learning and evaluating probabi...
research
∙
10/11/2017
The Provable Virtue of Laziness in Motion Planning
The Lazy Shortest Path (LazySP) class consists of motion-planning algori...
research
∙
03/14/2017
Weighted Voting Via No-Regret Learning
Voting systems typically treat all voters equally. We argue that perhaps...
research
∙
11/04/2016