- 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
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.
Response to Reviewer rkgn
We thank the reviewer for the suggestions on positioning, theoretical support, and experiments. Please see:
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 and permits negative curvature. At the starting point X0=sI2 used in Appendix I.4, with s=1−2−8, the directional second derivative in Appendix I.2.4 equals s2−1<0. With the specified sampling parameters, the iterates stay in U0 and converge to a zero-loss factor with probability at least 95%.
Even from a low-loss start in U0, we must control the probability of ever leaving it. In a stationary stream, past observations determine θt and can affect the next sample, so E[Gt∣Ft] can differ from ∇F(θt). Squared bias enters the descent bound at order ηt, whereas variance enters at order ηt2. Lemmas 3.1 and 3.4 control both through the sampling gap or batch size. For consecutive batches of size B and summable powered mixing coefficients, the respective coefficients are O(B−2) and O(B−1). Section 3 uses these bounds to control exits and the last-iterate loss on confinement, including for 1/2<β<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: T subsampling updates consume a stream of length ∑t<Trt, while consecutive mini-batches use ∑t<TBt 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,d1 and the three local regions.