On the Almost Sure Convergence of the Stochastic Three Points Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910017022590976 |
|---|---|
| author | Kadi, Taha El Bakkali El Saadi, Omar |
| author_facet | Kadi, Taha El Bakkali El Saadi, Omar |
| contents | The stochastic three points (STP) algorithm is a derivative-free optimization technique designed for unconstrained optimization problems in $\mathbb{R}^d$. In this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation. For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at a rate of $o(1/{T^{\frac{1}{2}-ε}})$ for any $ε\in (0,\frac{1}{2})$, where $T$ is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence in expectation of the final gradient iterate towards zero. For the class of smooth convex functions, we establish that $f(θ^T)$ converges to $\inf_{θ\in \mathbb{R}^d} f(θ)$ almost surely at a rate of $o(1/{T^{1-ε}})$ for any $ε\in (0,1)$, and in expectation at a rate of $O(\frac{d}{T})$ where $d$ is the dimension of the space. Finally, for the class of smooth functions that are strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, $f(θ^T)$ converges to $\inf_{θ\in \mathbb{R}^d} f(θ)$ in expectation at a rate of $O((1-\fracμ{2πdL})^T)$, and almost surely at a rate of $o((1-s\fracμ{2πdL})^T)$ for any $s\in (0,1)$, where $μ$ and $L$ are the strong convexity and smoothness parameters of the function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13886 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Almost Sure Convergence of the Stochastic Three Points Algorithm Kadi, Taha El Bakkali El Saadi, Omar Optimization and Control The stochastic three points (STP) algorithm is a derivative-free optimization technique designed for unconstrained optimization problems in $\mathbb{R}^d$. In this paper, we analyze this algorithm for three classes of functions: smooth functions that may lack convexity, smooth convex functions, and smooth functions that are strongly convex. Our work provides the first almost sure convergence results of the STP algorithm, alongside some convergence results in expectation. For the class of smooth functions, we establish that the best gradient iterate of the STP algorithm converges almost surely to zero at a rate of $o(1/{T^{\frac{1}{2}-ε}})$ for any $ε\in (0,\frac{1}{2})$, where $T$ is the number of iterations. Furthermore, within the same class of functions, we establish both almost sure convergence and convergence in expectation of the final gradient iterate towards zero. For the class of smooth convex functions, we establish that $f(θ^T)$ converges to $\inf_{θ\in \mathbb{R}^d} f(θ)$ almost surely at a rate of $o(1/{T^{1-ε}})$ for any $ε\in (0,1)$, and in expectation at a rate of $O(\frac{d}{T})$ where $d$ is the dimension of the space. Finally, for the class of smooth functions that are strongly convex, we establish that when step sizes are obtained by approximating the directional derivatives of the function, $f(θ^T)$ converges to $\inf_{θ\in \mathbb{R}^d} f(θ)$ in expectation at a rate of $O((1-\fracμ{2πdL})^T)$, and almost surely at a rate of $o((1-s\fracμ{2πdL})^T)$ for any $s\in (0,1)$, where $μ$ and $L$ are the strong convexity and smoothness parameters of the function. |
| title | On the Almost Sure Convergence of the Stochastic Three Points Algorithm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.13886 |