Improved Dynamic Regret for Non-degenerate Functions
Recently, there has been a growing research interest in the analysis of dynamic regret, which measures the performance of an online learner against a sequence of local minimizers. By exploiting the strong convexity, previous studies have shown that the dynamic regret can be upper bounded by the path-length of the comparator sequence. In this paper, we illustrate that the dynamic regret can be further improved by allowing the learner to query the gradient of the function multiple times, and meanwhile the strong convexity can be weakened to other non-degenerate conditions. Specifically, we introduce the squared path-length, which could be much smaller than the path-length, as a new regularity of the comparator sequence. When multiple gradients are accessible to the learner, we first demonstrate that the dynamic regret of strongly convex functions can be upper bounded by the minimum of the path-length and the squared path-length. We then extend our theoretical guarantee to functions that are semi-strongly convex or selfconcordant. To the best of our knowledge, this is the first time that semi-strong convexity and self-concordance are utilized to tighten the dynamic regret.
In this paper, the authors study the problem of minimizing the dynamic regret in online learning. First, they introduce squared path-length to measure the complexity of the comparator sequence. Then, they demonstrate that if multiple gradients are accessible to the learner, the dynamic regret of strongly convex functions can be upper bounded by the minimum of the path-length and the squared path-length. Finally, they extend their theoretical guarantees to functions that are semi-strongly convex or self-concordant.
This is a theoretical paper for analyzing the dynamic regret. The main difference from previous work is that the learner is able to query the gradient multiple times. The authors prove that under this feedback model, dynamic regret could be upper bounded by the minimum of the path-length and the squared path-length, which is a significant improvement when the squared path-length is small.
Strong Points:
1. A new performance measure is introduced to bound the dynamic regret.
2. When functions are strongly convex, the authors develop a new optimization algorithm and prove its dynamic regret is upper bounded by the minimum of the path-length and the squared path-length.
3. This is the first time that semi-strong convexity and self-concordance are utilized to tighten the dynamic regret.
Suggestions/Questions:
1. It is better to provide some empirical studies to support the theoretical results.
2. For self-concordant functions, why do we need an additional condition in (11)?
3. Due to the matrix inverse, the complexity of online multiple Newton update (OMNU) is much higher than online multiple gradient descent (OMGD), which should be mentioned explicitly.