CS Paper Radar

Continuous-Time Stochastic Contraction Induced by Common White Noise

Sunghyun Koo, Jin Gyu Lee, Hyungbo Shim

eess.SY math.DSmath.OC ·submitted 2026-11-15 21:25 UTC · v1

Abstract

This paper studies contraction properties of stochastic dynamical systems governed by Itô stochastic differential equations. We consider two trajectories driven by a common noise process and measure their separation using Finsler distances, which encompass Riemannian and norm-induced distances. Two notions of contraction are then investigated: $L^p$-contraction, defined by exponential decay of the $L^p$-norm (or the $p$-th moment) of the distance, and almost sure contraction, defined by exponential decay of the distance along almost every sample path. Each notion is characterized by a differential condition that is necessary and sufficient for contraction under mild hypotheses. Relations between contraction notions and an associated incremental input-to-state stability result are also established. As an illustration, we apply the established theory to analyze noise-induced synchronization and quantify its robustness with respect to parameter perturbations.

Closest papers

Nearest neighbours by meaning across the whole index.

Wasserstein Contraction of Stochastic Systems on Manifolds: A Differential Approach

eess.SY math.OC ·2026-10-02 ·Dongjun Wu
similarity 0.62
Abstract

Contraction analysis of dynamical systems turns a global convergence problem into a local one. If the variational system is stable in a uniform sense, then all trajectories of the original system converge toward each other. This paper develops a stochastic analogue for continuous-time stochastic systems, where convergence is measured by Wasserstein distance between probability laws. The key step is to employ mean-square differentiation to construct stochastic variational dynamics. Its uniform $L_2$ stability can then be integrated along curves of initial conditions, yielding Wasserstein contraction of the associated probability laws. This yields criteria formulated in terms of differential Lyapunov functions, and on manifolds, it leads to intrinsic Riemannian formulations. A distinctive feature of the stochastic setting is that the coupling of the noises becomes a design freedom. To exploit this freedom, we introduce an orthogonal differential coupling that extends the framework beyond synchronous coupling. The resulting criterion explicitly exposes how the curvature of the state space enters the contraction mechanism and, in the orthonormal-frame case, recovers the classical Ricci-curvature structure. Finally, we apply the framework to stochastic control on a compact manifold. By introducing stochastic control input, we overcome a deterministic obstruction to global stabilization. That is, a system that cannot be globally stabilized through smooth time-invariant deterministic feedback is rendered globally contracting in $W_2$, and its steady state distribution can be made arbitrarily concentrated around a prescribed target equilibrium.

0.46

Finite-Time Concentration and Convergence Rates for Projected Two-Time-Scale Stochastic Approximation with Markov Noise

cs.LG math.OC ·2026-09-28 ·Rahul Singh, Vivek S. Borkar, Eric Moulines
theory similarity 0.58
Abstract

We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contractive, while the slow iterate is projected onto a compact convex polyhedron. The associated projected ordinary differential equation may have a discontinuous vector field at the boundary, preventing a direct application of standard analyses based on Lipschitz vector fields. Using the Skorokhod map, we establish explicit high-probability bounds for tracking the moving fast equilibrium and the projected slow dynamics. These bounds separate martingale fluctuations, Markov-noise residuals, and the bias due to time-scale separation. A Lipschitz Lyapunov function satisfying a uniform decrease condition over fixed time intervals yields almost-sure convergence, with explicit last-iterate rates when the decrease admits a power lower bound. Under uniform Lyapunov contraction, polynomial step sizes yield joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to $1/3$. Under the additional assumption that the reduced slow update map is a Euclidean contraction, logarithmically separated step sizes improve the joint rate to $O(n^{-1/2}\log n)$ almost surely, including for boundary equilibria. The same rate holds under a distinct geometric condition involving a strictly attracting face of a box and a fast equilibrium that is constant on that face. An actor-critic application achieves an almost-sure value-gap rate of $O(n^{-1}\log n)$ relative to the optimum within the constrained policy class. Further applications include projected TD(0) and projected stochastic gradient descent. We also extend the analysis to projection of the fast recursion under Euclidean contractivity.

0.24

Steady-State Convergence of Stochastic Approximation

cs.LG stat.MLmath.OCmath.PR ·2026-09-14 ·Yixuan Zhang, Qiaomin Xie
similarity 0.53
Abstract · 56 pages, 7 figures

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.

0.45

Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD

cs.LG math.OC ·2026-09-30 ·Junghoon Seo
publishedtheory similarity 0.52
Abstract · To be presented at 2026 NeurIPS workshop on "Optimization for Machine Learning" (OPT2026)

We prove a sharp Gaussian approximation for the invariant law of constant-stepsize SGD with bounded additive noise generated by an exogenous uniformly ergodic Markov chain. For a smooth, strongly convex objective with a Lipschitz Hessian and nondegenerate long-run noise covariance, the centered iterate normalized by the square root of the stepsize is $O(\sqrtα)$-close in 1-Wasserstein distance to its limiting Gaussian. The proof combines blockwise Gaussian comparison with long-run contraction. A four-state example gives a matching lower bound although the one-time noise marginal is symmetric and every nonzero-lag autocovariance vanishes. In this example, an adjacent third-order mixed moment produces the leading correction.

0.51

Geometric Moment Contraction for Stochastic Nesterov Acceleration

cs.LG stat.ML ·2026-09-25 ·Wei Biao Wu
similarity 0.51
Abstract

We study geometric moment contraction (GMC) of the constant-parameter stochastic Nesterov recursion \[ Y_k=Θ_k+β(Θ_k-Θ_{k-1}),\qquad Θ_{k+1}=Y_k-γG(Y_k,X_{k+1}). \] Under mean strong monotonicity and stochastic $L^p$ Lipschitz continuity, an explicit Perron comparison proves synchronous $L^p$ contraction when $βγL_p<(1-β)(1-q_{γ,p})$. This direct criterion includes infinite-variance gradients for $1<p<2$, but its small-step regime requires $β<μ/(μ+L_p)$. A complementary power-Lyapunov argument establishes a positive, generally much smaller, step-size interval for every fixed $β<1$ and every $p>1$, using only a finite $p$th gradient moment. At $p=2$, a simpler explicit certificate gives \[ 0<γ<\frac{2μ(1-β)^2}{L_2^2(1-β+2β^2)}. \] Its quadratic high-momentum scaling is a limitation of the chosen metric, not a sharp stability boundary. We quantify this loss, provide a general mean-only quadratic $S$-procedure, and exploit endpoint Lyapunov inequalities under stronger samplewise sector information. Verified endpoint certificates can be orders of magnitude less conservative than the explicit metric.

0.36

A Distributed Observer with Random Agent Activations over Random Communication Networks

eess.SY ·2026-11-08 ·Yong Joo Do, Jin Gyu Lee
similarity 0.50
Abstract

This paper develops a distributed observer for the forward-Euler discretization of a continuous-time linear time-invariant system under random local operations and random communications. Under uniform stochastic strong connectivity, we establish almost sure exponential convergence of all local state estimates for sufficiently small discretization step sizes. We further examine how the underlying parameters and components affect the admissible range of the discretization step size and the guaranteed convergence rate bound. Unlike related approaches, the proposed method does not require each local unobservable subspace to admit an $A$-invariant complement.

0.26

On the Spectral Dependence of Decentralized Stochastic Gradient Tracking

eess.SY math.OC ·2026-11-05 ·Sulaiman A. Alghunaim, Haoyuan Cai, Ali H. Sayed
theory similarity 0.49
Abstract

We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor $Δ_λ^{-3}$ in the higher-order stochastic term, where $Δ_λ$ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact steady-state mean-square disagreement scales as $α^2σ^2Δ_λ^{-3}$ as the nontrivial eigenvalue approaches $-1$, provided the stepsize $α$ is sufficiently small relative to the gap. Here $σ^2$ is the gradient-noise variance. By unrolling the disagreement recursion, we establish a stochastic bound that averages all nontrivial eigenvalue contributions for diagonalizable mixing matrices, up to an eigenvector conditioning factor. As a real or complex eigenvalue approaches the unit circle away from $1$, its contribution grows as the inverse cube of its distance to the circle; growth can be slower near $1$. For symmetric mixing with gaps $p$ at $1$ and $ν$ at $-1$, the weighted sum $θ_1/p+θ_2/ν^3$ replaces the prior factor $(Δ_λν^2)^{-1}$. For $N$ agents, $Nθ_1$ and $Nθ_2$ count the nonnegative and negative nontrivial eigenvalues, respectively. On a symmetric family, a finite-horizon lower bound for the average iterate matches the worst-case factor $p^{-1}+ν^{-3}$ up to universal constants. Numerical experiments confirm the predicted scaling.

0.22

Stochastic Gradient Descent: A Nonlinear Time Series Perspective

cs.LG stat.MLmath.ST ·2026-10-14 ·Jiaqi Li, Zhipeng Lou, Stefan Richter, Wei Biao Wu
publishedtheoryhighly cited similarity 0.49
Abstract · 87 pages, 8 figures, accepted to JRSSB

This paper investigates the statistical behavior of Stochastic Gradient Descent (SGD) with constant step size under the framework of iterated random functions. Compared to previous studies establishing the convergence of SGD in probability measure, e.g., Wasserstein distance, our approach directly provides the convergence in Euclidean distance by showing the Geometric Moment Contraction (GMC) of SGD. This new convergence can address the non-stationarity of SGD due to fixed initial points and can provide a more refined asymptotic analysis of SGD. Specifically, we prove quenched central limit theorem, invariance principle and $α$-stable convergence for averaged SGD (ASGD) regardless of initialization. Furthermore, we provide a novel perspective to understand the impact of step sizes in SGD by studying its derivative with respect to the step size. The existence of stationary solutions for the derivative processes is shown, enabling the use of interpolation to recover the full-trajectory of SGD. Subsequently, we utilize multiple step sizes and show an enhanced Richardson-Romberg extrapolation with improved bias representation, which brings ASGD estimates closer to the global optimum. Finally, we propose a new online inference method and a bias-reduced variant for the extrapolated ASGD. Empirical confidence intervals are constructed and the coverage probabilities approach the nominal level as $n$ grows.

0.51