Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate

## Abstract

Abstract The sharpness-aware minimization (SAM) algorithm and its variants, including gap guided SAM (GSAM), have been successful at improving the generalization capability of deep neural network models by finding flat local minima of the empirical loss in training. Meanwhile, it has been shown theoretically and practically that increasing the batch size or decaying the learning rate avoids sharp local minima of the empirical loss. In this paper, we consider the GSAM algorithm with increasing batch sizes or decaying learning rates, such as cosine annealing or linear learning rate, and theoretically show its convergence. Moreover, we numerically compare SAM (GSAM) with and without an increasing batch size and conclude that using an increasing batch size or decaying learning rate finds flatter local minima than using a constant batch size and learning rate.

## 1 Introduction

One way to train a deep neural network (DNN) is to find an optimal parameter $\bm{x}^{\star}$ of the network in the sense of minimizing the empirical loss $f_{S}(\bm{x})=\frac{1}{n}\sum_{i\in[n]}f_{i}(\bm{x})$ given by the training set $S=(z_{1},z_{2},\cdots,z_{n})$ and a nonconvex loss function $f(\bm{x};z_{i})=f_{i}(\bm{x})$ corresponding to the $i$-th training data $z_{i}\in S$ ($i\in[n]:=\{1,2,\cdots,n\}$). Our main concern is whether a DNN trained by an algorithm for empirical risk minimization (ERM), wherein the empirical loss $f_{S}$ is minimized, has a strong generalization capability. The sharpness-aware minimization (SAM) problem (Foret et al., ) was proposed as a way to improve a DNN’s generalization capability. The SAM problem is to minimize a perturbed empirical loss defined as the maximum empirical loss $f_{S,\rho}(\bm{x}):=\max_{\|\bm{\epsilon}\|\leq\rho}f_{S}(\bm{x}+\bm{\epsilon})$ over a certain neighborhood of a parameter $\bm{x}\in\mathbb{R}^{d}$ of the DNN, where $\rho\geq 0$ and $\bm{\epsilon}\in\mathbb{R}^{d}$. From the definition of the perturbed empirical loss $f_{S,\rho}$, the SAM problem is specialized to finding flat local minima of the empirical loss $f_{S}$, which may lead to a better generalization capability than finding sharp minima (Keskar et al., ; Jiang et al., ). Although (Andriushchenko et al., ) reported that the relationship between sharpness and generalization would be weak, the SAM algorithm and its variants for solving the SAM problem have high generalization capabilities and superior performance, as shown in, e.g., (Chen et al., ; Du et al., ; Andriushchenko et al., ; Wen et al., ; Chen et al., ; Möllenhoff & Khan, ; Wang et al., ; Sherborne et al., ; Springer et al., ).

Meanwhile, an algorithm using a large batch size falls into sharp local minima of the empirical loss $f_{S}$ and the algorithm would experience a drop in generalization performance (Hoffer et al., ; Goyal et al., ; You et al., ). It has been shown that increasing the batch size (Byrd et al., ; Balles et al., ; De et al., ; Smith et al., ; Goyal et al., ) or decaying the learning rate (Wu et al., ; Ioffe & Szegedy, ; Loshchilov & Hutter, ; Hundt et al., ) avoids sharp local minima of the empirical loss. Hence, we are interested in verifying whether the SAM algorithm with an increasing batch size or decaying learning rate performs well in training DNNs. In this paper, we focus on the SAM algorithm called gap guided SAM (GSAM) algorithm(Zhuang et al., ) (see Algorithm 1 for details).

Contribution: The main contribution of this paper is to show an $\epsilon$-approximation of the GSAM algorithm with an increasing batch size and constant learning rate ((7) in Table 1; Theorem 2.3) and with a constant batch size and a decaying learning rate ((8) in Table 1; Theorem 2.4).

**Table 1: Convergence of SAM and its variants to minimize $\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x})=f_{S}(\bm{x})+\rho\|\nabla f_{S}(\bm{x })\|$ over the number of steps $T$. “Noise" in the Gradient column means that algorithm uses noisy observation, i.e., $\bm{g}(\bm{x})=\nabla f(\bm{x})+\text{(Noise)}$, of the full gradient $\nabla f(\bm{x})$, while “Mini-batch" in the Gradient column means that algorithm uses a mini-batch gradient $\nabla f_{B}(\bm{x})=\frac{1}{b}\sum_{i\in[b]}\nabla f_{\xi_{i}}(\bm{x})$ with a batch size $b$. Here, we let $\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}*}\|]:=\min_{t\in[T]}\mathbb{ E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\|]$, where $(\bm{x}_{t})_{t=0}^{T}$ is the sequence generated by Algorithm. Results (1)–(6) were presented in (1) (Andriushchenko & Flammarion, , Theorem 2), (2) (Mi et al., , Theorem 2), (3) (Zhuang et al., , Theorem 5.1), (4) (Si & Yun, , Theorem 4.6), (5) (Li & Giannakis, , Corollary 1), and (6) (Li et al., , Theorem 2).**
| Algorithm | Gradient | Leaning Rate | Perturbation | Convergence Analysis |
| --- | --- | --- | --- | --- |
| (1) SAM | Mini-batch $b$ | $\eta_{T}=\Theta(\frac{1}{T^{1/2}})$ | $\rho_{T}=\Theta(\frac{1}{T^{1/4}})$ | $\mathbb{E}[\|\nabla f_{S}^{*}\|]=O(\frac{1}{T^{1/4}}+\frac{1}{bT^{1/4}})$ |
| (2) SSAM | Noise | $\eta_{t}=\Theta(\frac{1}{t^{1/2}})$ | $\rho_{t}=\Theta(\frac{1}{t^{1/2}})$ | $\mathbb{E}[\|\nabla f_{S}^{*}\|]=O(\frac{\sqrt{\log T}}{T^{1/4}})$ |
| (3) GSAM | Noise | $\eta_{t}=\Theta(\frac{1}{t^{1/2}})$ | $\rho_{t}=\Theta(\frac{1}{t^{1/2}})$ | $\mathbb{E}[\|\nabla\hat{f}_{S,\rho_{t}}^{\mathrm{SAM}*}\|]=O\left(\frac{\sqrt{<br>\log T}}{T^{1/4}}\right)$ |
| (4) $m$-SAM | Noise | $\eta_{T}=O(\frac{1}{T^{1/2}})$ | $\rho$ | $\mathbb{E}[\|\nabla f_{S}^{*}\|]=O(\sqrt{\frac{1}{T^{1/2}}+\rho^{2}})$ |
| (5) VaSSO | Noise | $\eta_{T}=\Theta(\frac{1}{T^{1/2}})$ | $\rho_{T}=\Theta(\frac{1}{T^{1/2}})$ | $\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}*}\|]=O(\frac{1}{T^{1/4}})$ |
| (6) FSAM | Noise | $\eta_{T}=\Theta(\frac{1}{T^{1/2}})$ | $\rho_{t}=\Theta(\frac{1}{t^{1/2}})$ | $\mathbb{E}[\|\nabla f_{S}^{*}\|]=O(\frac{\sqrt{\log T}}{T^{1/4}})$ |
| (7) GSAM | Increasing | Constant | $\rho$ | $\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}*}\|]\leq\epsilon$ |
| [Ours] | mini-batch $b_{t}$ | $\eta=O(n\epsilon^{2})$ | $=O(\frac{nb_{0}\epsilon^{2}}{\sqrt{n^{2}+b_{0}^{2}}})$ |  |
| (8) GSAM | Mini-batch $b$ | Cosine/Linear | $\rho$ | $\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}*}\|]\leq\epsilon$ |
| [Ours] |  | $\eta_{t}\to\underline{\eta}$ ($\geq 0$) | $=O(\frac{nb\epsilon^{2}}{\sqrt{n^{2}+b^{2}}})$ |  |

Our convergence analyses of GSAM are based on the search direction noise $\eta_{t}\bm{\omega}_{t}$ (defined by (9)) between GSAM and gradient descent (GD) (Theorems 2.1 and 2.2 in Section 2.3). The norm of the noise is approximately $\Theta(\frac{\eta_{t}}{\sqrt{b_{t}}})$ (see also (10)). Since this implies that GSAM using a large batch size $b$ or a small learning rate $\eta$ behaves approximately the same as GD in solving the SAM problem, GSAM eventually needs to use a large batch size or a small learning rate. Accordingly, it will be useful to use increasing batch sizes or decaying learning rates, as the previous results presented in the third paragraph of this section point out. We would also like to emphasize that our analyses allow us to use practical learning rates, such as constant, cosine-annealing, and linear learning rates, unlike the existing methods listed in Table 1.
Our other contribution is to provide numerical results on training ResNets and ViT-Tiny on the CIFAR100 dataset such that using a doubly increasing batch size or a cosine-annealing learning rate finds flatter local minima than using a constant batch size and learning rate (Section 3 and Appendix C).

Related work: Convergence analyses of SGD (Robbins & Monro, ) with a fixed batch size have been presented in (Ghadimi & Lan, ; Ghadimi et al., ; Vaswani et al., ; Fehrman et al., ; Chen et al., ; Scaman & Malherbe, ; Loizou et al., ; Wang et al., ; Arjevani et al., ; Khaled & Richtárik, ). Our analyses found that SGD (an example of GSAM) using increasing batch sizes or a cosine-annealing (linear) learning rate is an $\epsilon$-approximation. The linear scaling rule (Goyal et al., ; Smith et al., ; Xie et al., ) based on $\frac{\eta}{b}$ coincides with our rule based on the noise norm $\eta\|\bm{\omega}_{t}\|^{2}=\Theta(\frac{\eta_{t}}{b_{t}})$. In (Hazan et al., ; Sato & Iiduka, ), it was shown that SGD with an increasing batch size reaches the global optimitum under the strong convexity assumption of the smoothed function of $f_{S}$. This paper shows that, with nonconvex loss functions, GSAM with an increasing batch size achieves an $\epsilon$-approximation.

Limitations: The limitation of this study is the limited number of models and datasets used in the experiments. Hence, we should conduct similar experiments with a larger number of models and datasets to support our theoretical results.

## 2 SAM problem and GSAM

Let $\mathbb{N}$ be the set of natural numbers. Let $[n]:=\{1,2,\cdots,n\}$ and $[0:n]:=\{0,1,\cdots,n\}$ for $n\in\mathbb{N}$. Let $\mathbb{R}^{d}$ be a $d$-dimensional Euclidean space with inner product $\langle\bm{x},\bm{y}\rangle_{2}=\bm{x}^{\top}\bm{y}$ $(\bm{x},\bm{y}\in\mathbb{R}^{d})$ and its induced norm $\|\bm{x}\|_{2}:=\sqrt{\langle\bm{x},\bm{x}\rangle_{2}}$ $(\bm{x}\in\mathbb{R}^{d})$. The gradient and Hessian of a twice differentiable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ at $\bm{x}\in\mathbb{R}^{d}$ are denoted by $\nabla f(\bm{x})$ and $\nabla^{2}f(\bm{x})$, respectively. Let $L>0$. A differentiable function $f\colon\mathbb{R}^{d}\to\mathbb{R}$ is said to be $L$–smooth if the gradient $\nabla f\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is Lipschitz continuous; i.e., for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$, $\|\nabla f(\bm{x})-\nabla f(\bm{y})\|_{2}\leq L\|\bm{x}-\bm{y}\|_{2}$. Let $O$ and $\Theta$ be Landau’s symbols, i.e., $y_{t}=O(x_{t})$ (resp. $y_{t}=\Theta(x_{t})$) if there exist $c>0$ (resp. $c_{1},c_{2}>0$) and $t_{0}\in\mathbb{N}$ such that, for all $t\geq t_{0}$, $y_{t}\leq cx_{t}$ (resp. $c_{1}x_{t}\leq y_{t}\leq c_{2}x_{t}$).

### 2.1 SAM problem and its approximation problem

Given a parameter $\bm{x}\in\mathbb{R}^{d}$ and a data point $z$, a machine-learning model provides a prediction whose quality can be measured by a differentiable nonconvex loss function $f(\bm{x};z)$. For a training set $S=(z_{1},z_{2},\ldots,z_{n})$, $f_{i}(\cdot):=f(\cdot;z_{i})$ is the loss function corresponding to the $i$-th training data $z_{i}$. The empirical risk minimization (ERM) is to minimize the empirical loss defined for all $\bm{x}\in\mathbb{R}^{d}$ by

$$ $\displaystyle f_{S}(\bm{x})=\frac{1}{n}\sum_{i\in[n]}f(\bm{x};z_{i})=\frac{1}{ n}\sum_{i\in[n]}f_{i}(\bm{x}).$ (1) $$

Given $\rho\geq 0$ and a training set $S$, the SAM problem (Foret et al., , (1)) is to minimize

$$ $\displaystyle f_{S,\rho}^{\mathrm{SAM}}(\bm{x}):=\max_{\|\bm{\epsilon}\|_{2} \leq\rho}f_{S}(\bm{x}+\bm{\epsilon}).$ (2) $$

Let $\bm{x}\in\mathbb{R}^{d}$ and $\rho\geq 0$. Taylor’s theorem thus implies that there exists $\tau=\tau(\bm{x},\rho)\in(0,1)$ such that the maximizer $\bm{\epsilon}_{S,\rho}^{\star}(\bm{x})$ of $f_{S}(\bm{x}+\bm{\epsilon})$ over $B_{2}(\bm{0};\rho):=\{\bm{\epsilon}\in\mathbb{R}^{d}\colon\|\bm{\epsilon}\|_{2
}\leq\rho\}$ is as follows:

$$ $\displaystyle\bm{\epsilon}_{S,\rho}^{\star}(\bm{x}):=\operatorname*{arg\,max}_ {\|\bm{\epsilon}\|_{2}\leq\rho}f_{S}(\bm{x}+\bm{\epsilon})=\operatorname*{arg \,max}_{\|\bm{\epsilon}\|_{2}\leq\rho}\left\{f_{S}(\bm{x})+\langle\nabla f_{S} (\bm{x}),\bm{\epsilon}\rangle_{2}+\frac{1}{2}\langle\bm{\epsilon},\nabla^{2}f_ {S}(\bm{x}+\tau\bm{\epsilon})\bm{\epsilon}\rangle_{2}\right\},$ $$

where we suppose that $f_{S}$ is twice differentiable on $\mathbb{R}^{d}$. Then, assuming $\|\bm{\epsilon}\|_{2}^{2}\approx 0$ (i.e., a small enough $\rho^{2}$), $\bm{\epsilon}_{S,\rho}^{\star}(\bm{x})$ can be approximated as follows $\hat{\bm{\epsilon}}_{S,\rho}(\bm{x})$ (Foret et al., , (2)):

$$ $\displaystyle\bm{\epsilon}_{S,\rho}^{\star}(\bm{x})\approx\hat{\bm{\epsilon}}_ {S,\rho}(\bm{x}):=\operatorname*{arg\,max}_{\|\bm{\epsilon}\|_{2}\leq\rho} \langle\nabla f_{S}(\bm{x}),\bm{\epsilon}\rangle_{2}=\begin{cases}\left\{\rho \frac{\nabla f_{S}(\bm{x})}{\|\nabla f_{S}(\bm{x})\|_{2}}\right\}&\text{ }( \nabla f_{S}(\bm{x})\neq\bm{0})\\ B_{2}(\bm{0};\rho)&\text{ }(\nabla f_{S}(\bm{x})=\bm{0}).\end{cases}$ (3) $$

Here, our goal is to solve the following problem that is an approximation of the SAM problem of minimizing $f_{S,\rho}^{\mathrm{SAM}}(\bm{x})=\max_{\|\bm{\epsilon}\|_{2}\leq\rho}f_{S}(
\bm{x}+\bm{\epsilon})$ (see (2) and (3)).

###### Problem 2.1 (Approximated SAM problem (Foret et al., 2021 ) ).

Let $f_{S}$ be the empirical loss defined by (1) with the training set $S=(z_{1},z_{2},\cdots,z_{n})$. Given $\rho\geq 0$,

$$ $\displaystyle\text{minimize }\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}):=\max_{\| \bm{\epsilon}\|_{2}\leq\rho}\left\{f_{S}(\bm{x})+\langle\nabla f_{S}(\bm{x}), \bm{\epsilon}\rangle_{2}\right\}=f_{S}(\bm{x})+\rho\|\nabla f_{S}(\bm{x})\|_{2 }\text{ subject to }\bm{x}\in\mathbb{R}^{d}.$ $$

We use the following approximation (Foret et al., , (3)) of the gradient of $\hat{f}_{S,\rho}^{\mathrm{SAM}}$ at $\bm{x}\in\mathbb{R}^{d}$:

$$ $\displaystyle\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x})$ $\displaystyle:=\nabla f_{S}(\bm{x})|_{\bm{x}+\hat{\bm{\epsilon}}_{S,\rho}(\bm{ x})}=\begin{cases}\nabla f_{S}\left(\bm{x}+\rho\frac{\nabla f_{S}(\bm{x})}{\| \nabla f_{S}(\bm{x})\|_{2}}\right)&\text{ }(\nabla f_{S}(\bm{x})\neq\bm{0})\\ \nabla f_{S}\left(\bm{x}+\bm{u}\right)&\text{ }(\nabla f_{S}(\bm{x})=\bm{0}), \end{cases}$ (4) $$

where $\hat{\bm{\epsilon}}_{S,\rho}(\bm{x})$ is denoted by (3) and $\bm{u}$ is an arbitrary point in $B_{2}(\bm{0};\rho)$ (e.g., we may set $\bm{u}=\bm{0}$ before implementing algorithms).

###### Problem 2.1 (Approximated SAM problem (Foret et al., 2021 ) ).

### 2.2 Mini-batch GSAM algorithm

As a way of solving Problem 2.1, we will study the GSAM algorithm (Zhuang et al., , Algorithm 1) using $b$ loss functions $f_{\xi_{t,1}},f_{\xi_{t,2}},\cdots,f_{\xi_{t,b}}\in\{f_{1},f_{2},\cdots,f_{n}\}$ which are randomly chosen at each time $t$, where $b$ is a batch size satisfying $b\leq n$. We suppose that loss functions satisfy the following conditions.

###### Assumption 2.1 .

(A1) $f_{i}\colon\mathbb{R}^{d}\to\mathbb{R}$ ($i\in[n]$) is twice differentiable and $L_{i}$-smooth.

(A2) $\nabla f_{\xi}\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ is the stochastic gradient of $\nabla f_{S}$; i.e., (i) for all $\bm{x}\in\mathbb{R}^{d}$, $\mathbb{E}_{\xi}[\nabla f_{\xi}(\bm{x})]=\nabla f_{S}(\bm{x})$, (ii) there exists $\sigma\geq 0$ such that, for all $\bm{x}\in\mathbb{R}^{d}$, $\mathbb{V}_{\xi}[\nabla f_{\xi}(\bm{x})]=\mathbb{E}_{\xi}[\|\nabla f_{\xi}(\bm
{x})-\nabla f_{S}(\bm{x})\|_{2}^{2}]\leq\sigma^{2}$, where $\xi$ is a random variable which is independent of $\bm{x}$ and $\mathbb{E}_{\xi}[\cdot]$ stands for the expectation with respect to $\xi$.

(A3) Let $t\in\mathbb{N}$ and suppose that $b_{t}\in\mathbb{N}$ and $b_{t}\leq n$. Let $\bm{\xi}_{t}=(\xi_{t,1},\xi_{t,2},\cdots,\xi_{t,b_{t}})^{\top}$ be a random variable that consists of $b_{t}$ independent and identically distributed variables. The full gradient $\nabla f_{S}(\bm{x})$ is estimated as the following mini-batch gradient at $\bm{x}\in\mathbb{R}^{d}$:

$$ $\displaystyle\nabla f_{S_{t}}(\bm{x}):=\frac{1}{b_{t}}\sum_{i\in[b_{t}]}\nabla f _{\xi_{t,i}}(\bm{x}),$ (5) $$

where $\bm{\xi}_{t}$ is independent of $\bm{x}$, $b_{t}$, and $\bm{\xi}_{t^{\prime}}$ ($t\neq t^{\prime}$).

We define $\hat{\bm{\epsilon}}_{S_{t},\rho}$ by replacing $S$ in (3) with $S_{t}$ in (A3), i.e.,

$$ $\displaystyle\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}):=\operatorname*{arg\,max }_{\|\bm{\epsilon}\|_{2}\leq\rho}\langle\nabla f_{S_{t}}(\bm{x}),\bm{\epsilon} \rangle_{2}=\begin{cases}\left\{\rho\frac{\nabla f_{S_{t}}(\bm{x})}{\|\nabla f _{S_{t}}(\bm{x})\|_{2}}\right\}&\text{ }(\nabla f_{S_{t}}(\bm{x})\neq\bm{0})\\ B_{2}(\bm{0};\rho)&\text{ }(\nabla f_{S_{t}}(\bm{x})=\bm{0}),\end{cases}$ (6) $$

where $\nabla f_{S_{t}}$ is defined as in (5). Accordingly, a mini-batch gradient of $\hat{f}_{S,\rho}^{\mathrm{SAM}}$ (see Problem 2.1 and (4)) at $\bm{x}\in\mathbb{R}^{d}$ can be defined as

$$ $\displaystyle\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x})$ $\displaystyle:=\nabla f_{S_{t}}(\bm{x})|_{\bm{x}+\hat{\bm{\epsilon}}_{S_{t}, \rho}(\bm{x})}=\begin{cases}\nabla f_{S_{t}}\left(\bm{x}+\rho\frac{\nabla f_{S _{t}}(\bm{x})}{\|\nabla f_{S_{t}}(\bm{x})\|_{2}}\right)&\text{ }(\nabla f_{S_{ t}}(\bm{x})\neq\bm{0})\\ \nabla f_{S_{t}}\left(\bm{x}+\bm{u}\right)&\text{ }(\nabla f_{S_{t}}(\bm{x})= \bm{0}),\end{cases}$ (7) $$

where $\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x})$ is denoted by (6) and $\bm{u}$ is an arbitrary point in $B_{2}(\bm{0};\rho)$. Accordingly, the SAM algorithm (Foret et al., , Algorithm 1) can be obtained by applying SGD to the objective function $\hat{f}_{S,\rho}^{\mathrm{SAM}}$ in Problem 2.1, as described in Algorithm 1. GD for Problem 2.1 coincides with Algorithm 1 with $S_{t}=S$ (i.e., $b_{t}=n$), as follows:

$$ $\displaystyle\bm{x}_{t+1}:=\bm{x}_{t}-\eta_{t}\nabla\hat{f}_{S,\rho}^{\mathrm{ SAM}}(\bm{x}_{t}),$ (8) $$

where $\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}$ is defined as in (4). The GSAM algorithm uses an ascent step in the orthogonal direction that is obtained by using stochastic gradient decomposition $\nabla f_{S_{t}}(\bm{x})=\nabla f_{S_{t}\parallel}(\bm{x})+\nabla f_{S_{t}
\perp}(\bm{x})$ to minimize a surrogate gap $h_{t}(\bm{x}):=\hat{f}^{\mathrm{SAM}}_{S_{t},\rho}(\bm{x})-f_{S_{t}}(\bm{x})$ (see (Zhuang et al., , Section 4)).

Figure: Algorithm 1 Mini-batch GSAM algorithm

###### Assumption 2.1 .

### 2.3 Search direction noise between GSAM and GD

GSAM can find local minima of Problem 2.1 (by using $-\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})$) that are flatter than the minima of the perturbed loss function $\hat{f}_{S,\rho}^{\mathrm{SAM}}$ (by using $\alpha\nabla f_{S_{t}\perp}(\bm{x}_{t})$) (see (Zhuang et al., , Section 4) for details). Meanwhile, GD defined as (8) (i.e., GSAM with $b_{t}=n$ and $\alpha=0$) is the simplest algorithm for solving Problem 2.1. Although this GD can minimize $\hat{f}_{S,\rho}^{\mathrm{SAM}}$ by using the full gradient $\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})$, it is not guaranteed that it converges to a flatter minimum of Problem 2.1 compared with the one of GSAM. Here, let us compare GSAM with GD. Let $\bm{x}_{t}\in\mathbb{R}^{d}$ be the $t$-th approximation of Problem 2.1 and $\eta_{t}>0$. The $\bm{x}_{t+1}$ generated by GSAM is as follows:

$$ $\displaystyle\begin{split}\bm{x}_{t+1}&=\bm{x}_{t}+\eta_{t}\{-(\nabla\hat{f}_{ S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\alpha\nabla f_{S_{t}\perp}(\bm{x}_{t}) )\}\\ &=\underbrace{\bm{x}_{t}-\eta_{t}\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_ {t})}_{\text{GD}}+\underbrace{\eta_{t}(\overbrace{\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})-\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t} )}^{\hat{\bm{\omega}}_{t}}+\alpha\nabla f_{S_{t}\perp}(\bm{x}_{t}))}_{\text{ Search Direction Noise }\eta_{t}\bm{\omega}_{t}}\end{split}$ (9) $$

This implies that, if $\eta_{t}\bm{\omega}_{t}:=\eta_{t}(\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}
_{t})-\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})+\alpha\nabla f_{S_
{t}\perp}(\bm{x}_{t}))$ is approximately zero, i.e., $b_{t}\approx n$ and $\alpha\approx 0$, then GSAM is approximately GD in the sense of the norm of $\mathbb{R}^{d}$, and if $\eta_{t}\bm{\omega}_{t}$ is not zero under $\alpha\neq 0$, i.e., $b_{t}<n$, then the behavior of GSAM with $b_{t}<n$ differs from the one of GD. We call $\eta_{t}\bm{\omega}_{t}$ the search direction noise of GSAM, since $\eta_{t}\bm{\omega}_{t}$ is noise from the viewpoint of the search direction of GD. We provide an upper bound of the norm of the search direction noise of GSAM. Theorem 2.1 is proved in Appendix A.

###### Theorem 2.1 (Upper bound of $\mathbb{E}\eta_{t}\|\bm{\omega}_{t}\|_{2}$ ).

Suppose that Assumption 2.1 holds and define $\bm{\omega}_{t}\in\mathbb{R}^{d}$ for all $t\in\mathbb{N}\cup\{0\}$ by $\bm{\omega}_{t}:=\hat{\bm{\omega}}_{t}+\alpha\nabla f_{S_{t}\perp}(\bm{x}_{t})$, where $\bm{x}_{t}$ is generated by Algorithm 1 and we assume that $G_{\perp}:=\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|
_{2}<+\infty$. Then, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]\leq\begin{cases}\eta_ {t}|\alpha|G_{\perp}&(b_{t}=n)\\ \eta_{t}\left\{\sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+\frac{1}{n^{2}}\right) \big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b_{t}}}+|\alpha|G_{ \perp}\right\}&(b_{t}<n),\end{cases}$ $$

where $\mathbb{E}[\cdot]$ stands for the total expectation defined by $\mathbb{E}=\mathbb{E}_{\bm{\xi}_{0}}\mathbb{E}_{\bm{\xi}_{1}}\cdots\mathbb{E}_
{\bm{\xi}_{t}}$.

In the case of GSAM with $b_{t}=n$ and $\alpha\neq 0$, we have that $\eta_{t}\bm{\omega}_{t}=\eta_{t}(\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_
{t})-\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})+\alpha\nabla f_{S\perp}
(\bm{x}_{t}))=\eta_{t}\alpha\nabla f_{S\perp}(\bm{x}_{t})$. Hence, an upper bound of $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ is $\eta_{t}|\alpha|G_{\perp}$ (Theorem 2.1 ($b_{t}=n$)). For simplicity, let us consider the case of $\alpha=0$. The search direction noise $\eta_{t}\bm{\omega}_{t}$ of GSAM with $b_{t}<n$ is not zero, from $\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\neq\nabla\hat{f}_{S_{t},\rho
}^{\mathrm{SAM}}(\bm{x}_{t})$ (see (9)). Meanwhile, the search direction noise $\eta_{t}\bm{\omega}_{t}$ of GD (GSAM with $b_{t}=n$ and $\alpha=0$) is $\eta_{t}\bm{\omega}_{t}=\eta_{t}(\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_
{t})-\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t}))=\bm{0}$, which implies that $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]=0$ (This result coincides with Theorem 2.1 ($b_{t}=n$ and $\alpha=0$)). Accordingly, the noise norm $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ of GSAM will decrease as the batch size $b_{t}$ increases. In fact, from Theorem 2.1 ($b_{t}<n$), the upper bound $U(\eta_{t},b_{t})$ of $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$

$$ $\displaystyle\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]\leq\eta_{t}\sqrt{4 \rho^{2}\left(\frac{1}{b_{t}^{2}}+\frac{1}{n^{2}}\right)\big{(}\sum_{i\in[n]}L _{i}\big{)}^{2}+\frac{2\sigma^{2}}{b_{t}}}\leq\eta_{t}\frac{\sqrt{8\rho^{2}( \sum_{i\in[n]}L_{i})^{2}+2\sigma^{2}}}{\sqrt{b_{t}}}=:U(\eta_{t},b_{t})$ $$

is a monotone decreasing function of $b_{t}$. As a result, $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ decreases as $b_{t}$ increases. Theorem 2.1 also indicates that the smaller $\eta_{t}$ is, the smaller $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ becomes.

Next, we provide a lower bound of the norm of the search direction noise of GSAM. Theorem 2.2 is proven in Appendix A.

###### Theorem 2.2 (Lower bound of $\mathbb{E}\eta_{t}\|\bm{\omega}_{t}\|_{2}$ ).

Under the assumptions in Theorem 2.1, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]\geq\begin{cases}\eta_ {t}|\alpha|\mathbb{E}[\|\nabla f_{S\perp}(\bm{x}_{t})\|_{2}]&(b_{t}=n)\\ \eta_{t}\left\{\frac{c_{t}\sigma}{\sqrt{b_{t}}}-\rho\left(\frac{1}{b_{t}}+ \frac{1}{n}\right)\sum_{i\in[n]}L_{i}-|\alpha|G_{\perp}\right\}&(b_{t}<n\land A _{t}\geq 0)\\ \eta_{t}\left\{\rho\left(\frac{d_{t}}{b_{t}}-\frac{1}{n}\right)\sum_{i\in[n]}L _{i}-\frac{\sigma}{\sqrt{b_{t}}}-|\alpha|G_{\perp}\right\}&(b_{t}<n\land A_{t} <0)\end{cases}$ $$

where $A_{t}$ is defined by (A.3), $c_{t},d_{t}\in(0,1]$, and $|\alpha|$ is small such that, for $b_{t}<n$, $|\alpha|\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|_{2}\leq\|\hat{\bm{\omega}}_{t}\|
_{2}$.

From the definition (9) of the search direction noise, the noise norm $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ of GSAM will increase as the batch size $b_{t}$ decreases. We can verify this fact from Theorem 2.2 ($b_{t}<n\land A_{t}\geq 0$). For simplicity, let us consider the case where $\alpha=0$. We set $T\geq 1$, $c:=\min_{t\in[0:T]}c_{t}$, and $\rho\leq\frac{c\sigma}{2\sum_{i\in[n]}L_{i}}$ (this setting implies that $\rho$, which is used in the definition of Problem 2.1, will be a small parameter (see also (3)). Then, the lower bound $L(\eta_{t},b_{t})$ of $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ satisfies

$$ $\displaystyle\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]\geq\eta_{t}\left\{ \frac{c_{t}\sigma}{\sqrt{b_{t}}}-\rho\left(\frac{1}{b_{t}}+\frac{1}{n}\right) \sum_{i\in[n]}L_{i}\right\}\geq\eta_{t}\frac{c_{t}\sigma-2\rho\sum_{i\in[n]}L_ {i}}{\sqrt{b_{t}}}=:L(\eta_{t},b_{t})\text{ }(\geq 0),$ $$

which implies that the smaller $b_{t}$ is, the larger the lower bound $L(\eta_{t},b_{t})$ of $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ becomes (We can verify this result from Theorem 2.2 ($b_{t}<n\land A_{t}<0$)). Therefore, $\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]$ increases as $b_{t}$ decreases.

To solve Problem 2.1, we consider a mini-batch scheduler and a learning rate scheduler based on Theorems 2.1 and 2.2. To apply not only GSAM but also SAM ($\alpha=0$) to Problem 2.1, we will assume that $|\alpha|$ is approximately zero. Theorems 2.1 and 2.2 (see also the definitions of $U(\eta_{t},b_{t})$ and $L(\eta_{t},b_{t})$) indicate that, for a given small $\rho$ and for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[\eta_{t}\|\bm{\omega}_{t}\|_{2}]\approx\mathbb{E}\left [\eta_{t}\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\nabla\hat{f }_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\approx\begin{ cases}\Theta\left(\frac{\eta_{t}}{\sqrt{b_{t}}}\right)&\text{ }(b_{t}<n)\\ 0&\text{ }(b_{t}=n).\end{cases}$ (10) $$

Equation (10) indicates that the full gradient $\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{0})$ substantially differs from $\nabla\hat{f}_{S_{0},\rho}^{\mathrm{SAM}}(\bm{x}_{0})$ with a small batch size $b_{0}$ or a large learning rate $\eta_{0}$. Meanwhile, GSAM eventually needs to use a large batch size $b$ or a small learning rate, since the behavior of GSAM using a large $b$ or small $\eta$ is approximately like that of GD in minimizing$\hat{f}_{S,\rho}^{\mathrm{SAM}}$. Accordingly, in the process of training DNN, it would be useful to use increasing batch sizes or decaying learning rates.

###### Theorem 2.1 (Upper bound of 𝔼 ⁢ η t ⁢ ‖ ω t ‖ 2 𝔼 subscript 𝜂 𝑡 subscript norm subscript 𝜔 𝑡 2 \mathbb{E}\eta_{t}\|\bm{\omega}_{t}\|_{2} blackboard_E italic_η start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ∥ bold_italic_ω start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ∥ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ).

###### Theorem 2.2 (Lower bound of 𝔼 ⁢ η t ⁢ ‖ ω t ‖ 2 𝔼 subscript 𝜂 𝑡 subscript norm subscript 𝜔 𝑡 2 \mathbb{E}\eta_{t}\|\bm{\omega}_{t}\|_{2} blackboard_E italic_η start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ∥ bold_italic_ω start_POSTSUBSCRIPT italic_t end_POSTSUBSCRIPT ∥ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ).

### 2.4 Convergence analysis of GSAM

#### 2.4.1 Increasing batch size and constant learning rate

Motivated by (Smith et al., ), we focus on using a constant learning rate defined for all $t\in\mathbb{N}\cup\{0\}$ by $\eta_{t}=\eta\in(0,+\infty)$ and a mini-batch scheduler that gradually increases the batch size:

$$ $\displaystyle\underbrace{b_{0}=\cdots=b_{0}}_{E_{0}\text{ epochs}}\leq \underbrace{b_{1}=\cdots=b_{1}}_{E_{1}\text{ epochs}}\leq\cdots\leq\underbrace {b_{M}=\cdots=b_{M}=n}_{E_{M}\text{ epochs}},$ (11) $$

where $M\in\mathbb{N}$ and $E_{i}\in\mathbb{N}$ ($i\in[0:M]$). Accordingly, we have that the total number of steps for training is $T=\sum_{i\in[0:M]}\lceil\frac{n}{b_{i}}\rceil E_{i}$.

Theorem 2.1 leads us to the following theorem, the proof of which is given in Appendix B.2.

###### Theorem 2.3 ( $\epsilon$ –approximation of GSAM with an increasing batch size and constant learning rate).

Consider the sequence $(\bm{x}_{t})$ generated by the mini-batch GSAM algorithm (Algorithm 1) with an increasing batch size $b_{t}\in(0,n]$ defined by (11) and a constant learning rate, $\eta_{t}=\eta\in(0,+\infty)$. Furthermore, let us assume that there exists a positive number $G$ such that
$\max\{\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S}(\bm{x}_{t}+\hat{\bm{
\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))\|_{2},\sup_{t\in\mathbb{N}\cup\{0\}}\|
\nabla\hat{f}^{\mathrm{SAM}}_{S_{t},\rho}(\bm{x}_{t})\|_{2},\sup_{t\in\mathbb{
N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t})\|_{2},G_{\perp
}\}\leq G$,
where $G_{\perp}:=\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|
_{2}<+\infty$ (see Theorem 2.1). Let $\epsilon>0$ be the precision and let $b_{0}>0$, $\eta>0$, $\alpha\in\mathbb{R}$, and $\rho\geq 0$ such that

$$ $\displaystyle\eta\in\left[\frac{12\sigma C}{\epsilon^{2}}\left(\frac{\rho G}{ \sqrt{b_{0}}}+\frac{3\sigma}{nb_{0}}\sum_{i\in[n]}L_{i}\right),\frac{(|\alpha| +1)^{-2}n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n]}L _{i})^{2}\}}\right],$ (12) $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b_{0}}\epsilon^{2}}{6G(CG\sqrt{b _{0}}+B\sigma)\sum_{i\in[n]}L_{i}},\text{ }\rho\leq\frac{nb_{0}\epsilon^{2}}{2 \sqrt{42}G\sqrt{n^{2}+b_{0}^{2}}\sum_{i\in[n]}L_{i}},$ (13) $$

where $B$ and $C$ are nonnegative constants. Then, there exists $t_{0}\in\mathbb{N}$ such that, for all $T\geq t_{0}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\leq\epsilon.$ $$

Theorem 2.3 indicates that the parameters $|\alpha|$ and $\rho$ in (13) become small and thereby achieve an $\epsilon$–approximation of GSAM. The setting of the small parameter $\rho$ is consistent with the definition of Problem 2.1 (see also (3)). Moreover, the setting also matches the numerical results in (Zhuang et al., ) that used small $|\alpha|$ and $\rho$. Using a small $\rho$ leads to the finding that $C$ and $B$ are approximately zero (see Propositions B.2 and B.3). In particular, $\rho=0$ implies that $B=C=0$). Hence, a constant learning rate $\eta$ satisfying (12) is approximately

$$ $\displaystyle\eta\in\left(0,\frac{n\epsilon^{2}}{6(|\alpha|+1)^{2}G^{2}\sum_{i \in[n]}L_{i}}\right].$ (14) $$

From (14), it would be appropriate to set a small $\eta$ in order to achieve an $\epsilon$-approximation of GSAM. In fact, the numerical results in (Zhuang et al., ) used small learning rates, such as $10^{-2}$, $10^{-3}$, and $10^{-5}$.

Since SGD (i.e., GSAM with $\alpha=\rho=0$) satisfies (13), Theorem 2.3 guarantees that SGD is an $\epsilon$-approximation in the sense of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f_{S}(\bm{x}_{t})\|]\leq\epsilon$. Moreover, using $\alpha=\rho=0$ makes the upper bound of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f_{S}(\bm{x}_{t})\|]$ ($=\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\text{SAM}}(\bm{x}_{t}
)\|]$) smaller than using $\alpha\neq 0\lor\rho\neq 0$. Hence, SGD using $\alpha=\rho=0$ would minimize the empirical loss $f_{S}$ more quickly than would SAM/GSAM using $\alpha\neq 0\lor\rho\neq 0$ (see Figure 1 (Left) indicating that SGD minimizes $f_{S}$ more quickly than SAM/GSAM). Meanwhile, the previous results in (Foret et al., ; Zhuang et al., ) indicate that using $\alpha\neq 0\lor\rho\neq 0$ leads to a better generalization than using $\alpha=\rho=0$ (see Figure 1 (Right) and Table 2 indicating that SAM/GSAM with an increasing batch size has a higher generalization capability than SGD has with an increasing batch size).

###### Theorem 2.3 ( ϵ italic-ϵ \epsilon italic_ϵ –approximation of GSAM with an increasing batch size and constant learning rate).

#### 2.4.2 Constant batch size and decaying learning rate

Motivated by (Loshchilov & Hutter, ), we focus on a constant batch size defined for all $t\in\mathbb{N}\cup\{0\}$ by $b_{t}=b$ and examine a cosine-annealing rate scheduler defined by

$$ $\displaystyle\eta_{t}=\underline{\eta}+\frac{\overline{\eta}-\underline{\eta}} {2}\left(1+\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right)\quad(t \in[0:KE]),$ (15) $$

where $\underline{\eta}$ and $\overline{\eta}$ are such that $0\leq\underline{\eta}\leq\overline{\eta}$, $E$ is the number of epochs, and $K=\lceil\frac{n}{b}\rceil$ is the number of steps per epoch. We then have that the total number of steps for training is $T=KE$. The cosine-annealing learning rate (15) is updated per epoch and remains unchanged during $K$ steps.

Moreover, for a constant batch size $b_{t}=b$ ($t\in\mathbb{N}\cup\{0\}$), we examine a linear learning rate scheduler (Liu et al., ) defined by

$$ $\displaystyle\eta_{t}=\frac{\underline{\eta}-\overline{\eta}}{T}t+\overline{ \eta}\quad(t\in[0:T]),$ (16) $$

where $\underline{\eta}$ and $\overline{\eta}$ are such that $0\leq\underline{\eta}\leq\overline{\eta}$ and $T$ is the number of steps. The linear learning rate scheduler (16) is updated per step whose size decays linearly from step 0 0 to $T$.

Theorem 2.1 leads us to the following theorem, the proof which is given in Appendix B.3 (The case where $\underline{\eta}>0$ is also shown in Appendix B.3).

###### Theorem 2.4 ( $\epsilon$ –approximation of GSAM with a constant batch size and decaying learning rate).

Consider the sequence $(\bm{x}_{t})$ generated by the mini-batch GSAM algorithm (Algorithm 1) with a constant batch size $b_{t}=b\in(0,n]$ and a decaying learning rate $\eta_{t}\in[\underline{\eta},\overline{\eta}]$ defined by (15) or (16). Furthermore, let us assume that there exists a positive number $G$ defined as in Theorem 2.3. Let $\epsilon>0$ be the precision and let $b>0$, $\overline{\eta}>0$ ($=\underline{\eta}$), $\alpha\in\mathbb{R}$, and $\rho\geq 0$ such that

$$ $\displaystyle\overline{\eta}\in\begin{cases}\left[\frac{24\sigma C}{\epsilon^{ 2}}\left(\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right), \frac{2(|\alpha|+1)^{-2}n^{3}\epsilon^{2}}{9G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C (\sum_{i\in[n]}L_{i})^{2}\}}\right]&\text{ if }(\ref{cosine_lr})\text{ is used },\\ \left[\frac{24\sigma C}{\epsilon^{2}}\left(\frac{\rho G}{\sqrt{b}}+\frac{3 \sigma}{nb}\sum_{i\in[n]}L_{i}\right),\frac{(|\alpha|+1)^{-2}n^{3}\epsilon^{2} }{4G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n]}L_{i})^{2}\}}\right]&\text { if }(\ref{linear_lr})\text{ is used},\end{cases}$ (17) $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b}\epsilon^{2}}{6G(CG\sqrt{b}+B \sigma)\sum_{i\in[n]}L_{i}},\text{ }\rho\leq\frac{nb\epsilon^{2}}{12G\sqrt{n^{ 2}+b^{2}}\sum_{i\in[n]}L_{i}},$ (18) $$

where $B$ and $C$ are nonnegative constants. Then, there exists $t_{0}\in\mathbb{N}$ such that, for all $T\geq t_{0}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\leq\epsilon.$ $$

Theorem 2.4 indicates that the parameters $|\alpha|$ and $\rho$ in (18) become small and thereby achieve an $\epsilon$–approximation of GSAM, as also seen in Theorem 2.3. A discussion similar to the one showing (14) implies that the maximum learning rate $\overline{\eta}$ satisfying (17) using a small $\rho$ is approximately

$$ $\displaystyle\overline{\eta}\in\begin{cases}\left(0,\frac{2(|\alpha|+1)^{-2}n \epsilon^{2}}{9G^{2}\sum_{i\in[n]}L_{i}}\right]&\text{ if }(\ref{cosine_lr}) \text{ is used},\\ \left(0,\frac{(|\alpha|+1)^{-2}n\epsilon^{2}}{4G^{2}\sum_{i\in[n]}L_{i}}\right ]&\text{ if }(\ref{linear_lr})\text{ is used}.\end{cases}$ (19) $$

From (19), it would be appropriate to set a small $\eta$ in order to achieve an $\epsilon$-approximation of GSAM. In fact, the numerical results in (Zhuang et al., ) used small values of $\overline{\eta}$, such as $1.6$ and $3\times 10^{-3}$.

Theorem 2.4 guarantees that SGD is an $\epsilon$-approximation in the sense of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f_{S}(\bm{x}_{t})\|]\leq\epsilon$. Moreover, using $\alpha=\rho=0$ makes the upper bound of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla f_{S}(\bm{x}_{t})\|]$
smaller than when using $\alpha\neq 0\lor\rho\neq 0$. Hence, SGD using $\alpha=\rho=0$ would minimize the empirical loss $f_{S}$ more quickly than SAM/GSAM using $\alpha\neq 0\lor\rho\neq 0$ (see Figure 2 (Left) indicating that SGD minimizes $f_{S}$ more quickly than SAM/GSAM). Meanwhile, the previous results in (Foret et al., ; Zhuang et al., ) indicate that using $\alpha\neq 0\lor\rho\neq 0$ leads to a higher generalization capability than using $\alpha=\rho=0$ (see Table 2 which shows that the generalization capability of SAM/GSAM+C has a higher than that of SGD+C).

###### Theorem 2.4 ( ϵ italic-ϵ \epsilon italic_ϵ –approximation of GSAM with a constant batch size and decaying learning rate).

## 3 Numerical results

We used a computer equipped with NVIDIA GeForce RTX 4090$\times$2GPUs and an Intel Core i9 13900KF CPU. The software environment was Python 3.10.12, PyTorch 2.1.0, and CUDA 12.2.
The solid lines in the figures represent the mean value and the shaded areas represent the maximum and minimum over three runs.

Training Wide-ResNet28-10 on CIFAR100 We set $E=200$, $\eta=\overline{\eta}=0.1$, and $\underline{\eta}=0.001$. We trained Wide-ResNet-28-10 on the CIFAR100 dataset (see Appendix C for an explanation of training ResNet-18 on the CIFAR100 dataset). The parameters, $\alpha=0.02$ and $\rho=0.05$,
were determined by conducting a grid search of $\alpha\in\{0.01,0.02,0.03\}$ and $\rho\in\{0.01,0.02,0.03,0.04,0.05\}$. Figure 1 compares the use of an increasing batch size $[8,16,32,64,128]$ (SGD/SAM/GSAM + increasing_batch) with the use of a constant batch size $128$ (SGD/SAM/GSAM) for a fixed learning rate, $0.1$. SGD/SAM/GSAM + increasing_batch decreased the empirical loss (Figure 1 (Left)) and achieved higher test accuracies compared with SGD/SAM/GSAM (Figure 1 (Right)). Figure 2 compares the use of a cosine-annealing learning rate defined by (15) (SGD/SAM/GSAM + Cosine) with the use of a constant learning rate, $0.1$ (SGD/SAM/GSAM) for a fixed batch size $128$. SAM/GSAM + Cosine decreased the empirical loss (Figure 2 (Left)) and achieved higher test accuracies compared with SGD/SAM/GSAM (Figure 2 (Right)).

Figure: Figure 1: (Left) Loss function value in training and (Right) accuracy score in testing for the algorithms versus the number of epochs in training Wide-ResNet-28-10 on the CIFAR100 dataset. The learning rate of each algorithm was fixed at 0.1. In SGD/SAM/GSAM, the batch size was fixed at 128. In SGD/SAM/GSAM + increasing_batch, the batch size was set at 8 for the first 40 epochs and then it was doubled every 40 epochs afterwards, i.e., to 16 for epochs 41-80, 32 for epochs 81-120, etc.
Refer to caption: x1.png

Figure: Figure 2: (Left) Loss function value in training and (Right) accuracy score in testing for the algorithms versus the number of epochs in training Wide-ResNet28-10 on the CIFAR100 dataset. The batch size of each algorithm was fixed at 128. In SGD/SAM/GSAM, the constant learning rate was fixed at 0.1. In SGD/SAM/GSAM + Cosine, the maximum learning rate was 0.1 and the minimum learning rate was 0.001.
Refer to caption: x3.png

**Table 2: Mean values of the test errors (Test Error) and the worst-case $\ell_{\infty}$ adaptive sharpness (Sharpness) for the parameter obtained by the algorithms at $200$ epochs in training Wide-ResNet28-10 on the CIFAR100 dataset. “(algorithm)+B" refers to“ (algorithm) + increasing_batch" used in Figure 1, and “(algorithm)+C" refers to “ (algorithm) + Cosine" used in Figure 2.**
|  | SGD | SAM | GSAM | SGD+B | SAM+B | GSAM+B | SGD+C | SAM+C | GSAM+C |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Test Error | 25.62 | 24.78 | 24.94 | 22.65 | 21.10 | 21.50 | 25.57 | 24.16 | 24.00 |
| Sharpness | 1113.26 | 456.20 | 435.17 | 22.72 | 10.99 | 12.37 | 1148.09 | 687.44 | 665.13 |

Table 2 summarizes the mean values of the test errors and the worst-case $\ell_{\infty}$ adaptive sharpness defined by (Andriushchenko et al., , (1)) for the parameters $\bm{c}=(1,1,\cdots,1)^{\top}$ and $\rho=0.0002$ obtained by the algorithm after $200$ epochs. SAM+B (SAM + increasing_batch) had the highest test accuracy and the lowest sharpness, which implies that SAM+B approximated a flatter local minimum. The table indicates that increasing batch sizes could avoid sharp local minima to which the algorithms using the constant and cosine-annealing learning rates converged.

Training ViT-Tiny on CIFAR100
We set $E=100$ and a learning rate of $\overline{\eta}=0.001$ with an initial learning rate of $0.00001$ and linear warmup during $10$ epochs. We trained ViT-Tiny on the CIFAR100 dataset (see Appendix D for the ViT-Tiny model). We used Adam (Kingma & Ba, ) with $\beta_{1}=0.9$, $\beta_{2}=0.999$ and a weight decay of $0.05$ as the base algorithm. The parameters, $\alpha=0.1$ and $\rho=0.6$,
were determined by conducting a grid search of $\alpha\in\{0.1,0.2,0.3\}$ and $\rho\in\{0.1,0.2,0.3,0.4,0.5,0.6\}$. We used the data extension and regularization technique in (Lee et al., ). Figure 3 compares the use of an increasing batch size $[64,128,256,512]$ (Adam/SAM/GSAM + increasing_batch) with the use of a constant batch size $128$ (Adam/SAM/GSAM) for a fixed learning rate, $0.001$. SAM + increasing_batch achieved higher test accuracies compared with Adam/SAM/GSAM (Figure 3 (Right)). Figure 4 comapares the use of a cosine-annealing learning rate defined by (15) (Adam/SAM/GSAM + Cosine) with the use of a constant learning rate, $0.001$, (Adam/SAM/GSAM) for a fixed batch size, $128$. Adam + Cosine achieved higher test accuracies than Adam/SAM/GSAM (Figure 4 (Right)).

Figure: Figure 3: (Left) Loss function value in training and (Right) accuracy score in testing for the optimizers versus the number of epochs in training ViT-Tiny on the CIFAR100 dataset. The learning rate of each optimizer was fixed at 0.001 with an initial learning rate 0.00001 and linear warmup during 10 epochs. In Adam/SAM/GSAM, the batch size was fixed at 128. In Adam/SAM/GSAM + increasing batch, the batch size was set at 64 for the first 25 epochs and then it was doubled every 25 epochs afterwards, i.e., to 128 for epochs 26-50, 256 for epochs 51-75, etc.
Refer to caption: x5.png

Figure: Figure 4: (Left) Loss function value in training and (Right) accuracy score in testing for the optimizers versus the number of epochs in training ViT-Tiny on the CIFAR100 dataset. The batch size of each optimizer was fixed at 128. In Adam/SAM/GSAM, the constant learning rate was fixed at 0.001 with an initial learning rate 0.00001 and linear warmup during the first 10 epochs. In Adam/SAM/GSAM + Cosine, the maximum learning rate was 0.001 and the minimum learning rate was 0.00001 with linear warmup during the first 10 epochs.
Refer to caption: x7.png

**Table 3: Mean values of the test errors (Test Error) and the worst-case $\ell_{\infty}$ adaptive sharpness (Sharpness) for the parameter obtained by the algorithms at $100$ epochs in training ViT-Tiny on the CIFAR100 dataset. “(algorithm)+B" refers to “ (algorithm) + increasing batch" in Figure 3, and “(algorithm)+C" refers to “ (algorithm) + Cosine" in Figure 4.**
|  | Adam | SAM | GSAM | Adam+B | SAM+B | GSAM+B | Adam+C | SAM+C | GSAM+C |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Test Error | 31.62 | 29.20 | 29.81 | 29.26 | 28.45 | 29.10 | 27.06 | 28.18 | 28.90 |
| Sharpness | 0.28 | 0.16 | 0.15 | 0.24 | 0.15 | 0.16 | 0.42 | 0.17 | 0.17 |

Table 3 summarizes the mean values of the test errors and the worst-case $\ell_{\infty}$ adaptive sharpness defined by (Andriushchenko et al., , (1)) for the parameters $\bm{c}=(1,1,\cdots,1)^{\top}$ and $\rho=0.0002$ obtained by the algorithm after $100$ epochs. The table indicates that SAM+B could avoid local minima to which the algorithms using the cosine-annealing learning rate converged.

## 4 Conclusion

First we gave upper and lower bounds of the search direction noise of the GSAM algorithm for solving the SAM problem. Then, we examined the GSAM algorithm with two mini-batch and learning rate schedulers based on the bounds: an increasing batch size and constant learning rate scheduler and a constant batch size and decaying learning rate scheduler. We performed convergence analyses on GSAM for the two schedulers. We also provided numerical results to support the analyses. The numerical results showed that, compared with SGD/Adam, SAM/GSAM with an increasing batch size and a constant learning rate converges to flatter local minima of the empirical loss functions for ResNets and ViT-Tiny on the CIFAR100 dataset.

## Appendix A Proofs of Theorems 2.1 and 2.2

### A.1 Propositions

We first give an upper bound of the variance of the stochastic gradient $\nabla f_{S_{t}}(\bm{x})$.

###### Proposition A.1 .

Under Assumption 2.1, we have that, for all $\bm{x}\in\mathbb{R}^{d}$ and all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]=\nabla f_{S}(\bm{x}),$ $\displaystyle\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]=\mathbb{E}_{\bm{\xi}_{t}}\left[\|\nabla f_{S_{t}}( \bm{x})-\nabla f_{S}(\bm{x})\|_{2}^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]\leq \frac{\sigma^{2}}{b_{t}},$ $$

where $\mathbb{E}_{\bm{\xi}_{t}}[\cdot|\hat{\bm{\xi}}_{t-1}]$ stands for the expectation with respect to $\bm{\xi}_{t}$ conditioned on $\bm{\xi}_{t-1}=\hat{\bm{\xi}}_{t-1}$.

Proof: Let $\bm{x}\in\mathbb{R}^{d}$ and $t\in\mathbb{N}\cup\{0\}$. Assumption 2.1(A3) ensures that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]=\mathbb{E}_{\bm{\xi}_{t}}\left[\frac{1}{b_{t}}\sum _{i\in[b_{t}]}\nabla f_{\xi_{t,i}}(\bm{x})\Bigg{|}\hat{\bm{\xi}}_{t-1}\right]= \frac{1}{b_{t}}\sum_{i\in[b_{t}]}\mathbb{E}_{\xi_{t,i}}\left[\nabla f_{\xi_{t, i}}(\bm{x})\Big{|}\hat{\bm{\xi}}_{t-1}\right],$ $$

which, together with Assumption 2.1(A2)(i) and the independence of $\bm{\xi}_{t}$ and $\bm{\xi}_{t-1}$, implies that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]=\nabla f_{S}(\bm{x}).$ $$

Assumption 2.1(A3) implies that

$$ $\displaystyle\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\mathbb{E}_{\bm{\xi}_{t}}\left[\|\nabla f_{S_{t}}(\bm{x})-\nabla f _{S}(\bm{x})\|_{2}^{2}\Big{|}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\frac{1}{b_{t}}\sum_{i\in[ b_{t}]}\nabla f_{\xi_{t,i}}(\bm{x})-\nabla f_{S}(\bm{x})\right\|_{2}^{2}\Bigg{ |}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\frac{1}{b_{t}^{2}}\mathbb{E}_{\bm{\xi}_{t}}\left[\left\|\sum_{i \in[b_{t}]}\left(\nabla f_{\xi_{t,i}}(\bm{x})-\nabla f_{S}(\bm{x})\right) \right\|_{2}^{2}\Bigg{|}\hat{\bm{\xi}}_{t-1}\right].$ $$

From the independence of $\xi_{t,i}$ and $\xi_{t,j}$ ($i\neq j$), for all $i,j\in[b_{t}]$ with $i\neq j$,

$$ $\displaystyle\mathbb{E}_{\xi_{t,i}}[\langle\nabla f_{\xi_{t,i}}(\bm{x})-\nabla f _{S}(\bm{x}),\nabla f_{\xi_{t,j}}(\bm{x})-\nabla f_{S}(\bm{x})\rangle_{2}|\hat {\bm{\xi}}_{k-1}]$ $\displaystyle=\langle\mathbb{E}_{\xi_{t,i}}[\nabla f_{\xi_{t,i}}(\bm{x})|\hat{ \bm{\xi}}_{t-1}]-\mathbb{E}_{\xi_{t,i}}[\nabla f_{S}(\bm{x})|\hat{\bm{\xi}}_{t -1}],\nabla f_{\xi_{t,j}}(\bm{x})-\nabla f_{S}(\bm{x})\rangle_{2}=0.$ $$

Hence, Assumption 2.1(A2)(ii) guarantees that

$$ $\displaystyle\mathbb{V}_{\bm{\xi}_{t}}\left[\nabla f_{S_{t}}(\bm{x})\Big{|} \hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle=\frac{1}{b_{t}^{2}}\sum_{i\in[b_{t}]}\mathbb{E}_{\xi_{t,i}}\left [\left\|\nabla f_{\xi_{t,i}}(\bm{x})-\nabla f_{S}(\bm{x})\right\|_{2}^{2}\Big{ |}\hat{\bm{\xi}}_{t-1}\right]$ $\displaystyle\leq\frac{\sigma^{2}b_{t}}{b_{t}^{2}}=\frac{\sigma^{2}}{b_{t}},$ $$

which completes the proof.
$\Box$

We will use the following proposition to prove Theorem 2.1.

###### Proposition A.2 .

(Ortega & Rheinboldt, , 3.2.6, (10))
Let $f\colon\mathbb{R}^{d}\to\mathbb{R}$ be twice differentiable. Then, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\nabla f(\bm{y})=\nabla f(\bm{x})+\int_{0}^{1}\nabla^{2}f(\bm{x}+ t(\bm{y}-\bm{x}))(\bm{y}-\bm{x})\mathrm{d}t.$ $$

###### Proposition A.1 .

###### Proposition A.2 .

### A.2 Proof of Theorem 2.1

We will use Propositions A.1 and A.2 to prove Theorem 2.1.

Let $t\in\mathbb{N}\cup\{0\}$ and $b<n$ and suppose that $\bm{x}_{t}$ generated by Algorithm 1 satisfies $\nabla f_{S_{t}}(\bm{x}_{t})\neq\bm{0}$ and $\nabla f_{S}(\bm{x}_{t})\neq\bm{0}$. Then, we have

$$ $\displaystyle\begin{split}\|\hat{\bm{\omega}}_{t}\|_{2}^{2}&=\left\|\nabla\hat {f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\nabla\hat{f}_{S,\rho}^{\mathrm{ SAM}}(\bm{x}_{t})\right\|_{2}^{2}\\ &\underset{(\ref{sam_s_t})}{=}\left\|\nabla f_{S_{t}}\left(\bm{x}_{t}+\rho \frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}} \right)-\nabla f_{S}\left(\bm{x}_{t}+\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\| \nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\right\|_{2}^{2}\\ &=\Bigg{\|}\nabla f_{S_{t}}(\bm{x}_{t})+\int_{0}^{1}\nabla^{2}f_{S_{t}}\left( \bm{x}_{t}+\rho s\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x} _{t})\|_{2}}\right)\rho\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}( \bm{x}_{t})\|_{2}}\mathrm{d}s\\ &\quad-\left(\nabla f_{S}(\bm{x}_{t})+\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_ {t}+\rho s\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}} \right)\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}} \mathrm{d}s\right)\Bigg{\|}_{2}^{2},\end{split}$ (20) $$

where the third equation comes from Proposition A.2. From $\|\bm{x}+\bm{y}\|_{2}^{2}\leq 2\|\bm{x}\|_{2}^{2}+2\|\bm{y}\|_{2}^{2}$ ($\bm{x},\bm{y}\in\mathbb{R}^{d}$), we have

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}^{2}$ $\displaystyle\leq 2\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{ 2}^{2}$ $\displaystyle\quad+4\left\|\int_{0}^{1}\nabla^{2}f_{S_{t}}\left(\bm{x}_{t}+ \rho s\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2} }\right)\rho\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t}) \|_{2}}\mathrm{d}s\right\|_{2}^{2}$ $\displaystyle\quad+4\left\|\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s \frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\rho \frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\mathrm{d}s \right\|_{2}^{2},$ $$

which, together with the property of $\|\cdot\|_{2}$, implies that

$$ $\displaystyle\begin{split}\|\hat{\bm{\omega}}_{t}\|_{2}^{2}&\leq 2\|\nabla f_{ S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{2}^{2}\\ &\quad+4\left(\rho\int_{0}^{1}\left\|\nabla^{2}f_{S_{t}}\left(\bm{x}_{t}+\rho s \frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}} \right)\right\|_{2}\mathrm{d}s\right)^{2}\\ &\quad+4\left(\rho\int_{0}^{1}\left\|\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s \frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\right \|_{2}\mathrm{d}s\right)^{2}.\end{split}$ (21) $$

Meanwhile, the triangle inequality and the $L_{i}$–smoothness of $f_{i}$ (see (A1)) ensure that, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\|\nabla f_{S_{t}}(\bm{x})-\nabla f_{S_{t}}(\bm{y})\|_{2}$ $\displaystyle=\left\|\frac{1}{b_{t}}\sum_{i\in[b_{t}]}(\nabla f_{\xi_{t,i}}( \bm{x})-\nabla f_{\xi_{t,i}}(\bm{y}))\right\|\leq\frac{1}{b_{t}}\sum_{i\in[b_{ t}]}\left\|\nabla f_{\xi_{t,i}}(\bm{x})-\nabla f_{\xi_{t,i}}(\bm{y})\right\|$ $\displaystyle\leq\frac{1}{b_{t}}\sum_{i\in[b_{t}]}L_{\xi_{t,i}}\|\bm{x}-\bm{y} \|_{2}\leq\frac{1}{b_{t}}\sum_{i\in[n]}L_{i}\|\bm{x}-\bm{y}\|_{2},$ $$

which implies that, for all $\bm{x}\in\mathbb{R}^{d}$, $\|\nabla^{2}f_{S_{t}}(\bm{x})\|_{2}\leq b_{t}^{-1}\sum_{i\in[n]}L_{i}$. A discussion similar to the one showing that $\nabla f_{S_{t}}$ is $b_{t}^{-1}\sum_{i\in[n]}L_{i}$–smooth ensures that $\nabla f_{S}$ is $n^{-1}\sum_{i\in[n]}L_{i}$–smooth, which in turn implies that, for all $\bm{x}\in\mathbb{R}^{d}$, $\|\nabla^{2}f_{S}(\bm{x})\|_{2}\leq n^{-1}\sum_{i\in[n]}L_{i}$. Accordingly, (21) guarantees that

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}^{2}\leq 2\|\nabla f_{S_{t}}(\bm{x}_ {t})-\nabla f_{S}(\bm{x}_{t})\|_{2}^{2}+\frac{4\rho^{2}}{b_{t}^{2}}\bigg{(} \sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{4\rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L _{i}\bigg{)}^{2}.$ (22) $$

Taking the expectation with respect to $\bm{\xi}_{t}$ conditioned on $\bm{\xi}_{t-1}=\hat{\bm{\xi}}_{t-1}$ on both sides of (22) ensures that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}[\|\hat{\bm{\omega}}_{t}\|_{2}^{2}|\hat{ \bm{\xi}}_{t-1}]\leq 2\mathbb{E}_{\bm{\xi}_{t}}[\|\nabla f_{S_{t}}(\bm{x}_{t}) -\nabla f_{S}(\bm{x}_{t})\|_{2}^{2}|\hat{\bm{\xi}}_{t-1}]+\frac{4\rho^{2}}{b_{ t}^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{4\rho^{2}}{n^{2}}\bigg{(} \sum_{i\in[n]}L_{i}\bigg{)}^{2},$ $$

which, together with Proposition A.1, implies that

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t}}[\|\hat{\bm{\omega}}_{t}\|_{2}^{2}|\hat{ \bm{\xi}}_{t-1}]\leq\frac{2\sigma^{2}}{b_{t}}+\frac{4\rho^{2}}{b_{t}^{2}}\bigg {(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{4\rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n ]}L_{i}\bigg{)}^{2}.$ $$

Since $\bm{\xi}_{t}$ is independent of $\bm{\xi}_{t-1}$, we have

$$ $\displaystyle\mathbb{E}_{\bm{\xi}_{t-1}}\mathbb{E}_{\bm{\xi}_{t}}[\|\hat{\bm{ \omega}}_{t}\|_{2}^{2}]=\mathbb{E}_{\bm{\xi}_{t-1}}[\mathbb{E}_{\bm{\xi}_{t}}[ \|\hat{\bm{\omega}}_{t}\|_{2}^{2}|\bm{\xi}_{t-1}]]\leq\frac{2\sigma^{2}}{b_{t} }+\frac{4\rho^{2}}{b_{t}^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{4 \rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2},$ $$

which, together with $\mathbb{E}=\mathbb{E}_{\bm{\xi}_{0}}\mathbb{E}_{\bm{\xi}_{1}}\cdots\mathbb{E}_
{\bm{\xi}_{t}}$ implies that

$$ $\displaystyle\mathbb{E}[\|\hat{\bm{\omega}}_{t}\|_{2}^{2}]\leq\frac{2\sigma^{2 }}{b_{t}}+\frac{4\rho^{2}}{b_{t}^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+ \frac{4\rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}.$ (23) $$

Suppose that $\bm{x}_{t}$ generated by Algorithm 1 satisfies either $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ or $\nabla f_{S}(\bm{x}_{t})=\bm{0}$. Let $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$. A discussion similar to the one obtaining (20) and (21), together with (7), ensures that

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}^{2}$ $\displaystyle=\left\|\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})- \nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}$ $\displaystyle=\left\|\nabla f_{S_{t}}(\bm{x}_{t}+\bm{u})-\nabla f_{S}\left(\bm {x}_{t}+\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}} \right)\right\|_{2}^{2}$ $\displaystyle=\Bigg{\|}\nabla f_{S_{t}}(\bm{x}_{t})+\int_{0}^{1}\nabla^{2}f_{S _{t}}(\bm{x}_{t}+s\bm{u})\bm{u}\mathrm{d}s$ $\displaystyle\quad-\left(\nabla f_{S}(\bm{x}_{t})+\int_{0}^{1}\nabla^{2}f_{S} \left(\bm{x}_{t}+\rho s\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{ t})\|_{2}}\right)\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t} )\|_{2}}\mathrm{d}s\right)\Bigg{\|}_{2}^{2},$ $$

which, together with $\|\bm{u}\|_{2}\leq\rho$, implies that

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}^{2}$ $\displaystyle\leq 2\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{ 2}^{2}$ $\displaystyle\quad+4\left(\rho\int_{0}^{1}\left\|\nabla^{2}f_{S_{t}}(\bm{x}_{t }+s\bm{u})\right\|_{2}\mathrm{d}s\right)^{2}$ $\displaystyle\quad+4\left(\rho\int_{0}^{1}\left\|\nabla^{2}f_{S}\left(\bm{x}_{ t}+\rho s\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}} \right)\right\|_{2}\mathrm{d}s\right)^{2}.$ $$

Hence, the same discussion as in (22) leads to the finding that

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}^{2}\leq 2\|\nabla f_{S_{t}}(\bm{x}_ {t})-\nabla f_{S}(\bm{x}_{t})\|_{2}^{2}+\frac{4\rho^{2}}{b_{t}^{2}}\bigg{(} \sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{4\rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L _{i}\bigg{)}^{2}.$ $$

Accordingly, Proposition A.1 and a discussion similar to the one showing (23) imply that (23) holds in the case of $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$. Moreover, it ensures that (23) holds in the case of $\nabla f_{S}(\bm{x}_{t})=\bm{0}$. Therefore, we have

$$ $\displaystyle\mathbb{E}[\|\hat{\bm{\omega}}_{t}\|_{2}]\leq\sqrt{\frac{2\sigma^ {2}}{b_{t}}+\frac{4\rho^{2}}{b_{t}^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2} +\frac{4\rho^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}}.$ (24) $$

We reach the desired result for when $b_{t}<n$ in Theorem 2.1 from $\|\bm{\omega}_{t}\|_{2}\leq\|\hat{\bm{\omega}}_{t}\|_{2}+|\alpha|G_{\perp}$ and (24). We reach the desired result for when $b_{t}=n$ from $\|\hat{\bm{\omega}}_{t}\|_{2}^{2}=0$. This completes the proof.
$\Box$

### A.3 Proof of Theorem 2.2

Let $t\in\mathbb{N}\cup\{0\}$ and $b<n$ and suppose that $\bm{x}_{t}$ generated by Algorithm 1 satisfies $\nabla f_{S_{t}}(\bm{x}_{t})\neq\bm{0}$ and $\nabla f_{S}(\bm{x}_{t})\neq\bm{0}$. From $|\alpha|\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|_{2}\leq\|\hat{\bm{\omega}}_{t}\|
_{2}$, we have

$$ $\displaystyle\|\bm{\omega}_{t}\|_{2}\geq\|\hat{\bm{\omega}}_{t}\|_{2}-|\alpha| \|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|_{2}\geq\|\hat{\bm{\omega}}_{t}\|_{2}-| \alpha|G_{\perp}.$ $$

From (20), we have

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}$ $\displaystyle=\left\|\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})- \nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}$ $\displaystyle\geq\Bigg{|}\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t })\|_{2}-\Bigg{\|}\int_{0}^{1}\nabla^{2}f_{S_{t}}\left(\bm{x}_{t}+\rho s\frac{ \nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}\right)\rho \frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}} \mathrm{d}s$ $\displaystyle\quad-\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\rho\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\mathrm{d}s\Bigg{\| }_{2}\Bigg{|}=:|A_{t}|.$ (25) $$

When $A_{t}\geq 0$,

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}$ $\displaystyle\geq\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{2} -\Bigg{\|}\int_{0}^{1}\nabla^{2}f_{S_{t}}\left(\bm{x}_{t}+\rho s\frac{\nabla f _{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}\right)\rho\frac{ \nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}\mathrm{d}s$ $\displaystyle\quad-\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\rho\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\mathrm{d}s\Bigg{\| }_{2}$ $\displaystyle\geq\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{2} -\rho\left(\frac{1}{b_{t}}+\frac{1}{n}\right)\sum_{i\in[n]}L_{i},$ $$

where the second inequality comes from (21) and (22). A similar discussion to the one in (23), together with Proposition A.1, implies that there exists $c_{t}\in[0,1]$ such that

$$ $\displaystyle\mathbb{E}[\|\hat{\bm{\omega}}_{t}\|_{2}]\geq\frac{c_{t}\sigma}{ \sqrt{b_{t}}}-\rho\left(\frac{1}{b_{t}}+\frac{1}{n}\right)\sum_{i\in[n]}L_{i}.$ $$

Accordingly, we have

$$ $\displaystyle\mathbb{E}[\|\bm{\omega}_{t}\|_{2}]\geq\frac{c_{t}\sigma}{\sqrt{b _{t}}}-\rho\left(\frac{1}{b_{t}}+\frac{1}{n}\right)\sum_{i\in[n]}L_{i}-|\alpha |G_{\perp}.$ (26) $$

Furthermore, when $A_{t}<0$, we have

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}$ $\displaystyle\geq\Bigg{\|}\int_{0}^{1}\nabla^{2}f_{S_{t}}\left(\bm{x}_{t}+\rho s \frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}} \right)\rho\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t}) \|_{2}}\mathrm{d}s$ $\displaystyle\quad-\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\rho\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\mathrm{d}s\Bigg{\| }_{2}-\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t})\|_{2}$ $\displaystyle\geq\Bigg{|}\Bigg{\|}\int_{0}^{1}\nabla^{2}f_{S_{t}}\left(\bm{x}_ {t}+\rho s\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\| _{2}}\right)\rho\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_ {t})\|_{2}}\mathrm{d}s\Bigg{\|}_{2}$ $\displaystyle\quad-\Bigg{\|}\int_{0}^{1}\nabla^{2}f_{S}\left(\bm{x}_{t}+\rho s \frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right)\rho \frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\mathrm{d}s \Bigg{\|}_{2}\Bigg{|}-\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t}) \|_{2},$ $$

which, together with (21) and (22), implies that there exists $d_{t}\in(0,1]$ such that

$$ $\displaystyle\|\hat{\bm{\omega}}_{t}\|_{2}\geq\rho\left(\frac{d_{t}}{b_{t}}- \frac{1}{n}\right)\sum_{i\in[n]}L_{i}-\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_ {S}(\bm{x}_{t})\|_{2}.$ $$

A similar discussion to the one in (23), together with Proposition A.1, implies that

$$ $\displaystyle\mathbb{E}[\|\hat{\bm{\omega}}_{t}\|_{2}]\geq\rho\left(\frac{d_{t }}{b_{t}}-\frac{1}{n}\right)\sum_{i\in[n]}L_{i}-\frac{\sigma}{\sqrt{b_{t}}}.$ $$

Hence,

$$ $\displaystyle\mathbb{E}[\|\bm{\omega}_{t}\|_{2}]\geq\rho\left(\frac{d_{t}}{b_{ t}}-\frac{1}{n}\right)\sum_{i\in[n]}L_{i}-\frac{\sigma}{\sqrt{b_{t}}}-|\alpha| G_{\perp}.$ (27) $$

Suppose that $\bm{x}_{t}$ generated by Algorithm 1 satisfies $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ or $\nabla f_{S}(\bm{x}_{t})=\bm{0}$. Then, a discussion similar to the one proving Theorem 2.1 under $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}\lor\nabla f_{S}(\bm{x}_{t})=\bm{0}$ ensures that (26) and (27) hold. When $b_{t}=n$, we have $\bm{\omega}_{t}=\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\nabla\hat{f
}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})+\alpha\nabla f_{S\perp}(\bm{x}_{t})=
\alpha\nabla f_{S\perp}(\bm{x}_{t})$, which implies that $\mathbb{E}[\|\bm{\omega}_{t}\|_{2}]=|\alpha|\mathbb{E}[\|\nabla f_{S\perp}(\bm
{x}_{t})\|_{2}]$.
$\Box$

## Appendix B General convergence analysis of GSAM and its proof

###### Theorem B.1 ( $\epsilon$ –approximation of GSAM with an increasing batch size and decaying learning rate).

Consider the sequence $(\bm{x}_{t})$ generated by the mini-batch GSAM algorithm (Algorithm 1) with an increasing batch size $b_{t}\in(0,n]$ and a decaying learning rate $\eta_{t}\in[\underline{\eta},\overline{\eta}]\subset[0,+\infty)$ satisfying that there exist positive numbers $H_{1}(\underline{\eta},\overline{\eta})$, $H_{2}(\underline{\eta},\overline{\eta})$, and $H_{3}(\underline{\eta},\overline{\eta})$ such that, for all $T\geq 1$,

$$ $\displaystyle\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}\leq H_{1}(\underline{\eta}, \overline{\eta})\quad\text{and}\quad\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{\sum_{ t=0}^{T-1}\eta_{t}}\leq H_{2}(\underline{\eta},\overline{\eta})+\frac{H_{3}( \underline{\eta},\overline{\eta})}{T}.$ (28) $$

Let us assume that there exists a positive number $G$ such that
$\max\{\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S}(\bm{x}_{t}+\hat{\bm{
\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))\|_{2},\sup_{t\in\mathbb{N}\cup\{0\}}\|
\nabla\hat{f}^{\mathrm{SAM}}_{S_{t},\rho}(\bm{x}_{t})\|_{2},\sup_{t\in\mathbb{
N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t})\|_{2},G_{\perp
}\}\leq G$,
where $G_{\perp}:=\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|
_{2}<+\infty$ (Theorem 2.1). Let $\epsilon>0$ be the precision and let $b_{0}>0$, $\alpha\in\mathbb{R}$, and $\rho\geq 0$ such that

$$ $\displaystyle H_{1}\leq\frac{\epsilon^{2}}{12\sigma C}\left(\frac{\rho G}{ \sqrt{b_{0}}}+\frac{3\sigma}{nb_{0}}\sum_{i\in[n]}L_{i}\right)^{-1},\text{ }(| \alpha|+1)^{2}H_{2}\leq\frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{ 2}+4C(\sum_{i\in[n]}L_{i})^{2}\}},$ $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b_{0}}\epsilon^{2}}{6G(\sum_{i \in[n]}L_{i})(CG\sqrt{b_{0}}+B\sigma)},\text{ }\rho^{2}\leq\frac{n^{2}b_{0}^{2 }\epsilon^{4}}{168G^{2}(n^{2}+b_{0}^{2})(\sum_{i\in[n]}L_{i})^{2}},$ (29) $$

where $B$ and $C$ are positive constants. Then, there exists $t_{0}\in\mathbb{N}$ such that, for all $T\geq t_{0}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\leq\epsilon.$ $$

Let us start with a brief outline of the proof strategy of Theorem B.1, with an emphasis on the main difficulty that has to be overcome. The flow of our proof is almost the same in Theorem 5.1 of (Zhuang et al., ), indicating that GSAM using a decaying learning rate, $\eta_{t}=\eta_{0}/\sqrt{t}$, and a perturbation amplitude, $\rho_{t}=\rho_{0}/\sqrt{t}$, proportional to $\eta_{t}$ satisfies

$$ $\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\left\|\nabla\hat{f}_{S, \rho_{t}}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]\leq\frac{C_{1}+C_{ 2}\log T}{\sqrt{T}},$ $$

where $C_{1}$ and $C_{2}$ are positive constants. First, from the smoothness condition (A1) of $f_{S}$ and the descent lemma, we prove the inequality (Proposition B.1) that is satisfied for GSAM. Next, using the Cauchy–Schwarz inequality and the triangle inequality, we provide upper bounds of the terms $X_{t}$ (Proposition B.2), $Y_{t}$ (Proposition B.3), and $Z_{t}$ (Proposition B.4) in Proposition B.1. The main issue in Theorem B.1 is to evaluate the full gradient $\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})$ using the mini-batch gradient $\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})$. The difficulty comes from the fact that the unbiasedness of $\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})$ does not hold (i.e., $\mathbb{E}[\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})]\neq\nabla
\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})$, although (A2)(i) holds). However, we can resolve this issue using Theorem 2.1. In fact, in order to evaluate the upper bound of $X_{t}$, we can use Theorem 2.1 indicating the upper bound of $\|\hat{\bm{\omega}}_{t}\|_{2}=\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{
t})-\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})\|_{2}$. Another issue that has to be overcome in order to prove Theorem B.1 is to evaluate the upper bound of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t
})\|_{2}^{2}]$ using a learning rate $\eta_{t}\in[\underline{\eta},\overline{\eta}]$. We can resolve this issue by using $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t
})\|_{2}^{2}]\leq\sum_{t=0}^{T-1}\eta_{t}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{
\mathrm{SAM}}(\bm{x}_{t})\|_{2}^{2}]/\sum_{t=0}^{T-1}\eta_{t}$. As a result, we can provide an upper bound of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t
})\|_{2}^{2}]$. Finally, we set $H_{1}$, $H_{2}$, $\alpha$, and $\rho$ such that the upper bound of $\min_{t\in[0:T-1]}\mathbb{E}[\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t
})\|_{2}^{2}]$ is less than or equal to $\epsilon^{2}$.

###### Theorem B.1 ( ϵ italic-ϵ \epsilon italic_ϵ –approximation of GSAM with an increasing batch size and decaying learning rate).

### B.1 Lemma and propositions

The following lemma, called the descent lemma, holds.

###### Lemma B.1 (Descent lemma).

(Beck, , Lemma 5.7)
Let $f\colon\mathbb{R}^{d}\to\mathbb{R}$ be $L$–smooth. Then, we have that, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle f(\bm{y})\leq f(\bm{x})+\langle\nabla f(\bm{x}),\bm{y}-\bm{x} \rangle_{2}+\frac{L}{2}\|\bm{y}-\bm{x}\|_{2}^{2}.$ $$

Lemma B.1 leads to the following proposition.

###### Proposition B.1 .

Under Assumption 2.1, we have that, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle f_{S}(\bm{x}_{t+1}+\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+ 1}))$ $\displaystyle\leq f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))$ $\displaystyle\quad+\eta_{t}\underbrace{\left\langle\nabla f_{S}(\bm{x}_{t}+ \hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t})),\bm{d}_{t}\right\rangle_{2}}_{X_ {t}}+\underbrace{\left\langle\nabla f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t },\rho}(\bm{x}_{t})),\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1})-\hat{\bm {\epsilon}}_{S_{t},\rho}(\bm{x}_{t})\right\rangle_{2}}_{Y_{t}}$ $\displaystyle\quad+\frac{\sum_{i\in[n]}L_{i}}{n}\underbrace{\left\{\eta_{t}^{2 }\|\bm{d}_{t}\|_{2}^{2}+\left\|\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1} )-\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t})\right\|_{2}^{2}\right\}}_{Z_{t}}.$ $$

Proof of Proposition B.1: The $L_{i}$–smoothness (A1) of $f_{i}$ and the definition of $f_{S}$ ensure that, for all $\bm{x},\bm{y}\in\mathbb{R}^{d}$,

$$ $\displaystyle\|\nabla f_{S}(\bm{x})-\nabla f_{S}(\bm{y})\|_{2}$ $\displaystyle=\left\|\frac{1}{n}\sum_{i\in[n]}(\nabla f_{i}(\bm{x})-\nabla f_{ i}(\bm{y}))\right\|_{2}\leq\frac{1}{n}\sum_{i\in[n]}\|\nabla f_{i}(\bm{x})- \nabla f_{i}(\bm{y})\|_{2}$ $\displaystyle\leq\frac{1}{n}\sum_{i\in[n]}L_{i}\|\bm{x}-\bm{y}\|_{2},$ $$

which implies that $f_{S}$ is $(1/n)\sum_{i\in[n]}L_{i}$–smooth. Lemma B.1 thus guarantees that, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle f_{S}(\bm{x}_{t+1}+\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+ 1}))$ $\displaystyle\leq f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t} ))+\left\langle\nabla f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x} _{t})),(\bm{x}_{t+1}-\bm{x}_{t})+(\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t +1})-\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))\right\rangle_{2}$ $\displaystyle\quad+\frac{\sum_{i\in[n]}L_{i}}{2n}\left\|(\bm{x}_{t+1}-\bm{x}_{ t})+(\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1})-\hat{\bm{\epsilon}}_{S_{ t},\rho}(\bm{x}_{t}))\right\|_{2}^{2},$ $$

which, together with $\|\bm{x}+\bm{y}\|_{2}^{2}\leq 2(\|\bm{x}\|_{2}^{2}+\|\bm{y}\|_{2}^{2})$ and $\bm{x}_{t+1}-\bm{x}_{t}=\eta_{t}\bm{d}_{t}$, implies that

$$ $\displaystyle f_{S}(\bm{x}_{t+1}+\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+ 1}))$ $\displaystyle\leq f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))$ $\displaystyle\quad+\eta_{t}\left\langle\nabla f_{S}(\bm{x}_{t}+\hat{\bm{ \epsilon}}_{S_{t},\rho}(\bm{x}_{t})),\bm{d}_{t}\right\rangle_{2}+\langle\nabla f _{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t})),\hat{\bm{ \epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1})-\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x }_{t})\rangle_{2}$ $\displaystyle\quad+\frac{\sum_{i\in[n]}L_{i}}{n}\left\{\eta_{t}^{2}\|\bm{d}_{t }\|_{2}^{2}+\left\|\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1})-\hat{\bm{ \epsilon}}_{S_{t},\rho}(\bm{x}_{t})\right\|_{2}^{2}\right\},$ $$

which completes the proof.
$\Box$

Using Theorem 2.1, we provide an upper bound of $\mathbb{E}[X_{t}]$.

###### Proposition B.2 .

Suppose that Assumption 2.1 holds and there exist $G>0$ and $G_{\perp}>0$ such that $\max\{\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM}}_{S_{t},\rho
}(\bm{x}_{t})\|_{2},\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM
}}_{S,\rho}(\bm{x}_{t})\|_{2}\}\leq G$ and $\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|_{2}\leq G_
{\perp}$. Then, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[X_{t}]$ $\displaystyle\leq-\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}} (\bm{x}_{t})\right\|_{2}^{2}\right]+G\sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+ \frac{1}{n^{2}}\right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+2\sigma_{t}^{2}}$ $\displaystyle\quad+(G+|\alpha|G_{\perp})\frac{\rho B\sigma}{n\sqrt{b_{t}}}\sum _{i\in[n]}L_{i},$ $$

where $\sigma_{t}^{2}:=\mathbb{E}[\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_
{t})\|_{2}^{2}]\leq\sigma^{2}/b_{t}$ and $B>0$ is a constant.

Proof: Let $t\in\mathbb{N}\cup\{0\}$ and $b_{t}<n$. The definition of $\bm{d}_{t}=-(\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\alpha
\nabla f_{S_{t}\perp}(\bm{x}_{t}))$ implies that

$$ $\displaystyle X_{t}=\underbrace{-\left\langle\nabla f_{S}(\bm{x}_{t}+\hat{\bm{ \epsilon}}_{S_{t},\rho}(\bm{x}_{t})),\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}} (\bm{x}_{t})\right\rangle_{2}}_{X_{t,1}}+\underbrace{\alpha\left\langle\nabla f _{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t})),\nabla f_{S_{t} \perp}(\bm{x}_{t})\right\rangle_{2}}_{X_{t,2}}.$ (30) $$

Then, we have

$$ $\displaystyle\begin{split}X_{t,1}&=-\bigg{\{}\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}+\left\langle\nabla f_{S}(\bm{x}_{t}+ \hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))-\nabla\hat{f}_{S,\rho}^{\mathrm{ SAM}}(\bm{x}_{t}),\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right \rangle_{2}\\ &\quad+\Big{\langle}\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t}), \underbrace{\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})-\nabla\hat{f }_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})}_{-\hat{\bm{\omega}}_{t}}\Big{\rangle}_{ 2}\bigg{\}}\\ &\leq-\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2} +\underbrace{\left\|\nabla f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}( \bm{x}_{t}))-\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}}_{X _{t,3}}\left\|\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2 }\\ &\quad+\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\| \hat{\bm{\omega}}_{t}\|_{2},\end{split}$ (31) $$

where the second inequality comes from the Cauchy–Schwarz inequality. Suppose that $\nabla f_{S_{t}}(\bm{x}_{t})\neq\bm{0}$ and $\nabla f_{S}(\bm{x}_{t})\neq\bm{0}$. The $(1/n)\sum_{i\in[n]}L_{i}$–smoothness of $f_{S}$ implies that

$$ $\displaystyle X_{t,3}$ $\displaystyle=\left\|\nabla f_{S}\left(\bm{x}_{t}+\rho\frac{\nabla f_{S_{t}}( \bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}\right)-\nabla f_{S}\left( \bm{x}_{t}+\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2 }}\right)\right\|_{2}$ $\displaystyle\leq\frac{\rho}{n}\sum_{i\in[n]}L_{i}\left\|\frac{\nabla f_{S_{t} }(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}-\frac{\nabla f_{S}(\bm{x} _{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right\|_{2}.$ $$

The discussion in (Zhuang et al., , Pages 15 and 16) implies there exists $B_{t}\geq 0$ such that

$$ $\displaystyle\left\|\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm {x}_{t})\|_{2}}-\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{ 2}}\right\|_{2}\leq B_{t}\left\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{ x}_{t})\right\|_{2}$ (32) $$

Let $B:=\sup_{t\in\mathbb{N}\cup\{0\}}B_{t}$. Then, Proposition A.1 ensures that

$$ $\displaystyle\mathbb{E}[X_{t,3}]\leq\frac{\rho B\sigma}{n\sqrt{b_{t}}}\sum_{i \in[n]}L_{i}.$ (33) $$

Suppose that $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ or $\nabla f_{S}(\bm{x}_{t})=\bm{0}$. Let $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$. The $(1/n)\sum_{i\in[n]}L_{i}$–smoothness of $f_{S}$ ensures that

$$ $\displaystyle X_{t,3}$ $\displaystyle=\left\|\nabla f_{S}\left(\bm{x}_{t}+\bm{u}\right)-\nabla f_{S} \left(\bm{x}_{t}+\rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t} )\|_{2}}\right)\right\|_{2}\leq\frac{1}{n}\sum_{i\in[n]}L_{i}\left\|\bm{u}- \rho\frac{\nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right\|_ {2},$ $$

which, together with $\|\bm{u}\|_{2}\leq\rho$, implies there exists $C_{t}\geq 0$ such that

$$ $\displaystyle X_{t,3}\leq\frac{\rho C_{t}}{n}\sum_{i\in[n]}L_{i}\left\|\frac{ \nabla f_{S_{t}}(\bm{x}_{t})}{\|\nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}-\frac{ \nabla f_{S}(\bm{x}_{t})}{\|\nabla f_{S}(\bm{x}_{t})\|_{2}}\right\|_{2}$ $$

Hence, Proposition A.1 implies that (33) holds. A discussion similar to the case where $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ ensures that (33) holds for $\nabla f_{S}(\bm{x}_{t})=\bm{0}$. Taking the total expectation on both sides of (31), together with (33) and Theorem 2.1, yields

$$ $\displaystyle\mathbb{E}[X_{t,1}]$ $\displaystyle\leq-\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}} (\bm{x}_{t})\right\|_{2}^{2}\right]+G\sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+ \frac{1}{n^{2}}\right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+2\sigma_{t}^{2}}$ $\displaystyle\quad+\frac{\rho BG\sigma}{n\sqrt{b_{t}}}\sum_{i\in[n]}L_{i}.$ (34) $$

The Cauchy–Schwarz inequality implies that

$$ $\displaystyle X_{t,2}$ $\displaystyle=\alpha\left\langle\nabla f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S _{t},\rho}(\bm{x}_{t}))-\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t})+ \nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t}),\nabla f_{S_{t}\perp}(\bm{x} _{t})\right\rangle_{2}$ $\displaystyle\leq|\alpha|X_{t,3}\left\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\right \|_{2}+\alpha\left\langle\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t}), \nabla f_{S_{t}\perp}(\bm{x}_{t})\right\rangle_{2}$ $\displaystyle\leq|\alpha|G_{\perp}X_{t,3}+\alpha\left\langle\nabla\hat{f}^{ \mathrm{SAM}}_{S,\rho}(\bm{x}_{t}),\nabla f_{S_{t}\perp}(\bm{x}_{t})\right \rangle_{2},$ $$

which, together with $\mathbb{E}_{\bm{\xi}_{t}}[\nabla f_{S_{t}\perp}(\bm{x}_{t})|\bm{\xi}_{t-1}]=
\nabla f_{S\perp}(\bm{x}_{t})$, $\langle\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t}),\nabla f_{S\perp}(\bm
{x}_{t})\rangle_{2}=0$, and (33), implies that

$$ $\displaystyle\mathbb{E}[X_{t,2}]\leq\frac{|\alpha|\rho BG_{\perp}\sigma}{n \sqrt{b_{t}}}\sum_{i\in[n]}L_{i}.$ (35) $$

Accordingly, (30), (B.1), and (35) guarantee that

$$ $\displaystyle\mathbb{E}[X_{t}]$ $\displaystyle\leq-\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}} (\bm{x}_{t})\right\|_{2}^{2}\right]+G\sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+ \frac{1}{n^{2}}\right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+2\sigma_{t}^{2}}$ $\displaystyle\quad+(G+|\alpha|G_{\perp})\frac{\rho B\sigma}{n\sqrt{b_{t}}}\sum _{i\in[n]}L_{i},$ $$

which completes the proof.
$\Box$

###### Proposition B.3 .

Suppose that the assumptions in Proposition B.2 hold and there exists $G>0$ such that
$\max\{\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S}(\bm{x}_{t}+\hat{\bm{
\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))\|_{2},\sup_{t\in\mathbb{N}\cup\{0\}}\|
\nabla\hat{f}^{\mathrm{SAM}}_{S_{t},\rho}(\bm{x}_{t})\|_{2},\sup_{t\in\mathbb{
N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t})\|_{2},G_{\perp
}\}\leq G$.
Then, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[Y_{t}]\leq\rho CG\left\{\frac{\eta_{t}(|\alpha|+1)G}{n }\sum_{i\in[n]}L_{i}+\frac{2\sigma}{\sqrt{b_{t}}}\right\},$ $$

where $C>0$ is a constant.

Proof: Let $t\in\mathbb{N}\cup\{0\}$. The Cauchy–Schwarz inequality ensures that

$$ $\displaystyle Y_{t}\leq G\left\|\hat{\bm{\epsilon}}_{S_{t+1},\rho}(\bm{x}_{t+1 })-\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t})\right\|_{2}=:GY_{t,1}.$ (36) $$

Suppose that $\nabla f_{S_{t+1}}(\bm{x}_{t+1})\neq\bm{0}$ and $\nabla f_{S_{t}}(\bm{x}_{t})\neq\bm{0}$. The discussion in (Zhuang et al., , Pages 15 and 16) (see (32)) implies that there exists $C_{t}\geq 0$ such that

$$ $\displaystyle Y_{t,1}=\rho\left\|\frac{\nabla f_{S_{t+1}}(\bm{x}_{t+1})}{\| \nabla f_{S_{t+1}}(\bm{x}_{t+1})\|_{2}}-\frac{\nabla f_{S_{t}}(\bm{x}_{t})}{\| \nabla f_{S_{t}}(\bm{x}_{t})\|_{2}}\right\|_{2}\leq\rho C_{t}\left\|\nabla f_{ S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S_{t}}(\bm{x}_{t})\right\|_{2}.$ (37) $$

Let $C:=\sup_{t\in\mathbb{N}\cup\{0\}}C_{t}$. The triangle inequality gives

$$ $\displaystyle\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S_{t}}(\bm{x}_{ t})\right\|_{2}$ $\displaystyle\leq\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x}_{ t+1})\right\|_{2}+\left\|\nabla f_{S}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x}_{t}) \right\|_{2}+\left\|\nabla f_{S}(\bm{x}_{t})-\nabla f_{S_{t}}(\bm{x}_{t}) \right\|_{2},$ $$

which, together with the $(1/n)\sum_{i\in[n]}L_{i}$–smoothness of $f_{S}$, $\bm{x}_{t+1}-\bm{x}_{t}=\eta_{t}\bm{d}_{t}$, (36), and (37), implies that

$$ $\displaystyle Y_{t,1}\leq\rho C\left\{\frac{\eta_{t}}{n}\sum_{i\in[n]}L_{i}\| \bm{d}_{t}\|_{2}+\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x}_{ t+1})\right\|_{2}+\left\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t}) \right\|_{2}\right\}.$ $$

Moreover, the Cauchy–Schwarz inequality and the definitions of $G$ and $G_{\perp}$ ensure that

$$ $\displaystyle\begin{split}\|\bm{d}_{t}\|_{2}^{2}&=\left\|\nabla\hat{f}_{S_{t}, \rho}^{\mathrm{SAM}}(\bm{x}_{t})-\alpha\nabla f_{S_{t}\perp}(\bm{x}_{t})\right \|_{2}^{2}\\ &=\left\|\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2} -2\alpha\left\langle\nabla\hat{f}_{S_{t},\rho}^{\mathrm{SAM}}(\bm{x}_{t}), \nabla f_{S_{t}\perp}(\bm{x}_{t})\right\rangle_{2}+|\alpha|^{2}\left\|\nabla f _{S_{t}\perp}(\bm{x}_{t})\right\|_{2}^{2}\\ &\leq G^{2}+2|\alpha|GG_{\perp}+|\alpha|^{2}G_{\perp}^{2}\leq(|\alpha|+1)^{2}G ^{2}.\end{split}$ (38) $$

Accordingly, we have

$$ $\displaystyle Y_{t,1}\leq\rho C\left\{\frac{\eta_{t}(|\alpha|+1)G}{n}\sum_{i \in[n]}L_{i}+\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x}_{t+1} )\right\|_{2}+\left\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S}(\bm{x}_{t}) \right\|_{2}\right\},$ $$

which, together with Proposition A.1, guarantees that

$$ $\displaystyle\mathbb{E}[Y_{t,1}]\leq\rho C\left\{\frac{\eta_{t}(|\alpha|+1)G}{ n}\sum_{i\in[n]}L_{i}+\frac{2\sigma}{\sqrt{b_{t}}}\right\}.$ (39) $$

Hence, from (36),

$$ $\displaystyle\mathbb{E}[Y_{t}]\leq\rho CG\left\{\frac{\eta_{t}(|\alpha|+1)G}{n }\sum_{i\in[n]}L_{i}+\frac{2\sigma}{\sqrt{b_{t}}}\right\}.$ $$

We can show that Proposition B.3 holds for the case where $\nabla f_{S_{t+1}}(\bm{x}_{t+1})=\bm{0}$ or $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ by proving Proposition B.2.
$\Box$

###### Proposition B.4 .

Suppose that the assumptions in Proposition B.3 hold. Then, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\mathbb{E}[Z_{t}]\leq\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}+\frac{6C\sigma ^{2}}{b_{t}}.$ $$

Proof: Let $t\in\mathbb{N}\cup\{0\}$. From (38), we have

$$ $\displaystyle\eta_{t}^{2}\mathbb{E}[\|\bm{d}_{t}\|_{2}]\leq\eta_{t}^{2}(| \alpha|+1)^{2}G^{2}.$ $$

Suppose that $\nabla f_{S_{t+1}}(\bm{x}_{t+1})\neq\bm{0}$ and $\nabla f_{S_{t}}(\bm{x}_{t})\neq\bm{0}$. Then, from $\|\bm{x}+\bm{y}\|_{2}^{2}\leq 2(\|\bm{x}\|_{2}^{2}+\|\bm{y}\|_{2}^{2})$,

$$ $\displaystyle\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S_{t}}(\bm{x}_{ t})\right\|_{2}^{2}$ $\displaystyle\leq 2\left\|\nabla f_{S_{t+1}}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x} _{t+1})\right\|_{2}^{2}+4\left\|\nabla f_{S}(\bm{x}_{t+1})-\nabla f_{S}(\bm{x} _{t})\right\|_{2}^{2}+4\left\|\nabla f_{S}(\bm{x}_{t})-\nabla f_{S_{t}}(\bm{x} _{t})\right\|_{2}^{2}.$ $$

A discussion similar to the one showing (39) ensures that

$$ $\displaystyle\mathbb{E}[Y_{t,1}^{2}]=\mathbb{E}\left[\left\|\hat{\bm{\epsilon} }_{S_{t+1},\rho}(\bm{x}_{t+1})-\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}) \right\|_{2}^{2}\right]\leq 2C\left\{\frac{2\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}} {n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{3\sigma^{2}}{b_{t}}\right\}.$ $$

The above inequality holds for the case where $\nabla f_{S_{t+1}}(\bm{x}_{t+1})=\bm{0}$ or $\nabla f_{S_{t}}(\bm{x}_{t})=\bm{0}$ by an argument similar to the one used to prove Proposition B.2. Hence,

$$ $\displaystyle\mathbb{E}[Z_{t}]$ $\displaystyle\leq\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}+2C\left\{\frac{2\eta_{t}^{2 }(|\alpha|+1)^{2}G^{2}}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}+\frac{3 \sigma^{2}}{b_{t}}\right\}$ $\displaystyle=\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}\left\{1+\frac{4C}{n^{2}}\bigg{ (}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}+\frac{6C\sigma^{2}}{b_{t}},$ $$

which completes the proof.
$\Box$

Proof of Theorem B.1:
Let us define $F_{\rho}(t):=f_{S}(\bm{x}_{t}+\hat{\bm{\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))$. From Proposition B.1, Proposition B.2, Proposition B.3, and Proposition B.4, for all $t\in\mathbb{N}\cup\{0\}$, we have

$$ $\displaystyle\mathbb{E}[F_{\rho}(t+1)]\leq\mathbb{E}[F_{\rho}(t)]+\eta_{t} \mathbb{E}[X_{t}]+\mathbb{E}[Y_{t}]+\frac{\sum_{i\in[n]}L_{i}}{n}\mathbb{E}[Z_ {t}]$ $\displaystyle\leq\mathbb{E}[F_{\rho}(t)]-\eta_{t}\mathbb{E}\left[\left\|\nabla \hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]+\eta_{t}G \sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+\frac{1}{n^{2}}\right)\bigg{(}\sum_{i \in[n]}L_{i}\bigg{)}^{2}+2\sigma_{t}^{2}}$ $\displaystyle\quad+\eta_{t}(|\alpha|+1)\frac{\rho BG\sigma}{n\sqrt{b_{t}}}\sum _{i\in[n]}L_{i}+\rho CG\left\{\frac{\eta_{t}(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{ i}+\frac{2\sigma}{\sqrt{b_{t}}}\right\}$ $\displaystyle\quad+\frac{\sum_{i\in[n]}L_{i}}{n}\left[\eta_{t}^{2}(|\alpha|+1) ^{2}G^{2}\left\{1+\frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2} \right\}+\frac{6C\sigma^{2}}{b_{t}}\right],$ $$

which implies that

$$ $\displaystyle\begin{split}\eta_{t}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho }^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]&\leq\left(\mathbb{E}[F_{ \rho}(t)]-\mathbb{E}[F_{\rho}(t+1)]\right)+2\sigma C\left(\frac{\rho G}{\sqrt{ b_{t}}}+\frac{3\sigma}{nb_{t}}\sum_{i\in[n]}L_{i}\right)\\ &\quad+\frac{\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_{i}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}\\ &\quad+\eta_{t}G\sqrt{4\rho^{2}\left(\frac{1}{b_{t}^{2}}+\frac{1}{n^{2}}\right )\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+2\sigma_{t}^{2}}\\ &\quad+\eta_{t}\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i}\left(CG+\frac{B \sigma}{\sqrt{b_{t}}}\right).\end{split}$ (40) $$

Let $\epsilon>0$. From $g(b_{t})=\sigma_{t}^{2}:=\mathbb{E}[\|\nabla f_{S_{t}}(\bm{x}_{t})-\nabla f_{S
}(\bm{x}_{t})\|_{2}^{2}]\leq\sigma^{2}/b_{t}$ ($t\in\mathbb{N}\cup\{0\}$) (see Proposition A.1 and (Freund, , Theorem 8.6)) and $g(n)=0$, the sequence $(b_{t})$ of increasing batch sizes implies that there exists $t_{0}\in\mathbb{N}$ such that, for all $t\geq t_{0}$,

$$ $\displaystyle 2\sigma_{t}^{2}\leq\frac{\epsilon^{4}}{7G^{2}}.$ $$

Let $T\geq t_{0}+1$. Summing the above inequality from $t=0$ to $t=T-1$, together with $b_{0}\leq b_{t}$ and $\eta_{t}\leq\overline{\eta}$ ($t\in\mathbb{N}\cup\{0\}$), ensures that

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}\mathbb{E}\left[\left\|\nabla\hat{f}_{S, \rho}^{\mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\left(\mathbb{E}[F_{\rho}(0)]-f_{S}^{\star}\right)+2\sigma C \left(\frac{\rho G}{\sqrt{b_{0}}}+\frac{3\sigma}{nb_{0}}\sum_{i\in[n]}L_{i} \right)T$ $\displaystyle\quad+\frac{(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_{i}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}\sum_{t=0}^{T-1 }\eta_{t}^{2}$ $\displaystyle\quad+G\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}} \right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b_{0}}}t_{0} \overline{\eta}$ $\displaystyle\quad+G\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}} \right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{\epsilon^{4}}{7G^{2}}}\sum_ {t=t_{0}}^{T-1}\eta_{t}$ $\displaystyle\quad+\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i}\left(CG+ \frac{B\sigma}{\sqrt{b_{0}}}\right)\sum_{t=0}^{T-1}\eta_{t},$ $$

where $f_{S}^{\star}$ is the minimum value of $f_{S}$ over $\mathbb{R}^{d}$. Since we have that

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]\leq\frac{\sum_{t=0}^{T-1}\eta _{t}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{SAM}}(\bm{x}_{t}) \right\|_{2}^{2}\right]}{\sum_{t=0}^{T-1}\eta_{t}},$ $$

we also have that

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\frac{\mathbb{E}[F_{\rho}(0)]-f_{S}^{\star}}{\sum_{t=0}^{T-1} \eta_{t}}+2\sigma C\left(\frac{\rho G}{\sqrt{b_{0}}}+\frac{3\sigma}{nb_{0}} \sum_{i\in[n]}L_{i}\right)\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle\quad+\frac{(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_{i}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}\frac{\sum_{t=0 }^{T-1}\eta_{t}^{2}}{\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle\quad+G\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}} \right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b_{0}}}\frac{t _{0}\overline{\eta}}{\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle\quad+G\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}} \right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{\epsilon^{4}}{7G^{2}}}$ $\displaystyle\quad+\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i}\left(CG+ \frac{B\sigma}{\sqrt{b_{0}}}\right).$ (41) $$

From (28), i.e.,

$$ $\displaystyle\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}\leq H_{1}(\underline{\eta}, \overline{\eta})\quad\text{and}\quad\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{\sum_{ t=0}^{T-1}\eta_{t}}\leq H_{2}(\underline{\eta},\overline{\eta})+\frac{H_{3}( \underline{\eta},\overline{\eta})}{T},$ $$

we have that

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\underbrace{\frac{H_{1}(\mathbb{E}[F_{\rho}(0)]-f_{S}^{\star} )}{T}+GH_{1}\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}}\right) \big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b_{0}}}\frac{t_{0} \overline{\eta}}{T}}_{U_{1}\leq\frac{\epsilon^{2}}{6}}$ $\displaystyle\quad+\underbrace{\frac{(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_ {i}\left\{1+\frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\} \frac{H_{3}}{T}}_{U_{2}\leq\frac{\epsilon^{2}}{6}}$ $\displaystyle\quad+\underbrace{\left(\frac{\rho G}{\sqrt{b_{0}}}+\frac{3\sigma }{nb_{0}}\sum_{i\in[n]}L_{i}\right)2\sigma CH_{1}}_{U_{3}\leq\frac{\epsilon^{2 }}{6}}+\underbrace{\frac{(|\alpha|+1)^{2}G^{2}H_{2}}{n}\sum_{i\in[n]}L_{i} \left\{1+\frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}}_{U_{ 4}\leq\frac{\epsilon^{2}}{6}}$ $\displaystyle\quad+\underbrace{\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i} \left(CG+\frac{B\sigma}{\sqrt{b_{0}}}\right)}_{U_{5}\leq\frac{\epsilon^{2}}{6} }+\underbrace{G\sqrt{4\rho^{2}\left(\frac{1}{b_{0}^{2}}+\frac{1}{n^{2}}\right) \big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{\epsilon^{4}}{7G^{2}}}}_{U_{6}\leq \frac{\epsilon^{2}}{6}}.$ $$

It is guaranteed that there exists $t_{1}\in\mathbb{N}$ such that,
for all $T\geq\max\{t_{0},t_{1}\}$, $U_{1}\leq\frac{\epsilon^{2}}{6}$ and $U_{2}\leq\frac{\epsilon^{2}}{6}$. Moreover, if (29) holds, i.e.,

$$ $\displaystyle H_{1}\leq\frac{\epsilon^{2}}{12\sigma C}\left(\frac{\rho G}{ \sqrt{b_{0}}}+\frac{3\sigma}{nb_{0}}\sum_{i\in[n]}L_{i}\right)^{-1},\text{ }(| \alpha|+1)^{2}H_{2}\leq\frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{ 2}+4C(\sum_{i\in[n]}L_{i})^{2}\}},$ $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b_{0}}\epsilon^{2}}{6G(\sum_{i \in[n]}L_{i})(CG\sqrt{b_{0}}+B\sigma)},\text{ }\rho^{2}\leq\frac{n^{2}b_{0}^{2 }\epsilon^{4}}{168G^{2}(n^{2}+b_{0}^{2})(\sum_{i\in[n]}L_{i})^{2}},$ $$

then $U_{i}\leq\frac{\epsilon^{2}}{6}$ ($i=3,4,5,6$), i.e.,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\leq\epsilon.$ (42) $$

This completes the proof.
$\Box$

###### Lemma B.1 (Descent lemma).

###### Proposition B.1 .

###### Proposition B.2 .

###### Proposition B.3 .

###### Proposition B.4 .

### B.2 Proof of Theorem 2.3

Let $\eta_{t}=\eta>0$. Then, we have

$$ $\displaystyle\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}=\frac{1}{\eta}=:H_{1}\text{ and }\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{\sum_{t=0}^{T-1}\eta_{t}}=\eta=:H_{2},$ $$

which implies that (28) with $H_{3}=0$ holds. Hence, from (29), the assertion in Theorem 2.3 holds.
$\Box$

### B.3 Proof of Theorem 2.4

We can prove the following corollary by using Theorem B.1.

###### Corollary B.1 ( $\epsilon$ –approximation of GSAM with a constant batch size and decaying learning rate).

Consider the sequence $(\bm{x}_{t})$ generated by the mini-batch GSAM algorithm (Algorithm 1) with a constant batch size $b\in(0,n]$ and a decaying learning rate $\eta_{t}\in[\underline{\eta},\overline{\eta}]\subset[0,+\infty)$ satisfying that there exist positive numbers $H_{1}(\underline{\eta},\overline{\eta})$, $H_{2}(\underline{\eta},\overline{\eta})$, and $H_{3}(\underline{\eta},\overline{\eta})$ such that, for all $T\geq 1$, (28) holds. We will assume that there exists a positive number $G$ such that $\max\{\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S}(\bm{x}_{t}+\hat{\bm{
\epsilon}}_{S_{t},\rho}(\bm{x}_{t}))\|_{2},\sup_{t\in\mathbb{N}\cup\{0\}}\|
\nabla\hat{f}^{\mathrm{SAM}}_{S_{t},\rho}(\bm{x}_{t})\|_{2},\sup_{t\in\mathbb{
N}\cup\{0\}}\|\nabla\hat{f}^{\mathrm{SAM}}_{S,\rho}(\bm{x}_{t})\|_{2},G_{\perp
}\}\leq G$, where $G_{\perp}:=\sup_{t\in\mathbb{N}\cup\{0\}}\|\nabla f_{S_{t}\perp}(\bm{x}_{t})\|
_{2}<+\infty$ (Theorem 2.1). Let $\epsilon>0$ be the precision and let $b_{0}>0$, $\alpha\in\mathbb{R}$, and $\rho\geq 0$ such that

$$ $\displaystyle H_{1}\leq\frac{\epsilon^{2}}{12\sigma C}\left(\frac{\rho G}{ \sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)^{-1},\text{ }(|\alpha|+ 1)^{2}H_{2}\leq\frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C( \sum_{i\in[n]}L_{i})^{2}\}},$ $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b}\epsilon^{2}}{6G(\sum_{i\in[n] }L_{i})(CG\sqrt{b}+B\sigma)},\text{ }\rho^{2}\leq\frac{n^{2}b^{2}\epsilon^{4}} {144G^{2}(n^{2}+b^{2})(\sum_{i\in[n]}L_{i})^{2}},$ (43) $$

where $B$ and $C$ are positive constants. Then, there exists $t_{0}\in\mathbb{N}$ such that, for all $T\geq t_{0}$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}\right]\leq\epsilon.$ $$

Proof: Let $b_{t}=b$ ($t\in\mathbb{N}\cup\{0\}$). Using inequality (40) that was used to prove Theorem B.1, we have that, for all $t\in\mathbb{N}\cup\{0\}$,

$$ $\displaystyle\eta_{t}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{\mathrm{ SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\left(\mathbb{E}[F_{\rho}(t)]-\mathbb{E}[F_{\rho}(t+1)]\right )+2\sigma C\left(\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)$ $\displaystyle\quad+\frac{\eta_{t}^{2}(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_ {i}\left\{1+\frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}$ $\displaystyle\quad+\eta_{t}G\sqrt{4\rho^{2}\left(\frac{1}{b^{2}}+\frac{1}{n^{2 }}\right)\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b}}$ $\displaystyle\quad+\eta_{t}\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i}\left (CG+\frac{B\sigma}{\sqrt{b}}\right),$ $$

which, together with a discussion similar to the one showing (41), implies that, for all $T\geq 1$,

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\frac{\mathbb{E}[F_{\rho}(0)]-f_{S}^{\star}}{\sum_{t=0}^{T-1} \eta_{t}}+2\sigma C\left(\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[ n]}L_{i}\right)\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle\quad+\frac{(|\alpha|+1)^{2}G^{2}}{n}\sum_{i\in[n]}L_{i}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}\frac{\sum_{t=0 }^{T-1}\eta_{t}^{2}}{\sum_{t=0}^{T-1}\eta_{t}}$ $\displaystyle\quad+G\sqrt{4\rho^{2}\left(\frac{1}{b^{2}}+\frac{1}{n^{2}}\right )\big{(}\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b}}$ $\displaystyle\quad+\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i}\left(CG+ \frac{B\sigma}{\sqrt{b}}\right).$ $$

Let $\epsilon>0$. From (28),

$$ $\displaystyle\min_{t\in[0:T-1]}\mathbb{E}\left[\left\|\nabla\hat{f}_{S,\rho}^{ \mathrm{SAM}}(\bm{x}_{t})\right\|_{2}^{2}\right]$ $\displaystyle\leq\underbrace{\frac{H_{1}(\mathbb{E}[F_{\rho}(0)]-f_{S}^{\star} )}{T}}_{V_{1}\leq\frac{\epsilon^{2}}{6}}+\underbrace{\frac{(|\alpha|+1)^{2}G^{ 2}}{n}\sum_{i\in[n]}L_{i}\left\{1+\frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i} \bigg{)}^{2}\right\}\frac{H_{3}}{T}}_{V_{2}\leq\frac{\epsilon^{2}}{6}}$ $\displaystyle\quad+\underbrace{2\sigma CH_{1}\left(\frac{\rho G}{\sqrt{b}}+ \frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)}_{V_{3}\leq\frac{\epsilon^{2}}{6} }+\underbrace{\frac{(|\alpha|+1)^{2}G^{2}H_{2}}{n}\sum_{i\in[n]}L_{i}\left\{1+ \frac{4C}{n^{2}}\bigg{(}\sum_{i\in[n]}L_{i}\bigg{)}^{2}\right\}}_{V_{4}\leq \frac{\epsilon^{2}}{6}}$ $\displaystyle\quad+\underbrace{\frac{\rho(|\alpha|+1)G}{n}\sum_{i\in[n]}L_{i} \left(CG+\frac{B\sigma}{\sqrt{b}}\right)}_{V_{5}\leq\frac{\epsilon^{2}}{6}}+ \underbrace{G\sqrt{4\rho^{2}\left(\frac{1}{b^{2}}+\frac{1}{n^{2}}\right)\big{( }\sum_{i\in[n]}L_{i}\big{)}^{2}+\frac{2\sigma^{2}}{b}}}_{V_{6}\leq\frac{ \epsilon^{2}}{6}}.$ $$

There exists $t_{2}\in\mathbb{N}$ such that, for all $T\geq t_{2}$, $V_{1}\leq\frac{\epsilon^{2}}{6}$ and $V_{2}\leq\frac{\epsilon^{2}}{6}$. Moreover, if

$$ $\displaystyle H_{1}\leq\frac{\epsilon^{2}}{12\sigma C}\left(\frac{\rho G}{ \sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)^{-1},\text{ }(|\alpha|+ 1)^{2}H_{2}\leq\frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C( \sum_{i\in[n]}L_{i})^{2}\}},$ $\displaystyle\rho(|\alpha|+1)\leq\frac{n\sqrt{b}\epsilon^{2}}{6G(\sum_{i\in[n] }L_{i})(CG\sqrt{b}+B\sigma)},\text{ }\rho^{2}\leq\frac{\epsilon^{4}}{144G^{2}} \frac{n^{2}b^{2}}{(n^{2}+b^{2})(\sum_{i\in[n]}L_{i})^{2}},$ $$

then $V_{i}\leq\frac{\epsilon^{2}}{6}$ ($i=3,4,5,6$), i.e., (42) holds.
$\Box$

Proof of Theorem 2.4: Let $\eta_{t}$ be the cosine-annealing learning rate defined by (15). We then have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}$ $\displaystyle=\underline{\eta}KE+\frac{\overline{\eta}-\underline{\eta}}{2}KE+ \frac{\overline{\eta}-\underline{\eta}}{2}\sum_{t=0}^{KE-1}\cos\left\lfloor \frac{t}{K}\right\rfloor\frac{\pi}{E}.$ $$

From $\sum_{t=0}^{KE}\cos\lfloor\frac{t}{K}\rfloor\frac{\pi}{E}=0$, we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{ \pi}{E}=-\cos\pi=1.$ (44) $$

We thus have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}$ $\displaystyle=\underline{\eta}KE+\frac{\overline{\eta}-\underline{\eta}}{2}KE+ \frac{\overline{\eta}-\underline{\eta}}{2}$ $\displaystyle=\frac{1}{2}\{(\underline{\eta}+\overline{\eta})KE+\overline{\eta }-\underline{\eta}\}$ $\displaystyle\geq\frac{(\underline{\eta}+\overline{\eta})KE}{2}.$ $$

Moreover, we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\underline{\eta}^{2}KE+\underline{\eta}(\overline{\eta}- \underline{\eta})\sum_{t=0}^{KE-1}\left(1+\cos\left\lfloor\frac{t}{K}\right \rfloor\frac{\pi}{E}\right)$ $\displaystyle\quad+\frac{(\overline{\eta}-\underline{\eta})^{2}}{4}\sum_{t=0}^ {KE-1}\left(1+\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}\right)^{2},$ $$

which implies that

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\underline{\eta}\overline{\eta}KE+\frac{(\overline{\eta}- \underline{\eta})^{2}}{4}KE+\underline{\eta}(\overline{\eta}-\underline{\eta}) \sum_{t=0}^{KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}$ $\displaystyle\quad+\frac{(\overline{\eta}-\underline{\eta})^{2}}{2}\sum_{t=0}^ {KE-1}\cos\left\lfloor\frac{t}{K}\right\rfloor\frac{\pi}{E}+\frac{(\overline{ \eta}-\underline{\eta})^{2}}{4}\sum_{t=0}^{KE-1}\cos^{2}\left\lfloor\frac{t}{K }\right\rfloor\frac{\pi}{E}.$ $$

From

$$ $\displaystyle\sum_{t=0}^{KE}\cos^{2}\left\lfloor\frac{t}{K}\right\rfloor\frac{ \pi}{E}$ $\displaystyle=\frac{1}{2}\sum_{t=0}^{KE}\left(1+\cos 2\left\lfloor\frac{t}{K} \right\rfloor\frac{\pi}{E}\right)$ $\displaystyle=\frac{1}{2}(KE+1)+\frac{1}{2}$ $\displaystyle=\frac{KE}{2}+1,$ $$

we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\cos^{2}\left\lfloor\frac{t}{K}\right\rfloor \frac{\pi}{E}=\frac{KE}{2}+1-\cos^{2}\pi=\frac{KE}{2}.$ $$

From (44), we have

$$ $\displaystyle\sum_{t=0}^{KE-1}\eta_{t}^{2}$ $\displaystyle=\frac{(\underline{\eta}+\overline{\eta})^{2}}{4}KE+\underline{ \eta}(\overline{\eta}-\underline{\eta})+\frac{(\overline{\eta}-\underline{\eta })^{2}}{2}+\frac{(\overline{\eta}-\underline{\eta})^{2}}{4}\frac{KE}{2}$ $\displaystyle=\frac{3\underline{\eta}^{2}+2\underline{\eta}\overline{\eta}+3 \overline{\eta}^{2}}{8}KE+\frac{(\overline{\eta}-\underline{\eta})(\overline{ \eta}+\underline{\eta})}{2}.$ $$

Hence, we have

$$ $\displaystyle\frac{KE}{\sum_{t=0}^{KE-1}\eta_{t}}\leq\frac{2KE}{(\underline{ \eta}+\overline{\eta})KE}<\frac{2}{\underline{\eta}+\overline{\eta}}=:H_{1}$ $$

and

$$ $\displaystyle\frac{\sum_{t=0}^{KE-1}\eta_{t}^{2}}{\sum_{t=0}^{KE-1}\eta_{t}}$ $\displaystyle\leq\underbrace{\frac{(3\underline{\eta}^{2}+2\underline{\eta} \overline{\eta}+3\overline{\eta}^{2})}{4(\underline{\eta}+\overline{\eta})}}_{ H_{2}}+\frac{1}{KE}\underbrace{(\overline{\eta}-\underline{\eta})}_{H_{3}}.$ $$

Accordingly, (28) holds. From (43), we have

$$ $\displaystyle\frac{2}{\underline{\eta}+\overline{\eta}}\leq\frac{\epsilon^{2}} {12\sigma C}\left(\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i }\right)^{-1},$ $\displaystyle(|\alpha|+1)^{2}\frac{(3\underline{\eta}^{2}+2\underline{\eta} \overline{\eta}+3\overline{\eta}^{2})}{4(\underline{\eta}+\overline{\eta})} \leq\frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n] }L_{i})^{2}\}}.$ $$

In particular, when $\underline{\eta}=0$, we have

$$ $\displaystyle\frac{2}{\overline{\eta}}\leq\frac{\epsilon^{2}}{12\sigma C}\left (\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)^{-1},$ $\displaystyle(|\alpha|+1)^{2}\frac{3\overline{\eta}}{4}\leq\frac{n^{3}\epsilon ^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n]}L_{i})^{2}\}}.$ $$

Therefore, Corollary B.1 leads to the assertion in Theorem 2.4.

Let $\eta_{t}$ be the linear learning rate defined by (16). We then have

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}=\overline{\eta}T+\frac{\underline{\eta}- \overline{\eta}}{T}\frac{(T-1)T}{2}=\frac{1}{2}\{(\underline{\eta}+\overline{ \eta})T+\overline{\eta}-\underline{\eta}\}>\frac{\underline{\eta}+\overline{ \eta}}{2}T,$ $$

where the third inequality comes from $\overline{\eta}>\underline{\eta}$. We also have

$$ $\displaystyle\sum_{t=0}^{T-1}\eta_{t}^{2}$ $\displaystyle=\left(\frac{\underline{\eta}-\overline{\eta}}{T}\right)^{2}\frac {(T-1)T(2T-1)}{6}+\frac{2(\underline{\eta}-\overline{\eta})\overline{\eta}}{T} \frac{(T-1)T}{2}+\overline{\eta}^{2}T$ $\displaystyle=\frac{(\underline{\eta}-\overline{\eta})^{2}(T-1)(2T-1)}{6T}+( \underline{\eta}-\overline{\eta})\overline{\eta}(T-1)+\overline{\eta}^{2}T$ $\displaystyle<\frac{(\underline{\eta}-\overline{\eta})^{2}T}{3}+(\underline{ \eta}-\overline{\eta})\overline{\eta}T+\overline{\eta}^{2}T$ $\displaystyle=\frac{(\underline{\eta}-\overline{\eta})^{2}T}{3}+\underline{ \eta}\overline{\eta}T$ $\displaystyle=\frac{\underline{\eta}^{2}+\underline{\eta}\overline{\eta}+ \overline{\eta}^{2}}{3}T,$ $$

where the third inequality comes from $T-1<T$ and $2T-1<2T$. Hence,

$$ $\displaystyle\frac{T}{\sum_{t=0}^{T-1}\eta_{t}}<\frac{2}{\underline{\eta}+ \overline{\eta}}=:H_{1}$ $$

and

$$ $\displaystyle\frac{\sum_{t=0}^{T-1}\eta_{t}^{2}}{\sum_{t=0}^{T-1}\eta_{t}}< \frac{2(\underline{\eta}^{2}+\underline{\eta}\overline{\eta}+\overline{\eta}^{ 2})}{3(\underline{\eta}+\overline{\eta})}=:H_{2}.$ $$

Accordingly, (28) holds. From (43), we have that

$$ $\displaystyle\frac{2}{\underline{\eta}+\overline{\eta}}\leq\frac{\epsilon^{2}} {12\sigma C}\left(\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i }\right)^{-1},$ $\displaystyle(|\alpha|+1)^{2}\frac{2(\underline{\eta}^{2}+\underline{\eta} \overline{\eta}+\overline{\eta}^{2})}{3(\underline{\eta}+\overline{\eta})}\leq \frac{n^{3}\epsilon^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n]}L_{ i})^{2}\}}.$ $$

In particular, when $\underline{\eta}=0$, we have that

$$ $\displaystyle\frac{2}{\overline{\eta}}\leq\frac{\epsilon^{2}}{12\sigma C}\left (\frac{\rho G}{\sqrt{b}}+\frac{3\sigma}{nb}\sum_{i\in[n]}L_{i}\right)^{-1},$ $\displaystyle(|\alpha|+1)^{2}\frac{2\overline{\eta}}{3}\leq\frac{n^{3}\epsilon ^{2}}{6G^{2}\sum_{i\in[n]}L_{i}\{n^{2}+4C(\sum_{i\in[n]}L_{i})^{2}\}}.$ $$

Therefore, Corollary B.1 leads to the assertion in Theorem 2.4.
$\Box$

###### Corollary B.1 ( ϵ italic-ϵ \epsilon italic_ϵ –approximation of GSAM with a constant batch size and decaying learning rate).

## Appendix C Training ResNet-18 on CIFAR100

The code is available at [https://anonymous.4open.science/r/INCREASING-BATCH-SIZE-F09C](https://anonymous.4open.science/r/INCREASING-BATCH-SIZE-F09C).
We set $E=200$, $\eta=\overline{\eta}=0.1$, and $\underline{\eta}=0.001$. First, we trained ResNet18 on the CIFAR100 dataset. The parameters, $\alpha=0.02$ and $\rho=0.05$, used in GSAM were determined by conducting a grid search of $\alpha\in\{0.01,0.02,0.03\}$ and $\rho\in\{0.01,0.02,0.03,0.04,0.05\}$. Figure 5 compares the use of an increasing batch size $[16,32,64,128,256]$ (SGD/SAM/GSAM + increasing_batch) with the use of a constant batch size $128$ (SGD/SAM/GSAM) for a fixed learning rate, $0.1$. SGD/SAM/GSAM + increasing_batch decreased the empirical loss (Figure 5 (Left)) and achieved higher test accuracies compared with SGD/SAM/GSAM (Figure 5 (Right)). Figure 6 compares the use of a cosine-annealing learning rate defined by (15) (SGD/SAM/GSAM + Cosine) with the use of a constant learning rate, $0.1$ (SGD/SAM/GSAM) for a fixed batch size, $128$. SAM/GSAM + Cosine decreased the empirical loss (Figure 6 (Left)) and achieved higher test accuracies compared with SGD/SAM/GSAM (Figure 6 (Right)).

**Table 4: Mean values of the test errors (Test Error) and the worst-case $\ell_{\infty}$ adaptive sharpness (Sharpness) for the parameter obtained by the algorithms at $200$ epochs of training ResNet18 on the CIFAR100 dataset. “(algorithm)+B" refers to “ (algorithm) + increasing batch" in Figure 5, and “(algorithm)+C" refers to " (algorithm) + Cosine" in Figure 6.**
|  | SGD | SAM | GSAM | SGD+B | SAM+B | GSAM+B | SGD+C | SAM+C | GSAM+C |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Test Error | 26.61 | 26.39 | 26.61 | 25.58 | 25.10 | 25.18 | 26.63 | 25.87 | 26.12 |
| Sharpness | 154.27 | 46.23 | 47.55 | 1.33 | 0.94 | 0.90 | 155.88 | 72.70 | 71.86 |

Table 4 summarizes the mean values of the test errors and the worst-case $\ell_{\infty}$ adaptive sharpness defined by (Andriushchenko et al., , (1)) for the parameters $\bm{c}=(1,1,\cdots,1)^{\top}$ and $\rho=0.0002$ of the parameter obtained by the algorithm after $200$ epochs. SAM+B (SAM + increasing batch) had the highest test accuracy, while GSAM+B (GSAM + increasing_batch) had the lowest sharpness, which implies that GSAM+B approximated a flatter local minimum. The table indicates that using an increasing batch size could avoid sharp local minima to which the algorithms using constant and cosine-annealing learning rates converged.

Figure: Figure 5: (Left) Loss function value in training and (Right) accuracy score in testing for the optimizers versus the number of epochs in training ResNet18 on the CIFAR100 dataset. The learning rate of each optimizer was fixed at 0.1. In SGD/SAM/GSAM, the batch size was fixed at 128. In SGD/SAM/GSAM + increasing_batch, the batch size was set at 16 for the first 40 epochs and then it was doubled every 40 epochs afterwards, i.e., to 32 for epochs 41-80, 64 for epochs 81-120, 128 for epochs 120 to 160 and 256 for epochs 160 to 200).
Refer to caption: x9.png

Figure: Figure 6: (Left) Loss function value in training and (Right) accuracy score in testing for the optimizers versus the number of epochs in training ResNet18 on the CIFAR100 dataset. The batch size of each optimizer was fixed at 128. In SGD/SAM/GSAM, the constant learning rate was fixed at 0.1. In SGD/SAM/GSAM + Cosine, the maximum learning rate was 0.1 and the minimum learning rate was 0.001.
Refer to caption: x11.png

Figure: Figure 7: (Left) Loss function value in training and (Right) accuracy score in testing for the batch sizes versus the number of steps in training ResNet18 on the CIFAR100 dataset. The learning rate for each batch size was fixed at 0.1. This is a comparison between the case of a varying batch size [16, 32, 64, 128, 256] (iteration: 242,120) and the case of a fixed batch size of 41 (iteration: 243,800).
Refer to caption: x13.png

## Appendix D The model of ViT-Tiny

|  | Patch size | Embedding<br>Dimension | Heads | Depth | MLP Rate | Params |
| --- | --- | --- | --- | --- | --- | --- |
| ViT-Tiny | 4 | 192 | 12 | 9 | 2 | 2.7M |

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: For major question please respond to Weaknesses section above. On top:

Q1: l 45-47: Is the claim fully correct? For instance referred work (Smith et al., 2018) rather argues for merits of increasing batch size over learning rate annealing, comaring those relatively, not cllaiming that both of each produce flatter otima solutions compared to fixed learning rate. Could authors clarify please?

Q2: How is i.i.d. A3 assumtion (Assumtion 2.1) of losses achived in practice/experiments? Would not be losses dependent due to shared weight updates over the course of training?
soundness: 2
strengths: S1: Well chosen and interesting topic
summary: Paper addressen generalization and convergence properties of Deep learning. In particular, incsiperd by previous works, it takes SAM and applies hypothesis of "increasing batch sizes or decaying learning rates leading to flatter optima" to Aproximated SAM problem Problem 2.1. In a series of Theorems and corroborated by experimetns on ResNet, ViT on CIFAR the claims of the hypothesis are argued to hold.
weaknesses: W1: To me, experiments seem to express a faster convergence for batch size progression $\{8,16,32,64,128\}$ compared to just $128$ batch size training. In other words, the 'early stopping' regularisation effect, which is well-known and widely used. It is clearly demonstrated in Fig.1 when at epoch 40 (first batch increase, I believe) the training and error of small batch models outperform already the large batch size models. Similar in Figure 2, 3, 4 and so on. Thus one can propose that instead of showing the merits of decaying learning rate or increasing batch size, what is reported is the opposite - a faster convergence of larger learning rate or smaller batch size.

I find provided experiments not convincing and I would encourage authors to argue otherwise. Until then it seems to me extremely important authors providing a much stronger evidence for the claims of the paper on carefully chosen experimental setting, before paper could be considered for accepting.

W1a. Labels and text used in Figures render those hardly readable and surely not sufficient for a potential camera ready version. An obvious update is suggested.

Theoretical part:
W2: My concerns on too many approximations and indications and assumptions taken and combined are summarized in line 379: "... Theorem 2.4 indicates that the parameters |α| and ρ in (18) become small and thereby achieve an ε–approximation of GSAM, ..." - The presented theory is an approximation of GSAM that is an approximation to SAM that is an approximation to exact min-max loss. On top is quite hard to verify it as paper ofter refer to Theorems, equations and algorithm form other papers etc. and take many assumtions ... Theo retical argument in the paper seems to be suitable for an 'experimental paper' rather than rigorous theory paper. Then it is even more important to produce good experiments ... see W1.

W2b: Convergence Theorems 2.3, 2.4 claim converegce result of the $expected$ gradient. What does it really say about individial training paths? Can we even conclude anything without bounds on higher moments or likes?


W4: In conclusion, l 537-539: "... The numerical results showed that, compared with SGD/Adam, SAM/GSAM with an increasing batch size and a constant learning rate converges to flatter local minima of the empirical loss functions ..." - I can't follow how experiments showed any convergence to $flatter$ local minima? It was only demonstrated (unconvincingly, see other comments) that test loss after early stopping is lower. Could authors elaborate or adjust?


Overall and despite authors claims, to me paper seems more experimental than theoretical work (see weaknesses above). Yet, experimental results are unconvincing (see comments) for given, rather strong claims of the paper. Extensive update and additional experiments would be required before my recommending the paper for acceptance. I encourage authors to addres raised concernes and I would more than willing to raise my score, however.

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. In Fig 1 and Fig 2., SAM with a fixed batch size or constant learning rate shows no better test accuracy compared with SGD in the same setting. However, in practice, it is expected that SAM outperforms SGD in the same setting. Is there any explanation for this phenomenon?
soundness: 2
strengths: 1. The theoretical analysis looks sound. The setting of increasing batch size is interesting to investigate, which is a good perspective.
2. The experiments are extensive. Seemingly increasing batch size during training indeed avoids sharp minima in practice and leads to a better generalization ability. This message is insightful.
summary: This paper analyzes the convergence of GSAM, a variant of SAM optimizer, with an increasing batch and constant learning rate, also with a constant batch size and decaying learning rate. Numeric experiments partially validate their analyses.
weaknesses: 1. The contribution of this paper is seemingly marginal and incremental. I am not an expert in convergence analysis, but as shown in the table 1, the convergence results of SAM and its variants has been well established before. This paper focuses on a variant of SAM, namely GSAM, and its convergence has been established before under a different setting. The authors are suggested to discuss more on the significance of this problem.
2. The setting of this paper is motivated by the observations that increasing the batch size or decaying the learning rate avoids sharp local minima of the empirical loss, however, the convergence analysis under this setup cannot explain the phenomenon of avoiding sharp local minima. The theoretical insights drawn from its analyses are limited.
3. In Tab. 2, "SAM+C" and "GSAM+C" shows no better flatness compared to vanilla SAM or GSAM. This observation contradicts with previous observation that increasing the batch size or decaying the learning rate avoids sharp local minima of the empirical loss.
4. The authors provide experiments in real-world scenarios, however, some synthetic experiments are also encouraged. Because experiments under synthetic setup could better validate the correctness of the theorems, while real-world experiments are hard to control variables.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: - Seeing decreased flatness (for ResNet) is interesting. Is this result interpreted in the same manner as in the convergence or can authors suggest different ways to understand this result?
soundness: 2
strengths: - The upper and lower bounds for the difference between GSAM and GD seem to be reasonable, achieving that GSAM can behave similarly to GD under the two strategies of this paper's interest.
- The convergence results indicating the existence of t yielding within $\epsilon$-accuracy are interesting.
summary: This paper investigates the ideas of increasing batch size and decaying learning rate for GSAM. The paper mainly provides convergence analyses for both cases showing that GSAM can achieve $\epsilon$-accuracy with these two strategies. The paper also provide numerical evaluations on some image classification tasks to support their theoretical results.
weaknesses: - The theory results focused on showing the $\epsilon$ convergence are a bit nonrealistic, requiring asymptotically increasing batch size to the full batch for example. This creates a gap between theory and practical settings, diminishing the significance of the paper. Also, in the extremely simplified settings with increasing batch size for GD, this results are quite expected.
- "Increasing batch size" used in theory and its implementation for experiments are different.
- The numerical results only cover for CIFAR 100 which is too small and may not generalize, diminishing the empirical validation. ViT results are quite weak and do not support well the theory results.
- The choice of a particular class of SAM (GSAM) is somewhat arbitrary, possibly favoring analyses and potentially limiting the generality of the results; in experiments, it appears that this choice turns to be quite random as well because GSAM is not consistently better than SAM both in terms of either accuracy or flatness.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: 1. Can the author explain more about the main concern stated in P1/030 - P1/032? The concern sounds trivial and has been widely considered in many works. For example:
- [R1]
- [R2]
2. What do the authors mean in P1/35 - P1/37: “which may lead to better generalization than finding sharp minima”? From my limited understanding, the two attached researches are not about finding the sharp minima. Furthermore, finding sharp minima seems not to be the actual contribution and research direction in the topics of improving generalization.
3. In P1/043 - P1/048: The two sentences mentioned by the authors are conflicts. For instance, while the first sentence said that using large batch size falls into sharp local minima, the second sentence said that increasing batch size improves the generalization. What is the information that the authors want to convey?
4. Where is the Approximated SAM problem in the paper [R1]?
5. Can you explain why (3) in the research is equivalent to (2) in [R1]?
6. Can you explain more about the statements about GSAM in P3/158-161: “GSAM using b loss function which are randomly chosen at time t”?
7. What does the author mean by $\xi$ as a random variable in P4/166? What does it operate in Assumption 2.1?
8. The replacement of S and $S_t$ in (6) is trivial and should be truncated or put in the appendix to save space for more important information.
9. In P4/187 - P4/196, after mentioning SAM update, why do we talk about GSAM? What is the relationship between GSAM and SAM in this case? What is the key takeaway?
10. Moreover, despite Section 2.2 being a Mini-batch GSAM algorithm, we do not see much about the key features of GSAM, we only see the SAM algorithm derivations.
11. Is algorithm 1 a contribution to the paper?
12. The upper bound in L794-L795 is too large, I worry that the too large upper-bound may make every equation in the proof become too high. Thus, making (21) to (22) become trivial. As a consequence, Theorem 2.1 becomes trivial. Not that the L value may be very large. 
13. Similarly, the lower bound seems to be loose (L864 - L878). Please discuss this.
14. Can the authors explain the significance of Theorem 2-3 in the convergence analysis?
15. Is $\epsilon$ in L323 also the $\epsilon$ in (2). If so, the convergence rate of GSAM is fixed over the training, isn’t it? A similar question applied to Theorem 2.4.
16. Did the authors conduct empirical studies with different weight initialization? Or can the authors provide any theoretical study to prove the finding observation?
17. Did the authors conduct an ablation test on the combination of methods with different kinds of weight initialization mechanisms?

Reference:
- [R1]: Pierre Foret, Ariel Kleiner, Hossein Mobahi, Behnam Neyshabur, Sharpness-aware Minimization for Efficiently Improving Generalization, ICLR 2021.
- [R2]: Maksym Andriushchenko, Nicolas Flammarion, Towards Understanding Sharpness-Aware Minimization, Towards Understanding Sharpness-Aware Minimization, ICML 2022.
- [R3]: Yong Liu, Siqi Mai, Xiangning Chen, Cho-Jui Hsieh, Yang You, Towards Efficient and Scalable Sharpness-Aware Minimization, CVPR 2022.
soundness: 2
strengths: - This work progressively establishes and justifies its framework
- The results are promising, however, I have some concerns regarding the results as discussed below.
summary: - The authors consider empirically and theoretically the GSAM algorithm with various learning rates, batch sizes, and decay learning rates techniques. 
- The authors compare GSAM in different settings and empirically analyze the convergence rate and the loss landscape when using increasing large batch size and decay algorithms.
weaknesses: - One of the main weaknesses of this paper comes from the significance of the paper. To be more specific, the algorithm seems to be incremental and the contribution lies in fine-tuning GSAM in different settings. Note that this fine-tuning is compulsory for any algorithm to 
- Although the authors evaluate the algorithms on different model architectures. It would be better if the authors evaluated the algorithms on more datasets to prove the effectiveness of the proposed algorithm in various settings.
- The writing seems to be verbose, especially in the introduction, and thus, does not make the reader understand clearly what are the issues of current works, what is the motivation that leads to the paper’s contribution.
- The paper requires more proofreading as some parts of the paper are not easy to follow and lack coherence. For examples:
    - P1/015 - P1/01.
    - P1/030 - P1/033.
    - Perturbed empirical loss and maximum empirical loss needed to be discussed in more detailedly as these terminologies are not widely used in many AI/ML works.
    - P4/187 - P4/196 is verbose, it is hard to understand what information the authors want to convey. The Eq.~(8) is trivial and does not bring a new observation to readers.
    - P4/213 - P5/217.
    - Is Theorem 2.3 also Theorem B.1?
- Despite the paper shows potential, many issues need to be addressed.