A Gradient Descent Optimizer with auto-controlled large Learning Rates, dynamic Batch Sizes and without Momentum

Authors: Alexander Kleinsorge, Alexander Fauck, Davide Paglieri, Stefan Kupper, Nina Singiri
Primary area: optimization
Keywords: Machine Learning, ICRL, Optimization

Abstract:
We present a novel, fast gradient based momentum-free optimizer algorithm with dynamic learning rate and dynamic batch size. The main ideas are to exponentially adapt the learning rate $ \alpha $ by situational awareness, mainly striving for orthogonal neighboring gradients, and to increase the batch size when the gradients become too noisy, leading to random walks rather than gradient descent. The method has a high success and fast convergence rate and relies only on few hyper-parameters, providing greater universality. It scales only linearly (of order $O(n)$) with dimension and is rotation invariant, thereby overcoming known limitations. The optimization method is termed ELRA (Exponential Learning Rate Adaption). The impressive performance of ELRA is demonstrated by experiments on several benchmark data-sets (ranging from MNIST to ImageNet) against common optimizers such as Adam, Lion and SGD.

Decision: reject
Reviewer scores: 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730274899473

thread_type:
official_review

<thread_object>
creator: reviewer_bzbf

<content>
summary:
This work presents a new fast gradient based momentum-free optimizer algorithm with dynamic learning rate and dynamic batch size. They evaluated their algorithm on several benchmarks and made some basic empirical achievement.

strengths:
* The authors have fused several accelerating tricks in the field of optimization into their optimizer, it seems to surprisingly work well.
* The authors provide interesting derivations for their design of the optimizer

weaknesses:
* It needs to clarify that, since this optimizer introduces adaptive learning rate for each parameter, then momentum-free shouldn’t be an advantage of this work at efficiency, the cache of learning rates is equivalent to cache momentum practically.
* In Section 2, the definition of the local minimum of $\alpha$ is unclear, as the authors assume that $f$ is convex, whereas it does not straightly lead that $f(x_t)$ is convex for $\alpha$, I am not sure about the effectiveness of devoting “local minimum” for faster optimization theoretically.
* The key derivation in Section 2 first appeared in the delta-bar-delta method in [1], in which it starts a series of following works, please at least review these works in the paper, and compare how the key idea of ELRA demonstrates advancement. In my opinion, the reasons why the old trick doesn’t last long in the application of optimization may be various. However, this work lacks a considerable review to the prior works.
* The efficiency claim in line 257 to line 258 sounds unprofessional: This gives ELRA a roughly 10% computation advantage over Adam and Lion, when used with the same batch size. The authors should at least provide some experimental analysis to prove it.
* It’s not clear what problem or challenges the study mainly aims to address, I checked 7 subsections in Section 3, and found no necessary or professional reason for introducing such or that trick in this optimizer. It seems like an addition of several existing works, but with poor writing.
* Showcasing “fast” needs comprehensive experiments, evaluations on some toy datasets seem far away from the word “enough”. Could the authors add some speed analysis on those real-world benchmarks compared with baseline optimizers like Adam, Lion, SGDm?
* Typo: line 479: Our experiments suggest that ELRA shares this behaviour with SDG.
* I didn’t find out the definition of “ELRA+FT”, please define it somewhere conspicuous, since it looks like this line performs best in the results but I could not find what it is.
* In conclusion, this paper has a limitation in its presentation, some words seem unprofessional. I suggest the authors to re-organize the whole writing to tell a better story and show a better result.

References:
[1]: Bernard Widrow, Marcian E Hoff, et al. Adaptive switching circuits. In IRE WESCON convention record, volume 4, pages 96–104. New York, 1960.

questions:
Please answer the issues and questions in the Weakness and point out my potential misunderstandings. I am happy to discuss and enhance my rate.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730562786539

thread_type:
official_review

<thread_object>
creator: reviewer_zpxz

<content>
summary:
This paper proposes an optimization algorithm that dynamically tunes the learning rate and dynamics, based on its last two gradients. The algorithm is evaluated on neural networks with several standard benchmark datasets, and compared with SGD and Adam.

strengths:
The proposed algorithm introduces not much extra computation cost while tuning the learning rate, as the tuning mechanism only depends on the norms of, and inner products between, past two gradient vectors.

There is less need in tuning the initial learning rate, compared with pure SGD. The algorithm is invariant under coordinate rotation, which could be an advantage over Adam and other Ada-family algorithms.

weaknesses:
1: The design of the proposed algorithm is based on strong assumptions/conjectures which may not be true in practice. Specifically, it assumes that the loss function is a parabola in the line that goes through any two consecutive iterates. Moreover, it requires that the minimizer of the parabola happens at $x=0$. These conditions usually do not hold in modern deep learning where loss function is considered as highly non-convex, and is far from quadratic.

In addition, the paper did not verify these assumptions/conjectures in experiments.

2: The proposed algorithm does not seem to improve empirical performance (according to the experiments of the paper). Without those additional techniques (FT, WD), ELRA actually performs quite worse than SGD. The successful run includes too many other techniques (boosting, FT, weight decay, gradient decay etc), it is not clear whether it is ELRA or those accessories that lead to a relatively good performance.

3:  [about the empirical term $\kappa$]. The algorithm introduced the empirical term $\kappa$. 
There is no theoretical justification of introducing it
There is no explanation of the formula of $\kappa$ (Line 151). Is it an empirical choice?
There is no (theoretical) justification of the claim “($\kappa$) neutralizes random noise effects in neural networks”. It is hard to believe a single scalar can neutralize random noise. There must be some theory to support the claim. 

4: In line 123, the paper says “we expect the optimal $\alpha_t$ for $x_t$ does not vary too much from the optimal $\alpha_{t-1}$ for $x_{t-1}$. I could not see why this should be true. The algorithm makes discrete steps (some steps may be quite big), hence $x_t$ is not necessarily close to $x_{t-1}$. At least, the paper needs to experimentally verify the relation between $\alpha_t$ and $\alpha_{t-1}$.

5: As for saddle points, the paper only looked at a special type $f(x)=x_1^2-x_2^2$. However, geometry near saddle points can be much more complicated than this special case, and the analysis of the special case may not generalize.

questions:
no further questions, see comments above
</content>
</thread_object>

</thread>
<thread>
creation date:
1730774558810

thread_type:
official_review

<thread_object>
creator: reviewer_emgk

<content>
summary:
This paper derives a new step size schedule based on a quadratic model. The key observation is that 
the optimal step size happens when current and previous gradients are orthogonal. Thus, their inner products play an important role in controlling the magnitude of the step size. Besides this, it introduces several heuristics to stabilize the training and improve the overall performance. Noticeably, it considers  damping the learning rate increase when the function value rises (when compared against previous iterations); and gradually increasing the batch size when some criteria based on function values are met (to reduce the random noise when a local minimum is approached). It demonstrates the effectiveness of the proposed method mostly using vision experiments.

strengths:
- This paper can be followed easily and most heuristics are intuitive. The computation of the step size is cheap.

- The experiments on the 2-dimensional example are interesting and show under certain settings (e.g., rotation) the proposed method can significantly outperform other adaptive step sizes such as Adam and RMSprop.

weaknesses:
- The proposed step size lacks theoretical guarantees even in the convex settings (or even convex quadratics?). I am not sure where the technical challenges are.

- I don’t think the current method is compared fairly with other methods given all the heuristics added on top of the learning rate. It is difficult to tell  where the gain (if there is any) comes from? Is it because of the step size schedule, or batch size increase, or iterates averaging (named as mean value boosting in the paper)? If iterates averaging were applied to other baselines, would the results change?

- Another major concern is that there are many hyperparameters associated with the proposed method, which raises questions regarding its practical usability. How expensive are the tunings of these hyperparameters?

- The experiments on language modelling are inconclusive.

questions:
N/A
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary:** The authors introduce a new optimizer, ELRA, that uses adaptive step size and adaptive batch, based on the last two gradients. ELRA increases the batch size when the gradient is too noisy. The new algorithm is $\mathcal{O}(n)$ and rotation invariant. They validate their results on several models.  

**Strengths:** The method does not require much additional computation, is more robust to the choice of the initial learning rate, and shows some improvements. Rotation invariance is advantageous when rotating the coordinates.  

**Weaknesses:** The method lacks theoretical guarantees, even in the convex (quadratic setting), and some of the choices do not have theoretical justification. The method combines several previously known techniques, and it is sometimes unclear where the improvements come from (step size, batch size, averaging, etc.). Some of the assumptions are not theoretically verified (for instance, the closeness of the iterates). Relation to previous methods such as delta-bar-delta and step-size adaptation using exponentiated gradient updates have not been discussed. The method introduces additional hyperparameters, which still require tuning.  

**Decision:** Based on the concerns raised by the reviewers, the paper will benefit from 1) additional theoretical results and analysis, 2) discussion and comparison to previous approaches, 3) clean ablations where the effect of each component (step-size, batch-size, averaging, weight decay, etc.) is studied separately. A more thorough benchmarking result based on, e.g., [1], would strongly validate the applicability of the method. I recommend rejection for the current version.  

[1] GE Dahl et al. "Benchmarking neural network training algorithms", arXiv preprint arXiv:2306.07179, 2023.