Stochastic Tracking of Drifting Affine Fixed Points

Sajad Khodadadian

cs.LGOct 19, 2026

Stochastic Tracking of Drifting Affine Fixed Points

Authors: Sajad Khodadadian

Organizations: Grado Department of Industrial and Systems Engineering, Virginia Tech

Abstract

Linear stochastic approximation (SA) is widely used to estimate fixed points from noisy observations, but most finite-time analyses assume that the underlying operator remains fixed. We study linear SA with time-varying affine operators, where the fixed points change over time and the observation noise may be correlated across rounds. For constant-stepsize updates, we establish a bound on the cumulative expected squared distance between the iterates and the corresponding fixed points. The bound accounts for the initial error, observation noise, and changes in the fixed points over time. We also establish lower bounds for scalar Gaussian models, showing that, under specified conditions, a suitably chosen constant stepsize achieves the smallest possible worst-case cumulative error up to constant factors, even compared with estimators that use future observations. These results further quantify the effect of temporal correlation on estimation accuracy. Since choosing an appropriate stepsize generally requires knowledge of the noise level and how much the fixed points change, we develop an adaptive method that uses an additional bounded, unbiased observation of the fixed point to achieve an almost optimal algorithm without needing the knowledge of the noise level and the fixed point variation over time. Finally, we apply our results to value-function estimation using synchronous tabular temporal-difference learning in changing environments, assuming generative-model access and a common invariant distribution.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 1 — Figure 1: The triangular sequence $\psi$ on a single block of length $m=2r+1$ . It starts at $0$ , rises linearly to $1$ , and then decreases linearly back to $0$ .

Panel of Figure 2 — Figure 2: Schematic of the signed triangular construction. The first $Km$ indices form $K=\lfloor T/m\rfloor$ disjoint blocks, each containing $m$ indices. Dashed lines mark the boundaries between blocks; the zero-valued endpoints of adjacent blocks are distinct coordinates. The sequence is zero at the remaining $T-Km$ indices, where $0\leq T-Km<m$ . The figure illustrates a nonzero remainder; this final part is absent when $Km=T$ .

Work	Model and observations	Target variation	Selected guarantee
Hadiji et al. (2026) , Theorem 2.1	Contractive updates with exact operator evaluations	Sum of squared target increments	Cumulative squared tracking error with initialization and target-movement terms
Bastianello et al. (2024) , Propositions 1 and 3	General time-varying contractive operators with possibly biased observation errors	Bound on target movement per round	Expected-distance tracking under second-moment-bounded additive errors; high-probability guarantees under sub-Weibull error assumptions and additional conditions on the random update operators
Cutler et al. (2023) , Theorem 3	Strongly convex optimization with unbiased stochastic gradients	Uniform bound on expected squared minimizer increments	Pointwise expected squared tracking error for $\eta\leq 1/(2L)$ , with initialization, noise, and movement terms; the latter two scale as $\eta\sigma^{2}/m+\Delta^{2}/(m^{2}\eta^{2})$
Baby & Wang (2019) , Section 3.5	Scalar target observations with independent sub-Gaussian noise; known horizon and noise parameter	$\left\lVert D\theta\right\rVert_{2}^{2}\leq W$	Adaptive high-probability squared-error bound $\widetilde{O}(T^{2/3}W^{1/3}\nu^{4/3}+U^{2}+W+\nu^{2})$
This paper, Theorems 3 and 9	Deterministic affine contractions with centered noise satisfying equation 2	Sum of squared fixed-point increments, $W_{T}$	Cumulative mean-square tracking bound; stepsize adaptation using additional bounded, unbiased target observations

Appendix

Table 1: Comparison of selected tracking and estimation guarantees. Numerical constants are suppressed, and

\widetilde{O}

hides logarithmic factors.

Stochastic Approximation

Stochastic approximation studies iterative algorithms that solve optimization, root-finding, and fixed-point problems using noisy data.

See all 76 papers

Sep 14, 2026

Steady-State Convergence of Stochastic Approximation

For constant-stepsize stochastic approximation (SA), the iterates converge in distribution to a stationary law that depends on the stepsize

α.

Steady-state convergence (SSC) concerns the limit of the scaled stationary distribution as

α\downarrow 0.

Existing SSC theory requires i.i.d. or additive noise and global differentiability of the mean operator, and yields suboptimal rates. We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise, covering both locally differentiable and locally nondifferentiable mean operators. A key methodological contribution is a multi-step universality framework that progressively reduces the original stochastic recursion to tractable auxiliary dynamics while preserving its steady-state limit. Under local quadratic linearization at the fixed point, we obtain a Gaussian approximation of the scaled steady state at the optimal rate

O(\sqrtα)

in Wasserstein-2 distance, which further gives finite-time Gaussian approximations for the raw iterates. In the locally nondifferentiable regime, we establish a general SSC result and show that the leading-order asymptotic bias can be of order

\sqrtα

, in contrast to the

α

-order bias in the smooth regime. We apply the theory to Markovian linear SA and asynchronous Q-learning, neither of which is covered by prior results. We further propose a bias-reduction scheme for Q-learning that requires no knowledge of the local smoothness regime, validated by numerical experiments.

Yixuan Zhang, Qiaomin Xie

Department of Industrial & Systems Engineering, University of Wisconsin–Madison

Stochastic Approximation Q-Learning

Ask PDF

Feb 15, 2026

Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds

Constant-stepsize stochastic approximation (SA) is widely used in learning for computational efficiency, yet the distribution of the iterates is typically intractable. Classical asymptotics results give

X_k^{(α)} \approx X^{(α)} \approx x^\star+\sqrtαY

, where

X^{(α)}

is the steady state and

Y

is an appropriate Gaussian limit, by progressively taking the time

k\uparrow\infty

and stepsize

α\downarrow0

. Such limit results, however, do not quantify finite-time, finite-stepsize errors. We develop an explicit pre-limit characterization for SA with i.i.d.\ and Markovian noise. We establish existence and uniqueness of the stationary law, a geometric Wasserstein convergence to stationarity, and almost-sure and

L^3

convergence of the steady state to the root

x^\star

, identifying the scale

\sqrtα

as first-order fluctuation. At this scale, we derive a higher-order quantitative Gaussian approximation with a Wasserstein error, using Stein's method and Poisson equation techniques. We further obtain non-uniform Berry--Esseen-type tail bounds, incorporating both steady-state approximation and finite-time convergence errors. We instantiate the theory for strongly convex smooth SGD, linear SA, and nonlinear contractive SA. Beyond strong convexity, for general convex SGD, we identify a Gibbs limiting law and prove a pre-limit Wasserstein approximation error under stability and Stein-equation hypothesis, which are validated numerically.

Zedong Wang, Yuyang Wang, Ijay Narang +3

H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA · Department of Mathematics, Brown University, Providence, RI 02912, USA · School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA +2

Stochastic Approximation Stochastic Gradient Descent

Ask PDF

May 29, 2026

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations

\bar{F}(x)=x

, where the operator

\bar{F}(\cdot)

can only be accessed through a noisy oracle. We first focus on the standard setting in which

\bar{F}(\cdot)

is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.

Zaiwei Chen, Siva Theja Maguluri

Purdue IE · Georgia Tech IE

Control Lyapunov Functions Lyapunov Stability Stochastic Approximation Temporal-Difference Learning Convergence Analysis

Ask PDF

Abstract

Stochastic Approximation

Explore similar work

Steady-State Convergence of Stochastic Approximation

Constant-Stepsize Stochastic Approximation: Finite-Time Convergence, Gaussian Approximation, and Tail Bounds

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework