Neural Network - Sparsity of collaborative based filtering and modelling the prediction problem
You don't have to use full input and output vectors to predict the ratings for a user.

Use the embedding idea and make pairs of (user_id,movie_id) for training. So your input could be like this: (112,1456)=7, it means the user with id number 112 watched the movie number 1456 and the rating was 7.So the size of embedding for the User is  |unique users|  and movies are |unique movies| you call it |M|.

With this trick, we changed the structure of the problem to what we already know. It's regression! 

Now you can add all the bias(and whatever you want) to movies and users embeddings. Use the known loss functions for regression like 
RMSE and you all set. For sure you can add other linear layers, relu, and dropouts on top of this embeddings and make it just like fully connected NN and get even better results.