Absence of spurious solutions far from ground truth: A low-rank analysis with high-order losses
This addresses the challenge of avoiding suboptimal solutions in non-convex optimization for machine learning, though it is incremental as it builds on existing theoretical insights.
The paper tackles the problem of spurious solutions in non-convex matrix sensing by proving that critical points far from the ground truth are strict saddle points under certain conditions, and shows that using high-order losses amplifies negative curvature to accelerate escape from these points.
Matrix sensing problems exhibit pervasive non-convexity, plaguing optimization with a proliferation of suboptimal spurious solutions. Avoiding convergence to these critical points poses a major challenge. This work provides new theoretical insights that help demystify the intricacies of the non-convex landscape. In this work, we prove that under certain conditions, critical points sufficiently distant from the ground truth matrix exhibit favorable geometry by being strict saddle points rather than troublesome local minima. Moreover, we introduce the notion of higher-order losses for the matrix sensing problem and show that the incorporation of such losses into the objective function amplifies the negative curvature around those distant critical points. This implies that increasing the complexity of the objective function via high-order losses accelerates the escape from such critical points and acts as a desirable alternative to increasing the complexity of the optimization problem via over-parametrization. By elucidating key characteristics of the non-convex optimization landscape, this work makes progress towards a comprehensive framework for tackling broader machine learning objectives plagued by non-convexity.