10
$\begingroup$

Is there a known general table of statistical techniques that explain how they scale with sample size and dimension? For example, a friend of mine told me the other day that the computation time of simply quick-sorting one dimensional data of size n goes as n*log(n).

So, for example, if we regress y against X where X is a d-dimensional variable, does it go as O(n^2*d)? How does it scale if I want to find the solution via exact Gauss-Markov solution vs numerical least squares with Newton method? Or simply getting the solution vs using significance tests?

I guess I more want a good source of answers (like a paper that summarizes the scaling of various statistical techniques) than a good answer here. Like, say, a list that includes the scaling of multiple regression, logistic regression, PCA, cox proportional hazard regression, K-means clustering, etc.

$\endgroup$
  • $\begingroup$ This is a good question. A lot of statistics books talk about the theoretical aspects of high-dimensional data and not the computational aspects. $\endgroup$ – shadowtalker Aug 6 '14 at 0:23
  • $\begingroup$ In many cases, the original literature will discuss complexity. But often theoretical complexity is useless. QuickSort has a worst-case of O(n^2), but often is the fastest - faster than HeapSort, which has worst case O(n log n). If you do a little research, you will find out complexity results for many algorithms - if known. E.g. PCA being O(n d^3), k-means being O(n k i d) etc. $\endgroup$ – Has QUIT--Anony-Mousse Aug 16 '14 at 10:39
6
$\begingroup$

Most of the efficient (and non trivial) statistic algorithms are iterative in nature so that the worst case analysis O() is irrelevant as the worst case is 'it fails to converge'.

Nevertheless, when you have a lot of data, even the linear algorithms (O(n)) can be slow and you then need to focus on the constant 'hidden' behind the notation. For instance, computing the variance of a single variate is naively done scanning the data twice (once for computing an estimate of the mean, and then once to estimate the variance). But it also can be done in one pass.

For iterative algorithms, what is more important is convergence rate and number of parameters as a function of the data dimensionality, an element that greatly influences convergence. Many models/algorithm grow a number of parameters that is exponential with the number of variables (e.g. splines) while some other grow linearly (e.g. support vector machines, random forests, ...)

$\endgroup$
  • $\begingroup$ I'm not sure I agree with this: when designing an algorithm for a statistical problem, a lot of concern goes into the complexity of each iterative step (and is usually documented in a manuscript). But as you point out, often it's not that easy to summarize, as two algorithms with the same complexity per iteration may perform very differently due to necessary iterations. That being said, it's very rare that the number of iterations required grows faster than O(log(n) ). $\endgroup$ – Cliff AB Sep 26 '15 at 2:12
5
$\begingroup$

You mentioned regression and PCA in the title, and there is a definite answer for each of those.

The asymptotic complexity of linear regression reduces to O(P^2 * N) if N > P, where P is the number of features and N is the number of observations. More detail in Computational complexity of least square regression operation.

Vanilla PCA is O(P^2 * N + P ^ 3), as in Fastest PCA algorithm for high-dimensional data. However fast algorithms exist for very large matrices, explained in that answer and Best PCA Algorithm For Huge Number of Features?.

However I don't think anyone's compiled a single lit review or reference or book on the subject. Might not be a bad project for my free time...

$\endgroup$
  • $\begingroup$ Thanks, that's very helpful! If you do a literature review for various predictive modelling techniques, I'm sure it would get referenced a lot. It would be very helpful for people who want to differentiate between which algorithms to use in large n or large p cases, or for medium values of those for more precise calculations. Do you happen to know how some of the more obscure techniques scale? (Like Cox proportional hazard regression or confirmatory factor analysis) $\endgroup$ – Bridgeburners Aug 8 '14 at 13:31
  • $\begingroup$ Unfortunately no, but if I ever do that review I will try to be comprehensive. I'd hardly call Cox regression "obscure," at least in my field. $\endgroup$ – shadowtalker Aug 19 '14 at 16:31
5
$\begingroup$

I gave a very limited partial answer for the confirmatory factor analysis package that I developed for Stata in this Stata Journal article based on timing the actual simulations. Confirmatory factor analysis was implemented as a maximum likelihood estimation technique, and I could see very easily how the computation time grew with each dimension (sample size n, number of variables p, number of factors k). As it is heavily dependent on how Stata thinks about the data (optimized to compute across columns/observations rather than rows), I found performance to be O(n^{0.68} (k+p)^{2.4}) where 2.4 is the fastest matrix inversion asymptotics (and there's hell of a lot of that in confirmatory factor analysis iterative maximization). I did not give a reference for the latter, but I think I got this from Wikipedia.

Note that there is also a matrix inversion step in OLS. However, for reasons of numerical accuracy, no one would really brute-force inverse the X'X matrix, and would rather use sweep operators and identify the dangerously collinear variables to deal with precision issues. If you add up $10^8$ numbers that originally were in double precision, you will likely end up with a number that only has a single precision. Numerical computing issues may become a forgotten corner of big data calculations as you start optimizing for speed.

$\endgroup$
  • 2
    $\begingroup$ Math formatting does not work on DataScience? Really? May be we should ask to get it. $\endgroup$ – StasK Aug 14 '14 at 17:29
  • $\begingroup$ Good point about numerical accuracy. $\endgroup$ – shadowtalker Aug 15 '14 at 0:24

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.