新算法无需降方差或正则化，直接加速随机根求解问题。
Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization
- 提出双锚机制，避免误差累积导致的加速失效。
- 在期望共单调节/平方非扩张条件下，达到O(ε⁻³)复杂度。
- 适合追求高效稳定、无需调参的随机优化场景。
近年来，确定性根求解问题的加速已得到广泛研究；特别是基于锚点（Halpern型）的方法在算子范数下实现了最优收敛速率。然而，这类方法在随机设置下无法直接推广，因误差累积问题，除非通过增大批次或方差减少技术实现递减方差。本文表明，另一类加速机制——双锚机制，可在不依赖方差降低或双重循环正则化的情况下，直接适用于随机情形。因此，在期望共单调节（cocoercivity）或平方非扩张（square-nonexpansivity）条件下，该算法以迭代无关的固定批次大小，干净地实现O(ε⁻³)复杂度。对于强单调算子，算法达到更优的~O(ε⁻²)复杂度，其ε依赖性几乎逼近理论下界。
原文摘要 · Abstract (English)
Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stochastic setting due to accumulation of errors, unless one enforces diminishing variance via increasing batch sizes or variance reduction techniques. In this work, we show that another class of acceleration, namely the dual-anchor mechanism, extends to the stochastic setting without such error accumulation, in contrast to anchor-based algorithms. Consequently, we cleanly achieve $O(ε^{-3})$ complexity with iteration-independent batch size, without any variance reduction or double-loop recursive regularization, for stochastic root-finding (resp. fixed-point) problems with cocoercivity (resp. square-nonexpansivity) in expectation. For strongly monotone operators, the same algorithm attains a sharper $\widetilde{O} (ε^{-2})$ complexity, nearly matching the lower bound in terms of $ε$-dependence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。