Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
We analyze the robustness of Burer-Monteiro factorization for matrix sensing under over-parameterization (search rank k > target rank r_star), revealing that robustness depends on both the degree of over-parameterization and the local geometry of second-order stationary points. While increasing k generally decreases robustness, stationary points with the same k can exhibit varying sensitivities. A novel trajectory-aware algorithm, employing spectral balancing and randomized sketching, successfully navigates optimization to more robust solutions, reducing paired sensitivity by up to 89% without compromising reconstruction accuracy.
Over-parameterization's impact on robustness is not monotonic; solution geometry and optimization path, not just parameter count, dictate sensitivity in matrix sensing.
Over-parameterization is ubiquitous in modern machine learning, yet its effect on robustness remains poorly understood. We study this question in matrix sensing, a canonical non-convex problem that can also be viewed, under an appropriate parameterization, as training a two-layer quadratic neural network. We develop a rank-aware robustness theory for the Burer-Monteiro factorization when the search rank k may exceed the target rank r_star, thereby capturing over-parameterization. Our analysis shows that robustness depends jointly on the degree of over-parameterization and the local geometry of the attained second-order stationary point: increasing k generally worsens sensitivity, but stationary points with the same search rank can exhibit substantially different robustness. Motivated by this observation, we propose a trajectory-aware algorithm that uses spectral balancing and randomized sketching to steer optimization toward less sensitive solutions. In matrix-sensing experiments, the method reduces paired sensitivity by 18-29 percent for isotropic operators and 87-89 percent for weak-tail operators, without degrading reconstruction accuracy. These results demonstrate that parameter count alone does not determine robustness and identify solution geometry and the optimization trajectory as important levers for improving it.