Towards Simple and Provable Parameter-Free Adaptive Gradient Methods

Authors: Yuanzhe Tao, Huizhuo Yuan, Xun Zhou, Yuan Cao, Quanquan Gu
Primary area: optimization
Keywords: parameter-free optimization, adaptive gradient methods

Abstract:
Optimization algorithms such as AdaGrad and Adam have significantly advanced the training of deep models by dynamically adjusting the learning rate during the optimization process. However, adhoc tuning of learning rates poses a challenge, leading to inefficiencies in practice. To address this issue, recent research has focused on developing "learning-rate-free" or "parameter-free" algorithms that operate effectively without the need for learning rate tuning. This paper presents AdaGrad++ and Adam++, novel parameter-free variants of AdaGrad and Adam with convergence guarantees. We prove that AdaGrad++ achieves comparable convergence rates to AdaGrad in convex optimization without predefined learning rate assumptions. Similarly, Adam++ matches the convergence rate of Adam without relying on any conditions on the learning rates. Experimental results across various deep learning tasks validate the competitive performance of AdaGrad++ and Adam++

Decision: reject
Reviewer scores: 3, 3, 6

Reviews and discussion:
<thread>
creation date:
1729010668852

thread_type:
official_review

<thread_object>
creator: reviewer_c1yw

<content>
summary:
The authors extend the idea of the DoG framework to Adam and AdaGrad to create parameter-free optimizers with adaptive learning rates. They also propose theorems for the convergence guarantees of their methods.

strengths:
The paper is well-written, clear, and easy to follow. The authors extend the idea of the DoG framework to Adam and AdaGrad. They also propose theorems for the convergence guarantees of their methods; however, the math was not carefully checked by the reviewer.

weaknesses:
-    The novel update rule of the learning rate requires storing in memory the original weights of the model, in addition to the weights of the current model and the first and second moments (in Adam’s case). This results in a memory overhead, approximately 33% larger than that of Adam. Furthermore, the update rules require the computation of an additional L2 norm, which can slowdown wallclock time for larger models. These memory and computational overheads are never mentioned or measured explicitly.

-    When comparing optimizers, wall-clock time is important; however, the paper does not mention how the proposed method compares with others in terms of computational time.

-    The minimal performance gains may not justify the added memory and computational overheads.

-    The plotted figures are so small that it is difficult to discern the details.

-    AdaGrad++ is introduced, but the authors state that it underperforms Adam and it is never actually plotted or shown in image classification or language modeling tasks. This raises the question of why it is included in the paper. A comparison with the standard AdaGrad version would have been appropriate since it was introduced.

-    Sophia is mentioned yet never compared against; the authors even state that they use NanoGPT from Sophia’s codebase, which is concerning. In fact, looking at Sophia’s results, it seems to the reviewer that it outperforms Adam++ on the GPT-2 language modeling tasks at 50K steps.

-    In image classification, standard Adam achieves the highest test accuracy in most cases.

-    CIFAR-10 is arguably an outdated task for image classification. It would be beneficial to test at least CIFAR-100, Tiny-ImageNet, and possibly full ImageNet. Additionally, testing transformer-based backbones like the ViT would be more appropriate than VGG16.

questions:
-    What are the memory and computational overhead required for AdaGrad++ and Adam++? 
-    How does Adam++ compare in wall-clock time with respect to classic Adam?
-    CIFAR-10 is a small dataset for today's standard, how does Adam++ perform on larger image classification datasets and on ViT backbones?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729132231662

thread_type:
official_review

<thread_object>
creator: reviewer_c9og

<content>
summary:
This paper proposes a learning-rate-tuning-free method. Compared with the previous method DoG [1], this work introduces the parameter dimension $d$ into the Learning Rate (LR) and proposes AdaGrad++ and Adam++ by incorporating the new formula of LR into vanilla AdaGrad and Adam. 

Besides, following the previous settings and proof framework of DoG, this work provides the convergence guarantee of the proposed methods, specifically, Theorem 4.2 and Theorem 5.2, under strong assumptions, i.e.,  convex, bounded stochastic gradient.  Regarding the evaluation, this work conducted image classification tasks - ResNet18, ResNet50, and VGG16 under CIFAR10 dataset, and language tasks - GPT-2 under OpenWebText dataset.

[1] Ivgi, Maor, Oliver Hinder, and Yair Carmon. "Dog is sgd’s best friend: A parameter-free dynamic step size schedule." International Conference on Machine Learning. PMLR, 2023.

strengths:
The parameter-free methods have gained attention recently.  Achieving optimal convergence guarantees without the knowledge of specific problem-dependent properties is beneficial theoretically and practically.  And this paper tries to tackle this challenge practically and shows some evidence.

weaknesses:
$\textbf{Weakness in techniques:}$

(1) Both Corollary 4.4 and Corollary 5.2 (and Theorem 4.2 and Theorem 5.1) state that the number of iterations requires $T \propto \mathcal{O}(d)$ to converge, where $d$ is the parameter dimension. Thus, this result is less useful or enlightening to demonstrate the practical performance of the proposed method since the $T<<d$ in practical practice. Besides, $T$ is independent of $d$ in previous work such as Corollary 1 of [1] and Theorem 1 of [2].

(2) Corollary 4.4 and Corollary 5.2 state similar convergence rates for AdaGrad++ and Adam++. However, as mentioned by the author “AdaGrad++ as we found it consistently underperforms compared to Adam and Adam++”.

(3) The first discrepancy between theorem proof and practical algorithm. Theorem 5.1 (Corollary 5.2) requires $\lambda \in (0,1)$, which actually disables the momentum update of Adam very quickly, seeing line-6 and line-7. However, I believe the success of Adam and the proposed method in fact counts on the momentum update, as mentioned by the Author that “Adam++ with $\lambda$ = 1 can achieve highly competitive performance under various practical settings”.

(4) The second discrepancy between theorem proof and practical algorithm. “Case 2” operation in Algorithm 2 requires the max operation over $v_{t}$ to comfort the convergence proof, however, the practical algorithm needs to eliminate it, as mentioned by the author “experiments have demonstrated that the simplified version $s_{t} = \sqrt{ (t + 1)  v_{t}}$ works better in practice”.

Overall, the technical proofs and results are less connected with the practical performance.

$\textbf{Weakness in evaluation:}$

(1) Considering a parameter-free (or learning-rate-free) optimizer, it is expected to perform well on a spectrum of optimization tasks across different datasets, network architectures, and training parameters such as batch size, number of epochs, etc.  I recognize that it is hard to comprehensively verify the method and lacks a uniform criterion of comparison. But universal adaptivity matters for LR-tuning-free methods.

However, the conducted experiments in this work are insufficient to demonstrate the adaptivity compared with previous work. For example, in terms of the image classification tasks, Table 5 of [1] employed 5 diverse network architectures and 12 different datasets, while this work employed 2 diverse network architectures (ResNet* and VGG) and 1 dataset. Same for the language tasks, seeing Table 4 of [1]. The small-scale experiment cannot support the adaptivity of the proposed methods.

(2) I believe a golden choice of training settings is: Adam+LR(1e-3)+Cosine LR decay, which could be used as the baseline instead of a constant learning rate, since decreasing LR w.r.t. Iterations is well supported by many theoretical results. Table 1 in this paper demonstrates that the default choice of training method, Adam+LR(1e-3)+Cosine LR decay, outperforms the proposed methods.


$\textbf{Weakness in method novelty or enlightenment:}$
	
(1) The main modification compared with the previous method is introducing $\sqrt{d}$ into the learning rate, however, this modification is not well supported intuitively or theoretically. 


[1] Ivgi, Maor, Oliver Hinder, and Yair Carmon. "Dog is sgd’s best friend: A parameter-free dynamic step size schedule." International Conference on Machine Learning. PMLR, 2023.

[2] Mishchenko, Konstantin, and Aaron Defazio. "Prodigy: An expeditiously adaptive parameter-free learner." arXiv preprint arXiv:2306.06101 (2023).

questions:
(1) how to explain $T\propto d$? and how to connect the theoretical results with the performance improvements?

(2) Regarding the image classification task, Adam++ is employed, however, AdamW++ (Case 2) is employed for language tasks. Do you have any particular reasons for the switching&tuning operations?  I also noticed two missing settings, i.e., AdamW++ (Case 1) and constant learning rate, in language tasks.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730513957092

thread_type:
official_review

<thread_object>
creator: reviewer_fulj

<content>
summary:
This paper proposes two simple parameter-free variants of AdaGrad and Adam, called AdaGrad++ and Adam++. The authors also prove that the proposed algorithms including AdaGrad++ and Adam++ can achieve comparable convergence rates to their counterparts, AdaGrad and Adam. Some experimental results are reported.

strengths:
The paper is complete in format.

weaknesses:
As shown in Algorithm 1, the main differences between AdaGrad++ and Adam are from (Ivgi et al., 2023). Therefore, the novelty of this paper is limited. The experimental results are not convincing. The comparisons with recent algorithms are missing.

questions:
1.	What’s the difference between the parameter-free techniques used in the proposed algorithm and existing ones?
2.	The detailed discussions about the convergence rates of the proposed algorithms and recently proposed algorithms are missing.
3.	The authors should compare the proposed algorithms with more recently proposed algorithms.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732559831233

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Major Additional Experiments

comment:
Dear Reviewers, 

Thank you for your helpful and constructive comments. To address your comments, we have added a number of additional experiment results. Here, we would like to give a summary of the experiment results we have added in the revision. In the additional experiments, we have compared different algorithms (Adam, D-Adapt Adam, Prodigy, Adam++(Case 1), Adam++ (Case 2), AdaGrad, and AdaGrad++) in training various network architectures (DenseNet-121, Vision Transformer, and Wide ResNet-50-2) on various datasets (CIFAR-10, CIFAR-100, and SVHN).

The following two tables compare the best accuracy (%) of different algorithms in 100 and 200 epochs on the CIFAR-10 dataset respectively:

|CIFAR-10, best accuracy in 100 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam  | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121     | 86.9  | 67.07        | 72.47   | 87.1           | **87.87**       | 65.8    | 86.32     |
| Vision Transformer       | 76.0  | 73.7         | 70.0    | **80.14**      | 78.76           | 65.13   | 76.53     |
| Wide ResNet-50-2 | 87.02 | 77.32        | 79.64   | 76.27          | **87.17**       | 63.91   | 75.12     |


|CIFAR-10, best accuracy in 200 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam      | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121     | 89.2      | 77.22        | 79.66   | **89.59**      | 89.07    | 66.39   | 89.58     |
| Vision Transformer     | 78.74     | 75.78        | 73.55   | **81.66**      | 80.09     | 66.49   | 79.4      |
| Wide ResNet-50-2 | **89.34** | 85.51        | 85.08   | 78.42    | 88.86     | 64.54   | 77.92     |

The two tables below present a comparison of the best accuracy (%) achieved by different algorithms in 100 and 200 epochs on the CIFAR-100 dataset:

|CIFAR-100, best accuracy in 100 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam      | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121     | 60.51     | 31.4         | 47.38   | 60.83  | **61.54**       | 36.86   | 59.49     |
| Vision Transformer    | 49.22     | 47.92        | 46.39   | **52.78**      | 51.41           | 23.99   | 50.34     |
| Wide ResNet-50-2 | **60.94** | 39.05        | 54.24   | 43.28          | 57.24           | 35.22   | 42.07     |

|CIFAR-100, best accuracy in 200 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam      | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121     | 63.05     | 43.44        | 54.25   | **64.05**      | 62.9            | 37.56   | 63.75     |
| Vision Transformer   | 52.91     | 51.78        | 50.6    | **55.68**      | 53.58           | 25.2    | 53.32     |
| Wide ResNet-50-2 | **64.33** | 51.97        | 59.25   | 46.5           | 61.11           | 35.38   | 45.76     |

Finally, shown in the following tables is a comparison of the best accuracy (%) attained by different algorithms in 100 and 200 epochs on the SVHN dataset:

|SVHN, best accuracy in 100 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam      | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121     | **95.45** | 79.01        | 88.15   | 95.41   | 95.32    | 79.27   | 94.83     |
| Vision Transformer  | 77.17     | 19.59        | 64.23   | **88.93**  | 35.09     | 70.36   | 85.69     |
| Wide ResNet-50-2 | 95.21     | 87.64        | 93.66   | 93.01    | **95.57**  | 87.07   | 95.20     |

|SVHN, best accuracy in 200 epochs | | | | | | | |
| --------------- | --------- | ------------ | ------- | -------------- | --------------- | ------- | --------- |
| Models          | Adam      | D-Adapt Adam | Prodigy | Adam++(Case 1) | Adam++ (Case 2) | AdaGrad | AdaGrad++ |
| DenseNet-121    | 95.51     | 89.46        | 92.94   | 95.53          | 95.34           | 80.35   | **95.73** |
| Vision Transformer  | 82.34     | 19.59        | 76.11   | **90.07**      | 44.06           | 73.36   | 87.84     |
| Wide ResNet-50-2 | **95.75** | 93.71        | 95.16   | 93.63          | 95.63           | 87.59   | 95.59     |

We believe these additional results can fully address your (Reviewers C9og and c1YW) initial concerns about the insufficient experiments. If you have any further questions, please let us know and we will try our best to address them. Thank you!

Best regards,

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces two parameter-free optimizers as variants of AdaGrad and Adam. The proposed methods aim to simplify hyperparameter tuning while maintaining theoretical guarantees and practical performance. While the theoretical contributions were acknowledged, reviewers raised concerns about practical relevance, novelty, experimental results, and computational overhead.

### **Strengths:**
- AdaGrad++ and Adam++ achieve convergence guarantees comparable to their classic counterparts under convex assumptions.
- General direction is of interest: parameter-free optimizers reduce the need for hyperparameter tuning
- During the rebuttal, the authors significantly expanded experiments, including new datasets (CIFAR-100, SVHN) and architectures (Vision Transformers, Wide ResNet, DenseNet).


### **Weaknesses:**
- Limited novelty: the core ideas are closely tied to the DoG framework, with limited innovation in the update rules for AdaGrad++ and Adam++. Some reviewers questioned whether the modifications were intuitive or theoretically necessary.
- Practical algorithms diverge slightly from their theoretical versions (e.g., the max operation and adjusting momentum parameters).
- Initial experiments lacked breadth, focusing on small-scale datasets like CIFAR-10 and limited architectures like ResNet and VGG. This was however addressed to a large extent.

While the paper has merits in providing parameter-free adaptive gradient methods, the mixed reviews highlight concerns about its contribution compared to prior work. I do want to acknowledge the lack of discussion from some reviewers (despite my best attempts) but the paper is overall significantly below the acceptance bar so I do think another round of reviews is necessary. I am unfortunately not able to recommend acceptance at the moment but I do encourage the authors to improve the paper to resubmit to a later deadline.