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

## Abstract

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.

## 1 Introduction

### 1.1 Background

The amazing success of deep neural networks (DNN) in recent years has been based on optimization by stochastic gradient descent (SGD) (Robbins & Monro, ) and its variants, such as Adam (Kingma & Ba, ). These methods have been widely studied for their convergence (Moulines & Bach, ; Needell et al., ) (Fehrman et al., ; Bottou et al., ; Scaman & Malherbe, ; Loizou et al., ; Zaheer et al., ; Zou et al., ; Chen et al., ; Zhou et al., ; Chen et al., ; Iiduka, ) and stability (Hardt et al., ; Lin et al., ; Mou et al., ; He et al., ) in nonconvex optimization.

SGD updates the parameters as $\bm{x}_{t+1}:=\bm{x}_{t}-\eta\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})$, where $\eta$ is the learning rate and $\nabla f_{\mathcal{S}_{t}}$ is the stochastic gradient estimated from the full gradient $\nabla f$ using a mini-batch $\mathcal{S}_{t}$. Therefore, there is only an $\bm{\omega}_{t}:=\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})$ difference between the search direction of SGD and the true steepest descent direction. Some studies claim that it is crucial in nonconvex optimization. For example, it has been proven that noise helps the algorithm to escape local minima (Ge et al., ; Jin et al., ; Daneshmand et al., ; Harshvardhan & Stich, ), achieve better generalization (Hardt et al., ; Mou et al., ), and find a local minimum with a small loss value in polynomial time under some assumptions (Zhang et al., ).

(Kleinberg et al., ) also suggests that noise smooths the objective function. Here, at time $t$, let $\bm{y}_{t}$ be the parameter updated by gradient descent (GD) and $\bm{x}_{t+1}$ be the parameter updated by SGD, i.e.,

$$ $\displaystyle\bm{y}_{t}:=\bm{x}_{t}-\eta\nabla f(\bm{x}_{t}),\ \ \bm{x}_{t+1}: =\bm{x}_{t}-\eta\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})=\bm{x}_{t}-\eta(\nabla f (\bm{x}_{t})+\bm{\omega}_{t}).$ $$

Then, we obtain the following update rule for the sequence $\left\{\bm{y}_{t}\right\}$,

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t+1}\right]=\mathbb{E}_ {\bm{\omega}_{t}}\left[\bm{y}_{t}\right]-\eta\nabla\mathbb{E}_{\bm{\omega}_{t} }\left[f(\bm{y}_{t}-\eta\bm{\omega}_{t})\right],$ (1) $$

where $f$ is Lipschitz continuous and differentiable. Therefore, if we define a new function $\hat{f}(\bm{y}_{t}):=\mathbb{E}_{\bm{\omega}_{t}}[f(\bm{y}_{t}-\eta\bm{\omega}
_{t})]$, $\hat{f}$ can be smoothed by convolving $f$ with noise (see Definition 2.1, also (Wu, )), and its parameters $\bm{y}_{t}$ can approximately be viewed as being updated by using the gradient descent to minimize $\hat{f}$. In other words, simply using SGD with a mini-batch smooths the function to some extent and may enable escapes from local minima. (The derivation of equation (1) is in Section A.)

Graduated Optimization. Graduated optimization is one of the global optimization methods that search for the global optimal solution of difficult multimodal optimization problems. The method generates a sequence of simplified optimization problems that gradually approach the original problem through different levels of local smoothing operations. It solves the easiest simplified problem first, as the easiest simplification should have nice properties such as convexity or strong convexity; after that, it uses that solution as the initial point for solving the second-simplest problem, then the second solution as the initial point for solving the third-simplest problem and so on, as it attempts to escape from local optimal solutions of the original problem and reach a global optimal solution.

This idea first appeared in the form of graduated non-convexity (GNC) by (Blake & Zisserman, ) and has since been studied in the field of computer vision for many years. Similar early approaches can be found in (Witkin et al., ) and (Yuille, ) Moreover, the same concept has appeared in the fields of numerical analysis (Allgower & Georg, ) and optimization (Rose et al., ; Wu, ). Over the past 25 years, graduated optimization has been successfully applied to many tasks in computer vision, such as early vision (Black & Rangarajan, ), image denoising (Nikolova et al., ), optical flow (Sun et al., ; Brox & Malik, ), dense correspondence of images (Kim et al., ), and robust estimation (Yang et al., ; Antonante et al., ; Peng et al., ). In addition, it has been applied to certain tasks in machine learning, such as semi-supervised learning (Chapelle et al., ; Sindhwani et al., ; Chapelle et al., ), unsupervised learning (Smith & Eisner, ), and ranking (Chapelle & Wu, ). Moreover, score-based generative models (Song & Ermon, ; Song et al., ) and diffusion models (Sohl-Dickstein et al., ; Ho et al., ; Song et al., ; Rombach et al., ), which are currently state-of-the-art generative models, implicitly use the techniques of graduated optimization. A comprehensive survey on the graduated optimization approach can be found in (Mobahi & Fisher III, ).

Several previous studies have theoretically analyzed the graduated optimization algorithm. (Mobahi & Fisher III, ) performed the first theoretical analysis, but they did not provide a practical algorithm. (Hazan et al., ) defined a family of nonconvex functions satisfying certain conditions, called $\sigma$-nice, and proposed a first-order algorithm based on graduated optimization. In addition, they studied the convergence and convergence rate of their algorithm to a global optimal solution for $\sigma$-nice functions. (Iwakiri et al., ) proposed a single-loop method that simultaneously updates the variable that defines the noise level and the parameters of the problem and analyzed its convergence. (Li et al., ) analyzed graduated optimization based on a special smoothing operation. Note that (Duchi et al., ) pioneered the theoretical analysis of optimizers using Gaussian smoothing operations for nonsmooth convex optimization problems. Their method of optimizing with decreasing noise level is truly a graduated optimization approach.

### 1.2 Motivation

Equation (1) indicates that SGD smooths the objective function (Kleinberg et al., ), but it is not clear to what extent the function is smoothed or what factors are involved in the smoothing. Therefore, we decided to clarify these aspects and identify what parameters contribute to the smoothing. Also, once it is known what parameters of SGD contribute to smoothing, an implicit graduated optimization can be achieved by varying the parameters so that the noise level is reduced gradually. Our goal was thus to construct an implicit graduated optimization framework using the smoothing properties of SGD to achieve global optimization of deep neural networks.

### 1.3 Contributions

Figure: Figure 1: Conceptual diagram of implicit graduated optimization for $\sigma$-nice function.
[Uncaptioned image]: x1.png

1. SGD’s Smoothing Property (Section 3). 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 (see Assumption 2.1). Accordingly, the smaller the batch size $b$ is and the larger the learning rate $\eta$ is, the smoother the function becomes (see Figure 1).
This finding provides a theoretical explanation for several experimental observations. For example, as is well known, training with a large batch size leads to poor generalization performance, as evidenced by the fact that several prior studies (Hoffer et al., ; Goyal et al., ; You et al., ) provided techniques that do not impair generalization performance even with large batch sizes. This is because, if we use a large batch size, the degree of smoothing $\delta=\frac{\eta C}{\sqrt{b}}$ becomes smaller and the original nonconvex function is not smoothed enough, so the sharp local minima do not disappear and the optimizer is more likely to fall into one. (Keskar et al., ) showed this experimentally, and our results provide theoretical support for it.

2. Relationship between degree of smoothing, sharpness, and generalizability (Section 4).

Figure: Figure 2: (A) Sharpness versus degree of smoothing calculated from learning rate, batch size, and the estimated variance of the stochastic gradient. (B) Test accuracy after 200 epochs ResNet18 training on the CIFAR100 dataset versus sharpness. (C) Test accuracy versus degree of smoothing. The color shading in the scatter plots represents the batch size: the larger the batch size, the darker the color of the plotted points. “lr” means learning rate.
Refer to caption: x2.png

To support our theory that simply using SGD for optimization smoothes the objective function and that the degree of smoothing is determined by $\delta=\eta C/\sqrt{b}$, we experimentally confirmed the relationship between the sharpness of the function around the approximate solution to which the optimizer converges and the degree of smoothing. We showed that the degree of smoothing is clearly able to express the smoothness/sharpness of the function as well as the well-studied “sharpness” indicator (Figure 2 (A)), and that it is more strongly correlated with generalization performance than sharpness (Figure 2 (B) and (C)). Our results follow up on a previous study (Andriushchenko et al., ) that found, through extensive experiments, correlations between generalization performance and hyperparameters such as the learning rate, but no correlation between it and sharpness.

3. Implicit Graduated Optimization (Section 5). Since the degree of smoothing of the objective function by stochastic noise in SGD is determined by $\delta=\frac{\eta C}{\sqrt{b}}$, it should be possible to construct an implicit graduated optimization algorithm by decreasing the learning rate and/or increasing the batch size during training. Based on this theoretical intuition, we propose a new implicit graduated optimization algorithm and show that the algorithm for the $\sigma$-nice function converges to an $\epsilon$-neighborhood of the global optimal solution in $\mathcal{O}\left(1/\epsilon^{2}\right)$ rounds. In Section 5.2, we show experimentally that our implicit graduated algorithm outperforms SGD using a constant learning rate and constant batch size. We also find that methods which increase the batch size outperform those which decrease the learning rate when the decay rate of the degree of smoothing is set at $1/\sqrt{2}$.

## 2 Preliminaries

Let $\mathbb{N}$ be the set of non-negative integers. For $m\in\mathbb{N}\setminus\{0\}$, define $[m]:=\{1,2,\ldots,m\}$. Let $\mathbb{R}^{d}$ be a $d$-dimensional Euclidean space with inner product $\langle\cdot,\cdot\rangle$, which induces the norm $\|\cdot\|$. $I_{d}$ denotes a $d\times d$ identity matrix. $B(\bm{y};r)$ is the Euclidean closed ball of radius $r$ centered at $\bm{y}$, i.e., $B(\bm{y};r):=\left\{\bm{x}\in\mathbb{R}^{d}:\|\bm{x}-\bm{y}\|\leq r\right\}$. Let $\mathcal{N}(\bm{\mu};\Sigma)$ be a $d$-dimensional normal distribution with mean $\bm{\mu}\in\mathbb{R}^{d}$ and variance $\Sigma\in\mathbb{R}^{d\times d}$. The DNN is parameterized by a vector $\bm{x}\in\mathbb{R}^{d}$, which is optimized by minimizing the empirical loss function $f(\bm{x}):=\frac{1}{n}\sum_{i\in[n]}f_{i}(\bm{x})$, where $f_{i}(\bm{x})$ is the loss function for $\bm{x}\in\mathbb{R}^{d}$ and the $i$-th training data $\bm{z}_{i}$ $(i\in[n])$. Let $\xi$ be a random variable that does not depend on $\bm{x}\in\mathbb{R}^{d}$, and let $\mathbb{E}_{\xi}[X]$ denote the expectation with respect to $\xi$ of a random variable $X$. $\xi_{t,i}$ is a random variable generated from the $i$-th sampling at time $t$, and $\bm{\xi}_{t}:=(\xi_{t,1},\xi_{t,2},\ldots,\xi_{t,b})$ is independent of $(\bm{x}_{k})_{k=0}^{t}\subset\mathbb{R^{d}}$, where $b$ $(\leq n)$ is the batch size. The independence of $\bm{\xi}_{0},\bm{\xi}_{1},\ldots$ allows us to define the total expectation $\mathbb{E}$ as $\mathbb{E}=\mathbb{E}_{\bm{\xi}_{0}}\mathbb{E}_{\bm{\xi}_{1}}\cdots\mathbb{E}_
{\bm{\xi}_{t}}$. Let $\mathsf{G}_{\bm{\xi}_{t}}(\bm{x})$ be the stochastic gradient of $f(\cdot)$ at $\bm{x}\in\mathbb{R}^{d}$. The mini-batch $\mathcal{S}_{t}$ consists of $b$ samples at time $t$, and the mini-batch stochastic gradient of $f(\bm{x}_{t})$ for $\mathcal{S}_{t}$ is defined as $\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t}):=\frac{1}{b}\sum_{i\in[b]}\mathsf{G}_{
\xi_{t,i}}(\bm{x}_{t})$.

###### Definition 2.1 (Smoothed function) .

Given a function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, define $\hat{f}_{\delta}\colon\mathbb{R}^{d}\to\mathbb{R}$ to be the function obtained by smoothing $f$ as $\hat{f}_{\delta}(\bm{x}):=\mathbb{E}_{\bm{u}\sim\mathcal{N}\left(\bm{0};\frac{
1}{\sqrt{d}}I_{d}\right)}\left[f(\bm{x}-\delta\bm{u})\right],$ where $\delta>0$ represents the degree of smoothing and $\bm{u}$ is a random variable from a normal distribution. Also, $\bm{x}^{\star}:=\underset{\bm{x}\in\mathbb{R}^{d}}{\operatorname{argmin}}f(\bm
{x})\text{\ \ and \ }\bm{x}_{\delta}^{\star}:=\underset{\bm{x}\in\mathbb{R}^{d
}}{\operatorname{argmin}}\hat{f}_{\delta}(\bm{x}).$

The graduated optimization algorithm uses several smoothed functions with different noise levels. There are a total of $M$ noise levels $(\delta_{m})_{m\in[M]}$ and smoothed functions $(\hat{f}_{\delta_{m}})_{m\in[M]}$ in this paper. The largest noise level is $\delta_{1}$ and the smallest is $\delta_{M}$(see also Figure 1). For all $m\in[M]$, $(\hat{\bm{x}}_{t}^{(m)})_{t\in\mathbb{N}}$ is the sequence generated by an optimizer to minimize $\hat{f}_{\delta_{m}}$. Here, this paper refers to the graduated optimization approach with explicit smoothing operations (Definition 2.1) as “explicit graduated optimization” and to the graduated optimization approach with implicit smoothing operations as “implicit graduated optimization”. All previous studies (see Section 1.1) have considered explicit graduated optimization, and we consider implicit graduated optimization for the first time.

We make the following assumptions:

###### Assumption 2.1 .

(A1) $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is continuously differentiable and $L_{g}$-smooth, i.e., for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$, $\|\nabla f(\bm{x})-\nabla f(\bm{y})\|\leq L_{g}\|\bm{x}-\bm{y}\|.$ (A2) $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is an $L_{f}$-Lipschitz function, i.e., for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$, $\left|f(\bm{x})-f(\bm{y})\right|\leq L_{f}\|\bm{x}-\bm{y}\|.$ (A3) Let $(\bm{x}_{t})_{t\in\mathbb{N}}\subset\mathbb{R}^{d}$ be the sequence generated by SGD. (i) For each iteration $t$, $\mathbb{E}_{\xi_{t}}\left[\mathsf{G}_{\xi_{t}}(\bm{x}_{t})\right]=\nabla f(\bm
{x}_{t}).$ (ii) There exists a nonnegative constant $C^{2}$ such that $\mathbb{E}_{\xi_{t}}\left[\|\mathsf{G}_{\xi_{t}}(\bm{x}_{t})-\nabla f(\bm{x}_{
t})\|^{2}\right]\leq C^{2}.$ (A4) For each iteration $t$, SGD samples a mini-batch $\mathcal{S}_{t}\subset\mathcal{S}$ and estimates the full gradient $\nabla f$ as $\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t}):=\frac{1}{b}\sum_{i\in[b]}\mathsf{G}_{
\xi_{t,i}}(\bm{x}_{t})=\frac{1}{b}\sum_{\{i\colon\bm{z}_{i}\in\mathcal{S}_{t}
\}}\nabla f_{i}(\bm{x}_{t}).$

The proof of Lemmas 2.1 and 2.2 can be found in Appendix C.

###### Lemma 2.1 .

Suppose that (A3)(ii) and (A4) hold for all $t\in\mathbb{N}$; then, $\mathbb{E}_{\xi_{t}}\left[\|\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})-\nabla f(
\bm{x}_{t})\|^{2}\right]\leq\frac{C^{2}}{b}.$

###### Lemma 2.2 .

Let $\hat{f}_{\delta}$ be the smoothed version of $f$; then, for all $\bm{x}\in\mathbb{R}^{d}$,
$\left|\hat{f}_{\delta}(\bm{x})-f(\bm{x})\right|\leq\mathbb{E}_{\bm{u}}[\|\bm{u
}\|]\delta L_{f}.$

The graduated optimization algorithm is a method in which the degree of smoothing $\delta$ is gradually decreased. Let us consider the case where the degree of smoothing $\delta$ is constant throughout the training. Here, a larger degree of smoothing should be necessary to make many local optimal solutions of the objective function $f$ disappear and lead the optimizer to the global optimal solution. On the other hand, Lemma 2.2 implies that the larger the degree of smoothing is, the further away the smoothed function will be from the original function. Therefore, there should be an optimal value for the degree of smoothing that balances the tradeoffs, because if the degree of smoothing is too large, the original function is too damaged and thus cannot be optimized properly, and if it is too small, the function is not smoothed enough and the optimizer falls into a local optimal solution. This knowledge is useful because the degree of smoothing due to stochastic noise in SGD is determined by the learning rate and batch size (see Section 3), so when a constant learning rate and constant batch size are used, the degree of smoothing is constant throughout the training (see Section 4).

###### Definition 2.1 (Smoothed function) .

###### Assumption 2.1 .

###### Lemma 2.1 .

###### Lemma 2.2 .

## 3 SGD’s smoothing property

This section discusses the smoothing effect of using stochastic gradients. From Lemma 2.1, we have

$$ $\displaystyle\mathbb{E}_{\xi_{t}}\left[\left\|\bm{\omega}_{t}\right\|\right] \leq\frac{C}{\sqrt{b}},$ $$

due to $\bm{\omega}_{t}:=\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})$. The $\bm{\omega}_{t}$ for which this equation is satisfied can be expressed as $\bm{\omega}_{t}=\frac{C}{\sqrt{b}}\bm{u}_{t},$ where $\bm{u}_{t}\sim\mathcal{N}\left(\bm{0};\frac{1}{\sqrt{d}}I_{d}\right)$. Here, we have assumed that $\bm{\omega}_{t}$ in image classification tasks with CNN-based models follows a normal distribution in accordance with experimental observations in several previous studies (Zhang et al., ; Kunstner et al., ). Then, using Definition 2.1, we further transform equation (1) as follows:

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t+1}\right]$ $\displaystyle=\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t}\right]-\eta\nabla \mathbb{E}_{\bm{\omega}_{t}}\left[f(\bm{y}_{t}-\eta\bm{\omega}_{t})\right]$ $\displaystyle=\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t}\right]-\eta\nabla \mathbb{E}_{\bm{u}_{t}\sim\mathcal{N}\left(\bm{0};\frac{1}{\sqrt{d}}I_{d} \right)}\left[f\left(\bm{y}_{t}-\frac{\eta C}{\sqrt{b}}\bm{u}_{t}\right)\right]$ $\displaystyle=\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t}\right]-\eta\nabla \hat{f}_{\frac{\eta C}{\sqrt{b}}}(\bm{y}_{t}).$ (2) $$

This shows that $\mathbb{E}_{\bm{\omega}_{t}}\left[f(\bm{y}_{t}-\eta\bm{\omega}_{t})\right]$ is a smoothed version of $f$ with a noise level $\eta C/\sqrt{b}$ and its parameter $\bm{y}_{t}$ can be approximately updated by using the gradient descent to minimize $\hat{f}_{\frac{\eta C}{\sqrt{b}}}$. Therefore, we can say that the degree of smoothing $\delta$ by the stochastic noise $\bm{\omega}_{t}$ in SGD is determined by the learning rate $\eta$, the batch size $b$, and the variance of the stochastic gradient $C^{2}$ and that optimizing the function $f$ with SGD and optimizing the smoothed function $\hat{f}_{\frac{\eta C}{\sqrt{b}}}$ with GD are equivalent in the sense of expectation.

There are still more discoveries that can be made from the finding that simply by using SGD for optimization, the objective function is smoothed and the degree of smoothing is determined by $\delta=\eta C/\sqrt{b}$.

Why the Use of Large Batch Sizes Leads to Solutions Falling into Sharp Local Minima. It is known that training with large batch sizes leads to a persistent degradation of model generalization performance. In particular, (Keskar et al., ) showed experimentally that learning with large batch sizes leads to sharp local minima and worsens generalization performance. According to equation (2), using a large learning rate and/or a small batch size will make the function smoother. Thus, in using a small batch size, the sharp local minima will disappear through extensive smoothing, and SGD can reach a flat local minimum. Conversely, when using a large batch size, the smoothing is weak and the function is close to the original multimodal function, so it is easy for the solution to fall into a sharp local minimum. Thus, we have theoretical support for what (Keskar et al., ) showed experimentally, and our experiments have yielded similar results (see Figure 3 (a) and (e)).

Why Decaying Learning Rates and Increasing Batch Sizes are Superior to Fixed Learning Rates and Batch Sizes. From equation (2), the use of a decaying learning rate or increasing batch size during training is equivalent to decreasing the noise level of the smoothed function, so using a decaying learning rate or increasing the batch size is an implicit graduated optimization. Thus, we can say that using a decaying learning rate (Loshchilov & Hutter, ; Hundt et al., ; You et al., ; Lewkowycz, ) or increasing batch size (Byrd et al., ; Friedlander & Schmidt, ; Balles et al., ; De et al., ; Bottou et al., ; Smith et al., ) makes sense in terms of avoiding local minima and provides theoretical support for their experimental superiority.

## 4 Relationship between degree of smoothing, sharpness, and generalizability

The smoothness of the function, and in particular the sharpness of the function around the approximate solution to which the optimizer converged, has been well studied because it has been thought to be related to the generalizability of the model. In this section, we reinforce our theory by experimentally observing the relationship between the degree of smoothing and the sharpness of the function.

Several previous studies (Hochreiter & Schmidhuber, ; Keskar et al., ; Izmailov et al., ; Li et al., ; Andriushchenko et al., ) have addressed the relationship between the sharpness of the function around the approximate solution to which the optimizer converges and the generalization performance of the model. In particular, the hypothesis that flat local solutions have better generalizability than sharp local solutions is at the core of a series of discussions, and several previous studies (Keskar et al., ; Liang et al., ; Tsuzuku et al., ; Petzka et al., ; Kwon et al., ) have developed measures of sharpness to confirm this. In this paper, we use “adaptive sharpness” (Kwon et al., ; Andriushchenko et al., ) as a measure of the sharpness of the function that is invariant to network reparametrization, highly correlated with generalization, and generalizes several existing sharpness definitions. In accordance with (Andriushchenko et al., ), let $\mathcal{S}$ be a set of training data; for arbitrary model weights $\bm{w}\in\mathbb{R}^{d}$, the worst-case adaptive sharpness with radius $\rho\in\mathbb{R}$ and with respect to a vector $\bm{c}\in\mathbb{R}^{d}$ is defined as

$$ $\displaystyle S_{\text{max}}^{\rho}(\bm{w},\bm{c}):=\mathbb{E}_{\mathcal{S}} \left[\max_{\|\bm{\delta}\odot\bm{c}^{-1}\|_{p}\leq\rho}f(\bm{w}+\bm{\delta})- f(\bm{w})\right],$ $$

where $\odot/^{-1}$ denotes elementwise multiplication/inversion. Thus, the larger the sharpness value is, the sharper the function around the model weight $\bm{w}$ becomes, with a smaller sharpness leading to higher generalizability.

We trained ResNet18 (He et al., ) with the learning rate $\eta\in\{0.01,0.05,0.1,0.5\}$ and batch size $b\in\{2^{1},\ldots,2^{13}\}$ for 200 epochs on the CIFAR100 dataset (Krizhevsky, ) and then measured the worst-case $l_{\infty}$ adaptive sharpness of the obtained approximate solution with radius $\rho=0.0002$ and $\bm{c}=(1,1,\ldots,1)^{\top}\in\mathbb{R}^{d}$. Our implementation was based on (Andriushchenko et al., ) and the code used is available on our anonymous github. Figure 3 plots the relationship between measured sharpness and the batch size $b$ and the learning rate $\eta$ used for training as well as the degree of smoothing $\delta$ calculated from them. Figure 3 also plots the relationship between test accuracy, sharpness, and degree of smoothing. Three experiments were conducted per combination of learning rate and batch size, with a total of 156 data plots. The variance of the stochastic gradient $C^{2}$ included in the degree of smoothing $\delta=\eta C/\sqrt{b}$ used values estimated from theory and experiment (see Appendix B for details).

Figure: Figure 3: (a) Sharpness around the approximate solution after 200 epochs of ResNet18 training on the CIFAR100 dataset versus batch size used. (b) Sharpness versus learning rate used. (c) Sharpness versus degree of smoothing calculated from learning rate, batch size and estimated variance of the stochastic gradient. (d) Test accuracy after 200 epochs training versus sharpness. (e) Test accuracy versus degree of smoothing. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. The color shade in the scatter plots represents the batch size; the larger the batch size, the darker the color of the plotted points. “lr” means learning rate. The experimental results that make up the all graphs are all identical.
Refer to caption: x3.png

Figure 3 (a) shows that the larger the batch size is, the larger the sharpness value becomes, whereas (b) shows that the larger the learning rate is, the smaller the sharpness becomes, and (c) shows a greater the degree of smoothing for a smaller sharpness. These experimental results guarantee the our theoretical result that the degree of smoothing $\delta$ is proportional to the learning rate $\eta$ and inversely proportional to the batch size $b$, and they reinforce our theory that the quantity $\eta C/\sqrt{b}$ is the degree of smoothing of the function. Figure 3 (d) also shows that there is no clear correlation between the generalization performance of the model and the sharpness around the approximate solution. This result is also consistent with previous study (Andriushchenko et al., ). On the other hand, Figure 3 (e) shows an excellent correlation between generalization performance and the degree of smoothing; generalization performance is clearly a concave function with respect to the degree of smoothing. Thus, a degree of smoothing that is neither too large nor too small leads to high generalization performance. This experimental observation can be supported theoretically (see Lemma 2.2). That is, if the degree of smoothing is a constant throughout the training, then there should be an optimal value for the loss function value or test accuracy; for the training of ResNet18 on the CIFAR100 dataset, for example, 0.1 to 1 was the desired value (see Figure 3 (e)). For degrees of smoothing smaller than 0.1, the generalization performance is not good because the function is not sufficiently smoothed so that locally optimal solutions with sharp neighborhoods do not disappear, and the optimizer falls into this trap. On the other hand, a degree of smoothing greater than 1 leads to excessive smoothing and smoothed function becomes too far away from the original function to be properly optimized; the generalization performance is not considered excellent. In addition, the optimal combination of learning rate and batch size that practitioners search for by using grid searches or other methods when training models can be said to be a search for the optimal degree of smoothing. If the optimal degree of smoothing can be better understood, the huge computational cost of the search could be reduced.

(Andriushchenko et al., ) observed the relationship between sharpness and generalization performance in extensive experiments and found that they were largely uncorrelated, suggesting that the sharpnesss may not be a good indicator of generalization performance and that one should avoid blanket statements like “flatter minima generalize better”. Figure 3 (d) and (e) show that there is no correlation between sharpness and generalization performance, as in previous study, while there is a correlation between degree of smoothing and generalization performance. Therefore, we can say that degree of smoothing may be a good indicator to theoretically evaluate generalization performance, and it may be too early to say that “flatter minima generalize better” is invalid.

## 5 Implicit Graduated Optimization

In this section, we construct an implicit graduated optimization algorithm that varies the learning rate $\eta$ and batch size $b$ so that the degree of smoothing $\delta=\eta C/\sqrt{b}$ by stochastic noise in SGD gradually decreases and then analyze its convergence.

### 5.1 Analysis of Implicit Graduated Optimization Algorithm

In order to analyze the graduated optimization algorithm, Hazan et al. defined $\sigma$-nice functions (see Definition 5.1), a family of nonconvex functions that has favorable conditions for a graduated optimization algorithm to converge to a global optimal solution (Hazan et al., ).

###### Definition 5.1 ( $\sigma$ -nice function (Hazan et al., 2016 ) ) .

Let $M\in\mathbb{N}$ and $m\in[M]$. A function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is said to be $\sigma$-nice if the following two conditions hold:

(i) For all $\delta_{m}>0$ and all $\bm{x}_{\delta_{m}}^{\star}$, there exists $\bm{x}_{\delta_{m+1}}^{\star}$ such that: $\left\|\bm{x}_{\delta_{m}}^{\star}-\bm{x}_{\delta_{m+1}}^{\star}\right\|\leq
\delta_{m+1}:=\frac{\delta_{m}}{2}$.

(ii) For all $\delta_{m}>0$, the function $\hat{f}_{\delta_{m}}(\bm{x})$ over $N(\bm{x}_{\delta_{m}}^{\star};3\delta_{m})$ is $\sigma$-strongly convex.

The $\sigma$-nice property implies that optimizing the smoothed function $\hat{f}_{\delta_{m}}$ is a good start for optimizing the next smoothed function $\hat{f}_{\delta_{m+1}}$, which has been shown to be sufficient for graduated optimization (Hazan et al., ). We will take this route and consider an implicit graduated optimization algorithm for $\sigma$-nice functions.

Algorithm 1 embodies the framework of implicit graduated optimization with SGD for $\sigma$-nice functions, while Algorithm 2 is used to optimize each smoothed function; it should be GD (see (2)). Note that our implicit graduated optimization (Algorithm 1) is achieved by SGD with decaying learning rate and/or increasing batch size.

Figure: Algorithm 1 Implicit Graduated Optimization

From the definition of $\sigma$-nice function, the smoothed function $\hat{f}_{\delta_{m}}$ is $\sigma$-strongly convex in $B(\bm{x}_{\delta_{m}}^{\star};3\delta_{m})$. Also, the learning rate used by Algorithm 2 to optimize $\hat{f}_{\delta_{m}}$ should always be constant. Therefore, let us now consider the convergence of GD with a constant learning rate for a $\sigma$-strongly convex function $\hat{f}_{\delta_{m}}$. The proof of Theorem 5.1 is in Appendix F.1.

###### Theorem 5.1 (Convergence analysis of Algorithm 2 ) .

Suppose that $\hat{f}_{\delta_{m}}\colon\mathbb{R}^{d}\to\mathbb{R}$ is a $\sigma$-strongly convex and $L_{g}$-smooth and $\eta<\min\left\{\frac{1}{\sigma},\frac{2}{L_{g}}\right\}$. Then, the sequence $(\hat{\bm{x}}_{t}^{(m)})_{t\in\mathbb{N}}$ generated by Algorithm 2 satisfies

$$ $\displaystyle\min_{t\in[T]}\hat{f}_{\delta_{m}}\left(\hat{\bm{x}}_{t}^{(m)} \right)-\hat{f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^{\star})\leq\frac{H_{m}}{T}= \mathcal{O}\left(\frac{1}{T}\right),$ (3) $$

where $H_{m}:=\frac{9\left(1-\sigma\eta\right)\delta_{m}^{2}}{2\eta}+\frac{3L_{f}
\delta_{m}}{\eta\left(2-L_{g}\eta\right)}$ is nonnegative constant.

Theorem 5.1 shows that Algorithm 2 can reach an $\epsilon_{m}$-neighborhood of the optimal solution $\bm{x}_{\delta_{m}}^{\star}$ of $\hat{f}_{\delta_{m}}$ in approximately $T_{m}:=H_{m}/\epsilon_{m}$ iterations.
The next proposition is crucial to the success of Algorithm 1 and guarantees the soundness of the $\sigma$-nice function (The proof is in Appendix F.2).

###### Proposition 5.1 .

Let $f$ be a $\sigma$-nice function and $\delta_{m+1}:=\gamma\delta_{m}$. Suppose that $\gamma\in[0.5,1)$ and $\bm{x}_{1}\in B(\bm{x}_{\delta_{1}}^{\star};3\delta_{1})$. Then for all $m\in[M]$, $\|\bm{x}_{m}-\bm{x}_{\delta_{m}}^{\star}\|<3\delta_{m}.$

$\bm{x}_{m}$ is the approximate solution obtained by optimization of the smoothed function $\hat{f}_{\delta_{m-1}}$ with Algorithm 2 and is the initial point of optimization of the next smoothed function $\hat{f}_{\delta_{m}}$. Therefore, Proposition 5.1 implies that $\gamma\in[0.5,1)$ must hold for the initial point of optimization of $\hat{f}_{\delta_{m}}$ to be contained in the strongly convex region of $\hat{f}_{\delta_{m}}$. In the definition of the $\sigma$-nice function, $\gamma$ is set to $0.5$. Therefore, from Theorem 5.1 and Proposition 5.1, if $f$ is a $\sigma$-nice function and $\bm{x}_{1}\in B(\bm{x}_{\delta_{1}}^{\star};3\delta_{1})$ holds, the sequence $(\bm{x}_{m})_{m\in[M]}$ generated by Algorithm 1 never goes outside of the $\sigma$-strongly convex region $B(\bm{x}_{\delta_{m}}^{\star};3\delta_{m})$ of each smoothed function $\hat{f}_{\delta_{m}}$ $(m\in[M])$ .

The next theorem guarantees the convergence of Algorithm 1 with the $\sigma$-nice function (The proof of Theorem 5.2 is in Appendix F.3).

###### Theorem 5.2 (Convergence analysis of Algorithm 1 ) .

Let $\epsilon\in(0,1)$, $d\in\mathbb{N}$ be sufficiently large, and $f\colon\mathbb{R}^{d}\to\mathbb{R}$ be an $L_{f}$-Lipschitz $\sigma$-nice function. Suppose that we run Algorithm 1; then after $\mathcal{O}\left(1/\epsilon^{2}\right)$ rounds, the algorithm reaches an $\epsilon$-neighborhood of the global optimal solution $\bm{x}^{\star}$.

Note that Theorem 5.2 provides a total complexity including those of Algorithm 1 and Algorithm 2, because Algorithm 1 uses Algorithm 2 at each $m\in[M]$.

###### Definition 5.1 ( σ 𝜎 \sigma italic_σ -nice function (Hazan et al., 2016 ) ) .

###### Theorem 5.1 (Convergence analysis of Algorithm 2 ) .

###### Proposition 5.1 .

###### Theorem 5.2 (Convergence analysis of Algorithm 1 ) .

### 5.2 Numerical Results

The experimental environment is in Appendix G and the code is available at [https://anonymous.4open.science/r/new-sigma-nice](https://anonymous.4open.science/r/new-sigma-nice).

We compared four types of SGD for image classification: 1. constant learning rate and constant batch size, 2. decaying learning rate and constant batch size, 3. constant learning rate and increasing batch size, 4. decaying learning rate and increasing batch size, in training ResNet34 (He et al., ) on the ImageNet dataset (Deng et al., ) (Figure 4), ResNet18 on the CIFAR100 dataset (Figure 5 in Appendix G), and WideResNet-28-10 (Zagoruyko & Komodakis, ) on the CIFAR100 dataset (Figure 6 in Appendix G).
Therefore, methods 2, 3, and 4 are our Algorithm 1.
All experiments were run for 200 epochs. In methods 2, 3, and 4, the noise decreased every 40 epochs, with a common decay rate of $1/\sqrt{2}$. That is, every 40 epochs, the learning rate of method 2 was multiplied by $1/\sqrt{2}$, the batch size of method 3 was doubled, and the learning rate and batch size of method 4 were respectively multiplied by $\sqrt{3}/2$ and $1.5$. Note that this $1/\sqrt{2}$ decay rate is $\gamma$ in Algorithm 1 and it satisfies the condition in Proposition 5.1. The initial learning rate was 0.1 for all methods, which was determined by performing a grid search among $\left[0.01,0.1,1.0,10\right]$. The noise reduction interval was every 40 epochs, which was determined by performing a grid search among $\left[10,20,25,40,50,100\right]$. A history of the learning rate or batch size for each method is provided in the caption of each figure.

Figure: Figure 4: Accuracy score for the testing and loss function value for training versus the number of epochs (left) and the number of parameter updates (right) in training ResNet34 on the ImageNet dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and batch size were fixed at 0.1 and 256, respectively. In method 2, the learning rate was decreased every 40 epochs as $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 256. In method 3, the learning rate was fixed at 0.1, and the batch size was increased as $\left[32,64,128,256,512\right]$. In method 4, the learning rate was decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size was increased as $\left[32,48,72,108,162\right]$.
Refer to caption: x4.png

For methods 2, 3, and 4, the decay rates are all $1/\sqrt{2}$, and the decay intervals are all 40 epochs, so throughout the training, the three methods should theoretically be optimizing the exact same five smoothed functions in sequence. Nevertheless, the local solutions reached by each of the three methods are not exactly the same. All results indicate that method 3 is superior to method 2 and that method 4 is superior to method 3 in both test accuracy and training loss function values. This difference can be attributed to the different learning rates used to optimize each smoothing function. Among methods 2, 3, and 4, method 3, which does not decay the learning rate, maintains the highest learning rate 0.1, followed by method 4 and method 2. In all graphs, the loss function values are always small in that order; i.e., the larger the learning rate is, the lower loss function values become. Therefore, we can say that the noise level $\delta$, expressed as $\frac{\eta C}{\sqrt{b}}$, needs to be reduced, while the learning rate $\eta$ needs to remain as large as possible. Alternatively, if the learning rate is small, then a large number of iterations are required. Thus, for the same rate of change and the same number of epochs, an increasing batch size is superior to a decreasing learning rate because it can maintain a large learning rate and can be made to iterate a lot when the batch size is small.

Theoretically, the noise level $\delta_{m}$ should gradually decrease and become zero at the end, so in our algorithm 1, the learning rate $\eta_{m}$ should be zero at the end or the batch size $b_{m}$ should match the number of data sets at the end. However, if the learning rate is 0, training cannot proceed, and if the batch size is close to a full batch, it is not feasible from a computational point of view. For this reason, the experiments described in this paper are not fully graduated optimizations; i.e., full global optimization is not achieved. In fact, the last batch size used by method 2 is around 128 to 512, which is far from a full batch. Therefore, the solution reached in this experiment is the optimal one for a function that has been smoothed to some extent, and to achieve a global optimization of the DNN, it is necessary to increase only the batch size to eventually reach a full batch, or increase the number of iterations accordingly while increasing the batch size and decaying the learning rate.

## 6 Conclusion

We proved that SGD with a mini-batch stochastic gradient has the effect of smoothing the function, and the degree of smoothing is greater with larger learning rates and smaller batch sizes. This shows theoretically that smoothing with large batch sizes is makes it easy to fall into sharp local minima and that using a decaying learning rate and/or increasing batch size is implicitly graduated optimization, which makes sense in the sense that it avoids local optimal solutions. Based on these findings, we proposed a new graduated optimization algorithm that uses a decaying learning rate and increasing batch size and analyzed it. We conducted experiments whose results showed the superiority of our recommended framework for image classification tasks on CIFAR100 and ImageNet. In addition, we observed that the degree of smoothing of the function due to stochastic noise in SGD can express the degree of smoothness of the function as well as sharpness does, and that the degree of smoothing is a good indicator of the generalization performance of the model.

## 7 Previous studies and our novelty

As shown in equation (1), Kleinberg et al. suggested that stochastic noise in SGD smooths the objective function (Kleinberg et al., ), but the degree to which it did so was not analyzed. We theoretically derived the degree of smoothing and experimentally observed the relationship with sharpness to ensure its correctness, which is a novel and valuable result.

We have shown that the degree of smoothing by stochastic noise in SGD is determined by $\delta=\eta C/\sqrt{b}$. This result may remind readers of previous studies (Goyal et al., ; Smith et al., ; Xie et al., ) that investigated the dynamics of SGD and demonstrated how the ratio $\eta/b$ affects the training dynamics. We should emphasize that our $\eta/\sqrt{b}$ is derived from a completely different point of view, and in particular, the finding that the quantity $\eta C/\sqrt{b}$ contributes to the smoothing of the objective function can only be obtained from our theory.

We use the $\sigma$-nice function proposed by (Hazan et al., ) to analyze the implicit graduated optimization algorithm. Technically, the difference between our work and theirs is that they optimize each smoothed function with projected gradient descent with a decaying learning rate, whereas we optimize with gradient descent with a constant learning rate given our theoretical motivation (see (2)). Furthermore, all previous studies (see Section 1.1), including the work of Hazan et al. consider explicit graduated optimization. Our implicit graduated optimization with stochastic noise in the optimizer is a completely new idea, and this is the first paper to apply the graduated optimization algorithm to the training of deep learning models on a modern dataset such as ImageNet.

## Appendix A Derivation of equation ( 1 )

Let $\bm{y}_{t}$ be the parameter updated by gradient descent (GD) and $\bm{x}_{t+1}$ be the parameter updated by SGD at time $t$, i.e.,

$$ $\displaystyle\bm{y}_{t}$ $\displaystyle:=\bm{x}_{t}-\eta\nabla f(\bm{x}_{t}),$ $\displaystyle\bm{x}_{t+1}$ $\displaystyle:=\bm{x}_{t}-\eta\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})$ $\displaystyle=\bm{x}_{t}-\eta(\nabla f(\bm{x}_{t})+\bm{\omega}_{t}).$ $$

Then, we have

$$ $\displaystyle\bm{x}_{t+1}$ $\displaystyle:=\bm{x}_{t}-\eta\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})$ $\displaystyle=\left(\bm{y}_{t}+\eta\nabla f(\bm{x}_{t})\right)-\eta\nabla f_{ \mathcal{S}_{t}}(\bm{x}_{t})$ $\displaystyle=\bm{y}_{t}-\eta\bm{\omega}_{t},$ (4) $$

from $\bm{\omega}_{t}:=\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})$. Hence,

$$ $\displaystyle\bm{y}_{t+1}$ $\displaystyle=\bm{x}_{t+1}-\eta\nabla f(\bm{x}_{t+1})$ $\displaystyle=\bm{y}_{t}-\eta\bm{\omega}_{t}-\eta\nabla f(\bm{y}_{t}-\eta\bm{ \omega}_{t}).$ $$

By taking the expectation with respect to $\bm{\omega}_{t}$ on both sides, we have, from $\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{\omega}_{t}\right]=\bm{0}$,

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{y}_{t+1}\right]=\mathbb{E}_ {\bm{\omega}_{t}}\left[\bm{y}_{t}\right]-\eta\nabla\mathbb{E}_{\bm{\omega}_{t} }\left[f(\bm{y}_{t}-\eta\bm{\omega}_{t})\right],$ $$

where we have used $\mathbb{E}_{\bm{\omega}_{t}}\left[\nabla f(\bm{y}_{t}-\eta\bm{\omega}_{t})
\right]=\nabla\mathbb{E}_{\bm{\omega}_{t}}\left[f(\bm{y}_{t}-\eta\bm{\omega}_{
t})\right]$, which holds for a Lipschitz-continuous and differentiable $f$ (Shapiro et al., , Theorem 7.49). In addition, from (4) and $\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{\omega}_{t}\right]=\bm{0}$, we obtain

$$ $\displaystyle\mathbb{E}_{\bm{\omega}_{t}}\left[\bm{x}_{t+1}\right]=\bm{y}_{t}.$ $$

Therefore, on average, the parameter $\bm{x}_{t+1}$ of the function $f$ arrived at by SGD coincides with the parameter $\bm{y}_{t}$ of the smoothed function $\hat{f}(\bm{y}_{t}):=\mathbb{E}_{\bm{\omega}_{t}}\left[f(\bm{y}_{t}-\eta\bm{
\omega}_{t})\right]$ arrived at by GD.

## Appendix B Estimation of variance of stochastic gradient

In Section 4, we need to estimate the variance $C^{2}$ of the stochastic gradient in order to plot the degree of smoothing $\delta=\eta C/\sqrt{b}$. In general, this is difficult to measure, but several previous studies (Imaizumi & Iiduka, ; Sato & Iiduka, ) have provided the following estimating formula. For some $\epsilon>0$, when training until $\frac{1}{T}\sum_{k=1}^{T}\mathbb{E}\left[\|\nabla f(\bm{x}_{k})\|^{2}\right]
\leq\epsilon^{2}$, the variance of the stochastic gradient can be estimated as

$$ $\displaystyle C^{2}<\frac{b^{\star}\epsilon^{2}}{\eta},$ $$

where $b^{\star}$ is the batch size that minimizes the amount of computation required for training and $\eta$ is learning rate used in training. We determined the stopping condition $\epsilon$ for each learning rate, measured the batch size that minimized the computational complexity required for the gradient norm of the preceding $t$ steps at time $t$ to average less than $\epsilon$ in training ResNet18 on the CIFAR100 dataset, and estimated the variance of the stochastic gradient by using an estimation formula (see Table 1).

**Table 1: Learning rate $\eta$ and threshold $\epsilon$ used for training, measured optimal batch size $b^{\star}$ and estimated variance of the stochastic gradient $C^{2}$.**
| $\eta$ | $\epsilon$ | $b^{\star}$ | $C^{2}$ |
| --- | --- | --- | --- |
| 0.01 | 1.0 | $2^{7}$ | 12800 |
| 0.05 | 0.5 | $2^{9}$ | 1280 |
| 0.1 | 0.5 | $2^{10}$ | 1280 |
| 0.5 | 0.5 | $2^{10}$ | 256 |

## Appendix C Proofs of the Lemmas in Section 2

### C.1 Proof of Lemma 2.1

###### Proof.

(A3)(ii) and (A4) guarantee that

$$ $\displaystyle\mathbb{E}_{\xi_{t}}\left[\|\nabla f_{\mathcal{S}_{t}}(\bm{x}_{t} )-\nabla f(\bm{x}_{t})\|^{2}\right]$ $\displaystyle=\mathbb{E}_{\xi_{t}}\left[\left\|\frac{1}{b}\sum_{i=1}^{b}{ \mathsf{G}_{\xi_{t,i}}(\bm{x}_{t})}-\nabla f(\bm{x}_{t})\right\|^{2}\right]$ $\displaystyle=\mathbb{E}_{\xi_{t}}\left[\left\|\frac{1}{b}\sum_{i=1}^{b}{ \mathsf{G}_{\xi_{t,i}}(\bm{x}_{t})}-\frac{1}{b}\sum_{i=1}^{b}\nabla f(\bm{x}_{ t})\right\|^{2}\right]$ $\displaystyle=\mathbb{E}_{\xi_{t}}\left[\left\|\frac{1}{b}\sum_{i=1}^{b}\left( {\mathsf{G}_{\xi_{t,i}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})}\right)\right\|^{2}\right]$ $\displaystyle=\frac{1}{b^{2}}\mathbb{E}_{\xi_{t}}\left[\left\|\sum_{i=1}^{b} \left({\mathsf{G}_{\xi_{t,i}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})}\right)\right\| ^{2}\right]$ $\displaystyle=\frac{1}{b^{2}}\mathbb{E}_{\xi_{t}}\left[\sum_{i=1}^{b}\left\|{ \mathsf{G}_{\xi_{t,i}}(\bm{x}_{t})-\nabla f(\bm{x}_{t})}\right\|^{2}\right]$ $\displaystyle\leq\frac{C^{2}}{b}.$ $$

This completes the proof.
∎

###### Proof.

### C.2 Proof of Lemma 2.2

###### Proof.

From Definition 2.1 and (A2), we have, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\left|\hat{f}_{\delta}(\bm{x})-f(\bm{x})\right|$ $\displaystyle=\left|\mathbb{E}_{\bm{u}}\left[f(\bm{x}-\delta\bm{u})\right]-f( \bm{x})\right|$ $\displaystyle=\left|\mathbb{E}_{\bm{u}}\left[f(\bm{x}-\delta\bm{u})-f(\bm{x}) \right]\right|$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[\left|f(\bm{x}-\delta\bm{u})-f(\bm{x })\right|\right]$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[L_{f}\|(\bm{x}-\delta\bm{u})-\bm{x} \|\right]$ $\displaystyle=\delta L_{f}\mathbb{E}_{\bm{u}}\left[\|\bm{u}\|\right].$ $$

This completes the proof.
∎

Note that, since the standard normal distribution in high dimensions $d$ is close to a uniform distribution on a sphere of radius $\sqrt{d}$ (Vershynin, , Section 3.3.3), in deep neural network training, for all $\bm{u}\sim\mathcal{N}\left(\bm{0};\frac{1}{\sqrt{d}}I_{d}\right)$,

$$ $\displaystyle\|\bm{u}\|\approx 1.$ $$

Therefore, we have

$$ $\displaystyle\left|\hat{f}_{\delta}(\bm{x})-f(\bm{x})\right|\leq\delta L_{f}.$ (5) $$

###### Proof.

## Appendix D Lemmas on smoothed function

The following Lemmas concern the properties of smoothed functions $\hat{f}_{\delta}$.

###### Lemma D.1 .

Suppose that (A1) holds; then, $\hat{f}_{\delta}$ defined by Definition 2.1 is also $L_{g}$-smooth; i.e., for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\left\|\nabla\hat{f}_{\delta}(\bm{x})-\nabla\hat{f}_{\delta}(\bm{ y})\right\|\leq L_{g}\|\bm{x}-\bm{y}\|.$ $$

###### Proof.

From Definition 2.1 and (A1), we have, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\left\|\nabla\hat{f}_{\delta}(\bm{x})-\nabla\hat{f}_{\delta}(\bm{ y})\right\|$ $\displaystyle=\left\|\nabla\mathbb{E}_{\bm{u}}\left[f(\bm{x}-\delta\bm{u}) \right]-\nabla\mathbb{E}_{\bm{u}}\left[f(\bm{y}-\delta\bm{u})\right]\right\|$ $\displaystyle=\left\|\mathbb{E}_{\bm{u}}\left[\nabla f(\bm{x}-\delta\bm{u}) \right]-\mathbb{E}_{\bm{u}}\left[\nabla f(\bm{y}-\delta\bm{u})\right]\right\|$ $\displaystyle=\left\|\mathbb{E}_{\bm{u}}\left[\nabla f(\bm{x}-\delta\bm{u})- \nabla f(\bm{y}-\delta\bm{u})\right]\right\|$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[\left\|\nabla f(\bm{x}-\delta\bm{u}) -\nabla f(\bm{y}-\delta\bm{u})\right\|\right]$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[L_{g}\left\|(\bm{x}-\delta\bm{u})-( \bm{y}-\delta\bm{u})\right\|\right]$ $\displaystyle=\mathbb{E}_{\bm{u}}\left[L_{g}\left\|\bm{x}-\bm{y}\right\|\right]$ $\displaystyle=L_{g}\|\bm{x}-\bm{y}\|.$ $$

This completes the proof.
∎

###### Lemma D.2 .

Suppose that (A2) holds; then $\hat{f}_{\delta}$ is also an $L_{f}$-Lipschitz function; i.e., for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\left|\hat{f}_{\delta}(\bm{x})-\hat{f}_{\delta}(\bm{y})\right| \leq L_{f}\|\bm{x}-\bm{y}\|.$ $$

###### Proof.

From Definition 2.1 and (A2), we have, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\left|\hat{f}_{\delta}(\bm{x})-\hat{f}_{\delta}(\bm{y})\right|$ $\displaystyle=\left|\mathbb{E}_{\bm{u}}\left[f(\bm{x}-\delta\bm{u})\right]- \mathbb{E}_{\bm{u}}\left[f(\bm{y}-\delta\bm{u})\right]\right|$ $\displaystyle=\left|\mathbb{E}_{\bm{u}}\left[f(\bm{x}-\delta\bm{u})-f(\bm{y}- \delta\bm{u})\right]\right|$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[\left|f(\bm{x}-\delta\bm{u})-f(\bm{y }-\delta\bm{u})\right|\right]$ $\displaystyle\leq\mathbb{E}_{\bm{u}}\left[L_{f}\|(\bm{x}-\delta\bm{u})-(\bm{y} -\delta\bm{u})\|\right]$ $\displaystyle=\mathbb{E}_{\bm{u}}\left[L_{f}\left\|\bm{x}-\bm{y}\right\|\right]$ $\displaystyle=L_{f}\|\bm{x}-\bm{y}\|.$ $$

This completes the proof.
∎

Lemmas D.1 and D.2 imply that the Lipschitz constants $L_{f}$ of the original function $f$ and $L_{g}$ of $\nabla f$ are taken over by the smoothed function $\hat{f}_{\delta}$ and its gradient $\nabla\hat{f}_{\delta}$ for all $\delta\in\mathbb{R}$.

###### Lemma D.1 .

###### Proof.

###### Lemma D.2 .

###### Proof.

## Appendix E Lemmas used in the proofs of the theorems

###### Lemma E.1 .

Suppose that $\hat{f}_{\delta_{m}}\colon\mathbb{R}^{d}\to\mathbb{R}$ is $\sigma$-strongly convex and $\hat{\bm{x}}_{t+1}^{(m)}:=\hat{\bm{x}}_{t}^{(m)}-\eta_{t}\bm{g}_{t}$. Then, for all $t\in\mathbb{N}$,

$$ $\displaystyle\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\hat{f}_{\delta_{m}} (\bm{x}^{\star})\leq\frac{1-\sigma\eta_{t}}{2\eta_{t}}X_{t}-\frac{1}{2\eta_{t} }X_{t+1}+\frac{\eta_{t}}{2}\|\bm{g}_{t}\|^{2},$ $$

where $\bm{g}_{t}:=\nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})$, $X_{t}:=\|\hat{\bm{x}}_{t}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}$, and $\bm{x}_{\delta_{m}}^{\star}$ is the global minimizer of $\hat{f}_{\delta_{m}}$.

###### Proof.

Let $t\in\mathbb{N}$. The definition of $\hat{\bm{x}}_{t+1}^{(m)}$ guarantees that

$$ $\displaystyle\|\hat{\bm{x}}_{t+1}^{(m)}-\bm{x}^{\star}\|^{2}$ $\displaystyle=\|(\hat{\bm{x}}_{t}^{(m)}-\eta_{t}\bm{g}_{t})-\bm{x}^{\star}\|^{2}$ $\displaystyle=\|\hat{\bm{x}}_{t}^{(m)}-\bm{x}^{\star}\|^{2}-2\eta_{t}\langle \hat{\bm{x}}_{t}^{(m)}-\bm{x}_{\delta_{m}}^{\star},\bm{g}_{t}\rangle+\eta_{t}^ {2}\|\bm{g}_{t}\|^{2}.$ $$

From the $\sigma$-strong convexity of $\hat{f}_{\delta_{m}}$,

$$ $\displaystyle\|\hat{\bm{x}}_{t+1}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}\leq \|\hat{\bm{x}}_{t}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}+2\eta_{t}\left(\hat {f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^{\star})-\hat{f}_{\delta_{m}}(\hat{\bm{x} }_{t}^{(m)})-\frac{\sigma}{2}\|\hat{\bm{x}}_{t}^{(m)}-\bm{x}_{\delta_{m}}^{ \star}\|^{2}\right)+\eta_{t}^{2}\|\bm{g}_{t}\|^{2}.$ $$

Hence,

$$ $\displaystyle\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\hat{f}_{\delta_{m}} (\bm{x}_{\delta_{m}}^{\star})\leq\frac{1-\sigma\eta_{t}}{2\eta_{t}}\|\hat{\bm{ x}}_{t}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}-\frac{1}{2\eta_{t}}\|\hat{\bm{ x}}_{t+1}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}+\frac{\eta_{t}}{2}\|\bm{g}_{ t}\|^{2}.$ $$

This completes the proof.
∎

###### Lemma E.2 .

Suppose that $\hat{f}_{\delta_{m}}\colon\mathbb{R}^{d}\to\mathbb{R}$ is $L_{g}$-smooth and $\hat{\bm{x}}_{t+1}^{(m)}:=\hat{\bm{x}}_{t}^{(m)}-\eta_{t}\bm{g}_{t}$. Then, for all $t\in\mathbb{N}$,

$$ $\displaystyle\eta_{t}\left(1-\frac{L_{g}\eta_{t}}{2}\right)\|\nabla\hat{f}_{ \delta_{m}}(\hat{\bm{x}}_{t}^{(m)})\|^{2}\leq\hat{f}_{\delta_{m}}(\hat{\bm{x}} _{t}^{(m)})-\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t+1}^{(m)}).$ $$

where $\bm{g}_{t}:=\nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})$ and $\bm{x}_{\delta_{m}}^{\star}$ is the global minimizer of $\hat{f}_{\delta_{m}}$.

###### Proof.

From the $L_{g}$-smoothness of the $\hat{f}_{\delta_{m}}$ and the definition of $\hat{\bm{x}}_{t+1}^{(m)}$, we have, for all $t\in\mathbb{N}$,

$$ $\displaystyle\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t+1}^{(m)})$ $\displaystyle\leq\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})+\langle\nabla \hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)}),\hat{\bm{x}}_{t+1}^{(m)}-\hat{\bm {x}}_{t}^{(m)}\rangle+\frac{L_{g}}{2}\|\hat{\bm{x}}_{t+1}^{(m)}-\hat{\bm{x}}_{ t}^{(m)}\|^{2}$ $\displaystyle=\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\eta_{t}\langle \nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)}),\bm{g}_{t}\rangle+\frac{L_{ g}\eta_{t}^{2}}{2}\|\bm{g}_{t}\|^{2}$ $\displaystyle\leq\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\eta_{t}\left(1- \frac{L_{g}\eta_{t}}{2}\right)\|\nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{( m)})\|^{2}.$ $$

Therefore, we have

$$ $\displaystyle\eta_{t}\left(1-\frac{L_{g}\eta_{t}}{2}\right)\|\nabla\hat{f}_{ \delta_{m}}(\hat{\bm{x}}_{t}^{(m)})\|^{2}\leq\hat{f}_{\delta_{m}}(\hat{\bm{x}} _{t}^{(m)})-\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t+1}^{(m)}).$ $$

This completes the proof.
∎

###### Lemma E.3 .

Suppose that $\hat{f}_{\delta_{m}}\colon\mathbb{R}^{d}\to\mathbb{R}$ is $L_{g}$-smooth, $\hat{\bm{x}}_{t+1}^{(m)}:=\hat{\bm{x}}_{t}^{(m)}-\eta_{t}\bm{g}_{t}$, and $\eta_{t}:=\eta<\frac{2}{L_{g}}$. Then, for all $t\in\mathbb{N}$,

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\|\bm{g}_{t}\|^{2}\leq\frac{6L_{f}\delta _{m}}{\eta\left(2-L_{g}\eta\right)T},$ $$

where $\bm{g}_{t}:=\nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})$ and $\bm{x}_{\delta_{m}}^{\star}$ is the global minimizer of $\hat{f}_{\delta_{m}}$.

###### Proof.

According to Lemma E.2, we have

$$ $\displaystyle\eta\left(1-\frac{L_{g}\eta}{2}\right)\|\nabla F(\bm{x}_{t}^{(m)} )\|^{2}\leq\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\hat{f}_{\delta_{m}}( \hat{\bm{x}}_{t+1}^{(m)}).$ $$

Summing over $t$, we find that

$$ $\displaystyle\eta\left(1-\frac{L_{g}\eta}{2}\right)\frac{1}{T}\sum_{t=1}^{T}\| \nabla\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})\|^{2}\leq\frac{\hat{f}_{ \delta_{m}}(\hat{\bm{x}}_{1}^{(m)})-\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{T+1}^{( m)})}{T}.$ $$

Hence, from $\eta<\frac{2}{L_{g}}$,

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\|\bm{g}_{t}\|^{2}=\frac{2\left(\hat{f}_ {\delta_{m}}(\hat{\bm{x}}_{1}^{(m)})-\hat{f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^ {\star})\right)}{\eta\left(2-L_{g}\eta\right)T}.$ $$

Here, from the $L_{f}$-Lipschitz continuity of $\hat{f}_{\delta_{m}}$,

$$ $\displaystyle\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{1}^{(m)})-\hat{f}_{\delta_{m}} (\bm{x}_{\delta_{m}}^{\star})$ $\displaystyle\leq L_{f}\|\hat{\bm{x}}_{1}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|$ $\displaystyle\leq 3L_{f}\delta_{m},$ $$

where we have used $\bm{x}_{1}^{(m)}\in B(\bm{x}_{\delta_{m}}^{\star};3\delta_{m})$. Therefore, we have

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\|\bm{g}_{t}\|^{2}=\frac{6L_{f}\delta_{m }}{\eta\left(2-L_{g}\eta\right)T}.$ $$

This completes the proof.
∎

###### Lemma E.1 .

###### Proof.

###### Lemma E.2 .

###### Proof.

###### Lemma E.3 .

###### Proof.

## Appendix F Proof of the Theorems and Propositions

### F.1 Proof of Theorem 5.1

###### Proof.

Lemma E.1 guarantees that

$$ $\displaystyle\hat{f}_{\delta_{m}}(\hat{\bm{x}}_{t}^{(m)})-\hat{f}_{\delta_{m}} (\bm{x}_{\delta_{m}}^{\star})$ $\displaystyle\leq\frac{1-\sigma\eta_{t}}{2\eta_{t}}X_{t}-\frac{1}{2\eta_{t}}X_ {t+1}+\frac{\eta_{t}}{2}\|\bm{g}_{t}\|^{2}$ $\displaystyle=\frac{1-\sigma\eta}{2\eta}\left(X_{t}-X_{t+1}\right)-\frac{ \sigma}{2}X_{t+1}+\frac{\eta}{2}\|\bm{g}_{t}\|^{2}.$ $$

From $\eta<\min\left\{\frac{1}{\sigma},\frac{2}{L_{g}}\right\}$ and Lemma E.3, by summing over $t$ we find that

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(\hat{f}_{\delta_{m}}(\hat{\bm{x}}_ {t}^{(m)})-\hat{f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^{\star})\right)$ $\displaystyle\leq\frac{1-\sigma\eta}{2\eta T}\left(X_{1}-X_{T+1}\right)-\frac{ \sigma}{2T}\sum_{t=1}^{T}X_{t+1}+\frac{\eta}{2T}\sum_{t=1}^{T}\|\bm{g}_{t}\|^{2}$ $\displaystyle\leq\frac{1-\sigma\eta}{2\eta T}X_{1}+\frac{\eta}{2T}\sum_{t=1}^{ T}\|\bm{g}_{t}\|^{2}$ $\displaystyle\leq\underbrace{\frac{9\left(1-\sigma\eta\right)\delta_{m}^{2}}{2 \eta}}_{=:H_{1}}\frac{1}{T}+\underbrace{\frac{3L_{f}\delta_{m}}{\eta\left(2-L_ {g}\eta\right)}}_{=:H_{2}}\frac{1}{T}$ $\displaystyle=\underbrace{\left(H_{1}+H_{2}\right)}_{=:H_{m}}\frac{1}{T}$ $\displaystyle=\frac{H_{m}}{T},$ $$

where we have used $X_{1}:=\|\hat{\bm{x}}_{1}^{(m)}-\bm{x}_{\delta_{m}}^{\star}\|^{2}\leq 9\delta_
{m}^{2}$ and $H_{m}>0$ is a nonnegative constant. From the convexity of $F$,

$$ $\displaystyle\hat{f}_{\delta_{m}}\left(\frac{1}{T}\sum_{t=1}^{T}\hat{\bm{x}}_{ t}^{(m)}\right)\leq\frac{1}{T}\sum_{t=1}^{T}\hat{f}_{\delta_{m}}(\hat{\bm{x}}_ {t}^{(m)}).$ $$

Hence,

$$ $\displaystyle\hat{f}_{\delta_{m}}\left(\frac{1}{T}\sum_{t=1}^{T}\hat{\bm{x}}_{ t}^{(m)}\right)-\hat{f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^{\star})\leq\frac{H_{ m}}{T}=\mathcal{O}\left(\frac{1}{T}\right).$ $$

In addition, since the minimum value is smaller than the mean, we have

$$ $\displaystyle\min_{t\in[T]}\left(\hat{f}_{\delta_{m}}\left(\hat{\bm{x}}_{t}^{( m)}\right)-\hat{f}_{\delta_{m}}(\bm{x}_{\delta_{m}}^{\star})\right)\leq\frac{H _{m}}{T}=\mathcal{O}\left(\frac{1}{T}\right).$ $$

This completes the proof.
∎

###### Proof.

### F.2 Proof of Proposition 5.1

###### Proof.

This proposition can be proved by induction. Since we assume $\bm{x}_{1}\in N(\bm{x}_{\delta_{1}}^{\star};3\delta_{1})$, we have

$$ $\displaystyle\|\bm{x}_{1}-\bm{x}_{\delta_{1}}^{\star}\|<3\delta_{1},$ $$

which establishes the case of $m=1$. Now let us assume that the proposition holds for any $m>1$. Accordingly, the initial point $\bm{x}_{m}$ for the optimization of the $m$-th smoothed function $\hat{f}_{\delta_{m}}$ and its global optimal solution $\bm{x}_{\delta_{m}}^{\star}$ are both contained in the its $\sigma$-strongly convex region $N(\bm{x}_{\delta_{m}}^{\star};3\delta_{m})$. Thus, after $T_{m}:=H_{m}/\epsilon_{m}$ iterations, Algorithm 2 (GD) returns an approximate solution $\hat{\bm{x}}_{T_{m}+1}^{(m)}=:\bm{x}_{m+1}$, and the following holds from Theorem 5.1:

$$ $\displaystyle\hat{f}_{\delta_{m}}(\bm{x}_{m+1})-\hat{f}_{\delta_{m}}(\bm{x}_{ \delta_{m}}^{\star})\leq\frac{H_{m}}{T_{m}}=\epsilon_{m}:=\frac{\sigma\delta_{ m}^{2}}{2}=\frac{\sigma\delta_{m+1}^{2}}{2\gamma^{2}}.$ $$

Hence, from the $\sigma$-strongly convexity of $\hat{f}_{\delta_{m}}$,

$$ $\displaystyle\frac{\sigma}{2}\|\bm{x}_{m+1}-\bm{x}_{\delta_{m}}^{\star}\|^{2} \leq\frac{\sigma\delta_{m+1}^{2}}{2\gamma^{2}},\ \text{i.e., }\|\bm{x}_{m+1}- \bm{x}_{\delta_{m}}^{\star}\|\leq\frac{\delta_{m+1}}{\gamma}$ $$

Therefore, from the $\sigma$-niceness of $f$ and $\gamma\in[0.5,1)$,

$$ $\displaystyle\|\bm{x}_{m+1}-\bm{x}_{\delta_{m+1}}^{\star}\|$ $\displaystyle\leq\|\bm{x}_{m+1}-\bm{x}_{\delta_{m}}^{\star}\|+\|\bm{x}_{\delta _{m}}^{\star}-\bm{x}_{\delta_{m}+1}^{\star}\|$ $\displaystyle\leq\frac{\delta_{m+1}}{\gamma}+\left(|\delta_{m}|-\delta_{m+1}\right)$ $\displaystyle=\frac{\delta_{m+1}}{\gamma}+\left(\frac{\delta_{m+1}}{\gamma}- \delta_{m+1}\right)$ $\displaystyle=\left(\frac{2}{\gamma}-1\right)\delta_{m+1}$ $\displaystyle\leq 3\delta_{m+1}.$ $$

This completes the proof.
∎

###### Proof.

### F.3 Proof of Theorem 5.2

The following proof uses the technique presented in (Hazan et al., ).

###### Proof.

According to $\delta_{m+1}:=\frac{\eta_{m+1}C}{\sqrt{b_{m+1}}}$ and $\frac{\kappa_{m}}{\sqrt{\lambda_{m}}}=\gamma$, we have

$$ $\displaystyle\delta_{m+1}$ $\displaystyle:=\frac{\eta_{m+1}C}{\sqrt{b_{m+1}}}$ $\displaystyle=\frac{\kappa_{m}\eta_{m}C}{\sqrt{\lambda_{m}}\sqrt{b_{m}}}$ $\displaystyle=\frac{\kappa_{m}}{\sqrt{\lambda_{m}}}\delta_{m}$ $\displaystyle=\gamma\delta_{m}.$ $$

Therefore, from $M:=\log_{\gamma}(\alpha_{0}\epsilon)+1$ and $\delta_{1}:=\frac{\eta_{1}C}{\sqrt{b_{1}}}$

$$ $\displaystyle\delta_{M}$ $\displaystyle=\delta_{1}\gamma^{M-1}$ $\displaystyle=\delta_{1}\alpha_{0}\epsilon$ $\displaystyle=\frac{\eta_{1}C\alpha_{0}\epsilon}{\sqrt{b_{1}}}.$ $$

According to Theorem 5.1,

$$ $\displaystyle\mathbb{E}\left[\hat{f}_{\delta_{M}}(\bm{x}_{M+1})-\hat{f}_{ \delta_{M}}(\bm{x}_{\delta_{M}}^{\star})\right]$ $\displaystyle\leq\epsilon_{M}$ $\displaystyle=\sigma\delta_{M}^{2}$ $\displaystyle=\left(\frac{\sqrt{\sigma}\eta_{1}C\alpha_{0}\epsilon}{\sqrt{b_{1 }}}\right)^{2}$ $$

From Lemma D.2 and (5),

$$ $\displaystyle f(\bm{x}_{M+2})-f(\bm{x}^{\star})$ $\displaystyle=\left\{f(\bm{x}_{M+2})-\hat{f}_{\delta_{M}}(\bm{x}_{M+2})\right \}+\left\{\hat{f}_{\delta_{M}}(\bm{x}^{\star})-f(\bm{x}^{\star})\right\}+\left \{\hat{f}_{\delta_{M}}(\bm{x}_{M+2})-\hat{f}_{\delta_{M}}(\bm{x}^{\star})\right\}$ $\displaystyle\leq\left\{f(\bm{x}_{M+2})-\hat{f}_{\delta_{M}}(\bm{x}_{M+2}) \right\}+\left\{\hat{f}_{\delta_{M}}(\bm{x}^{\star})-f(\bm{x}^{\star})\right\} +\left\{\hat{f}_{\delta_{M}}(\bm{x}_{M+2})-\hat{f}_{\delta_{M}}(\bm{x}_{\delta _{M}}^{\star})\right\}$ $\displaystyle\leq\delta_{M}L_{f}+\delta_{M}L_{f}+\left\{\hat{f}_{\delta_{M}}( \bm{x}_{M+2})-\hat{f}_{\delta_{M}}(\bm{x}_{\delta_{M}}^{\star})\right\}$ $\displaystyle=2\delta_{M}L_{f}+\left\{\hat{f}_{\delta_{M}}(\bm{x}_{M+2})-\hat{ f}_{\delta_{M}}(\bm{x}_{M+1})\right\}+\left\{\hat{f}_{\delta_{M}}(\bm{x}_{M+1} )-\hat{f}_{\delta_{M}}(\bm{x}_{\delta_{M}}^{\star})\right\}$ $\displaystyle\leq 2\delta_{M}L_{f}+L_{f}\left\|\bm{x}_{M+2}-\bm{x}_{M+1}\right \|+\left\{\hat{f}_{\delta_{M}}(\bm{x}_{M+1})-\hat{f}_{\delta_{M}}(\bm{x}_{ \delta_{M}}^{\star})\right\}.$ $$

Then, we have

$$ $\displaystyle f(\bm{x}_{M+2})-f(\bm{x}^{\star})$ $\displaystyle\leq 2\delta_{M}L_{f}+6L_{f}\delta_{M}+\epsilon_{M}$ $\displaystyle=8L_{f}\delta_{M}+\epsilon_{M},$ $$

where we have used $\left\|\bm{x}_{M+2}-\bm{x}_{M+1}\right\|\leq 6\delta_{M}$ since $\bm{x}_{M+2},\bm{x}_{M+1}\in N(\bm{x}^{\star};3\delta_{M})$. Therefore,

$$ $\displaystyle f(\bm{x}_{M+2})-f(\bm{x}^{\star})$ $\displaystyle\leq\frac{8L_{f}\eta_{1}C\alpha_{0}\epsilon}{\sqrt{b_{1}}}+\left( \frac{\sqrt{\sigma}\eta_{1}C\alpha_{0}\epsilon}{\sqrt{b_{1}}}\right)^{2}$ $\displaystyle\leq\epsilon,$ $$

where we have used $\alpha_{0}:=\min\left\{\frac{\sqrt{b_{1}}}{16L_{f}\eta_{1}C},\frac{\sqrt{b_{1}
}}{\sqrt{2\sigma}\eta_{1}C}\right\}$.
Let $T_{\text{total}}$ be the total number of queries made by Algorithm 1; then,

$$ $\displaystyle T_{\text{total}}$ $\displaystyle=\sum_{m=1}^{M+1}\frac{H_{m}}{\epsilon_{m}}=\sum_{m=1}^{M+1}\frac {H_{m}}{\sigma\delta_{m}^{2}}.$ $$

Here, from the proof of Theorem 5.1 (see Section F.1), we define $H_{4}>0$ as follows:

$$ $\displaystyle H_{m}:=\frac{9(1-\sigma\eta)\delta_{m}^{2}}{2\eta}+\frac{3L_{f} \delta_{m}}{\eta(2-L_{g}\eta)}\leq\frac{9(1-\sigma\eta)\delta_{1}^{2}}{2\eta}+ \frac{3L_{f}\delta_{1}}{\eta(2-L_{g}\eta)}=:H_{4}$ $$

Thus, from $\delta_{M}=\delta_{1}\alpha_{0}\epsilon$,

$$ $\displaystyle T_{\text{total}}$ $\displaystyle=\sum_{m=1}^{M+1}\frac{H_{m}}{\sigma\delta_{m}^{2}}\leq H_{4}\sum _{m=1}^{M+1}\frac{1}{\sigma\delta_{m}^{2}}\leq H_{4}\sum_{m=1}^{M+1}\frac{1}{ \sigma\delta_{M}^{2}}=\frac{H_{4}(M+1)}{\sigma\delta_{M}^{2}}$ $\displaystyle=\frac{H_{4}(M+1)}{\sigma\delta_{1}^{2}\alpha_{0}^{2}\epsilon^{2} }=\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right).$ $$

This completes the proof.
∎

###### Proof.

## Appendix G Full Experimental Results

The experimental environment was as follows: NVIDIA GeForce RTX 4090$\times$2GPU and Intel Core i9 13900KF CPU. The software environment was Python 3.10.12, PyTorch 2.1.0 and CUDA 12.2.

Figure: Figure 5: Accuracy score for testing and loss function value for training versus the number of epochs (left) and the number of parameter updates (right) in training ResNet18 on the CIFAR100 dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and the batch size were fixed at 0.1 and 128, respectively. In method 2, the learning rate decreased every 40 epochs as $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 128. In method 3, the learning rate was fixed at 0.1, and the batch size was increased as $\left[16,32,64,128,256\right]$. In method 4, the learning rate was decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size was increased as $\left[32,48,72,108,162\right]$.
Refer to caption: x6.png

Figure: Figure 6: Accuracy score for testing and loss function value for training versus the number of epochs (left) and the number of parameter updates (right) in training WideResNet-28-10 on the CIFAR100 dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and batch size were fixed at 0.1 and 128, respectively. In method 2, the learning rate was decreased every 40 epochs as $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 128. In method 3, the learning rate was fixed at 0.1, and the batch size was increased as $\left[8,16,32,64,128\right]$. In method 4, the learning rate was decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size was increased as $\left[8,12,18,27,40\right]$.
Refer to caption: x8.png

For the sake of fairness, we provide here a version of Figures 4-6 with the number of gradient queries on the horizontal axis (see Figure 7-9). Since $b$ stochastic gradients are computed per epoch, the number of gradient queries is $Tb$, where $T$ means the number of steps and $b$ means the batch size.

Figure: Figure 7: Accuracy score for testing and loss function value for training versus the number of gradient queries in training ResNet18 on the CIFAR100 dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and the batch size were fixed at 0.1 and 128, respectively. In method 2, the learning rate decreased every 40 epochs as in $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 128. In method 3, the learning rate was fixed at 0.1, and the batch size was increased as $\left[16,32,64,128,256\right]$. In method 4, the learning rate was decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size was increased as $\left[32,48,72,108,162\right]$. This graph shows almost the same results as Figure 5.
Refer to caption: x10.png

Figure: Figure 8: Accuracy score for testing and loss function value for training versus the number of gradient queries in training WideResNet-28-10 on the CIFAR100 dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and batch size were fixed at 0.1 and 128, respectively. In method 2, the learning rate was decreased every 40 epochs as $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 128. In method 3, the learning rate was fixed at 0.1, and the batch size increased as $\left[8,16,32,64,128\right]$. In method 4, the learning rate decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size increased as $\left[8,12,18,27,40\right]$. This graph shows almost the same results as Figure 6.
Refer to caption: x11.png

Figure: Figure 9: Accuracy score for testing and loss function value for training versus the number of gradient queries in training ResNet34 on the ImageNet dataset. The solid line represents the mean value, and the shaded area represents the maximum and minimum over three runs. In method 1, the learning rate and batch size were fixed at 0.1 and 256, respectively. In method 2, the learning rate was decreased every 40 epochs as $\left[0.1,\frac{1}{10\sqrt{2}},0.05,\frac{1}{20\sqrt{2}},0.025\right]$ and the batch size was fixed at 256. In method 3, the learning rate was fixed at 0.1, and the batch size was increased as $\left[32,64,128,256,512\right]$. In method 4, the learning rate was decreased as $\left[0.1,\frac{\sqrt{3}}{20},0.075,\frac{3\sqrt{3}}{80},0.05625\right]$ and the batch size was increased as $\left[32,48,72,108,162\right]$. This graph shows almost the same results as Figure 4.
Refer to caption: x12.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
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?
soundness: 3
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.
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.
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"

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: Please refer to the weakness.
soundness: 3
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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: Is there any new insight/advantage the degree of smoothing offers other than decreasing the learning rate or increasing the batch size?
soundness: 3
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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: See the weakness section.
soundness: 2
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.
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.
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

Meta-review: 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.

Decision: Reject