SGD with Dependent Data: Optimal Estimation, Regret, and Inference
Yinan Shen, Yichen Zhang, Wen-Xin Zhou · 2026
Read SGD with Dependent Data: Optimal Estimation, Regret, and Inference by Yinan Shen, Yichen Zhang, Wen-Xin Zhou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-01371.txt.
Description
Yinan Shen, Yichen Zhang, and Wen-Xin Zhou study stochastic gradient descent, the workhorse training method of machine learning, when the data arrive as a dependent stream. Most theory assumes each data point is independent. Real streams, from markets to sensors to sequential decisions, break that assumption, and older results suggested a trade-off between estimation accuracy and regret.
The authors show the method adapts on its own to two broad kinds of dependence, including streams that never settle into a fixed pattern. For finite samples, the final iterate achieves optimal estimation error and optimal regret at the same time, so the supposed trade-off can be avoided. Over long runs, the iterates settle into a Gaussian distribution with a small, controlled remainder. A new geometric approximation lets the data range over unbounded values. For sparse online regression, their variant uses minimal storage and still reaches long-term optimality.
Catalog record
| CREATOR | Yinan Shen, Yichen Zhang, Wen-Xin Zhou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 268 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-01371