Prodigy: An Expeditiously Adaptive Parameter-Free Learner

Summary

Overall, I very strongly recommend rejection. The paper makes no new theoretical contributions and is seemingly unaware of large portions of the related literature. The results presented here have already been achieved more generally and in harder problem settings, and the lower bounds are both invalid. The experiments show some evidence of improvement over D-Adaptation, but makes no attempt to compare against the obvious existing baselines from the online learning literature. The main novelty is the improvement of the results from the D-Adaptation paper, which suffered from all of the same issues mentioned above, so I don't believe improving over this work warrants publication. Additional discussion on these points is provided below.

The Algorithm

Algorithms that attain the $\\|x_0-x^\*\\|\sqrt{\log(\\|x_0-x^\*\\|/d_0)}/\sqrt{T}$ rate (or equivalently $\\|x_0-x^\*\\|\sqrt{T\log(\\|x_0-x^\*\\|/d_0)}$ regret) under Lipschitz losses have existed for almost a decade now, and they accomplish it in strictly harder problems (see e.g. McMahan & Orabona 2014, Orabona & Pal 2016, Cutkosky & Orabona 2018). In particular, there are countless algorithms from the so-called "parameter-free" online learning literature which already achieve this result in the significantly harder adversarial online learning setting, in which the $\\|x_0-x^*\\|\sqrt{T\log(\\|x_0-x^\*\\|/d_0)}$ regret is un-improvable. The methods presented here achieve this rate in the easiest possible problem setting: optimizing a fixed function, where this rate isn't even optimal. Non-trivial extensions have even been achieved in these harder problem settings, such as as scale-free learning (Mhammedi & Koolen 2020), dynamic regret (Jacobsen & Cutkosky 2022), learning with switching costs (Zhang & Cutkosky 2022b), and many more. Note that these results have been achieved using a variety of approaches: coin-betting, FTRL, mirror descent, and general potential-based approaches, while the discussion in Section 5 seems to only be aware of the coin-betting approach.

The paper also claims to improve on methods other than D-Adaptation, such as the T-DoG algorithm of Ivgi et al (2023). This is factually incorrect: the problem setting studied in this paper is strictly easier than all other comparable works in this field (besides D-Adaptation), so Prodigy actually has no guarantee in the problem setting studied by Ivgi et al. 2023. In this sense Prodigy is actually a strict downgrade of T-DoG, and likewise of any of the other existing works that can solve the problem studied here.

Section 5 also implies that standard D-adaptation (and Prodigy by extension) actually improve over the existing online learning works, as "Standard D-Adaptation obtains asymptotic rates without the log factor". This is at least misleading: their asymptotic result holds under the condition that the user chooses $d_0\le \\|x_0-x^\*\\|$, which would only be possible to guarantee if you have prior knowledge of $\\|x_0-x^\*\\|$. If you had this prior knowledge, you wouldn't need any special algorithm to achieve the $O(G\\|x_0-x^\*\\|/\sqrt{T})$ rate, you could accomplish this using gradient descent with step-sizes $\eta_t = \frac{\\|x_0-x^\*\\|}{\sqrt{G^2+\sum_s^{t-1}\\|g_s\\|^2}}$. One might argue that you can just set $d_0$ to be very close to 0, but the smaller you set $d_0$, the longer it takes for the asymptotic result to kick in, making it easy to wind up with a result that holds only for some $\tilde T$ such that $G\\|x_0-x^\*\\|\sqrt{\tilde T}\ge G\\|x_0-x^\*\\|\sqrt{T\log(\\|x^\*-x_0\\|/d_0)}$, making the result again redundant. So there is no meaningful improvement via the asymptotic result either.

An Adam-based variant is also proposed, but this leads to something of a contradiction: Adam itself isn't guaranteed to converge (Reddi et al. 2019), so Prodigy+Adam isn't guaranteed to converge either. How can we claim an algorithm as "parameter-free" if it makes zero performance guarantees and may diverge? The whole point is that the algorithm makes some performance guarantee without tuning hyperparameters. Moreover, it's unclear to me how interesting the global step-size of Adam even is --- the momentum parameters have far more impact on the behavior of Adam. The experiments claim that Prodigy+Adam performs roughly as well as hand-tuned Adam, but I would not be surprised if Adam with the default global step-size also performed similarly to hand-tuned Adam.

The Lower bounds

Neither of the lower bounds are valid constructions. The lower bounds choose $D$ to be either $2^{2^T}x_1$ or $2^Tx_1$, neither of which are valid ways to construct the stated lower bound, because now the bound holds for only a specific class of comparators, rather than for all comparators simultaneously. In other words, the lower bounds should show that for any $D,G$, there is an $x^\*$ such that $\\|x_0-x^\*\\|= D$ and the stated lower bound holds. This is also what the theorem statement implies is happening, until you actually read the proof, which is misleading.

The Experiments

The experiments demonstrate some improvement over D-Adaptation, but are not particularly convincing aside from that. Notably, the experiments include no baselines from the many existing works from online learning. Given that there are several existing algorithms that already achieve stronger results than presented here, this paper should at the very least be justifying its existence by showing some improvement over these existing works. Yet not a single one is included as a baseline.

The experiments use other tricks on top of Prodigy such as a warm-up epoch, step-size annealing, and weight-decay, so I'm again unsure how the algorithm can be claimed to be an "Expeditiously Adaptive Parameter-Free Learner" --- these all involve some form of hyperparameter selection. I also don't understand why weight decay is necessary; adding an L2 penalty to the loss will implicitly constrain the algorithm to a ball of some radius, which shouldn't even be necessary for an algorithm that already adapts to $\\|x_0-x^\*\\|$. The fact that this needed to be included suggests that the algorithm in fact does not attain this form of adaptivity in general, as one would hope to demonstrate in the experiments.

The Large-scale Adam experiments of Section 6.1 show evidence that the performance of Prodigy can be similar to that of hand-tuned Adam. However, as mentioned earlier, this is not particularly convincing on its own because Adam's global step-size has a relatively benign impact on performance. These experiments should at least include "un-tuned Adam" using the default step-size, which I suspect will also perform similarly to Prodigy.

References

• Cutkosky, Ashok, and Francesco Orabona. "Black-box reductions for parameter-free online learning in banach spaces." Conference On Learning Theory. PMLR, 2018.
• Mhammedi, Zakaria, and Wouter M. Koolen. "Lipschitz and comparator-norm adaptivity in online learning." Conference on Learning Theory. PMLR, 2020.
• Jacobsen, Andrew, and Ashok Cutkosky. "Parameter-free mirror descent." Conference on Learning Theory. PMLR, 2022.
• Orabona, Francesco, and Dávid Pál. "Parameter-free stochastic optimization of variationally coherent functions." arXiv preprint arXiv:2102.00236 (2021).
• Orabona, Francesco. "A modern introduction to online learning." arXiv preprint arXiv:1912.13213 (2019).
• Orabona, Francesco, and Dávid Pál. "Coin betting and parameter-free online learning." Advances in Neural Information Processing Systems 29 (2016).
• McMahan, H. Brendan, and Francesco Orabona. "Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations." Conference on Learning Theory. PMLR, 2014.
• McMahan, Brendan, and Matthew Streeter. "No-regret algorithms for unconstrained online convex optimization." Advances in neural information processing systems 25 (2012).
• Reddi, Sashank J., Satyen Kale, and Sanjiv Kumar. "On the convergence of adam and beyond." arXiv preprint arXiv:1904.09237 (2019).
• Zhang, Jiujia, and Ashok Cutkosky. "Parameter-free regret in high probability with heavy tails." Advances in Neural Information Processing Systems 35 (2022a).
• Zhang, Zhiyu, Ashok Cutkosky, and Yannis Paschalidis. "Optimal Comparator Adaptive Online Learning with Switching Cost." Advances in Neural Information Processing Systems 35 (2022b)

The main weakness of the paper might boil down to presentation, but I am having a hard time correctly understanding many of the contributions. I am mostly knowledgeable on the theoretical aspects of optimization and online learning (although I am not closely acquainted with parameter-free methods in online learning). Maybe some of my worries are due to a lack of background from my part, At the same time, I consider myself a researcher with more knowledge in these fields than the average person in the community. So I do think these worries would be shared by many people that even work in topics related to this paper. I hope my questions and discussion with authors and reviewers help me arrive to a fair assessment of the paper. Of course, feel free to let me know if I am missing a major point of the paper or a big piece of the literature that was not mentioned in the prodigy paper due to space constraints. The main point is likely the first one, the other ones are minor points.

Prodigy convergence rates vs rates in more general settings: Theorem 1 and 2 show that prodigy improved on the learning rate of D-adaptation by a factor of $\sqrt{\log(D/d_0)}$. It is not clear if this improvement should be expected to be reflected in empirical problems since in practice we see convergence rates that are much faster than $1/\sqrt{t}$. In this case, if the rate does not reflect what happens empirically, I would guess that getting better rates is important for its novelty among other convergence rates. However, in the related work section the authors say that this new rate matches the one from online learning, which is a much more adversarial setting. In the stochastic case, which more closely matches the deep learning optimization case, the work of Carmon and Hinder (2022) have a $\log \log (D)$ factor in the convergence rate for the deterministic version of the algorithm if I am not mistaken, which is better than Prodigy's convergence rates. However, this is mostly a theoretical work, and the goal of Prodigy is to also be practical. On this line, the authors claim that they improve on the DoG convergence rates by shaving off a $\sqrt{\log D/d_0}$ factor. The DoG rates are for the stochastic setting with locally Lipschitz gradients, significantly more general than the deterministic setting where the rates of Prodigy hold.

So in the end I am not able to grasp what is the relevance of the improved theoretical convergence rates. It is in fact interesting that the improvement in the empirical performance might be connected to this slightly tighter convergence rate. But it is not clear how connected they are, if at all, and the paper does not discuss this connection. In the purely theoretical side, the rates at match (or slightly improve in the case of DoG) over other convergence rates, but on a more restricted setting.

Comparison with other algorithms: Although the empirical results are definitely the strongest part of the paper, I did not understand why the only comparison point in the experiments is D-adaptation and DoG. Maybe this is discussed in a part of the appendix that I have not read (if so, please let me know), but is it the case that any other algorithms perform poorly enough that they are not worth considering in these comparisons?

Here are a few minor suggestions:

Lower bounds and the dependency of $n$ and $D$: I thought the lower bounds were interesting, but the fact that the function $f$ (and, thus, $D$) depend on $n$ in such a way that $\log \log D/d_0$ is roughly of order $\sqrt{n}$ seems very important and a big reason why these lower bounds do not rule out the possibility of improved asymptotic convergence rates, even in the stochastic case. Although this is mentioned by the authors before the lower bounds, adding that this is the case in the theorem statements themselves would make them more readily understandable by people. Mentioning that the function is of the form $f(x) = |x - x^*|$ could also be interesting, if space allows.

Typos and crammed equations: As a last minor point, there are several equations that are crammed in the paper (sometimes with parts going on top of the text). I understand the submission process can be rushed, but if the authors could do a revision pass of the paper, it would be great.

1. Both approaches appear to be more complex than the original D-adaptation approach, by introducing additional weights, and the practical benefit of the newer theoretical guarantees is not clear. As mentioned, they remove one factor from the non-asymptotic bound of D-adaptation, but replace it with another. It is not clear how much tuning was needed to obtain the small occasional improvements over D-adaptation in Figures 1-3.

2. The paper is also marred by symbolic confusion and occasional grammatical errors, e.g.,

   2a. line 4 in Algorithm 2 mentions $\lambda_k = d_k^2$, but the fifth line of Sec. 2 mentions $\lambda_k = d_k$

   2b. Grammatical error or typo in Sec 5, page 7: "...can divergence in theory..."

   2c. Grammatical error or typo in Sec 5, page 7: "...initial sub-optimally of the D estimate ... "

I’m mostly concerned about some of the claims made in the non-convex deep learning section, beyond just the fact that what any of these algorithms are really doing deep learning is unclear.

• In terms of practical impact, the improvements made by Prodigy reported Figure 1/2/3 are small. Often the differences between Adam, Prodigy, and D-Adaptation are much smaller than their standard errors. It doesn’t always do better either, superseded by Adam, and sometimes D-Adaptation.
• Adam’s initial learning rate should be hyperparameter tuned.
• They start to make claims about the test accuracy / generalization that I don’t think they should/need to include. Specifically, they make this claim about CIFAR10 on ResNet and ImageNet on Vision Transformers. In both scenarios, the models are overfitting, trained for hundreds of epochs on the training data. Lower training loss here does not necessarily mean higher test accuracy.
  • Under Figure 1, they write “Prodigy estimates a larger step size than D-Adaptation, which helps it reach test accuracy closer to the one of Adam.” (They aren’t talking about any implicit bias of large learning rate, just strictly that large learning rate leads to better training loss convergence.)
  • Under paragraph “ViT training” they write “Prodigy almost closes the gap [of test performance] between tuned Adam and D-Adaptation.”

Some other minor comments:

• Can Figure 2 be plotted in log scale? It’s hard to see the difference between the lines.
• Text spacing issue in Page 3