13 papers
Communication Complexity of Universal Features
Lunjia Hu, Anish Jayant, Peter Li +2
Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we…
Sample-Optimal Multi-Group Learning with an ERM Oracle
Princewill Okoroafor
In multi-group learning, a single predictor must perform nearly as well as the best hypothesis in a class on every group in a rich, possibly infinite and overlapping, collection of…
The Sample Complexity of Multicalibration with an ERM Oracle
Princewill Okoroafor
A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every…
Fast Rates for Swap-Agnostic Learning of Proper Losses
Princewill Okoroafor
Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benc…
Oracle-efficient Hybrid Learning with Constrained Adversaries
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
The Hybrid Online Learning Problem, where features are drawn i.i.d. from an unknown distribution but labels are generated adversarially, is a well-motivated setting positioned betw…
Contextual Dynamic Pricing with Heterogeneous Buyers
Thodoris Lykouris, Sloan Nietert, Princewill Okoroafor +2
We initiate the study of contextual dynamic pricing with a heterogeneous population of buyers, where a seller repeatedly posts prices (over rounds) that depend on the observabl…
Full Swap Regret and Discretized Calibration
Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor +3
We study the problem of minimizing swap regret in structured normal-form games. Players have a very large (potentially infinite) number of pure actions, but each action has an embe…
Near-Optimal Algorithms for Omniprediction
Princewill Okoroafor, Robert Kleinberg, Michael P. Kim
Omnipredictors are simple prediction functions that encode loss-minimizing predictions with respect to a hypothesis class , simultaneously for every loss function within a class…
Breaking the Barrier for Sequential Calibration
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson +3
A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where tha…
Omnipredictors for Regression and the Approximate Rank of Convex Functions
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra +2
Consider the supervised learning setting where the goal is to learn to predict labels given points from a distribution. An \textit{omnipredictor} for a clas…
Faster Recalibration of an Online Predictor via Approachability
Princewill Okoroafor, Robert Kleinberg, Wen Sun
Predictive models in ML need to be trustworthy and reliable, which often at the very least means outputting calibrated probabilities. This can be particularly difficult to guarante…
On the Vulnerability of Fairness Constrained Learning to Malicious Noise
Avrim Blum, Princewill Okoroafor, Aadirupa Saha +1
We consider the vulnerability of fairness-constrained learning to small amounts of malicious noise in the training data. Konstantinov and Lampert (2021) initiated the study of this…
Non-Stochastic CDF Estimation Using Threshold Queries
Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg +1
Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a…