The Collusion of Memory and Nonlinearity in Stochastic Approximation With Constant Stepsize

We thank the reviewer for recognizing the strengths and contribution of our paper, and for the constructive comments. Below we provide our responses to the comments. In the following, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references, with bibliographic information given at the end of this reply.

Comment: Discussion on the limitation of Assumption 2 (smoothness) and Assumption 3 (strong convexity/monotonicity).

We thank the reviewer for raising this point. We refer the reviewer to the global rebuttal for additional discussion on the smoothness and strong convexity/monotonicity assumptions.

Comment: Discussion on Assumption 5 on noise minorization.

We address this comment in the global rebuttal, as it is an important point.

Comment: paper structure and presentation

We thank the reviewer for their feedback on the paper's structure. We will incorporate the suggestions in the revision to make our paper more succinct.

Comment: practical application and numerical experiments.

We thank the reviewer for the constructive comment. We briefly remark on the practical application of our results. As discussed in Section 4.6, many GLMs satisfy the conditions of our results. Our theory suggests that by running SGD with two stepsizes in parallel and tracking the PR-averaged iterates for each, we can use RR-extrapolation to obtain a reduced-bias estimate. Additionally, we can construct confidence intervals under our CLT guarantee.

We also include numerical experiments in the global rebuttal to demonstrate our results. Specifically, we performed a set of experiments with $L_2$-regularized logistic regression with Markovian data to support our theoretical findings: the presence of bias and its reduction through Richardson-Romberg (RR) extrapolation, as well as the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Employing $L_2$-regularized logistic regression in these experiments also showcases the practical applicability of our results within the scope of generalized linear models (GLMs). We will add the numerical experiments in the revised paper.

Comment: Additional reference.

We thank the reviewer for pointing out the additional related works. All three works examine general (non-linear) SA under Markovian noise with a constant stepsize. Both [b] and our work prove weak convergence, but with different techniques. [b] provides an upper bound for the asymptotic bias, while we offer an equality and closed-form solution for the leading-order bias. [a] presents an upper bound for the PR-averaged iterates and, similar to our results, demonstrates the effectiveness of RR-extrapolation in reducing bias. Besides constant stepsize, [c] also explores diminishing stepsizes and examines the impact of the stepsize decay rate on the asymptotic statistics of PR-averaged SA. We will discuss these related works in our revised literature review.

Comment: Assumption on exogenous Markovian noise.

We acknowledge that our current model of Markovian noise does not account for dependence on $\theta$. In fact, the very recent work (pointed out by the reviewer) [a] considers the Markovian model that incorporates such dependence. We are confident that our work can be extended to adopt a similar modeling approach for the Markovian noise and achieve comparable results.

Comment: Tighter higher order in the bias.

We agree with the reviewer's comment that $O(\alpha^{3/2})$ might not be the tightest next order in the bias characterization, and we believe that $O(\alpha^2)$ can be obtained. Improving the next highest order to $O(\alpha^2)$ requires a more refined characterization of the asymptotic second order $E[(\theta_\infty-\theta^*)^{\otimes2}]$ by following a similar strategy as our current approach. Thus, we leave this refinement out of the scope of the current paper. We conjecture that, with appropriate assumptions on smoothness and noise moment, we can prove refined characterizations of higher orders of $E[(\theta_\infty-\theta^*)^{\otimes p}]$, and subsequently we obtain $E[\theta_\infty]=\theta^*+\sum_{n=1}^m\alpha^nb_n+O(\alpha^{n+1})$.

References:

[a] S. Allmeier and N. Gast. Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise. 2024.

[b] C. K. Lauand and S. Meyn. Bias in Stochastic Approximation Cannot Be Eliminated With Averaging. 2022.

[c] C. K. Lauand and S. Meyn. Revisiting Step-Size Assumptions in Stochastic Approximation. 2024.

We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below. In the following, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references, with bibliographic information given at the end of this reply.

Comment: numerical experiments.

We thank the reviewer for the suggestion. We include numerical experiments in the global rebuttal to demonstrate our results. In particular, we conducted two sets of experiments using $L_2$-regularized logistic regression with Markovian data to verify our theoretical results: the existence of bias and its attenuation via Richardson-Romberg (RR) extrapolation, and the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Using $L_2$-regularized logistic regression in the experiment also demonstrates the practicality of our results in the context of generalized linear models (GLMs). We will add the numerical experiments in the revised paper.

Comment: Clarification of Assumption 3 (boundedness and smoothness of $g$) and Assumption 4 (strong monotonicity) for Theorem 4.6.

We thank the reviewer for raising this point. For discussions on strong convexity and Lipschitz smoothness in proving weak convergence, we refer the reviewer to the global rebuttal. Here, we discuss the role of these two assumptions in bias characterization.

The key technique in bias characterization is Taylor expansion around $\theta^\ast$. The strong monotonicity and Lipschitz smoothness together ensures that $E\|\theta_\infty-\theta^*\|^{2p}$ is of order $O((\alpha\tau)^p)$, which subsequently controls the order of the residual term in Taylor expansion. Moreover, the algebraic manipulation in bias characterization involves the inversion of $\bar{g}'(\theta^*)$ (in the context of SGD, this is equivalent to the Hessian of the objective function). Therefore, the strong monotonicity (convexity) ensures the validity of this inversion.

We believe that we could potentially relax the strong monotonicity assumption to Hurwitz $\bar{g}'(\theta^\ast)$ to ensure the validity of such a matrix inversion. It is unclear what our approach would imply if we only have a positive semi-definite (not full-rank) $\bar{g}'(\theta^*)$. We conjecture that the joint process would still converge, but the bias may exhibit drastically different behaviors that we do not yet fully understand. This conjecture is based on [a], where the SA update is strongly convex and Lipschitz-smooth but non-differentiable at $\theta^*$. [a] shows that the bias admits a very different behavior, with the leading term scaling with $\sqrt{\alpha}$ instead of $\alpha$. Therefore, we currently do not have a clear conjecture for this case without the strong monotonicity assumption at $\theta^*$.

Comment: "Fine-grained" characterization of bias in Theorem 4.6.

We clarify how our bias characterization (4.2) -- (4.5) in Theorem 4.6 differs from the result (8) in [40]. We first remark that characterization in [40] is an upper bound ($\limsup$) on the averaged iterate's bias, not the asymptotic bias of the limiting random variable $E[\theta_\infty]-\theta^*$, since [40] does not prove weak convergence for general SA. Additionally, the result in [40] only shows that the leading term of bias is of $\alpha$-order. In contrast, we provide a closed-form expression in (4.2) -- (4.5) for the leading term of bias, which is computable if the underlying Markovian noise is known or can be approximated. Moreover, we show that the leading term can be decomposed into three components: Markovian noise $b_m$, non-linearity $b_n$, and the compound effect $b_c$, which cannot be implied from [40]. Therefore, our result is a more "fine-grained" characterization.

Comment: Clarification on projection for results in Section 4.3/4.5.

We thank the reviewer for raising this point. The results in Section 4.3 (non-asymptotic result) and 4.5 (CLT), as well as 4.4 (asymptotic bias characterization), are follow-up results to the weak convergence results in Sections 4.1 and 4.2 (weak convergence with or without projection). In obtaining these follow-up results, projection for uniform boundedness of iterates $\theta_t$ is not required. If we have weak convergence without projection, these results subsequently do not require projection. For discussions on removing the projection and minorization noise assumption, please refer to the global rebuttal.

References:

[a] Y. Zhang, D. L. Huo, Y. Chen, Q. Xie. Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA. 2024.

We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below. In what follows, we use [1] [2] etc. to refer to papers cited in our submission, and [a] [b] etc. for new references, with bibliographic information given at the end of this response.

Comment: High probability bounds instead of MSE.

We are grateful to the reviewer for this suggestion. We believe that we can derive high probability bounds by applying the Markov inequality to our Proposition 4.2 (convergence of $E\|\theta_k-\theta^*\|^{2p}$). Our bias characterization allows these bounds to be further tightened. If one would like to prove exponential tail bounds, stronger assumptions on the noise sequence, such as having exponential tails, are necessary as shown in [a] for iid data.

Comment: Discussion on projection and Assumption 5 on minorization.

We address this comment in the global rebuttal, as it is an important point.

Comment: Discussion on explicit dependence on variance of Markov chain.

We thank the reviewer for raising this point. We believe that it is straightforward to extend our results to characterize the dependence on the variance of the Markovian noise in the second moment of Polyak-Ruppert (PR) averaged iterates. We conjecture that by quantifying the variance introduced by the Markovian noise under an additional assumption that $\|g(\theta,x)-g(\theta,y)\|\leq \sigma_d$ for any $x,y\in\mathcal{X}$ and $\theta\in R^d$ (similar assumption in [46]), the explicit dependence of $\sigma$ would be $O(\sigma_d^2\tau_\alpha/(k-k_0))$.

Comment: Discussion on dependence between stepsize and number of iterates.

We thank the reviewer for bringing up this question. Our result allows for independent choices of stepsize $\alpha$ and the number of iterates $k$, provided that $\alpha$ is sufficiently small and $k$ sufficiently large. The first two terms of the second moment bound of the PR averaged iterates do not depend on the number of iterates, which verifies the presence of asymptotic bias with a leading term proportional to the stepsize $\alpha$. The remaining two terms depend on the number of iterates and will vanish as the number of iterates increases $k\to\infty$. The third term corresponds to the asymptotic variance and decays at the rate of $1/k$, and the fourth term corresponds to the optimization error. Our result also allows for optimizing the stepsize $\alpha$ if the number of iterates $k$ is known a priori. Suppose $k$ is fixed and $k_0=k/2$, the optimized $\alpha$ is obtained by balancing the first $\alpha^2$ term and the last $(1-\alpha\mu)^{k_0/2}/(\alpha (k-k_0)^2)$ term. The optimized order is $\alpha = O(k^{-2/3})$, which matches the order in [46], and, to the best of our knowledge, provides the tightest dependence for Markovian linear SA with constant stepsize. We would appreciate it if the reviewer could clarify any remaining questions to ensure our response fully addresses the question on the dependence between stepsize $\alpha$ and the number of iterates $k$ in the PR-averaging bound.

References:

[a] I. Merad and S. Gaïffas. Convergence and concentration properties of constant step-size SGD through Markov chains. 2023.

We thank the reviewer for recognizing our paper’s contribution and strengths, and for the constructive comments. We provide our detailed responses below.

Comment: Numerical experiments.

We thank the reviewer for the suggestion. We conduct a set of experiments, running SGD on $L_2$-regularized logistic regression with Markovian data, to verify our theoretical results: the existence of bias, bias reduction via Richardson-Romberg (RR) extrapolation, and the central limit theorem (CLT) of Polyak-Ruppert (PR) averaged iterates. Using $L_2$-regularized logistic regression also demonstrates the practicality of our results in the context of generalized linear models (GLMs). For a more detailed discussion and the experiment results, please refer to the global rebuttal and the figures in the one-page PDF. We will add the numerical experiments in the revised paper.

Comment: Discussion on Assumption 3 on strong convexity/monotonicity.

We thank the reviewer for raising this point, and we refer the reviewer to the global rebuttal for clarification on the strong convexity/monotonicity assumption.

Comment: the $\otimes$ notation.

We use "$u\otimes v$'' to denote the tensor product of the two vectors $u$ and $v$, and "$u^{\otimes k}$" to denote the $k$-th tensor power of vector $u$. When $k=2$, it is simply the outer product of $M$. We thank the reviewer for pointing this out, and we will add this definition to the paper.

Comment: Discussion on Assumption 4 on the noise sequence.

We would like to further clarify Assumption 4, in which we assume the existence of the $2p$ moment of the noise sequence. We note that it is standard in the SA literature to assume the existence of the $2p$ moment of the noise sequence to control the $2p$ moment of the limiting random variable, as seen in [18,53,60] (cited in our submission). Moreover, we believe that this assumption is necessary; without a finite $2p$ moment for the noise sequence, the limiting random variable $\theta_\infty$ might not have a finite $2p$ moment. For example, consider the simple case $\theta_{t+1}=\theta_t-\alpha(\theta_t-w_t)$, with $\theta_0=0$ and iid noise $w_t$. Note that we have $\theta_T=\alpha\sum_{t=0}^{T-1}(1-\alpha)^{T-t}w_t$. Therefore, it is easy to see that if the noise sequence does not have a finite $2p$ moment, $\theta_\infty$ would not have a finite $2p$ moment.