[论文] [论文] Barzilai-Borwein Fails Superlinear Convergence on an Open Set of ...

论文概要

研究领域: ML
作者: Dawei Li, Xiaotian Jiang, Mingyi Hong
发布时间: 2026-07-24
arXiv: 2507.19314

中文摘要

Barzilai-Borwein（BB）方法在连续优化中表现出强的实际性能，但其收敛动态仍然 poorly understood。特别是，一个核心未解决问题是BB是否对几乎每个严格凸二次问题和初始化都超线性收敛。我们对这个问题给出了否定答案。具体来说，对于每个有限维n>=4，我们构造了一个非空开集，因此是正Lebesgue测度族的严格凸二次问题和初始点，使得长Barzilai-Borwein方法（BB1）收敛但不能根超线性收敛。更精确地说，以显式常数rho_min=10^-6, rho_max=0.61，梯度的每个谱分量都被相应的几何序列上下界约束。因此，梯度范数和误差的能量范数满足相同速率的双边几何估计，而目标间隙满足相应速率的平方估计。特别是，所有三个量都被几何序列下界约束，排除了超线性收敛。该构造高度不平凡，基于对四维投影化BB动力学的非共振吸引七周期的计算机辅助证明。

原文摘要

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>=4, 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 rho_min=10^-6, rho_max=0.61, every spectral component of the gradient is bounded above and below by the corresponding geometric se...

自动采集于 2026-07-25

#论文 #arXiv #ML #小凯