High-Dimensional Prediction for Sequential Decision Making

Georgy Noarov, Ramya Ramalingam, Aaron Roth, Stephan Xie
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:46762-46783, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-noarov25b, title = {High-Dimensional Prediction for Sequential Decision Making}, author = {Noarov, Georgy and Ramalingam, Ramya and Roth, Aaron and Xie, Stephan}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {46762--46783}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/noarov25b/noarov25b.pdf}, url = {https://proceedings.mlr.press/v267/noarov25b.html}, 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.} }
Endnote
%0 Conference Paper %T High-Dimensional Prediction for Sequential Decision Making %A Georgy Noarov %A Ramya Ramalingam %A Aaron Roth %A Stephan Xie %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-noarov25b %I PMLR %P 46762--46783 %U https://proceedings.mlr.press/v267/noarov25b.html %V 267 %X 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.
APA
Noarov, G., Ramalingam, R., Roth, A. & Xie, S.. (2025). High-Dimensional Prediction for Sequential Decision Making. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:46762-46783 Available from https://proceedings.mlr.press/v267/noarov25b.html.

Related Material