Summary
A new algorithm for online learning is provided, together with improved regret bounds compared to the state-of-the-art:
The new regret guarantees are summarised in table 1 on page 2: in the case of a strongly convex function, the regret guarantee is of $O(min(\log(V_T),\log (F_T)))$ where $V_T$ and $F_T$ are the gradient variation and cumulative loss of the best comparator respectively (cf. equation on lines 53 to 54). In the case of exp-concave functions, the rate is the same, whereas in the case of a convex function, the rate is $\widetilde{O}(\min(\sqrt{V_t},\sqrt{F_T})$ instead. In terms of the regret bound, only the convex case is an improvement over the existing results ([3], $O(\sqrt{F_T})$). An additional claimed advantage is that the gradient query is reduced to $O(1)$ instead of $O(\log(T))$: this is valid for an improved algorithm (separate from the main algorithm presented in the paper) with additional surrogate losses, which is only presented in the appendix on page 18 (Algorithm 2)
The main algorithm itself is a combination of several existing techniques: at each iteration, a set of $KN$ experts $(k,i)\in [K]\times [N]$ each consisting of different gradient descent methods is maintained. Each expert computes the gradient update as per Optimistic OMD [3]. Then, for each fixed $k$, the experts $(k,i')$ for $i'\leq N$ are aggregated exactly as in MsMwC (cf. [1] and equation (2.3)), then the resulting experts are aggregated again via another use of MsMwC, with different parameters. The proof is a very long list of re-expressions of the regret via various existing results and additional calculations, drawing a lot of inspiration from [1], which itself improves on techniques in [2].
=================Post-Rebuttal=============
After discussing with the authors, I am convinced that the presentation issues are theoretically fixable, and I still think the amount of work is adequate. Thus, I will keep my score and hope the authors fix all the minor errors as promised and try hard to make the paper more accessible to a broader audience.
==============
**References**
[1] Sijia Chen, Wei-Wei Tu, Peng Zhao and Lijun Zhang. Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization. ICML 2023.
[2] Pierre Gaillard, Gilles Stoltz and Tim Van Erven. A Second-order Bound with Excess Losses. COLT 2014.
[3] Lijun Zhang, Guanghui Wang, Jinfeng Yi and Tianbao Yang. A Simple yet Universal Strategy for Online Convex Optimization. ICML 2022.
Strengths
This is a highly technical and long paper and it is clear the authors know what they are doing. The parts of the proofs I managed to check are generally correct with only minor typos (though they are not reader friendly).
Weaknesses
In my opinion, the main paper is poorly written. I understand that the authors are trying to explain the intuition for why they construct their algorithm in this way, but there isn't enough context or revision of existing methods to make the paper readable.
The paper reads like a soliloquy of a researcher trying to solve the problem at hand: for instance, in lines 140 to 148, the authors are saying "if we used Adapt-ML [2], bad things ill happen, what can be done about this?" then later in Section 3, their solution is proposed, which consists in using [3] instead, with a purportedly novel choice of optimism.
See also how the authors are using expressions like "Another try is to" on line 206. This is an issue not just in terms of grammar but also because it occurs in the context of a vague exposition that follows the stream of consciousness of the author rather than trying to present a cogent story.
Here are examples of more concrete **issues with the presentation**:
**1** There is a lot of talk in the main paper of "how to cancel out terms" which comes a long time before the part where the authors introduce their main algorithm. When they finally decide to do so on page 7, it is only the basic version of the algorithm (not the one with the $O(1)$ gradient calls) and it still vaguely refers to "the base learners described in Section 2", which I can only imagine refers to what is introduced in line 168 (section 3.1), but is still presented as new in line 177 "to unify all kinds of functions, we propose...."
**2** The concept of "optimism" isn't properly introduced either in the main or in the supplementary; the only definition is on line 72 in the intro: "a hyperparameter encoding historical information", which I am given to understand means slightly different things in different algorithms. A few more words of explanation here would be nice. Definitely, the base learners should be defined properly in the main text. In the current form, not even the reference to [3] is especially clear outside of Table 1. The same goes for the section names, terms such as "exogeneous negativity" are not very informative. In footnote 2, the authors even speak of "implementing $m_t$", which is definitely very informal and should be explained more clearly.
**3** Note also that the Bregman Divergence is note defined in lines 486 to 487 or 211-212 (page 6), despite the fact that it would make the description more complete and that it is indeed defined in the reference [1] when the same equation is introduced.
**4** In the proof of Lemma 2, the first equation is hard to understand without background in the field. the only explanation is "by standard analysis of optimistic OMD". It would be nice to say that this refers specifically to Theorem 1 of [4], which is explained better later in the appendix when the argument arises again (line 767 page 30). Since it is natural for the reader to read the proof of Lemma 2 first, the more detailed explanation should be present there as well.
**5** Similarly, the proof of Lemma 1 on page 14 uses equation E.1 from page 29, which is completely unnecessary as E.1. is derived from first principles.
**6** The proof of Lemma 2 is done for "an arbitrary comparator $u\in\Delta$, but the concept of comparator isn't really defined there, though it becomes clear from context after some effort. This also seems to run counter to the fact that in the main paper the authors write elsewhere in the paper that they "focus on the proof for fixed learning rate", which seems not to be the case in the case of the proof of Lemma 2.
**7** What does the notation $\|.\|_{U_t}$ mean on line 761? Is it explained somewhere?
I understand that I am not an expert in the field and my difficulties understanding the bigger picture is mostly due to this, but I do feel like in the case of well written papers, I am often able to make better progress, in less time, towards understanding more complex papers than this one in equally distant areas. However, I am not sure, it may be that the prerequisites are intrinsically larger.
**References**
[1] Sijia Chen, Wei-Wei Tu, Peng Zhao and Lijun Zhang. Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization. ICML 2023.
[2] Pierre Gaillard, Gilles Stoltz and Tim Van Erven. A Second-order Bound with Excess Losses. COLT 2014.
[3] Lijun Zhang, Guanghui Wang, Jinfeng Yi and Tianbao Yang. A Simple yet Universal Strategy for Online Convex Optimization. ICML 2022.
[4] Zhao, Peng ; Zhang, Yu-Jie ; Zhang, Lijun ; Zhou, Zhi-Hua. Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization. ArXiv. May 2023.
Questions
**1** Can you describe the base learner from [3] concisely? Perhaps rewrite the main paper in a more careful way?
**2** I am a bit confused about what you mean by the $O$ notation sometimes: which constants are considered to be "$O(1)$ exactly? In page 31, it seems like $\gamma$ is treated as a variable (not $O(1)$), but it is less clear in the case of $D$ and $G$: at the end of the proof of Lemma 10, **the $O(1)$ notation hides a term of $4DG^2$**. If you can absorb this into the $O(1)$ notation, why do you still need to write $\gamma D^2$? I can sort of see that the reason is that there is a $\gamma$ in there, but providing a bit of context might help.
**3** Do you really mean an equal sign at the second equality (first line) describing the Adaptivity term in page 30? it seems like if $1/\gamma<\frac{D}{\sqrt{1+\bar{V_T}}}$, **the equality wouldn't hold**. More worrying still, the inequality would be in the wrong direction.
**4** In lemma 3, you make the assumption that $(\ell_{t,k -m_{t,k}})^2 =\langle l_{t,k}-m_{t,k},p_{t,k}\rangle^2$. Could you provide more context there?
**5** Could you summarize the difference between your work and [1] more concisely? Why was the base learner [3] not used directly in [1]? What would happen if we used the correct base learner but did not use the hierarchical approach from your method?
**Minor mathematical errors:**
**1** I think the term $-8\sum_{t=2}^T \|p_t-p_{t-1}\|$ should be $-4\sum_{t=2}^T \|p_t-p_{t-1}\|$ in Lemma 2. Indeed, the definition of "term C" excludes the factor of $1/2$ at the bottom of page 14 (as evidenced not just by the curly bracket but also by the use of Pinsker's inequality in line 498 as there would need to be a factor of 16 instead of 32 if the 1/2 were included): this factor of $1/2$ needs to be reintroduced in line 513 on page 16. It would also be nice to quote Pinsker's inequality and perhaps add a citation at line 499 (page 15).
**2** In the calculations on page 15, lines 497-498, at the third equality on the first line, the $b_i$ should be at the numerator instead of the denominator.
**3** In the second line of the series of equations for the optimality gap in the proof of Lemma 10 on page 30, I think it should be $\leq$ instead of $=$ because there is a term of $-\|x^*-\hat{x}_{T+1}\|^2\frac{1}{2\eta_T}$ which is dropped out.
**4** In the statement of Lemma 5, it should be $\|p-q\|_1^2$ instead of $\|p-p\|_1^2$
**5** In the proof of Lemma 1 on page 14, at the second line of equalities after line 482, I think it should be $\leq $ and not $=$ because of a missing $\langle g_T-g_{T+1},x_T-x_{T,i*}\rangle$ term which is added to make the sum look simpler.
**6** In the definitions of the iterations of $p_t$ and $q_t$ from [1] in line 486 page 14 and also in line 211 page 6, the last term should be $D(p,q_{t-1})$ instead of $D(p,q_{t})$, consistent with equation 6 in [1]. **NB**: I have used q instead of \hat{p} due to issues with markdown.
**Typos**
line 7: "the O notation" (missing "the")
line 146: constants=> constant
line 161, same thing
line 205 "it is still open that whether..>" ==> "it is still an open problem to determine whether"
line 217 "same of" ==> "same as"
line 252 "same of" ==> "same as"
line 488: "follows the similar logic of" ==> "follows a similar logic as"
line 506 "which equals to" ==> "which is equivalent to" (this somewhat changes the meaning and makes the line more understandable. Also, one might want to consider turning some of these inline equations into {align} blocks).
line 739 "it the optimal step size" ==> "if the optimal step size"
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The improvement compared to [3] is somewhat disappointing compared to the much larger complexity of the algorithm: it seems that eh main improvement is to use a single algorithm for all types of functions and to reach similar rates, with a better rate in the case of convex functions. This is interesting theoretically but the algorithm seems too unwieldy to be used in either practice or future work.
I cannot fully vouch for the correctness as I often had to read the supplementary line by line without fully grasping the bigger picture. It is also hard to vouch for the originality compared to [3] as I am not familiar enough with it. Nevertheless, this seems like solid work, assuming the presentation was improved.