On a Faster $R$-Linear Convergence Rate of the Barzilai-Borwein Method
This work addresses a long-standing theoretical gap for optimization researchers by providing a tighter convergence rate for the Barzilai-Borwein method, aligning theory more closely with its observed practical performance.
The Barzilai-Borwein (BB) method is empirically successful in nonlinear optimization, but its theoretical convergence rate for quadratic problems was previously worse than the steepest descent (SD) method. This paper proves that the BB method converges R-linearly at a rate of 1-1/κ for strongly convex quadratic problems, where κ is the condition number, and constructs an example demonstrating the tightness of this bound.
The Barzilai-Borwein (BB) method has demonstrated great empirical success in nonlinear optimization. However, the convergence speed of BB method is not well understood, as the known convergence rate of BB method for quadratic problems is much worse than the steepest descent (SD) method. Therefore, there is a large discrepancy between theory and practice. To shrink this gap, we prove that the BB method converges $R$-linearly at a rate of $1-1/κ$, where $κ$ is the condition number, for strongly convex quadratic problems. In addition, an example with the theoretical rate of convergence is constructed, indicating the tightness of our bound.