How do various statistical techniques (regression, PCA, etc) scale with sample size and dimension?

Question

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.

Answer 1

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, ...)

Answer 2

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...

Answer 3

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.