arXiv:2610.19652v2 cs.LG

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Yuxuan Xia, Xiao-Tong Yuan

제출 2026-11-04

원문 초록

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as $O(d\epsilon^{-4})$, with both factors separately necessary. We show that their product is unavoidable. We establish an $\Omega(d\epsilon^{-4})$ lower bound for smooth stochastic nonconvex optimization, yielding an $\Omega(d\delta^{-1}\epsilon^{-3})$ bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.19652v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.