固定函数值查询预算下零阶Heavy Ball方法的数值比较
Numerical Comparison of Zeroth-Order Heavy Ball Methods under a Fixed Query Budget
摘要: 随机梯度下降算法是优化问题的基本算法,但在实际应用中,有时目标函数的梯度难以获得,或者没有解析表达,只能得到其函数值。本文考虑在此情形下的零阶优化方法,在固定函数值查询预算下,比较小批量SGD、零阶随机梯度下降(ZO-SGD)及不同动量系数的零阶Heavy Ball方法(ZO-HB)的数值表现。主实验在合成线性回归、Diabetes岭回归和Breast Cancer逻辑回归三个任务上进行,并补充100维合成回归、非凸神经网络和扰动尺度比较。零阶训练统一采用96,000次零阶训练函数值查询上限(不含调参与性能评估)。结果表明,对比ZO-SGD,所考察ZO-HB配置在合成与Breast Cancer上的平均测试指标较好,在Diabetes上的平均RMSE较高。逐方向数独立选参后,K的增加并不一定带来预算内性能提升;两个补充任务中,验证选择的ZO-HB平均RMSE均低于ZO-SGD。单样本替换实验进一步显示,参数距离与测试目标变化不一定同向,其结果依赖于不同任务和超参数。本文结果说明了有限查询预算下随机方向数、动量和学习率选择之间的关系。
Abstract: Stochastic gradient descent is a fundamental algorithm for optimization problems. In practice, however, the gradient of the objective function is sometimes difficult to obtain or has no analytic expression, and only function values are available. This paper considers zeroth-order optimization methods in this setting and compares the numerical performance of mini-batch SGD, zeroth-order stochastic gradient descent (ZO-SGD), and zeroth-order Heavy Ball methods (ZO-HB) with different momentum coefficients under a fixed function value query budget. The main experiments are conducted on synthetic linear regression, Diabetes ridge regression, and Breast Cancer logistic regression, with additional comparisons on 100-dimensional synthetic regression, a nonconvex neural network, and perturbation scales, all with a cap of 96,000 zeroth-order training function-value queries, excluding tuning and evaluation. The results show that, compared with ZO-SGD, the tested ZO-HB configurations have better mean test metrics on synthetic data and Breast Cancer but higher mean RMSE on Diabetes. After independent validation selection for each direction count, increasing K does not necessarily improve performance within the budget. On both additional tasks, the validation-selected ZO-HB has lower mean RMSE than ZO-SGD. One-sample replacement experiments further show that parameter distance and test-objective change need not follow the same ordering, and the results depend on the task and hyperparameters. The results illustrate the relationships among direction count, momentum, and learning-rate selection under a limited query budget.
参考文献
|
[1]
|
Nesterov, Y. and Spokoiny, V. (2017) Random Gradient-Free Minimization of Convex Functions. Foundations of Computational Mathematics, 17, 527-566. https://doi.org/10.1007/s10208-015-9296-2
|
|
[2]
|
Zeng, S. and Lei, Y. (2026) Stochastic Gradient Methods: Bias, Stability and Generalization. Journal of Machine Learning Research, 27, 1-55. https://jmlr.org/papers/v27/24-0637.html
|
|
[3]
|
Polyak, B.T. (1964) Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathematical Physics, 4, 1-17. https://doi.org/10.1016/0041-5553(64)90137-5
|
|
[4]
|
Gorbunov, E., Bibi, A., Sener, O., Bergou, E.H. and Richtárik, P. (2020) A Stochastic Derivative Free Optimization Method with Momentum. 2020 International Conference on Learning Representations, Online, 26 April-1 May 2020. https://openreview.net/forum?id=HylAoJSKvH
|
|
[5]
|
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., et al. (2011) Scikit-Learn: Machine Learning in Python. Journal of Machine Learning Research, 12, 2825-2830. https://jmlr.org/papers/v12/pedregosa11a.html
|
|
[6]
|
Efron, B., Hastie, T., Johnstone, I. and Tibshirani, R. (2004) Least Angle Regression. The Annals of Statistics, 32, 407-499. https://doi.org/10.1214/009053604000000067
|
|
[7]
|
Wolberg, W.H., Street, W.N. and Mangasarian, O.L. (1994) Machine Learning Techniques to Diagnose Breast Cancer from Image-Processed Nuclear Features of Fine Needle Aspirates. Cancer Letters, 77, 163-171. https://doi.org/10.1016/0304-3835(94)90099-x
|