This paper develops a new dimension-free Azuma-Hoeffding type bound on summation norm of a martingale difference sequence with random individual bounds. With this novel result, we provide high-probability bounds for the gradient norm estimator in the proposed algorithm Prob-SARAH, which is a modified version of the StochAstic Recursive grAdient algoritHm (SARAH), a state-of-art variance reduced algorithm that achieves optimal computational complexity in expectation for the finite sum problem. The in-probability complexity by Prob-SARAH matches the best in-expectation result up to logarithmic factors. Empirical experiments demonstrate the superior probabilistic performance of Prob-SARAH on real datasets compared to other popular algorithms.

本研究开发了一种基于Azuma-Hoeffding类型边界的新的无维度维数的martingale差异序列的累加范数，利用这一结果，我们为所提出的Prob-SARAH算法中的梯度范数估计器提供了高概率边界，该算法是StochAstic Recursive grAdient algoritHm（SARAH）的改进版本，它是一种具有最优计算复杂性的方差减小算法，用于有限和问题的期望。Prob-SARAH的概率复杂性与最佳期望结果相匹配，并且经验实验表明Prob-SARAH在真实数据集上相对于其他流行算法具有更优异的概率性能。

非凸有限和问题中随机递归梯度的概率性保证