Timezone: »
We consider a number of classical and new computational problems regarding marginal distributions, and inference in models specifying a full joint distribution. We prove general and efficient reductions between a number of these problems, which demonstrate that algorithmic progress in inference automatically yields progress for “pure data” problems. Our main technique involves formulating the problems as linear programs, and proving that the dual separation oracle for the Ellipsoid Method is provided by the target problem. This technique may be of independent interest in probabilistic inference.
Author Information
Tim Roughgarden (Stanford University)
Michael Kearns (University of Pennsylvania)
Michael Kearns is Professor and National Center Chair in the Computer and Information Science department at the University of Pennsylvania. His research interests include topics in machine learning, algorithmic game theory, social networks, and computational finance. Prior to joining the Penn faculty, he spent a decade at AT&T/Bell Labs, where he was head of AI Research. He is co-director of Penn’s Warren Center for Network and Data Sciences (warrencenter.upenn.edu), and founder of Penn’s Networked and Social Systems Engineering (NETS) undergraduate program (www.nets.upenn.edu). Kearns consults extensively in technology and finance, and is a Fellow of the Association for the Advancement of Artificial Intelligence and the American Academy of Arts and Sciences.
More from the Same Authors
-
2022 : Differentially Private Gradient Boosting on Linear Learners for Tabular Data »
Saeyoung Rho · Shuai Tang · Sergul Aydore · Michael Kearns · Aaron Roth · Yu-Xiang Wang · Steven Wu · Cedric Archambeau -
2023 Poster: Replicable Reinforcement Learning »
Eric Eaton · Marcel Hussing · Michael Kearns · Jessica Sorrell -
2023 Poster: Scalable Membership Inference Attacks via Quantile Regression »
Martin Bertran · Shuai Tang · Aaron Roth · Michael Kearns · Jamie Morgenstern · Steven Wu -
2022 Poster: Private Synthetic Data for Multitask Learning and Marginal Queries »
Giuseppe Vietri · Cedric Archambeau · Sergul Aydore · William Brown · Michael Kearns · Aaron Roth · Ankit Siva · Shuai Tang · Steven Wu -
2020 : Invited Talk 7:Fair Portfolio Design »
Michael Kearns -
2020 : Keynote: Michael Kearns »
Michael Kearns -
2019 Poster: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2019 Oral: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2018 : Invited Talk 3: Fairness in Allocation Problems »
Michael Kearns -
2018 Poster: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2018 Oral: Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization »
Rad Niazadeh · Tim Roughgarden · Joshua Wang -
2018 Poster: Online Learning with an Unknown Fairness Metric »
Stephen Gillen · Christopher Jung · Michael Kearns · Aaron Roth -
2017 Workshop: Learning in the Presence of Strategic Behavior »
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan -
2017 Poster: Online Prediction with Selfish Experts »
Tim Roughgarden · Okke Schrijvers -
2016 Poster: Fairness in Learning: Classic and Contextual Bandits »
Matthew Joseph · Michael Kearns · Jamie Morgenstern · Aaron Roth -
2015 Poster: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2015 Spotlight: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2014 Invited Talk: Games, Networks, and People »
Michael Kearns -
2007 Spotlight: Privacy-Preserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan -
2007 Poster: Privacy-Preserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan -
2006 Poster: Learning from Multiple Sources »
Yacov Crammer · Michael Kearns · Jennifer Wortman Vaughan -
2006 Poster: A Small World Threshold for Economic Network Formation »
Eyal Even-Dar · Michael Kearns