This paper proposes a new easy-to-implement parameter-free gradient-based optimizer: DoWG (Distance over Weighted Gradients). We prove that DoWG is efficient -- matching the convergence rate of optimally tuned gradient descent in convex optimization up to a logarithmic factor without tuning any parameters, and universal -- automatically adapting to both smooth and nonsmooth problems. While popular algorithms following the AdaGrad framework compute a running average of the squared gradients to use for normalization, DoWG maintains a new distance-based weighted version of the running average, which is crucial to achieve the desired properties. To complement our theory, we also show empirically that DoWG trains at the edge of stability, and validate its effectiveness on practical machine learning tasks.
Paper
Similar papers
Peer review
Summary
This paper is concerned with parameter free - adaptive first order optimisation method, that is a method that achieves optimal rates of convergence in the class of function considered without having access to a priori quantities such as smoothness of the function or the minimum value of the function. The authors discuss on normalized gradient descent and they show that this method is adaptive to the smoothness of the function when the step-size is proportional to the distance to the minimizer. The main contribution of the paper is to introduce a new estimation of the distance to the minimizer that achieves optimal rate up to logarithm factor. The method is an improvement over the so-called distance over gradients (DoW) by introducing weights (DoWG) so that it gives more weight to the last gradients. Numerical experiments are provided, including comparison to Adam (which is not in the same category...).
Strengths
I am not a specialist of the field so my contribution in this review was to check the proofs, also in the supplementary material. All the proofs are correct. The paper is globally nicely written, easy to read and accessible for an outsider of the field as I am. Although from the theoretical point of view, DoWG is incremental (correct me if I am wrong), numerical experiments tend to show that it is clearly more efficient practically. Although the resulting algorithm performs poorly compared to Adam, it seems a fair contribution on the understanding and the technics in the class of methods considered.
Weaknesses
This work appears as an improvement over DoG. It is a bit surprising that the result on Normalized Gradient Descent is new; I was not able to find it in the literature although, again, I am not an expert in the field. The proposed method DoWG of using weights in front of the gradients is a natural idea. From the theoretical results, DoWG seems a rather incremental advance over DoG. The resulting algorithm is probably not going to have any impact on the optimization method in deep learning.
Questions
Could the rate obtained in the analysis of NGD be improved? - line 131: gives eta so that - line 554: Therefore.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
3 good
Contribution
2 fair
Limitations
do no apply.
Summary
The paper presents a modification to the recently proposed DoG algorithm to obtain a adaptive algorithm for the deterministic, convex and [Lipschitz or Smooth] setting that does not need any hyperparameter to achieve a convergence rate competitive with algorithms that know the problem-specific constants. The submission discusses the benefits of normalization, linking its behavior to the edge of stability phenomenon and providing an analysis that normalized gradient descent obtains the convergence of GD on smooth function with step-size 1/L without needing to know the smoothness constant.
Strengths
The submission is well presented and I could understand the main objective of the paper at first read. The DoWG algorithm, and especially its proof, is simpler than the one found the prior work of Ivgi et al. (2023) on DoG, and would be an easier starting point for readers trying to understand algorithms that can adapt to the initial distance to the optimum.
Weaknesses
Beyond the DoWG algorithm, the contributions are also already known in the literature. To the credit of the submission, this is clearly mentioned for the observation that normalized gradient descent on smooth functions leads to a similar behavior to the edge of stability phenomenon (Arora et al., 2022). However, the result that normalized gradient descent obtains the smooth rate can be found in the work of Levy (2017), which seems to have been missed. The submission also suffers from a lack of formalism on some of its claims. Some concepts such as weak and strong adaptivity, “adapting to geometry” and what is meant by the edge of stability are left vague, and would benefit from a formal definition and nuanced discussion. If those issues, detailed in the question section, are addressed in a revision, I will increase my score to 6.
Questions
**Prior work** I found the discussion of the adaptivity to smoothness of normalized GD and the key inequalities (5—7) useful to understand how DoWG achieves a similar result. However, the paragraph prior to Theorem 4 should cite Levy (2017). Their analysis of what they call the AdaNGDk algorithm (an overly general form that recovers normalized gradient descent with a decreasing step-size of the order $1/\sqrt{t}$ for k=1), in Theorem 2.1 is the equivalent of theorem 4 in the current submission, except with a decreasing step-size of $1/\sqrt{t}$ rather than the constant but horizon-dependent step-size $1/\sqrt{T}$ used here. Kfir Levy, “Online to Offline Conversions, Universality and Adaptive Minibatch Sizes”, NeurIPS 2017 --- **Formal definition for some concepts** **Strong vs. Weak Adaptivity** The working definitions of “weak” and “strong” adaptivity are not clear from the current writing, or seems to lead to undesirable conclusions. I find the separation useful, and being able to formalize how sub-optimal the “adaptivity” of AdaGrad-Norm is in the smooth setting would be helpful. However, the definition of weakly adaptive requires that “[weak-adaptivity] just seeks non-divergence given stepsize misspecification. […] the algorithm’s objective is to ensure that the learning process does not result in divergence, even if the chosen stepsize is not optimal” (L145). This definition is problematic because an algorithm that does not move, or gradient descent with a step-size of 0, satisfies the above definition. Similarly, for strongly adaptive, the text requires that “an algorithm [is strongly adaptive if] it preserves the convergence rate of optimally tuned gradient descent without any manual tuning.” The proposed DoWG algorithm does not fit this description as the rate worse, if only by a log-factor. A formalization of the above that could work would be to say that an algorithm is strongly adaptive in a problem setting if it achieves the same convergence rate, up to polylogarithmic terms, as an algorithm that knows problem specific constants. Weakly-adaptive could similarly be defined by allowing for multiplicative polynomial factors. **Adapting to geometry** The term “adapting to geometry” is used in multiple places, but it isn’t clear what is meant by that statement. This term is often used in the literature as a way to convey the intuition of why a method is good, but with limited formalism. For example, Newton adapts to the geometry of the problem by using the Hessian, or AdaGrad adapts to the geometry of the problem by finding a preconditioner that is competitive with the optimal one in hindsight. On each usage of “adapting to geometry”, I do not understand what is meant,. I strongly suggest avoiding it and using a more direct description instead. - L32: “We say an algorithm is universal if it adapts to many different problem geometries or regularity conditions on the function f” (should be removed and only mention regularity condition) - L56: “In particular, such adaptive methods empirically show the ability to adapt to the local geometry of the problem (Cohen et al., 2022), especially compared to plain (stochastic) gradient descent (Pan and Li, 2022).” L107: “There are other justifications for why adaptive methods work outside of adapting to geometry.” - L246 “Therefore, we may may expect this to aid the method in adapting to the geometry of the problem once far away from the initialization x0.” --- **A mention of the difficulties of obtaining similar results in online learning would be helpful to the reader.** While the online-learning algorithms of Streeter and McMahan (2012), Orabona et Pal (2016) and Orabona and Cutkosky (2020) aim for a similar goal of not having to know the diameter of the set and the Lipschitz constant, the rates presented for the current algorithm or those in the prior works of of Ivgi et al. (2023) and Carmon and Hinder (2022) are not achievable in the adversarial that is common in online learning, see Cutkosky and Boahen (2016, 2017). Ashok Cutkosky, Kwabena Boahen, “Online Convex Optimization with Unconstrained Domains and Losses”, NeurIPS 2016 Ashok Cutkosky, Kwabena Boahen, “Online Learning Without Prior Information”, COLT 2017 --- **Question on Universality and the edge of stability** The convergence of normalized GD or DoWG are not discussed under strong-convexity, which I think should be mentioned given the focus on universal algorithms. Especially as some alternative algorithms such as the Polyak step-size do benefit from strong-convexity, whether in the smooth or Lipschitz+bounded set case. Given that the empirical results shown in Figure 2 are on a strongly convex problem and the effective step-size oscillates around a constant 2/L, I am interpreting it as the algorithm *not* achieving a linear rate (as the gradient norm should also go down as a linear rate, which does not seem to be the case if $\eta/\Vert\nabla f(x_t)\Vert$ is constant)? --- **typo?** - L80: "Orvieto et al. (2022) show that a variant of the Polyak stepsize with decreasing stepsizes can recover the convergence rate of gradient descent in the deterministic setting, provided the stepsize is initialized properly" -- this should be stochastic?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
2 fair
Limitations
Yes
Summary
This paper considers the problem of optimizing a convex function over a convex, closed, and possibly compact set $\mathcal{X}$. In particular, they are interested in finding a first-order method which is (i) universal (i.e., the same algorithm can be used when the objective is Lipschitz or smooth), (ii) parameter-free (i.e., converges without any hyperparameter tuning w.r.t. problem parameters) (iii) has no search subroutines, and (iv) strongly-adaptive (i.e., preserves the convergence rate of an optimally-tuned GD without tuning). The authors propose an algorithm, Distance-over-Weighted-Gradients, which (essentially) achieves all of these desired properties. The two caveats are (i) the convergence rates have an extra log factor not present in optimally-tuned GD, and (ii) the convergence rates depend on the diameter of the constraint set $\mathcal{X}$ instead of on $D_0 = || x_0 - x^* ||$. Towards establishing this result, the authors prove that normalized GD universal but not parameter-free.
Strengths
This paper provides an algorithm with the remarkable properties of being universal, parameter-free, (nearly) strongly-adaptive, and not requiring a search subroutine. Unless I have misunderstood, this seems to be the first such algorithm satisfying all of these properties simultaneously. Moreover, the analysis is well-written and easy to follow. I also found the discussion of the universal properties of normalized GD to be quite instructive and interesting. Overall, I think this is a very nice paper.
Weaknesses
Much of the analysis appears to rely on or extend arguments from Ivgi et al., (2023). Further, the results in this paper are restricted to the deterministic setting, while the results of Ivgi et al. hold also in the noisy setting (albeit, assuming uniformly bounded stochastic gradients, and thus the results are restricted to the Lipschitz setting). Despite this, I still think the results in this paper are quite nice.
Questions
The results of Ivgi et al. (2023) hold also in the stochastic setting (assuming stochastic gradients are uniformly-bounded). What are the main barriers to extending your results to the stochastic setting? Is there any similar result that you can obtain when, e.g., the noise of stochastic gradients is uniformly bounded? It might be beneficial to the paper to add a discussion on why extending to this setting is difficult. In the introduction of your paper, you mention that the constraint set $\mathcal{X}$ is “(potentially) compact“, However, your main results (Theorems 5 and 6) assume that the diameter $D$ of $\mathcal{X}$ is finite (but unknown). Is it possible to extend these results to the unconstrainted case where $\mathcal{X} = \mathbb{R}^d$?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed 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.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
N/A
Summary
This paper introduces a new algorithm for optimization problems. The paper introduces DoWG (Distance over Weighted Gradient) which is a simple extension of a previous work DOG (Distance over gradient). It is a parameter-free gradient optimization method where the step size is automatically adjusted to the function being optimized over the course of the optimization. This works also provides justification of why DoWG produces close to the optimal convergence that can be achieved by Normalized Gradient Descent (NGD) for either Lipschitz or smooth functions. As part of this claim the authors also show a new derivation of the optimal convergence for NGD on smooth functions. Finally the authors show results on training Deep Nets for vision and these demonstrate the while DoWG performs better than other parameter-free methods it doesn't attain the level of accuracy achieved by momentum-based methods such as ADAM.
Strengths
## Defining Universality The authors have very systematically defined their concept of a Universal Gradient Descent-based optimization algorithm. In fact as part of this definition of Universality they have computed the optimal convergence rate of NGD for smooth functions which appears to be a new result although it is not a very surprising result. ## Discussions of NGD The paper provides some very strong intuition about how NGD is self-stabilizing. The discussion and example in the paper provides good insight about how parameter-free methods work in general.
Weaknesses
## Comparison to DOG The proposed algorithm itself is only slightly different than the existing DOG algorithm and the intuition of why it was proposed is not that clear. The paper mentions that DoWG gives higher weight to later gradients, but why is this important? They do also demonstrate on line 263 that DoWG step sizes could be larger than DOG's and this seems reasonable, but overall the motivation for the improvement is not clear. Now the paper does show that DoWG has optimal NGD convergence for Lipschitz functions, but it points out that the same holds for DOG. There is no discussion of whether optimal NGD convergence that is proven for smooth functions with DoWG also holds for DOG or not. If the authors could prove that DOG *doesn't* have optimal NGD convergence for smooth functions then their claim that DoWG is the first parameter-free Universal gradient descent algorithm without a search subroutine would be overall stronger. ## Performance Relative to ADAM The authors should certainly be lauded for including a superior baseline result. However, the fact that ADAM does so much better than DoWG makes their work more of a theoretical curiosity. It appears that the authors hurried through the final evaluation and included very limited results. The previous work that introduced DOG had results showing both fine-tuning as well as training a model from scratch. I would encourage the authors of the current work to do something similar as well as introduce variants such as L-DOWG.
Questions
- Does DOG have optimal NGD convergence for smooth functions? Have the authors found a reason why this is not the case or why this would be unlikely and could provide a justification? - Have the authors considered L-DOWG (layer-wise DOWG similar to L-DOG)? - The DOG paper (https://arxiv.org/pdf/2302.12022.pdf) in Table 2 page 14 show results for DOG that are superior than ADAM for training a model from scratch. Why could the authors not reproduce those results as a baseline?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
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.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Not applicable.
Summary
The paper proposes a new algorithm, DoWG, which modifies DoG (Ivgi et al., 2023) by utilizing the weighted sum instead of the usual sum for the squared gradients. Convergence is established for convex and convex & smooth deterministic settings, under the assumption of a (possibly unknown) bounded domain. The method is adaptive to the Lipschitz/smoothness constant and is parameter-free in the sense that the bound of the domain may be unknown. Experiments comparing DoWG to several adaptive methods are presented. Additionally, a complementary result for convex & smooth NGD establish that NGD is weakly adaptive to the diameter of the problem.
Strengths
1. The modification from DoG to DoWG is appealing as it results in larger stepsizes, potentially leading to faster convergence. 2. A (limited) set of experiments is provided, demonstrating positive empirical evidence for the effectiveness of the DoWG method.
Weaknesses
3. It is important to highlight that the convergence of DoWG is established exclusively in the deterministic setting, making it weaker than DoG's convergence, which extends to both deterministic and stochastic settings (note that AdaGrad-Norm results also apply to the stochastic setting). The paper should explicitly emphasize this difference and consider exploring DoWG's performance in the stochastic setting. 4. The theoretical results for DoWG hold significance when dealing with unknown domain bounds. When the domain bound is known, AdaGrad-Norm with stepsizes $\eta_t=D/\sqrt{\sum_t \lVert \nabla f(w_t) \rVert^2}$ has tighter bounds for both convex and convex & smooth settings. 5. The term "parameter-free method" typically used for rates that depends on the distance to the comparator or the minimizer. In this context the convergence of DoWG is not truly parameter-free as it is relevant only for bounded domains and does not improve with a good initialization.
Questions
6. Can DoWG achieve similar convergence results to DoG in the stochastic setting? If it is yet established, what is the additional difficulty with respect to DoG? 7. In the deterministic setting, would DoG achieve similar convergence results to DoGW, or was the modification to DoWG necessary to address specific issues in that setting? 8. What is the motivation for the problem of deterministic optimization with unknown bounded domain? Corollary 1 of Ivgi et al. (2023) mentions two-stage stochastic programming as an application, but is the deterministic counterpart of interest as well? Overall, while DoWG shows promise and may yield novel convergence properties, I find the current established guarantees to be partly insufficient compared to previous work on adaptive and parameter-free methods. Edit: Per the authors response regarding the unbounded case with adaptivity to $D_0$ and the improved log factor with respect to the smooth result of DoG (unknown at the time of submission), i raise my score.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
N/A
Summary
The paper proposes a new optimization algorithm, DOWG, that does not rely on additional hyperparameter tuning or a line search subroutine. Interestingly, the paper also contains a proof and analysis regarding the behavior of NGD and shows that (1) NGD adapts to the smoothness of continuous loss surfaces and (2) NGD operates at the edge of the maximum stable learning rate for continuous loss functions. Finally, the paper presents two empirical studies on CIFAR10 with two different neural networks.
Strengths
I am not an expert in optimization, but I thoroughly enjoyed reading this paper. The writing is clearly organized and accessible to readers with only some rudimentary knowledge of optimization. Regarding related work, the paper carefully assigns credit to existing work and precisely describes how the current work stands out at each step along the way, which demonstrates a high level of expertise in the field. The theoretical contribution seems solid, and the new algorithm seems to be well motivated and work well, when compared with other parameter-free algorithms. I strongly recommend this paper be accepted.
Weaknesses
DOWG does not work as well as Adam with cosine annealing on both neural network problems. However, this is not very surprising because cosine annealing is extremely strong. I do not consider this to be a fatal issue.
Questions
Nil
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
Nil
I thank the authors for their elaborate comment. 1. I strongly suggest to include the result that depends only on $D_0$, including a discussion of the result in the main body. Calling the method "parameter-free" without adaptivity to the distance form the minimizer (comparator in online learning) might be misleading. 2. The same goes for support for unbounded domains. It is fine to have a theoretical method and an "in-practice" small modification of the method. Those two guarantees makes the theoretical setting much less restricted. 3. Did the authors considered a version that use the Lipschitz parameter for the stochastic setting? Will this modification solve the stochastic setting? A common distinction is that a method is parameter-free if it is adaptive to the distance from the minimizer (or comparator, i.e., in parameter-space), and scale-free if no knowledge of the Lipschitz constant is needed (e.g. [1,2]). [1] Orabona, Francesco, and Dávid Pál. "Open problem: Parameter-free and scale-free online algorithms." Conference on Learning Theory. PMLR, 2016. [2] Orabona, Francesco, and Dávid Pál. "Scale-free online learning." Theoretical Computer Science 716 (2018): 50-69.
Thank you for your quick response. 1. (On proof with $D_0$ and unbounded domains). We shall include the result on the variant of DoWG with dependence on the initial distance $D_0$ in the final paper. The result is not very difficult to derive, and we include the main lemma here for completeness. The main idea is that by dividing the stepsize by a running logarithmic factor, we can prove the iterates stay bounded by a constant multiplied by the initial distance $d_0$. Then we can just apply the ordinary DoWG proof (at the cost of an additional logarithmic factor only). The proof follows follows [1]. Lemma 1 (Stability). Suppose that $r_0 \leq d_0$. Then the iterates of DoWG with stepsizes $\eta_t = \frac{\bar{r}_t^2}{2 \sqrt{v_t}} \frac{1}{\log \frac{2v_t}{v_0}}$ satisfy $\bar{d}_t \leq 16 d_0$ and $\bar{r}_t \leq 16 d_0$ for all $t$. Proof. We have by convexity $$ d_{k+1}^2 - d_k^2 \leq \eta_k^2 |{g_k}|^2 $$ Summing up from $k=1$ to $k=t$ we get by [1, Lemma 6] $$ d_t^2 - d_1^2 \leq \sum_{k=1}^{t} \eta_k^2 |{g_k}|^2 = \sum_{k=1}^{t} \frac{ {\bar{r}\_k}^4 }{v_{k-1}} \frac{|{g_k}|^2}{4 \log^2 \left( \frac{2v_{k-1}}{v_0} \right)} \leq \frac{\bar{r}\_t^2}{4} \sum{k=1}^{t-1} \frac{v_k - v_{k-1}}{v_{k-1} \log_+^2 \left( \frac{v_{k-1}}{v_0} \right)} \leq \frac{1}{4} \bar{r}\_t^2 $$ Thus we have $d_{t+1}^2 \le d_1^2 + \frac{\bar{r}t^2}{4}$. Now suppose in the way of induction that $\bar{r}\_t^2 \leq 8 d_1^2$, then applying the last equation we get $d\_{t+1}^2 \leq d_1^2 + \frac{8}{4} d_1^2 = 3 d_1^2$. Taking square roots gives $d{t+1} \leq \sqrt{3} d_1$. Subsequently, by the triangle inequality we have $$ |{x_{t+1} - x_1}| \leq |{x_{t+1} - x_{}}| + |{x_{} - x_1}| \leq \left[ \sqrt{3} + 1 \right] d_1 $$ Squaring both sides gives $|{x_{t+1} - x_1}|^2 \leq \left( \sqrt{3}+1 \right)^2 d_1^2 \leq 8 d_1^2$. It follows that $\bar{r}\_{t+1}^2 \leq 8 d_1^2$, and the induction thus gives us $\bar{r}_t^2 \leq 8 d_1^2$ for all $t$. Next, observe that $$ d_1 = |{x_1 - x_{}}| \leq |{x_0 - x_1}| + |{x_0 - x_{}}| = r_0 + d_0 \leq 2 d_0 $$ It follows that $\bar{r}\_t \leq 16 d_0$ for all $t$. Finally, observe that the same analysis implies $d_t \leq 16 d_0$ for all $t$. Therefore, we get that the iterates stay in a bounded domain, and with a small modification of the main proof, we get the same result as the original paper, with $D$ replaced by $16 D_0$ and an additional log factor. We shall include the result in full in the final paper. 2. If we do have knowledge of the Lipschitz parameter (or the Lipschitz smoothness parameter in the smooth case) then we can do the stochastic case. We did not consider this for long because the algorithm is then no-longer parameter free. In the online learning setting, it is not possible to do away with knowledge of the Lipschitz parameter in the worse case, as the lower bound of Cutkosky and Boahen (2016) shows. This may not be the case for offline stochastic convex optimization. References: [1] Ivgi et al., DoG is SGD's best friend, 2023.
I thank the authors for their response. Per the authors response regarding the unbounded case with adaptivity to $D_0$ and the improved log factor with respect to the smooth result of DoG (unknown at the time of submission), i raise my score.
Thanks
Thanks for the detailed response. My main concerns have been addressed. > The application of the restarting scheme of [3] to NGD/DoWG is straightforward, and we will include it in the appendix. The authors are welcome to include it, but I don't think the restart scheme extension is necessary. Mentioning that "universality" often includes the strongly-convex case, but does not apply to normalized GD (and would require an extension) should be sufficient. --- (Minor point; please prioritize other responses) Could you clarify the following? > On strong convexity: Indeed, due to the fact that NGD forces the effective stepsize to be 1/L, NGD does not adapt to strong convexity out of the box if we use a constant stepsize. Therefore a linear rate is not possible. If the effective step-size $\eta/\Vert\nabla f\Vert$ was forced to be 1/L, wouldn't the algorithm reduce to GD with step-size 1/L and get linear convergence?
Thank you for following up with us. We are happy that your main concerns have been addressed. 1. (On universality) We will add that universality includes the strongly-convex case but doesn't apply to NGD. We agree it is important to point that out. 2. (On NGD) Because the effective stepsize stabilizes, this means that we cannot get much better than $\| \nabla f \| \approxeq \eta L$. What we observe (Figure 2 in the paper) is that when the gradient norms just keep oscillating. That is, the algorithm does a step that decreases the gradient norm, which results at the next step in a much larger effective stepsize, this in turn is too large (larger than the threshold $2/L$) and causes divergence, which forces the effective stepsize at the next iteration to be smaller, and so on. In this way, the effective stepsize oscillates around $2/L$, while at the same time not enabling linear convergence.
Thanks. I've read the response and have nothing further to add.
Thanks
Thank you for your response. I've read the discussion with the other reviewers, and will maintain my original score. In the next revision of the paper, I would recommend that the authors include their results on rates which depend only on $D_0$, as I agree with Reviewer WSp1 that these results are interesting (even if practical performance is not as good as the other step-size).
no major change based on response
Thanks for the response. - For 4. It would help to list exactly where in the main text or supplementary material you have results showing better accuracy than Adam for Imagenet or CIFAR. (As shown in the DoG paper with polynomial decay averaging).
The experiments in our paper do not show superiority of either DoG/DoWG over Adam because we do not use polynomial decay averaging. What we meant to say is that we reproduce that vanilla DoG (without polynomial decay averaging) is worse than Adam.
Could the authors be very precise. Did they ever run an experiment with polynomial decay averaging as was done in the DoG paper in their current work. How did the results compare to Adam? If they didn't run this experiment, why not?
No, we did not run any experiments that included polynomial decay averaging. We used the vanilla DoWG/DoG for comparison against Adam. Using polynomial decay averaging requires passing a $\gamma$ parameter for the averaging, and we wanted to evaluate DoWG/DoG as parameter-free methods against Adam. We can do experiments that include polynomial decay averaging if they would be more instructive.
Repeating the prior experiment with polynomial decay averaging would be instructive to the extent that it would assure us that there is at least one scenario in which the new work does better than Adam. Also, if a paper builds very closely on top of a prior work it is expected (but not required) to repeat all the experiments in that prior work.
Decision
Accept (poster)