Adaptive evolution strategies for stochastic zeroth-order optimization
We consider solving a class of unconstrained optimization problems in which only stochastic estimates of the objective functions are available. Existing stochastic optimization methods are mainly extended from gradient-based methods, faced with the challenges of noisy function evaluations, hardness...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2022
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/162832 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-162832 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1628322022-11-10T08:36:46Z Adaptive evolution strategies for stochastic zeroth-order optimization He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren School of Computer Science and Engineering Engineering::Computer science and engineering Stochastic Processes Optimization We consider solving a class of unconstrained optimization problems in which only stochastic estimates of the objective functions are available. Existing stochastic optimization methods are mainly extended from gradient-based methods, faced with the challenges of noisy function evaluations, hardness in choosing step-sizes, and probably ill-conditioned landscapes. This paper presents a stochastic evolution strategy (SES) framework and several adaptation schemes to avoid these challenges. The SES framework combines the ideas of population sampling and minibatch sampling in exploiting the zeroth-order gradient information, efficiently reducing the noise in both data selection and gradient approximation. In addition, it admits approximating the gradients using a non-isotropic Gaussian distribution to better capture the curvature information of the landscapes. Based on this framework, we implement a step-size adaptation rule and two covariance matrix adaptation rules, where the former can automatically tune the step-sizes and the latter are intended to cope with ill-conditioning. For SES with certain fixed step-sizes, we establish a nearly optimal convergence rate over smooth landscapes. We also show that using the adaptive step-sizes allows convergence at a slightly slower rate but without the need to know the smoothness constant. Several numerical experiments on machine learning problems verify the above theoretical results and suggest that the adaptive SES methods show much promise. Agency for Science, Technology and Research (A*STAR) This work was supported in part by the Key-Area Research and Development Program of Guangdong Province under Grant 2020B010165003, in part by the National Natural Science Foundation of China under Grant 62006252, in part by Guangdong Basic and Applied Basic Research Foundation under Grant 2021A1515011840, and in part by A*STAR CyberPhysical Production System (CPPS) - Towards Contextual and Intelligent Response Research Program through the RIE2020 IAF-PP under Grant A19C1a0018. 2022-11-10T08:36:45Z 2022-11-10T08:36:45Z 2022 Journal Article He, X., Zheng, Z., Chen, Z. & Zhou, Y. (2022). Adaptive evolution strategies for stochastic zeroth-order optimization. IEEE Transactions On Emerging Topics in Computational Intelligence, 6(5), 1271-1285. https://dx.doi.org/10.1109/TETCI.2022.3146330 2471-285X https://hdl.handle.net/10356/162832 10.1109/TETCI.2022.3146330 2-s2.0-85125359931 5 6 1271 1285 en A19C1a0018 IEEE Transactions on Emerging Topics in Computational Intelligence © 2022 IEEE. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering Stochastic Processes Optimization |
spellingShingle |
Engineering::Computer science and engineering Stochastic Processes Optimization He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren Adaptive evolution strategies for stochastic zeroth-order optimization |
description |
We consider solving a class of unconstrained optimization problems in which only stochastic estimates of the objective functions are available. Existing stochastic optimization methods are mainly extended from gradient-based methods, faced with the challenges of noisy function evaluations, hardness in choosing step-sizes, and probably ill-conditioned landscapes. This paper presents a stochastic evolution strategy (SES) framework and several adaptation schemes to avoid these challenges. The SES framework combines the ideas of population sampling and minibatch sampling in exploiting the zeroth-order gradient information, efficiently reducing the noise in both data selection and gradient approximation. In addition, it admits approximating the gradients using a non-isotropic Gaussian distribution to better capture the curvature information of the landscapes. Based on this framework, we implement a step-size adaptation rule and two covariance matrix adaptation rules, where the former can automatically tune the step-sizes and the latter are intended to cope with ill-conditioning. For SES with certain fixed step-sizes, we establish a nearly optimal convergence rate over smooth landscapes. We also show that using the adaptive step-sizes allows convergence at a slightly slower rate but without the need to know the smoothness constant. Several numerical experiments on machine learning problems verify the above theoretical results and suggest that the adaptive SES methods show much promise. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren |
format |
Article |
author |
He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren |
author_sort |
He, Xiaoyu |
title |
Adaptive evolution strategies for stochastic zeroth-order optimization |
title_short |
Adaptive evolution strategies for stochastic zeroth-order optimization |
title_full |
Adaptive evolution strategies for stochastic zeroth-order optimization |
title_fullStr |
Adaptive evolution strategies for stochastic zeroth-order optimization |
title_full_unstemmed |
Adaptive evolution strategies for stochastic zeroth-order optimization |
title_sort |
adaptive evolution strategies for stochastic zeroth-order optimization |
publishDate |
2022 |
url |
https://hdl.handle.net/10356/162832 |
_version_ |
1751548488430125056 |