arXiv:2505.19720math.OCcs.LG2025-05被引 1

结构化方向提升有限差分优化效率,精度更高且成本可控。

A Structured Tour of Optimization with Finite Differences

  • 用正交等结构化方向替代随机方向,提升梯度逼近质量。
  • 在合成任务与对抗扰动中,性能显著优于无结构方法。
  • 计算开销接近无结构方法,适合高维场景使用。

有限差分方法广泛用于梯度信息不可得或计算昂贵的零阶优化场景。这类方法通过沿一组随机方向进行函数评估来近似梯度,模拟一阶优化策略。理论上,近期研究指出,在所选方向上施加结构(如正交性)可获得与无结构随机方向相当的收敛速率。然而,实证上,结构化方向常引入额外计算开销,限制其在高维设置中的应用。本文系统考察了结构化方向选择对有限差分方法的影响,综述并扩展多种构造结构化方向矩阵的策略,并在计算成本、梯度逼近质量及收敛行为方面与无结构方法进行对比。评估涵盖合成任务与真实应用(如对抗扰动)。结果表明,结构化方向可在计算成本与无结构方法相当的前提下,显著提升梯度估计精度与优化性能。

原文摘要 · Abstract (English)

Finite-difference methods are widely used for zeroth-order optimization in settings where gradient information is unavailable or expensive to compute. These procedures mimic first-order strategies by approximating gradients through function evaluations along a set of random directions. From a theoretical perspective, recent studies indicate that imposing structure (such as orthogonality) on the chosen directions allows for the derivation of convergence rates comparable to those achieved with unstructured random directions (i.e., directions sampled independently from a distribution). Empirically, although structured directions are expected to enhance performance, they often introduce additional computational costs, which can limit their applicability in high-dimensional settings. In this work, we examine the impact of structured direction selection in finite-difference methods. We review and extend several strategies for constructing structured direction matrices and compare them with unstructured approaches in terms of computational cost, gradient approximation quality, and convergence behavior. Our evaluation spans both synthetic tasks and real-world applications such as adversarial perturbation. The results demonstrate that structured directions can be generated with computational costs comparable to unstructured ones while significantly improving gradient estimation accuracy and optimization performance.

优化有限差分梯度估计

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。