突破多序列随机逼近理论瓶颈，无需平滑假设即可获高效收敛。
Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications
- 提出无平滑性假设的单时标多序列随机逼近分析方法
- 强单调条件下收敛率达 $\tilde{\mathcal{O}}(K^{-1})$
- 适用于双层优化与分布式学习，理论更宽松、算法更简洁
多序列随机逼近（MSSA）在信号处理与机器学习中广泛应用，但现有理论受限：多时标分析收敛慢，单时标分析依赖严格的不动点光滑性假设。本文建立无需不动点光滑性的更紧致单时标分析。当所有算子均强单调时，MSSA收敛率为 $\tilde{\mathcal{O}}(K^{-1})$，其中 $K$ 为总迭代次数；当仅主算子不满足强单调时，收敛率为 $\mathcal{O}(K^{-\frac{1}{2}})$。这些结果与单序列SA一致。将该理论应用于双层优化与通信高效分布式学习，可放宽假设或简化算法并保证性能，数值实验验证了有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。