Forming Relations Between Supervised Learning and Games
Paper: https://papers.nips.cc/paper/6315-deep-learning-games.pdf
Supervised learning can be described as the learning task of making predictions on data with unknown labels by using previous labeled data. This paper, by Dale Schuurmans and Martin Zinkevich at Google, is able to form a reduction of supervised learning to game playing. At first, they look at simple convex one-layer problems. They are able to identify a basic game, whose Nash equilibria corresponds to global minima of the one-layer learning problem. The game identified is between a protagonist and an antagonist who choose their actions without knowledge of the other’s choice. This allows one to take any convex one-layer supervised learning problem, convert it into the corresponding game, solve that game’s Nash equilibria, which produces the global minimum of the learning problem. Additionally, one can perform the reverse, take a game of the aforementioned structure and solve its Nash equilibria by optimizing the corresponding learning problem. This reduction also produces new insight on ways to optimize supervised learning problems. One of these new methods, Regret Matching, shows promising results in the experiments.
However, convex one-layer problems are one of the simplest forms of supervised learning, so the authors then look at Deep Learning with differentiable convex gates, a more complex and interesting problem. It turns out that the they are also able to identify a reduction to a Deep Learning Game. Thus as before, they can optimize the learning problem to create a Nash Equilibria for the reduced game. It turns out that this is quite powerful because massive-scale games, which are quite difficult to solve, can be represented and solved by deep networks. In addition, new optimizers derived from the game representation are introduced for Deep Learning, and show promising results. All these definitions, theorems and results are discussed in much more detail in the paper. Overall, this paper shows great promise on combining methods and knowledge from Game Theory and Machine Learning.