Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911767304601600 |
|---|---|
| author | Zhong, Yanjie Li, Jiaqi Lahiri, Soumendra |
| author_facet | Zhong, Yanjie Li, Jiaqi Lahiri, Soumendra |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15890 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems Zhong, Yanjie Li, Jiaqi Lahiri, Soumendra Machine Learning Optimization and Control Statistics Theory 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. |
| title | Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problems |
| topic | Machine Learning Optimization and Control Statistics Theory |
| url | https://arxiv.org/abs/2401.15890 |