Review for NeurIPS paper: Implicit Regularization in Deep Learning May Not Be Explainable by Norms

Summary and Contributions: Reconstruction of a low-rank matrix from its linear measurements is a canonical problem in machine learning and signal processing. There has been an intense effort to establish theoretical guarantees and design efficient algorithms for solving these problems. Of these, the most prominent two methods are: 1- Convex optimization approach - Nuclear-norm regularization. In particular, the non-convex factorization approach has received increasing attention due to the reduced arithmetic and storage costs. Recently, Gunasekar et al. (2017) reported a surprising observation, that the non-convex factorization approach (when solved with gradient descent) generalizes (i.e., recovers the low-rank matrix of interest) even when the factors U and V are full dimensional (i.e., not tall, hence UV' does not impose an explicit low-rank structure).