Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation

As stated: can the authors show that they can realize this n^{3/4} correction term in an experiment, (the setup should be such that I can reproduce it and, the 3/4 fit cleanly on a log-log plot)?

Thank you for your question. We added to the revised version of the paper the simple $1-$dimensional example, which demonstrates the scaling of the second-order term $n^{-3/4}$. We also provide the code at the anonymized github (see the revised version of our paper) in order to simplify reproducibility of our results. We also attach reference here:

https://anonymous.4open.science/r/richardson_romberg_example-3DD4/

The optimality of the 3/4 is asserted multiple places, but it is nowhere displayed. What construction demonstrates the non-improvability of the 3/4?

In our work, for the Polyak-Ruppert averaging algorithm and Richardson-Romberg extrapolation, we establish an estimate of the form $\mathbb{E}{\nu}[|H (\bar{\theta}{n}^{(RR)} - \theta^\star)|^2] \leq \frac{\operatorname{tr}(\Sigma_\varepsilon)}{n} + O\left(\frac{1}{n^{3/2}}\right),$ which demonstrates a clear separation of scales between the leading term and the remainder terms. In the paper ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm by Chris Junchi Li, Wenlong Mou, Martin Wainwright, and Michael Jordan (Proceedings of the Thirty-Fifth Conference on Learning Theory, PMLR 178:909–981, 2022), it is stated on page 3, after formula (3), that the second term in ROOT SGD algorithm is unavoidable under a natural setup. Our numerical experiment also shows that the second order term in our algorithm behaves as $n^{-3/2}$ as well. Following your suggestion, we have removed the optimality statement, replacing it with the best known order at the moment. Plese, see revised pdf.

We thank the reviewer for their valuable feedback and are happy to provide further details in response to the questions they raised.

First, the referee is indeed correct, that the $\lesssim$ symbol is overused in the current submission. However, when considering the leading term of the bounds for the second moment (e.g. in Corollaries 4 and 7), the constant in front of the leading term in our variance bounds is precisely $1$. In case of the $p$-th moment bound the leading term of our bounds is affected by a numerical absolute constant, which comes through the Pinelis version of Rosenthal inequality, see [2], Theorem 4.1. We have revised presentation of our main results in order to reflect this fact.

Second, we would like to bring the referee's attention to the point that our Richardson-Romberg corrected estimator is the corrected version of the Polyak-Ruppert averaged estimator. It is a bit tricky to understand, if RR can help in improving the performance of solely the last iterate of SGD. Indeed, the standard analysis of the last iterate $\theta_n$ in case of constant step size SGD reveals (see e.g. [1]), that \mathbb{E} [\|\|\theta_n - \theta^{\star}\|\|^2] \leq C_0 \gamma + C_1 \exp^{-\gamma n} \|\theta_0 - \theta^{\star}\|\|^2\. Thus, when the number of iterations $n$ is large enough, the fluctuations of $\theta_n$ around $\theta^*$ scales as $\sqrt{\gamma}$, while its bias scales as $\mathcal{O}(\gamma)$. Thus it is hard to expect that applying the RR procedure solely to the last iterate can improve the performance of the algorithm.

References

[1] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 – 1382, 2020. doi: 10.1214/19-AOS1850. URL https://doi.org/10.1214/19-AOS1850.

[2] Iosif Pinelis. Optimum Bounds for the Distributions of Martingales in Banach Spaces. The Annals of Probability, 22(4):1679 – 1706, 1994. doi: 10.1214/aop/1176988477. URL https://doi. org/10.1214/aop/1176988477

We thank the reviewer for their valuable feedback and are happy to provide further details in response to the questions they raised.

The geometric ergodicity of the sequence of updates is a crucial aspect, yet is not defined in the preliminaries. It would also be valuable to add an intuitive explanations for how this fact would be used to derive the risk bounds.

We thank the reviewer for their suggestion. They are, of course, correct in emphasizing that the geometric ergodicity of the update is crucial to our derivation. In fact, the geometric ergodicity of the iterates $\\{\theta_{k}^{(\gamma)}\\}$ is stated in the Proposition 1. For convenience, we have revised its statement accordingly. The geometric ergodicity of this chain (or, equivalently, its underlying Markov kernel) is used in the proof of the Rosenthal inequality, which we state in Proposition 8 of our submission. This inequality enables us to obtain sharp bounds on the terms in the decompositions outlined in Equations (31) and (39). The intuition here is the fact that the covariances between the elements $\theta_{k}^{(\gamma)}$ and $\theta_{k+\ell}^{(\gamma)}$ decays exponentially with the growth of $\ell$, given that $\\{\theta_{k}^{(\gamma)}\\}$ is geometrically ergodic. We included this explanation in the revised version of our paper.

*** In line 480, the beginning of the sentence should be "Directions …” $D_{\last,2}$ used eq. (19) in line 222 is not defined.***

We thank the reviewer for pointing out these two omissions, which we will address in the revision of our manuscript.

The authors should also make explicit the fact that the number of samples, $n$, needs to be known a priori to optimize the step size $\gamma$.

We will add this remark to the revised version of our manuscript, starting from the introduction where we outline our contributions.

Could the authors provide a geometric interpretation for the definition of $c(\theta,\theta’)$, and the ensuing geometric ergodicity of the SGD iterates with respect to $W_c$? Also, are the authors aware of other contexts were such non-standard distance-like functions have been used, which could be cited in the paper?

We can distinguish two behaviors in the distance-like function $c$ depending on $\Vert \theta - \theta' \Vert$. If $\Vert \theta - \theta^\star \Vert \vee \Vert \theta - \theta^\star \Vert \geq \frac{2\sqrt{2} \tau_2 \sqrt{\gamma}}{\mu}$, $c(\theta, \theta')$ behaves essentially as $\Vert \theta - \theta' \Vert \times( \Vert \theta - \theta^\star \Vert \vee \Vert \theta - \theta^\star \Vert)$. However, if $\Vert \theta - \theta' \Vert \leq \frac{2\sqrt{2} \tau_2 \sqrt{\gamma}}{\mu}$, the dominating term in the definition of $c$ is $\frac{2\sqrt{2} \tau_2 \sqrt{\gamma} \Vert \theta - \theta' \Vert}{\mu}$. Note that convergence in $W_2$ has been shown in [1], and initially, we considered relying on convergence in $W_2$ since $c$ is roughly equivalent to the squared norm. However, this led to suboptimal bounds with respect to the step size, which is why we designed the distance-like function $c$. Indeed, the main justification for introducing this distance is that we need to bound terms of the form $\vert Q_{\gamma}^k f(\theta) - \pi_{\gamma}(f) \vert$, for some functions $f$ satisfying $\vert f(\theta) - f(\theta') \vert \leq c(\theta, \theta')$, but not $\vert f(\theta) - f(\theta') \vert \leq \Vert \theta - \theta' \Vert$, such as the function $\psi$ defined in our paper. Therefore, convergence in $W_2$ is not sufficient or leads to suboptimal bounds.

We thank the reviewer for their feedback and we are happy to provide further details on the questions they formulated.

Could the authors provide more discussion on C1? Especially, when can (20) hold?

It is shown in [1, Lemma 13] that $C_1(p)$ (and not only (21)) holds under the assumptions A1, A2, and A3(p) in our papers. The main reason we set $C_1(p)$ as an assumption in our work is that, while this result is valid, we believe the constants appearing in [1, Lemma 13] are likely suboptimal. Specifically, $D_{last,p} = O(p!!)$ when using [1, Lemma 13]. While we consider these constants suboptimal, deriving tighter bounds is challenging and we believe it falls outside the scope of our current submission. We leave this for future work, along with deriving tight high-probability bounds for RR extrapolation (as mentioned in the answer to your second question).

The paper studies the convergence in expectation, is it possible to establish the high-probability convergence result with the same rate for both leading and higher-order terms?

Based on our $L^p$ bounds (Theorem 9 in our main paper), we can establish high-probability bounds using Markov's inequality for some adjusted moment $p$. Typically, this moment is tuned with respect to the desired excess probability in order to obtain the tightest bounds. However, since the constants in our results depend on those in $C_1(p)$, our bounds remain implicit. Furthermore, directly incorporating the bounds from [1, Lemma 13] would lead to overly pessimistic estimates. As previously emphasized, the derivation of tight constants in $C_1(p)$ and tight high-probability bounds are closely related, and for this reason, we have decided to leave these two problems for future work.

One point I found is that when the stochastic problem degenerates into the deterministic problem, the current rate cannot recover the well-known linear convergence result. Could the authors make some statement on this point?

We can actually recover the linear convergence result if we consider the deterministic problem. In this case, the noise $\varepsilon$ is simply zero, and $C_1(p)$ is satisfied for any $p$, with $D_{last,p} = 0$. Therefore, Theorems 3 and 6 provide exponential convergence bounds, which are embedded in the remainder term. Indeed, all other terms are zero: the covariance matrix $\Sigma_{\varepsilon}$ is zero because $\varepsilon$ is zero, and the other terms are proportional to some $D_{last,p}$ for some $p$, and are therefore also zero. We will include this remark in the revised version of the paper and thank the reviewer for their insightful question.

Another thing I am interested in is that the leading term $O(n^{-1/2})$ seems not to be infected by the stepsize (even if without the Richardson-Romberg extrapolation), which seems very different from the existing analysis of SGD for the same problem. Could the authors elaborate more on this fact?

Indeed, some works have derived a leading term of $O(n^{-1/2})$, which depends on the step size. For example, in [1, Corollary 6], which we extend and improve, the authors also provide an expansion for the number of iterations with a fixed step size, applied to the expectation of $(\bar{\theta}_k^{(\gamma)} - \theta^\star)$. However, when closely examining their result, one can see that the leading term takes the form

$n^{-1/2} \int \mathcal{C}(\tilde{\theta}) \, \mathrm{d} \pi_{\gamma}(\tilde{\theta}),$

where $\mathcal{C}(\tilde{\theta})$ is the covariance matrix of $\varepsilon_1(\tilde{\theta})$. In fact, we show in our paper that

$\int \mathcal{C}(\tilde{\theta}) \, \mathrm{d} \pi_{\gamma}(\tilde{\theta}) = \mathcal{C}(\tilde{\theta}) + O(\gamma),$

which leads to a leading term that is not affected by the step size.

References

[1] Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. The Annals of Statistics, 48(3):1348 – 1382, 2020. doi: 10.1214/19-AOS1850. URL https://doi.org/10.1214/19-AOS1850.