Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications
This work provides a more robust theoretical foundation for the convergence of MSSA algorithms, benefiting researchers and practitioners in signal processing and machine learning who use these methods for problems like bilevel optimization and distributed learning.
This paper addresses the limitations of existing theoretical understandings for multiple-sequence stochastic approximation (MSSA) by establishing a tighter single-timescale analysis without assuming fixed point smoothness. The authors found that MSSA converges at a rate of \tilde{\mathcal{O}}(K^{-1}) when all operators are strongly monotone, and at \mathcal{O}(K^{-\frac{1}{2}}) when only the main operator is not strongly monotone.
Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings {of} MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Our theoretical findings reveal that, when all involved operators are strongly monotone, MSSA converges at a rate of $\tilde{\mathcal{O}}(K^{-1})$, where $K$ denotes the total number of iterations. In addition, when all involved operators are strongly monotone except for the main one, MSSA converges at a rate of $\mathcal{O}(K^{-\frac{1}{2}})$. These theoretical findings align with those established for single-sequence SA. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees, as validated by numerical experiments.