Learning the Learning Rate for Prediction with Expert Advice
Most standard algorithms for prediction with expert advice depend on a parameter called the learning rate. This learning rate needs to be large enough to fit the data well, but small enough to prevent overfitting. For the exponential weights algorithm, a sequence of prior work has established theoretical guarantees for higher and higher data-dependent tunings of the learning rate, which allow for increasingly aggressive learning. But in practice such theoretical tunings often still perform worse (as measured by their regret) than ad hoc tuning with an even higher learning rate. To close the gap between theory and practice we introduce an approach to learn the learning rate. Up to a factor that is at most (poly)logarithmic in the number of experts and the inverse of the learning rate, our method performs as well as if we would know the empirically best learning rate from a large range that includes both conservative small values and values that are much higher than those for which formal guarantees were previously available. Our method employs a grid of learning rates, yet runs in linear time regardless of the size of the grid.
The paper proposes a Learning the Learning Rate (LLR) algorithm for learning from expert advice which while retaining several worst case bounds for the problem enjoyed by previous algorithms like exponential weights algorithm, in addition also enjoys a guarantee on regret that is at most a poly logarithmic factor in number of experts and inversely in learning rate to the regret of exponential weights algorithm with that prescribed learning rate (for learning rates in a prescribed interval).  Further the proposed algorithm employs a grid over learning rates in the interval and yet runs in linear time regardless of the granularity of the grid. The problem of adaptively learning from expert advice in a way which while retains worst case guarantees also enjoys better practical performance against benign adversaries has been a problem of great interest. The algorithm proposed first of all neatly combines three adaptive bounds from previous works, the variance type bound, the L* type bound for small losses and a more recent bound of the order of follow-the-leader algorithm which has been shown to work well in practice (eg. for iid data). Overall the paper is well written and the problem considered is of practical interest.  Some remarks : 1. I do have some concerns over the lower limit of learning rate used though. Yes, it is true that sqrt{log K / T} is as small a learning rate one needs to consider to be able to guarantee the absolute worst case performance for prediction with experts advice. However in the regret bound you provide, the bound is with respect to eta chosen in hindsight. So it would make sense to provide bounds for even smaller learning rates. I wonder if one could get a guarantee over entire range of step sizes while worsening the regret bound by an additive factor beyond only the multiplicative factor over regret bound of best eta. 2. The paper only considers hind sign bounds w.r.t. to experts algorithms with optimal fixed step sizes. However in practice often step size schemes that vary with time are considered. For instance one might consider step sizes of form eta_t =  eta / t^a  where eta and a are tuned. The result in this paper only refers to a = 0. At least glancing from the results it is not clear to me that the results can be adapted to the non-zero a case.