arXiv:2411.04845math.OCcs.LG2024-11被引 14

提出一种通用随机Halpern迭代,实现线性与二次收敛率。

Asymptotic regularity of a generalised stochastic Halpern scheme

  • 抽象化处理随机性,兼容多种优化算法框架
  • 在内积空间中获得二次收敛率,特殊情形达线性率
  • 适用于强化学习中的Q-learning新方法设计

我们为一种广义的随机Halpern型迭代提供了抽象、通用且高度统一的渐近正则性速率,该迭代在风格上引入了第二个映射,类似于Krasnoselskii-Mann迭代。该迭代具有双重普遍性:第一,完全抽象地处理随机性,不固定采样方式;第二,包含优化文献中多种方案的随机版本,包括Halpern迭代以及Boţ、Csetnek和Meier提出的带Tikhonov正则项的Krasnoselskii-Mann迭代(本文首次研究其随机变体)。针对这些特例,我们获得了线性渐近正则性速率,达到或优于当前最优的随机优化结果;在内积空间中,对一般迭代可得二次速率。最后,讨论了通过小批量采样等方法管理方差的实际策略,说明如何将收敛速率转化为查询复杂度界,并简要展示如何将所提方案应用于强化学习以构造新型Q-learning方法。

原文摘要 · Abstract (English)

We provide abstract, general and highly uniform rates of asymptotic regularity for a generalized stochastic Halpern-style iteration, which incorporates a second mapping in the style of a Krasnoselskii-Mann iteration. This iteration is general in two ways: First, it incorporates stochasticity completely abstractly, rather than fixing a sampling method; second, it includes as special cases stochastic versions of various schemes from the optimization literature, including Halpern's iteration as well as a Krasnoselskii-Mann iteration with Tikhonov regularization terms in the sense of Boţ, Csetnek and Meier (where this stochastic variant of the latter is considered for the first time in this paper). For these specific cases, we obtain linear rates of asymptotic regularity, matching (or improving) the currently best known rates for these iterations in stochastic optimization, and quadratic rates of asymptotic regularity are obtained in the context of inner product spaces for the general iteration. We conclude by discussing how variance can be managed in practice through sampling methods in the style of minibatching, how our convergence rates can be adapted to provide oracle complexity bounds, and by sketching how the schemes presented here can be instantiated in the context of reinforcement learning to yield novel methods for Q-learning.

优化算法随机迭代收敛分析强化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。