Summary
Problem: The paper studies the OCO problem under the generalized smoothness assumption, i.e. at each time $t$, $f_{t}$ satisfies $\|| \nabla ^ {2} f_{t} (x) \|| \le \ell_{t}(\|| \nabla f_{t}(x) \||)$ for all $x \in \mathcal{X}$, where $\ell_{t}$ is a positive non-decreasing function. In addition to the information model in OCO, the algorithm can query $\ell_{t}$ at any local point $x \in \mathcal{X}$. This condition subsumes global smoothness, i.e. $\ell \le L$ is upper bounded globally, and $(L_{0},L_{1})$ smoothness, i.e. $\ell(x) = L_0 + L_1 x$; which have been studied in the prior works. The authors obtain gradient-based variation bounds for several settings of interest (see contributions below).
Contributions:
1) First, the authors extend the classic optimistic OMD algorithm to handle generalized smoothness and obtain an optimal $\mathcal{O}(\log V_{T})$ rate for strongly convex and $\mathcal{O}(\sqrt{V_{T}})$ static regret for convex functions (ref. Theorem 1, 2). However, these rates are first derived assuming that the algorithm knows the curvature of the $f_{t}$'s, i.e. whether all the $f_{t}$'s are convex or strongly convex.
2) To circumvent the curvature information, the authors devise an algorithm that is adaptive to the curvature of the functions $f_{t}$'s (referred to as universal online learning -- the goal is to obtain an algorithm with simultaneous guarantees for convex and strongly convex functions). The proposed algorithm obtains the optimal $\mathcal{O}(\sqrt{V_T}), \mathcal{O}(\log V_T)$ static regret bounds for convex, strongly convex functions respectively (ref. Theorem 4).
3) Finally, the authors consider stronger regret measures, i.e. interval regret and dynamic regret (referred to as non-stationary online learning), and propose an algorithm with the optimal gradient variation-based regret guarantees (ref. Theorem 5, 6).
Strengths
The paper is solid and shows that gradient variation-based bounds can be derived under a more general smoothness assumption. Prior works focused on global smoothness, or $(L_{0}, L_{1})$ smoothness, and did not consider some or the other regret metrics as considered in the paper, e.g. the authors mention that an adaptive regret guarantee was not obtained even in the context of global smoothness.
While this might seem doable, the authors very well mention the key challenges in obtaining the desired algorithms, e.g. for contribution (2) above, section 3.2 does a great job of highlighting the key challenges. I liked this section and the authors spent considerable effort explaining why existing meta algorithms, e.g. McMwC-Master algorithm (Chen et al.) do not directly work since they cannot handle heterogeneous inputs.
The function-to-gradient variation technique is simple and seems pretty useful since it allows us to decouple the meta-algorithm and the base learners and explicitly aim toward obtaining a meta-algorithm with the desired guarantee. It helps avoid the seemingly messier cancellation-based tricks as done by Yan et al.
Weaknesses
1) Section 4 is presented in a rush. Like section 3.1, it would be quite beneficial to have some more discussion on the algorithm and potential challenges in deriving non-stationary regret guarantees. The authors claim that their proposed algorithm is the first to obtain gradient variation-based non-stationary regret guarantees under the generalized smoothness assumption, whereas prior works did not obtain similar guarantees under the global smoothness assumption. The authors should have at least backed this with the potential difficulties faced by existing approaches. I recommend that the authors cut down some earlier discussions, such as the discussion about exp-concave functions, which in my opinion is not very relevant, given that the entire paper is about convex and strongly convex functions.
2) While the paper shows interesting results, I feel the key ideas are borrowed from existing works. While this is fine, in some places the authors failed to mention the potential technical challenges in the analysis. This is the most applicable to section 3. The authors mention that the proposed algorithm can be analyzed similarly to the prod-style algorithms. Are there technical difficulties in directly incorporating the analysis of prod-style algorithms into Algorithm 1?
Some minor typos that I found:
1) Line 38: "stochatsic -> stochastic"
2) Lemma 1: Remove the $\ell_t$
Questions
1) The discussion towards the end of page 3 is confusing to me. The authors mention that assuming the Lipschitzness of $f_{t}$ is not reasonable since the bound on $\|| \nabla ^ {2} f(x) \||$ can be obtained from knowing $\ell$ directly, and the function is globally smooth. However, the bounds presented in the Theorems are a function of the Lipschitzness parameters. I would appreciate clarification from the authors.
2) In the Equation after Line 384, $\xi_{t, i}$ is not necessarily same for $f_t$ and $f_{t - 1}$ since the Mean Value Theorem only guarantees the existence of a $\xi$. With $\xi_t$ and $\xi_{t-1}$ being possibly different, I don't think the next inequality follows immediately. Is that a typo or am I missing something?
Limitations
The authors adequately addressed the limitations.