提出新型双时间尺度算法，证明其收敛速度可达O(1/k^{1/4−ε})
Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis
- 将慢速尺度扩展为非扩张映射，构建随机近似框架
- 证明最后迭代均方残差以O(1/k^{1/4−ε})速率衰减
- 适用于极小极大优化等场景，适合关注收敛性分析的研究者
双时间尺度随机近似算法广泛应用于优化、强化学习和控制等领域。现有有限时间分析主要针对两个时间尺度均为压缩映射的情形。本文将分析范围拓展至慢速尺度为非扩张映射的情况，此时慢速尺度可视为随机近似的不精确Krasnoselskii-Mann迭代。同时研究了一种快尺度含投影步骤的变体，该设计使慢速尺度呈现非扩张性。我们证明，此类算法的最后迭代均方残差误差以速率O(1/k^{1/4−ε})衰减，其中ε>0为任意小正数。此外，还建立了迭代序列几乎必然收敛到不动点集合的结果。通过最小最大优化、线性随机逼近及拉格朗日优化等实例，验证了所提框架的有效性。
原文摘要 · Abstract (English)
Two-time-scale stochastic approximation algorithms are iterative methods used in applications such as optimization, reinforcement learning, and control. Finite-time analysis of these algorithms has primarily focused on fixed point iterations where both time-scales have contractive mappings. In this work, we broaden the scope of such analyses by considering settings where the slower time-scale has a non-expansive mapping. For such algorithms, the slower time-scale can be viewed as a stochastic inexact Krasnoselskii-Mann iteration. We also study a variant where the faster time-scale has a projection step which leads to non-expansiveness in the slower time-scale. We show that the last-iterate mean square residual error for such algorithms decays at a rate $O(1/k^{1/4-ε})$, where $ε>0$ is arbitrarily small. We further establish almost sure convergence of iterates to the set of fixed points. We demonstrate the applicability of our framework by applying our results to minimax optimization, linear stochastic approximation, and Lagrangian optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。