Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization

Sam Reifenstein, Timothee Leleu, Yoshihisa Yamamoto
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:42332-42364, 2024.

Abstract

We propose a novel algorithm that extends the methods of ball smoothing and Gaussian smoothing for noisy derivative-free optimization by accounting for the heterogeneous curvature of the objective function. The algorithm dynamically adapts the shape of the smoothing kernel to approximate the Hessian of the objective function around a local optimum. This approach significantly reduces the error in estimating the gradient from noisy evaluations through sampling. We demonstrate the efficacy of our method through numerical experiments on artificial problems. Additionally, we show improved performance when tuning NP-hard combinatorial optimization solvers compared to existing state-ofthe-art heuristic derivative-free and Bayesian optimization methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-reifenstein24a, title = {Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization}, author = {Reifenstein, Sam and Leleu, Timothee and Yamamoto, Yoshihisa}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {42332--42364}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/reifenstein24a/reifenstein24a.pdf}, url = {https://proceedings.mlr.press/v235/reifenstein24a.html}, abstract = {We propose a novel algorithm that extends the methods of ball smoothing and Gaussian smoothing for noisy derivative-free optimization by accounting for the heterogeneous curvature of the objective function. The algorithm dynamically adapts the shape of the smoothing kernel to approximate the Hessian of the objective function around a local optimum. This approach significantly reduces the error in estimating the gradient from noisy evaluations through sampling. We demonstrate the efficacy of our method through numerical experiments on artificial problems. Additionally, we show improved performance when tuning NP-hard combinatorial optimization solvers compared to existing state-ofthe-art heuristic derivative-free and Bayesian optimization methods.} }
Endnote
%0 Conference Paper %T Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization %A Sam Reifenstein %A Timothee Leleu %A Yoshihisa Yamamoto %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-reifenstein24a %I PMLR %P 42332--42364 %U https://proceedings.mlr.press/v235/reifenstein24a.html %V 235 %X We propose a novel algorithm that extends the methods of ball smoothing and Gaussian smoothing for noisy derivative-free optimization by accounting for the heterogeneous curvature of the objective function. The algorithm dynamically adapts the shape of the smoothing kernel to approximate the Hessian of the objective function around a local optimum. This approach significantly reduces the error in estimating the gradient from noisy evaluations through sampling. We demonstrate the efficacy of our method through numerical experiments on artificial problems. Additionally, we show improved performance when tuning NP-hard combinatorial optimization solvers compared to existing state-ofthe-art heuristic derivative-free and Bayesian optimization methods.
APA
Reifenstein, S., Leleu, T. & Yamamoto, Y.. (2024). Dynamic Anisotropic Smoothing for Noisy Derivative-Free Optimization. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:42332-42364 Available from https://proceedings.mlr.press/v235/reifenstein24a.html.

Related Material