paper-with-me

홈 › Papers

Unraveling Zeroth-Order Optimization through the Lens of Low-Dimensional Structured Perturbations

2025-01-31 · Sihwan Park, Jihun Yun, Sungyub Kim, Souvik Kundu, Eunho Yang

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 suffer from slow convergence due to high-variance stochastic gradient estimators. While structured perturbations, such as sparsity and low-rank constraints, have been explored to mitigate these issues, their effectiveness remains highly under-explored. In this work, we develop a unified theoretical framework that analyzes both the convergence and generalization properties of ZO optimization under structured perturbations. We show that high dimensionality is the primary bottleneck and introduce the notions of \textit{stable rank} and \textit{effective overlap} to explain how structured perturbations reduce gradient noise and accelerate convergence. Using the uniform stability under our framework, we then provide the first theoretical justification for why these perturbations enhance generalization. Additionally, through empirical analysis, we identify that \textbf{block coordinate descent} (BCD) to be an effective structured perturbation method. Extensive experiments show that, compared to existing alternatives, memory-efficient ZO (MeZO) with BCD (\textit{MeZO-BCD}) can provide improved converge with a faster wall-clock time/iteration by up to $\times\textbf{2.09}$ while yielding similar or better accuracy.

📄 PDF Abstract BibTeX arXiv:2501.19099

Code (0)

등록된 구현이 없습니다.

Tasks

Large Language Model

Similar Papers 제목 키워드 기반

How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspective

2022-03-27 · ICLR 2022 4 · Yimeng Zhang, Yuguang Yao, Jinghan Jia, JinFeng Yi 외

The lack of adversarial robustness has been recognized as an important issue for state-of-the-art machine learning (ML) models, e.g., deep neural networks (DNNs). Thereby, robustifying ML models against adversarial attac…

Adversarial Robustnessimage-classificationImage ClassificationImage Reconstruction

Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens

2026-05-29 · Junbin Qiu, Zhaowei Hong, Renzhe Xu, Yao Shu arxiv

Accurate Zeroth-Order (ZO) Hessian estimation is a cornerstone of derivative-free methods, essential for tasks such as bilevel optimization, Bayesian inference, and uncertainty quantification. However, obtaining a comple…

Bilevel OptimizationBayesian Inference

Distributed Zeroth-Order Optimization: Convergence Rates That Match Centralized Counterpart

2021-09-29 · Deming Yuan, Lei Wang, Alexandre Proutiere, Guodong Shi

Zeroth-order optimization has become increasingly important in complex optimization and machine learning when cost functions are impossible to be described in closed analytical forms. The key idea of zeroth-order o…

Zeroth-Order Optimization is Secretly Single-Step Policy Optimization

2025-06-17 · Junbin Qiu, Zhengpeng Xie, Xiangda Yan, Yongjie Yang 외

Zeroth-Order Optimization (ZOO) provides powerful tools for optimizing functions where explicit gradients are unavailable or expensive to compute. However, the underlying mechanisms of popular ZOO methods, particularly t…

Reinforcement Learning (RL)

Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction

2016-12-05 · Bin Gu, Zhouyuan Huo, Heng Huang

Zeroth-order (derivative-free) optimization attracts a lot of attention in machine learning, because explicit gradient calculations may be computationally expensive or infeasible. To handle large scale problems both in v…