Implicit Regularization in Matrix Factorization

Implicit Regularization in Matrix Factorization

Suriya Gunasekar, etc.

Intro

谈及quadratic objective的implicit regularization。提出的假设是optimization的选择会影响结果，bias到不同的global minima。

在parameter比较多的情况下，优化问题是underdetermined。也就是有很多个0-training-error的点，其中有很多泛化性能很差。这种泛化能力无法通过模型明确设定的capacity来解释。

反而是，看上去优化算法会将我们bias到某些simple model，最小化某些implicit regularization measure，而泛化能力是与这个measure相关。这篇paper会讨论是什么样的regularization measure，会隐性地被不同优化过程最小化。

作为研究implicit regularization在复杂模型中的作用，这篇paper作为第一步，是分析implicit regularization在matrix factorization model的情况，也就是2-layer NN + linear transfer(activation)。

把nuclear nrom当作这种implicit regularizer，展示了最full dimensional factorization的情况下，使用基于gradient descent的优化方法会将我们带向minimum nuclear norm solution。

Factorized Gradient Descent for Matrix Regression

优化目标是$$U$$

$$ f(U) = | A(U U^T) - y|_2^2

$$

主要分析在两张图上。得出的结论是，当$$U$$满秩，step size足够小，initialization接近于0，gradient descent会得出一个minimum norm solution。