On the Convergence and Complexity of the Stochastic Central Finite-Difference Based Gradient Estimation Methods
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913644499959808 |
|---|---|
| author | Bollapragada, Raghu Karamanli, Cem |
| author_facet | Bollapragada, Raghu Karamanli, Cem |
| contents | This paper presents an algorithmic framework for solving unconstrained stochastic optimization problems using only stochastic function evaluations. We employ central finite-difference based gradient estimation methods to approximate the gradients and dynamically control the accuracy of these approximations by adjusting the sample sizes used in stochastic realizations. We analyze the theoretical properties of the proposed framework on nonconvex functions. Our analysis yields sublinear convergence results to the neighborhood of the solution, and establishes the optimal worst-case iteration complexity ($\mathcal{O}(ε^{-1})$) and sample complexity ($\mathcal{O}(ε^{-2})$) for each gradient estimation method to achieve an $ε$-accurate solution. Finally, we demonstrate the performance of the proposed framework and the quality of the gradient estimation methods through numerical experiments on nonlinear least squares problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06610 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Convergence and Complexity of the Stochastic Central Finite-Difference Based Gradient Estimation Methods Bollapragada, Raghu Karamanli, Cem Optimization and Control This paper presents an algorithmic framework for solving unconstrained stochastic optimization problems using only stochastic function evaluations. We employ central finite-difference based gradient estimation methods to approximate the gradients and dynamically control the accuracy of these approximations by adjusting the sample sizes used in stochastic realizations. We analyze the theoretical properties of the proposed framework on nonconvex functions. Our analysis yields sublinear convergence results to the neighborhood of the solution, and establishes the optimal worst-case iteration complexity ($\mathcal{O}(ε^{-1})$) and sample complexity ($\mathcal{O}(ε^{-2})$) for each gradient estimation method to achieve an $ε$-accurate solution. Finally, we demonstrate the performance of the proposed framework and the quality of the gradient estimation methods through numerical experiments on nonlinear least squares problems. |
| title | On the Convergence and Complexity of the Stochastic Central Finite-Difference Based Gradient Estimation Methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.06610 |