arXiv:2604.06926math.OCcs.LG2026-04被引 2

将DC算法视为连续动力系统,揭示其收敛机制与分解质量的几何关系。

Continuous-Time Dynamics of the Difference-of-Convex Algorithm

  • 用微分方程视角分析DCA,提出带阻尼的新变体。
  • 证明了全局线性收敛率及在非退化极小值附近的局部指数收敛。
  • 揭示不同分解方式导致不同几何动力,提供分解质量判断标准。

我们研究平滑DC分解中带强凸分量的差分凸算法(DCA)的连续时间结构。在对偶坐标下,经典DCA恰好是某个非线性自治系统的全步显式欧拉离散化。这一视角催生了一种阻尼型DCA方案,也是Bregman正则化版本,其零步长极限对应由分解中凸部生成的海森-黎曼梯度流。对于该阻尼方案,我们证明了单调下降、渐近临界性、有界条件下的Kurdyka-Łojasiewicz收敛性,以及在度量DC-PL不等式下的全局线性速率。对于极限流,我们建立了精确的能量恒等式,有界轨迹的渐近临界性,度量相对误差界下的显式全局速率,满足K-L假设时的有限长度与单点收敛性,以及在非退化局部极小值附近的局部指数收敛性。分析还揭示了全局与局部权衡:半松弛方案在框架内给出最佳全局保证,而全步方案在非退化极小值附近局部最快。最后,我们表明同一目标的不同DC分解会因凸部分生成的度量而产生不同的连续动力,提供了分解质量的几何判据,并将DCA与Bregman几何相联系。

原文摘要 · Abstract (English)

We study the continuous-time structure of the difference-of-convex algorithm (DCA) for smooth DC decompositions with a strongly convex component. In dual coordinates, classical DCA is exactly the full-step explicit Euler discretization of a nonlinear autonomous system. This viewpoint motivates a damped DCA scheme, which is also a Bregman-regularized DCA variant, and whose vanishing-step limit yields a Hessian-Riemannian gradient flow generated by the convex part of the decomposition. For the damped scheme we prove monotone descent, asymptotic criticality, Kurdyka-Lojasiewicz convergence under boundedness, and a global linear rate under a metric DC-PL inequality. For the limiting flow we establish an exact energy identity, asymptotic criticality of bounded trajectories, explicit global rates under metric relative error bounds, finite-length and single-point convergence under a Kurdyka-Lojasiewicz hypothesis, and local exponential convergence near nondegenerate local minima. The analysis also reveals a global-local tradeoff: the half-relaxed scheme gives the best provable global guarantee in our framework, while the full-step scheme is locally fastest near a nondegenerate minimum. Finally, we show that different DC decompositions of the same objective induce different continuous dynamics through the metric generated by the convex component, providing a geometric criterion for decomposition quality and linking DCA with Bregman geometry.

优化算法DC规划收敛分析几何优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。