I recommend for an overview:

- the original paper "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks", https://arxiv.org/abs/1803.03635

- "Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask" https://eng.uber.com/deconstructing-lottery-tickets/ showing that if we remove "non-winning tickets" before the training, the trained network still works well

(Many things were rediscovered over and over, sure.)

> random steps in high-dimensional spaces unless you align with a ‘large’ eigenvector of the Hessian

In this case, the main observation is different than this one, and has much more to do with sparsity (and an exponentially growing number of connections with each layer).

Well, maybe, but won't the gradient become misaligned just after the first step?

IIRC, ResNet was a good example of that: It's more efficient to learn relu(x + Mx + b) than relu(Mx + b)

One difficulty, though, is that proofs generally /don't/ carry over, and IME a lot of 'classical' methods constrain themselves to provable operations... So at times it can be hard to tell the difference between 'useful folklore' and 'tweak that makes the proofs work.'

I've been delving into sparse coding literature from about ten years ago, and there's a lot of this kind of difficulty... Interestingly, the best sparse coding architectures ended up being very very similar to shallow neural networks. There's a nice 'deep ksvd denoising' paper from a few months back which improves handily on the older sparse coding architectures by bringing in a smattering of ideas from the DNN age; the rant at the end is makes the case for building these 'blended' architectures to get the best of both worlds. https://arxiv.org/abs/1909.13164

I tend to think that the DNN architectures beat the provable-domain architectures for Good Reasons, but the USEFUL response is to build awesome blended architectures that maybe go a long way towards bringing down model sizes and complexity, while increasing explainability.

I also found (in my "learn DL" experiments) that for ReLU the x - relu(Mx + b) version works better (trains faster and achieves better accuracy).

A simple transformation shows you can get the same effect by just flipping the input the output and the weights. The weights are initialized from a symmetric distribution, so the only difference may come from having the input nonevenly distributed around zero.

y = x - relu(Mx + b)

-y = -x + relu((-M)(-x) + b)

y' = x' + relu(M'x' + b)

Have you tried normalizing your input to have zero mean?

The output after ReLU is all non-negatives. So subtraction, actually, does a correction on input.

Yes, I tried normalization on input values and normalization and cross-correlation reduction of outputs of affine transformations. They all have separate positive effects on speed of training and final accuracy.

The only reason that yours might be better is an asymmetric distribution of x o around 0. If you flip the sign on x, you should get the same benefits.

To summarize: your net is not exactly the same as the usual one, but if you train your version on x and I train the usual version with -x, our results will be indistinguishable.

I don't think I can explain this well over comments, think about what happens if you initialize your net from scratch. "Self-contained though experiment: Does it make a difference if you multiply all weights by -1 directly after init? " Once that is clear in itself, think of what happens if you init and flip all your very first inputs, the inputs that you feed to the start of the network.

  Prelude> let relu x = (x + abs x)/2
  Prelude> let res x = x - relu x
  Prelude> let f x = res $ res x
  Prelude> map f [-2..2]
  [-2.0,-1.0,0.0,0.0,0.0]
  Prelude> let res x = x + relu (negate x)
  Prelude> let f x = res $ res x
  Prelude> map f [-2..2]
  [0.0,0.0,0.0,1.0,2.0]
  Prelude> let f x = res $ res $ res x
  Prelude> map f [-2..2]
  [0.0,0.0,0.0,1.0,2.0]
  Prelude> let res x = x - relu x
  Prelude> let f x = res $ res $ res x
  Prelude> map f [-2..2]
  [-2.0,-1.0,0.0,0.0,0.0]

I have to add that you cannot have zero mean outputs of residual layer with the definition res x = x + relu (Ax + b). In that case outputs will have non-zero mean and subsequent layers will have to correct for that.

But I'll try: the sequence of actions (random init, teain your residual net, test your net) is indistinguishable in effect from (random init, train usual net on negated starting input, and test on negated input). The second version will be indistinguishable from running a repeated experiment of the first type with a new random init.

Also, please note that you cannot have zero mean outputs of residual in the res x = x + relu (Ax + b) and you obviously can have zero mean outputs in the subtraction case (res x = x - relu (Ax + b)).

The very fact that in one case you have zero mean outputs and in other case you don't brings me to necessity to point you to SELU: https://towardsdatascience.com/selu-make-fnns-great-again-sn...

This SELU paper demonstrates, in my opinion, the benefits of having zero mean outputs.

(I have to say that in my experiments SELU was not all that beneficial, but other means that bring zero means into existence were)

I think that residual neural network is capable to route around the case of having to learn non-zero means in inputs. So you are right in stating that these two cases will be indistinguishable. I just have to say that having subtraction instead of addition helps neural net to train faster and get better accuracy just because training process have less things to learn.

> please note that you cannot have zero mean outputs of residual in the res x = x + relu (Ax + b) and you obviously can have zero mean outputs in the subtraction case (res x = x - relu (Ax + b)

This is incorrect. You seem to assume x is positive an therefore adding something relu'd onto it will take it further from zero, while your subtractive one can pull it towards and beyond zero. The problem in this reasoning is that in your version you sequentially subtract the residuals so you have the exact symmetric effect, getting further away from zero.

It's like a left hand and a right hand. Not the same, but have the same effect.

I said all I could at this point. If you still have your experiments set up, just try negating your input to the network and initialize randomly. The accuracies observed will be indistinguishable from using your variant. The network is not the same but the training procedure yields a sample from the same distribution.

I hope it clears things up.

I've admittedly been pretty terrible about actually publishing... But definitely have notes and slide decks that could probably be put together into Something.

seems to be "the" numerical optimization textbook

https://podcasts.apple.com/us/podcast/101-the-lottery-ticket...

As you increase number of nodes N in a graph, the number of edges grows at most quadratically, but the number of possible subgraphs grows exponentially.

So even if you use totally random edge weights, with high probability some of those O(2^N) subgraphs will be pretty good.

OP paper is basically providing formal mathematical definitions for these loose notions, then chasing down a bunch of epsilons and deltas to prove that, in fact, good subgraphs actually do always exist (with high probability for large enough N).

From a practical standpoint, the main citation's is pretty informative:

- "What's Hidden in a Randomly Weighted Neural Network?" by Ramanujan et al, https://arxiv.org/abs/1911.13299

This paper actually gives an algorithm which empirically does a decent job at finding a "good" subgraph.

https://www.scientificamerican.com/article/the-adult-brain-d...

We can also train networks that are sparse from the beginning of training (without requiring any special knowledge of the solution): https://arxiv.org/abs/1911.11134. It remains to be shown that this can be done with a speed advantage.

"Sparse Networks from Scratch: Faster Training without Losing Performance" https://arxiv.org/abs/1907.04840 openly says "Currently, no GPU accelerated libraries that utilize sparse tensors exist, and as such we use masked weights to simulate

sparse neural networks.".

However, the situation seems to be very dynamic. See:

- https://github.com/StanfordVL/MinkowskiEngine (Minkowski Engine is an auto-diff convolutional neural network library for high-dimensional sparse tensors)

- https://github.com/rusty1s/pytorch_sparse (an efficient sparse tensor implementation for PyTorch; the official one is slower SciPy https://github.com/pytorch/pytorch/issues/16187; however, I failed to install it - it is not "pip install"-simple)

EDIT:

I checked it now and was able to install pytorch_sparse with one command. It is a dynamic field indeed.

In the other hand, it will trigger research on reducing the size of the networks. That is important, as most researchers don't have access to the computing power of Google and the like.

This looks like to me, adding more and more bullshit to a model while managing to increase its accuracy, eventually leads to a "smaller" model with less bullshit?

That is to say, adding correlated or endogenous variables to a model (over-parameterization), so long as it increases its accuracy, will one day yield, a smaller, more optimized, model with less variables?

If so; why is this news? Isn't this like the fundamental process of most statistics and optimization problems? Or like isn't adding more data (when available) a fundamental method of solving/fixing with multicolinearity?

> this model contains a smaller model, that has similar performance to the trained large model, without training

The point is the opposite. There is a small net X within big net Y, such that training only X gives the same performance as training all of Y.

Edit: See also https://arxiv.org/abs/1911.13299

But there is a theorem that even depth-2 networks can approximate any continuous function F. If the assumptions were the same, then their theorem would imply any continuous function F is w.h.p. approximated by some subnetwork of a depth-4 network.

So what is the difference in assumptions, i.e. what’s the significance of F being computed by a depth-ell network? What functions can a depth-ell+1 network approximate that a depth-ell network can’t? I’d guess it has to do with Lipschitz assumptions and bounded parameters but would be awesome if someone can clarify!

This paper assumes a nn is given with fixed width n and fixed depth l. The main result is that there exists a subnetwork of a nn with depth 2l and width polynomial in n and l that can approximate it arbitrarily well.

It's mathematically interesting, but not a practical advance.

The state of the art when I started following AI in the late 90s was random weights and hyper-parameters chosen with a GA, then optimized with NN hill climbing to find the local maximum. Looks like the research has continued:

https://www.google.com/search?q=genetic+algorithm+neural+net...

All I'm saying is that since we're no longer compute-bound, I'd like to see more big-picture thinking. We're so obsessed with getting 99% accuracy on some pattern-matching test that we completely miss other options, like in this case that effective subnetworks can evolve within a larger system of networks.

I'd like to see a mathematical proof showing that these and all other approaches to AI like simulated annealing are (or can be made) equivalent. Sort of like a Church–Turing thesis for machine learning:

https://en.wikipedia.org/wiki/Church–Turing_thesis

If we had this, then we could use higher-level abstractions and substitute simpler algorithms (like GAs) for the harder ones (like NNs) and not get so lost in the minutia and terminology. Once we had working solutions, we could analyze them and work backwards to covert them to their optimized/complex NN equivalents.

An analogy for this would be solving problems in our heads with simpler/abstract methods like spreadsheets, functional programming and higher-order functions. Then translating those solutions to whatever limited/verbose imperative languages we have to use for our jobs.

Edit: I should have said "NN gradient descent to find the local minimum" but hopefully my point still stands.

Edit 2: I should clarify that in layman's terms, Church-Turing says "every effectively calculable function is a computable function" so functional programming and imperative programming can solve the same problems, be used interchangeably and even be converted from one form to the other.

There are so many people working in this field now, you can be sure a lot of them are doing big picture thinking.

> I'd like to see a mathematical proof showing that these and all other approaches to AI like simulated annealing are (or can be made) equivalent. Sort of like a Church–Turing thesis for machine learning:

Maybe I’m misunderstanding what you are saying, but I think the different optimization techniques/Metaheuristics you’re talking do actually have provably different properties.

Look at all of the effort that has been put into optimizing rasterization in 3D graphics. But meanwhile a student can write a ray tracer in a page of code. I would have preferred that the industry put more effort into the ray tracing side because the abstractions are so much simpler that it would have progressed the state of the art further. Instead we ended up with relatively complex and proprietary implementations of SIMD and that's great and everything but that completely overshadowed the alternatives.

And at the end of the day, users don't care if their 3D framework uses ray tracing or rasterization. All they really see is performance or efficiency under the current paradigm.

So when I see pages and pages of relatively cryptic NN code, I wonder to myself if maybe some other simple curve-fitting or hill-climbing algorithms would produce the same results. Or maybe even spitballing with a GA and letting the computer discover the algorithm would work just as well. It seems like with 10 times the computing power, we could use algorithms that are 10 times simpler. But I'm not really seeing that.

Ok to be a bit more concrete: say you have teams all competing to write the best sorting algorithm. Maybe they all independently derive each of the main ones listed here:

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

But none of them read the fine print to see that big-O complexity wouldn't be judged, just code size. So the bubble sort team ends up winning with the simplest implementation.

Maybe the judges are running the contest in order to find the smallest code that performs sorting. Maybe they have a special computer with a billion cores that can only hold 256 bytes of code each. But the contestants are still thinking linearly in terms of serial execution so submit solutions that really don't help.

I feel like everyone is focusing on the details of whether to use RNNs or CNNs or any of the other types of NN:

https://medium.com/@datamonsters/artificial-neural-networks-...

When we should really have "classifier" algorithm that works like a "sort" function in a programming language. The computer should use the best machine learning model for the use case automagically and not trouble us with implementation details. Then we should be able to build up larger constructs out of those basic building blocks.

I'm not articulating this very well. Just trying to express a general frustration I've had with AI from the very beginning and trying to point out alternatives that could get more people involved and bring us artificial general intelligence (AGI) sooner.