On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method

Dawei Li, Ruoyu SunarXiv 2021 · arXiv

Abstract

The Barzilai-Borwein (BB) method is a popular gradient-based optimization algorithm known for its empirical efficiency. However, existing theoretical analysis suggested a dimension-dependent convergence rate that failed to explain its performance in high-dimensional settings. This paper provides a new analysis for strongly convex quadratic problems, proving an R-linear convergence rate of $1 - 1/\kappa$, where $\kappa$ is the condition number of the Hessian. This result removes the dependence on dimension $n$, establishing that the BB method is theoretically as competitive as the classic Steepest Descent method.

Introduction

The Barzilai-Borwein (BB) method has long been favored by practitioners for its simplicity and superior speed compared to the standard Steepest Descent (SD) method. Despite its practical success, a significant gap existed between its observed performance and theoretical guarantees. While SD converges at a rate of approximately $1 - 2/\kappa$, the best-known theoretical bound for BB was $1 - (1/\kappa)^{1/n}$, where $n$ is the problem dimension. For large-scale problems, this bound suggested extreme inefficiency, contradicting real-world experience. This research investigates whether this discrepancy stems from inherent weaknesses in the algorithm or limitations in previous analytical frameworks.

Methodology

The study focuses on the minimization of strongly convex quadratic functions. The researchers analyzed the algorithm by decomposing the gradient into components along the eigenvectors of the Hessian matrix. They tracked the evolution of these components, identifying two distinct behaviors:

  1. Shrinking Mode: A state where the magnitude of a component naturally decreases.
  2. Fluctuation Mode: A state where a component may temporarily increase.

Through an inductive proof, the authors demonstrate that the BB stepsize rule possesses a self-correcting mechanism. When a component enters the fluctuation mode and grows, the stepsize eventually adjusts to force it back into the shrinking mode, preventing long-term divergence or stagnation.

Results

The primary contribution of this work is the proof of an $R$-linear convergence rate of $1 - 1/\kappa$ for $n$-dimensional strongly convex quadratic problems. This bound is independent of $n$, explaining why the BB method remains effective in high-dimensional spaces.

Trajectories of gradient components in a 4-dimensional quadratic problem, illustrating the oscillatory but convergent behavior of the BB method.

As shown in Figure 1, the trajectories of the gradient components exhibit significant oscillations (the "fluctuation mode"), yet they maintain a consistent downward trend over time. The analysis confirms that this new rate is comparable to the Steepest Descent rate ($1 - 2/(\kappa+1)$). Furthermore, the authors constructed a worst-case scenario to prove that this $1 - 1/\kappa$ bound is tight and cannot be improved without additional assumptions.

Conclusion

This paper successfully closes the theoretical gap for the Barzilai-Borwein method on quadratic problems. By providing a dimension-independent convergence rate, it aligns mathematical theory with empirical evidence. While the current proof is limited to quadratic objectives, it provides a rigorous foundation for understanding the "folk hero" of optimization. Future work may extend these insights to non-convex or general non-linear functions to explain why BB often outperforms its worst-case bounds in practice.

Summary updated

Abstract

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/\kappa$, where $\kappa$ 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.
BibTeX
@misc{li2021faster,
  author = {Dawei Li and Ruoyu Sun},
  title = {{On a Faster R-Linear Convergence Rate of the Barzilai-Borwein Method}},
  year = {2021},
  eprint = {2101.00205},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.00205},
}
Figure