2 citations · 2 across the 13 of their papers we have counts for
14 papers
Improved Multi-Dimensional Forecasting for Swap Regret
Joey Rivkin, Ramiro N. Deo-Campo Vuong, Robert Kleinberg +3
We study the problem of forecasting for an arbitrary number of downstream agents with unknown objectives, each of whom best responds to the forecaster's predictions. We seek a sing…
Price of Anarchy of Algorithmic Monoculture
Robert Kleinberg, Erald Sinanaj, Éva Tardos
Several recent works investigate the effects of monoculture, the ever increasing phenomenon of (possibly) self-interested actors in a society relying on one common source of advice…
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…
Universal Connection Schedules for Reconfigurable Networking
Shaleen Baral, Robert Kleinberg, Sylvan Martin +3
Reconfigurable networks are a novel communication paradigm in which the pattern of connectivity between hosts varies rapidly over time. Prior theoretical work explored the inherent…
The Keychain Problem: On Minimizing the Opportunity Cost of Uncertainty
Ramiro N. Deo-Campo Vuong, Robert Kleinberg, Aditya Prasad +2
In this paper, we introduce a family of sequential decision-making problems, collectively termed the Keychain Problem, that involve exploring a set of actions to maximize expected…
Improving Pinwheel Density Bounds for Small Minimums
Ahan Mishra, Parker Rho, Robert Kleinberg
The density bound for schedulability for general pinwheel instances is , but density bounds better than can be shown for cases in which the minimum eleme…
Efficient AllReduce with Stragglers
Arjun Devraj, Eric Ding, Abhishek Vijaya Kumar +2
Distributed machine learning workloads use data and tensor parallelism for training and inference, both of which rely on the AllReduce collective to synchronize gradients or activa…
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…
Learning in Budgeted Auctions with Spacing Objectives
Giannis Fikioris, Robert Kleinberg, Yoav Kolumbus +3
In many repeated auction settings, participants care not only about how frequently they win but also how their winnings are distributed over time. This problem arises in various pr…
Online Matroid Embeddings
Andrés Cristi, Paul Dütting, Robert Kleinberg +2
We introduce the notion of an online matroid embedding, which is an algorithm for mapping an unknown matroid that is revealed in an online fashion to a larger-but-known matroid. We…
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…
Load is not what you should balance: Introducing Prequal
Bartek Wydrowski, Robert Kleinberg, Stephen M. Rumble +1
We present Prequal (Probing to Reduce Queuing and Latency), a load balancer for distributed multi-tenant systems. Prequal aims to minimize real-time request latency in the presence…
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…