In matrix factorization (especially under the scenario of recommendation system), we often try to factorize a matrix Y into two low rank matrices: $Y=U\cdot V^T$

If we assume there $m$ instances in $Y$ and error satisfies Gaussian distribution, then this leads us to a squared loss function:

$L(U,V)=1/2 \sum_{i=1}^m\Big( y^{(i)} - u^{(i)}v^{(i)} \Big)^2$

Many textbooks just say we could solve this minimization by gradient descent.

However, I think this loss function is non-convex (as its Hessian matrix is not positive semidefinite), why could we solve it with gradient descent? Gradient descent only leads us to local optimum, and there might be multiple local optimum over there, what is the point for getting one of them?

  • 3
    $\begingroup$ Because a local optimum is better than no optimum. Sometimes it may be good enough for the applications. $\endgroup$ – Marc Claesen Nov 4 '14 at 14:06
  • $\begingroup$ @MarcClaesen Is that means we have to run the gradient descent many times and choose the best result one? Because each time we might get different local optimums. $\endgroup$ – ice_lin Nov 5 '14 at 5:18

Sometimes it's the case that "good is good enough" and you don't need to have globally optimal results; an imperfect solution can be better than no solution at all.

It sounds like the practitioners who are using this method are, explicitly or implicitly, making the judgement call that they'd prefer to have this model rather than no model at all.

If it's possible to obtain a better solution with repeated optimization runs, the only conceptual impediment to leveraging that phenomenon is whether or not you risk overfitting, which is often hedged against by use of or .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.