# Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms

arXiv: https://arxiv.org/abs/2404.08073 · HTML: https://mlsanity.com/paper/2404.08073/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 11 Apr 2024.

## Builds on (most cited first, 14 of 14)

- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [Enhanced Bilevel Optimization via Bregman Distance](https://mlsanity.com/paper/2107.12301/) (2021)
- [On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1806.04781/) (2018)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Gradient Regularization of Newton Method with Bregman Distances](https://mlsanity.com/paper/2112.02952/) (2021)
- [Regularizing with Bregman-Moreau envelopes](https://mlsanity.com/paper/1705.06019/) (2017)
- [On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spaces](https://mlsanity.com/paper/2201.12332/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Bregman Proximal Point Algorithm Revisited: A New Inexact Version and its Inertial Variant](https://mlsanity.com/paper/2105.10370/) (2021)
- [Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity](https://mlsanity.com/paper/2102.10312/) (2021)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [Stochastic Bregman Proximal Gradient Method Revisited: Kernel Conditioning and Painless Variance Reduction](https://mlsanity.com/paper/2401.03155/) (2024)
- [Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditions](https://mlsanity.com/paper/1711.01136/) (2017)
- [On the convexity of piecewise-defined functions](https://mlsanity.com/paper/1408.3771/) (2014)

## Built on by (most cited first, 3 of 3)

- [Non-KKT Accumulation in Entropic Mirror Descent](https://mlsanity.com/paper/2608.01658/) (2026)
- [Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization](https://mlsanity.com/paper/2608.07248/) (2026)
- [Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning](https://mlsanity.com/paper/2610.04264/) (2026)

## Abstract (arXiv)

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 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.