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

CREATORYinan Shen, Yichen Zhang, Wen-Xin Zhou
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE268 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-01371

Browse the full library · About the Tower of Babel