On the Absence of Identifiable Manifolds in Finite-Max Composite Optimization
Abstract
In nonsmooth optimization, identifiable sets describe the local region eventually reached by sequences converging to a prescribed critical point. When such a set is a $C^2$ manifold on which the objective restricts to a $C^2$ function, it is called an identifiable manifold. Their appeal lies in what they enable: many first-order methods identify these manifolds in finitely many iterations, after which the iterates enter a region in which the problem is effectively smooth. Consequently, many powerful tools and guarantees from smooth optimization transplant naturally to the nonsmooth setting. Owing to these properties, much existing work has focused on characterizing conditions that guarantee their existence. In this work, we study a complementary question: under what conditions is a critical point devoid of any identifiable manifold? We answer this by developing a deterministic branching criterion for a broad class of finite-max composite optimization problems, characterizing when a critical point admits no identifiable manifold. This criterion is surprisingly mild in certain classes of problems: it holds with high probability for overparameterized robust low-rank recovery and almost surely at common interpolators of random minimax regression, suggesting that the absence of identifiable manifolds may be the rule rather than the exception in modern optimization.