{"ID":2856062,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.10945","arxiv_id":"2510.10945","title":"A Unified Zeroth-Order Optimization Framework via Oblivious Randomized Sketching","abstract":"We propose a new framework for analyzing zeroth-order optimization (ZOO) from the perspective of \\emph{oblivious randomized sketching}.In this framework, commonly used gradient estimators in ZOO-such as finite difference (FD) and random finite difference (RFD)-are unified through a general sketch-based formulation. By introducing the concept of oblivious randomized sketching, we show that properly chosen sketch matrices can significantly reduce the high variance of RFD estimates and enable \\emph{high-probability} convergence guarantees of ZOO, which are rarely available in existing RFD analyses. \\noindent We instantiate the framework on convex quadratic objectives and derive a query complexity of $\\tilde{\\mathcal{O}}(\\mathrm{tr}(A)/L \\cdot L/μ\\log\\frac{1}ε)$ to achieve a $ε$-suboptimal solution, where $A$ is the Hessian, $L$ is the largest eigenvalue of $A$, and $μ$ denotes the strong convexity parameter. This complexity can be substantially smaller than the standard query complexity of ${\\cO}(d\\cdot L/μ\\log\\frac{1}ε)$ that is linearly dependent on problem dimensionality, especially when $A$ has rapidly decaying eigenvalues. These advantages naturally extend to more general settings, including strongly convex and Hessian-aware optimization. \\noindent Overall, this work offers a novel sketch-based perspective on ZOO that explains why and when RFD-type methods can achieve \\emph{weakly dimension-independent} convergence in general smooth problems, providing both theoretical foundations and practical implications for ZOO.","short_abstract":"We propose a new framework for analyzing zeroth-order optimization (ZOO) from the perspective of \\emph{oblivious randomized sketching}.In this framework, commonly used gradient estimators in ZOO-such as finite difference (FD) and random finite difference (RFD)-are unified through a general sketch-based formulation. By...","url_abs":"https://arxiv.org/abs/2510.10945","url_pdf":"https://arxiv.org/pdf/2510.10945v1","authors":"[\"Haishan Ye\",\"Xiangyu Chang\",\"Xi Chen\"]","published":"2025-10-13T02:57:01Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}