Computational Complexity of Dependence Estimation via Generalized Linear Models in Multidimensional Feature Spaces

Usually, when speaking about dependence estimation in big sets of empirical data, it is adopted to suggest that the set of precedents does not fit in the memory of one computer, and some technology of distributed computing is required. However, even if the entire training set can be placed in one computer, the question remains how much time the training process will take. We keep here to the generalized linear methodology of dependence estimation, which covers, in particular, both regression estimation and pattern recognition. It is assumed that the training information (empirical data set) is a rectangular objects/features table. We consider here two kinds of algorithms of regularized empirical risk minimization, which are mutually opposite in their computational complexity relative to the number of features and the number of training objects, i.e., to the two sizes of the objects/features table. The computational complexity of one of them is linear with respect to the number of objects and polynomial relative to the number of features, whereas the other algorithm is of linear complexity in the number of features and polynomial in that of training objects. Thus, for any combination of the two sizes of the objects/features table, we have an algorithm whose computational complexity is linear relative to the greater of two sizes and polynomial with respect to the smaller of them. This property is especially favorable for the typical situation when the number of available features is much greater than that of training examples.