提出新理论解释零阶优化加速机制,实测提速近3倍。
Elucidating Subspace Perturbation in Zeroth-Order Optimization: Theory and Practice at Scale
- 通过子空间对齐理论分析梯度噪声,揭示加速原理
- 新方法在OPT-13B上实现2.77倍的时钟时间提速
- 适合大规模模型微调且对硬件要求低的场景
零阶(ZO)优化为黑盒优化和大语言模型微调提供了有前景的替代方案,但常因高方差随机梯度估计导致收敛缓慢。尽管已尝试使用稀疏性、低秩等子空间扰动来缓解此问题,其有效性仍不明确。本文构建了一个统一的理论框架,分析了在子空间扰动下零阶优化的收敛与泛化特性。研究表明,高维是主要瓶颈,并提出‘子空间对齐’概念,解释了为何此类扰动可降低梯度噪声并加速收敛。分析还表明,多种子空间扰动具有相似收敛速率,因此在实际算法设计中应更关注可行性。基于此,我们提出一种基于块坐标下降的高效零阶方法(MeZO-BCD),仅每步更新部分参数。大量实验显示,MeZO-BCD 在 OPT-13B 上相比 MeZO 实现高达 ×2.77 的时钟时间加速,同时保持相近的迭代复杂度与微调性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。