betaFeedback

WorksComputer Science

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

Abstract

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to language model fine-tuning. Can deterministic methods achieve the same savings? We study finding an ε\varepsilon-stationary point of an LL-smooth nonconvex function ff on Rd\mathbb{R}^d from exact function values when, on the set where ff is below its initial value f(0)f(0), the Hessian is dominated by a fixed matrix of trace at most LELE. For an initial gap ΔΔ, let T=LΔ/ε2T=LΔ/\varepsilon^2. We show that the Gaussian two-point method used in fine-tuning needs only O(ET)O(ET) calls if it accepts only the steps that decrease ff, and we prove that every randomized method requires at least Ω(ET)Ω(ET) calls when ET≤dET\le d, so this cost is optimal up to constants. In that range, every deterministic method requires at least Ω~(dmin⁡{T,ET})\widetildeΩ(d\min\{T,\sqrt{ET}\}) calls, and adaptive subspace search attains O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}) calls. A deterministic method pays about dd calls for each direction it discovers, and the trace budget allows about ET\sqrt{ET} directions. Determinism therefore multiplies the cost by a factor of order d/(E+ET)d/(E+\sqrt{ET}), up to logarithmic factors. Once EE exceeds TT by a logarithmic factor, deterministic methods require Ω(dT)Ω(dT) calls, just as they do without any trace budget. Our lower bounds hold for C∞C^\infty functions that satisfy the matrix bound on all of Rd\mathbb{R}^d, even when each call also returns projections of the gradient, charged by their rank.

Introduction

In zeroth-order optimization, an algorithm optimizes an objective function with access only to evaluations of its value. Such methods are the tool of choice whenever gradients are unavailable or too costly to compute, as when attacking or explaining a model only through its outputs [13], tuning simulations, hyperparameters, and engineering designs [33], or searching over policies in reinforcement learning [46]; see Liu et al. [37] for a survey. Large language models have brought renewed interest to this setting. Because fine-tuning with forward passes alone requires about the same memory as inference, zeroth-order methods allow a single GPU to tune models that backpropagation cannot fit in memory [38] (Zhang et al. 2024), while seed-based zeroth-order updates reduce communication in federated fine-tuning [44].

For an LL-smooth nonconvex function f:Rd→Rf : \mathbb{R}^{d} \to\mathbb{R} with initial gap f(0)−inf⁡f≤Δf(0)-\inf f \le\Delta, random finite differences find an ε\varepsilon-stationary point, a point x^\hat{x} with ∥∇f(x^)∥≤ε\|\nabla f(\hat{x})\| \le\varepsilon, and the classical analysis bounds their cost by O(dT)O(dT) function values, where T=LΔ/ε2T = L\Delta/\varepsilon^{2} (Nesterov and Spokoiny, 2017; Ghadimi

and Lan (2013). In high dimension, this rate cannot be improved on the full smooth class even with exact function values. Concurrent and independent work of Xia and Yuan [55] proves that randomized algorithms, and hence deterministic ones as well, require at least Ω(dT)\Omega(dT) exact value calls when d≳Tlog⁡Td\gtrsim T\log T. For deterministic algorithms, we prove the explicit lower bound dT/500dT/500 for 1≤T≤d/log⁡(ed)1\le T\le d/\log(ed), which matches coordinate finite differences up to constants (Theorem 3.4). In high-dimensional tasks such as language model fine-tuning, however, randomized zeroth-order methods succeed at far lower query cost. Effective rank analyses attribute this speedup to a low curvature trace ([38, 57]), consistent with the low intrinsic dimension of fine-tuning ([35, 1]). Does this saving come from problem structure alone, or does it require randomness?

This question also applies to practical implementations of randomized methods. Memory-efficient zeroth-order fine-tuning regenerates each perturbation from a stored random seed ([38]). Once its seeds are fixed in advance, such a procedure is a deterministic algorithm, so deterministic lower bounds apply to it on functions chosen after the seeds are set; we defeat such a fixed-seed run experimentally in § 6. Classical derivative-free optimizers, including coordinate and pattern search ([24]), the Nelder–Mead method ([39]), and Powell’s interpolation methods ([15, 33]), are deterministic as well. This raises the question of whether a deterministic algorithm can learn the active subspace of curvature along its trajectory and search within it, paying only for the curvature trace rather than for the ambient dimension dd. Whereas Jordan et al. [28] and Kornowski [31] establish a price of determinism for nonsmooth Goldstein stationarity (§ 5), we study smooth first-order stationarity in high dimension and show that randomness is essential to fully exploit a low curvature trace.

To compare deterministic and randomized methods on the same functions, we consider an LL-smooth objective ff with initial gap Δ\Delta whose positive curvature has bounded trace on the initial sublevel set {x∈Rd:f(x)<f(0)}\{x \in\mathbb{R}^{d}: f(x) < f(0)\}, where descent methods operate. For almost every xx with f(x)<f(0)f(x) < f(0), we assume that the Hessian ∇2f(x)\nabla^{2}f(x) is dominated by one fixed positive semidefinite matrix of operator norm at most LL and trace at most LELE. Because EE bounds only the trace of this dominating matrix, positive curvature may spread across many directions. Since the matrix bounds the Hessian only from above, negative curvature is not charged at all. § 2.1 compares this class with prior curvature assumptions. Malladi et al. [38] assume such a dominating matrix near each iterate of a trajectory and derive an effective-rank upper bound for zeroth-order SGD, whereas our condition is fixed on the initial sublevel set before the run begins.

Suppose 1≤E≤d1 \le E \le d, T≥1T \ge1, and ET≤dET \le d, and let NdetN_{\mathrm{det}} and NrandN_{\mathrm{rand}} denote the deterministic and randomized worst-case query complexities on this class (Section 2). Randomized methods pay only for the curvature trace. We show that the Gaussian two-point method attains O(ET)O(ET) calls when it accepts only steps that decrease ff, and that every randomized method requires at least Ω(ET)\Omega(ET) calls. A deterministic method, by contrast, pays roughly dd calls for each active direction it discovers, while the trace budget allows at most O(ET)O(\sqrt{ET}) such directions. We show that adaptive subspace search attains O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}) calls, while our hidden-chain construction forces Ω~(min⁡{T,ET})\widetilde{\Omega}(\min\{T,\sqrt{ET}\}) directions. We prove (Theorems 3.1 and 3.2)

Ω~(dmin⁡{T,ET})≤Ndet≤O(dmin⁡{T,ET}),Ω(ET)≤Nrand≤O(ET),\begin{aligned} \widetilde{\Omega}(d\min\{T,\sqrt{ET}\}) &\le N_{\mathrm{det}} \le O(d\min\{T,\sqrt{ET}\}),\\ \Omega(ET) &\le N_{\mathrm{rand}} \le O(ET), \end{aligned}

where Ω~\widetilde{\Omega} hides only a factor log⁡(e+T)\sqrt{\log(e+T)}; Section 3 states the bounds with this factor written out. For ET≤dET \le d, the price of determinism Ndet/NrandN_{\mathrm{det}}/N_{\mathrm{rand}} is therefore bounded below by Ω~(d/(E+ET))\widetilde{\Omega}(d/(E+\sqrt{ET})) and above by O(d/(E+ET))O(d/(E+\sqrt{ET})), growing linearly with dd when EE and TT are fixed. Once E≥Tlog⁡(e+T)E \ge T\log(e+T) within this range, so that Tlog⁡(e+T)≤E≤d/TT\log(e+T) \le E \le d/T, deterministic methods require at least Ω~(dT)\widetilde{\Omega}(dT) calls, just as without a trace budget. Our upper and lower bounds then match up to constant factors for both algorithm classes, and their costs differ by a factor of order d/Ed/E (Corollary 3.3). Table 1 compares these bounds with the closest prior ones.

SettingAlg.BoundsUpper bound attained byMatched
Low curvature trace: ∇2f⪯H\nabla^{2}f \preceq H with tr⁡H≤LE\operatorname{tr} H \le LE below f(0)f(0) (this work)
ET≤dET \le d, Theorem 3.1RΩ(ET)\Omega(ET), O(ET)O(ET)Gaussian two-point with an acceptance testa^{a}yes
ET≤dET \le d, Theorem 3.2DΩ~(dmin⁡{T,ET})\widetilde{\Omega}(d\min\{T,\sqrt{ET}\}), O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\})restarted subspace search, adapting Cosson et al. [16]up to log⁡b\sqrt{\log}^{b}
Tlog⁡(e+T)≤E≤d/TT\log(e+T)\le E\le d/T, Corollary 3.3D vs RD: Ω(dT)\Omega(dT); R: Ω(ET)\Omega(ET); D: O(dT)O(dT); R: O(ET)O(ET)coordinate finite differences; Gaussian two-pointyes
Smooth NC, no trace budget
Xia and Yuan [55]RΩ(dT)§\Omega(dT)^{\S}, O(dT)O(dT)Gaussian two-point (Nesterov and Spokoiny, [41])yes
1≤T≤d/log⁡(ed)1\le T\le d/\log(ed), Theorem 3.4DΩ(dT)c\Omega(dT)^{c}, O(dT)O(dT)coordinate finite differencesyes
Other settings
Effective rank (Malladi et al., [38]; Yue et al. [57])Rdd replaced by an effective dimensionrandom finite differences–
∥∇2f∥∗≤L∗\lVert\nabla^{2}f\rVert_{*}\le L_{*} (Anonymous, [3])RO(L∗Δ/ε2)O(L_{*}\Delta/\varepsilon^{2})Gaussian two-point–
First-order oracle, large dd (Carmon et al., [12])D, RΩ(T)\Omega(T), O(T)O(T)gradient descentyes
Lipschitz, local oracle (Jordan et al., [28]; Kornowski [31])D vs RGoldstein points: D pays (1/ε)Ω(d)(1/\varepsilon)^{\Omega(d)}––

Table 1. Query complexity of finding an ε\varepsilon-stationary point and the algorithms that attain the upper bounds. D and R denote deterministic and randomized algorithms, NC means nonconvex, and T=LΔ/ε2T=L\Delta/\varepsilon^{2}. All results use exact function values unless the setting names another oracle. Bold entries are new in this paper. “Matched”: whether the two bounds agree up to constant factors (yes) or up to the stated factor; a dash means that only one side is known.

Why can exact real replies still force Ω(d)\Omega(d) calls per hidden direction? When each reply carries a bounded number of bits, lower bounds follow by counting the revealed information (Basu et al., [7]). An exact real reply, however, can encode arbitrarily much discrete information, so counting returned scalars gives no lower bound. Against a deterministic algorithm, we instead combine the gated chains of Carmon et al. [12] with a resisting oracle (Nemirovsky and Yudin, [40]), so that the replies agree exactly with those of a single function in the class along the adaptive transcript. The oracle fixes each hidden direction only when its stage closes, after Ω(d)\Omega(d) units of cost, and keeps an unfinished direction orthogonal to the output, even if the output was never queried. The resulting function produces every reply of the run, and its gradient at the output has norm above ε\varepsilon. Multiplying the chain by a perspective weight rules out small gradients far from the origin and keeps the Hessian dominated by one fixed matrix on all of Rd\mathbb{R}^{d} (§ 4). Against randomized algorithms, the function must be chosen before the seed, and Yao’s principle (Yao, [56]) applied to a quadratic with an unknown center gives Ω(ET)\Omega(ET).

Contributions.

  • Randomized complexity scales with the trace rather than the dimension. We show that for all 1≤E≤d1 \le E \le d and T≥1T \ge1, the Gaussian two-point method of Nesterov and Spokoiny [41] attains O(ET)O(ET) calls when it accepts only steps that decrease ff. Without this acceptance test, we prove that it attains O(ET)O(ET) calls when the matrix bound holds on all of Rd\mathbb{R}^{d} and O(ET+Tlog⁡(ET))O(ET + T \log(ET)) calls on our sublevel-set class. Conversely, we prove that when ET≤dET \le d, every randomized algorithm requires at least Ω(ET)\Omega(ET) calls (Theorem 3.1).

References

  1. [1]Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 7319–7328, 2021. doi: 10.18653/v1/2021.acl-long.568.DOI
  2. [2]Anonymous. When does symmetry reduce effective rank in zeroth-order optimization? Submitted to ICLR 2027, 2026a. URL https://openreview.net/forum?id=EpIKUV Cy5D.
  3. [3]Anonymous. Revisiting the dimension dependence of zeroth-order optimization under Hessian trace-norm conditions. Submitted to ICLR 2027, 2026b. URL https://openreview.net/forum?id=ypBUtS8S0N.
  4. [4]Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1–2):165–214, 2023. doi: 10.1007/s10107-022-01822-7.
  5. [5]Larry Armijo. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of Mathematics, 16(1):1–3, 1966. doi: 10.2140/pjm.1966.16.1.DOI
  6. [6]Stefan Banach. Über homogene Polynome in (L²). Studia Mathematica, 7(1):36–44, 1938. doi: 10.4064/sm-7-1-36-44.
  7. [7]Amitabh Basu, Phillip Kerger, and Marco Molinaro. Tight lower bounds for binary first-order oracles for convex optimization. arXiv preprint arXiv:2511.02082, 2025.
  8. [8]Atılım Güneş Baydin, Barak A. Pearlmutter, Don Syme, Frank Wood, and Philip Torr. Gradients without backpropagation. arXiv preprint arXiv:2202.08587, 2022.arxiv.org/abs/2202.08587
  9. [9]El Houcine Bergou, Eduard Gorbunov, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal on Optimization, 30(4):2726–2749, 2020. doi: 10.1137/19M1244378.
  10. [10]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. doi: 10.1017/CBO9780511804441.DOI
  11. [11]Sébastien Bubeck and Dan Mikulincer. How to trap a gradient flow. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 940–960, 2020.arxiv.org/abs/2001.02968
  12. [12]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming, 184(1–2):71–120, 2020. doi: 10.1007/s10107-019-01406-y.DOI
  13. [13]Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15–26. ACM, 2017. doi: 10.1145/3128572.3140448.
  14. [14]Sinho Chewi, Sébastien Bubeck, and Adil Salim. On the complexity of finding stationary points of smooth functions in one dimension. In Shipra Agrawal and Francesco Orabona, editors, Proceedings of the 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 358–374, 2023.
  15. [15]Andrew R. Conn, Katya Scheinberg, and Luís N. Vicente. Introduction to Derivative-Free Optimization, volume 8 of MPS-SIAM Series on Optimization. SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718768.DOI
  16. [16]Romain Cosson, Ali Jadbabaie, Anuran Makur, Amirhossein Reisizadeh, and Devravrat Shah. Low-rank gradient descent. IEEE Open Journal of Control Systems, 2:380–395, 2023. doi: 10.1109/OJCSYS.2023.3315088.DOI
  17. [17]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, Hoboken, NJ, second edition, 2006. doi: 10.1002/047174882X.DOI
  18. [18]John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788–2806, 2015. doi: 10.1109/TIT.2015.2409256.DOI
  19. [19]Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013. doi: 10.1137/120880811.DOI
  20. [20]Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via Hessian eigenvalue density. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2232–2241, 2019.arxiv.org/abs/1901.10159
  21. [21]Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiyu Zhang. Gradientless descent: High-dimensional zeroth-order optimization. In International Conference on Learning Representations, 2020.arxiv.org/abs/1911.06317
  22. [22]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. doi: 10.1080/01621459.1963.10500830.DOI
  23. [23]Alexandros Hollender and Manolis Zampetakis. The computational complexity of finding stationary points in non-convex optimization. Mathematical Programming, 213(1–2):281–341, 2025. doi: 10.1007/s10107-024-02139-3.DOI
  24. [24]Robert Hooke and T. A. Jeeves. “Direct search” solution of numerical and statistical problems. Journal of the ACM, 8(2):212–229, 1961. doi: 10.1145/321062.321069.DOI
  25. [25]Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964. doi: 10.1214/aoms/1177703732.DOI
  26. [26]M. F. Hutchinson. A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Communications in Statistics – Simulation and Computation, 18(3):1059–1076, 1989. doi: 10.1080/03610918908812806.DOI
  27. [27]Kevin G. Jamieson, Robert D. Nowak, and Benjamin Recht. Query complexity of derivative-free optimization. In Advances in Neural Information Processing Systems 25, pages 2672–2680, 2012.arxiv.org/abs/1209.2434
  28. [28]Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, and Manolis Zampetakis. Deterministic nonsmooth nonconvex optimization. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4570–4597, 2023.arxiv.org/abs/2302.08300
  29. [29]Phillip Kerger. Closing the oracle-complexity gap in derivative-free convex optimization: A near-quadratic lower bound from exact function values. arXiv preprint arXiv:2607.13335, 2026.arxiv.org/abs/2607.13335
  30. [30]Pham Duy Khanh, Boris S. Mordukhovich, and Dat Ba Tran. General derivative-free optimization methods under global and local Lipschitz continuity of gradients. arXiv preprint arXiv:2311.16850, 2023.
  31. [31]Guy Kornowski. The exponential price of determinism in nonsmooth nonconvex optimization. arXiv preprint arXiv:2609.23837, 2026.arxiv.org/abs/2609.23837
  32. [32]David Kozak, Stephen Becker, Alireza Doostan, and Luis Tenorio. A stochastic subspace approach to gradient-free optimization in high dimensions. Computational Optimization and Applications, 79(2):339–368, 2021. doi: 10.1007/s10589-021-00271-w.DOI
  33. [33]Jeffrey Larson, Matt Menickelly, and Stefan M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287–404, 2019. doi: 10.1017/S0962492919000060.DOI
  34. [34]B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302–1338, 2000. doi: 10.1214/aos/1015957395.
  35. [35]Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.arxiv.org/abs/1804.08838
  36. [36]Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1–3):503–528, 1989. doi: 10.1007/BF01589116.
  37. [37]Sijia Liu, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O. Hero, III, and Pramod K. Varshney. A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43–54, 2020. doi: 10.1109/MSP.2020.3003837.DOI
  38. [38]Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. In Advances in Neural Information Processing Systems, volume 36, pages 53038–53075, 2023.arxiv.org/abs/2305.17333
  39. [39]John A. Nelder and Roger Mead. A simplex method for function minimization. The Computer Journal, 7(4):308–313, 1965. doi: 10.1093/comjnl/7.4.308.DOI
  40. [40]Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.
  41. [41]Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527–566, 2017. doi: 10.1007/s10208-015-9296-2.
  42. [42]Jorge Nocedal. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 35(151):773–782, 1980. doi: 10.1090/S0025-5718-1980-0572855-7.DOI
  43. [43]Gaku Omiya, Pierre-Louis Poirion, and Akiko Takeda. Randomized subspace Nesterov accelerated gradient. arXiv preprint arXiv:2605.00740, 2026.arxiv.org/abs/2605.00740
  44. [44]Zhen Qin, Daoyuan Chen, Bingchen Qian, Bolin Ding, Yaliang Li, and Shuiguang Deng. Federated full-parameter tuning of billion-sized language models with communication cost under 18 kilobytes. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 41473–41497, 2024.arxiv.org/abs/2312.06353
  45. [45]Farbod Roosta-Khorasani and Uri Ascher. Improved bounds on sample size for implicit matrix trace estimators. Foundations of Computational Mathematics, 15(5):1187–1212, 2015. doi: 10.1007/s10208-014-9220-1.
  46. [46]Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864, 2017.arxiv.org/abs/1703.03864
  47. [47]Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 3–24, 2013.arxiv.org/abs/1209.2388
  48. [48]Alexander Sholokhov and Alexander Rogozin. Parameter-free zeroth-order optimization with ellipsoidal sampling. arXiv preprint arXiv:2609.38561, 2026.arxiv.org/abs/2609.38561
  49. [49]Zbyněk Šidák. Rectangular confidence regions for the means of multivariate normal distributions. Journal of the American Statistical Association, 62(318):626–633, 1967. doi: 10.1080/01621459.1967.10482935.DOI
  50. [50]Joel Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679–706, 1985.DOI
  51. [51]Stephen A. Vavasis. Black-box complexity of local minimization. SIAM Journal on Optimization, 3(1):60–80, 1993. doi: 10.1137/0803004.DOI
  52. [52]Yining Wang, Simon S. Du, Sivaram Balakrishnan, and Aarti Singh. Stochastic zeroth-order optimization in high dimensions. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1356–1365, 2018.arxiv.org/abs/1710.10551
  53. [53]Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zh ouchen Lin. Near-optimal deterministic exact-value complexity for smooth convex optimization. arXiv preprint arXiv:2609.18230, 2026a.arxiv.org/abs/2609.18230
  54. [55]Yuxuan Xia and Xiao-Tong Yuan. On global joint lower bounds in zeroth-order nonconvex optimization. arXiv preprint arXiv:2610.19652, 2026.arxiv.org/abs/2610.19652
  55. [56]Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, pages 222–227, 1977. doi: 10.1109/SFCS.1977.24.DOI
  56. [57]Pengyun Yue, Long Yang, Cong Fang, and Zh ouchen Lin. Zeroth-order optimization with weak dimension dependency. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4429–4472, 2023.arxiv.org/abs/2307.05753
  57. [58]Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zh ouchen Lin. Joint lower bounds for zeroth-order nonconvex optimization on Euclidean balls. arXiv preprint arXiv:2610.00275, 2026a.arxiv.org/abs/2610.00275

Paper details

vlnc:W_76qbjs8r
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT (multiple versions), Anthropic’s Claude

View statement
Looking for related papers…
Contents