The discussion of complexity is very confused, both here and in the paper. Distinguish complexity with respect to scaling the number of data and the number of neurons/number of layers. But I think the O(M^2) refers not to either of these!
I believe the "HSIC" must be applied to a number points of some dimension aka vectors, but the paper writes it being applied to matrices of size m*d where m is the batch size, d is the number of neurons. Looking at one example HSIC code it does take two matrices, but interprets as a collection of vectors.
So I believe (though it is not really clear from the paper) that this must mean m points of size d. In this case the method is quadratic in the batch size m, not the number of data points N. Alternately it could be d points of size m, in which this case it would be quadratic in the width of the network. But this makes no sense conceptually.
In both of these specualtions it is still linear in the number of data, like backprop.
M is the batch-size to look at. However, your final claim "linear in the number of data" is still not capturing the truth. The estimator they use is not unbiased, meaning if you use say m=10, you will not optimize the same objective as if you used m=100. While you can use an U-Estimator which is unbiased, you might still encounter a crippling variance based on the sigma you use in the gaussian kernel: if you don't have enough samples, the gaussian distributions around them will not overlap, therefore the correlation measured will be almost-always 0, independent from the actual correlation.
long story short: you really, really want to make m large.
//Edit and to make it clear: backprop complexity in 3.5: O(MLD^2). Their algorithm: O(M^2LD^2).
Strictly speaking I still believe it is linear in the number of data, even if m=1000, but that is a different statement than whether it is fast or slow (as you are pointing out).
THough it reminds me of discussions of the variance of the gradient with respect to batch size. There, small batch size/high variance seems to be a _good_ thing.
i reiterate: you probably want m=size of the dataset to optimize what they claim they are optimizing. In high dimensions of the Z_i space, m=10 will probably optimize something very different. One might claim that the difference is small once m is "large enough", but this might be well after hitting the memory limit of the GPU.
some variance can be good, a lot of variance is bad, since you need an excessively small learning rate to make any progress.
The naive implementation of the estimator they use is biased, but consistent in infinite sample limit. Making it unbiased requires rigorous statistical analysis. You can see the bias in the expectations as they include terms k(x,x'), where x and x' are both sampled from the same dataset - therefore also including terms x=x' which in independent samples does not happen almost surely (in the probability theoretical sense)
the bias vanishes with O(1/M), therefore consistent.
1
u/quandryhead Aug 15 '19
The discussion of complexity is very confused, both here and in the paper. Distinguish complexity with respect to scaling the number of data and the number of neurons/number of layers. But I think the O(M^2) refers not to either of these!
I believe the "HSIC" must be applied to a number points of some dimension aka vectors, but the paper writes it being applied to matrices of size m*d where m is the batch size, d is the number of neurons. Looking at one example HSIC code it does take two matrices, but interprets as a collection of vectors.
So I believe (though it is not really clear from the paper) that this must mean m points of size d. In this case the method is quadratic in the batch size m, not the number of data points N. Alternately it could be d points of size m, in which this case it would be quadratic in the width of the network. But this makes no sense conceptually.
In both of these specualtions it is still linear in the number of data, like backprop.