LOZO+: Provably Efficient Zeroth-Order Fine-Tuning via Greedy Low-Rank Subspace Selection

Jinjie Fang, Chengxun Jin, Tianxing Man, Yi Chang, Bin Gu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:29201-29221, 2026.

Abstract

Zeroth-order (ZO) optimization offers a more memory-efficient alternative to first-order methods for fine-tuning large language models (LLMs). Recent ZO methods, exemplified by LOZO, estimate gradients within low-rank subspaces to align with the low-rank structure of LLM gradients. However, these methods rely on randomly generated subspaces of a fixed rank, which provides no guarantee of alignment with the actual dominant subspaces of the gradients; essentially, they remain ZO gradient descent with stochastic subspace sampling. To more effectively exploit the low-rank nature of LLM gradients, we propose LOZO+, an efficient ZO fine-tuning algorithm for LLMs that incorporates greedy Low-Rank subspace selection. Specifically, LOZO+ leverages loss-based feedback to assess alignment between candidate directions and the dominant low-rank gradient subspaces, and employs an adaptive thresholding criterion to retain only directions yielding substantial gradient descent, thereby steering ZO optimization toward more effective convergence. Importantly, we establish a theoretical framework that characterizes the convergence behavior of LOZO+, formally prove its superiority over existing methods. Extensive experiments demonstrate that LOZO+ consistently outperforms existing ZO methods and achieves performance competitive with FO algorithm, while retaining the memory efficiency inherent to ZO optimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-fang26k, title = {{LOZO}+: Provably Efficient Zeroth-Order Fine-Tuning via Greedy Low-Rank Subspace Selection}, author = {Fang, Jinjie and Jin, Chengxun and Man, Tianxing and Chang, Yi and Gu, Bin}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {29201--29221}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/fang26k/fang26k.pdf}, url = {https://proceedings.mlr.press/v306/fang26k.html}, abstract = {Zeroth-order (ZO) optimization offers a more memory-efficient alternative to first-order methods for fine-tuning large language models (LLMs). Recent ZO methods, exemplified by LOZO, estimate gradients within low-rank subspaces to align with the low-rank structure of LLM gradients. However, these methods rely on randomly generated subspaces of a fixed rank, which provides no guarantee of alignment with the actual dominant subspaces of the gradients; essentially, they remain ZO gradient descent with stochastic subspace sampling. To more effectively exploit the low-rank nature of LLM gradients, we propose LOZO+, an efficient ZO fine-tuning algorithm for LLMs that incorporates greedy Low-Rank subspace selection. Specifically, LOZO+ leverages loss-based feedback to assess alignment between candidate directions and the dominant low-rank gradient subspaces, and employs an adaptive thresholding criterion to retain only directions yielding substantial gradient descent, thereby steering ZO optimization toward more effective convergence. Importantly, we establish a theoretical framework that characterizes the convergence behavior of LOZO+, formally prove its superiority over existing methods. Extensive experiments demonstrate that LOZO+ consistently outperforms existing ZO methods and achieves performance competitive with FO algorithm, while retaining the memory efficiency inherent to ZO optimization.} }
Endnote
%0 Conference Paper %T LOZO+: Provably Efficient Zeroth-Order Fine-Tuning via Greedy Low-Rank Subspace Selection %A Jinjie Fang %A Chengxun Jin %A Tianxing Man %A Yi Chang %A Bin Gu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-fang26k %I PMLR %P 29201--29221 %U https://proceedings.mlr.press/v306/fang26k.html %V 306 %X Zeroth-order (ZO) optimization offers a more memory-efficient alternative to first-order methods for fine-tuning large language models (LLMs). Recent ZO methods, exemplified by LOZO, estimate gradients within low-rank subspaces to align with the low-rank structure of LLM gradients. However, these methods rely on randomly generated subspaces of a fixed rank, which provides no guarantee of alignment with the actual dominant subspaces of the gradients; essentially, they remain ZO gradient descent with stochastic subspace sampling. To more effectively exploit the low-rank nature of LLM gradients, we propose LOZO+, an efficient ZO fine-tuning algorithm for LLMs that incorporates greedy Low-Rank subspace selection. Specifically, LOZO+ leverages loss-based feedback to assess alignment between candidate directions and the dominant low-rank gradient subspaces, and employs an adaptive thresholding criterion to retain only directions yielding substantial gradient descent, thereby steering ZO optimization toward more effective convergence. Importantly, we establish a theoretical framework that characterizes the convergence behavior of LOZO+, formally prove its superiority over existing methods. Extensive experiments demonstrate that LOZO+ consistently outperforms existing ZO methods and achieves performance competitive with FO algorithm, while retaining the memory efficiency inherent to ZO optimization.
APA
Fang, J., Jin, C., Man, T., Chang, Y. & Gu, B.. (2026). LOZO+: Provably Efficient Zeroth-Order Fine-Tuning via Greedy Low-Rank Subspace Selection. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:29201-29221 Available from https://proceedings.mlr.press/v306/fang26k.html.

Related Material