# How to overcome symmetry in the solution space when learning a simple neural network?

What are good solution recipes to overcome the problem that in neural network learning, when the solution space has symmetries, learning may eventually stall due to the sum of the gradients over the network inputs converging to a tiny sum even though the individual gradients for each input to the network separately stay relatively big?

As a simple example, consider a neural network with a two-dimensional input and a singly dimensional output with a fully connected first layer, and a MaxPool layer as the second layer. We want the network to learn the function $$\max(x+2y,3x+y)$$ for network input tuples $$(x,y)$$. For this function, two different suitable weight matrices for the linear layer exist as the order of the input values to the MaxPool layer does not matter.

With a standard Adam optimizer, learning sometimes stalls before the MSE is very close to $$0$$. Small variations in the setting can cause learning to succeed, such as using a linear layer without a bias function or different random seeds. However, perhaps there are some commonly used approaches to solve such symmetry problems in a more systematic way?

The following example code in PyTorch exemplifies the problem:

import torch
import numpy
from livelossplot import PlotLosses

# Generate data to learn from
numpy.random.seed(42)
torch.manual_seed(123)
num_samples = 1000
X = torch.rand(num_samples, 2)
Y = torch.max(torch.cat((X[:,0:1]+2*X[:,1:2],3*X[:,0:1]+X[:,1:2]),dim=1),dim=1,keepdim=True)

network = torch.nn.Sequential(
torch.nn.Linear(X.shape,2,bias=True),
torch.nn.MaxPool1d(2,1)
)

liveloss = PlotLosses()
lossfn = lambda x,y: ((x-y)**2).mean()

for i in range(4000):
out = network(X)
l = lossfn(Y,out)
current_loss = l.item()
(l).backward()
opt.step()

logs = {}
logs["err"] = torch.mean(torch.abs(Y - out)).item()
liveloss.update(logs)
liveloss.draw()


The values of the loss function over time (MSE) look as follows: The final MSE is about 0.106. It can be verified that indeed the function to learn has a perfect representation in this network shape by initializing the weight matrix by hand:

with torch.no_grad():
network.weight[0, 0] = 1
network.weight[0, 1] = 2
network.weight[1, 0] = 3
network.weight[1, 1] = 1
network.bias = 0
network.bias = 0


When doing so before the learning process, the MSE starts with 0 and stays 0.

To provide some context for why this problem is interesting, the above example is just exemplifying a problem that occurs in a different context, namely encoding domain knowledge in a neural network with a structure adapted to this knowledge shape and then using neural network learning to fine-tune the model. The domain knowledge encoding may induce many such symmetries in the solution space, and hence just wiggling some aspects of the network or the learning process in an unsystematic way is unlikely to enforce learning across all such symmetries at the same time.

• With a learning rate of 0.02 and without dropout and L2-regularization, the MSE plateaus at a MSE of 0.106 after ~10 epochs
• With a learning rate of 0.02 with dropout of 0.05 before the first (linear) layer and without L2-regularization, the MSE jumps between ~0.2 and ~0.25 after ~10 epochs
• With a learning rate of 0.02 with dropout of 0.05 after the first (linear) layer and without L2-regularization, the MSE jumps between ~0.17 and ~0.21 after ~10 epochs

In all cases, the learned model doesn't look anywhere close to the perfect model with the linear layer weight matrix $$\left(\begin{matrix}1 & 2 \\ 3 & 1 \end{matrix}\right)$$ and the perfect bias vector $$(0,0)^T$$ (for the data set).

• dropout comes to mind. Jul 26 at 2:57
• @EngrStudent Interesting idea. For a quick test, I've injected a "torch.nn.Dropout" layer into the model (tried probabilities: 10%, 1%, 0.1%), and it seems to make the problem even worse. Not actually surprising when thinking about it: with dropout, over node of the linear layer has to take over a bit of the functionality of the other node when it is deactivated. The hand-made "perfect" model mentioned in the case is then even a bit worse for a mean squared error function than what is learned under drop-out. Jul 26 at 11:25
• Maybe your learning rate is too high, also you can try l2-regularization on the weights. Anyway, in principle you could encode symmetries in the way you represent the inputs. Jul 26 at 13:29
• @LucaAnzalone Thanks a lot for the suggestion! In some quick experiments, L2-Regularization (giving "weight_decay=0.0001" to the Adam optimizer) didn't make a difference. Dividing the learning rate by 100 doesn't make a difference either -- the MSE plateaus at 0.106. Could you explain what you mean by encoding the symmetries in the way the inputs are represented? The function to be learned is not actually symmetric in the input value order. The only symmetry is in the solution space - there are 2 optimal weight matrices for the linear layer, which are the same except for the order of the rows. Jul 26 at 14:33
• @EngrStudent I just added additional experimental result descriptions to the original question (at the bottom). Jul 26 at 20:34

learning may eventually stall due to the sum of the gradients over the network inputs converging to a tiny sum even though the individual gradients for each input to the network separately stay relatively big

In my opinion, this is the definition of a minima in a loss function. Infact, given any loss function $$L(\theta) = \min \sum \bar{L}(\theta)$$

and it's gradient, assuming being zero: $$\nabla L(\theta) = \vec{0}$$ you can multiply the loss by any scalar values, and the gradient would not be impacted by it: $$\nabla L(\theta) = \nabla( 10\cdot L(\theta))$$ thus you can make the single gradients as big as you want, or as arbitrarily small as you want, and the cumulative gradient would still be $$0$$

Just think about a logistic regression, if you just make the classes points further, the gradient will be bigger and bigger, but the global minima would stay the same

In your case, you are assuming that theory is sound, thus assuming your neural network as enough representation power to represent your function, and that your samples are enough, that you will end up in a global minima, and that your optimizer is good enough not to be too influenced by the possible stochasticity of the minibatches... this is not usually the case, you can for sure over-parametrize your network, and it will perfectly learn to interpolate your points, but little to no guarantees on the generalization however

• Thanks for your answer! I awarded the bounty because I'm not expecting any additional answer. The thing is that indeed the minimum found is a local minimum, but it's an unwanted one, and I'm searching for standard techniques for leaving it it in the presence of symmetries in the solution space. Aug 4 at 18:59
• @DCTLib unfortunately the loss landscape (convex/non convex) has little to do with the data, but with the model you are working with, but if you find any relevant paper, please let me know, I would be interested in what they have to say Aug 4 at 19:54