As you made this experiment available on Colab, I was able to test my thoughts on it, which was handy.
First, the simple "fix" is to run many epochs. Eventually even your relatively small and simple network will learn to predict whether the mean of a large randomly-generated vector is greater than the expected value of all the elements. In my tests, after 20 epochs, the neural network reached 90% accuracy on the task, but accuracy still varied a lot. Eventually, after 100 epochs or so, it became more stable, but accuracy could still vary significantly, ranging between 77% and 99%.
You can improve learning rate and stability for this task by:
Changing the optimiser from basic mini-batch SGD to Adam. This made the most difference.
Increasing number of neurons in hidden layer. Your example had 8, I increased to 64. This improved stability.
Changed activation to LeakyReLU. Again this was for stability, as I noticed that sometimes the network would get a prediction very confidently wrong, which generated large destabilising gradients. Decreasing learning rates or clipping gradients would also help with this issue.
With these changes, the neural network was 97% accurate after the first epoch, although it still fluctuated as low as 90% accuracy in some epochs, it tended to stay around the 98% mark, with a few epochs reaching 99%.
The problem is also much easier for smaller tensor sizes. A tensor of size 10 is trivially solved in the first epoch. A tensor of size 100 takes longer, but the function is still learned faster and to a higher accuracy.
Why is this problem so hard?
It is not uncommon in machine learning to find problems that are easy to state or set up, but that turn out to be more challenging in practice.
It should be possible to construct a simple neural network by hand that scores 100% on this task. However, that is using knowledge about the target function that the gradient descent algorithm has no access to.
The problem of triggering this "larger mean than expected" step function based on learning from examples becomes harder the more input variables there are (the larger your initial tensor is). There are at least two effects in play:
Each input is a free variable that interacts with all the other variables, and is equally important.
The variance of the mean is reduced for each new input, making the step function more sensitive, and requiring the approximation to be more accurate.
A simple feed-forward neural network has very few built-in assumptions about the nature of the function being approximated. It cannot "discover" or take advantage of the symmetry between inputs that is obvious to you as the experimenter. This is related to the no free lunch theorem in that you could build a different model type that took more advantage of the symmetry between inputs and that should learn your "step function over the mean" faster and more robustly. It would do better at this problem, but would probably do much worse at image recognition where neural networks are state of the art.
I suspect there may be two other effects at work making this task hard, but these are just guesses:
A simple "true" neural network for this function would have all weights identical in the first layer (there are other solutions, but this applies to the simplest constructed network). This is usually an awkward setup for a neural network that should be avoided (it prevents learning for most target functions), and may not be stable.
The "mode" of the two populations (vectors with sum below mean and vectors with sum above mean) coincide. The distribution of the mean is effectively the normal distribution, and your function cuts it down the middle. That means many training items will appear to be really similar, there is no "margin". Even a small error in the class separation will generate relatively large numbers of false positives or false negatives. I think this is what drives the unstable accuracy values.