Spurious Stationarity and Hardness Results for Mirror Descent
He Chen Jiajin Li Anthony Man-Cho So
Despite the considerable success of Bregman proximal-type algorithms, such as
mirror descent, in machine learning, a critical question remains: Can existing
stationarity measures, often based on Bregman divergence, reliably distinguish
between stationary and non-stationary points? In this paper, we present a
groundbreaking finding: All existing stationarity measures necessarily imply
the existence of spurious stationary points. We further establish an
algorithmic independent hardness result: Bregman proximal-type algorithms are
unable to escape from a spurious stationary point in finite steps when the
initial point is unfavorable, even for convex problems. Our hardness result
points out the inherent distinction between Euclidean and Bregman geometries,
and introduces both fundamental theoretical and numerical challenges to both
machine learning and optimization communities.