{"ID":2851444,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19165","arxiv_id":"2510.19165","title":"Query-Efficient Zeroth-Order Algorithms for Nonconvex Constrained Optimization","abstract":"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.","short_abstract":"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. Ho...","url_abs":"https://arxiv.org/abs/2510.19165","url_pdf":"https://arxiv.org/pdf/2510.19165v2","authors":"[\"Ruiyang Jin\",\"Yuke Zhou\",\"Yujie Tang\",\"Jie Song\",\"Siyang Gao\"]","published":"2025-10-22T01:50:44Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.CC\",\"eess.SY\"]","methods":"[]","has_code":false}