Using Funk SVD with SGD?

Problem Detail: 

I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here).

However the framework that we are trying to integrate doesn't support Funk SVD, only SGD (Stochastic Gradient Descent).

Since shouldn't these be compatible? In other words, I should be able to create the U and V matrices with SGD and then treat them like they were made via the Funk SVD process?

Are there any disadvantages of using this versus the algorithm detailed by Funk?

Asked By : jozefg

Answered By : vzn

simon funk is the apparent inventor of a simple & ingenious SVD (singular value decomposition) algorithm during the netflix contest although the algorithm may have predated his discovery (would like to know a ref if anyone knows). SGD = stochastic gradient descent (?) which can be applied to all kinds of optimization problems, incl SVD.

so it depends on your recommender system framework and if its trying to use SVD for recommendations, which is common, but not universal. if it is using SGD to compute the SVD, then that is very similar to the Funk algorithm except the Funk algorithm is probably more prone to get stuck in local minima.

in other words the SGD may find a superior solution but it may take longer. so basically both SGD/Funk are two approaches to computing the U,V matrices & you can do experimental testing to see which gives you the best results or desirable performance.

Funks algorithm is basically just straight gradient descent and SGD is stochastic gradient descent that adds a simulated annealing-like approach to the optimization where earlier in the convergence/search, weights are randomly perturbed to avoid local minima, and then as the search progresses & hopefully converges, the perturbation factor decreases.

fyi for SVD it can be possible to find the optimal solution using matrix based methods even for large matrices (esp if large distributed resources are available) and one could possibly compare either the Funk algorithm or SGD to the actual global optimum.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4806