---
title: "Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension n ≥ 4"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2607.21579v1"
permalink: "https://feed.astralor.com/items/itm_2d5c7dcda498d3f552f8974a"
published: "2026-07-23T17:56:05.000Z"
score: 77
channel: "ai"
tags: ["Barzilai-Borwein method","Optimization Algorithm","Convergence analysis","Computer-assisted proof"]
---

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

## AI commentary

> This paper is extremely rigorous and worth reading for anyone interested in optimization theory. It not only disproves a long-standing conjecture but also demonstrates the power of computer-assisted proofs in continuous optimization. If you design or analyze adaptive step-size optimizers, this result reminds you that superlinear convergence is not guaranteed. For AI researchers, understanding the true behavior of the BB method helps avoid overreliance on empirical assumptions.

## At a glance

The Barzilai-Borwein (BB) method performs well in continuous optimization, yet its convergence dynamics have long been poorly understood. This paper constructs a nonempty open set (positive Lebesgue measure) of strictly convex quadratic problems and initial points in every dimension n ≥ 4, showing that the long BB1 method converges but cannot achieve root-superlinear convergence. Via a computer-assisted proof of a nonresonant, attracting seven-cycle in the projectivized BB dynamics in dimension four, it shows that gradient norms and energy norms are bounded both above and below by geometric sequences, ruling out superlinear convergence.

## Key points

- Barzilai-Borwein method converges but fails root-superlinear convergence on an open set of strictly convex quadratics for n ≥ 4.
- Explicit constants ρ_min=10^{-6}, ρ_max=0.61 bound each spectral component of the gradient by geometric sequences.
- Computer-assisted proof of a nonresonant, attracting seven-cycle in projectivized BB dynamics in dimension four.
- Both gradient norm, energy norm, and objective gap satisfy two-sided geometric estimates, ruling out superlinear convergence.

## Full text

Barzilai--Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. We provide a negative answer to this question. Specifically, for every finite dimension $n\geq4$, we construct a nonempty open, hence positive-Lebesgue-measure, family of strictly convex quadratic problems and initial points for which the long Barzilai--Borwein method (BB1) converges but cannot converge root-superlinearly. More precisely, with the explicit constants $ρ_{\min}=10^{-6},ρ_{\max}=0.61$, every spectral component of the gradient is bounded above and below by the corresponding geometric sequence. Consequently, the gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rates, while the objective gap satisfies the corresponding estimates with squared rates. In particular, all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial, based on a computer-assisted proof of a nonresonant, attracting seven-cycle of the projectivized BB dynamics in dimension four.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_2d5c7dcda498d3f552f8974a