Low-rank matrix optimization landscapes with overparametrization

I will discuss the global nonconvex landscape of low-rank matrix optimization. In particular, we consider the landscape under restricted strong convexity and restricted smoothness assumptions. We focus on the effect of rank overparametrization, that is, optimizing over matrices of rank strictly larger than that of the global optimum. Our main contribution is twofold:

First, we give a positive landscape result for smooth factored formulations, showing that, under certain conditions on the rank parameters and restricted strong convexity/smoothness constants, every second-order critical point is globally optimal. This generalizes and unifies previous state-of-the-art results; in particular, our result allows for nuclear-norm regularization and applies to asymmetric matrix problems without requiring balancing of the factorization. A more statistical version of this result gives, under classical statistical assumptions, optimal recovery of low-rank matrices from noisy linear measurements.

Second, we construct a family of counterexamples showing that our positive result is optimal in terms of all problem parameters. In particular, contrary to popular belief, rank overparameterization does not always improve the optimization landscape. Although our examples are adversarial, empirical evidence suggests that this phenomenon extends to standard statistical matrix sensing settings.

Joint work with Richard Y. Zhang (UIUC).