提出在线协方差估计算法,实现非光滑优化中的有效统计推断。
Online Covariance Estimation in Nonsmooth Stochastic Approximation
- 基于分批均值法在线估计协方差矩阵,无需预知样本总量。
- 收敛速度达 $O(\sqrt{d}n^{-1/8+\varepsilon})$,匹配光滑凸情形最优率。
- 适用于非光滑、非单调(可能非凸)场景,支持置信区间与假设检验。
我们研究在非光滑随机逼近(SA)框架下求解变分包含问题。已有研究表明,SA方法的平均迭代序列具有渐近正态性,且其极限协方差矩阵在Hájek-Le Cam局部极小极大意义下为最优。然而,尚未有方法能在非光滑且可能非单调(非凸)的设定中估计该协方差矩阵。本文研究了Zhu等(2023)提出的在线批均值协方差估计算法:通过合理分组SA迭代点,计算批次间的样本协方差以估计极限协方差。该方法无需预先知晓总样本量,可随新数据递归更新。我们证明,只要批大小序列与步长序列适当匹配,该估计器的收敛速率可达 $O(\sqrt{d}n^{-1/8+\varepsilon})$(对任意 $\varepsilon>0$),其中 $d$ 为问题维度,$n$ 为迭代次数(或样本数)。尽管问题非光滑且可能非单调(非凸),该速率仍与仅使用一阶信息的光滑强凸情形下的最优协方差估计率相当。该估计器的一致性支持渐近有效的统计推断,包括构造置信区间和进行假设检验。
原文摘要 · Abstract (English)
We consider applying stochastic approximation (SA) methods to solve nonsmooth variational inclusion problems. Existing studies have shown that the averaged iterates of SA methods exhibit asymptotic normality, with an optimal limiting covariance matrix in the local minimax sense of Hájek and Le Cam. However, no methods have been proposed to estimate this covariance matrix in a nonsmooth and potentially non-monotone (nonconvex) setting. In this paper, we study an online batch-means covariance matrix estimator introduced in Zhu et al.(2023). The estimator groups the SA iterates appropriately and computes the sample covariance among batches as an estimate of the limiting covariance. Its construction does not require prior knowledge of the total sample size, and updates can be performed recursively as new data arrives. We establish that, as long as the batch size sequence is properly specified (depending on the stepsize sequence), the estimator achieves a convergence rate of order $O(\sqrt{d}n^{-1/8+\varepsilon})$ for any $\varepsilon>0$, where $d$ and $n$ denote the problem dimensionality and the number of iterations (or samples) used. Although the problem is nonsmooth and potentially non-monotone (nonconvex), our convergence rate matches the best-known rate for covariance estimation methods using only first-order information in smooth and strongly-convex settings. The consistency of this covariance estimator enables asymptotically valid statistical inference, including constructing confidence intervals and performing hypothesis testing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。