Global Convergence Guarantees for Adaptive Gradient Algorithms with Barzilai–Borwein and Alternative Step-Length Strategies

Alyaqdhan Ammar Abed

Authors

Alyaqdhan Ammar Abed Department of Mathematics, Faculty of Science, Maragheh University, Iran

Keywords:

Convex Optimization, Proximal-Gradient Methods, Adaptive Step-Lengths, Global Convergence, Barzilai–Borwein, Anderson Acceleration

Abstract

Motivated by recent progress in adaptive schemes for convex optimization, this work develops a proximal-gradient framework that enforces global convergence without resorting to linesearch procedures. The proposed approach accommodates widely used step-length rules, including Barzilai–Borwein updates and one-dimensional Anderson-type acceleration. Importantly, the analysis applies to problems where the smooth component admits only local Hölder continuity of its gradient. The resulting theory unifies and strengthens several existing results, while numerical experiments confirm the practical benefits of coupling aggressive step-length selection with adaptive safeguarding mechanisms.

References

D. G. Anderson, "Iterative procedures for nonlinear integral equations," J. ACM, vol. 12, no. 4, pp. 547–560, 1965.

J. Barzilai and J. M. Borwein, "Two-point step size gradient methods," IMA J. Numer. Anal., vol. 8, no. 1, pp. 141–148, 1988.

A. Beck, First-order methods in optimization. SIAM, 2017.

A. Beck and M. Teboulle, "Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems," IEEE Trans. Image Process., vol. 18, no. 11, pp. 2419–2434, 2009.

D. P. Bertsekas, Nonlinear Programming. Athena Scientific, 2016.

S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.

S. Bubeck, "Theory of convex optimization for machine learning," arXiv preprint arXiv:1405.4980, 2014.

O. Burdakov, Y. Dai, and N. Huang, "Stabilized Barzilai-Borwein method," J. Comput. Math., vol. 37, no. 6, pp. 916–936, 2019.

C. Chang and C. Lin, "LIBSVM: a library for support vector machines," ACM Trans. Intell. Syst. Technol., vol. 2, no. 3, pp. 1–27, 2011.

Y. Dai and L. Liao, "R-linear convergence of the Barzilai and Borwein gradient method," IMA J. Numer. Anal., vol. 22, no. 1, pp. 1–10, 2002.

H. Fang and Y. Saad, "Two classes of multisecant methods for nonlinear acceleration," Numer. Linear Algebra Appl., vol. 16, no. 3, pp. 197–221, 2009.

P. Latafat, A. Themelis, and P. Patrinos, "On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms," arXiv preprint arXiv:2311.18431, 2023.

P. Latafat, A. Themelis, L. Stella, and P. Patrinos, "Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient," arXiv preprint arXiv:2301.04431, 2023.

D. Li and R. Sun, "On a faster R-linear convergence rate of the Barzilai-Borwein method," arXiv preprint arXiv:2101.00205, 2021.

Y. Li, X. Tang, X. Lin, L. Grzesiak, and X. Hu, "The role and application of convex modeling and optimization in electrified vehicles," Renewable Sustainable Energy Rev., vol. 153, p. 111796, 2022.

Z. Luo, "Applications of convex optimization in signal processing and digital communication," Math. Program., vol. 97, no. 1, pp. 177–207, 2003.

Y. Malitsky and K. Mishchenko, "Adaptive gradient descent without descent," in Proc. 37th Int. Conf. Mach. Learn., vol. 119, pp. 6702–6712, 2020.

Y. Malitsky and K. Mishchenko, "Adaptive proximal gradient method for convex optimization," arXiv preprint arXiv:2308.02261, 2023.