MODELING CONVERGENCE RATE ESTIMATES OF THE HEAVY BALL ALGORITHM VIA A RANDOM FOREST WITH SELF-ATTENTION
DOI:
https://doi.org/10.58225/sw.2026.1-53-61Keywords:
Convergence rate estimation, heavy ball method, momentum-based optimization, random Forest with self-attention, synthetic trajectory modeling, optimization dynamicsAbstract
This paper addresses the problem of estimating convergence rates of iterative optimization algorithms, which is essential for analyzing and accelerating the training of modern machine learning models. Classical approaches to convergence rate estimation for momentum-based methods typically rely on analytical bounds derived under restrictive assumptions or on extensive empirical experimentation, both of which are computationally expensive and poorly scalable. As an alternative, we propose a data-driven framework for modeling convergence rate estimates using supervised machine learning. The proposed approach is demonstrated for the Heavy Ball optimization method applied to quadratic objective functions with heterogeneous curvature. A synthetic dataset is constructed by simulating Heavy Ball trajectories under randomly sampled objective parameters, optimization hyperparameters, and normalized initial conditions. The input features capture key characteristics of the optimization process, while the target variable represents a logarithmic estimate of the objective function decay along the trajectory, serving as a proxy for the convergence rate. To model nonlinear dependencies between optimization parameters and convergence behavior, we employ a Random Forest model augmented with a self-attention mechanism. This architecture enables adaptive weighting of feature interactions and improves predictive accuracy without requiring explicit analytical modeling of the underlying dynamics. Numerical experiments show that the proposed model achieves a coefficient of determination exceeding 0.8 when predicting convergence-related quantities, indicating strong agreement with empirically observed behavior. The results suggest that machine learning-based surrogate models can substantially simplify convergence rate estimation and that the proposed methodology is applicable to other optimization algorithms and objective classes.
- Views
- 161
- Downloads
- 124
References
[1] Polyak, B. T. (1964). Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5), 1–17. https://doi.org/10.1016/00415553(64)90137-5
[2] Nesterov, Y. (2004). Introductory lectures on convex optimization: A basic course. Springer. https://doi.org/10.1007/978-1-4419-8853-9
[3] Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization methods for large-scale machine learning. SIAM Review, 60(2), 223–311. https://doi.org/10.1137/16M1080173
[4] Andrychowicz, M., Denil, M., Gómez, S., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., & de Freitas, N. (2016). Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems (Vol. 29).
[5] via Lessard, L., Recht, B., & Packard, A. (2016). Analysis and design of optimization algorithms integral quadratic constraints. SIAM Journal on Optimization, 26(1), 57–95. https://doi.org/10.1137/15M1009597
[6] Su, W., Boyd, S., & Candès, E. J. (2016). A differential equation for modeling Nesterov's accelerated gradient method. Journal of Machine Learning Research, 17(153), 1–43.
[7] Chen, T., Chen, X., Chen, W., & Wang, Z. (2022). Learning to optimize: A primer and a benchmark. Journal of Machine Learning Research, 23, 1–59.
[8] Trajanov, R., Dimeski, S., Popovski, M., Korošec, P., & Eftimov, T. (2022). Explainable landscape analysis in automated algorithm performance prediction. arXiv:2203.11828.
[9] Pietrenko-Dąbrowska, A., et al. (2024). Variable resolution machine learning for global antenna optimization using sensitivity-analysis-based dimensionality reduction. Scientific Reports, 14, 28796.
https://doi.org/10.1038/s41598-024-77367-w
[10] Zhao, Y., et al. (2024). A review on optimization algorithms and surrogate models. Geoenergy Science and Engineering, 234, 212554. https://doi.org/10.1016/j.geoen.2023.212554
[11] Rane, N. L., Choudhary, S., & Rane, J. (2024). Techniques and optimization algorithms in machine learning: A review. In Machine Learning and Artificial Intelligence (pp. 27–48). Deep Science Publishing. https://doi.org/10.70593/978-81-981271-4-3_2
[12] Utkin, L. V., & Konstantinov, A. V. (2022). Self-Attention Forests. arXiv:2207.04293.
Published
Issue
Section
License
Copyright (c) 2026 Daniil Miroshnichenko, Majid Abbasov (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
