Gradient-free optimization via integration
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_ | 1866914177897988096 |
|---|---|
| author | Andrieu, Christophe Chopin, Nicolas Fincato, Ettore Gerber, Mathieu |
| author_facet | Andrieu, Christophe Chopin, Nicolas Fincato, Ettore Gerber, Mathieu |
| contents | We develop and analyse an approach to optimize functions $l\colon \mathbb{R}^d
\rightarrow \mathbb{R}$ not assumed to be convex, differentiable or even
continuous. The algorithm belongs to the class of model-based search methods. The idea is to fit recursively $l$ to a parametric family of distributions, using a Bayesian update followed by a reprojection back
onto the chosen family. Remarkably, reprojection in our scenario boils down to computing
expectations, which can be simply approximated through Monte Carlo. We
show that when the family of distributions is appropriately chosen this approach can be interpreted as an implicit time-inhomogeneous
gradient descent algorithm on a sequence of smoothed approximations of $l$, providing a route to establishing convergence. We
establish new results for generic inhomogeneous gradient descent algorithms, which we specialise to the model-based search algorithm in the Gaussian scenario. We illustrate the performance of the algorithm on a
challenging classification task in machine learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_00888 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Gradient-free optimization via integration Andrieu, Christophe Chopin, Nicolas Fincato, Ettore Gerber, Mathieu Computation We develop and analyse an approach to optimize functions $l\colon \mathbb{R}^d \rightarrow \mathbb{R}$ not assumed to be convex, differentiable or even continuous. The algorithm belongs to the class of model-based search methods. The idea is to fit recursively $l$ to a parametric family of distributions, using a Bayesian update followed by a reprojection back onto the chosen family. Remarkably, reprojection in our scenario boils down to computing expectations, which can be simply approximated through Monte Carlo. We show that when the family of distributions is appropriately chosen this approach can be interpreted as an implicit time-inhomogeneous gradient descent algorithm on a sequence of smoothed approximations of $l$, providing a route to establishing convergence. We establish new results for generic inhomogeneous gradient descent algorithms, which we specialise to the model-based search algorithm in the Gaussian scenario. We illustrate the performance of the algorithm on a challenging classification task in machine learning. |
| title | Gradient-free optimization via integration |
| topic | Computation |
| url | https://arxiv.org/abs/2408.00888 |