A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization
Abstract
This paper studies zeroth-order optimization for stochastic convex minimization problems. We propose a parameter-free stochastic zeroth-order method (POEM), which introduces a step-size scheme based on the distance over finite difference and an adaptive smoothing parameter. Our theoretical analysis shows that POEM achieves near-optimal stochastic zeroth-order oracle complexity. Furthermore, numerical experiments demonstrate that POEM outperforms existing zeroth-order methods in practice.
Cite
Text
Ren and Luo. "A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization." Proceedings of the 42nd International Conference on Machine Learning, 2025.Markdown
[Ren and Luo. "A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization." Proceedings of the 42nd International Conference on Machine Learning, 2025.](https://mlanthology.org/icml/2025/ren2025icml-parameterfree/)BibTeX
@inproceedings{ren2025icml-parameterfree,
title = {{A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization}},
author = {Ren, Kunjie and Luo, Luo},
booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
year = {2025},
pages = {51450-51470},
volume = {267},
url = {https://mlanthology.org/icml/2025/ren2025icml-parameterfree/}
}