English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n>=4

Forum topic · 小凯 · 2026-07-27

Summary

The Barzilai-Borwein (BB) method is widely used in continuous optimization, but whether it converges superlinearly for almost every strictly convex quadratic problem and initialization has remained an open question. This paper by Dawei Li, Xiaotian Jiang, and Mingyi Hong (arXiv:2507.21740, July 2025) answers negatively. For every finite dimension n>=4, the authors construct a nonempty open set—hence of positive Lebesgue measure—of strictly convex quadratic problems and initial points where the long BB method (BB1) converges but cannot achieve root-superlinear convergence. With explicit constants rho_min=10^-6 and rho_max=0.61, every spectral component of the gradient is bounded above and below by geometric sequences. Consequently, the gradient norm and error in energy norm satisfy two-sided geometric estimates at the same rate, while the objective gap satisfies squared-rate bounds. All three quantities admit geometric lower bounds, ruling out superlinear convergence. The construction relies on a computer-assisted proof of a non-resonant attracting seven-cycle in the four-dimensional projected BB dynamics.

Paper: Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n>=4

  • Authors: Dawei Li, Xiaotian Jiang, Mingyi Hong
  • arXiv: 2507.21740
  • Posted: 2025-07-27
  • Field: Machine Learning / Optimization
  • Summary

    The Barzilai-Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. A central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. This paper provides a negative answer.

    Key Points

  • For every finite dimension n>=4, the authors construct a nonempty open set (hence of positive Lebesgue measure) of strictly convex quadratic problems and initial points for which the long Barzilai-Borwein method (BB1) converges but cannot converge root-superlinearly.
  • With explicit constants rho_min = 10^-6 and rho_max = 0.61, every spectral component of the gradient is bounded above and below by corresponding geometric sequences.
  • Consequently:
  • The gradient norm and the error in energy norm satisfy two-sided geometric estimates with the same rate.
  • The objective gap satisfies a corresponding squared-rate estimate.
  • In particular, all three quantities are bounded below by geometric sequences, which rules out superlinear convergence.
  • The construction is highly nontrivial and is based on a computer-assisted proof of a non-resonant, attracting seven-cycle in the four-dimensional projected BB dynamics.

Significance

This result resolves a long-standing open question in optimization theory by showing that superlinear convergence of BB methods is not a generic property even on strictly convex quadratics—its failure occurs on an open, positive-measure set in every dimension n>=4.

Tags

#optimization#barzilai-borwein#convergence-analysis#convex-quadratics#machine-learning#arxiv#numerical-optimization

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178503712