1.4k citations · 2.5k across the 47 of their papers we have counts for
24 papers · 1 filter
Loss Minimization Yields Multicalibration for Large Neural Networks
Jarosław Błasiok, Parikshit Gopalan, Lunjia Hu +2
Multicalibration is a notion of fairness for predictors that requires them to provide calibrated predictions across a large set of protected groups. Multicalibration is known to be…
Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms
Surbhi Goel, Sham Kakade, Adam Tauman Kalai +1
Neural networks (NNs) struggle to efficiently solve certain problems, such as learning parities, even when there are simple learning algorithms for those problems. Can NNs discover…
Partial Matrix Completion
Elad Hazan, Adam Tauman Kalai, Varun Kanade +2
The matrix completion problem aims to reconstruct a low-rank matrix based on a revealed set of possibly noisy entries. Prior works consider completing the entire matrix with genera…
Language Models Can Teach Themselves to Program Better
Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai
Recent Language Models (LMs) achieve breakthrough performance in code generation when trained on human-authored problems, even solving some competitive-programming problems. Self-p…
Why GANs are overkill for NLP
David Alvarez-Melis, Vikas Garg, Adam Tauman Kalai
This work offers a novel theoretical perspective on why, despite numerous attempts, adversarial approaches to generative modeling (e.g., GANs) have not been as popular for certain…
Omnipredictors
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold +2
Loss minimization is a dominant paradigm in machine learning, where a predictor is trained to minimize some loss function that depends on an uncertain event (e.g., "will it rain to…
Social Norm Bias: Residual Harms of Fairness-Aware Algorithms
Myra Cheng, Maria De-Arteaga, Lester Mackey +1
Many modern machine learning algorithms mitigate bias by enforcing fairness constraints across coarsely-defined groups related to a sensitive attribute like gender or race. However…
Programming Puzzles
Tal Schuster, Ashwin Kalyan, Oleksandr Polozov +1
We introduce a new type of programming challenge called programming puzzles, as an objective and comprehensive evaluation of program synthesis, and release an open-source dataset o…
Towards optimally abstaining from prediction with OOD test examples
Adam Tauman Kalai, Varun Kanade
A common challenge across all areas of machine learning is that training data is not distributed like test data, due to natural shifts, "blind spots," or adversarial examples; such…
Efficient Learning with Arbitrary Covariate Shift
Adam Kalai, Varun Kanade
We give an efficient algorithm for learning a binary function in a given class C of bounded VC dimension, with training data distributed according to P and test data according to Q…
Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples
Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai +1
We present a transductive learning algorithm that takes as input training examples from a distribution and arbitrary (unlabeled) test examples, possibly chosen by an adversary.…
Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization
Vikas K. Garg, Adam Kalai, Katrina Ligett +1
Domain generalization is the problem of machine learning when the training data and the test data come from different data domains. We present a simple theoretical model of learnin…
Learning to Prune: Speeding up Repeated Computations
Daniel Alabi, Adam Tauman Kalai, Katrina Ligett +3
It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each inst…
What's in a Name? Reducing Bias in Bios without Access to Protected Attributes
Alexey Romanov, Maria De-Arteaga, Hanna Wallach +7
There is a growing body of work that proposes methods for mitigating bias in machine learning systems. These methods typically rely on access to protected attributes such as race,…
Unleashing Linear Optimizers for Group-Fair Learning and Optimization
Daniel Alabi, Nicole Immorlica, Adam Tauman Kalai
Most systems and learning algorithms optimize average performance or average loss -- one reason being computational complexity. However, many objectives of practical interest are m…
Actively Avoiding Nonsense in Generative Models
Steve Hanneke, Adam Kalai, Gautam Kamath +1
A generative model may generate utter nonsense when it is fit to maximize the likelihood of observed data. This happens due to "model error," i.e., when the true data generating di…
Glass-Box Program Synthesis: A Machine Learning Approach
Konstantina Christakopoulou, Adam Tauman Kalai
Recently proposed models which learn to write computer programs from data use either input/output examples or rich execution traces. Instead, we argue that a novel alternative is t…
Decoupled classifiers for fair and efficient machine learning
Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai +1
When it is ethical and legal to use a sensitive attribute (such as gender or race) in machine learning systems, the question remains how to do so. We show that the naive applicatio…
Meta-Unsupervised-Learning: A supervised approach to unsupervised learning
Vikas K. Garg, Adam Tauman Kalai
We introduce a new paradigm to investigate unsupervised learning, reducing unsupervised learning to supervised learning. Specifically, we mitigate the subjectivity in unsupervised…
Feature Multi-Selection among Subjective Features
Sivan Sabato, Adam Kalai
When dealing with subjective, noisy, or otherwise nebulous features, the "wisdom of crowds" suggests that one may benefit from multiple judgments of the same feature on the same ob…
Adaptively Learning the Crowd Kernel
Omer Tamuz, Ce Liu, Serge Belongie +2
We introduce an algorithm that, given n objects, learns a similarity matrix over all n^2 pairs, from crowdsourced data alone. The algorithm samples responses to adaptively chosen t…
Decision trees are PAC-learnable from most product distributions: a smoothed analysis
Adam Tauman Kalai, Shang-Hua Teng
We consider the problem of PAC-learning decision trees, i.e., learning a decision tree over the n-dimensional hypercube from independent random labeled examples. Despite significan…
Online convex optimization in the bandit setting: gradient descent without a gradient
Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan
We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a sign…
Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
Avrim Blum, Adam Kalai, Hal Wasserman
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise. This results in a polynomial-time algorithm for…