Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914360674222080 |
|---|---|
| author | Jin, Ruiyang Zhou, Yuke Tang, Yujie Song, Jie Gao, Siyang |
| author_facet | Jin, Ruiyang Zhou, Yuke Tang, Yujie Song, Jie Gao, Siyang |
| contents | Zeroth-order optimization (ZO) has been a powerful framework for solving black-box problems, which estimates gradients using zeroth-order data to update variables iteratively. The practical applicability of ZO critically depends on the efficiency of single-step gradient estimation and the overall query complexities. However, existing constrained ZO algorithms cannot achieve efficiency on both simultaneously. In this work, we consider a general constrained optimization model with black-box objective and constraint functions. To solve it, we propose novel algorithms that can achieve the best-known overall query complexity bound of $\mathcal{O}(d/ε^4)$ to find an $ε$-stationary solution ($d$ is the dimension of variables), while reducing the queries for estimating a single-step gradient from $\mathcal{O}(d)$ to $\mathcal{O}(1)$. Specifically, we integrate block gradient estimators with gradient descent ascent, which leads to two algorithms, ZOB-GDA and ZOB-SGDA, respectively. Instead of constructing full gradients, they estimate only partial gradients along random blocks of dimensions, where the adjustable block sizes enable high single-step efficiency without sacrificing convergence guarantees. Our theoretical results establish the finite-sample convergence of the proposed algorithms for nonconvex optimization. Finally, numerical experiments demonstrate the superior performance of our algorithms compared to existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19165 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization Jin, Ruiyang Zhou, Yuke Tang, Yujie Song, Jie Gao, Siyang Optimization and Control Computational Complexity Systems and Control Zeroth-order optimization (ZO) has been a powerful framework for solving black-box problems, which estimates gradients using zeroth-order data to update variables iteratively. The practical applicability of ZO critically depends on the efficiency of single-step gradient estimation and the overall query complexities. However, existing constrained ZO algorithms cannot achieve efficiency on both simultaneously. In this work, we consider a general constrained optimization model with black-box objective and constraint functions. To solve it, we propose novel algorithms that can achieve the best-known overall query complexity bound of $\mathcal{O}(d/ε^4)$ to find an $ε$-stationary solution ($d$ is the dimension of variables), while reducing the queries for estimating a single-step gradient from $\mathcal{O}(d)$ to $\mathcal{O}(1)$. Specifically, we integrate block gradient estimators with gradient descent ascent, which leads to two algorithms, ZOB-GDA and ZOB-SGDA, respectively. Instead of constructing full gradients, they estimate only partial gradients along random blocks of dimensions, where the adjustable block sizes enable high single-step efficiency without sacrificing convergence guarantees. Our theoretical results establish the finite-sample convergence of the proposed algorithms for nonconvex optimization. Finally, numerical experiments demonstrate the superior performance of our algorithms compared to existing methods. |
| title | Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization |
| topic | Optimization and Control Computational Complexity Systems and Control |
| url | https://arxiv.org/abs/2510.19165 |