Pith. sign in

REVIEW 3 major objections 5 minor 82 references

Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale

T0 review · 3 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper claims that a unified subspace-alignment analysis explains why sparse, low-rank, and block-sparse perturbations in zeroth-order optimization converge at the same rate, and that this licenses building MeZO-BCD for…

desk verdict MeZO-BCD is a real practical win, but the theoretical bridge from equal expected alignment to equal average-case convergence is not secured. read the letter →

arxiv 2501.19099 v2 pith:CSTLPE7G submitted 2025-01-31 cs.LG

Sihwan Park , Jihun Yun , SungYub Kim , Souvik Kundu , Eunho Yang This is my paper · ORCID
classification cs.LG
keywords zeroth-orderoptimizationsubspaceperturbationalignmentblockcoordinatedescentlargelanguagemodelfine-tuningconvergencerategeneralizationmemory-efficient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish why subspace-structured perturbations speed up zeroth-order optimization and when they stop helping. It proposes a unified convergence analysis built on a quantity called subspace alignment, showing that the dominant bottleneck is parameter dimension, not the perturbation family. The central rate is $O(r^2/(\rho T)+s^2/(dT)+\Delta/(\alpha T)+\sigma^2/B)$, where $r$ is the local intrinsic dimension and $\rho$ is subspace alignment. The paper argues that sparse, low-rank, and block-sparse perturbations share the same expected subspace alignment, so the perturbation family should be chosen for engineering efficiency. This motivates MeZO-BCD, a block-coordinate zeroth-order fine-tuner that reports up to 2.77x wall-clock speedup over MeZO on OPT-13B with comparable fine-tuning quality.

What carries the argument

The central object is subspace alignment $\rho_t = \operatorname{Tr}(M_t^\top H(\theta_t)M_t)/\lambda_{\max}(H(\theta_t))$, which measures how much of the local Hessian upper bound is captured by the perturbation matrix $M_t$. It drives the $r^2/(\rho T)$ term in Theorem 3.3, and the paper couples it with Assumption 3.1 (local intrinsic dimension $r$) and the stable rank $s$ of $M_t$. Proposition 3.4 is the identity $E[\rho]=s\operatorname{Tr}(H)/(d\lambda_{\max}(H))$ for any PSD projection matrix with $E[M]=(s/d)I$, which is what makes low-rank, sparse, and block-sparse perturbations equivalent in expectation; Proposition 3.6 then separates them by tail behavior.

What would settle it

Measure the local Hessian intrinsic dimension $r$ during actual OPT-13B fine-tuning with a Lanczos or sub-sampled Hessian estimator: if $r$ is comparable to $d$ in the regions visited by MeZO-BCD, the predicted $r^2/(\rho T)$ advantage vanishes, and if $r\ll d$ holds but convergence still does not improve with subspace size, the alignment mechanism itself is called into question.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims that high dimensionality, not the perturbation family, is the primary bottleneck in zeroth-order optimization, and that a scalar quantity—subspace alignment $\rho_t = \operatorname{Tr}(M_t^\top H(\theta_t)M_t)/\lambda_{\max}(H(\theta_t))$—controls how much a structured perturbation reduces gradient noise. Under the local-intrinsic-dimension assumption (Assumption 3.1), subspace ZO-SGD converges at $O(r^2/(\rho T) + s^2/(dT) + \Delta/(\alpha T) + \sigma^2/B)$, and in the ideal regime $\rho=O(r)$ this improves to $O(r/T)$ instead of the standard $O(d/T)$. Proposition 3.4 shows that any randomly chosen projection matrix with $E[M]=(s/d)I$ has expected alignment $E[\rho]=s\operatorname{Tr}(H)/(d\lambda_{\max}(H))$, so low-rank, sparse, and block-sparse perturbations coincide in expectation; Proposition 3.6 distinguishes them only by tail concentration. The paper therefore argues the perturbation family should be selected for practical efficiency, and builds MeZO-BCD, a block-coordinate zeroth-order method that perturbs and updates one block per step, cutting per-iteration parameter loading from roughly $5d$ to $2d+3d/N$. On OPT-13B, MeZO-BCD reports up to 2.77x wall-clock speedup over MeZO with comparable fine-tuning accuracy, and a stability analysis gives generalization error $O(T^{1-1/(1+q)}/n)$ with $q=CL\sqrt{s}$, independent of $d$.

Load-bearing premise

The analysis rests on Assumption 3.1: near every iterate the loss has a local intrinsic dimension $r$, meaning its Hessian upper bound is effectively rank $r$; if the Hessian is actually full-rank ($r\approx d$), the theory's dimension-free advantage disappears and subspace methods fall back to the standard $O(d/T)$ rate.

Editorial extensions

If this is right

  • If the central claim is right, subspace ZO-SGD with $s=\Theta(\sqrt{rd})$ has near-dimension-free convergence whenever the loss has local intrinsic dimension $r\ll d$.
  • The equivalence result means algorithm designers can choose perturbation structure by memory bandwidth and implementation cost without sacrificing average-case convergence.
  • MeZO-BCD's per-step parameter loading drops from about $5d$ to $2d+3d/N$, and this is what yields the reported up to 2.77x wall-clock speedup on OPT-13B.
  • MeZO-BCD enables stateful optimizers such as Adam in a memory-efficient way, cutting peak memory for OPT-13B from 73.4GB for MeZO plus Adam to 26.5GB while keeping iteration time close to MeZO-BCD.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit that the equivalence-in-expectation result also predicts when subspace methods will fail: on tasks where the Hessian is effectively full rank ($r\approx d$), every perturbation family, including MeZO-BCD, should fall back to the standard $O(d/T)$ rate.
  • A testable extension suggested by the analysis is to use block-level subspace alignments as a cheap adaptive schedule; the paper's own preliminary experiments show only marginal gains, so the open question is whether better estimators of block curvature close the gap.
  • The $d$-independence of the generalization bound hints that block-coordinate ZO might be unusually stable for very wide models, which could matter for private or low-memory distributed training where per-step noise must be controlled.
  • Because the bandwidth argument applies to any forward-only memory-bound setting, the same block-coordinate idea could transfer to on-device fine-tuning or federated zeroth-order methods, not just single-GPU LLM fine-tuning.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper develops a unified theoretical framework for zeroth-order SGD with subspace perturbations (sparse, low-rank, block-sparse), introducing a notion of 'subspace alignment' ρ_t that measures the overlap between the perturbation subspace and the local Hessian. Theorem 3.3 bounds the average squared gradient norm by O(r²/(ρT) + s²/(dT) + Δ/(αT) + σ²/B), where ρ is the time-averaged alignment, and Theorem 3.10 provides a dimension-free generalization bound. Proposition 3.4 shows that three natural perturbation families have the same expected alignment E[ρ], and Proposition 3.6 describes their different tail behaviors. Based on the claimed equivalence, the paper proposes MeZO-BCD, a block-coordinate-descent variant that perturbs and updates one block per step, and reports up to 2.77× wall-clock speedup over MeZO on OPT-13B with comparable fine-tuning accuracy.

Significance. If the equivalence claim were fully supported, the paper would provide a principled justification for choosing perturbation families by practical efficiency rather than by their convergence theory, which is a valuable design principle for memory-bound LLM fine-tuning. The empirical contribution, MeZO-BCD, is practically interesting and the experiments are reasonably thorough, including ablations on block partitioning and selection strategies. The theoretical development is structurally novel—it extends the intrinsic-dimension analysis of MeZO to finite smoothing and arbitrary projection perturbations, and the proofs are written out in detail. However, the load-bearing step from equal expected alignment to comparable average-case convergence is not secured, as detailed in the major comments. The paper's central conceptual claim therefore needs substantial reworking, even though the algorithmic idea may survive independently.

major comments (3)
  1. [Section 3.2, Theorem 3.3 and remark after Proposition 3.4] The inference that the three instantiations in Definition 3.5 have 'comparable average convergence' is not supported by Theorem 3.3. The theorem's rate contains 1/ρ, where ρ = (1/T)Σ_{t=1}^T ρ_t is a realized random quantity for the three instantiations, while Proposition 3.4 only equates E[ρ]. Since x ↦ 1/x is strictly convex, equal E[ρ] does not imply equal E[1/ρ]. For block-sparse perturbation, ρ_t is the normalized trace of a single block; if any block has zero (or very small) diagonal Hessian contribution, ρ_t = 0 (or very small) with probability at least 1/N, so E[1/ρ] can be infinite or substantially larger than for low-rank or sparse perturbations. The paper must either bound the expectation of the full RHS of Theorem 3.3, or prove a high-probability lower bound on ρ_t that holds uniformly for all three families, before claiming equivalent average-case convergence.
  2. [Theorem 3.3 statement and its proof (Appendix B.5)] The displayed bound in Theorem 3.3 is not an unconditional expectation bound: the RHS depends on the random quantities ρ and ρmax both directly (through 1/ρ) and through the step-size and smoothing parameters, μ = O(1/(L√(ρ d T))) and α ≤ 1/(36Lρmax + 336Ls·exp(-s/2)). The proof treats these as given scalars for a fixed M_t sequence. When M_t is random, as in Definition 3.5, the bound holds only conditional on the realized ρ_t sequence, and no expectation is taken over the 1/ρ and 1/ρmax terms. The theorem should be rephrased either as a statement conditional on the M_t sequence or with explicit high-probability or expectation arguments over the randomness in ρ and ρmax.
  3. [Proposition 3.6 and Section 3.4 (empirical validation)] The discussion of Proposition 3.6 calls the Chebyshev-based quadratic tail bound for sparse perturbation 'tight concentration' and contrasts it with block-sparse's 'point mass.' Chebyshev's inequality is a worst-case bound and is not tight in general; more importantly, the block-sparse distribution has exactly the heavy lower tail (ρ near 0 with probability proportional to the number of low-curvature blocks) that makes the 1/ρ term in Theorem 3.3 blow up. The empirical validation in Section 3.4 uses a block-diagonal Hessian whose blocks all have positive curvature, so it never probes the regime where the theoretical gap between the families is most severe. The paper should acknowledge this limitation and, if possible, provide separate experiments or bounds for the low-curvature-block regime.
minor comments (5)
  1. [Assumption 3.1 / Appendix B.1] The advertised dimension-free rate relies on r << d, but the paper does not measure r on the OPT-13B tasks; the discussion in Appendix B.1 appeals to prior Hessian-spectrum studies, which is reasonable but does not directly validate the regime for the actual experiments. A brief empirical check of the local intrinsic dimension, even on a smaller model, would strengthen the link between theory and practice.
  2. [Definition 3.5, item 3] The block-sparse instantiation assumes N = d/s is an integer; the paper should explicitly state that s divides d, since Proposition 3.4 and the subsequent rates treat s as a real number.
  3. [Theorem 3.3 notation] The LHS of the theorem reads E[||∇L(θ_t)||²], but the proof establishes a bound on (1/T)Σ_{t=1}^T E[||∇L(θ_t)||²]. The theorem statement should use the averaged form to match the proof and avoid ambiguity.
  4. [Table 9 and Appendix F.2] The three-seed results in Table 9 are useful, but the table caption should state which seeds were used (the text says {0, 42, 100}); it would be even clearer to list them in the caption or directly in the table.
  5. [Lemma B.8] The concentration inequality used to bound P(E^c) ≤ exp(-c1 d) is not stated explicitly; a reference or a one-line derivation would help readers verify the constant and the applicability to the Gaussian random vector u.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence and alignment results are derived from stated assumptions and external evidence, not from fitting or self-referential definitions.

full rationale

The paper's central derivation chain is self-contained and non-circular. Assumption 3.1 is a stated regularity condition on the loss's local Hessian, with independent external support cited from the Hessian-spectrum literature and from MeZO (Malladi et al., 2023); it is not defined in terms of the convergence result. The subspace alignment quantity in Definition 3.2 is defined from the perturbation matrix and the assumed Hessian upper bound, and Theorem 3.3 is proved from smoothness, bounded variance, stable rank, and local intrinsic dimension, without fitting parameters to the LLM experiments. Proposition 3.4 is a direct expectation calculation under the explicit condition E[M]=(s/d)I, and the three instantiations in Definition 3.5 are checked against those conditions; Proposition 3.6 derives distinct tail behaviors rather than assuming them. The step from equal E[rho] to comparable average-case convergence is a mathematical-inference point (the theorem's rate involves 1/rho, so one must be careful with Jensen's inequality), but that is a soundness question, not circularity: the claim is not true by construction and does not reuse its own conclusion as an input. MeZO-BCD is then introduced as a block-sparse perturbation instance, and its reported speedups are measured wall-clock results against external baselines. The only self-citations, such as Park et al. (2024), appear as related-work background and are not load-bearing in the convergence or generalization proofs. There is no fitted input renamed as a prediction, no uniqueness theorem imported from the authors' own prior work, and no ansatz smuggled in through self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The theory rests on standard smoothness and bounded-variance assumptions plus a local intrinsic-dimension assumption inherited from MeZO. No constants are fitted to data; the empirical sections vary alignment and block structure to confirm predicted trends rather than to set parameters. The main new entity is the subspace alignment scalar, which is a definition with a testable convergence implication.

assumptions (5)
  • domain assumption C-1: each loss L_i is L-smooth
    Standard smoothness assumption in non-convex optimization; used throughout convergence and generalization proofs (Section 3.1).
  • domain assumption C-2: unbiased stochastic gradients with bounded variance and bounded true gradient
    Standard stochastic optimization assumption; used to bound the estimator variance in Lemma B.7 and Theorem 3.3.
  • domain assumption Assumption 3.1: local intrinsic dimension r of an upper-bound Hessian H(θ_t) in an O(s)-ball
    Load-bearing: yields the r^2/(ρT) term; if r is O(d) the rate degrades to standard d/T. Justified by prior empirical LLM Hessian observations, not verified here. Section 3.2, Assumption 3.1.
  • standard math In Proposition 3.4, M is an orthogonal projection with E[M]=(s/d)I
    Structural condition for the three instantiations (low-rank, sparse, block-sparse); the paper proves they satisfy it in Appendix B.7.
  • domain assumption For Theorem 3.10, bounded loss sup|L|≤1 and step sizes α_t=C/t
    Uniform stability framework requires a bounded loss; standard for generalization bounds.
invented entities (1)
  • Subspace alignment ρ_t independent evidence
    purpose: Scalar measure of overlap between perturbation subspace M_t and Hessian upper bound H(θ_t), used to predict convergence speed.
    This is a new mathematical quantity introduced in Definition 3.2. It has a falsifiable handle: the theory predicts faster convergence for higher ρ, which the authors test in synthetic quadratic experiments (Figure 1, Left and Middle), but it is not measured on real LLMs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale." pith.science (2026). https://pith.science/paper/CSTLPE7G

@misc{pith2026250119099,
  author       = {Pith},
  title        = {Pith review of: Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CSTLPE7G}},
  note         = {Machine review of arXiv:2501.19099}
}
abstract

Zeroth-order (ZO) optimization has emerged as a promising alternative to gradient-based backpropagation methods, particularly for black-box optimization and large language model (LLM) fine-tuning. However, ZO methods often suffer from slow convergence due to high-variance stochastic gradient estimators. While subspace perturbations, such as sparsity and low-rank constraints, have been explored to mitigate this issue, their effectiveness remains poorly understood. In this work, we develop a \emph{unified theoretical framework} that analyzes both the convergence and generalization properties of ZO optimization under subspace perturbations. We show that high dimensionality is the primary bottleneck and introduce the notion of \textit{subspace alignment} to explain how the subspace perturbations reduce gradient noise and accelerate convergence. Our analysis further shows that a broad class of subspace perturbations exhibits a similar convergence rate, motivating us to prioritize practical considerations in real-world algorithm design. Building on these insights, we propose an efficient ZO method using block coordinate descent (MeZO-BCD), which perturbs and updates only a subset of parameters at each step. Extensive experiments show that MeZO-BCD significantly accelerates optimization, achieving up to $\mathbf{\times2.77}$ speedup in wall-clock time over MeZO on OPT-13B, while maintaining comparable iteration complexity and fine-tuning performance.

Figures

Figures reproduced from arXiv: 2501.19099 by the authors.

Figure 1
Figure 1. Empirical validation of theoretical insights on randomized quadratic minimization. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Comparison of training loss curves in terms of iterations ( [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Comparative visualization of the distribution of subspace alignment [PITH_FULL_IMAGE:figures/full_fig_p042_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Training loss curves for varying srank(M) across low-rank, sparse, and block sparse perturbation methods. Each plot corresponds to a fixed srank(M). The reported ρ¯ values indicate the mean subspace alignment for each method. Learning rate η = 10−4 is used throughout …
Figure 5
Figure 5. Figure 5: Training loss curves averaged over three seeds { [PITH_FULL_IMAGE:figures/full_fig_p043_5.png]
Figure 6
Figure 6. Figure 6: Loss curves for MeZO-BCD under adaptive vs random block selection strategies on OPT [PITH_FULL_IMAGE:figures/full_fig_p045_6.png]
Figure 7
Figure 7. Figure 7: Statistics of adaptive block selection. Left: The heatmap shows the p (j) t for each block as training progresses. For heatmap visualization, the probability distribution is averaged every 100 steps. The line plot below the heatmap shows the block index with the highes…
Figure 8
Figure 8. Figure 8: Training loss curves for MeZO-BCD and MeZO-BCD (+Adam) on SST-2 and SQuAD. [PITH_FULL_IMAGE:figures/full_fig_p048_8.png]
Figure 9
Figure 9. Figure 9: Comparison of per-step iteration time (left) and peak memory consumption (right) for MeZO and MeZO-BCD with and without Adam, across model sizes for fine-tuning on SST-2 (averaged over 100 training steps). MeZO-BCD (+Adam) achieves significantly lower memory usage comp…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

82 extracted references · 49 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    and Cutkosky, A

    Ahn, K. and Cutkosky, A. Adam with model exponential moving average is effective for nonconvex optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=v416YLOQuU

    2024

  3. [3]

    The second pascal recognising textual entailment challenge

    Bar-Haim, R., Dagan, I., Dolan, B., Ferro, L., Giampiccolo, D., Magnini, B., and Szpektor, I. The second pascal recognising textual entailment challenge. In Proceedings of the second PASCAL challenges workshop on recognising textual entailment, volume 1. Citeseer, 2006

    work page 2006

  4. [4]

    The fifth pascal recognizing textual entailment challenge

    Bentivogli, L., Clark, P., Dagan, I., and Giampiccolo, D. The fifth pascal recognizing textual entailment challenge. TAC, 7 0 (8): 0 1, 2009

    work page 2009

  5. [5]

    S., Cao, L., Choromanski, K., and Scheinberg, K

    Berahas, A. S., Cao, L., Choromanski, K., and Scheinberg, K. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, 22 0 (2): 0 507--560, 2022

    work page 2022

  6. [6]

    and Elisseeff, A

    Bousquet, O. and Elisseeff, A. Stability and generalization. The Journal of Machine Learning Research, 2: 0 499--526, 2002

    2002

  7. [7]

    A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization

    Cai, H., Lou, Y., McKenzie, D., and Yin, W. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference on Machine Learning, pages 1193--1203. PMLR, 2021

    work page 2021

  8. [8]

    Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models

    Chen, P.-Y., Zhang, H., Sharma, Y., Yi, J., and Hsieh, C.-J. 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, 2017

    work page 2017

Show all 82 references
  1. [9]

    On the convergence of a class of adam-type algorithms for non-convex optimization

    Chen, X., Liu, S., Sun, R., and Hong, M. On the convergence of a class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=H1x-x309tm

    2019

  2. [10]

    Enhancing zeroth-order fine-tuning for language models with low-rank structures

    Chen, Y., Zhang, Y., Cao, L., Yuan, K., and Wen, Z. Enhancing zeroth-order fine-tuning for language models with low-rank structures. arXiv preprint arXiv:2410.07698, 2024

    2024 arXiv

  3. [11]

    Boolq: Exploring the surprising difficulty of natural yes/no questions

    Clark, C., Lee, K., Chang, M.-W., Kwiatkowski, T., Collins, M., and Toutanova, K. Boolq: Exploring the surprising difficulty of natural yes/no questions. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human...

    2019

  4. [12]

    Large scale machine learning

    Collobert, R. Large scale machine learning. Technical report, Universit \'e de Paris VI, 2004

    2004

  5. [13]

    The pascal recognising textual entailment challenge

    Dagan, I., Glickman, O., and Magnini, B. The pascal recognising textual entailment challenge. In Machine learning challenges workshop, pages 177--190. Springer, 2005

    2005

  6. [14]

    T., Padmanabhan, S., and Ye, G

    Davis, D., Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., and Ye, G. A gradient sampling method with complexity guarantees for lipschitz functions in high and low dimensions. Advances in neural information processing systems, 35: 0 6692--6703, 2022

    2022

  7. [15]

    The commitmentbank: Investigating projection in naturally occurring discourse

    De Marneffe, M.-C., Simons, M., and Tonhauser, J. The commitmentbank: Investigating projection in naturally occurring discourse. In proceedings of Sinn und Bedeutung, volume 23, pages 107--124, 2019

    2019

  8. [16]

    Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs

    Dua, D., Wang, Y., Dasigi, P., Stanovsky, G., Singh, S., and Gardner, M. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: ...

    2019

  9. [17]

    C., Jordan, M

    Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61 0 (5): 0 2788--2806, 2015

    2015

  10. [18]

    Variance-reduced zeroth-order methods for fine-tuning language models

    Gautam, T., Park, Y., Zhou, H., Raman, P., and Ha, W. Variance-reduced zeroth-order methods for fine-tuning language models. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=VHO4nE7v41

    2024

  11. [19]

    and Lan, G

    Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23 0 (4): 0 2341--2368, 2013

    2013

  12. [20]

    W., and Keutzer, K

    Gholami, A., Yao, Z., Kim, S., Hooper, C., Mahoney, M. W., and Keutzer, K. Ai and memory wall. IEEE Micro, 2024

    2024

  13. [21]

    An investigation into neural net optimization via hessian eigenvalue density

    Ghorbani, B., Krishnan, S., and Xiao, Y. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, pages 2232--2241, 2019

    2019

  14. [22]

    Giampiccolo, D., Magnini, B., Dagan, I., and Dolan, W. B. The third pascal recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing, pages 1--9, 2007

    2007

  15. [23]

    R., Bastani, O., De Sa, C., Yu, X., et al

    Guo, W., Long, J., Zeng, Y., Liu, Z., Yang, X., Ran, Y., Gardner, J. R., Bastani, O., De Sa, C., Yu, X., et al. Zeroth-order fine-tuning of llms with extreme sparsity. arXiv preprint arXiv:2406.02913, 2024

    2024 arXiv

  16. [24]

    Hanson, D. L. and Wright, F. T. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42 0 (3): 0 1079--1083, 1971

    1971

  17. [25]

    Train faster, generalize better: Stability of stochastic gradient descent

    Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225--1234. PMLR, 2016

    2016

  18. [26]

    Ipsen, I. C. and Saibaba, A. K. Stable rank and intrinsic dimension of real and complex matrices. arXiv preprint arXiv:2407.21594, 2024

    2024 arXiv

  19. [27]

    On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables

    Isserlis, L. On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables. Biometrika, 12 0 (1/2): 0 134--139, 1918

    1918

  20. [28]

    Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization

    Ji, K., Wang, Z., Zhou, Y., and Liang, Y. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In International conference on machine learning, pages 3100--3109. PMLR, 2019

    2019

  21. [29]

    How large language models encode context knowledge? a layer-wise probing study

    Ju, T., Sun, W., Du, W., Yuan, X., Ren, Z., and Liu, G. How large language models encode context knowledge? a layer-wise probing study. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LREC-COLING 2024),...

    2024

  22. [30]

    Looking beyond the surface: A challenge set for reading comprehension over multiple sentences

    Khashabi, D., Chaturvedi, S., Roth, M., Upadhyay, S., and Roth, D. Looking beyond the surface: A challenge set for reading comprehension over multiple sentences. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistic...

    2018

  23. [31]

    RA - L o RA : Rank-adaptive parameter-efficient fine-tuning for accurate 2-bit quantized large language models

    Kim, M., Lee, S., Sung, W., and Choi, J. RA - L o RA : Rank-adaptive parameter-efficient fine-tuning for accurate 2-bit quantized large language models. In Ku, L.-W., Martins, A., and Srikumar, V., editors, Findings of the Association for Computational Linguistics: ACL 2024, p...

    2024 doi

  24. [32]

    W., and Keutzer, K

    Kim, S., Hooper, C., Gholami, A., Dong, Z., Li, X., Shen, S., Mahoney, M. W., and Keutzer, K. Squeezellm: Dense-and-sparse quantization. arXiv preprint arXiv:2306.07629, 2023

    2023 arXiv

  25. [33]

    and Ba, J

    Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015

    2015

  26. [34]

    and Shamir, O

    Kornowski, G. and Shamir, O. An algorithm with optimal dimension-dependence for zero-order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25 0 (122): 0 1--14, 2024

    2024

  27. [35]

    J., and Bengio, S

    Kurakin, A., Goodfellow, I. J., and Bengio, S. Adversarial machine learning at scale. In International Conference on Learning Representations, 2017. URL https://openreview.net/forum?id=BJm4T4Kgx

    2017

  28. [36]

    H., Gonzalez, J., Zhang, H., and Stoica, I

    Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles, pages 611--626, 2023

    2023

  29. [37]

    Decoderlens: Layerwise interpretation of encoder-decoder transformers

    Langedijk, A., Mohebbi, H., Sarti, G., Zuidema, W., and Jumelet, J. Decoderlens: Layerwise interpretation of encoder-decoder transformers. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 4764--4780, 2024

    2024

  30. [38]

    Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems

    Lei, Y. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In The Thirty Sixth Annual Conference on Learning Theory, pages 191--227. PMLR, 2023

    2023

  31. [39]

    The winograd schema challenge

    Levesque, H., Davis, E., and Morgenstern, L. The winograd schema challenge. In Thirteenth international conference on the principles of knowledge representation and reasoning, 2012

    2012

  32. [40]

    A zeroth-order adaptive learning rate method to reduce cost of hyperparameter tuning for deep learning

    Li, Y., Ren, X., Zhao, F., and Yang, S. A zeroth-order adaptive learning rate method to reduce cost of hyperparameter tuning for deep learning. Applied Sciences, 11 0 (21): 0 10184, 2021

    2021

  33. [41]

    Scaling down to scale up: A guide to parameter-efficient fine-tuning

    Lialin, V., Deshpande, V., and Rumshisky, A. Scaling down to scale up: A guide to parameter-efficient fine-tuning. arXiv preprint arXiv:2303.15647, 2023

    2023 arXiv

  34. [42]

    General stability analysis for zeroth-order optimization algorithms

    Liu, X., Zhang, H., Gu, B., and Chen, H. General stability analysis for zeroth-order optimization algorithms. In The Twelfth International Conference on Learning Representations, 2024 a . URL https://openreview.net/forum?id=AfhNyr73Ma

    2024

  35. [43]

    Sparse mezo: Less parameters for better performance in zeroth-order llm fine-tuning

    Liu, Y., Zhu, Z., Gong, C., Cheng, M., Hsieh, C.-J., and You, Y. Sparse mezo: Less parameters for better performance in zeroth-order llm fine-tuning. arXiv preprint arXiv:2402.15751, 2024 b

    2024

  36. [44]

    Badam: A memory efficient full parameter training method for large language models

    Luo, Q., Yu, H., and Li, X. Badam: A memory efficient full parameter training method for large language models. arXiv preprint arXiv:2404.02827, 2024

    2024 arXiv

  37. [45]

    Magnus, J. R. et al. The moments of products of quadratic forms in normal variables. Univ., Instituut voor Actuariaat en Econometrie, 1978

    1978

  38. [46]

    D., Chen, D., and Arora, S

    Malladi, S., Gao, T., Nichani, E., Damian, A., Lee, J. D., Chen, D., and Arora, S. Fine-tuning language models with just forward passes. Advances in Neural Information Processing Systems, 36: 0 53038--53075, 2023

    2023

  39. [47]

    Milman, V. D. The heritage of P. L\'evy in geometrical functional analysis. In Colloque Paul L\'evy sur les processus stochastiques (22-26 juin 1987. \'Ecole Polytechnique, Palaiseau), number 157-158 in Ast\'erisque, pages 273--301. Soci\'et\'e math\'ematique de France, 1988. ...

    1987

  40. [48]

    and Spokoiny, V

    Nesterov, Y. and Spokoiny, V. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17 0 (2): 0 527--566, 2017

    2017

  41. [49]

    B., and Swami, A

    Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A. Practical black-box attacks against machine learning. In 2017 ACM Asia Conference on Computer and Communications Security, ASIA CCS 2017, pages 506--519. Association for Computing Machinery, Inc, 2017

    2017

  42. [50]

    The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size

    Papyan, V. The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv:1811.07062, 2018

    2018 arXiv

  43. [51]

    Traces of class/cross-class structure pervade deep learning spectra

    Papyan, V. Traces of class/cross-class structure pervade deep learning spectra. Journal of Machine Learning Research, 21 0 (252): 0 1--64, 2020

    2020

  44. [52]

    Y., Jung, Y., Kundu, S., Kim, K., and Yang, E

    Park, S., Yun, J., Kim, S.-Y., Yang, J. Y., Jung, Y., Kundu, S., Kim, K., and Yang, E. Me ZO -a\ \ 3\ \ dam: Memory-efficient zeroth-order adam with adaptivity adjustments for fine-tuning LLM s, 2024. URL https://openreview.net/forum?id=OBIuFjZzmp

    2024

  45. [53]

    Pilehvar, M. T. and Camacho-Collados, J. Wic: the word-in-context dataset for evaluating context-sensitive meaning representations. arXiv preprint arXiv:1808.09121, 2018

    2018 arXiv

  46. [54]

    Know what you don’t know: Unanswerable questions for squad

    Rajpurkar, P., Jia, R., and Liang, P. Know what you don’t know: Unanswerable questions for squad. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 784--789, 2018

    2018

  47. [55]

    An optimal structured zeroth-order algorithm for non-smooth optimization

    Rando, M., Molinari, C., Rosasco, L., and Villa, S. An optimal structured zeroth-order algorithm for non-smooth optimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023 a . URL https://openreview.net/forum?id=SfdkS6tt81

    2023

  48. [56]

    An optimal structured zeroth-order algorithm for non-smooth optimization

    Rando, M., Molinari, C., Rosasco, L., and Villa, S. An optimal structured zeroth-order algorithm for non-smooth optimization. Advances in Neural Information Processing Systems, 36: 0 36738--36767, 2023 b

    2023

  49. [57]

    J., Kale, S., and Kumar, S

    Reddi, S. J., Kale, S., and Kumar, S. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL https://openreview.net/forum?id=ryQu7f-RZ

    2018

  50. [58]

    and Monro, S

    Robbins, H. and Monro, S. A Stochastic Approximation Method . The Annals of Mathematical Statistics, 22 0 (3): 0 400 -- 407, 1951. doi:10.1214/aoms/1177729586. URL https://doi.org/10.1214/aoms/1177729586

    1951

  51. [59]

    A., and Gordon, A

    Roemmele, M., Bejan, C. A., and Gordon, A. S. Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In 2011 AAAI spring symposium series, 2011

    2011

  52. [60]

    U., Dauphin, Y., and Bottou, L

    Sagun, L., Evci, U., Guney, V. U., Dauphin, Y., and Bottou, L. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04454, 2017

    2017 arXiv

  53. [61]

    On the complexity of bandit and derivative-free stochastic convex optimization

    Shamir, O. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory, pages 3--24. PMLR, 2013

    2013

  54. [62]

    R., Zhao, D., Patel, N., Naghiyev, J., LeCun, Y., and Shwartz-Ziv, R

    Skean, O., Arefin, M. R., Zhao, D., Patel, N., Naghiyev, J., LeCun, Y., and Shwartz-Ziv, R. Layer by layer: Uncovering hidden representations in language models. arXiv preprint arXiv:2502.02013, 2025

    2025 arXiv

  55. [63]

    D., Ng, A., and Potts, C

    Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C. D., Ng, A., and Potts, C. Recursive deep models for semantic compositionality over a sentiment treebank. In Yarowsky, D., Baldwin, T., Korhonen, A., Livescu, K., and Bethard, S., editors, Proceedings of the 2013 Confer...

    2013

  56. [64]

    Spall, J. C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37 0 (3): 0 332--341, 1992

    1992

  57. [65]

    and Ye, Y

    Sun, R. and Ye, Y. Worst-case complexity of cyclic coordinate descent: O (n\^ 2) o (n 2) gap with randomized version. Mathematical Programming, 185: 0 487--520, 2021

    2021

  58. [66]

    Llama: Open and efficient foundation language models

    Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozi \`e re, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023

    2023 arXiv

  59. [67]

    Zarts: On zero-order optimization for neural architecture search

    Wang, X., Guo, W., Su, J., Yang, X., and Yan, J. Zarts: On zero-order optimization for neural architecture search. Advances in Neural Information Processing Systems, 35: 0 12868--12880, 2022

    2022

  60. [68]

    The evaluation of the collision matrix

    Wick, G.-C. The evaluation of the collision matrix. Physical review, 80 0 (2): 0 268, 1950

    1950

  61. [69]

    Wright, F. T. A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric. The Annals of Probability, 1 0 (6): 0 1068--1070, 1973

    1973

  62. [70]

    Dissecting hessian: Understanding common structure of hessian in neural networks

    Wu, Y., Zhu, X., Wu, C., Wang, A., and Ge, R. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020

    2010 arXiv

  63. [71]

    Subzero: Random subspace zeroth-order optimization for memory-efficient llm fine-tuning

    Yu, Z., Zhou, P., Wang, S., Li, J., and Huang, H. Subzero: Random subspace zeroth-order optimization for memory-efficient llm fine-tuning. arXiv preprint arXiv:2410.08989, 2024

    2024 arXiv

  64. [72]

    Adablock: Sgd with practical block diagonal matrix adaptation for deep learning

    Yun, J., Lozano, A., and Yang, E. Adablock: Sgd with practical block diagonal matrix adaptation for deep learning. In International Conference on Artificial Intelligence and Statistics, pages 2574--2606. PMLR, 2022

    2022

  65. [73]

    and Pilanci, M

    Zhang, F. and Pilanci, M. R iemannian preconditioned L o RA for fine-tuning foundation models. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F., editors, Proceedings of the 41st International Conference on Machine Learning,...

    2024

  66. [74]

    Complexity of finding stationary points of nonconvex nonsmooth functions

    Zhang, J., Lin, H., Jegelka, S., Sra, S., and Jadbabaie, A. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pages 11173--11182. PMLR, 2020

    2020

  67. [75]

    When foresight pruning meets zeroth-order optimization: Efficient federated learning for low-memory devices

    Zhang, P., Liu, Y., Zhou, Y., Du, X., Wei, X., Wang, T., and Chen, M. When foresight pruning meets zeroth-order optimization: Efficient federated learning for low-memory devices. arXiv preprint arXiv:2405.04765, 2024 a

    2024 arXiv

  68. [76]

    Record: Bridging the gap between human and machine commonsense reading comprehension

    Zhang, S., Liu, X., Liu, J., Gao, J., Duh, K., and Van Durme, B. Record: Bridging the gap between human and machine commonsense reading comprehension. arXiv preprint arXiv:1810.12885, 2018

    2018 arXiv

  69. [77]

    V., et al

    Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M., Li, X., Lin, X. V., et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022 a

    2022 arXiv

  70. [78]

    How to robustify black-box ML models? a zeroth-order optimization perspective

    Zhang, Y., Yao, Y., Jia, J., Yi, J., Hong, M., Chang, S., and Liu, S. How to robustify black-box ML models? a zeroth-order optimization perspective. In International Conference on Learning Representations, 2022 b . URL https://openreview.net/forum?id=W9G_ImpHlQd

    2022

  71. [79]

    Why transformers need adam: A hessian perspective

    Zhang, Y., Chen, C., Ding, T., Li, Z., Sun, R., and Luo, Z.-Q. Why transformers need adam: A hessian perspective. arXiv preprint arXiv:2402.16788, 2024 b

    2024 arXiv

  72. [80]

    Adam-mini: Use fewer learning rates to gain more

    Zhang, Y., Chen, C., Li, Z., Ding, T., Wu, C., Ye, Y., Luo, Z.-Q., and Sun, R. Adam-mini: Use fewer learning rates to gain more. arXiv preprint arXiv:2406.16793, 2024 c

    2024 arXiv

  73. [81]

    Investigating layer importance in large language models

    Zhang, Y., Dong, Y., and Kawaguchi, K. Investigating layer importance in large language models. In Proceedings of the 7th BlackboxNLP Workshop: Analyzing and Interpreting Neural Networks for NLP, pages 469--479, 2024 d

    2024

  74. [82]

    D., Yin, W., Hong, M., Wang, Z., Liu, S., and Chen, T

    Zhang, Y., Li, P., Hong, J., Li, J., Zhang, Y., Zheng, W., Chen, P.-Y., Lee, J. D., Yin, W., Hong, M., Wang, Z., Liu, S., and Chen, T. Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: A benchmark. In Salakhutdinov, R., Kolter, Z., Heller, K., Weller, ...

    2024

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.