acceptodds
Under review as a conference paper at ICLR 2027

Non-Convex Online SGD with Dependent Data: Last-Iterate Convergence and Temporal Preconditioning

Abstract

Stochastic gradient descent (SGD) is usually analyzed under the assumption that data samples are independent and identically distributed. In practice, however, samples collected over time are often correlated, which can bias stochastic gradients and slow down the training process. We study online SGD for non-convex optimization problems when the data follow a temporally dependent -mixing process. Our analysis explains how the sampling strategy, the rate at which data correlations decay, and the optimization dynamics together determine last-iterate convergence. In particular, we investigate how subsampling and mini-batch sampling methods mitigate the effects of data dependence and how their effectiveness depends on the mixing rate. We also propose a preconditioner that uses online estimates of temporal dependence to adjust SGD updates. We study this approach in controlled settings with known additive noise. The proposed preconditioner complements our convergence analysis of sampling strategies by addressing temporal dependence through the SGD updates.

Primary area:
optimization
Keywords:
stochastic gradient descent, non-convex optimization, temporally dependent data, last-iterate convergence, sampling, temporal preconditioning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_rkgnOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies Online SGD in non-convex settings with non-iid data. In particular it is assumed that the data may display some form of auto-correlation, under the assumption that the dependence of between two observations is shrinking to 0 as the time gap between them tends to infinity. The paper sidesteps the need for dealing with the non-convexity which may be preset by making a 'local gradient domination condition' assumption which they claim is justified in other work. This assumption allows them to focus on establishing convergence in a well behaved region around a local minima. The paper proves results for two separate mechanisms which allow for combatting the auto-correlation type structure. In particular these are 'subsampling' (throwing away most observatoins within some window, allowing for a greater spacing of the observations and hence weakening their dependence) and mini-batching. Separately under each of these schemes the authors show that SGD converges to a a local minima.

The authors additionally propose an algorithm 'Long Run Variance Preconditioned SGD' or 'LRV-SGD'. This algorithm estimates the long run variance of each coordinate in order to precondition them appropriately to account for varying degrees of auto-correlation. They test this algorithm against SGD and Adam via a very narrow set of experiments to show the benefits of their approach at dealing with auto-correlated data.

Critical strengths

The paper is able to establish convergence guarantees of SGD and auto-correlated data with various techniques (subsampling and minibatching), demonstrating how these techniques can be used to ensure convergence.

Critical weaknesses

There are some presentation issues which make the paper harder to read: 'We often use a_t = ...' is not very helpful when none of the many symbols used in the definition have been defined. Assumption 2.1 defines but does not use d_0 and d_1. Grammar issues in definition 2.3 'consider a process... be a process'. Please give a more careful read and try to fix this sort of thing.

Seemingly one of the main contributions is proposing a new algorithm: LRV-SGD. There is however no analysis for this algorithm which is stated to be left as future work. Given that this is a theory paper and the experiment section is very weak relative to empirical papers, introducing a new algorithm without supporting theory is strange and does not seem like it belongs in the paper.

The title explicitly says non-convex, but the assumptions and analysis are such that one initializes near a local optima with a well behaved surrounding region and thus never leaves or encounters any sort of non-convex behaviour. The non-convexity is therefore irrelevant to the analysis, which makes the title feel like a bit of a stretch to me (this is surely a critique that extends broader than this paper). The rationale for these assumptions is borrowed from other works it seems and not well justified in this work.

The contribution of this work relative to the existing literature is not very clear to me. Other works have studied SGD with correlated data, why is this work necessary?

Questions for authors

Did you consider testing your algorithm on any RL problems given that this was one of the stated motivations for auto-correlated data?

What value does this work add to the existing literature, particularly in comparison to existing work studying SGD under auto-correlated data? The paper makes it seem like previous work studies sample complexity and this work does not but opts for different assumptions? Is this correct? Is there something that makes the assumptions here more general or favorable to existing work?

2 comments
AuthorsOpenReview ↗

Response to Reviewer rkgn

We thank the reviewer for the suggestions on positioning, theoretical support, and experiments. Please see:

  • Common Reply 1 for assumption verification and explicit negative curvature inside the analyzed local region.
  • Common Reply 2 for convergence guarantees for Algorithm 1 with its online LRV estimator.

Below we address the remaining questions.

Q1. Why does non-convexity matter near the initialization, and what do dependent observations add?

A1. Local gradient domination rules out stationary points with positive loss in U\mathcal U and permits negative curvature. At the starting point X0=sI2X_0=sI_2 used in Appendix I.4, with s=1−2−8s=1-2^{-8}, the directional second derivative in Appendix I.2.4 equals s2−1<0s^2-1<0. With the specified sampling parameters, the iterates stay in U0\mathcal U_0 and converge to a zero-loss factor with probability at least 95%.

Even from a low-loss start in U0\mathcal U_0, we must control the probability of ever leaving it. In a stationary stream, past observations determine θt\theta_t and can affect the next sample, so E[Gt∣Ft]\mathbb E[G_t\mid\mathcal F_t] can differ from ∇F(θt)\nabla F(\theta_t). Squared bias enters the descent bound at order ηt\eta_t, whereas variance enters at order ηt2\eta_t^2. Lemmas 3.1 and 3.4 control both through the sampling gap or batch size. For consecutive batches of size BB and summable powered mixing coefficients, the respective coefficients are O(B−2)O(B^{-2}) and O(B−1)O(B^{-1}). Section 3 uses these bounds to control exits and the last-iterate loss on confinement, including for 1/2<β<11/2<\beta<1.

An and Lu (2025) and Weissmann et al. (2025) study local convergence with unbiased gradients. For dependent data, Alacaoglu and Lyu (2023) bound the cost of finding an approximately stationary point, and Ma et al. (2022) study sampling for convex objectives. Section 1.2 discusses these comparisons.

Q2. How should the results be compared with sample-complexity analyses?

A2. Our results quantify last-iterate loss and confinement per parameter update. Section 3 now makes the data cost explicit: TT subsampling updates consume a stream of length ∑t<Trt\sum_{t<T}r_t, while consecutive mini-batches use ∑t<TBt\sum_{t<T}B_t observations. This gives the observation budget associated with each sampling schedule.

Q3. Did you consider RL problems?

A3. We added two model-based policy-optimization tasks—trajectory tracking and coupled-tank regulation—to connect the RL motivation with Algorithm 1's observable-noise setting. Known dynamics provide the exact population gradient and additive residual. We measure excess policy cost as the expected cost of the learned policy minus the minimum expected cost within the specified policy class.

Across 20 paired confirmation seeds per task, LRV-SGD reduces the mean late-stage excess policy cost by 16.65% and 26.10%, respectively, relative to marginal-variance scaling. The corresponding total expected cost reductions are 0.105% and 0.263%. Section 5.2 summarizes the results, and Appendix J gives the full protocol and comparisons. Given the time available during the rebuttal period, we did not run a large-scale evaluation on standard RL benchmarks. We plan to evaluate LRV preconditioning on a broader set of these benchmarks in future work.

Q4. Presentation and notation.

A4. Section 2 defines set distance, and Definition 2.3 now distinguishes observation time from update time with corrected grammar. Common Reply 1 explains the roles of d0,d1d_0,d_1 and the three local regions.

Thank you to the authors for their response. They have addressed my concern about non-convexity. They have also added a theoretical result to accompany their proposed algorithm and some RL examples, although these do not quite address the concerns. The non-convex analysis seems to be missing for the new algorithm, which is understandable given it is likely a lot of work to try and cram last minute although this doesn't excuse it from missing. The RL examples are also not very well presented and it sounds like the overall improvement in these examples is <1%? It has also now been brought to my attention from the other reviews which I had previously missed but the demonstration of the theorems via assumption verification on existing problems is quite weak even after the update. Overall I will not change my score, I think the authors still have some work to do to complete this work.

Reviewer_FdnaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the convergence of online SGD for non-convex optimization with dependent data. The authors establish the convergence guarantees for subsampling and mini-batch SGD under certain assumptions. This paper also proposes LRV-SGD, a new optimizer that estimates long-term variance and adjusts learning rates. Experiments on SVHN and synthetic data show that  LRV-SGD outperforms SGD, Adam, and RMSProp in terms of loss.

Critical strengths
  • Convergence of stochastic algorithms under temporally dependent data is an interesting and meaningful problem, as traditional SGD assumes that data is i.i.d., which might not hold in the real applications.

  • The authors considered various sampling strategies, including subsampling and mini-batching sampling, and analyzed under conditions like local PL and general gradient dominance condition.

Critical weaknesses
  • The theoretical study is an extension of the analysis of online SGD to nonconvex cases. But the proposed LRV-SGD algorithm lacks theoretical convergence guarantees. There is a gap between theoretical and application contributions.
  • Definition 2.3 uses Ft\mathcal{F}_t to define the ϕ\phi-mixing coefficient, but Section 3.1 also defines Ft\mathcal{F}_t as SGD update steps rather than the original observation time. This inconsistency may affect the validity of the mixing assumption and subsequent convergence analysis. For example, with a fixed subsampling gap of r=2r=2, Ft\mathcal{F}_t contains ξ\sb2t\xi\sb{2t}. Taking k=tk=t, the supposedly future observation ξ\sbt+k=ξ\sb2t\xi\sb{t+k}=\xi\sb{2t} is already included in Ft\mathcal{F}_t.
Questions for authors
  • LRV-SGD needs to estimate the covariances and assume ztz_t is second-order stationary. What happens if this assumption is violated, especially in practical applications?
  • Can authors clarify which filtration should be used to define the mixing coefficient in Definition 2.3? Which filtration is actually used in the proofs of Lemmas 3.1 and 3.4? Under the clarified definition, do the convergence guarantees remain valid?
1 comment
AuthorsOpenReview ↗

Response to Reviewer Fdna

We thank the reviewer for identifying the time-index inconsistency and requesting an analysis of LRV-SGD. Common Reply 2 presents the new convergence guarantees and the treatment of persistent nonstationarity. Below we clarify the filtrations and their role in the sampling proofs.

Q1. Which filtration defines mixing, and how is the apparent contradiction resolved?

A1. Definition 2.3 now defines mixing through the raw history Hm=σ(ξ1,…,ξm)\mathcal H_m=\sigma(\xi_1,\ldots,\xi_m) and the later observation ξm+k\xi_{m+k}, with both indices measured in observation time. The pre-update Ft\mathcal F_t contains the information available before sampling GtG_t, so θt\theta_t is Ft\mathcal F_t-measurable.

The two sampling rules have the following correspondence:

  • Subsampling: Ft⊆Hst\mathcal F_t\subseteq\mathcal H_{s_t}; the next sample is ξst+rt\xi_{s_t+r_t}, at raw-time lag rtr_t.
  • Mini-batching: Ft=HSt\mathcal F_t=\mathcal H_{S_t}, where St=∑s<tBsS_t=\sum_{s<t}B_s; sample ξSt+j\xi_{S_t+j} is at lag jj.

For a fixed gap rr, the comparison is therefore between Hrt\mathcal H_{rt} and ξr(t+1)\xi_{r(t+1)}. The next observation lies beyond the conditioning history, resolving the example in the review. Section 3 explicitly states the deterministic initialization and sampling schedules used for these relations.

Q2. Which filtration is used in Lemmas 3.1 and 3.4, and what changes in the analysis?

A2. Both lemmas condition on the pre-update Ft\mathcal F_t; Hm\mathcal H_m supplies the raw-time mixing estimates. Thus E[εt∣Ft]=0\mathbb E[\varepsilon_t\mid\mathcal F_t]=0, the subsampling bound uses ϕξ(rt)\phi_\xi(r_t), and the batch bound uses lags 1,…,Bt1,\ldots,B_t together with the within-batch covariance terms.

We have synchronized the definition, sampling descriptions, lemma statements, and Appendix B. The corrected histories preserve the intended lag arguments and the sampling algorithms' asymptotic rate regimes. The lemmas now explicitly connect Assumption 2.5 and mixing to the bias and variance bounds in Assumption 2.4.

Reviewer_XDHVOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies last iterate convergence of stochastic first order gradient methods. That is, they study recursions x_{t+1} = x_{t} - \eta_t G_t where G_t is an estimate of the gradient, and they are particularly interested in function values at the last iterate, F(x_t) as t tends to infinity. They work in a general noise setting, where the the true gradient is the expectation at the stationary distribution of a data generating process, while the gradient estimates are taken from a stochastic process which converges to that distribution in a certain sense. Key assumptions include a Lipschitz gradient assumption and the Polyak-Lojasiewicz (PL) condition, and that the function is initialized sufficiently close to an optimum. The theoretical results establish asymptotic convergence of function values to zero in several models for the gradient estimates (subsampling over time, minibatching) and under variations of the assumptions (the coefficient \beta on the right hand side of the PL inequality)

Critical strengths

Understanding last iterate convergence behavior of SGD is of interest because that is the mode closest to which it is used in practice, as opposed to analysis which consider only a random iterate from the trajectory.

Additionally, relaxed requirements on the noise structure are useful because many real ML scenarios involve generalized/markovian noise structures; the authors mention reinforcement learning as an example.

Furthermore, the results under the PL condition \beta=1/2 stood out as they allow constant step sizes.

Critical weaknesses

The assumptions appear quite strong. It is not clear what if any relevant machine learning problems satisfy the assumptions of the theory. While examples are cited including specially constructed wide neural nets, it should be noted that there are many simple MLP training tasks that fail to satisfy L-smoothness (Lipschitz continuity of the gradient). Without further elaboration on this point, the reviewer has significant concerns about whether these results can be applied to bona fide non-convex optimization problems, which the paper's title and abstract promises. Also, the convergence results require initialization close to an optimum F(x_0) \leq \epsilon which also appears to be a strong assumption. The main text could benefit from a discussion of what values this \epsilon might take.

Additionally, the conclusions are limited as they are asymptotic, and don't guarantee performance at a particular finite number of iterations, which also raises questions about the utility of the results for real world problems.

Questions for authors

The paper would benefit from substantial discussion on whether any functions satisfy all of the conditions of the theorems, as well as to what extent models of interest in machine learning are applicable. Specifically, are there bona fide non-convex ML training scenarios where Assumptions 2.1, 2.4,2.5 are satisfied (simultaneously, of course)? Furthermore, what is the requirement on \epsilon in the assumption F(x_0) \leq \epsilon appearing in the statements of the theorems?

Minor issues:

  • Notation (line 138): what is \sigma? This has not been defined until Assumption 2.4, although it used here, which is a little bit confusing.

  • There deserves to be more discussion after assumption 2.1. What is the intuitive meaning of U_0, U, and U_1?

  • What is dist(A,B) ? This seems to not be defined.

  • Theorem 3.5: There seems to be an extra one word sentence "Assume." in the statement of the theorem.

1 comment
AuthorsOpenReview ↗

Response to Reviewer XDHV

We thank the reviewer for the helpful questions on applicability and quantitative guarantees. Please see Common Reply 1 for the jointly verified non-convex example and the general squared-loss verification of the noise assumptions. Below we address the remaining questions.

Q1. Simple MLP objectives may fail to be globally smooth.

A1. The required smoothness is local, on U1\mathcal U_1. We have corrected the unnecessarily global wording of Lemma 2.2 and made its local argument explicit in Appendix C.1: the buffer condition d1≥C‾/CLd_1\ge\overline C/C_L keeps the gradient-step segment inside U1\mathcal U_1. The unmodified matrix-sensing objective satisfies this local condition. A twice continuously differentiable network loss has bounded Hessian on a compact convex parameter neighborhood, which gives the required local gradient Lipschitz bound.

Q2. What values can the initialization threshold ϵ\epsilon take?

A2. Appendix I.4 gives an explicit relationship between initial loss and success probability: P(Ω∞c)≤F(X0)/l0.\mathbb P(\Omega_\infty^c)\le F(X_0)/l_0. Here Ω∞\Omega_\infty denotes confinement in U0\mathcal U_0.

For the example's specified batch and step sizes, X0∈U0X_0\in\mathcal U_0 and F(X0)≤δl0F(X_0)\le\delta l_0 ensure confinement and convergence with probability at least 1−δ1-\delta. At δ=0.05\delta=0.05, this gives ϵ=1/20480\epsilon=1/20480; Appendix I.4 supplies the constants, calculation, and a non-optimal initialization meeting this threshold.

Q3. Are the guarantees only asymptotic?

A3. Theorem 3.3 provides a finite-iteration localized expectation bound. Appendix I.4 additionally gives E[F(Xt)1Ωt]≤qtF(X0)\mathbb E[F(X_t)\mathbf1_{\Omega_t}]\le q^tF(X_0) for every tt, with an explicit q<1q<1. Together with the exit bound above, this quantifies loss decay and confinement probability. Section 3 now highlights this interpretation and translates update counts into observation counts.

Q4. Notation and presentation issues.

A4. The noise scale σ\sigma is specified in Assumptions 2.4–2.5, and ata_t collects the noise terms in the one-step descent estimate. Section 2 defines set distance;Common Reply 1 explains the local regions and buffer distances. We have also removed the stray “Assume.” in Theorem 3.5.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.