arXiv:2411.00112cs.LGmath.OC2024-11被引 3

用批量有限差分法优化,比传统方法更快更准。

Derivative-Free Optimization via Finite Difference Approximation: An Experimental Study

  • 用多组样本批量计算梯度,提升估计精度
  • 在低维和高维场景中均优于经典KW与SPSA算法
  • 适合需要高精度、可接受更多采样的优化任务

无导数优化(DFO)在仅有噪声函数值可通过查询获取的复杂优化问题中至关重要。其中,基于有限差分(FD)的DFO方法表现突出。经典方法如Kiefer-Wolfowitz(KW)和同时扰动随机逼近(SPSA)每轮仅需两个样本估算梯度,以节省样本,但导致梯度估计不准确,需采用递减步长保证收敛,常致优化缓慢。相反,基于批量样本的FD梯度估计器能更精确地近似梯度,使基于梯度下降的算法在每轮迭代中取得更优结果,但需更多样本且迭代次数受限。本文系统比较了这些方法,探究梯度估计精度与迭代次数间的根本权衡。在低维与高维场景的大量实验中发现:当使用高效的批量FD估计器时,其对应的梯度下降算法在测试条件下通常优于传统的KW和SPSA算法。

原文摘要 · Abstract (English)

Derivative-free optimization (DFO) is vital in solving complex optimization problems where only noisy function evaluations are available through an oracle. Within this domain, DFO via finite difference (FD) approximation has emerged as a powerful method. Two classical approaches are the Kiefer-Wolfowitz (KW) and simultaneous perturbation stochastic approximation (SPSA) algorithms, which estimate gradients using just two samples in each iteration to conserve samples. However, this approach yields imprecise gradient estimators, necessitating diminishing step sizes to ensure convergence, often resulting in slow optimization progress. In contrast, FD estimators constructed from batch samples approximate gradients more accurately. While gradient descent algorithms using batch-based FD estimators achieve more precise results in each iteration, they require more samples and permit fewer iterations. This raises a fundamental question: which approach is more effective -- KW-style methods or DFO with batch-based FD estimators? This paper conducts a comprehensive experimental comparison among these approaches, examining the fundamental trade-off between gradient estimation accuracy and iteration steps. Through extensive experiments in both low-dimensional and high-dimensional settings, we demonstrate a surprising finding: when an efficient batch-based FD estimator is applied, its corresponding gradient descent algorithm generally shows better performance compared to classical KW and SPSA algorithms in our tested scenarios.

无导数优化有限差分批量估计梯度下降

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