Abstract:Bregman proximal-type algorithms (BPs), such as mirror descent, have become popular tools in machine learning and data science for exploiting problem structures through non-Euclidean geometries. In this paper, we show that BPs can get trapped near a class of non-stationary points, which we term \emph{spurious stationary points}. Such stagnation can persist for any finite number of iterations if the gradient of the Bregman kernel is not Lipschitz continuous, even in convex problems. The root cause lies in a fundamental contrast in descent behavior between Euclidean and Bregman geometries: While Euclidean gradient descent ensures sufficient decrease near any non-stationary point, BPs may exhibit arbitrarily slow decrease around spurious stationary points. As a result, commonly used Bregman-based stationarity measure, such as relative change in terms of Bregman divergence, can vanish near spurious stationary points. This may misleadingly suggest convergence, even when the iterates remain far from any true stationary point. Our analysis further reveals that spurious stationary points are not pathological, but rather occur generically in a broad class of nonconvex problems with polyhedral constraints. Taken together, our findings reveal a serious blind spot in Bregman-based optimization methods and calls for new theoretical tools and algorithmic safeguards to ensure reliable convergence.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2404.08073 [math.OC] |
| (or arXiv:2404.08073v3 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2404.08073 arXiv-issued DOI via DataCite |
From: Jiajin Li [view email]
[v1]
Thu, 11 Apr 2024 18:28:01 UTC (85 KB)
[v2]
Mon, 14 Jul 2025 00:46:09 UTC (271 KB)
[v3]
Mon, 25 May 2026 08:13:38 UTC (295 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。