通过维度窥探降低离散优化梯度方差，提升收敛速度。
Dimensional Peeking for Low-Variance Gradients in Zeroth-Order Discrete Optimization via Simulation
- 将采样粒度从标量升至同控制流类值，提升每次模拟信息量
- 在高维输入下方差降低最多达7.9倍，优化进展优于三种元启发法
- 适用于离散非凸仿真优化，尤其适合无法求导的场景
基于梯度的优化方法常用于高维空间中寻找局部最优解。当无法直接计算导数时，可通过随机估计器获得近似梯度。然而，这类估计器依赖扰动采样目标函数，引入的方差会导致收敛缓慢。本文提出维度窥探（Dimensional Peeking），一种用于仿真驱动的离散优化中的梯度估计方差减少方法。通过将采样粒度从标量值提升至遵循相同控制流路径的值类别，提升了每次模拟评估所获取的信息量。从已有的平滑梯度估计器推导出该方法不引入偏差。我们通过自定义数值数据类型，在C++程序中透明实现维度窥探。在三个高维输入的仿真优化问题中，方差降低最高达7.9倍。与三种元启发式算法相比，优化进展显著提升，增强了零阶优化在离散与非凸仿真场景下的竞争力。
原文摘要 · Abstract (English)
Gradient-based optimization methods are commonly used to identify local optima in high-dimensional spaces. When derivatives cannot be evaluated directly, stochastic estimators can provide approximate gradients. However, these estimators' perturbation-based sampling of the objective function introduces variance that can lead to slow convergence. In this paper, we present dimensional peeking, a variance reduction method for gradient estimation in discrete optimization via simulation. By lifting the sampling granularity from scalar values to classes of values that follow the same control flow path, we increase the information gathered per simulation evaluation. Our derivation from an established smoothed gradient estimator shows that the method does not introduce any bias. We present an implementation via a custom numerical data type to transparently carry out dimensional peeking over C++ programs. Variance reductions by factors of up to 7.9 are observed for three simulation-based optimization problems with high-dimensional input. The optimization progress compared to three meta-heuristics shows that dimensional peeking increases the competitiveness of zeroth-order optimization for discrete and non-convex simulations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。