Asymptotic Analysis of the Ruppert – Polyak Averaging for Stochastic Order Oracle

V. N. Smirnov ; K. M. Kazistova ; I. A. Sudakov ; V. Leplat ; A. V. Gasnikov ; A. V. Lobanov

Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 961-978.

Résumé

Black-box optimization, a rapidly growing field, faces challenges due to limited knowledge of the objective function’s internal mechanisms. One promising approach to addressing this is the Stochastic Order Oracle Concept. This concept, similar to other Order Oracle Concepts, relies solely on relative comparisons of function values without requiring access to the exact values. This paper presents a novel, improved estimation of the covariance matrix for the asymptotic convergence of the Stochastic Order Oracle Concept. Our work surpasses existing research in this domain by offering a more accurate estimation of asymptotic convergence rate. Finally, numerical experiments validate our theoretical findings, providing strong empirical support for our proposed approach.

Détail

Keywords: stochastic order oracle, stochastic optimization, asymptotic convergence analysis

Bibliographie

[1] Avtomat. i Telemekh., 1980, no. 8, 74–84 (Russian) | MR | Zbl

[2] Polyak, B. T. and Juditsky, A. B., “Acceleration of Stochastic Approximation by Averaging”, SIAM J. Control Optim., 30:4 (1992), 838–855 | DOI | MR | Zbl

[3] Lobanov, A., Gasnikov, A., and Krasnov, A., Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values, , 2024, 33 pp. arXiv:2402.09014 [math.OC]

[4] Zhang, C. and Li, T., Comparisons Are All You Need for Optimizing Smooth Functions, , 2024, 39 pp. arXiv:2405.11454 [cs.LG]

[5] Cutkosky, A. and Mehta, H., “Momentum improves normalized sgd”, International Conference on Machine Learning, 2020, 2260–2268

[6] Sun, T., Wang, Q., Li, D., and Wang, B., “Momentum ensures convergence of signsgd under weaker assumptions”, International Conference on Machine Learning, 2023, 33077–33099

[7] Liu, S., Chen, P.-Y., Chen, X., and Hong, M., “signSGD via Zeroth-Order Oracle”, International Conference on Learning Representations, 2019

[8] Praneeth Karimireddy, S., Rebjock, Q., Stich, S. U., and Jaggi, M., Error Feedback Fixes SignSGD and other Gradient Compression Schemes, , 2019, 22 pp. arXiv:1901.09847 [cs.LG]

[9] Saha, A., Koren, T., and Mansour, Y., “Dueling Convex Optimization”, Proc. of the 38th Internat. Conf. on Machine Learning (ICML'2021), 9245–9254

[10] Boyd, S. and Vandenberghe, L., Convex Optimization, Cambridge Univ. Press, Cambridge, 2004, 727 pp. | MR | Zbl

[11] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R., “Training Language Models to Follow Instructions with Human Feedback”, Proc. of the 36th Internat. Conf. on Neural Information Processing Systems (NIPS, New Orleans, La., USA, 2022), 27730–27744

[12] Chen, P.-Y., Zhang, H., Sharma, Y., Yi, J., and Hsieh, C.-J., Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, 2017, Zoo: Zeroth Order Optimization based Black-Box Attacks to Deep Neural Networks without Training Substitute Models

[13] Conn, A. R., Scheinberg, K., and Vicente, L. N., Introduction to Derivative-Free Optimization, SIAM, Philadelphia, Penn., 2009, 289 pp. | MR | Zbl

[14] Nesterov, Yu., Lectures on Convex Optimization, Springer Optimization and Its Applications, 137, 2nd ed., Springer, Cham, 2018, xxiii, 589 pp. | DOI | MR | Zbl

[15] Tang, Z., Rybin, D., and Chang, T.-H., Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles, , 2023, 33 pp. arXiv:2303.03751 [cs.LG]

[16] Larson, J., Menickelly, M., and Wild, S. M., “Derivative-Free Optimization Methods”, Acta Numer., 28 (2019), 287–404 | DOI | MR | Zbl

[17] Murray, R., Swenson, B., and Kar, S., “Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points”, IEEE Trans. Autom. Control., 64:11 (2019), 4818–4824 | DOI | MR | Zbl

[18] Nesterov, Yu. and Spokoiny, V., “Random Gradient-Free Minimization of Convex Functions”, Found. Comput. Math., 17:2 (2017), 527–566 | DOI | MR | Zbl

[19] Papernot, N., McDaniel, P., Goodfellow, I., Jha, S., Celik, Z. B., and Swami, A., Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, 2017, Practical Black-Box Attacks against Machine Learning

[20] Gadat, S. and Panloup, F., “Optimal Non-Asymptotic Analysis of the Ruppert – Polyak Averaging Stochastic Algorithm”, Stoch. Proc. Appl., 156:C (2023), 312–348 | DOI | MR | Zbl