Independently-Normalized SGD for Generalized-Smooth Nonconvex Optimization

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We have revised the manuscript accordingly and uploaded a revised manuscript. Please let us know if further clarifications are needed.

Q1: There are papers with the analysis of NSGD with momentum [2], Adam [3,4], AdaGrad-Norm/AdaGrad [5,6]. All are tailored for the stochastic optimization in the generalized smooth setting and seem more advanced. All have convergence guarantees. Is the newly proposed I-NSGD faster in practice than any of them?

A: Thanks for your question. We agree that both our work and these achieve the optimal rate under similar generalized-smoothness conditions. While these works focus on analyzing the existing adaptive-type algorithms, our work aims to propose a new and fundamental independent sampling scheme that can inspire new stochastic algorithm designs and hence is complementary to the existing studies on algorithms. We have conducted more experiments to show that our proposed I-NSGD is indeed much faster than SPIDER, Normalization SGD with momentum.

For Phase Retrieval and DRO experiments, the training loss versus sample complexity and detailed description of algorithm settings can be found at Appendix I.

the loss function evaluated every 100 epochs are

For DRO, the detailed description of algorithm settings and training loss versus sample complexity can be found at our paper's Appendix I.

The objective function evaluated at each 200 epochs are

Q2: The original paper [7], which introduced the generalized smoothness assumption, explains that this assumption is based on empirical findings from language model training and image classification tasks. Does I-NSGD perform well on them?

A: Thank you for your question. The generalized smoothness condition we use belongs to $EL_{\text{asym}}^*(\alpha)$ proposed in [1], which is a generalized of $(L_0, L_1)$-smooth condition proposed in [7] by inducing problem-dependent constant $\alpha\in (0,1]$. This modification allows $EL_{\text{asym}}^*(\alpha)$ to characterize function geometry more tightly. However, per request, we conducted experiments to train ResNet on CIFAR 10 with algorithms SGD, Adam, Adagrad, NSGD with momentum, NSGD, Clipped SGD, and I-NSGD. Results are available in Appendix I in the submitted paper.

Q3: There is a recent paper [8], which contains a similar to NSGD method with smoothed clipping (Algorithm 1: $(L_0,L_1)$-GD). You mention this work in your paper. I can see that the authors develop the adaptive versions of the algorithm, the accelerated version. How does your theory compares to theirs?

A: Thank you for pointing out this reference. We will add more discussions in related work accordingly. We notice that the proposed $(L_0,L_1)$-GD and its acceleration is deterministic algorithm. Their analysis is conducted under convex settings. Our proposed I-NSGD algorithm's sample complexity, $\mathcal{O}(\epsilon^{-4})$ is obtained on non-convex stochastic settings. The stochastic extension $(L_0, L_1)$-SGD in [8] doesn't include the independent sampling scenario and clipping structure and their convergence analysis is also under convex setting. We appreciate their work very much, but this concurrent work[8] has a totally different setting from ours.

Q4cIn Theorem 2 when choosing in the minimum you compare $\frac{1}{4L_0}$ to $\frac{1}{4L_1\sqrt{T}}$, you add them again.

A: Thanks you for pointing out this question. We notice that this is indeed a typo and we are sorry for the confusion. To clarify, the learning rate in theorem 2 should be

and

For the term $\frac{1}{2}(L_0+L_1)(1+ \tau_2^2/\tau_1^2)^2$, this is produced from Lemma 6 in Appendix F, where we claim

When we prove this fact, we divide upper bound based on value of $||\nabla F(w_t) ||$. When $||\nabla F(w_t) ||$ is a small constant, we upper bound the LHS by a constant; When $||\nabla F(w_t) ||$ is large, we upper bound LHS $||\nabla F(w_t) ||^2/h_t^{\beta}$ associated with constant factor. Finally, we sum the two upper bounds together to yield RHS, as they are always positive.

To elaborate, when $||\nabla F(w_t) ||\leq \sqrt{1+{\tau_2^2}/{\tau_1^2}}$, we have $||\nabla F(w_t) ||^{\alpha}\leq (1+{\tau_2^2}/{\tau_1^2})^{\frac{\alpha}{2}}$ for $0<\alpha \leq 1$. Since $(1+{\tau_2^2}/{\tau_1^2}) >1$, so does $(1+{\tau_2^2}/{\tau_1^2})^{\frac{\alpha}{2}}$. These facts lead to $\frac{1}{2}\gamma^2\frac{(L_0+L_1||\nabla F(w_t) ||^{\alpha})}{h_t^{2\beta}}\frac{\tau_2^2}{\tau_1^2} \leq \frac{1}{2}\gamma^2(1+\frac{\tau_2^2}{\tau_1^2})^{\frac{\alpha}{2}}\frac{(L_0+L_1)}{h_t^{2\beta}}\frac{\tau_2^2}{\tau_1^2}$ Here, we derive the upper bound by replacing $||\nabla F(w_t) ||^{\alpha}$ by $(1+{\tau_2^2}/{\tau_1^2})^{\frac{\alpha}{2}}$ and multiply $(1+{\tau_2^2}/{\tau_1^2})^{\frac{\alpha}{2}}$ in front of $L_0$. Moreover, by using the clipping structure $h_t\geq 1$, and $0<\alpha\leq \beta\leq 1$, we have $\frac{1}{2}\gamma^2(1+\frac{\tau_2^2}{\tau_1^2})^{\frac{\alpha}{2}}\frac{(L_0+L_1)}{h_t^{2\beta}}\frac{\tau_2^2}{\tau_1^2} \leq \frac{1}{2}\gamma^2(L_0+L_1)(1+\frac{\tau_2^2}{\tau_1^2})^{2}.$ The second case where $||\nabla F(w_t) ||>\sqrt{1+\tau_2^2/\tau_1^2}$ will result $\frac{\gamma}{4h_t^{\beta}}||\nabla F(w_t) ||^2$, we omit the discussion here. For more details, you can check Appedix F, Proof of Lemma 6.

References:

[1] Chen, Ziyi, et al. Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization.

[2] Hübler, Florian, et al. Parameter-Agnostic Optimization under Relaxed Smoothness.

[3] Wang, Bohan, et al. Provable adaptivity in adam.

[4] Li, H., Rakhlin, A., and Jadbabaie, A., Convergence of adam under relaxed assumptions.

[5] Faw, Matthew, et al Beyond uniform smoothness: A stopped analysis of adaptive sgd.

[6] Wang, Bohan, et al. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions.

[7] Jingzhao Zhang, Tianxing He, Suvrit Sra, Ali Jadbabaie, Why gradient clipping accelerates training: A theoretical justification for adaptivity

[8]Gorbunov,Eduard, et al. Methods for Convex (L0,L1)-Smooth Optimization: Clipping, Acceleration, and Adaptivity.

[9] Arjevani, Yossi, et al. Lower bounds for non-convex stochastic optimization.

[10]Fang, Cong, et al. "Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator." Advances in neural information processing systems 31 (2018).

[11] Cutkosky, Ashok, et al. "Momentum improves normalized sgd." International conference on machine learning. PMLR, 2020.

Q4a: There is a standard sanity check procedure in optimization. The field is connected to physics (take the heavy-ball method of Polyak, for instance). And different quantities in physics have different units of measure. In Theorem 1, when choosing the constants $L_0$ and $L_1$ are added to each other. How two quantities with different units of measure can be added to each other?

A: Great Question! We agree with your point that some optimization algorithms (such as heavy-ball method) have physical meaning in practice. And we understand some areas related with optimization, such as adaptive control, do assign physical measurement for parameters to make the system output has desired performance and reasonable interpretability. But in optimization, we do not agree with the sanity check that you proposed, i.e., assigning physical units to check learning rate's technical correctness. In generalized smooth condition, $L_0$ and $L_1$ are just scalar numbers that characterize the function's geometry, which is totally different from a real system's physical property.

On the other hand, if $L_0$ and $L_1$ has $m/s^2$ and $m/s$ physical units, the resulting descent lemma

contradicts to the physical units you assumed since $f(w),\forall w$, and $w, \forall w$ should be measured in terms of $m$. As long as the learning rate can control the update so that the generated sequences from algorithm oracle, such as $f(w_t)$, $\nabla F(w_t)$, $w_t$ can converge, the learning rate is suitable to use for proof. In summary, the role of learning rate is to numerically avoid sequence divergence as algorithm progresses.

Q4b: In Theorem 1, when choosing the constants $L_0$ and $L_1$ are added to each other. How two quantities with different units of measure can be added to each other?

A: Thanks for raising question about step size rule. We will address your question by listing key steps resulting the design of step-size rule. The main derivation can be found at inequality (23) in appendix, from the descent lemma, by putting the NGD update rule, Lemma E.2 derived in [1], we have

f\big(w_{t+1}\big)-f\big(w_t\big)\leq -\frac{\gamma}{2}||\nabla f\left(w_t\right)||^{2-\beta}+\gamma^{\frac{2}{\beta}}\big(2 L_0+2 L_1\big)^{\frac{2}{\beta}-1}

We'd like to update our experiment results on training ResNet over CIFAR10 dataset. The baseline method includes SGD, Adagrad, Adam, NSGD, NSGD with momentum and Clipped SGD. The loss function we choose is cross-entropy loss. The initialization uses Kaiming initialization. The detailed algorithm settings can be found at Appendix I in our paper. We train all the baseline methods and I-NSGD on CIFAR10 Dataset for 30 epochs each. The resultant training loss recorded every 5 epochs are as following.

ResNet18 on CIFAR10

From the records, we can see that INSGD demonstrates fast convergence, which is comparable with Adam, Clipped SGD and better than NSGDm, NSGD, and SGD. This demonstrates the effectiveness of the I-NSGD algorithm.

ResNet50 on CIFAR10

From the above records, we can see that INSGD indeed demonstrates fast convergence, which is comparable with Adam, Adagrad and better than ClipSGD,NSGDm, NSGD, SGD. This demonstrates the effectiveness of the I-NSGD algorithm.

Thank you for your response.

I repeat that this sanity check procedure is standard in the optimization field. I do not see why the descent lemma contradicts to the procedure. The descent Lemma does not depend on your algorithm, it is based on Calculus. Physical laws do not depend on your algorithm either. By saying that the descent Lemma contradicts the physical units you essentially mean that Physical laws do not merge with Calculus. But Calculus is the language of Physics, all Physical laws are expressed through it. Both of the theories are built so that they merge.

I think I have explained myself very clearly in the previous review and made no mistake. It is a simple procedure, I will repeat it. I will set $\alpha=1.$

$x(t_{n+1}) \le x(t_n) + \langle x'(t_n), t_{n+1} - t_n\rangle + \frac{1}{2}\left(L_0 + L_1|x'(t_n)|\right)|t_{n+1} - t_n|^2.$

Let us go term by term. $x(t_{n+1})$ and $x(t_n)$ are measured in meters $m$ since they are coordinates of the material point at times $t_{n+1}$ and $t_n.$ Next, $x'(t)$ is $m/s$ (the speed), $t_{n+1} - t_n$ is $s$ (seconds, time). Then, $\langle x'(t_n), t_{n+1} - t_n\rangle$ gives $m/s\cdot s = m.$ No contradiction so far! Let's go further, $|t_{n+1} - t_n|^2$ is $s^2,$ therefore, $L_0$ has to be $m/s^2$ as $L_0 \cdot |t_{n+1} - t_n|^2$ has to be measured in meters: $m/s^2 \cdot s^2 = m.$ Next, $L_1$ needs to be $s^{-1}$ since $L_1|x'(t_n)|\cdot |t_{n+1} - t_n|^2$ has to be in meters: $s^{-1} \cdot m/s \cdot s^2 = m.$

Once again, $L_0$ and $L_1$ have different units of measure. These are not just simple constants.

The primary area of your paper is chosen as optimization. Imagine I want to optimize a simple function from Physics with your algorithms (why not, it is optimization, it should work on functions from Physics). I look at your theoretical guarantees, try to use them and suddenly I fail because I can not add $m/s^2$ to $s^{-1}.$

The problem is in the further analysis, I believe.

The paper is theoretical. However, the theory fails on a simple example. I will keep my score.

Q3: Can authors argue that the more general variance assumption is not compatible with analysis conducted in the work [3]?

A: Great question! We have added some discussions in our related work accordingly. [3] studies normalized gradient with momentum under $(L_0, L_1)$-generalized smoothness with bounded variance, and the learning rate they adopt is in the parameter-free regime. We found that their Lemma 13 in appendix served as a key inequality under their variance assumptions, where they upper bound $||m_t-\nabla F(w_t) ||$ by some terms including

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We have revised the manuscript accordingly and uploaded a revised manuscript. Please let us know if further clarifications are needed.

Q1a: Why (generalized) Polyak-Łojasiewicz condition is important? Its value seems to be limited.

A: Great Question! we have updated our related work to discuss more about the motivation of studying generalized PL condition. Initially, the PL condition attracted researchers' attention because it relaxes the strong convexity requirement. Recently, from the deep learning perspective, [5] found that PL* -- a variant of PL condition widely exists in loss landscape of over-parametrized neural networks. They also provide explanation why SGD-type algorithm can converge fast when training over-parametrized neural network with mean-squared loss. Later, [6] further proposed a more general $\psi$-KL* condition to include more loss function such as the CE loss, hinge loss and also provide convergence guarantee of SGD. Interestingly, it turns out that the generalized PL condition is a sub-class of $\psi$-KL* condition if $F^*$ is non-negative. This is because if $F^*\geq 0$, we can rewrite the generalized PL condition as

where the function $f(.)=(.)^{1/\rho}$ is non-decreasing for $\rho>0$. Based on these observations, we are motivated to analyze the convergence of stochastic algorithm under the generalized PL condition.

Q1b: In deterministic case, why NGD is considered under this setup but not GD? Does NGD remarkably benefit from Polyak-Łojasiewicz setup?

A: Great Question! In the deterministic setting, [2] showed that generalized-smooth functions have the following challenging local geometry

where the term $L_1 ||\nabla f(w') ||^{\alpha}||w-w' ||^2$ induced by generalized-smoothness scales polynomially with the gradient norm. This motivates [8] to apply NGD update to control such an error term induced by generalized-smooth geometry.

In [2], the authors also have conducted experiments showing that NGD outperforms GD in solving various nonconvex generalized-smooth machine learning problems. Moreover, the previous work [6] has studied GD under $\ell$-generalized smooth. The convergence result, and $\ell$-smooth requires strong assumptions on initial gradient bound $G$, which is impractical. These evidences indicate NGD is more adaptive to the generalized-smooth geometry than GD, and motivates us to continue studying NGD under the generalized PL condition, which has attracted much attention in optimization and deep learning.

Q2: The most important factor is the focus of the paper only on asymmetric generalized smooth, symmetric smoothness holds for a problem appearing in [2]. Why the author picks the less general smoothness condition? Why they think the case of less general smoothness overweights more than general variance assumption?

A: Thanks for your question! We study the asymmetric generalized-smoothness just to simplify the calculations in the proof. We note that our analysis can be directly generalized to the symmetric generalized smooth case with minor modifications. Specifically, in the deterministic case, we can choose the following NGD learning rate instead.

and

where $K_0:=L_0\big(2^{\frac{\alpha^2}{1-\alpha}}+1\big), K_1:=L_1 \cdot 2^{\frac{\alpha^2}{1-\alpha}} \cdot 3^\alpha, K_2:=L_1^{\frac{1}{1-\alpha}} \cdot 2^{\frac{\alpha^2}{1-\alpha}} \cdot 3^\alpha(1-\alpha)^{\frac{\alpha}{1-\alpha}}$. The same conclusion and proof logic still hold. The stochastic setting can be similarly addressed by using a slightly smaller learning rate.

To provide a intuitive justification, note that the only difference between asymmetric and symmetric generalized-smoothness is that the definition of asymmetric smoothness depends on $||\nabla F(w) ||$ whereas the symmetric smoothness depends on $\max_{\theta \in [0,1]}||\nabla F(w_{\theta}) ||$ with $w_{\theta} = (1-\theta)w+\theta w'$. Such a difference is marginal since the distance between $w_{t+1}$ and $w_t$ is bounded very small in the proof (by using a small learning rate). Thus, we use the asymmetric version merely for simplicity of the proof. On the other hand, we note that the machine learning applications (DRO, deep networks, etc) mentioned in the paper satisfies asymmetric generalized smooth. The proof of DRO problem can be found at proposition 3.2 in [2].

Thanks for your quick reply. We'd like to add more discussions regarding on your claim.

Claim: PL condition simplifies the proof.

Discussion: In Chen et al, the authors have already studied NGD convergence in non-convex settings and reach $\mathcal{O}(\epsilon^{-2})$ iteration complexities. Our study continues contributing through this line under generalized PL condition. Unlike applying the original PL condition, which can directly replace $||\nabla f(w_t) ||^2$ by $2\mu \cdot (f(w_t)-f^*)$ to lead linear convergence, our generalized PL condition is more difficult to handle with because of $\rho$ and $\beta$. These difficulties finally lead us to the descent lemma

f\left(w^{\prime}\right) \leq f(w)+\nabla f(w)^{\top}\left(w^{\prime}-w\right)+\frac{1}{2}||w^{\prime}-w||^2\left(K_0+K_1||\nabla f(w)||^\alpha+2 K_2||w^{\prime}-w||^{\frac{\alpha}{1-\alpha}}\right) .

f\left(w^{\prime}\right) \leq f(w)+\nabla f(w)^{\top}\left(w^{\prime}-w\right)+\frac{1}{2}||w^{\prime}-w||^2\left(L_0+L_1||\nabla f(w)||\right) \exp \left(L_1 ||w^{\prime}-w||\right)

and

NGD will lead to the same convergence conclusion. The proof logic is same as the proof given in Appendix, except inducing another small component $K_2 \gamma^{\frac{1}{1-\alpha}} \cdot||\nabla f\left(w_t\right)||^{\frac{(2-\alpha)(1-\beta)}{1-\alpha}}$. To deal with terms including $K_2 \gamma^{\frac{1}{1-\alpha}} \cdot||\nabla f\left(w_t\right)||^{\frac{(2-\alpha)(1-\beta)}{1-\alpha}}$, $K_0 \gamma \cdot||\nabla f\left(w_t\right)||^{2-2 \beta}$, and $K_1 \gamma \cdot||\nabla f\left(w_t\right)||^{2+\alpha-2 \beta}$, Chen et al. introduce Lemma E.1, where they utilize Young's inequality to unify the orders of all terms containing $||\nabla f(w_t) ||$ to $2-\beta$. This technique is also used in our proof when dealing with $L_0 \gamma \cdot||\nabla f\left(w_t\right)||^{2-2 \beta}$,$L_1 \gamma \cdot||\nabla f\left(w_t\right)||^{2+\alpha-2 \beta}$.

We'd like to thank the reviewer for pointing out this excellent reference in your comment. We saw that their convergence rate indeed touched the desired bound in different cases. But conclusions are based on $(L_0, L_1)$ generalized smooth, where Chen et al. classify such condition as $L_H^*$-generalized smooth. And it is also a sub-class of symmetric generalized smooth defined in the paper done by Chen et al. It's unclear regarding your statement, "Results from Vankov Daniil et al. give promises that for GD the right rates should recover the standard one." because the authors didn't analyze algorithms under symmetric generalized smooth with consideration of $\alpha$ and existence of $\max_{\theta \in [0,1]} ||\nabla F(w_{\theta}) ||$. We're not sure if their conclusions have direct implications for potential improvements in our results under symmetric generalization smooth conditions, as the designed learning rates are different and some of their convergence results are dependent on radius $|| x_0 - x^*||$, where we didn't assume such constant. Could you explain it more explicitly? We are happy to respond to your concerns.

References

Vankov, Daniil, et al. "Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods." arXiv preprint arXiv:2410.10800 (2024).

Chen, Ziyi, et al. "Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization." International Conference on Machine Learning. PMLR, 2023.

Q3: The technical novelty is limited except for using independent normalization. All other tools used are quite direct and similar to prior work. Can you explain explicitly about the technical novelty and technical tools?

A: We would like to briefly compare our work and the previous work [1] and [2]. [1] is the first work to propose $(L_0, L_1)$-generalized smoothness and study Clipped SGD's convergence under bounded stochastic gradient bias assumption. Later, [2] proposes the $EL_{\text{asym}}^*(\alpha)$ generalized-smoothness and studied the convergence of SPIDER [3] under affine bounded variance assumption. Their batch size choices are $\Omega(\tau_2^2/\epsilon^2)$, which can be impractical. Our work continued on contributing to this line of research, we proposed the I-NSGD with newly designed learning rate and clipping rule tailored for optimizing $EL_{\text{asym}}^*(\alpha)$ generalized-smooth functions under the relaxed gradient variance assumptions. Moreover, our algorithm design achieves convergence under constant-level batch size.

We agree that independent normalization is a simple modification in the algorithm design, yet the resulting theoretical convergence analysis turns out to be highly different and more effective than the existing literature. In particular, the affine bounded gradient assumption and the normalization parameter $\beta$ bring new challenges into the stochastic setting. To be specific, we theoretically designed new learning rate $\gamma = \min ( \frac{1}{4L_0},\frac{1}{4L_1}, \frac{1}{\sqrt{T}}, \frac{1}{8L_1(3\tau_2/\tau_1)^{\beta}} )$, and adaptive normalization term $h_t = \max \Big(1, (4L_1\gamma)^{\frac{1}{\beta}}\Big({2||\nabla f_{\xi_{B'}}(w_t)||+\frac{\tau_2}{\tau_1} }\Big) \Big)$ to guarantee convergence with constant level batch size choices $B, B' = \Theta (\tau_1^2)$ under generalized-smoothness. For example, in the main proof of Theorem 2 (in Appendix), the inequalities (36), (37) and (40) utilizes the proposed learning rate and adaptive normalization factor $h_t$ to bound the coefficient $\gamma (L_0+L_1||\nabla F(w) ||^{\alpha})/h_t^{\beta}$ by $1/2$ . In Lemma 6, the $\gamma^2(L_0+L_1||\nabla F(w) ||^{\alpha})\frac{\tau_2^2}{\tau_1^2}$ induced from the generalized-smooth condition is upper bounded by combining two upper bounds together derived based on different values of $|| \nabla F(w)||$. These techniques and resultant inequalities are indirect to handle without rigorously mathematical reasoning.

Q: Why is the generalized PL condition interesting to study? I know you do give an example in lines 172-175 but how relevant is this in practice?

A: Great Question! we have updated our related work to include more discussions on the motivation of studying generalized PL condition. To elaborate, the PL condition initially caught researchers' attention because it relaxes the strong convexity requirement but yield linear convergence rate. Recently, [4] found PL*, a variation of PL condition widely exists in loss landscape of over-parametrized neural networks. They also provide explanation why SGD-type algorithm can converge fast when training over-parametrized neural network with mean-squared loss. Later, [5] further propose $\psi$-KL* condition to include a broader class of loss functions such as CE loss, hinge loss and also provide convergence guarantee of SGD algorithm. Interestingly, our generalized PL condition turn out to be a sub-class of $\psi$-KL* condition if $F^*$ is non-negative. Because if $F^*\geq 0$, we can rewritten generalized PL condition as

where function $f(.)=(.)^{1/\rho}$ is non-decreasing for $\rho>0$.

References

[1] Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019)

[2] Chen, Ziyi, et al. "Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization." International Conference on Machine Learning. PMLR, 2023

[3] Fang, Cong, et al. "Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator." Advances in neural information processing systems 31 (2018).

[4] Liu, Chaoyue, et al. "Loss landscapes and optimization in over-parameterized non-linear systems and neural networks." Applied and Computational Harmonic Analysis 59 (2022): 85-116.

[5] Scaman, Kevin, et al. "Convergence rates of non-convex stochastic gradient descent under a generic lojasiewicz condition and local smoothness." International conference on machine learning. PMLR, 2022.

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We have revised the manuscript accordingly and uploaded a revised manuscript. Please let us know if further clarifications are needed.

Q1a Can theorem 2 hold for any batch size ? When $\tau_1=0$, the learning rate explodes.

A: Thanks for pointing this out. We set the batch size as $\mathcal{O}(\tau_1^2)$ just to simplify the calculations in the proof. In fact, our proof still holds for the more relaxed batch size choice $\mathcal{O}(\tau_1^2)+\mathcal{O}(1)$, which resolves the learning rate explosion issue. Since $\tau_1$ is normally a numerical constant, we can use any constant-level batch size. We have updated the theorem statement and its proof accordingly. In our experiments, we showed that for both Phase Retrieval and Distributionally Robust Optimization problems, constant-level batch sizes like $B=64,B' = 8$ and $B=128, B'=32$ always work well.

Q1b: In theorem 2, the batch size is directly related with $\tau_1$ and $\tau_2$, which are generally unknown. How can we choose a batch size when we don't know $\tau_1$ and $\tau_2$?

A: As we explained in the response to Q1, our proof still holds for the more relaxed batch size choice $\mathcal{O}(\tau_1^2)+\mathcal{O}(1)$, which allows to use any constant-level batch size since $\tau_1$ is normally a numerical constant. All our experiments use constant-level batch sizes.

Q2: The experiment is not fair enough: 1. for I-NSGD, you tune $\beta$ while for NSGD you didn't; 2. For clipping constant, this hyper-parameter should be tuned as well. Can you report the performance of additional experiment results?

A: Yes, we have conducted more experiments per the reviewer's request. We first want to clarify that the existing algorithms such as Clip-SGD and NSGD use the normalization hyper-parameter $\beta=1$ by default. In our new experiment,we add baseline methods: NSGD with momentum and SPIDER algorithm for comparison. And per request from you, we unify all the normalization algorithm's $\beta$ as $2/3$. The training loss curve versus sample compelxity, and the detailed algorithm settings can be found at our updated Appendix I. The objective value evaluated every 100 iterations are listed as following

For the DRO problem, the result recorded every 200 iterations is

Thanks for your reply! Regarding your concern about our batch size choice, which is related to $\tau_1$ originating from assumption 4, we want to explain in more detail.

In stochastic optimization literature, people assume either a constant bound or affine bound like our assumption 4, mainly to upper bound expectation of the second momentum of stochastic gradient. Mathematically, it can be expressed as

where $||\nabla F(w_t) ||$ is the norm of full gradient.

The motivation for doing this is because, in stochastic optimization, the theoretical evaluation metric for an algorithm is in terms of $||\nabla F(w_t) ||$ instead of stochastic estimator $||g_t||$, which can vary at each trial. To eliminate the effect of randomness, assumptions like bounded/affine bounded estimation bias or bounded/affine bounded variance are necessary when conducting convergence proof in terms of $||\nabla F(w_t) ||$. The usage of these assumptions can vary depending on specific algorithm structure.

Back to the derived batch size $B, B'=\Theta(\tau_1^2)$ from assumption 4, we agree there is no intuitive way to estimate $\tau_1$. It's possible that for low dimension (2d, 1d)data, exploratory data analysis might help to determine the value of $\tau_1$ accurately. However, by tuning batch sizes from 16, 32, 64, and so on, users can find the appropriate batch size. Since in standard deep learning training pipeline, data pre-processing, which includes normalization (i.e., normalized image matrix or word embeddings), can control $\tau_1$, $\tau_2$ so that it wouldn't be a huge constant. As we have demonstrated in experiments of Phase retrieval, DRO, and training ResNet(See Appendix I), $B = 128, B'=32$ is enough to guarantee convergence for most problems using I-NSGD.

Previous works, such as [1], [2],[3],[4], either require the batch size of their stochastic algorithms to be $\mathcal{O}(\tau_2^2\epsilon^{-2})$ to guarantee convergence under relaxed variance assumption, or they require strong assumption such that $||g_t - \nabla F(w_t) ||\leq \tau_2$ to guarantee convergence with $\mathcal{O}(1)$ batch size [Note: $\epsilon$ represents the desired algorithm accuracy, which is a small constant in (0,1)]. Our work balances the assumptions and resultant batch size, which said the newly proposed I-NSGD algorithm can converge with batch size $\Theta(\tau_1^2)$ under relaxed gradient bias assumption, $||g_t - \nabla F(w_t) ||\leq \tau_1|| \nabla F(w_t)||+\tau_2$.

References

[1] Chen, Ziyi, et al. "Generalized-smooth nonconvex optimization is as efficient as smooth nonconvex optimization." International Conference on Machine Learning. PMLR, 2023

[2] Reisizadeh A, Li H, Das S, et al. Variance-reduced clipping for non-convex optimization[J]. arXiv preprint arXiv:2303.00883, 2023.

[3] Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019)

[4]Zhang B, Jin J, Fang C, et al. Improved analysis of clipping algorithms for non-convex optimization[J]. Advances in Neural Information Processing Systems, 2020, 33: 15511-15521.

References

[1] Wang, Bohan, et al. Convergence of AdaGrad for non-convex objectives: simple proofs and relaxed assumptions. COLT 2023.

[2] Faw, Matthew, et al. Beyond uniform smoothness: a stopped analysis of adaptive SGD. COLT 2023.

[3] Hong, Yusong, et al. Revisiting Convergence of AdaGrad with Relaxed Assumptions.

[4]Arjevani, Yossi, et al. Lower bounds for non-convex stochastic optimization.

[5] Liu, Chaoyue, et al. "Loss landscapes and optimization in over-parameterized non-linear systems and neural networks." Applied and Computational Harmonic Analysis 59 (2022): 85-116.

[6] Scaman, Kevin, et al. "Convergence rates of non-convex stochastic gradient descent under a generic lojasiewicz condition and local smoothness." International conference on machine learning. PMLR, 2022.

[7] Zhang, Jingzhao, et al. "Why gradient clipping accelerates training: A theoretical justification for adaptivity." arXiv preprint arXiv:1905.11881 (2019).

[8] Kingma, Diederik et al. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014).

Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We have revised the manuscript accordingly and uploaded a revised manuscript. Please let us know if further clarifications are needed.

Q1 PL condition greatly restrict the universality of these rates. Although PL does not imply convexity, it allows the objective to have favorable geometric properties that lead to fast rates, sometimes even comparable to the convex or strongly-convex setting. Can author explain the value of inducing generalized PL condition?

A: Great Question! we have updated our related work to discuss more about the motivation of studying generalized PL condition. Initially, the PL condition attracted researchers' attention because it relaxes the strong convexity requirement. Recently, from the deep learning perspective, [5] found that PL* -- a variant of PL condition widely exists in loss landscape of over-parametrized neural networks. They also provide explanation why SGD-type algorithm can converge fast when training over-parametrized neural network with mean-squared loss. Later, [6] further proposed a more general $\psi$-KL* condition to include more loss function such as the CE loss, hinge loss and also provide convergence guarantee of SGD. Interestingly, it turns out that the generalized PL condition is a sub-class of $\psi$-KL* condition if $F^*$ is non-negative. This is because if $F^*\geq 0$, we can rewrite the generalized PL condition as

where the function $f(.)=(.)^{1/\rho}$ is non-decreasing for $\rho>0$. Based on these observations, we are motivated to analyze the convergence of stochastic algorithm under the generalized PL condition.

Q2: The authors argue that the analysis of I-NSGD outperforms [7] by using an affine noise bound stated in assumption 4. Nevertheless, similar assumptions have already been explored in other prior works like [1], [2], and [3], where convergence rates of are established for adaptive gradient methods when the same general smooth assumption is satisfied. This reduces the contribution of this work, as the above results already achieve the optimal rate under similar conditions. Can author add a more thorough discussion of the connection to the literature would help the readers have a more complete understanding of the whole picture?

A: Thanks for sharing these previous works. We have added a discussion in the related work to compare with these works, and we summarize it below for your reference. We agree that both our work and the works [1-3] achieve the optimal rate under similar generalized-smoothness conditions. While [1-3] focus on analyzing the existing adaptive-type algorithms, our work aims to propose a new and fundamental independent sampling scheme that can inspire new stochastic algorithm designs and hence is complementary to the existing studies on algorithms.

Discussion: The references [1], [2], [3] focus on analyzing the existing algorithms from the AdaGrad family. The update rule of Adagrad leverages momentum and adaptive gradients, and hence is substantially different from the basic normalized SGD and clipped SGD. To elaborate, in Adagrad, the normalization term is accumulated as $v_{t} = v_{t-1}+||g_t ||^2$, the update rule is $w_{t+1} = w_{t}-\gamma\frac{1}{\sqrt{v_t}}g_t$. The normalized SGD and clipped SGD takes the form $w_{t+1} = w_t - \gamma \frac{1}{||g_t ||+\delta}g_t$ or $w_{t+1} = w_t - \gamma \frac{1}{\max( ||g_t ||+\delta, \eta)}g_t$, where $\eta$ and $\delta$ are some constant. The accumulation term $v_t$ will lead huge difference for convergence analysis.

Instead of focusing on the existing algorithms, our work aims to develop a new and fundamental sampling scheme, and further apply it to Clipped SGD to solve generalized-smooth problems. Based on this new sampling scheme, we are able to relax the constant upper bound developed in [7] for controlling the stochastic gradient bias and achieve a comparable convergence rate with constant-level batch sizes. To elaborate the novelty of our independent sampling, as illustrated in Figure 1, normalized SGD/clipped SGD without independent sampling take biased updates in expectation. By leveraging independent sampling, our proposed I-NSGD can reduce bias in expectation especially when the stochastic gradients have diverse directions. Furthermore, in the design of our I-NSGD, we specifically adapt the hyper-parameters to the generalized-smoothness and affine stochastic gradient noise to improve the analysis under independent sampling. As a result, the technical proof of I-NSGD is substantially different from that of the existing algorithms.