Online Learning and Solving Infinite Games with an ERM Oracle

Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell K. Fishelson
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:274-324, 2023.

Abstract

While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on computationally inefficient oracles such as the Standard Optimal Algorithm (SOA). In this work, we propose an algorithm for online binary classification setting that relies solely on ERM oracle calls, and show that it has finite regret in the realizable setting and sublinearly growing regret in the agnostic setting. We bound the regret in terms of the Littlestone and threshold dimensions of the underlying concept class.We obtain similar results for nonparametric games, where the ERM oracle can be interpreted as a best response oracle, finding the best response of a player to a given history of play of the other players. In this setting, we provide learning algorithms that only rely on best response oracles and converge to approximate-minimax equilibria in two-player zero-sum games and approximate coarse correlated equilibria in multi-player general-sum games, as long as the game has bounded fat-threshold dimension. Our algorithms apply to both binary-valued and real-valued games and can be viewed as providing justification for the wide use of double oracle and multiple oracle algorithms in the practice of solving large games.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-assos23a, title = {Online Learning and Solving Infinite Games with an ERM Oracle}, author = {Assos, Angelos and Attias, Idan and Dagan, Yuval and Daskalakis, Constantinos and Fishelson, Maxwell K.}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {274--324}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/assos23a/assos23a.pdf}, url = {https://proceedings.mlr.press/v195/assos23a.html}, abstract = {While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on computationally inefficient oracles such as the Standard Optimal Algorithm (SOA). In this work, we propose an algorithm for online binary classification setting that relies solely on ERM oracle calls, and show that it has finite regret in the realizable setting and sublinearly growing regret in the agnostic setting. We bound the regret in terms of the Littlestone and threshold dimensions of the underlying concept class.We obtain similar results for nonparametric games, where the ERM oracle can be interpreted as a best response oracle, finding the best response of a player to a given history of play of the other players. In this setting, we provide learning algorithms that only rely on best response oracles and converge to approximate-minimax equilibria in two-player zero-sum games and approximate coarse correlated equilibria in multi-player general-sum games, as long as the game has bounded fat-threshold dimension. Our algorithms apply to both binary-valued and real-valued games and can be viewed as providing justification for the wide use of double oracle and multiple oracle algorithms in the practice of solving large games.} }
Endnote
%0 Conference Paper %T Online Learning and Solving Infinite Games with an ERM Oracle %A Angelos Assos %A Idan Attias %A Yuval Dagan %A Constantinos Daskalakis %A Maxwell K. Fishelson %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-assos23a %I PMLR %P 274--324 %U https://proceedings.mlr.press/v195/assos23a.html %V 195 %X While ERM suffices to attain near-optimal generalization error in the stochastic learning setting, this is not known to be the case in the online learning setting, where algorithms for general concept classes rely on computationally inefficient oracles such as the Standard Optimal Algorithm (SOA). In this work, we propose an algorithm for online binary classification setting that relies solely on ERM oracle calls, and show that it has finite regret in the realizable setting and sublinearly growing regret in the agnostic setting. We bound the regret in terms of the Littlestone and threshold dimensions of the underlying concept class.We obtain similar results for nonparametric games, where the ERM oracle can be interpreted as a best response oracle, finding the best response of a player to a given history of play of the other players. In this setting, we provide learning algorithms that only rely on best response oracles and converge to approximate-minimax equilibria in two-player zero-sum games and approximate coarse correlated equilibria in multi-player general-sum games, as long as the game has bounded fat-threshold dimension. Our algorithms apply to both binary-valued and real-valued games and can be viewed as providing justification for the wide use of double oracle and multiple oracle algorithms in the practice of solving large games.
APA
Assos, A., Attias, I., Dagan, Y., Daskalakis, C. & Fishelson, M.K.. (2023). Online Learning and Solving Infinite Games with an ERM Oracle. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:274-324 Available from https://proceedings.mlr.press/v195/assos23a.html.

Related Material