Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad

Summary

This paper presents a novel algorithm, KATE, which demonstrates impressive scale-invariance properties for Generalized Linear Models.

Strengths

This paper presents a novel algorithm, KATE, which demonstrates impressive scale-invariance properties for Generalized Linear Models. The thorough theoretical analysis provided in the paper, along with the experimental results, showcases the effectiveness of KATE in various machine learning tasks. The comparison with existing algorithms like AdaGrad and Adam highlights the superior performance of KATE in terms of convergence rate and efficiency.

Weaknesses

While the paper excels in presenting the theoretical foundations and empirical results of the KATE algorithm, there are a few areas that could be further strengthened. Firstly, the paper could benefit from a more detailed discussion on the limitations of the proposed algorithm, especially in scenarios where certain assumptions may not hold. Additionally, providing insights into the computational efficiency and scalability of KATE with larger datasets could enhance the practical applicability of the algorithm.

Questions

1 How does the scale-invariance property of KATE impact its performance in real-world applications compared to traditional adaptive algorithms? 2 Can the authors elaborate on the computational complexity of KATE and how it scales with the size of the dataset? 3 Are there any specific scenarios or types of machine learning tasks where KATE may not perform as effectively, and if so, how does the algorithm address these limitations?

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

N/A

Summary

This work proposes an optimizer that achieves the optimal convergence guarantee for smooth nonconvex settings and more importantly the scale-invariance property.

Strengths

The paper is very cleanly written. It was very easy to follow. The main results look sound, and the experimental results are well presented as well.

Weaknesses

Overall, the paper presents the main scope and the results very well. In other words, I do not have much concern for this paper by itself. My only concern is the importance of the problem it tackles. Scale-invariance is definitely a desirable property, but I'm not sure what advances it brings about for the ML optimization. What I mean is, in general, the important question in the community is whether one can design an optimizer that has a noticeable advantage over the previous popular ones. I'm not sure whether resolving scale-invariance will drastically improve our current technology for optimizing ML models. The experiments presented in this paper doesn't seem to justify this in a compelling way. (I think results are convex models have limited practical impact.)

Questions

- I think since a lot of baselines this paper considers is originally designed for online convex optimization, it is important to also do an extensive analysis of KATE for the corresponding OCO settings and compare. In particular, some regret analysis as well as the convergence analysis for nonsmooth convex setting might be helpful. - The main motivation this paper argues for the need of scale-invariance under the data scaling is that previous approaches could be brittle when data has poor-scaling or ill-conditioning. In order to make a case that this is an important question to solve, I'd like to see some practically relevant scenarios where the lack of good scaling of data leads to failure of non-scale-invariance approaches like Adam and Adagrad. I think for this paper to be have a bigger impact, a compelling set of experiments along this line seems to be necessary. - Do you expect poor data scaling to be the major issue in the training large AI models such as LLMs? If that's the case, I think this paper might have a bigger impact.

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

As I said, the reason for the current score is mainly due to the main scope of this paper. In my opinion, unless the authors have compelling experimental results or arguments, tacking the scale-invarance seems to have limited practical impact in the community.

Summary

The paper introduces a novel optimization algorithm which demonstrate scale-invariance property for generlized linear models unlike Adagrad. The authors analyzed KATE for smooth and non-convex functions and on generalized linear models to obtain the same convergence upper bounds (asymptotically) as Adagrad and Adam. However the scale invariant algorithm implies, the speed of the algorithm would be the same as for the best scaling of data. The authors also empirically verify this via numerical experiments on logistic regression and deep learning tasks.

Strengths

1) The authors come up with KATE which is scale invariant, and yet admit a convergence upper bound of $\mathcal{O}(\log(T)/\sqrt{T})$, which is an interesting algorithmic finding. 2) The paper is easy to read and understand. 3) Comprehensive appendix.

Weaknesses

I think authors need to emphasize the first point in Strengths by comparing with the diagonal online-newton method (diag-SONew) [1] which is also scale-invariant algorithm and what part of the analysis can fail for diag-SONew. I wrote the algorithm without the EMA here, which is essentially adagrad without the square root but with varying $\eta_t$: $$ w_t := w_{t-1} -\eta_t g_t /({\sum_{s=1}^t g_s* g_s}) $$ schedules one can try is $\eta_t=1$ or $\eta_t=\sqrt{t}$. I think comparing with the latter schedule will give a good understanding of the novelty behind KATE, as the schedule simulates the square root in Adagrad while being scale-invariant. Similarly empirical comparisons (if possible) with this simple algorithm in logistic-regression can help understand which algorithm is better. 2) Comparison with Adam doesn’t make sense in neural networks as KATE lacks momentum and EMA in second-moments (which are key features of Adam). Devising KATE with these features similar to [2] would help the empirical performance in neural networks. [1] Devvrit, Fnu, Sai Surya Duvvuri, Rohan Anil, Vineet Gupta, Cho-Jui Hsieh, and Inderjit Dhillon. "A computationally efficient sparsified online newton method." Advances in Neural Information Processing Systems 36 (2024). [2] Defazio, A., & Mishchenko, K. (2023, July). Learning-rate-free learning by d-adaptation. In International Conference on Machine Learning (pp. 7449-7479). PMLR.

Questions

In line 80-81 “meaning that the speed of convergence of KATE is the same as for the best scaling of the data.”, is this reflected in the convergence bound? i.e., whether scale dependence of Adagrad bound vs scale independence of KATE bound is emphasized. The Table 1 only mention asymptotic bounds for Adagrad. It would help the paper if the convergence bounds are analyzed for the generalized linear models for Adagrad and KATE to understand the affect of scale on the final upperbounds.

Rating

6

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Authors have adequately addressed limitations.

Summary

This paper proposes a scale-invariant variant of AdaGrad, called KATE, particularly for generalized linear models. Theoretically, the authors proved a convergence rate of $\mathcal{O}(\log T/\sqrt{T})$ for KATE, matching the best known rates for AdaGrad and Adam. Numerical experiments are used to illustrate KATE on several machine learning tasks, which outperforms AdaGrad consistently and matches/outperforms Adam.

Strengths

This work studies a crucial problem of developing a scale-invariant variant of AdaGrad which is particularly useful whenever data exhibit poor scaling or ill-conditioning. Convergence rates of KATE similar to those of AdaGrad and Adam under both deterministic and stochastic settings are established, with comprehensive numerical experiments to justify the efficacy of KATE compared to AdaGrad and Adam.

Weaknesses

As the motivation of KATE is to develop a scale-invariant optimizer, the experiments (even the one with simulated data) do not seem to have demonstrated this.

Questions

While it could be harder to demonstrate the scale-invariant property of KATE with real data experiments, is it possible to demonstrate the scale invariant property of KATE compared to AdaGrad and Adam with the logistic regression using simulated data? This could better help readers understand why the scale-invariant property of KATE is plausible compared to other adaptive optimizers.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Thanks

Thanks for your responses. I read through your responses, and I understand that the scale invariance could be beneficial in practice. I'll increase my score to 7.

Discussion with the authors

Dear reviewers: As the discussion period is going to end soon, please try to actively engage with the authors about the paper. Thanks a lot for your help and dedication. You AC.

Response to Rebuttal

Thanks so much to the authors for their response. I think I did miss the pointers and did not go through the appendix during my review, so thanks for your pointer. While I acknowledge the significance of this work, I do think that experiments of larger scales such as ImageNet (and open-source softwares if possible) are required to justify a higher score. Therefore I've decided to maintain my rating.