5 papers · 1 filter
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…