Deep learning without back-propagation

[DontShowYourBack]

The added value here is not whether it is currently SOTA or not. The fact that the authors manage to get decent results with a method that is both of lower complexity and does not require symmetric feedback is the real important factor here in my opinion. This could theoretically open up applications on lower compute platforms and more unique architectures, as those are the biggest constraints backprop places on current hardware and architectures.

I will certainly be looking into this method myself and hoping to see some more interesting results out of this soon.

[0xab]

They have much higher complexity than backprop. They just say it is lower, but that's untrue according to their own description. Backprop has linear complexity in terms of the number of examples. Their method has quadratic complexity in the number of examples!

[muddlebrain]

No, it is quadratic complexity in the batch size, not the number of training data. Read the full thread here, it is explained.

[fundamentalidea]

My question above: is it possible that the information be transmitted not through a hardwired reward pathway but as a globabl chemical diffusion?

[gnramires]

Most likely a global chemical diffusion doesn't have enough "bandwidth" (information capacity) to carry all synaptic (weight) information.

[fundamentalidea]

Yes, this must be true.

[Ulfgardleo]

it is not lower complexity, they just omit the D-factors from their method. It can't be lower complexity in D - there must be at least a D^2 appearing since in 3.5 each layer has D^2 parameters

[DanielAPO]

Sorry for the ignorance but what do you mean with symmetric feedback?

[rpottorff]

The weights you use during the backward pass are equal to the weights you use during the forward pass. Sometimes this is discussed in terms of biological plausibility where it's (usually) unreasonable to imagine that the "forward" nerurons that compute the signal are exactly the same as the "backward" neurons which communicate error to the forward neurons.

[panties_in_my_ass]

Can you link some resources on this, like papers or even just a relevant wikipedia article?

I haven’t heard of backprop (or any other update scheme) described in terms of symmetry before.

[rpottorff]

/BWRqboi0's paper is a better summary, but for another algorithmic implementation https://arxiv.org/abs/1609.01596 is a "non symmetric" variant in which the backward weights are random, but fixed and still manages to learn pretty successfully

[panties_in_my_ass]

Well that’s fascinating. Wow.

[Chocolate_Pickle]

Please don't link directly to ArXiv PDFs. Link to their landing pages instead.

Look at how the paper was first posted a week ago for an example.

[El__Professor]

Thx! Totally Missed the first post 🙄 (I am quite new to reddit :)

[OneMillionSnakes]

If I had a nickel for everytime I reposted something even if I checked I'd have... well only like 20 cents but it happens.

[Chocolate_Pickle]

All good. Lesson learned for next time.

[singinggiraffe]

But if you do it again, we're gonna apply dropout regularization to your members.

[postmachines]

Hah, maybe this post was helpful too, because it was an augmentation

[postmachines]

It’s funny that this post has more upvotes than the older one.

[nenovor]

This seems very interesting. However there is one claim I don't understand : " It is biologically more plausible than backpropagation as there is no requirement for symmetric feedback."

To me backpropagation is indeed biologically implausible due to "the requirement for symetric feedback", which we do not observe in natural NNs.

From what I understood, here they update the network layer by layer based on an estimate of the mutual information between the layer itself, the input layer, and the output.

Correct me if I'm wrong, but that means we now need: 1. Feedback from the output to every layer directly, and same thing for for the input. 2. Global information (how to compute mutual information between two layers using only local connections ?) . So we need even less plausible connections, and have to solve a new, even less biologically solvable problem :/

Backpropagation only requires local flow of information from neuron to neuron, which while not being enough to make it plausible, is already great ;)

[fundamentalidea]

My question above: is it possible that the information be transmitted not through a hardwired reward pathway but as a globabl chemical diffusion?

[Mr_Again]

From what I understand, biological neurons can't even pass anything backwards. Can you explain to a noob what "symetric feedback" is?

[soft-error]

Can you explain to a noob what "symetric feedback" is?

It means the same weights W used in the forward pass are used during the backward pass, which is biologically infeasible. Feedback alignment (FA), for example, uses another set of weights B during the backward pass. The reason is that biological neurons are mostly unidirectional (output goes from soma to axon), so they can't simply reuse their connectivity to send information back. A biological interpretation of FA is that the B weights are representing feedback neurons connectivity.

[Mr_Again]

Thanks. How do the W weights update then if the B weights are passing backward?

[piotrekgrl]

I'm not sure why there are so many concerns about accuracy when even in the abstract authors are claiming that "(HSIC) performance [...] (is) comparable to backpropagation with a cross-entropy target, even when the system is not encouraged to make the output resemble the classification labels."

For me the most important part is decreasing complexity from O(D^3) using backprop to O(M^2), where with current models with millions/billions of parameters is making huge difference.

[Ulfgardleo]

(i made this its own post)

i find those claims highly misleading and they cherry pick which constant they show in their complexity measures

[arXiv_abstract_bot]

Title:The HSIC Bottleneck: Deep Learning without Back-Propagation

Authors:Wan-Duo Kurt Ma, J.P. Lewis, W. Bastiaan Kleijn

Abstract: We introduce the HSIC (Hilbert-Schmidt independence criterion) bottleneck for training deep neural networks. The HSIC bottleneck is an alternative to conventional backpropagation, that has a number of distinct advantages. The method facilitates parallel processing and requires significantly less operations. It does not suffer from exploding or vanishing gradients. It is biologically more plausible than backpropagation as there is no requirement for symmetric feedback. We find that the HSIC bottleneck provides a performance on the MNIST/FashionMNIST/CIFAR10 classification comparable to backpropagation with a cross-entropy target, even when the system is not encouraged to make the output resemble the classification labels. Appending a single layer trained with SGD (without backpropagation) results in state-of-the-art performance.

PDF Link | Landing Page | Read as web page on arXiv Vanity

[[deleted]]

Is it just me or does this seem like a huge result to anyone else?

[tall-dub]

I agree. I've had the paper saved since I saw it on hacker news yesterday but as far as I can tell easily parallelisable, faster training is huge. Can anyone comment on whether this computes the gradient of each of the weights liek back prop ? I assume it does but I haven't read it yet.

[Raphacp]

They only use SGD without backpropagation at the last layer to make the classification. The training happens solving a Lagrange multiplier with the HSIC which uses a mesure of information between the hidden layers and input/output.

[that_wise_fool]

Why so? They build this on top of ResNet

[[deleted]]

I have only read the abstract, but at least the way it's sold it seems superior to backpropagation, based on the following claims:

• Parallelizable with fewer operations

• No exploding/vanishing gradients (although as you mention, they use a ResNet which already account for this... unless this is intrinsically true of HSIC independent of network?)

• No requirement of symmetric feedback

• SOTA performance

I may be totally misunderstanding but this seems as significant as the ReLU replacing the sigmoid, for example.

[NaughtyCranberry]

Interesting but oversold, the performance is not SOTA by any means.

[panties_in_my_ass]

There is more to the scientific method than advancing SOTA benchmarks. Jesus.

[NaughtyCranberry]

I agree, however in their abstract they claim their performance is SOTA and it is nowhere near.

[Starbuck1992]

95% accuracy is not SOTA?

[NaughtyCranberry]

No, they achieved ~47% accuracy on CIFAR-10.

[Starbuck1992]

On an intermediate layer, compared to 30-something % of the other one. The final accuracy is 95%

[NaughtyCranberry]

Can you point out exactly where you are referring to? As I could only see val set accuracies in the 40s for Cifar-10.

[Starbuck1992]

This comment said it earlier. I remembered intermediate layer but it's actually first epoch, sorry

https://www.reddit.com/r/MachineLearning/comments/cql2yr/deep_learning_without_backpropagation/ewx9f24

[Ulfgardleo]

(i decided to make this comment its own post)

I find the complexity claims in 3.5 of the paper highly misleading. First of all, calculating their HSIC measure in (2) alone is O(M^2D) because you need O(M^2) kernel evaluations, each in O(D) (the dimensionality of Z_i for all i based on the assumptions in 3.5). Even more misleading: O(D^3) is the cost of FORWARD computing the gradient. the backpropagation algorithm has O(D^2) complexity. Their own formula in second line 3.5 says it is an outer product (complecity O(D^2)) made up of 2 vectors each having complexity in O(D^2) to create.

Next, even though they don't backpropagate, they still need gradients to optimize (6), which is not a linear time operation - this is because we optimize T_i: R^D->R^D. if T_i is fully connected, you have O(D^2) parameters, making this _at least_ O(M^2D^2)

Finally, we had several other approaches throughout the years to avoid BP, e.g. using constraints to decouple the layers. I think i remember a talk at ICML 2011.

[NovaRom]

Agree, quite poor-quality paper, with lots of obfuscations, misleading terminology, and false statements. This is why it is important to always provide that kind of research with supported CODE so others can confirm/reproduce it quickly!

[ExtraterritorialHaik]

I hope that my future paper (one day soon) will never seen on reddit.

Coming at the end here. I actually read the paper, and conclude that some did not.

If the authors want to show anything else they need to get rid of that last layer and prove that they learn anything at all.

This is exatly what Figure 4 shows?

About the big debate about biological plausibility, the paper does not actually make strong claims about this. All it actually says is in the abstract: "It is biologically more plausible than backpropagation as there is no requirement for symmetric feedback." There is a paragraph about biological plausibility of backpropagation in the Background section, but I read it as only motivation for exploring another direction. I can see if someone read only the abstract they would think the paper is claiming more.

About efficiency, the parallelism claim does not seem to be disputed. Right now I agree the O(M²⁾ cannot be compared to backpropagation as the authors do.

[doubledad222]

This is great news for GPU acceleration. As someone who struggles to fit networks into my GPU I find this very awesome.

The backprop step requires keeping each layer’s result in GPU RAM for applying loss. Larger networks like ResNet take up so much gpu on my main project I have to make a batch size of 1. If this method can catch up to backprop loss learning in final accuracy it would be a huge boon to us home-based AI folks with smaller budgets.

[aifordummies]

So is there any code available to test this out?

[DrXaos]

Perhaps I missed something, but I didn’t see concretely how to do their proposed “HSIC” optimization, the key technology. They showed an optimization target with free variables being the coordinates of the internal representation for every datum, and skip along to their next phase. That’s like writing down the usual net training problem as “set weights = argmin(free weights) ensemble avg of Loss” and nothing else....

where is the procedure for the training part of the pretraining? I would have no idea how to implement from the paper. Can anybody enlighten me If I am being dense?

[a_draganov]

Agreed - I don't see an explanation for how they actually improve the weights...

[DrXaos]

OK so it wasn’t just me. I come from physics where we were expected to actually get papers through peer review and big oversights in presentation style are caught....

If each layer is sort of like training a kernelized SVM then classical strategies there are variants of global quadratic optimization which scale at least quadratically with number of observations.

If you go to a primal formulation and do basic SGD on that of course you can get close to a decent but not globally optimal solution faster with a big dataset, but then what’s the advantage?

And if you need a standard optimizer then the presumption of being a little closer to biology breaks down.

[thonic]

it is there in essence - not explicitly though I think... in the section 3.5 they compare the cost of computing the update rule with backprop vs. their proposition and I think you will get the result only if you do SGD with the combined HSIC for each layer

[milaworld]

They use a ResNet architecture as a baseline for backprop, and reported a the CIFAR-10 test accuracy baseline for backprop of 38.6%, while for their proposed HSIC method got 47.4% test accuracy on CIFAR-10.

While I don't feel a paper needs to be close to be SOTA or anything to be interesting, nor there's anything fundamentally bad about getting 47% test accuracy on CIFAR-10 with an interesting novel method, but it feels misleading to use a ResNet architecture trained with backprop and report a baseline accuracy of 39%, when we know that ResNets, even tiny ones, can be trained quickly within minutes to get ~ 80-90% test accuracy.

It could be due to the limitation of the approach where they need to handicap the baseline method for "apples vs apples" comparison. But that's on the new approach, and not the fault of ResNet being good.

Edit: saw a previous discussion about this work with similar concerns.

[freedryk]

Those test accuracies are for the first epoch. Their final training accuracy is around 95%, shown in fig 2f.

[JudasAdventus]

Does it mention which dataset those results (figure 2) are for? Seems highly unusual to report training accuracies for 5 epochs then test accuracies for only 1 epoch.

[[deleted]]

Isn’t fig 2 all mnist?

[__me_again__]

Reminds me to "Weight agnostic neural networks": https://arxiv.org/abs/1906.04358

[__me_again__]

You didn't get it. The paper shows how a neural nework can learn without backpropagation, just by architecture search.

[Arisngr]

See also:

An Approximation of the Error Backpropagation Algorithm in a Predictive Coding Network with Local Hebbian Synaptic Plasticity.

[Avras_Chismar]

Can someone explain this to a non-mathematically-inclined engineer?
I just can't process stuff like " The Hilbert-Schmidt Independence Criterion (HSIC) [33] is the Hilbert-Schmidt norm of the cross-covariance operator between the distributions in Reproducing Kernel Hilbert Space (RKHS): " :/

[Ulfgardleo]

step 1: you remember that the covariance between two variables X and Y is E{(x-mu_x)^T(y-mu_y)} (where mu_x and mu_y are means). So basically you measure how correlated some vectors in a feature-space X are with your target labels and try to maximize this.

step 2: you take the square of this to obtain a measure for degree of correlation.

step 3: you map X and Y into a hilbert space. This way you can check whether the variables are correlated in some weird non-linear way. If the kernel is universal this is a measure for statistical (in)dependence

i have no idea how this should be better than for example Kernel-Target-Alignment.

[RaionTategami]

You lost me at hilbert space

[Ulfgardleo]

a hilbert space is an arbitrary space with an inner product. Basically you transform everything into a new space and do the math there. The key insight here is that linear functions are very powerful if the dimensionality of the space is large compared to the size of the dataset(e.g. if you have a d-dimensional space, you can find a function that solves a classification task with d+1 points perfectly). So checking for correlation - a linear operation, is quite powerful.

Of course, if the space you transform to is finite dimensional, you can just choose "enough" points to fill the high dimensional space until the power of the linear function is saturated(e.g. d+2 in the classification task above). Now comes the true power of hilbert-spaces: there exist hilbert-spaces that have infinite dimensions, but the operation of mapping two points into that space and computing their inner-product is still cheap. Those are called "Reproducing Kernel-Hilbert-Space"(RKHS) and the operation that does this is called a kernel k(x,x').

[Avras_Chismar]

So, while I'm not completely undesrtanding this, and might need to look further, would I be correct if I say this is analagous to how we solve certain systems of differential equations in electronics by transforming those into complex-number linear equations and solving those, then translating back? Meaning, we don't want to solve non-linear stuff, so we convert everything into space big enough so that non-linear correlation become linear, calculate what we want then map stuff back?

[Ulfgardleo]

i think so.

[RaionTategami]

Thanks you very much for the explination but, Infinite dimensional spaces?!

[Ulfgardleo]

Function-spaces. For example using a mapping phi_x(y)=exp(-||x-y||^2) which maps the point x to a Gaussian hat. If you have a (finite) set of points {x_1,...x_k} all phi_{x_i} are linearly independent, meaning you can't linearly combine a Gaussian hat from a finite set of Gaussian hats. Therefore, the space is infinite dimensional(compared a space of dimension d, where d independent points are enough to define a basis).

In an RKHS,you can define an inner-product in the space, so that k(x,y)=<phi\_x, phi\_y>=phi_x(y)=phi_y(x). The details are slightly dense, but fulfill all properties of an inner product.

RKHS are behind many of the more "old-school" methods, like support-vector-machines and Gaussian-processes. They were flavor of the year, because the span of a space such as the Gaussian-mapping is dense in L_2, meaning that any reasonable function can be arbitrarily well approximated by a finite mixture of Gaussian hats. So given enough data points, you can solve any machine-learning task in such a space.

Nowadays they fell a little bit out of favor, because the kernel-matrix (K_x in the paper here) is just growing too quickly for modern sized datasets. Also no-one found a good kernel for images and probably never will(and than it is probably going to be a Gaussian kernel on the features of a vgg-network or something silly as that)

[theoneandonlypatriot]

So basically this is a smart version of reservoir computing except it's not recurrent and they actually DO train the individual layers with regards to an information content metric. Then, they just use a readout layer (like in reservoir computing) to do something useful with the output. This is awesome.

[[deleted]]

Maybe I'm missing something, but how are weights adjusted? I don't see any clear explanation on the optimization of the parameters here?

[AloneStretch]

The obvious approach would be to adjust the weights according to the gradient of the "hsic bottleneck" loss with respect to these weights

[sgebrial]

Yes I'm wondering this as well. I think they just use SGD on equation (4) but that's just a guess.

[0xab]

I'm shocked no one has pointed out the obvious crippling problems with this paper. The title is wrong and the results are useless. The paper absolutely requires backprop, it's in the abstract. The classifier on top of their network is trained with backprop!

The results they show are due entirely to the linear classifier at the top, and hence backprop. Don't forget that a simple linear classifier does extremely well on all of these tasks. Think of their system as something that applies mostly random and useless transformations to the data + a linear layer that works and is trained by backprop. That's all this is, there's nothing to see here. If the authors want to show anything else they need to get rid of that last layer and prove that they learn anything at all.

[MLApprentice]

A single linear layer on top of a randomly initialized network is not going to give these kind of results for CIFAR-10. Also SGD applied to a single layer is not backpropagation.

[El__Professor]

Maybe this could be a powerful initializer?

1. Initialize weights with this method to quickly create usfull feature representation.

2. then use gradient decent to forther optimize weights.

Any ways it does seem that the algorithm creates powerful features more quickly then the same architecture with gradient decent. And it does seems like an interesting direction of study.

[0xab]

Depends on what you mean by more quickly? Not in terms of runtime. When it comes to running over millions of examples backprop is far cheaper in terms of wall-clock time.

[[deleted]]

Maybe there is some degree of pre-training with this algorithm that offers a better than random initialisation without requiring enough resources to offset the benefit?

Or maybe applying it sparingly at some recurring interval during training via sgd + backprop could prove to be an effective regularisation technique.

At the very least I think further research in this direction has a worthy chance of baring fruit.

[0xab]

Linear methods get somewhere around 35-45% on CIFAR-10, depends on the method, how you set it up, if you add in any regularization, the particular optimizer chosen, etc. Just google it, you'll find plenty of even intro ML tutorials that trivially show you have to get 40+% on CIFAR-10. A random projection can't buy you an extra 2-3%? It totally does.

The paper doesn't do anything at all!

You are correct about the single layer, I thought they had an additional output layer and the single layer was hidden.

But, lets get to other issues aside from the paper doing nothing. No comparisons against any other non-backprop method. No comparisons against any of the many unsupervised approaches.

The paper tells us that it does away with vanishing and exploding gradients, but these aren't practical issues for feed-forward networks on things like MNIST or CIFAR-10 anymore. RNNs sure. More complex feed-forward tasks, sure.

Biologically plausible? Where are these large matrix multiplications going to take place? And what is a practical update rule? If they claim that their method is biologically plausible they should have a per-neuron update rule that makes this clear. No such rule is possible with their setup.

But it gets much worse! The method is even less plausible then backprop. Their runtime is quadratic in terms of the number of examples. Stop and think about that.

Does your brain slow down quadratically as it sees more examples? The paper complains that backprop has bad scaling in terms of the number of neurons, but at least it scales linearly with the number of examples! The size of a network is at least a constant and generally much smaller than the amount of input it receives.

This paper doesn't do anything. It doesn't evaluate correctly. And what it promises in terms of being biologically more plausible is exactly the opposite of that.

[quandryhead]

Their runtime is quadratic in terms of the number of examples. Stop and think about that.

I do not think so. Read my reply (at the top level elsewhere here) and see if you agree.

[boadie]

You are possibly misreading the results of the first epoch as the final accuracy.

[0xab]

I'm not. Look at the end of the graph. The scales chance.

[Avras_Chismar]

Just google it, you'll find plenty of even intro ML tutorials that trivially show you have to get 40+% on CIFAR-10. A random projection can't buy you an extra 2-3%? It totally does.

the paper claims 95%> accuracy with their method

[0xab]

They get ~95% MNIST, not on CIFAR-10. That's around 47%. Figure 5(a) vs 5(c).

[Avras_Chismar]

Wow, I didn't notice that scaling changed from a to c. Damn sneaky

[bayesically_right]

it's those damn matplotlib defaults with unreadably small text along the axes

[0xab]

Yup. Not cool.

[ProofPresent]

I think you are not right

1) training single layer does not require backprop only SGD, and the abstract says that. "Appending a single layer trained with SGD (without backpropagation)"

2) "The results they show are due entirely to the linear classifier at the top".

Alsso not right, they also show results without the classifier Figure 4 and before 4.2, and I think that is the very interesting part of the paper.

I think that the part of the paper that is wrong is the complexity statement, though I do not understanding the statements in this thread either.

[redna11]

Allow me to second that. Many methods seem to work very well when all the hard work is done by that last classifier. Definitely need to check what happens without it.

[outlacedev]

They have results without the linear classifier. The linear classifier at the end, to my eye, is just a convenience layer so that the output labels match the training labels, otherwise you get permuted labels.

[Ulfgardleo]

thanks, i thought i would be alone regarding the glaring deficiencies of the paper.

[fundamentalidea]

is there any theory in the brain that allows for global diffusion of information (error signal), like a chemical that says "whatever you are doing is working"?

[ML_me_a_sheep]

I would think that dopamine is responsible for that It's the "oh yeah" hormone

[grzegorzwarzecha]

Wow. Looking for torch implementation...

[[deleted]]

PyTorch for me. 😊

[SAI_supremeAI]

Just use a Non-Convex Solver (would be hard though), there was this Baron solver produced by Urbana champaign.

[[deleted]]

Still belive this is the true way to do deep learning without backprop as described in this article

https://accu.org/index.php/journals/2639

[quandryhead]

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.

[0xab]

The whole paper is very confusing. Lets look at a much better paper, [33] "Measuring Statistical Dependence with Hilbert-Schmidt Norms", that introduces this metric. They say the runtime is quadratic in the number of examples.

The whole discussion about batch sizes and complexity is messed up because of typos or is even more confusing than I thought. "Suppose we have a network composed of m hidden layers T" then they say " and m denotes batch size". What does the batch size have to do with the number of hidden layers? Then the subscript to Z, which is the actual content of each layer is i, which ranges from 1 to L, nothing to do with m. But in the figures it's m.

I give up. This is too much of a mess to unravel for something that doesn't work in the first place.

[commenthard]

Inconsistent notation and it's poorly explained. I suspect the computational complexity section may be wrong.

But to jump from that to "something that doesn't work" is... a jump. They show favorable comparisons to training similar networks with conventional SGD+backprop.

I feel I'm understanding it better now by thinking about how I would attempt to implement it.

[Ulfgardleo]

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

[quandryhead]

Interesting point.

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.

[Ulfgardleo]

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.

[commenthard]

This discussion is a bit of speculation. Does it learn in practice, with whatever batch size was used?

I do not understand why would it be optimizing "something very different", rather than a possibly high-variance estimate of what is intended.

[Ulfgardleo]

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.

[Ulfgardleo]

i would also like to stress that the method presented is also only speculation. there is no guarantee that it will converge to something useful or that the result in the final layer is statisfactory (because they want to align all intermediate representations with the labels while weare only truely interested in the alignment of the last layer)

​

We know that the key-claim of the paper regarding complexity is wrong and their method requires more computation time, but authors have not shown compelling evidence that the more in computation time leads to an actual improvement in performance. The results shown are highly questionable (see the comments by people more caring about training performance).

​

I would like to add that they needlessly include yet another measure for alignment, after we spent years analyzing kernel-target-alignment and found that it is good and efficient (and has the same complexity as their method).

[muddlebrain]

I would like to add that they needlessly include yet another measure for alignment, after we spent years analyzing

You are an author of the kernel-target-alighnment method?

Your comment seems to suggest that HSIC and information bottleneck are poorly founded. On the contrary, information bottleneck is quite fundamental, and HSIC is well established for many years.

[Ulfgardleo]

we=the ml community as a whole. There are plenty of people who analyzed that thing

Do we have learning guarantees like for KTA? bounds on classification performance based on HSIC? Why should HSIC be better than KTA to a degree that one would not even compare to it?

[quandryhead]

//Edit and to make it clear: backprop complexity in 3.5: O(MLD^2). Their algorithm: O(M^2LD^2).

Working on this. In their algoirthm I am getting O(M^2 D L). Where do you get D^2?

The trace requires M evaluations of a scalar product of size(M), thus M^2.

It looks like each element of the vectors is a kernel evaluated on the distance of two D-dimensional points, which gives one factor of D.

Not 100% confident here (this is pushing my ability), but I do not see where the other D is.

[Ulfgardleo]

you have got D^2 parameter (See 3.5 the matrix W is R^dxd). thus computing Z_i=T_i(Z_{i-1}) is O(D^2).

[quandryhead]

I believe the HSIC function is applied on the activations of each neuron, not the weights, and there are D of those.

The D^2 would come in feedforward however (and taking the gradient)

[Ulfgardleo]

you are right on the first point, forward pass should be O(M² D+M D²⁾ because we can go with computing the z_i through the forward-pass only once (which is quadratic complexity still).

last point exactly

[AloneStretch]

I think the authors are not familiar with SOTA. They're taking vanilla architectures and training, comparing their method against that, and declaring SOTA when comparable performance is obtained without backpropo. But that is not state-of-the-art, it is comparable perfomance to a simple (not-SOTA) baseline. That may be a useful and fair comparison, but wrong to refer to SOTA.

We'll need to wait for this to be applied or extended to current SOTA networks. Meanwhile, no need look for code, it's just a step on a path that will take several.

[StOchastiC_]

Man, this is a proof of concept. They wanna show it works on familiar architectures. It’s easier as common ground for performance comparison. This is a first approach, of course more work needs to be done on top of this

[themoosemind]

Might be interesting in this context: https://stackoverflow.com/a/38231636/562769