随机方差缩减估计的统一高概率分析

arXiv cs.LG 论文
stochastic-optimization variance-reduction high-probability-bounds mirror-descent optimization-theory

摘要

本文提出了随机方差缩减估计的统一理论框架，通过新的Freedman不等式推导出高概率界，并改进了约束优化的预言机复杂度。

arXiv:2605.15388v1 公告类型：新 摘要：随机估计量是大规模优化的基础，其中总体量必须从有噪声的预言机观测中推断出来。尽管诸如动量、SPIDER、STORM和PAGE等有影响力的方法已经非常成功，但它们的分析很大程度上是估计量特定且基于期望的，这掩盖了决定可靠性的结构性权衡。在本文中，我们基于一个包含三个组成部分的递归开发了一个用于随机方差缩减估计的统一框架：记忆保持、重置概率以及迭代移动的修正项。该框架恢复了几种经典估计量，激发了新的二阶变体，并产生了估计误差的偏差-方差分解。我们的主要结果是一个统一的高概率界，通过一个新的无维度的向量值Freedman不等式证明，该不等式适用于涉及随机向量鞅和的平滑赋范空间。该结果适用于欧几里得和非欧几里得设置，包括巴拿赫空间中基于镜像下降方法的分析。作为应用，我们获得了使用镜像下降的无约束优化的高概率预言机复杂度，建立了对置信水平的对数依赖。我们还首次通过利用方差缩减估计在这个设置中推导了具有期望约束的随机优化的$\tilde{\mathcal{O}}(\varepsilon^{-3})$预言机复杂度界，改进了现有的$\tilde{\mathcal{O}}(\varepsilon^{-4})$复杂度。
查看原文
查看缓存全文

缓存时间: 2026/05/18 06:40 

# 随机方差缩减估计的统一高概率分析
来源：https://arxiv.org/abs/2605.15388
查看PDF (https://arxiv.org/pdf/2605.15388)

> 摘要：随机估计器是大规模优化的基础，其中总体量必须从噪声预言观测中推断出来。尽管动量法、SPIDER、STORM和PAGE等具有影响力的方法取得了巨大成功，但它们的分析在很大程度上是针对特定估计器且基于期望的，这掩盖了决定可靠性的结构性权衡。在本文中，我们基于一个包含三个组成部分的递归，为随机方差缩减估计开发了一个统一框架：记忆保持、重置概率和迭代移动的修正项。该框架恢复了几种经典估计器，激发了新的二阶变体，并得出了估计误差的偏差-方差分解。我们的主要结果是一个统一的高概率界，通过使用新的无维度向量值Freedman不等式证明，该不等式适用于涉及随机向量鞅和的平滑赋范空间。该结果在欧几里得和非欧几里得设置中均适用，包括巴拿赫空间中基于镜像下降的方法的分析。作为应用，我们获得了使用镜像下降进行无约束优化的高概率预言复杂度，建立了对置信水平的对数依赖。我们还首次推导了具有期望约束的随机优化的$\tilde{\mathcal{O}}(\varepsilon^{-3})$预言复杂度界，通过利用方差缩减估计，改进了现有的$\tilde{\mathcal{O}}(\varepsilon^{-4})$复杂度。

## 提交历史

来自：Zhankun Luo [查看电子邮件 (https://arxiv.org/show-email/e90fa7e4/2605.15388)] **\[v1\]** 2026年5月14日星期四 20:17:10 UTC (169 KB)

相似文章

通过后分层降低排序实验中重尾变现指标的方差

arXiv cs.LG

研究人员提出了一种实用的方差缩减框架，将后分层与 CUPED 相结合，用于处理排序实验中的重尾变现指标。该框架已在 ShareChat 部署，可在减少 45% 流量的情况下达到同等统计置信度。本文已被 SIGIR 2026 收录。