Information-Theoretic Analysis of Minimax Excess Risk
  Two main concepts studied in machine learning theory are generalization gap
(difference between train and test error) and excess risk (difference between
test error and the minimum possible error). While information-theoretic tools
have been used extensively to study the generalization gap of learning
algorithms, the information-theoretic nature of excess risk has not yet been
fully investigated. In this paper, some steps are taken toward this goal. We
consider the frequentist problem of minimax excess risk as a zero-sum game
between algorithm designer and the world. Then, we argue that it is desirable
to modify this game in a way that the order of play can be swapped. We prove
that, under some regularity conditions, if the world and designer can play
randomly the duality gap is zero and the order of play can be changed. In this
case, a Bayesian problem surfaces in the dual representation. This makes it
possible to utilize recent information-theoretic results on minimum excess risk
in Bayesian learning to provide bounds on the minimax excess risk. We
demonstrate the applicability of the results by providing information theoretic
insight on two important classes of problems: classification when the
hypothesis space has finite VC-dimension, and regularized least squares.
