Multi-Iteration Stochastic Optimizers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917538916466688 |
|---|---|
| author | Carlon, Andre Espath, Luis Lopez, Rafael Tempone, Raul |
| author_facet | Carlon, Andre Espath, Luis Lopez, Rafael Tempone, Raul |
| contents | We introduce Multi-Iteration Stochastic Optimizers, a novel class of first-order stochastic methods that control the relative $L^2$ error using successive control variates along the iteration path. By exploiting correlations between iterates, these control variates reduce the estimator's variance, making an accurate mean gradient estimation computationally affordable. Our approach centers on the Multi-Iteration stochastiC Estimator (MICE), which can be seamlessly coupled with any first-order stochastic optimizer due to its non-intrusive design. The algorithm adaptively selects which iterates to include in its index set. We provide both an error analysis of MICE and a convergence analysis for Multi-Iteration Stochastic Optimizers across various problem classes, including some non-convex cases. In the smooth, strongly convex setting, we demonstrate that to approximate a minimizer within a tolerance $tol$, SGD-MICE requires, on average, $O(tol^{-1})$ stochastic gradient evaluations, compared to $O(tol^{-1}\log(tol^{-1}))$ for SGD with adaptive batch sizes. In numerical experiments, SGD-MICE achieved the desired tolerance with fewer than 3\% of the gradient evaluations required by adaptive batch SGD. Additionally, MICE offers a straightforward stopping criterion based on the gradient norm, validated through consistency tests. To assess its efficiency, we present examples using both SGD-MICE and Adam-MICE, including a stochastic adaptation of the Rosenbrock function and logistic regression on various datasets. Compared to SGD, SAG, SAGA, SVRG, and SARAH, our approach consistently reduces the gradient sampling cost without the need for extensive parameter tuning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_01718 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Multi-Iteration Stochastic Optimizers Carlon, Andre Espath, Luis Lopez, Rafael Tempone, Raul Optimization and Control 62L20, 65K05, 90C15, 65C05 We introduce Multi-Iteration Stochastic Optimizers, a novel class of first-order stochastic methods that control the relative $L^2$ error using successive control variates along the iteration path. By exploiting correlations between iterates, these control variates reduce the estimator's variance, making an accurate mean gradient estimation computationally affordable. Our approach centers on the Multi-Iteration stochastiC Estimator (MICE), which can be seamlessly coupled with any first-order stochastic optimizer due to its non-intrusive design. The algorithm adaptively selects which iterates to include in its index set. We provide both an error analysis of MICE and a convergence analysis for Multi-Iteration Stochastic Optimizers across various problem classes, including some non-convex cases. In the smooth, strongly convex setting, we demonstrate that to approximate a minimizer within a tolerance $tol$, SGD-MICE requires, on average, $O(tol^{-1})$ stochastic gradient evaluations, compared to $O(tol^{-1}\log(tol^{-1}))$ for SGD with adaptive batch sizes. In numerical experiments, SGD-MICE achieved the desired tolerance with fewer than 3\% of the gradient evaluations required by adaptive batch SGD. Additionally, MICE offers a straightforward stopping criterion based on the gradient norm, validated through consistency tests. To assess its efficiency, we present examples using both SGD-MICE and Adam-MICE, including a stochastic adaptation of the Rosenbrock function and logistic regression on various datasets. Compared to SGD, SAG, SAGA, SVRG, and SARAH, our approach consistently reduces the gradient sampling cost without the need for extensive parameter tuning. |
| title | Multi-Iteration Stochastic Optimizers |
| topic | Optimization and Control 62L20, 65K05, 90C15, 65C05 |
| url | https://arxiv.org/abs/2011.01718 |