arXiv:2605.15388cs.LG2026-05被引 1

统一分析随机方差缩减估计,提升优化算法的可靠性与效率。

Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation

  • 构建包含记忆保持、重置概率和修正项的统一递推框架。
  • 首次在高概率下实现镜面下降的对数依赖复杂度,突破原有瓶颈。
  • 适用于欧氏与非欧空间,适合研究优化理论或算法设计者。

随机估计器是大规模优化的核心,需从带有噪声的观测中推断总体信息。尽管动量、SPIDER、STORM、PAGE等方法成效显著,但其分析多为特定估计器且基于期望,掩盖了影响可靠性的结构性权衡。本文提出一种基于三要素递推(记忆保留、重置概率、迭代移动修正项)的统一方差缩减估计框架,可还原多个经典估计器,并催生新型二阶变体,实现估计误差的偏倚-方差分解。主结果通过新的无维度向量值Freedman不等式,获得适用于光滑赋范空间(含随机向量鞅和)的统一高概率界,涵盖欧氏与非欧情形,包括巴拿赫空间中的镜面下降分析。应用上,建立了无约束优化中镜面下降的高概率查询复杂度,实现对置信水平的对数依赖;并首次得到带期望约束的随机优化的$ ilde{ ext{O}}(

原文摘要 · Abstract (English)

Stochastic estimators are fundamental to large-scale optimization, where population quantities must be inferred from noisy oracle observations. Although influential methods such as momentum, SPIDER, STORM, and PAGE have been highly successful, their analyses are largely estimator-specific and expectation-based, obscuring the structural tradeoffs that determine reliability. In this paper, we develop a unified framework for stochastic variance-reduced estimation based on a recursion with three components: memory retention, reset probability, and a correction term for iterate movement. This framework recovers several classical estimators, motivates new second-order variants, and yields a bias-variance decomposition of estimation error. Our main result is a unified high-probability bound proved using a new dimension-free vector-valued Freedman inequality, valid for smooth normed spaces involving random sums of vector martingales. The result applies in both Euclidean and non-Euclidean settings, including the analysis of mirror-descent-based methods in Banach spaces. As applications, we obtain high-probability oracle complexities for unconstrained optimization with mirror descent, establishing the logarithmic dependence on the confidence level. We also derive the first $\tilde{\mathcal{O}}(\varepsilon^{-3})$ oracle-complexity bounds for stochastic optimization with expectation constraints, improving upon the existing $\tilde{\mathcal{O}}(\varepsilon^{-4})$ complexity by leveraging variance-reduced estimation for the first time in this setting.

优化算法高概率分析方差缩减镜面下降

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