5
$\begingroup$

Suppose I have a very large dataset of size N, evenly distributed over M computers so that each computer has N/M data points. Suppose I want to fit a model using MLE that requires an iterative method. Also, the N datapoints cannot fit on one computer (hence why they are distributed). What are the disadvantages of the computing the MLE on each computer, and averaging over the parameters of each M to get a new, final set of parameters?

Some pros and cons I've thought of:

  • Pro: it's similar to a bootstrap procedure if M is large, so I can get confidence values quite easily.
  • Con: if my MLE is biased, my average will still be biased (and I can't rely on consistency either)

What are some other considerations I should think about?

$\endgroup$

1 Answer 1

4
$\begingroup$

One thing to keep in mind is that asymptotically, MLEs are going to be normal (under some conditions). Assuming those conditions apply, then if N/M is really large, and observations have been randomly given to computers (so that they should have equally uncertain likelihood functions) those likelihoods should be nearly quadratic near their maxima (with nearly constant second derivative across subsets), and the estimators should be nearly normal with constant variance, and in those circumstances it might arguably make sense to simply average them.

[You're right to worry about bias, of course. ... if the estimator has a certain amount of bias at n=N/M, you're not going to get rid of that by averaging. However, you may be able to take advantage of bootstrapping techniques to reduce bias.]

However, even if those things are not true (we can't assume the asymptotic distribution, for example), it doesn't mean we can't do something about MLE in a distributed way -- at least in some particular situations. Here's one example of something else that might be done (but see the comments at the end).

If the likelihoods are continuous and smooth (/not too wiggly) we can evaluate the entire log-likelihood function in some interval (over a reasonably fine grid) and pass back that information, summing the likelihoods at the end.

For example, let's say N is 10^10 and M is 1000. We pass 10^7 observations to each computer and produce the log-likelihood over a fine grid of values (say over something on the order of 10^3 to 10^4 values), combining all of the log-likelihoods in some suitable manner (with a view to keeping accuracy and not chewing up too much time, such as adding in pairs in parallel, which will take $\sim\log_2(N/M)$ cycles of adding up at the end). This allows us to deal with cases such as multimodality -- but we need to have some sensible idea of where to place our grids to start with, which may require some preprocessing (or some very specific domain knowledge). Then when we identify the location of the overall maximum at the last step, we may be able to smooth our function on the discrete grid by (again) treating it as quadratic in the immediate neighborhood of the optimum, and so obtain an estimate to considerably better than grid-accuracy.

This idea involves passing back (and subsequently adding) vectors for the likelihood rather than just the argmax.

This sort of approach can be adapted to some other circumstances than the smooth continuous one, but that's a very common case to deal with.

This approach should not suffer from the issue of retaining the bias at $n=N/M$ that you'd get with simply averaging the MLEs.

Here's a toy example done on the shape parameter of a gamma density:

enter image description here

The black represents the foll log-likelihood done on the grid, the green and blue are the log-likelihoods for two halves of the data set, and the red is their sum. If you plot the red over the black they (unsurprisingly) coincide.

Fitting a quadratic at the peak suggests the maximum is at about 0.4603 (the grid maximum is 0.46, the true parameter was 0.5).

In practice you could do it in two steps ... over a coarse grid first, then over a much finer grid near the maximum.

This approach would only be reasonable for a problem with very few parameters. (No mention was made of the dimension in the question, but in some situations the dimension is only 1 or 2 or 3). I wouldn't recommend this when there's more than a very small number of dimensions.

$\endgroup$
2
  • $\begingroup$ Can you comment how your approach (grid evaluation) would scale as the dimension of the parameter vector increases? It seems like it would scale exponentially? $\endgroup$
    – Andrew M
    Mar 2, 2015 at 4:59
  • $\begingroup$ @AndrewM It would indeed scale exponentially. No mention was made of the dimension in the question, but in many situations the dimension is small. I wouldn't recommend this when there's more than a very small number of dimensions (in some cases more than 2 or 3 may become infeasible). I should have made that clear in the answer. I'll add this discussion to the answer. $\endgroup$
    – Glen_b
    Mar 2, 2015 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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