# Linear regression on large sparse feature set

I have a sparse feature matrix with 50K observations and 150K features. All features are binary. On this I have to run a linear regression. I want just a decent fit.

Data: Let us consider training dataset as a matrix: observations are rows and features are columns. Each column has on average only 10~60 entries of 1s. Similarly, each row has on average 10~60 entries of 1s.

Context: Each row represents a movie and columns represents an actor. I want to predict movie ratings just based on cast. I have removed actors who appeared in less than 5 movies.

What will be the fastest way to run this? I would like to refrain from dimentionality reduction, because test users may not have any actor in common with the reduced feature vector.

• I'm not clear on the reasoning behind dimensionality reduction not working. Could you explain this a little more? – user20160 May 30 '16 at 7:59

You have several times more features than data points, which means the problem is underdetermined. So, you can't use ordinary least squares. The common ways around this are to penalize the $l_1$ or $l_2$ norm of the weights (called lasso or ridge regression, respectively). Lasso will make your weights sparse. Unclear whether you'd want this, because it would mean that your predicted ratings depend only on a sparse subset of the actors. In either case, you'll have to perform a search for a good value of the regularization parameter.

When there are many data points, you can often get faster convergence by training on minibatches than running through the entire dataset. The reason is that many points are redundant, and updating after each minibatch allows more frequent weight updates. Minibatch training can also be faster than stochastic gradient descent (i.e. training on single examples) because the underlying numerical computation libraries can play more tricks to speed things up.

Your weight update rule will also affect convergence speed, and may also require hyperparameter tuning. For example, using gradient descent, you'll have to play with the learning rate, possibly adjusting it over time. More sophisticated update rules are also available. Note that your objective function is convex in the case of linear regression, so this makes life easier than a lot of the situations you'll find people trying to deal with in this literature.

In terms of hardware tricks, you can try running your computation on a GPU. You can also parallelize the hyperparameter search across different machines.

You can run stochastic gradient descent / batch gradient descent to solve the regression objective. Since your feature matrix is sparse, this should run pretty fast.

If the regression equation is $y=Ax$ each SGD step is of the form

$$x_{t+1} = x_t + \eta (y_t - a_t^T x_t) a_t$$

Now if each row $a_t^T$ has just $z$ entries on average, each update step will take approx $2z$ multiplication and $z$ additions.