Coin Betting and Parameter-Free Online Learning
In the recent years, a number of parameter-free algorithms have been developed for online linear optimization over Hilbert spaces and for learning with expert advice. These algorithms achieve optimal regret bounds that depend on the unknown competitors, without having to tune the learning rates with oracle choices. We present a new intuitive framework to design parameter-free algorithms for both online linear optimization over Hilbert spaces and for learning with expert advice, based on reductions to betting on outcomes of adversarial coins. We instantiate it using a betting algorithm based on the Krichevsky-Trofimov estimator. The resulting algorithms are simple, with no parameters to be tuned, and they improve or match previous results in terms of regret guarantee and per-round complexity.
Many online learning algorithms are based on a learning parameter which controls how far the algorithm changes its answer after receiving new data. While many of these algorithms fix this rate in advance, others change it as they progress. The main problem discussed in this paper is trying to construct an algorithm that is comparable to the case where we know in advance all the data and not receive it part by part.  In this paper, the authors construct a strategy for a coin betting game such that in each turn the gambler needs to decide how much to bet and on which outcome. This strategy is based on suitably chosen potential functions. Each such family of functions produce a betting strategy which also gives an upper bound on the regret for the game, i.e. how much money the gambler could have won if he knew all the coin tosses in advance compared to how much he won using this strategy.  The authors then use this coin betting strategy to solve other online learning problems such as the Online Learning Optimization and Learning with Expert Advice problems. This strategy seems to generalize other parameter-free algorithms which already exist.
The coin betting game and both the Online learning optimization and Learning with expert advice are interesting problems in online learning, and the choice of the learning rate is fundamental to many learning algorithms. Thus any framework that provides a way to chose this rate in a smart way is highly interesting and can have many applications.  The main issue with the paper is the definition of Coin betting potential which lead to the choice of the learning rate. While the formula below line 137 explains why the condition in line 130 is useful, and lines 138-140 explain from where the expression for beta_t comes from (though it is a bit confusing explanation), it is not at all clear how to construct such a function. Later on it is shown that the known online learning algorithms have corresponding potential functions. It would be really interesting if the authors can give some intuition on how to produce more such functions, thus saying that not only their algorithm generalizes the known results, but actually can produce new ones (and not just other similar potentials).  some other minor comments:  line 16 - "the Hilbert space" should be "a Hilbert space" unless this space is defined before. line 24-29 - It might be better to add some explanation what is a learning rate (and not just how you use it in the examples of OGD). If the reader didn't know what learning rate is before reading this paper, he would just be more confused after this introduction. Also, it might be a good idea to write that "parameter free" means that we do not set the learning rate in advance. It can also be as simple as writing "the learning parameter" or the "learning rate or leaning parameter" instead of just the "learning rate".  line 49 - what do you mean by dom(f) not empty? Is the domain not all of V? if this is possible, then you should write it explicitly.  line 109 - The inequality in (5) doesn't seem trivial. If it is just some calculations, maybe add another step or say that this is the case.  line 114 - why are the names of Krichevsky and Trofimov in Blue?  line 141 - The coin betting seems to be one dimensional always. What is the meaning of infinite dimensional in this line?  line 196 - is this "peculiar property" has any significance ?