Summary
This manuscript considers the problem of multi-pass stochastic gradient descent with a finite batch-size and strongly convex objective. The key result is to show that when the stationary distribution of the parameters is heavy-tailed in the infinite data (one-pass) limit, then the stationary distribution of the finite batch limit is approximately heavy-tailed, in the sense of having a heavy-tailed component plus a correction depending on the 1-Wasserstein distance between empirical and population data distribution (hence decaying at worst as $\sim n^{-1/2}$). The authors also present numerical experiments that suggest the relevance of this theoretical result to more practical settings.
Strengths
Understanding SGD in its different flavours is an important problem in theoretical machine learning, and results on multi-pass SGD are scarce compared to the one-pass case. Therefore, the contribution is timely and significant. The technical part is sound. Moreover, the paper is well-written and the thread is relatively easy to follow: the motivation and goals are clearly stated and the main result addresses them. Finally, the numerical simulations supporting a broader scope of applicability are nice.
Weaknesses
There are two immediate shortcomings of the work. First, the setting is rather restricted (strongly convex goals). Second, while the authors cite related literature connecting heavy-tails with generalization, this is not explicitly explored in the context of the paper. Overall, one question that remains in the end of the reading is: the stationary distribution of the weights are approximately heavy-tailed, but so what?
Questions
- **[Q1]**: As a reader who is not very familiar with this line of work ([HM21, HSKM22, MM], etc.) I wonder how to conciliate these results to the classical literature [Fabian 1968, Kushner 1981, Pflug 1986] showing asymptotic normality of the stationary distribution under certain conditions. For instance, considering online SGD in the simple least-squares setting. Since the gradient is proportional to the residual $r_{i} = y_{i}-\langle a_{i}, x\rangle$:
$$
x^{k+1} = x^{k} + \gamma r_{k} a_{k}
$$
if the residuals are Gaussian close to the minimum (e.g. $y_{i}=\angle a_{i}, x_{\star}\rangle + z_{i}$ for some $x_{\star}$ and $z_{i}\sim\mathcal{N}(0,\sigma^2)$), won't the stationary distribution be Gaussian? What I am missing?
- **[Q2]**: Theorems 2 and 3 have an explicit dependence on the sample size $n$, but how do they depend on the batch size b?
**Minor comments**
- The following sentences are strong and misleading:
> *Previous works on this problem only considered, up to our knowledge, online (also called single-pass) SGD, which requires an infinite amount of data.*
> *However, all these results rely on exact heavy tails, which, to our current knowledge, can only occur in the online SGD regime where there is access to an infinite sequence of data points.*
While it is true that in one-pass SGD the maximum number of steps is limited by the availability of data, this doesn't necessarily means that it requires an infinite amount of data. Note that the number of steps required generically depend on the task under consideration, and in some practical scenarios where data is abundant only a few epochs are required, see e.g. Table 2.2. of [[Kaplan et al. 2020]](https://arxiv.org/pdf/2005.14165.pdf). The authors even acknowledge this fact in L29-30.
- Please add the details of the plots in the caption in Fig. 2 & 5: the reported tail indices correspond to what simulation?
- L128: You mean $[n] = \{1,\cdots, n\}$?
**References**
[[Fabian 1968]](https://projecteuclid.org/journals/annals-of-mathematical-statistics/volume-39/issue-4/On-Asymptotic-Normality-in-Stochastic-Approximation/10.1214/aoms/1177698258.full) Vaclav Fabian. *On Asymptotic Normality in Stochastic Approximation*. Ann. Math. Statist. 39 (4) 1327 - 1332, August, 1968. https://doi.org/10.1214/aoms/1177698258
[[Kushner 1981]](https://epubs.siam.org/doi/10.1137/0319007) Harold J. Kushner and Hai Huang. *Asymptotic Properties of Stochastic Approximations with Constant Coefficients*. SIAM Journal on Control and Optimization, 19(1), 1981
[[Pflug 1986]](https://epubs.siam.org/doi/10.1137/0324039) Georg Ch. Pflug. *Stochastic minimization with constant step-size: Asymptotic laws*. SIAM Journal on Control and Optimization, 24(4):655–666, 1986
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
I have discussed some of the limitations in the "Weaknesses" part.