用轨迹限定几何条件,揭示优化算法局部收敛的真正速率来源
Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence

- 基于轨迹局部几何构建新型收敛条件,避免全局最坏情况保守估计
- 在多面体复合问题中,收敛速度由路径所经面的受限Hoffman常数决定
- 适用于主动集或流形识别后的快速局部收敛分析,适合优化理论研究者
一阶优化方法的线性收敛通常由反映整体空间最坏几何特性的全局条件刻画。但在高维或结构化问题中,这些全局常数可能极度保守,无法捕捉优化轨迹实际经历的几何特征。本文提出一种轨迹受限的线性收敛分析框架,引入仅在定义域子集上成立的受限Polyak--Łojasiewicz不等式、误差界和二次增长条件。我们证明经典收敛保证可在这些局部条件下成立,并在关键情形下建立对应常数间的显式关系。最终收敛速率由算法轨迹所经过区域的几何量决定。对于多面体复合问题,收敛受路径中访问的活跃多面体面所对应的受限Hoffman常数控制。一旦迭代进入条件良好的面,有效条件数随之改善。本工作为主动集或流形识别后的快速局部收敛提供了几何量化,并表明线性收敛本质上由算法探索子集的几何决定,而非全局最坏条件。
原文摘要 · Abstract (English)
Linear convergence of first-order methods is typically characterized by global optimization conditions whose constants reflect worst-case geometry of the ambient space. In high-dimensional or structured problems, these global constants can be arbitrarily conservative and fail to capture the geometry actually encountered by optimization trajectories. In this paper, we develop a trajectory-restricted framework for linear convergence based on localized geometric regularity. We introduce restricted variants of the Polyak--Łojasiewicz inequality, error bound, and quadratic growth conditions that are required to hold only on subsets of the domain. We show that classical convergence guarantees extend under these localized conditions, and in key cases, we develop new arguments that yield explicit relationships between the corresponding constants. The resulting rates are governed by geometric quantities associated with the regions traversed by the algorithm. For polyhedral composite problems, we prove that convergence is controlled by restricted Hoffman constants corresponding to the active polyhedral faces visited along the trajectory. Once the iterates enter a well-conditioned face, the effective condition number improves accordingly. Our work provides a geometric quantification for fast local convergence after active-set or manifold identification and more broadly suggests that linear convergence is fundamentally governed by the geometry of the subsets explored by the algorithm, rather than by worst-case global conditioning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。