Stochastic Recursive Inclusions under Biased Perturbations: An Input-to-State Stability Perspective

Anik Kumar Paul, Karthik Shenoy, Arun D. Mahindrakar · 2026

Read Stochastic Recursive Inclusions under Biased Perturbations: An Input-to-State Stability Perspective by Anik Kumar Paul, Karthik Shenoy, Arun D. Mahindrakar (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-11462.txt.

Introduction

Anik Kumar Paul, Karthik Shenoy, and Arun Mahindrakar study recursions under biased noise. Their 2026 preprint uses an input-to-state stability lens. Stochastic recursive inclusions show up in many learning schemes. Zeroth-order optimization is one such scheme named here.

Stochastic approximation with iterate-linked noise is another. Distributed learning with adversarial agents is a third case. In all three, bias can stay nonzero and stubborn. The team tracks the long-run behavior under that bias. A differential inclusion serves as the continuous-time limit. Input-to-state stability of that limit guides the analysis. The view tells when biased runs still settle near a target.

Catalog record

CREATORAnik Kumar Paul, Karthik Shenoy, Arun D. Mahindrakar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Recursive Inclusions under Biased Perturbations: An Input-to-State Stability Perspective Anik Kumar Paul, Karthik Shenoy, Arun D. Mahindrakar Abstract This paper investigates the asymptotic behavior of stochastic recursive inclusions in the presence of non-zero, non-diminishing bias, a setting that frequently arises in zeroth-order optimization, stochastic approximation with iterate-dependent noise, and distributed learning with adversarial agents. The analysis is conducted through the lens of input-to-state stability of an associated differential inclusion, which serves as the continuous-time limit of the discrete recursion. We first establish that if the limiting differential inclusion is input-to-state stable and the iterates remain almost surely bounded, then the iterates converge almost surely to the neighborhood of desired equilibrium. We then provide a verifiable sufficient condition for almost sure boundedness by assuming that the underlying operator is single-valued and globally Lipschitz. Finally, we show that several zeroth-order variants of stochastic gradient naturally fit within this framework, and we demonstrate their input-to-state stability under standard conditions. Overall, the results provide a unified theoretical foundation for studying almost sure convergence of biased stochastic approximation schemes through the Input to State stability theory of differential inclusions. I Introduction In this paper, we study the stochastic recursive inclusion \begin{split}x_{n+1}-x_{n}-\alpha_{n}M_{n+1}&\in\alpha_{n}G(x_{n})\\ &\in\alpha_{n}\big(H(x_{n})+\bar{B}(0,\epsilon)\big),\end{split} (1) where \{x_{n}\} denotes the iterates, \{\alpha_{n}\} is a step-size sequence, \{M_{n+1}\}\subset\mathbb{R}^{d} is a martingale difference sequence with respect to standard filtration, H:\mathbb{R}^{d}\rightrightarrows\mathbb{R}^{d} is a set-valued map, and \bar{B}(0,\epsilon) is the closed ball of radius \epsilon centered at the origin. Recursions of the form ( 1 ) appear widely in stochastic approximation, especially in problems where one seeks a point x^{\ast} satisfying 0\in H(x^{\ast}) [ 1 ] . A prominent example is the stochastic subgradient method, where H(x) corresponds to the subdifferential, M_{n+1} models zero-mean noise, and \epsilon represents a non-zero bias. Similar formulations arise across several learning and estimation settings, including Q-learning [ 2 ] , neural network–based system identification [ 3 , 4 , 5 ] , adaptive signal processing [ 6 , 7 ] , and parameter tracking in linear dynamical systems with noisy measurements [ 8 , 9 ] . The asymptotic behavior of ( 1 ) has been studied in [ 10 ] . Under the assumption that the sequence {x_{n}} remains bounded almost surely, and under standard conditions such as the upper semi-continuity of the set-valued map and the Robbins–Monro requirements on the step-size, the asymptotic behavior of the iterates can be inferred by examining the stability properties of the differential inclusion \dot{x}(t)\in H(x(t))+\bar{B}(0,\epsilon). (2) More over in the unbiased case \epsilon=0 , classical results show that if x^{\ast}\in\mathbb{R}^{d} is an asymptotically stable equilibrium of ( 2 ), then x_{n}\to x^{\ast} almost surely [ 1 , 11 ] . However, in many practical settings—particularly in zeroth-order optimization—one does not have direct access to a subgradient at each iteration. Instead, the subgradient must be approximated using noisy function evaluations. Such an approximation is generally biased, and the resulting recursion naturally takes the form of ( 1 ) (see [ 12 ] ). Non-zero bias also arises in several other stochastic approximation problems, especially when the noise across iterations is not independent and depends on the current iterate [ 13 , 14 ] , or in distributed learning scenarios where a subset of agents may behave adversarially, thereby introducing systematic bias [ 15 , 16 ] . The analysis in this paper is carried out from the standpoint of zeroth-order optimization, although the results extend to the broader classes of applications mentioned above. We list the main contributions of this paper below (without loss of generality, we assume that 0\in H(0) ). • Almost Sure Convergence. Our first contribution establishes that if the differential inclusion in ( 2 ) is input-to-state stable and the iterates generated by ( 1 ) remain almost surely bounded, then the sequence x_{n} converges to a neighborhood of 0 almost surely (Theorem 1 ). Earlier analyses of ( 1 )—for example, [ 17 , 18 , 19 , 20 ] —typically rely on the assumption that the bias term vanishes asymptotically. However, a diminishing bias can slow down learning in practice, especially in machine learning implementations (see Chapter 4.4 of [ 21 ] ). Our numerical simulations also reflect this behavior; see Fig 1 and 2 . Moreover, such an assumption can be restrictive in many practical settings. In particular, in stochastic zeroth-order optimization with biased oracles—common in reinforcement learning and statistical learning—one typically encounters a nonzero and non-diminishing bias [ 22 ] . Similarly, in distributed learning systems, persistent bias may arise due to adversarial agents and is often beyond the designer’s control, rendering diminishing-bias assumptions unrealistic in many applications [ 16 ] . • Almost Sure Boundedness. A central assumption in stochastic approximation is the almost sure boundedness of the iterates [ 23 ] , yet verifying this assumption is often nontrivial. In this paper, we provide a sufficient condition ensuring boundedness: when H is single-valued and globally Lipschitz, the iterates generated by ( 1 ) remain almost surely bounded (Theorem 2 ). Existing results establish almost sure boundedness under the assumption of a nonzero but diminishing bias [ 18 , 20 , 19 ] . Boundedness results for gradient descent schemes under global Lipschitz continuity of the gradient have also been reported in [ 24 ] ; however, those works do not account for stochastic martingale difference noise, which limits their applicability in many practical settings. In contrast, this work provides sufficient conditions, together with rigorous justification, under which the recursion ( 1 ) remains almost surely bounded even in the presence of a persistent bias. • Stochastic Zeroth-Order Optimization. We also analyze stochastic gradient descent with a non-diminishing biased gradient oracle, motivated by zeroth-order optimization settings [ 25 ] . We show that the resulting iterates can be written in the general stochastic recursion form ( 1 ). Under standard conditions, including the Polyak–Łojasiewicz (PL) inequality, we establish that the iterates are almost surely bounded and that the associated dynamical systems for these stochastic gradient methods are input-to-state stable. We then extend the analysis to convex, nonsmooth, and constrained optimization problems. In this case, when the subgradient oracle is biased, the iterates again admit the representation ( 1 ), with the set-valued map H(x) given by the Minkowski sum of the subdifferential of the objective function and the truncated normal cone of the constraint set (see ( 23 )). Assuming strong monotonicity of the subdifferential mapping, we show that the corresponding dynamical system is input-to-state stable (Proposition 3 ). Overall, this section highlights the broad applicability of our main results and demonstrates that input-to-state stability provides a unified and powerful framework for analyzing the asymptotic behavior of zeroth-order stochastic gradient methods across smooth, nonsmooth, and constrained settings. II Notation and Math Preliminaries Let \mathbb{I}_{n} denote the n\times n identity matrix. The index set \{1,2,\cdots,N\} will be compactly denoted as [N] . We denote the Euclidean norm as \|x\| for x\in\mathbb{R}^{d} . The \delta -neighborhood of a set C\subset\mathbb{R}^{d} is defined as N_{\delta}(C)=\{x\in\mathbb{R}^{d}\;|\;\inf_{y\in C}\|x-y\|<\delta\} . For X,Y\subseteq\mathbb{R}^{d} , F:X\rightrightarrows Y denotes a set-valued map. The gradient and Hessian of f:\mathbb{R}^{d}\to\mathbb{R} will be represented by \nabla f and \nabla^{2}f respectively. For a convex function f:\mathbb{R}^{d}\to\mathbb{R} the subdifferential of f at x\in\mathrm{dom}(f)

Read the complete text