标题： 重尾流式统计估计 显示英文标题

标题： Heavy-tailed Streaming Statistical Estimation

摘要： 我们考虑在流式$p$-维样本下进行重尾统计估计的任务。 这也可以视为在重尾分布下的随机优化，同时还具有额外的$O(p)$空间复杂度约束。 我们设计了一种截断的随机梯度下降算法，并在对随机梯度噪声更细致的条件下提供了改进的分析，我们证明了该条件在分析来自一般统计估计问题的随机优化问题时是关键的。 我们的结果不仅保证了期望收敛，还保证了指数集中收敛，并且使用了$O(1)$的批量大小。 我们提供了结果在均值估计和线性回归中的应用。 最后，我们通过针对均值估计和线性回归的合成实验，提供了对结果和算法的经验验证。 显示英文摘要

摘要： We consider the task of heavy-tailed statistical estimation given streaming $p$-dimensional samples. This could also be viewed as stochastic optimization under heavy-tailed distributions, with an additional $O(p)$ space complexity constraint. We design a clipped stochastic gradient descent algorithm and provide an improved analysis, under a more nuanced condition on the noise of the stochastic gradients, which we show is critical when analyzing stochastic optimization problems arising from general statistical estimation problems. Our results guarantee convergence not just in expectation but with exponential concentration, and moreover does so using $O(1)$ batch size. We provide consequences of our results for mean estimation and linear regression. Finally, we provide empirical corroboration of our results and algorithms via synthetic experiments for mean estimation and linear regression.