论文标题
与多个耦合序列的随机近似的单时间尺度分析
A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences
论文作者
论文摘要
具有多个耦合序列的随机近似（SA）在机器学习中发现了广泛的应用，例如双光线学习和增强学习（RL）。在本文中，我们研究了具有多个耦合序列的非线性SA的有限时间收敛。与现有的多时间分析不同，我们寻求方案，其中细粒度分析可以为多序列单次尺度SA（STSA）提供严格的性能保证。我们分析的核心是在许多应用中具有多序列SA中固定点的平滑度。当所有序列都具有强烈的单调增量时，我们就建立了$ \ Mathcal {o}（ε^{ - 1}）$的迭代复杂性，以实现$ε$ -Accuracy，从而改善了现有的$ \ Mathcal {o}（ε^{-1.5}）$复杂性，用于两个coupled序列。当除主序列外具有强烈单调增量时，我们就会建立$ \ Mathcal {o}（ε^{ - 2}）$的迭代复杂性。我们的结果的优点在于，将它们应用于随机的二聚体和组成优化问题，以及RL问题会导致放松的假设或对其现有性能保证的改进。
Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). In this paper, we study the finite-time convergence of nonlinear SA with multiple coupled sequences. Different from existing multi-timescale analysis, we seek for scenarios where a fine-grained analysis can provide the tight performance guarantee for multi-sequence single-timescale SA (STSA). At the heart of our analysis is the smoothness property of the fixed points in multi-sequence SA that holds in many applications. When all sequences have strongly monotone increments, we establish the iteration complexity of $\mathcal{O}(ε^{-1})$ to achieve $ε$-accuracy, which improves the existing $\mathcal{O}(ε^{-1.5})$ complexity for two coupled sequences. When all but the main sequence have strongly monotone increments, we establish the iteration complexity of $\mathcal{O}(ε^{-2})$. The merit of our results lies in that applying them to stochastic bilevel and compositional optimization problems, as well as RL problems leads to either relaxed assumptions or improvements over their existing performance guarantees.
