Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimization

Authors: Naoki Sato, Hideaki Iiduka
Primary area: optimization
Keywords: deep learning theory, degree of smoothing, generalizability, graduated optimization, SGD, sharpness, smoothing property, stochastic noise

Abstract:
The graduated optimization approach is a heuristic method for finding global optimal solutions for nonconvex functions by using a function smoothing operation with stochastic noise. We show that stochastic noise in stochastic gradient descent (SGD) has the effect of smoothing the objective function, the degree of which is determined by the learning rate, batch size, and variance of the stochastic gradient. Using this finding, we propose and analyze a new graduated optimization algorithm that varies the degree of smoothing by varying the learning rate and batch size, and provide experimental results on image classification tasks with ResNets that support our theoretical findings. We further show that there is an interesting correlation between the degree of smoothing by SGD's stochastic noise, the well-studied ``sharpness'' indicator, and the generalization performance of the model.

Decision: reject
Reviewer scores: 6, 3, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1730451477295

thread_type:
official_review

<thread_object>
creator: reviewer_kxu4

<content>
summary:
The authors first analyzed the relationship between the batch size, learning rate, and test accuracy, showing that there is a correlation between $\frac{\eta C}{\sqrt{b}}$ and test accuracy.
Then, using these observations, the authors proposed Implicit Graduated Optimization, which changes the learning rate and batch size during the training.
The authors provided the convergence rate of Implicit Graduated Optimization and experimentally examined the effectiveness of their proposed method.

strengths:
* The authors analyzed the relationship between test accuracy, learning rate, and batch size.

* Based on this relationship, the authors proposed Implicit Graduated Optimization that adjusts the batch sizes and learning rate during the training.

weaknesses:
Overall, the reviewer feels that the proposed method itself is similar to that presented in previous studies, e.g., [1], and the clear advantage of the proposed methods over [1] has not been shown in this paper. 
Designing the scheduler of batch sizes and learning rates from the perspective of graduated optimization seems to be novel, while the reviewer feels that the relationship between test accuracy and $\frac{\eta C}{\sqrt{b}}$, derived as a conclusion, does not appear to be very novel.
See below for a detailed comment.


* The reviewer does not think the relationship between $\frac{\eta C}{\sqrt{b}}$ and accuracy presented in this paper is very new since it is well-known that large batch sizes and small learning rates degrade test accuracy. While showing this relationship is a good motivation for designing the proposed method, the reviewer does not think that showing this relationship in itself is a major contribution.

* The reviewer does not understand the difference between the proposed method and existing methods, e.g., [1]. Changing the batch size during training has already been proposed in [1].

* All methods achieved approximately 60% in Figure 4. However, by comparing the results reported in the existing papers [1,2], 60% appears to be too low. Thus, the reviewer is wondering if the results are reliable.

### Typo
* "." is missing in "Similar early approaches can be found in (Witkin et al., 1987) and (Yuille, 1989)" in line 67.

## Reference

[1] Samuel et al., Don't Decay the Learning Rate, Increase the Batch Size, In ICLR 2018

[2] He et al., Deep Residual Learning for Image Recognition, In CVPR 2016

questions:
See the weakness section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730619210188

thread_type:
official_review

<thread_object>
creator: reviewer_k496

<content>
summary:
This paper proposes the degree of smoothing notion in stochastic gradient descent and studies its relation with sharpness and generalization. From the proposed notion along with empirical studies, the paper observes that controlling the batch size and learning rate affects the degree of smoothness and therefore proposes a graduated optimization algorithm to gradually decrease the degree of smoothing by increasing the batch size and increasing the learning rate.

strengths:
1. It is an interesting observation to view the update of SGD as smoothing.
2. The proposed degree of smoothing offers another intuitive explanation for decreasing learning rate and increasing batch size along the way of optimization and establishes its connection to graduated optimization.

weaknesses:
1. The proposed degree of smoothing is somewhat obvious and simple, falling directly out of the variance/noise assumption of mini-batch SGD. Its correlation with concepts like sharpness is also straightforward because their definitions are somewhat similar already, with sharpness measuring the discrepancy of the function $f$ w.r.t. some $\delta$ neighborhood while the degree of smoothness the discrepancy of gradient $\nabla f$ w.r.t. some noisy disturbance $\omega$.
2. The numerical result is not quite informative as the effect of decreasing the learning rate or increasing the batch size has been studied and verified in previous optimization and learning theories like mini-batch SGD and sharpness-aware optimization.

questions:
Is there any new insight/advantage the degree of smoothing offers other than decreasing the learning rate or increasing the batch size?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685139282

thread_type:
official_review

<thread_object>
creator: reviewer_nrh8

<content>
summary:
This article discusses how Stochastic Gradient Descent (SGD), in its essence smoothens nonconvex functions while optimizing them theoretically analysis is provided here to show that the degree of smoothing ($\delta$) can be calculated using the formula $\delta= \eta C/\sqrt{b}$ where $\eta$ represents the learning rate and $C$ relates to variance while $b$ signifies the batch size. Additionally, it is theoretically and experimentally demonstrated that this smoothing effect clarifies findings in deep learning such as the reason behind poor generalization often observed with large batch sizes. The paper presents three contributions:
1. A mathematical model is offered to explain the smoothing effects of descent (SGDs).
2. There is a link between the level of smoothing and how the model performs overall; the best range for smoothing is between $0.1$ and $1.0$. 
3. Introducing a graduated optimization technique that adjusts the level of smoothing by modifying the learning rate and batch size dynamically throughout the training process.

strengths:
1. Introduce an innovative approach by showing that SGD’s inherent stochasticity can smooth nonconvex functions, it allows it to function as an implicit form of graduated optimization. This study leverages SGD’s existing stochasticity for the same purpose.
2. This paper offers a framework that explains the impact of learning rate adjustment and batch size variability on the level of smoothing in stochastic gradients. Its theoretical analysis is thorough and well supported by proofs. Clearly defined assumptions that provide a strong basis, for their assertions.

weaknesses:
1. This work is constrained by the assumption that gradient noise follows a normal distribution, which will be expected for a broader category beyond normal distribution.
2. Analysis only focused on image classification tasks with CNN-based models.
3. The proof of convergence only applies to $\sigma$-nice functions, which is a restricted class of nonconvex functions.
4. Experiments are insufficient, mainly conducted on CIFAR100 with ResNet architectures, and no experiments on other domains beyond image classification.
5. Lack of discussion of computational overhead compared to standard SGD.
6. No discussion of how the method scales to relatively large models or datasets.

questions:
Please refer to the weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745188137

thread_type:
official_review

<thread_object>
creator: reviewer_kvgj

<content>
summary:
This paper studies the convergence of stochastic gradient descent (SGD) in the context of nonconvex optimization. The authors aimed to show that the gradients help the objective by smoothing it through the noise injected by sampling functions. The claim that SGD smoothes the objective is shown by assuming that the gradients are distributed according to isotropic Gaussian distribution, which I find to be a trivial result. Moreover, since the work is written from the perspective of giving a new theory for SGD specifically, I find this to be very misleading. The authors also present experiments on CIFAR100 to study the numerical properties related to generalization such as sharpness, which serve as a secondary contribution. Next, the authors propose a new method for $\sigma$-nice functions that runs gradient descent on a smoothed objective with varying parameters and they explain why the method works. Finally, the authors run several variations of SGD on training ResNet-34 on ImageNet to show that increasing batch size helps SGD converge.

strengths:
1. I think a theory for SGD and an explanation why noise helps to train neural networks is highly desired. It is a great topic and if the results were good, I'd have considered this an important contribution.
2. The numerical evaluations are reasonable.

weaknesses:
1. My main concern about this work is the unrealistic assumption that the noise from sampling gradients follows Gaussian distribution with identity covariance matrix and variance that does not change over the course of training. What's worse, this assumption is not stated as clearly as other assumptions, instead it's introduced in the text and a couple of references are given to experimental papers that justify normality of the gradients. Those papers, however, do not show that gradients have exactly the same distribution throughout training. It's also never discussed in the paper why the assumption should hold or what happens if it doesn't. And what we should expect here, in contrast, is that the noise level changes every iteration and its variance is a random variable that depends on the iterates and previously sampled gradients.
2. Since the gradient noise is assumed to be exactly gaussian and consntant, the paper fails to deliver what the abstract promises, namely to "show that stochastic noise in stochastic gradient descent (SGD) has the effect of smoothing the objective function", because the authors essentially *assume* that the noise smoothes the objective. I usually refrain from calling a result trivial.
3. Since the results in this work assume Gaussian noise, it means that prior papers on injecting noise inside gradients immediately apply to SGD in this setting. However, there is no comparison to related work on this topic, such as Orvieto et al. "Anticorrelated Noise Injection for Improved Generalization" and Vardhan & Stich, (2021). The latter paper is only mentioned in passing as showing that noise helps escape saddle points, but the authors do not explain what novelty their paper has to offer.

## Minor
The abstract says that "The graduated optimization approach is a heuristic method", which is not true since it has already been studied in the work of Hazan et al. (2016). It's particularly inappropriate since the authors use the same assumption of $f$ being $\sigma$-nice  
The objective function $f$ is not properly introduced before being used in the introduction  
"noise smooths" -> "noise smoothes"  
"diffusion models (Sohl-Dickstein et al., 2015; Ho et al., 2020; Song et al., 2021a; Rombach et al., 2022), which are currently state-of-the-art generative models, implicitly use the techniques of graduated optimization". This seems like a very streched example, diffusion models are injecting noise in the image or latent space and for reasons very different from minimizing a nonconvex function. I suggest the authors remove this statement or give a reference where it is shown that there exists a function implicitly minimized by image denoising  
Lemmas 2.1 and 2.2 are introduced with no context, which leads to an unnatural flow when reading the paper. Perhaps the discussion that follows them could be put prior to stating the lemmas.  
Broken citation: "Harshvardhan" should have been "Harsh Vardhan"  
Line 420, "is nonnegative constant" -> "is a nonnegative constant"

questions:
1. In what sense do the authors "show" that noise in SGD helps? I see no theory for this, it all seems to follow from assuming Gaussian distribution of gradient noise and prior literature.
2. Can the assumption on Gaussian noise be removed?
3. It appears to me that log scale in Figure 2 in x-axis is actually not helpful as most growth seems to happen for larger values on the x-axis, especially in Figure 2 (B). Can you show us the figure with the x-axis not scaled logarithmically?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730858376928

thread_type:
official_review

<thread_object>
creator: reviewer_4qqd

<content>
summary:
The paper presents a heuristic approach for solving nonconvex optimization problems by combining a smoothing technique. The authors demonstrate that stochastic gradient noise impacts the smoothing of the objective function, with the extent of this effect determined by three factors: the learning rate, batch size, and the variance of the stochastic gradient. Building on these insights, the authors introduce a new graduated optimization method. Theoretical analysis and numerical results confirm the effectiveness of the proposed method.

strengths:
The paper offers a novel perspective on the smoothing effect of stochastic gradient descent (SGD) and its implications for optimizing nonconvex functions.

The connection between smoothing by SGD and generalization performance is a contribution to this field. The correlation between the degree of smoothing, sharpness of the objective function, and generalization performance is convincingly shown, enhancing the credibility of the theoretical insights.

weaknesses:
While the experiments with ResNets on CIFAR100 provide valuable insights, they may not fully generalize to other types of neural networks or more complex datasets.

A more comprehensive discussion on the practical implementation of the proposed implicit graduated optimization algorithm would further enhance its applicability and understanding.

questions:
How do different optimizer variants (e.g., Adam, RMSprop) impact the smoothing effect observed with SGD?

What strategies can practitioners use to effectively set the initial values and decay rates for learning rate and batch size to maximize the advantages of implicit graduated optimization?

Could this framework be extended to analyze optimization in graph neural networks or manifold learning?

What computational trade-offs might be associated with implementing the proposed algorithm, such as increased training time or memory usage?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733303760517

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We deeply appreciate the reviewers' careful review and active replying during the discussion period.

To assist the Chairs in their final decision, we summarize the reviewers and our arguments here.

The reviewers who recommended reject mainly raised the following issues
1. the SGD's gradient noise does not follow a Gaussian distribution or is not sure if it does (by Reviewer KvGj).
2. the analysis is only valid for $\sigma$-nice functions (by Reviewer NRH8).

To address this issue, we made the following additions and corrections.
1. **We modified the definition of smoothed function based on experimental observations and theory (see Definition 2.1 and Section H).**
This eliminates the assumption in our theory that the gradient noise of SGD follows a Gaussian distribution, and instead relaxes the assumption that it follows a light-tailed distribution. Issue 1 has been resolved, and Reviewer KvGj seems to be satisfied because the replying has ceased.

2. **We have shown that the cross entropy loss and the mean square error are 1-nice and 2-nice functions, respectively (see the reply to Reviewer NRH8).** The essence of issue 2 is that our theory is not valid for practical loss functions because the $\sigma$-nice function is a function that satisfies special conditions, and we do not know whether practical loss functions satisfy those conditions.
Cross-entropy loss and mean squared error are loss functions commonly used in classification and regression tasks, respectively. Therefore, the fact that these are $\sigma$-nice functions also eliminates issue 2. 
Reviewer NRH8 does not seem to be satisfied because we have not significantly extended the definition of the $\sigma$-nice function to more nonlinear functions. However, for the applications of the $\sigma$-nice function and graduated optimization approach in machine learning that are most important to us and to all reviewers, we believe that our additional results are sufficient and that this additional results more than raises the value of our paper.

The other reviewers' arguments are summarized below.
- Reviewer 4qQd appreciates the theoretical and experimental novelty and value of our paper and seem to agree with the acceptance of our paper.
- Reviewers k496 and kxU4, while acknowledging the correctness of our theory and the sufficiency of our experiments, are unwilling to accept our results as not surprising.

All of the above shows that our paper has no shortcomings other than the perceived lack of impact on the two reviewers and provides theoretically and experimentally correct results.

Our main contributions are listed below.
1. We show that the degree of smoothing $\delta$ provided by SGD's stochastic noise depends on the quantity $\delta = \frac{\eta C}{\sqrt{b}}$, where $\eta$ is the learning rate, $b$ is the batch size, and $C^2$ is the variance of the stochastic gradient.
2. We experimentally show the relationship between the degree of smoothing, Sharpness, and generalization performance.
3. By bringing in graduated optimization, we showed that the use of decaying learning rate and increasing batch size actually contributed to the search for the global optimal solution.
4. An implicit graduated optimization algorithm is proposed and analyzed. 
5. (Additional.) We showed that cross entropy loss and mean squared error, which are very common in machine learning, are $\sigma$-nice functions.

We consider any of these contributions to be novel and surprising. 
- Contributions 1 and 2 provides new insights into the relationship between the landscape of the loss function and generalization performance from a completely different perspective from previous studies, such as Sharpness. 
- Contribution 3 provides theoretical support for the general method of decreasing learning rate and increasing batch size. 
- Contribution 4 is the first ever attempt at implicit graduated optimization without an explicit smoothing operation. 
- Contribution 5 allows all previous theoretical and experimental findings on graduated optimization to be introduced into machine learning through the $\sigma$-nice function.

We are sorry to impose the hard work on the Chairs, but for these reasons, we believe that this paper is worthy of acceptance.
In addition to the rating scores, we ask that you consider our arguments and those of the reviewers before making a final decision.
Finally, our paper is more correct and more valuable thanks to the reviewers' valuable remarks. We sincerely appreciate the hard work of the reviewers.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper examines the smoothing effects of SGD on nonconvex functions, as influenced by the learning rate, batch size, and the variance of the stochastic gradient. While the reviewers found the exploration of the relationship between SGD parameters and smoothing a relevant topic, concerns were raised about the significance of the findings, arguing that they may offer limited novelty given existing knowledge about SGD. Additionally, some reviewers described the assumptions as overly restrictive and argued that the experimental work was not sufficiently persuasive. The authors are encouraged to incorporate the important feedback given by the knowledgeable reviewers.