Jiajin Li

Title:
Spurious Stationarity and Hardness Results for Bregman Proximal Type
Algorithms
 
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 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.