On Convergence of Incremental Gradient for Non-Convex Smooth Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914673000972288 |
|---|---|
| author | Koloskova, Anastasia Doikov, Nikita Stich, Sebastian U. Jaggi, Martin |
| author_facet | Koloskova, Anastasia Doikov, Nikita Stich, Sebastian U. Jaggi, Martin |
| contents | In machine learning and neural network optimization, algorithms like incremental gradient, and shuffle SGD are popular due to minimizing the number of cache misses and good practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored.
This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if $n$ is the training set size, we improve $n$ times the optimization term of convergence guarantee to reach accuracy $\varepsilon$ from $O(n / \varepsilon)$ to $O(1 / \varepsilon)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_19259 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Convergence of Incremental Gradient for Non-Convex Smooth Functions Koloskova, Anastasia Doikov, Nikita Stich, Sebastian U. Jaggi, Martin Machine Learning Optimization and Control In machine learning and neural network optimization, algorithms like incremental gradient, and shuffle SGD are popular due to minimizing the number of cache misses and good practical convergence behavior. However, their optimization properties in theory, especially for non-convex smooth functions, remain incompletely explored. This paper delves into the convergence properties of SGD algorithms with arbitrary data ordering, within a broad framework for non-convex smooth functions. Our findings show enhanced convergence guarantees for incremental gradient and single shuffle SGD. Particularly if $n$ is the training set size, we improve $n$ times the optimization term of convergence guarantee to reach accuracy $\varepsilon$ from $O(n / \varepsilon)$ to $O(1 / \varepsilon)$. |
| title | On Convergence of Incremental Gradient for Non-Convex Smooth Functions |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2305.19259 |