AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization

• 成果类型: Article; Early Access
• 署名作者: Zhou, Danqing; Ma, Shiqian; Yang, Tunfeng
• 署名单位: Nanjing University; Rice University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0510
• 发表日期: 2025
• 关键词: worst-case performance; 1st-order methods; gradient methods; minimization; steplength

摘要

In this paper, we propose AdaBB, an adaptive gradient method based on the Barzilai-Borwein stepsize. The algorithm is line-search-free and parameter-free, and it essentially provides a convergent variant of the Barzilai-Borwein method for general convex optimization problems. We analyze the ergodic convergence of the objective function value and the convergence of the iterates for solving general convex optimization problems. Compared with existing works along this line of research, our algorithm gives the best lower bounds on the stepsize and the average of the stepsizes. Furthermore, we present extensions of the proposed algorithm for solving locally strongly convex and composite convex optimization problems where the objective function is the sum of a smooth function and a nonsmooth function. In the case of local strong convexity, we achieve linear convergence. Our numerical results also demonstrate very promising potential of the proposed algorithms on some representative examples.