用子空间方法低成本估算海森矩阵，提升零阶优化速度
Subspace-based Approximate Hessian Method for Zeroth-Order Optimization
- 在随机二维子空间中拟合二次多项式估算海森矩阵
- 实验显示收敛速度比现有方法快，8个数据集均有效
- 适合高维黑箱优化，尤其函数查询成本高的场景
零阶优化处理无法获取梯度信息或计算代价过高的问题。尽管多数现有方法依赖一阶近似，理论上引入二阶（曲率）信息可显著加速收敛。但估算海森矩阵所需的高函数查询成本常限制其实际应用。本文提出基于子空间的零阶近似海森方法（ZO-SAH），通过聚焦随机选取的二维子空间降低计算成本。在每个子空间内，ZO-SAH通过拟合目标函数的二次多项式并提取其二阶系数来估计海森矩阵。为进一步减少函数查询次数，该方法采用周期性子空间切换策略，复用优化步骤间的函数评估结果。在包括逻辑回归和深度神经网络训练在内的八个基准数据集上的实验表明，ZO-SAH的收敛速度显著优于现有零阶方法。
原文摘要 · Abstract (English)
Zeroth-order optimization addresses problems where gradient information is inaccessible or impractical to compute. While most existing methods rely on first-order approximations, incorporating second-order (curvature) information can, in principle, significantly accelerate convergence. However, the high cost of function evaluations required to estimate Hessian matrices often limits practical applicability. We present the subspace-based approximate Hessian (ZO-SAH) method, a zeroth-order optimization algorithm that mitigates these costs by focusing on randomly selected two-dimensional subspaces. Within each subspace, ZO-SAH estimates the Hessian by fitting a quadratic polynomial to the objective function and extracting its second-order coefficients. To further reduce function-query costs, ZO-SAH employs a periodic subspace-switching strategy that reuses function evaluations across optimization steps. Experiments on eight benchmark datasets, including logistic regression and deep neural network training tasks, demonstrate that ZO-SAH achieves significantly faster convergence than existing zeroth-order methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。