Skip to yearly menu bar Skip to main content


Oral

High-Dimensional Prediction for Sequential Decision Making

Georgy Noarov · Ramya Ramalingam · Aaron Roth · Stephan Xie

West Ballroom D
[ ] [ Visit Oral 4E Algorithms ]
Wed 16 Jul 3:45 p.m. — 4 p.m. PDT

Abstract: We give an efficient algorithm for producing multi-dimensional forecasts in an online adversarial environment that have low bias subject to any polynomial number of conditioning events, that can depend both on external context and on our predictions themselves. We demonstrate the use of this algorithm with several applications. We show how to make predictions that can be transparently consumed by any polynomial number of downstream decision makers with different utility functions, guaranteeing them diminishing swap regret at optimal rates. We also give the first efficient algorithms for guaranteeing diminishing conditional regret in online combinatorial optimization problems for an arbitrary polynomial number of conditioning events --- i.e. on an arbitrary number of intersecting subsequences determined both by context and our own predictions. Finally, we give the first efficient algorithm for online multicalibration with $O(T^{2/3})$ rates in the ECE metric.

Chat is not available.