arXiv:2608.01658math.OCcs.LG2026-08被引 1

证明了熵镜下降法在边界处存在非KKT的累积点,揭示了其几何退化问题。

Non-KKT Accumulation in Entropic Mirror Descent

论文配图:Non-KKT Accumulation in Entropic Mirror Descent
图 1 · 摘自论文原文
  • 构造光滑目标函数与适定步长,使镜下降序列在边界形成非KKT累积点
  • 在n≥3的非负象限和n≥4的概率单纯形上,累积点集为含非KKT弧的光滑圆
  • 首次在目标值非增条件下给出镜下降法不收敛至KKT点的反例

对于由Legendre核生成的镜下降法,一个基本问题是:在适当步长下,有界镜下降序列的每个累积点是否必为Karush--Kuhn--Tucker(KKT)驻点?本文表明答案是否定的。长期阻碍该问题解决的障碍在于Legendre梯度在边界处的爆破:它使每一步都保持在内部,而在边界极限处,逆熵度量在活动坐标上消失,导致KKT系统中对偶可行性被抹除。本文构造了$C^ ty$目标函数及在非负象限$\R_+^n$($n\≥ 3$)和概率单纯形$Δ_n$($n\≥ 4$)上的有界序列,均采用Shannon熵镜下降法,其累积点集为包含非空相对开弧的光滑边界圆,且步长满足$α_k\asymp k^{-β}$($β\in(1/2,1)$),目标值非增,目标函数为熵相对光滑。因此,病理性现象源于边界处Bregman几何的退化,而非下降失败或步长不当。据我们所知,这是首次在目标值非增条件下,为有界镜下降序列提供不收敛于KKT点的反例。

原文摘要 · Abstract (English)

For mirror descent generated by a Legendre kernel, perhaps one of the most basic question in optimization is this: must every accumulation point of a bounded mirror descent sequence be Karush--Kuhn--Tucker (KKT) stationary under proper stepsizes? We show that the answer is no. A longstanding obstacle to resolving this question is the boundary blow-up of the Legendre gradient: it keeps every mirror step in the interior, while at a boundary limit, the inverse entropy metric vanishes on active coordinates and can erase the dual-feasibility in the KKT system. We construct $C^\infty$ objectives and bounded sequences generated by the Shannon-entropic mirror descent on the nonnegative orthant $\R_+^n$, for every $n\geq 3$, and on the probability simplex $Δ_n$, for every $n\geq 4$, such that, in each case, the set of accumulation points is a smooth boundary circle containing a nonempty relatively open arc of non-KKT points. The steps satisfy $α_k\asymp k^{-β}$ with $β\in(1/2,1)$, the objective values are nonincreasing, and the objectives are entropy-relatively smooth. Hence the pathology stems from the degeneracy of the Bregman geometry at the boundary, rather than from failure of descent, or improper stepsizes. To the best of our knowledge, these provide the first counterexamples to KKT accumulation for bounded mirror descent sequences with nonincreasing objective values.

优化理论镜下降边界退化KKT点

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