  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.
