betaFeedback

Reading v1View latest version

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 high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding ε\varepsilon-stationary points of LL-smooth nonconvex functions on Rd\mathbb{R}^d from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most LELE; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When ET≤dET\le d, the Gaussian two-point method that such fine-tuning uses needs only O(ET)O(ET) calls if it rejects steps that raise ff, where T=LΔ/ε2T=LΔ/\varepsilon^2 is the iteration count of gradient descent from initial gap ΔΔ, and we prove that every randomized method needs Ω(ET)Ω(ET) calls, so this cost is optimal up to constants. In contrast, every deterministic method needs Ω~(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}\}): a deterministic method pays about dd calls per discovered direction, and the trace budget allows about ET\sqrt{ET} directions. Determinism thus multiplies the cost by a factor of order d/(E+ET)d/(E+\sqrt{ET}) up to logarithmic factors, which grows linearly with dd for fixed EE and TT; once EE exceeds TT by a logarithmic factor, deterministic methods need Ω(dT)Ω(dT) calls, as without any trace budget. Our lower bounds hold for C∞C^\infty functions with the matrix bound on all of Rd\mathbb{R}^d, even when each call also returns gradient projections priced by rank.

Introduction

Zeroth-order methods optimize with function values alone. They are the tool of choice when gradients are unavailable or too costly: attacking or explaining a model only through its outputs [12], tuning simulations, hyperparameters, and engineering designs [32], and searching policies in reinforcement learning [45]; see Liu et al. [36] for a survey. Interest has surged with large language models. Fine-tuning with forward passes alone needs about the memory of inference, so a single GPU can tune models that backpropagation cannot fit [37, 61], and seed-based zeroth-order updates reduce communication in federated fine-tuning [43].

For an LL-smooth nonconvex function on Rd\mathbb{R}^{d} with initial gap Δ\Delta, the classical analysis of random finite differences finds an ε\varepsilon-stationary point with O(dT)O(dT) function values, where T=LΔ/ε2T = L\Delta/\varepsilon^{2} [40, 18]. We prove that on the whole smooth class, deterministic

methods cannot do better: they need Ω(dT)\Omega(dT) calls when 1≤T≤d/log⁡(ed)1\le T\le d/\log(ed), even under rank-priced gradient projections (Theorem 3.4), matching coordinate finite differences; for exact values without projections, randomized methods also need Ω(dT)\Omega(dT) when d≳Tlog⁡Td\gtrsim T\log T, by concurrent and independent work (Xia and Yuan [54]). In high-dimensional tasks such as language model fine-tuning, however, randomized zeroth-order methods succeed at far lower cost, which effective rank analyses attribute to a low curvature trace (Malladi et al. [37]; Yue et al. [56]), in line with the low intrinsic dimension of fine-tuning (Li et al., [34]; Aghajanyan et al., [1]). Does this saving come from problem structure alone, or does it require randomness? Classical derivative-free methods—coordinate and pattern search (Hooke and Jeeves, [23]), the Nelder–Mead method (Nelder and Mead, [38]), and Powell’s interpolation methods (Conn et al., [14]; Larson et al., [32])—are deterministic, and so is any randomized method run with a fixed seed. We ask: what is the price of determinism under a low curvature trace—can deterministic methods match random directions by learning active subspaces, or must they still pay for the ambient dimension?

We quantify the worst-case cost of both algorithm classes on the same functions. Whereas prior work establishes a price of determinism for nonsmooth Goldstein stationarity (§ 7), we establish the smooth first-order counterpart in high dimension: randomness is essential to fully exploit a low curvature trace. Our main class keeps LL-smoothness and the initial gap Δ\Delta and adds an effective rank condition on the initial sublevel set, where descent methods operate: wherever f(x)<f(0)f(x) < f(0), the Hessian is dominated by one positive semidefinite matrix of operator norm at most LL and trace at most LELE. Because EE bounds the trace rather than the rank, curvature may spread across many directions while negative curvature is uncharged; § 3.1 compares this condition with prior curvature assumptions. Malladi et al. [37] assume such a matrix near each iterate of a run and show that the slowdown of zeroth-order SGD then depends on its effective rank rather than on dd; this is an upper bound for one randomized method. Our condition is fixed before the run and imposed only on the initial sublevel set. Under it, when ET≤dET \le d, we prove that the Gaussian two-point method attains O(ET)O(ET) calls if it rejects steps that raise ff, that no randomized method needs fewer, and that deterministic methods need more calls by a factor of order d/(E+ET)d/(E+\sqrt{ET}), up to logarithmic factors.

The price of determinism. Suppose E,T≥1E,T \ge1 and ET≤dET \le d. Intuitively, random probes pay only for the curvature trace, whereas deterministic methods pay the dimension dd for each active direction they discover, and a fixed trace budget allows at most O(ET)O(\sqrt{ET}) such directions. We show that deterministic methods always need at least dd calls, already far above O(ET)O(ET) when ET≪dET \ll d; adaptive subspace search uses O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}) calls, and a hidden chain forces Ω~(min⁡{T,ET})\widetilde{\Omega}(\min\{T,\sqrt{ET}\}) directions. Hence, writing NdetN_{\mathrm{det}} and NrandN_{\mathrm{rand}} for the worst-case query complexities (Theorems 3.1 and 3.2),

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

where Ω~\widetilde{\Omega} hides only a factor log⁡(e+T)\sqrt{\log(e+T)}; Section 3 states the logarithm explicitly. The price of determinism, Ndet/NrandN_{\mathrm{det}}/N_{\mathrm{rand}}, thus lies between Ω~(d/(E+ET))\widetilde{\Omega}(d/(E+\sqrt{ET})) and O(d/(E+ET))O(d/(E+\sqrt{ET})), growing linearly with dd for fixed EE and TT. Once E≥Tlog⁡(e+T)E \ge T\log(e+T), deterministic cost reverts to Ω(dT)\Omega(dT), so both classes are matched up to constant factors with cost ratio of order d/Ed/E (Corollary 3.3).

Why exact feedback can still be hard. When each reply carries a bounded number of bits, counting information gives lower bounds ([6]). An exact real reply can encode arbitrarily much discrete information, so counting returned scalars gives no lower bound. Recent lower bounds with exact function values for convex minimization on a ball overcome this obstacle for deterministic ([28, 52 b]) and randomized ([58]) methods, bounding objective error on a compact domain. Our lower bounds concern the gradient norm on Rd\mathbb{R}^d under unrestricted queries, unqueried outputs, and rank-priced gradient projections, by constructing functions whose replies agree exactly along the adaptive transcript. Against a deterministic algorithm, a resisting oracle (Nemirovsky and Yudin [39]) fixes each hidden direction only when its stage closes, after Ω(d)\Omega(d) units of feedback: it is chosen orthogonal to the stage’s query points and to all its projection subspaces except possibly the closing one, and the next unfinished direction is chosen orthogonal to the output. One fixed function in the class realizes all replies and keeps the output gradient above ε\varepsilon. Multiplying the hidden chain by a perspective weight rules out small gradients far away and keeps the Hessian dominated by one fixed matrix on all of Rd\mathbb{R}^d (Appendix § 17.3). For randomized algorithms, Yao’s principle (Yao [55]) with an unknown quadratic center gives Ω(ET)\Omega(ET).

Contributions

  • Randomized cost scales with the trace, not the dimension. The Gaussian two-point method (Nesterov and Spokoiny [40]) uses O(ET)O(ET) calls for all E,T≥1E,T \ge1 when it rejects steps that raise ff; without this test it uses 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 in general. Conversely, every randomized method needs Ω(ET)\Omega(ET) calls when ET≤dET \le d (Theorem 3.1).

  • Quantifying the price of determinism under low trace. For ET≤dET \le d, adaptive subspace search achieves O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}) calls, while C∞C^\infty hard functions force Ω~(dmin⁡{T,ET})\widetilde{\Omega}(d\min\{T,\sqrt{ET}\}) calls even when the matrix bound holds on all of Rd\mathbb{R}^d (Theorem 3.2). Across Tlog⁡(e+T)≤E≤d/TT\log(e+T) \le E \le d/T, the trace stops helping deterministic methods (Ω(dT)\Omega(dT) calls), and determinism multiplies the cost by order d/Ed/E (Corollary 3.3).

  • Optimality of coordinate finite differences without a trace budget. On the unrestricted smooth class, deterministic methods need at least dT/500dT/500 calls when 1≤T≤d/log⁡(ed)1 \le T \le d/\log(ed), including under adaptive rank-priced gradient projections (Theorem 3.4).

Table 1 places these results among the closest prior bounds.

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 test2yes
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. [15]up to log⁡(e+T)\sqrt{\log(e+T)}3
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 [54]RΩ(dT)\Omega(dT)1, O(dT)O(dT)Gaussian two-point (Nesterov and Spokoiny, [40])yes
1≤T≤d/log⁡(ed)1\le T\le d/\log(ed), Theorem 3.4DΩ(dT)\Omega(dT)4, O(dT)O(dT)coordinate finite differencesyes
Other settings
Effective rank (Malladi et al., [37]; Yue et al., [56])Rdd replaced by an effective dimensionrandom finite differences–
∥∇2f∥∗≤H\lVert\nabla^2 f\rVert_* \le H (Anonymous, [3])RO(HΔ/ε2)O(H\Delta/\varepsilon^2)Gaussian two-point–
First-order oracle, large dd (Carmon et al., [11])D, RΩ(T)\Omega(T), O(T)O(T)gradient descentyes
Lipschitz, local oracle (Jordan et al., [27]; Kornowski, [30])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), up to the stated factor, or only on stated ranges; a dash means that only one side is known.

Section 2 defines the classes and oracles, Section 3 states the formal bounds, and § 6 explains the proof mechanisms. § 7 compares with prior work, § 8 illustrates the mechanisms numerically, and § 9 covers open problems and limitations. Appendices § 11, § 12, and § 17 give explicit constants, algorithm analyses, and C∞C^\infty constructions under global trace bounds.

Setting

Function classes. For L,Δ>0L,\Delta> 0, let

FL,Δd:={f∈C1,1(Rd):Lip⁡(∇f)≤L, f(0)−inf⁡f≤Δ}.(1)\mathcal{F}^{d}_{L,\Delta} := \{f \in C^{1,1}(\mathbb{R}^{d}) : \operatorname{Lip}(\nabla f) \le L,\ f(0) - \inf f \le\Delta\}. \tag*{(1)}

The goal is a point x^∈Rd\widehat{x} \in\mathbb{R}^{d} with ∥∇f(x^)∥≤ε\|\nabla f(\widehat{x})\| \le\varepsilon, and we write T:=LΔ/ε2T := L\Delta/\varepsilon^{2}. For 1≤E≤d1 \le E \le d, the main class BL,Δ,Ed\mathcal{B}^{d}_{L,\Delta,E} consists of the f∈FL,Δdf \in\mathcal{F}^{d}_{L,\Delta} for which some unknown matrix H⪰0H \succeq0 with ∥H∥op≤L\|H\|_{\mathrm{op}} \le L and tr⁡H≤LE\operatorname{tr} H \le LE satisfies

∇2f(x)⪯Hfor almost every x with f(x)<f(0).(2)\nabla^{2}f(x) \preceq H \qquad\text{for almost every }x\text{ with }f(x) < f(0). \tag*{(2)}

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=Ep1KUVcy5D.
  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=ypBUtS8SON.
  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]Amitabh Basu, Phillip K erger, and Marco Molinaro. Tight lower bounds for binary first-order oracles for convex optimization. arXiv preprint arXiv:2511.02082, 2025.arxiv.org/abs/2511.02082
  7. [7]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
  8. [8]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.DOI
  9. [9]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. doi: 10.1017/CBO9780511804441.DOI
  10. [10]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
  11. [11]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
  12. [12]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.DOI
  13. [13]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.arxiv.org/abs/2209.07513
  14. [14]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
  15. [15]Romain Cosson, Ali Jadbaie, Anuran Makur, Amirhossein Reisizadeh, and Devavrat Shah. Low-rank gradient descent. IEEE Open Journal of Control Systems, 2:380–395, 2023. doi: 10.1109/OJCSYS.2023.3315088.DOI
  16. [16]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, Hoboken, NJ, second edition, 2006. doi: 10.1002/047174882X.DOI
  17. [17]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
  18. [18]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
  19. [19]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
  20. [20]Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gradientless descent: High-dimensional zeroth-order optimization. In International Conference on Learning Representations, 2020.
  21. [21]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
  22. [22]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
  23. [23]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
  24. [24]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
  25. [25]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
  26. [26]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
  27. [27]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
  28. [28]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
  29. [29]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.arxiv.org/abs/2311.16850
  30. [30]Guy Kornowski. The exponential price of determinism in nonsmooth nonconvex optimization. arXiv preprint arXiv:2609.23837, 2026.arxiv.org/abs/2609.23837
  31. [31]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
  32. [32]Jeffrey Larson, Matt Menickelly, and Stefan M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287–404, 2019. doi: 10.1017/S0962492919000060.DOI
  33. [33]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.
  34. [34]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
  35. [35]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.
  36. [36]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
  37. [37]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
  38. [38]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
  39. [39]Arkadi S. Nemirovsky and David B. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, 1983.DOI
  40. [40]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.
  41. [41]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
  42. [42]Gaku Omiya, Pierre-Louis Poirion, and Akiko Takeda. Randomized subspace Nesterov accelerated gradient. arXiv preprint arXiv:2605.00740, 2026.arxiv.org/abs/2605.00740
  43. [43]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
  44. [44]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.DOI
  45. [45]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
  46. [46]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
  47. [47]Alexander Sholokhov and Alexander Rogozin. Parameter-free zeroth-order optimization with ellipsoidal sampling. arXiv preprint arXiv:2609.38561, 2026.arxiv.org/abs/2609.38561
  48. [48]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
  49. [49]Joel Spencer. Six standard deviations suffice. Transactions of the American Mathematical Society, 289(2):679–706, 1985.
  50. [50]Stephen A. Vavasis. Black-box complexity of local minimization. SIAM Journal on Optimization, 3(1):60–80, 1993. doi: 10.1137/0803004.DOI
  51. [51]Yining Wang, Simon S. Du, Sivaramakrishnan 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.
  52. [52]Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyu​​an 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
  53. [54]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
  54. [55]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
  55. [56]Pengyun Yue, Long Yang, Cong Fang, and Zhоуchen 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
  56. [57]Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchен Lin. Joint lower bounds for zeroth-order nonconvex optimization on Euclidean balls. arXiv preprint arXiv:2610.00275, 2026a.arxiv.org/abs/2610.00275
  57. [58]Haihan Zhang, Chenheng Zhang, Zhiquan Qi, and Zhоuchen Lin. Near-optimal lower bounds for randomized algorithms in exact value zeroth-order convex optimization. arXiv preprint arXiv:2607.16558, 2026b.arxiv.org/abs/2607.16558
  58. [60]Liang Zhang, Bingcong Li, Kiran Koshy Thekumparampil, Sewoong Oh, Michael Muehlebach, and Niao He. Zeroth-order optimization finds flat minima. In Advances in Neural Information Processing Systems, volume 38, pages 160959–160998, 2025. doi: 10.52202/085713-5375.DOI
  59. [61]Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen. Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: A benchmark. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 59173–59190, 2024.arxiv.org/abs/2402.11592

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