Noise Regularizes Over-parameterized Rank One Matrix Recovery, Provably

2022/02/07 by Liu, Tianyi, Li, Yan, Zhou, Enlu +1
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2202.03535

Abstract

We investigate the role of noise in optimization algorithms for learning over-parameterized models. Specifically, we consider the recovery of a rank one matrix Y^*∈ R^{d× d} from a noisy observation Y using an over-parameterization model. We parameterize the rank one matrix Y^* by XX^\top, where X∈ R^{d× d}. We then show that under mild conditions, the estimator, obtained by the randomly perturbed gradient descent algorithm using the square loss function, attains a mean square error of O(σ²/d), where σ² is the variance of the observational noise. In contrast, the estimator obtained by gradient descent without random perturbation only attains a mean square error of O(σ²). Our result partially justifies the implicit regularization effect of noise when learning over-parameterized models, and provides new understanding of training over-parameterized neural networks.

Related

• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Explicit Regularization in Overparametrized Models via Noise Injection
• A Validation Approach to Over-parameterized Matrix and Image Recovery
• Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations