Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers the classic online convex optimization game and proposes a method to obtain “full matrix” regret bounds in a “strongly adaptive” sense. That is, the algorithm outputs $w_t\in W\subset \mathbb{R}^d$ in response to vectors $g_1,\dots,g_{t-1}$ such that for any interval [a,b], the algorithm ensures:
$$\sup_{u\in W} \sum_{t=a}^b \langle g_t, w_t - u\rangle \le \tilde O(D \sqrt{d} \inf_{H\in \mathcal{H}}\sqrt{\sum_{t=a}^b g_t^\top H^{-1} g_t}$$

Where $\mathcal{H}$ is the set of symmetric PSD matrices of trace at most $d$ and $D$ is the L2 diameter of $W$.

Experiments are presented on problems with explicit drift and in offline deep learning settings.

strength_and_weaknesses: 
So far as I can tell, the results appear to be correct and are clearly presented and well-motivated. However, I have some concerns about the quality of the theoretical bounds.

In particular, the main term in the regret bound of $\sqrt{d} \inf_{H\in\mathcal{H}} \sqrt{\sum_{t=a}^b g_t^\top H^{-1} g_t}$ is equal to $\text{trace}\left(\sqrt{\sum_{t=a}^b g_tg_t^\top}\right)$ (by https://jmlr.org/papers/volume12/duchi11a/duchi11a.pdf lemma 15). 

Now, by applying the identity $\sum_{i} \sqrt{\lambda_i} \ge \sqrt{\sum_i \lambda_i}$ to the eigenvalues of $\sum_{t=a}^b g_tg_t^\top$, we have: $$\text{trace}\left(\sqrt{\sum_{t=a}^b g_tg_t^\top}\right)\ge \sqrt{\text{trace}\left(\sum_{t=a}^b g_tg_t^\top\right)}=\sqrt{\sum_{t=a}^b \|g_t\|^2}$$ where $\|\cdot\|$ indicates the 2-norm. Thus, the proposed bound of $D \sqrt{d} \inf_{H\in \mathcal{H}}\sqrt{\sum_{t=a}^b g_t^\top H^{-1} g_t}$ appears to never improve upon $D\sqrt{\sum_{t=a}^b \|g_t\|^2}$.  However, this bound is relatively easily obtainable without resorting to expensive matrix operations (e.g. in Cutkosky 2019 as cited in the paper. I believe also the analysis of Zhang et al 2018 https://arxiv.org/pdf/1906.10851.pdf can be tweaked to achieve this).

See for example http://blog.wouterkoolen.info/GrokkingAdaGrad/post.html for more discussion of this issue. So, while I am willing to believe that there is a possible improvement in the regret here, I do not see how this analysis brings it out. Instead, the theoretical result appears to be a somewhat worse regret bound with a significantly less efficient algorithm.

Some possibilities in this regard:

While the Duchi et al. 2011 does propose an example in which full-matrix adagrad performs better than a scalar learning rate, this analysis involved a special-case analysis of the dynamics of the algorithm rather than simply comparing regret bounds. Perhaps there is some way to modify this analysis to derive a general regret expression that can be applied here.

Alternatively, Cutkosky 2020 (https://proceedings.neurips.cc/paper/2020/hash/6495cf7ca745a9443508b86951b8e33a-Abstract.html) suggests that one can improve the analysis of adagrad by tuning the scalar part of the learning rate more carefully. Given the focus on learning rate adaptation in the experiments, perhaps the analysis could be improved to show a similar or better result in theory.


Beyond this issue, there should ideally be some discussion of Zhang et al 2018 https://arxiv.org/pdf/1906.10851.pdf  which achieves a different full-matrix bound of: $$\sum_{t=1}^T \langle g_t, w_t - u\rangle \le \tilde O\left(\sqrt{d \sum_{t=a}^b \langle g_t, w_t-u\rangle^2}\right).$$ Since both this paper and that one attempt to decrease the meta regret beyond $O(\sqrt{T})$ to obtain a better bound, it would be valuable to describe the differences.


Regarding the experiments: I appreciate the promise here, but I do not feel that these are convincing enough to overcome the analytical issues. With particular regard to the offline deep learning experiments, I am concerned that the algorithm will not scale to larger models. My understanding is that for modern extremely large models, even the space requirements that are a small linear multiple of the model size (e.g. as in Adam) can become difficult to accommodate, so I would much prefer to see convincing evidence that the method can scale up well. 

clarity,_quality,_novelty_and_reproducibility: No concerns here
summary_of_the_review: The theoretical results appear to not show advantage over prior methods. Given the focus of much of the paper on theory, this seems a significant issue.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an algorithm for strongly-adaptive full-matrix regret of the form $R_I\le \tilde O(\min_{H\succ 0}\sqrt{\sum_{t\in I} \|\|\nabla\ell_t(w_t)\|\|^2_{\star,H}})$ for any interval $I\subseteq[1,T]$. The core idea is to apply the geometric covering intervals of Daniely 2015 with instances of full-matrix AdaGrad as the base learners. A simplified version of the algorithm is tested empirically in simple online and offline experiments.
strength_and_weaknesses: Correctness
---
I have some concerns with the correctness of the analysis. 

Following standard experts analysis, the regret over an interval $I$ is decomposed as the regret of an expert $A_k$ on the interval, $R_{A_k}(I)$, and the regret of the meta-algorithm on the interval $R_\mathit{meta}(I, A_k)$ for not choosing this expert. To get the right rate in the meta-algorithm, it's necessary to balance a $\frac{\log(T)}{\eta}$ and a $\eta\sum\langle\nabla\ell_t(w_t),w_t-u\rangle^2$ term, where $\eta$ is the scaling factor of AdaGrad's step-size (see [Duchi 2011, Algorithm 2](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=14)). Since the optimal $\eta^\star$ is unknown a priori, the proposed algorithm runs several instances of AdaGrad over a grid of values, and argue that some $\eta_k\approx\eta^\star$, so that the meta-algorithm has the correct bound.

The flaw then is that it is stated that $R_{A_k}(I)\le O(D\min_{H\succ 0}\sqrt{\sum \|\| \nabla\ell_t(w_t)\|\|^2_{\star,H}})$ since it is an instance of AdaGrad (i.e. [Corollary 11](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=16)). But this is not true for arbitrary $\eta$. Instead, one should be invoking [Theorem 7](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=13) to get
\begin{align*}
R_{A_k}(I)&\le O\left( \frac{\|\|x^{\star}\|\|^2\text{Trace}(G_t^{\frac{1}{2}})}{\eta_k}+\eta_k \text{Trace}(G_I^{\frac{1}{2}})\right)\\\\
&\le O\left( \frac{\|\|x^{\star}\|\|^2\sqrt{\min_H\sum_t\|\|\nabla\ell_t(w_t)\|\|^2_{\star,H}}}{\eta_k}+\eta_k\sqrt{\min_H\sum_t\|\|\nabla\ell_t(w_t)\|\|^2_{\star,H}}\right)
\end{align*}
where $G_I=\sum_{t\in I}\nabla \ell_t(w_t)\nabla\ell_t(w_t)^\top$, and the inequality applies [Lemma 15](https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf#page=31).
Now if we assume that $\eta_k\approx \eta^\star=\sqrt{\frac{\log(T)}{D^2d\min_H\sum_t\|\|\nabla\ell_t(w_t)\|\|^2_{\star,H}}}$ (from page 13), we seem to get something strange like
\begin{align*}
R_{A_k}(I)\le \tilde O\left(D^3\sqrt{d}\min_H\sum_t\|\|\nabla\ell_t(w_t)\|\|^2_{\star,H}\right).
\end{align*}


Aside from this, there were a few minor oddities:
- Why are we assuming $G\ge 1$ and $D\ge 1$? This is not standard shouldn't really be necessary either
- It seems strange that the number of experts $Q=4\log(dTG^2D^2)$ in each interval is tied to the Lipschitz constant and the size of the domain, I don't think i've seen this happen in any prior works and it seems like it could lead to infeasible computation even at short horizons. In general, It's sort of rare to see factors of $G$ and $D$ inside of a logarithm without some fudge factor $\epsilon$ to correct the "units". I suspect that this issue is actually related to the above assumption that $G\ge1$ and $D\ge 1$ and the number of experts in an interval should actually be more like $O(\log(T))$

The Algorithm
---
- To get this sort of bound, is there any reason you couldn't just apply the residual learning algorithm of Cutkosky 2020? Their approach needs the base algorithm to have the parameter-free property $R_I(0)=\sum_{t\in I}\langle\nabla\ell_t(w_t),w_t\rangle\le \epsilon$ for some $\epsilon$, but there are algorithms with full-matrix regret bounds that do this, such as the Matrix FreeGrad algorithm of Mhammedi 2020.

Experiments
---
- "As described in the implementation section, SAMUEL here has five experts in total, which incurs five times more compute than one single run of the baseline. Nevertheless, this is a dramatic improvement over brute-force hyperparameter sweeping of learning rate schedulers"
  - I'm confused by this.  The preceeding paragraph states "specifically, we consider the quantity of decaying factors α with values {2, 3, 6} and {5, 10, 15, 20, 25, 30} number of $\eta$"; does this not imply that SAMUEL takes either 5x, 10x, 15x, 20x, 25x, or 30x computation compared to the baseline? Moreover, since these hyperparameters were tuned, overall didn't SAMUEL use the equivalent computation of a baseline which had its hyperparameters tuned over $3*(5+10+15+20+25+30)=315$ values?
  - Similarly, at the start of the section it's stated that "We experiment with popular vision and language tasks to demonstrate SAMUEL’s ability in selecting optimal learning rates on-the-fly without hyperparameter tuning"; but it seems that $\eta$ and $\alpha$ were actually  tuned hyperparameters?
- Specific hyperparameter settings are given in the appendix, but as far as I can tell there's no mention of how the baselines' hyperparameters were actually tuned. Without this information I can't really tell if these are actually reasonable baselines to compare against.
- "We demonstrate the effectiveness and robustness of SAMUEL in experiments, where we show that SAMUEL can automatically adapt to the optimal learning rate"
  - This was never actually demonstrated, just that SAMUEL empirically outperformed the baselines, none of which necessarily are equivalent to using the optimal learning rate


References
---
[1] Mhammedi, Z., & Koolen, W. M. (2020). Lipschitz and comparator-norm adaptivity in online learning. In J. Abernethy, & S. Agarwal, Proceedings of Thirty Third Conference on Learning Theory (pp. 2858–2887). PMLR.

[2] Cutkosky, A. (2020). Parameter-free, dynamic, and strongly-adaptive online learning. In H. D. III, & A. Singh, Proceedings of the 37th International Conference on Machine Learning (pp. 2250–2259). PMLR.


clarity,_quality,_novelty_and_reproducibility: The writing was generally well-written, clear, and easy to follow throughout, and seemed somewhat reproducible since they provide pseudocode for their practical implementation and test on standard benchmark problems.

Novelty
---
I think the main contribution of this paper may have already been achieved. In particular, Theorem 1 of Zhang et. al. (2021) provides an algorithm which achieves
$$
R_I(u)\le \tilde O\left(\sqrt{\sum_{t\in I}\langle \nabla \ell_t(w_t), w_t-u\rangle^2}\right)
$$
for any $I\subseteq[1,T]$ and comparator $u$ in the (bounded) domain. This implies the desired $\tilde O\left(\min_{H\succ 0}\sqrt{\sum_{t\in I}\|\|\nabla \ell_t(w_t)\|\|^2_{\star,H}}\right)$ bound using the same arguments as found on page 13 of the submitted paper. Please correct me if I am mistaken.



References
---
[3] Zhang, Lijun, Guanghui Wang, Wei-Wei Tu, Wei Jiang, and Zhi-Hua Zhou. "Dual adaptivity: A universal algorithm for minimizing the adaptive regret of convex functions." Advances in Neural Information Processing Systems 34 (2021): 24968-24980.
summary_of_the_review: Overall, I do not recommend accepting this paper in its current form. I am not confident in the correctness of the algorithm and analysis, which constitutes the main contributions of the paper, and a prior work (Zhang 2021) seems to achieve a strictly stronger result. The experimental results serve mostly as a sanity check, showing that a simplified version of their algorithm does something reasonable, but do not provide any novel insights in their own right.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Based on the strongly adaptive regret framework of Daniely et al., this paper proposes a strongly adaptive version of AdaGrad. The novelty seems to lie in an improved regret bound of SAOL, the meta algorithm of Daniely et al., which is similar to the regret bound of AdaGrad.
strength_and_weaknesses: ***Strength***
The idea is novel, simple, and seems to be effective in practice. 

***Weaknesses***
1. I do not understand the proof of Theorem 2, the main result, in Appendix A. Perhaps I missed something. The proof consists of three parts, among which the second part is new and confusing. 
    - The first part, until the first inequality on p. 13, just follows the proofs of Lemma 1 and Lemma 2 of Daniely et al. 
    - The second part is new and confusing to me. It directly analyzes the regret, without referring to any intermediate result obtained in the first part. The meaning of the first part is then unclear. 
    - Moreover, the second part starts with a regret bound of SAOL, which is the second inequality on p. 13. The regret bound is given without any proof and citation, but it is not obviously true to me. 
    - The third part, starting from Lemma 7, is a directly application of the results by Daniely et al. 
2. If I understand correctly, the result in this paper does not actually inherit the regret bound of AdaGrad. The regret bound in this paper has a $\sqrt{d}$ factor which is not present in the regret bound of AdaGrad (see, e.g., Theorem 5.6.1 of the second version of *Introduction to Online Convex Optimization* by Hazan). 
3. This is minor: Why not define $D$ as the radius of the constraint set? 


clarity,_quality,_novelty_and_reproducibility: ***Clarity***
The paper is clear. Nevertheless, for the reader to correctly understand the connection of this paper with existing work, it should be explicitly and clearly stated that the first part of the proof of Theorem 2, which occupies more than one page, simply follows the proof of Daniely et al. 

***Quality***
The presentation is fine. Below are some minor flaws. 
- Algorithm 1: Should $A_I (\tau)$ be $A_{I, q} (\tau)$? 
- p. 5: "Weighted majority" should be "multiplicative weight," too keep consistency of the terms. 
- Mathematical operators like "tr" should be in roman. 
- Please adjust the sizes of the brackets in the first two equations on p. 2. 

***Novelty***
The idea of developing an adaptive version of AdaGrad is novel. The regret bound of SAOL in Theorem 2 is the main technical breakthrough, but its correctness is in question; see my explanation above. 

This is minor: The second last paragraph of Section 1.1 and the second paragraph on p. 5 seem to be a novelty statement for SAOL of Daiely et al. and not for this paper. 

***Reproducibility***
The pseudo code for the numerical experiments is provided in Algorithm 2 in the appendix. 
summary_of_the_review: The idea is novel, simple, and seems to be empirically effective. However, the correctness of the theory is unclear to me, and the regret bound is indeed worse than that of AdaGrad by a $\sqrt{d}$ factor, which seems to be dismissed in the paper. Also, the connection between the proof of this paper and that by Daiely et al. is not addressed; this can mislead the reader about the paper's novelty. Therefore, I cannot suggest acceptance of this paper currently. 

====

***After reading the author response***

The first two weaknesses were actually due to my carelessness. I am sorry. 

However, the technical novelty seems to be limited and there is a novelty issue regarding the paper by Zhang et al. (NeurIPS 2021). So I cannot recommend acceptance of this paper. 

Two suggestions to the authors: 
1. Please highlight the novelty and address explicitly address what parts essentially follow existing proofs, to help the reader evaluate the novelty of the paper and its connection to existing literature.
2. Please make the dependence on dimension and possibly other problem parameters explicit in the big-O notations (e.g., in Table 1).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper have been carefully reviewed by experts in the field and found to be incremental with respect to prior work. In particular, two reviewers pointed out a paper that allow to derive the main result of this submission as a corollary. Given that in the rebuttal the authors acknowledged that they didn't know this paper, I encourage the authors to take it into account in their next iteration of their work.
justification_for_why_not_higher_score: There is a previous paper with a stronger result.
Decision: Reject