  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 a 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.
