Convex Repeated Games and Fenchel Duality

We describe an algorithmic framework for an abstract game which we term a convex repeated game. We show that various online learning and boosting algorithms can be all derived as special cases of our algorithmic framework. This unified view explains the properties of existing algorithms and also enables us to derive several new interesting algorithms. Our algorithmic framework stems from a connection that we build between the notions of regret in game theory and weak duality in convex optimization. 1 Introduction and Problem Setting Several problems arising in machine learning can be modeled as a convex repeated game. Convex repeated games are closely related to online convex programming (see [19, 9] and the discussion in the last section). A convex repeated game is a two players game that is performed in a sequence of consecutive rounds. On round t of the repeated game, the first player chooses a vector wt from a convex set S . Next, the second player responds with a convex function gt : S R. Finally, the first player suffers an instantaneous loss gt (wt ). We study the game from the viewpoint of the first t player. The goal of the first player is to minimize its cumulative loss, gt (wt ). To motivate this rather abstract setting let us first cast the more familiar setting of online learning as a convex repeated game. Online learning is performed in a sequence of consecutive rounds. On round t, the learner first receives a question, cast as a vector xt , and is required to provide an answer for this question. For example, xt can be an encoding of an email message and the question is whether the email is spam or not. The prediction of the learner is performed based on an hypothesis, ht : X Y , where X is the set of questions and Y is the set of possible answers. In the aforementioned example, Y would be {+1, -1} where +1 stands for a spam email and -1 stands for a benign one. After predicting an answer, the learner receives the correct answer for the question, denot