Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems

Yanjie Zhong, Jiaqi Li, Soumendra Lahiri
1/29/2024
stat.MLcs.LGmath.OC

No confident code implementation found for this paper.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Cite this paper

@article{zhong2024probabilistic,
  title  = {Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems},
  author = {Yanjie Zhong and Jiaqi Li and Soumendra Lahiri},
  year   = {2024},
  eprint = {2401.15890},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2401.15890v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2401.15890.svg)](https://codeofpaper.com/paper/2401.15890)

Discussion