MetaGrad: Multiple Learning Rates in Online Learning
In online convex optimization it is well known that certain subclasses of objective functions are much easier than arbitrary convex functions. We are interested in designing adaptive methods that can automatically get fast rates in as many such subclasses as possible, without any manual tuning. Previous adaptive methods are able to interpolate between strongly convex and general convex functions. We present a new method, MetaGrad, that adapts to a much broader class of functions, including exp-concave and strongly convex functions, but also various types of stochastic and non-stochastic functions without any curvature. For instance, MetaGrad can achieve logarithmic regret on the unregularized hinge loss, even though it has no curvature, if the data come from a favourable probability distribution. MetaGrad's main feature is that it simultaneously considers multiple learning rates. Unlike previous methods with provable regret guarantees, however, its learning rates are not monotonically decreasing over time and are not tuned based on a theoretically derived bound on the regret. Instead, they are weighted directly proportional to their empirical performance on the data using a tilted exponential weights master algorithm.
Online convex minimization is a fundamental problem in learning theory with various applications. Here, we are given a sequence of convex functions f1,...,fT in an online fashion and we seek to predict the minimizer of the sum so as to minimize the regret. This is a very well studied question with various guarantees known even when only given gradient information about the functions fi. For general functions this leads to a regret of sqrt(T) and for some special cases, we know better guarantees: O(log T) for strongly convex functions, O(d log T) for exp-convex functions etc. However, the algorithms that achieve the latter better guarantees are quite different and in some cases need to know bounds on the specific parameters of the functions (e.g., strong-convexity of the fi's, although this can now be avoided).   The paper seeks to present a single algorithm which with a small overhead, achieves the right dependence on T for all the above cases. As such, this is a very nice research direction.  Algorithm: The algorithm uses several techniques from previous works and while not very novel combines previous ideas in a clever way. The high level idea is to run several slave algorithms (that sort of correspond to using different parameter ranges for the base learning algorithm) and then use a master algorithm that combines the slave algorithms by using a modified exponential-weights method. This sort of approach of using two levels of learning algorithms is not particularly new to this approach, but the exact application is non-trivial.  Writing: The paper is written reasonably well but the high-level description of the algorithm can use more work. Specifically, it is too vague in some very important places (e.g., "tilted by learning rates") and assumes too much familiarity with previous work ("adaptive regularizer", "temporal ...") that muddles the presentation. It is important to connect to previous works, but it will be more helpful for the reader if such terms can be explained and if not they do not seem to help much.
The problem and algorithm are nice but there are two important drawbacks: the new algorithm does not seem to cover (i.e., obtain better than O(sqrt(T)) guarantee) any interesting new cases; the bound for strongly-convex is worse than what is known already. Even with these drawbacks, I recommend the paper be accepted as the problem is quite nice and the approch could be useful in the future.