Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization

Yicheng Lang; Changsheng Wang; Yihua Zhang; Mingyi Hong; Zheng Zhang; Wotao Yin; Sijia Liu

cs.LGFeb 19, 2026

Powering Up Zeroth-Order Training via Subspace Gradient Orthogonalization

Authors: Yicheng Lang, Changsheng Wang, Yihua Zhang, Mingyi Hong, Zheng Zhang, Wotao Yin, Sijia Liu

Organizations: Michigan State University · University of Minnesota · University of California, Santa Barbara · DAMO Academy, Alibaba Group US ·

Abstract

Zeroth-order (ZO) optimization provides a gradient-free alternative to first-order (FO) methods by estimating gradients via finite differences of function evaluations, and has recently emerged as a memory-efficient paradigm for fine-tuning large-scale models by avoiding backpropagation. However, ZO optimization has a fundamental tension between accuracy and query efficiency. In this work, we show that ZO optimization can be substantially improved by unifying two complementary principles: (i) a projection-based subspace view that reduces gradient estimation variance by exploiting the intrinsic low-rank structure of model updates, and (ii) Muon-style spectral optimization that applies gradient orthogonalization to extract informative spectral structure from noisy ZO gradients. These findings form a unified framework of subspace gradient orthogonalization, which we instantiate in a new method, ZO-Muon, admitting a natural interpretation as a low-rank Muon optimizer in the ZO setting. Extensive experiments on large language models (LLMs) and vision transformers (ViTs) demonstrate that ZO-Muon significantly accelerates convergence and achieves a win-win improvement in accuracy and query/runtime efficiency. Notably, compared to the popular MeZO baseline, ZO-Muon requires only 24.7% of the queries to reach the same SST-2 performance for LLM fine-tuning, and improves accuracy by 25.1% on ViT-B fine-tuning on CIFAR-100.

Figures & tables

Panel of Figure 1 — Figure 1: ZO-Muon achieves faster convergence and better fine-tuning accuracy than the SOTA ZO baselines MeZO ( Malladi et al., 2023 ) and LOZO ( Chen et al., 2025a ) against runtime. (a) OPT-1.3B fine-tuned on the RTE task: training loss ( left ) and test accuracy ( right ) versus runtime, with the cumulative query count indicated by the color bar in the right subplot. (b) ViT-B fine-tuned on CIFAR-10 ( left ) and CIFAR-100 ( right ), shown in the same format as in (a, right).

Figure 2: ZO-Muon yields lower runtime and fewer function queries than all baselines (under comparable GPU memory usage), when reaching the target fine-tuning accuracies: (a)

0.90

on SST-2 and (b)

0.93

on CIFAR-10. Baselines include MeZO ( Malladi et al., 2023 ) , SparseMeZO (S-MeZO) ( Liu et al., 2025b ) , HiZOO ( Zhao et al., 2025b ) , and LOZO ( Chen et al., 2025a ) .

Figure 3: The necessity and advantages of Subspace RGE, illustrated by fine-tuning OPT-1.3B on SST-2: (a) The low-rank structure of model components during FO training with Adam across steps; (b) Performance comparison of Subspace RGE–based MeZO ( i.e. , Subspace-MeZO) with the SOTA baselines SparseMeZO ( i.e. , S-MeZO) and MeZO; And (c) accuracy vs. runtime.

Figure 4: Training (a) and testing (b) performance comparison of the proposed Subspace RGE–based MeZO ( i.e. , Subspace-MeZO) with existing low-rank perturbation–based ZO baselines, LOZO ( Chen et al., 2025a ) and SubZero ( Yu et al., 2025 ) , for fine-tuning OPT-13B on SQuAD whose performance is measured by F1 (%).

Figure 5: Demonstration of the ineffectiveness of ZO-Muon-V0 vs. MeZO and the effectiveness of ZO-Muon through fine-tuning OPT-13B on SST-2.

Panel of Figure 6 — Figure 6: Comparison of ZO-Muon and Subspace-MeZO for fine-tuning OPT-1.3B on SST-2 and SQuAD with $r\in\{16,64,256\}$ . (Left) Fine-tuning accuracy (shown by cell color and numeric value) for different $r$ . ZO-Muon consistently outperforms Subspace-MeZO, with $r=64$ achieving the best performance. (Right) Training loss curves of ZO-Muon under different projection ranks for fine-tuning OPT-1.3B on SQuAD.

Method	LLM Fine-tuning						ViT Fine-tuning
Method	SST-2	RTE	CB	BoolQ	WiC	SQuAD	CIFAR-10	CIFAR-100
	LlaMA3-8B						ViT-B
${\color[rgb]{1,0.5,0}\bullet}$ Adam	96.0	92.0	92.0	86.6	72.6	90.4	98.9	91.2
${\color[rgb]{1,0.5,0}\bullet}$ LoRA	95.0	80.9	73.2	86.4	70.7	89.4	98.3	86.4
MeZO	92.7	74.4	69.6	76.7	57.8	86.7	93.5	64.5
S-MeZO	92.1	69.7	69.6	80.5	56.9	87.5	93.7	64.3

Table 1: ZO-Muon outperforms the ZO baselines by a non-negligible margin, demonstrated by fine-tuning LLMs (LlaMA3-8B and OPT-13B) on SuperGLUE benchmark and fine-tuning ViTs (ViT-B and ViT-L) on CIFAR datasets. FO methods (marked by

{\color[rgb]{1,0.5,0}\bullet}

) include Adam and LoRA. The best ZO fine-tuning result for each task is highlighted in bold .

Method	Steps $\downarrow$	Queries $\downarrow$	Runtime $\downarrow$	Memory $\downarrow$	GPU s $\downarrow$	Accuracy $\uparrow$
${\color[rgb]{1,0.5,0}\bullet}$ Adam	625	625	10 min	$4\times 63.7$ GB	$4\times\text{A100}$	95.3
${\color[rgb]{1,0.5,0}\bullet}$ LoRA	625	625	6 min	$2\times 52.7$ GB	$2\times\text{A100}$	94.8
MeZO	20k	40k	3 h 37 min	28.2 GB	$1\times\text{A100}$	91.4
S-MeZO	20k	40k	6 h 46 min	30.1 GB	$1\times\text{A100}$	90.4
HiZOO	13.3k	40k	4 h 46 min	55.4 GB	$1\times\text{A100}$	92.1
LOZO	20k	40k	3 h 19 min	27.6 GB	$1\times\text{A100}$	91.7

Table 2: Efficiency comparison in terms of the number of optimization steps, number of queries, runtime, memory cost, GPU usage, and accuracy for fine-tuning OPT-13B on SST-2. Note that the total query budget is fixed to 40k for all ZO methods.

Figure 7: Runtime and accuracy comparison of ZO-Muon using NS and SVD for fine-tuning OPT-1.3B/13B on SST-2 under the same query budget (5,000).

Panel of Figure 8 — Figure 8: Accuracy and GPU memory comparison under varying batch sizes. ZO-Muon vs. baselines on ViT-B fine-tuning for CIFAR-100 with a fixed query budget.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure A1: Fine-tune accuracy and runtime of full space gradient orthogonalization methods JAGUAR-Muon and ZO-Muon-V0 compared to MeZO and ZO-Muon, demonstrated by fine-tuning OPT-1.3B on SST-2.

Panel of Figure 12 — Figure A2: Fine-tuning accuracy vs. query cost for (a) ZO-Muon and (b) Subspace-MeZO when fine-tuning ViT-B on CIFAR-100, with marker color indicating the used iteration number. The per-iteration query budget is set to $N_{q}\in\{1,4,16\}$ . (a) ZO-Muon benefits from increasing $N_{q}$ , with a notable performance gain when moving from $N_{q}=1$ to $N_{q}=4$ . (b) Under the same setting, Subspace-MeZO exhibits a multi-query paradox, where performance degrades when $N_{q}>1$ .

Methods	Hyperparameters	Values
Methods	Hyperparameters	LLM	ViT
MeZO	Learning rate	$\{1\text{e}-7,1\text{e}-6\}$ or $\{1\text{e}-7,5\text{e}-7,1\text{e}-6\}$ for SQuAD	$\{1\text{e}-5,1\text{e}-4\}$
MeZO	Train steps	20k	20k
S-MeZO	Learning rate	$\{1\text{e}-7,1\text{e}-6\}$ or $\{1\text{e}-7,5\text{e}-7,1\text{e}-6\}$ for SQuAD	$\{1\text{e}-5,1\text{e}-4\}$
	Sparsity	$0.8$	$0.8$
	Train steps	20k	20k

Appendix

Table A1: Hyperparameter settings of ZO and FO methods used for fine-tuning LLMs and ViTs.

Panel of Figure 14 — Figure A3: ZO-Muon achieves faster convergence rate compared to MeZO and LOZO, demonstrated through fine-tuning OPT-13B on SST-2, SQuAD, RTE and BoolQ.

Method	Gemma2-2B Fine-tuning
Method	SST-2	RTE	CB	BoolQ	WiC	SQuAD
${\color[rgb]{1,0.5,0}\bullet}$ Adam	94.0	84.0	84.0	90.0	72.0	89.4
${\color[rgb]{1,0.5,0}\bullet}$ LoRA	91.6	57.8	55.4	75.2	56.1	86.9
MeZO	91.7	53.0	60.7	66.1	57.1	74.1
S-MeZO	92.7	53.8	53.6	63.9	55.8	76.1
HiZOO	92.1	53.1	60.7	66.6	55.2	73.4

Appendix

Table A2: Performance of ZO-Muon and baselines on Gemma2-2B under the same settings as Tab. 1 .

Panel of Figure 16 — Figure A4: Performance of ZO-Muon with different projection matrix resampling interval $v$ , demonstrated by (a) fine-tuning OPT-1.3B on SST-2 and (b) fine-tuning ViT-B on CIFAR-100.

Method	Sampling Strategy	LlaMA3-8B Fine-tuning						ViT-B Fine-tuning
		SST-2		RTE		SQuAD		CIFAR-10		CIFAR-100
		Acc. (%) $\uparrow$	Mem (MiB) $\downarrow$	Acc. (%) $\uparrow$	Mem (MiB) $\downarrow$	F1 (%) $\uparrow$	Mem (MiB) $\downarrow$	Acc. (%) $\uparrow$	Mem (MiB) $\downarrow$	Acc. (%) $\uparrow$	Mem (MiB) $\downarrow$
Subspace-MeZO	Random	92.3	19058	68.6	28242	84.5	32102	94.2	1634	58.2	4086
Subspace-MeZO	Sketching	92.3	34814	67.5	38874	87.2	44734	81.2	1898	29.1	4088
ZO-Muon	Random	94.3	19176	81.2	27224	88.2	30718	94.9	1686	72.6	4410
ZO-Muon	Sketching	93.8	35268	78.3	44304	88.3	45248	95.3	1950	59.8	4412

Appendix

Table A3: Performance (evaluated by accuracy and F1) and GPU memory (short for “Mem”) of Subspace-MeZO and ZO-Muon with different projection matrix sampling strategies.

Panel of Figure 18 — Figure A5: Fine-tuning accuracy and runtime of ZO-Muon using SVD vs. NS for gradient orthogonalization under the same query budget. Runtime is measured in seconds (s).

Panel of Figure 19 — Figure A6: Fine-tuning accuracy and GPU memory comparison under varying batch sizes. ZO-Muon versus baselines on LlaMA3-8B fine-tuning for RTE with the same number of iterations.

Zeroth-Order Optimization

Zeroth-order optimization uses function values or comparisons, rather than gradients, to optimize objectives when differentiation is unavailable or costly.

See all 86 papers

Accelerating Zeroth-Order Spectral Optimization with Partial Orthogonalization from Power Iteration
May 9, 2026Jiahe Chen, Ziye MaZeroth-Order Optimization LLM Fine-Tuning
Department of Computer Science City University of Hong Kong
SubZero+: Memory-Efficient Adaptive Zeroth-Order LLM Fine-Tuning in Random Subspaces
Aug 16, 2026Ziming Yu, Shuyao Xiao, Xingyu Zhao +6Memory-Efficient Fine-Tuning Zeroth-Order Optimization
Beijing Normal University · Singapore Management University · Xiaomi Inc. +2
GRZO: Group-Relative Zeroth-Order Optimization for Large Language Model Fine-Tuning
Jun 1, 2026Liyan Tan, Yequan Zhao, Yifan Yang +3Zeroth-Order Optimization Memory-Efficient Training
University of California, Santa Barbara

May 9, 2026J/K move · Enter open · S save

Accelerating Zeroth-Order Spectral Optimization with Partial Orthogonalization from Power Iteration

Jiahe Chen, Ziye Ma

Department of Computer Science City University of Hong Kong

Zeroth-Order Optimization LLM Fine-Tuning Muon Optimizer Spectral Methods Spectral Optimization

Open paper AskPDF arXiv

Zeroth-order (ZO) optimization has become increasingly popular and important in fine-tuning large language models (LLMs), especially on edge devices due to its ability to adjust the model to local data without the need for memory-intensive back-propagation. Recent works try to reduce ZO variance through low-dimensional subspace search, but subspace restriction alone leaves key optimization geometry under-exploited, motivating additional acceleration. In this work, we focus on the hidden layer training problem in which spectral optimizers like Muon outperform AdamW due to its ability to exploit weak spectral directions by orthogonalization. However, we have discovered that unlike in the first-order setting, full orthogonalization works poorly in the ZO setting since the gradient estimates are highly noisy and unreliable. To address this issue, we propose applying partial spectral orthogonalization to accelerate ZO optimization. To do so, we replace the iconic Newton-Schulz procedure in Muon with the faster, more concentrated power-iteration method so that it only amplifies dominant spectral directions. Furthermore, to improve the efficiency and generalization of the algorithm, we adopted a streaming variant of power-iteration that requires low variance in gradients, which was achieved through constraining our search inside a subspace obtained through the projection of momentum, echoing recent advances. Experiments on LLM fine-tuning show that our method can achieve from 1.5x to 4x the convergence speed of ZO-Muon, the current SOTA algorithm, across SuperGlue datasets in the OPT-13B model. Across different models, we also reach competitive final accuracies with less time in most cases compared with strong ZO baselines such as MeZO, LOZO and ZO-Muon. Code is available at https://github.com/MOFA-LAB/ZO-MOPI.git.

Abstract

Zeroth-Order Optimization

Explore similar work

Accelerating Zeroth-Order Spectral Optimization with Partial Orthogonalization from Power Iteration

SubZero+: Memory-Efficient Adaptive Zeroth-Order LLM Fine-Tuning in Random Subspaces

GRZO: Group-Relative Zeroth-Order Optimization for Large Language Model Fine-Tuning