Robust Analysis of Almost Sure Convergence of Zeroth-Order Mirror Descent Algorithm
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_ | 1866913408314507264 |
|---|---|
| author | Paul, Anik Kumar Mahindrakar, Arun D Kalaimani, Rachel K |
| author_facet | Paul, Anik Kumar Mahindrakar, Arun D Kalaimani, Rachel K |
| contents | This letter presents an almost sure convergence of the zeroth-order mirror descent algorithm. The algorithm admits non-smooth convex functions and a biased oracle which only provides noisy function value at any desired point. We approximate the subgradient of the objective function using Nesterov's Gaussian Approximation (NGA) with certain alternations suggested by some practical applications. We prove an almost sure convergence of the iterates' function value to the neighbourhood of optimal function value, which can not be made arbitrarily small, a manifestation of a biased oracle. This letter ends with a concentration inequality, which is a finite time analysis that predicts the likelihood that the function value of the iterates is in the neighbourhood of the optimal value at any finite iteration. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09793 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Robust Analysis of Almost Sure Convergence of Zeroth-Order Mirror Descent Algorithm Paul, Anik Kumar Mahindrakar, Arun D Kalaimani, Rachel K Optimization and Control This letter presents an almost sure convergence of the zeroth-order mirror descent algorithm. The algorithm admits non-smooth convex functions and a biased oracle which only provides noisy function value at any desired point. We approximate the subgradient of the objective function using Nesterov's Gaussian Approximation (NGA) with certain alternations suggested by some practical applications. We prove an almost sure convergence of the iterates' function value to the neighbourhood of optimal function value, which can not be made arbitrarily small, a manifestation of a biased oracle. This letter ends with a concentration inequality, which is a finite time analysis that predicts the likelihood that the function value of the iterates is in the neighbourhood of the optimal value at any finite iteration. |
| title | Robust Analysis of Almost Sure Convergence of Zeroth-Order Mirror Descent Algorithm |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2303.09793 |