New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915043443998720 |
|---|---|
| author | Veprikov, Andrey Bogdanov, Aleksandr Minashkin, Vladislav Beznosikov, Aleksandr |
| author_facet | Veprikov, Andrey Bogdanov, Aleksandr Minashkin, Vladislav Beznosikov, Aleksandr |
| contents | This paper deals with the black-box optimization problem. In this setup, we do not have access to the gradient of the objective function, therefore, we need to estimate it somehow. We propose a new type of approximation JAGUAR, that memorizes information from previous iterations and requires $\mathcal{O}(1)$ oracle calls. We implement this approximation in the Frank-Wolfe and Gradient Descent algorithms and prove the convergence of these methods with different types of zero-order oracle. Our theoretical analysis covers scenarios of non-convex, convex and PL-condition cases. Also in this paper, we consider the stochastic minimization problem on the set $Q$ with noise in the zero-order oracle; this setup is quite unpopular in the literature, but we prove that the JAGUAR approximation is robust not only in deterministic minimization problems, but also in the stochastic case. We perform experiments to compare our gradient estimator with those already known in the literature and confirm the dominance of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_10442 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback Veprikov, Andrey Bogdanov, Aleksandr Minashkin, Vladislav Beznosikov, Aleksandr Optimization and Control This paper deals with the black-box optimization problem. In this setup, we do not have access to the gradient of the objective function, therefore, we need to estimate it somehow. We propose a new type of approximation JAGUAR, that memorizes information from previous iterations and requires $\mathcal{O}(1)$ oracle calls. We implement this approximation in the Frank-Wolfe and Gradient Descent algorithms and prove the convergence of these methods with different types of zero-order oracle. Our theoretical analysis covers scenarios of non-convex, convex and PL-condition cases. Also in this paper, we consider the stochastic minimization problem on the set $Q$ with noise in the zero-order oracle; this setup is quite unpopular in the literature, but we prove that the JAGUAR approximation is robust not only in deterministic minimization problems, but also in the stochastic case. We perform experiments to compare our gradient estimator with those already known in the literature and confirm the dominance of our methods. |
| title | New Aspects of Black Box Conditional Gradient: Variance Reduction and One Point Feedback |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.10442 |