Spurious Stationarity and Hardness Results for Mirror Descent

arXiv:2404.08073v1 Announce Type: cross
Abstract: 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 …

abstract algorithms arxiv cs.lg divergence groundbreaking machine machine learning math.oc paper question results stat.ml success type