Implicit Regularization in Matrix Factorization
We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix X with gradient descent on a factorization of X. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, gradient descent on a full dimensional factorization converges to the minimum nuclear norm solution.
This paper studies an interesting observation:
with small enough step sizes and initialization close enough to the origin,
even for an underdetermined / unregularized problem of the form (1),
gradient descent seems to find the solution with minimum nuclear norm.
In other words, starting from an initialization with low nuclear norm,
gradient descent seems to increase the norm of the iterates "just as needed".
The authors state that conjecture and then proceed to prove it for the
restricted case when the operator A is based on commutative matrices.
The paper is pretty interesting and is a first step towards understanding
the implicit regularization imposed by the dynamics of an optimization algorithm
such as gradient descent.
There seems to be many small errors in Figure 1 and 2 (see below).
Detailed comments
-----------------
Line 46: I think there are way earlier references than [16] for multi-task
learning. I think it is a good idea to give credit to earlier references.
Another example of model that would fall within this framework is
factorization machines and their convex formulations.
Line 63: I guess X = U U^T? X is not defined...
Figure 1: 
- the figure does not indicate (a) and (b) (I assume they are the left and right plots)
- what does the "training error" blue line refer to?
- X_gd is mentioned in the caption but does not appear anywhere in the plot
Figure 2:
- I assume this is the nuclear norm of U U^T
- X_gd (dotted black line) does not appear anywhere
- It is a bit hard to judge how close the nuclear norms are to the magenta line
without a comparison point
- How big is the nuclear norm when d < 40? (not dislpayed)
Line 218: I assume the ODE solver is used to solve Eq. (3)?
Please clarify.