Timescale Separation for Discrete-Time Nonlinear Stochastic Systems

In this letter, we present a timescale separation result for discrete-time stochastic systems. We consider the feedback interconnection of two stochastic subsystems, referred to as fast and slow dynamics, and analyze them by combining timescale separation theory and stochastic LaSalle and Lyapunov theorems. Specifically, we separately focus on two auxiliary dynamics, named the boundary layer system (related to the fast part) and the reduced system (related to the slow part). For each of these auxiliary schemes, we identify a stochastic LaSalle testing condition and guarantee that satisfying both conditions is sufficient to prove almost sure LaSalle-type convergence of the original stochastic interconnection. Finally, we focus on stochastic optimization and exploit this new tool to prove almost sure convergence of the popular Stochastic Averaged Gradient and SAGA algorithms in a general nonconvex framework.