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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/162832 |
| _version_ | 1811678647300390912 |
|---|---|
| author | He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering He, Xiaoyu Zheng, Zibin Chen, Zefeng Zhou, Yuren |
| author_sort | He, Xiaoyu |
| collection | NTU |
| 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. |
| first_indexed | 2024-10-01T02:56:35Z |
| format | Journal Article |
| id | ntu-10356/162832 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:56:35Z |
| publishDate | 2022 |
| record_format | dspace |
| spelling | ntu-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. |
| 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 |
| title | 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_short | Adaptive evolution strategies for stochastic zeroth-order optimization |
| title_sort | adaptive evolution strategies for stochastic zeroth order optimization |
| topic | Engineering::Computer science and engineering Stochastic Processes Optimization |
| url | https://hdl.handle.net/10356/162832 |
| work_keys_str_mv | AT hexiaoyu adaptiveevolutionstrategiesforstochasticzerothorderoptimization AT zhengzibin adaptiveevolutionstrategiesforstochasticzerothorderoptimization AT chenzefeng adaptiveevolutionstrategiesforstochasticzerothorderoptimization AT zhouyuren adaptiveevolutionstrategiesforstochasticzerothorderoptimization |