# Maximum number of weights in a neural network

Suppose we have a neural network with an input layer, $$n$$ hidden layers, and an output layer. The input layer has $$d_o$$ units ($$d_o-1$$ inputs and a bias). Each hidden layer has $$d_i$$ units (bias is included in $$d_i$$). Finally, the output layer has only one unit. The restriction on the hidden layers is that the total number of units is a constant such that $$\sum_{i=1}^nd_i=Q_o$$.

By denoting the number of output layers $$d_{n+1}$$ (it is equal to $$1$$ here, but is denoted $$d_{n+1}$$ for generality), the total number of weights $$N_w$$ in the network is

$$N_w=d_o(d_1-1)+d_1(d_2-1)+...+d_{n-1}(d_n-1)+d_nd_{n+1}$$

or simply

$$N_w=\sum_{i=0}^{n}d_i(d_{i+1}-1)+d_n$$

The question is: Is there a way to maximize the number of weights $$N_w$$ by varying $$n$$ and the distribution $$d_i$$ for $$i=1,2,..,n$$ while holding the condition $$\sum_{i=1}^nd_i=Q_o$$?

Hint.

We can solve this optimization problem easily using the Lagrangian formulation. Calling

$$f_n = \sum_{k=1}^{n-1} d_k(d_{k+1}-1)+d_n$$

with the restrictions

$$\cases{ d_k \ge 1,\ \ k=1,\cdots, n-1\\ d_n = 1\\ \sum_{k=1}^n d_k=Q }$$

we have

$$L_n = f_n+\lambda\left(\sum_{k=1}^n d_k-Q\right)+\sum_{k=1}^{n-1}\mu_k(d_k-1-\epsilon_k^2)+\mu_n(d_n-1)$$

so the stationary conditions are the solutions for $$n=5$$

$$\nabla L = 0 = \left( \begin{array}{l} d_2+\lambda +\mu_1-1 \\ d_1+d_3+\lambda +\mu_2-1 \\ d_2+d_4+\lambda +\mu_3-1 \\ d_3+d_5+\lambda +\mu_4-1 \\ d_4+\lambda +\mu_5+1 \\ \epsilon_1 \mu_1 \\ \epsilon_2 \mu_2 \\ \epsilon_3 \mu_3 \\ \epsilon_4 \mu_4 \\ d_1-\epsilon_1^2-1 \\ d_2-\epsilon_2^2-1 \\ d_3-\epsilon_3^2-1 \\ d_4-\epsilon_4^2-1 \\ d_5-1 \\ d_1+d_2+d_3+d_4+d_5-Q \\ \end{array} \right.$$

Here $$\lambda,\mu_k$$ are multipliers and $$\epsilon_k$$ are slack variables to transform the inequalities into equations. The nonlinear restrictions $$e_k\mu_k = 0$$ can be handled by a binary expansion associated to the possible $$\epsilon_k=0$$ or $$\mu_k = 0$$ who verify $$\epsilon_k\mu_k=0$$.

The solution for $$n=5$$ gives

$$\left[ \begin{array}{cccccccccccccccc} f_5&d_1&d_2&d_3&d_4&d_5&\lambda &\mu _1&\mu _2&\mu _3&\mu_4&\mu _5&\epsilon _1^2&\epsilon _2^2&\epsilon _3^2&\epsilon _4^2\\ 1 & Q-4 & 1 & 1 & 1 & 1 & 0 & 0 & 4-Q & -1 & -1 & -2 & Q-5 & 0 & 0 & 0 \\ \frac{1}{2} \left(\frac{Q-2}{2}-1\right) (Q-4)+1 & \frac{Q-4}{2} & \frac{Q-2}{2} & 1 & 1 & 1 & \frac{4-Q}{2} & 0 & 0 & -1 & \frac{Q-6}{2} & \frac{Q-8}{2} & \frac{Q-6}{2} & \frac{Q-4}{2} & 0 & 0 \\ \frac{1}{2} \left(\frac{Q-3}{2}-1\right) (Q-3)+\frac{Q-3}{2} & 1 & 1 & \frac{Q-3}{2} & \frac{Q-3}{2} & 1 & \frac{3-Q}{2} & \frac{Q-3}{2} & 0 & 0 & 0 & -1 & 0 & 0 & \frac{Q-5}{2} & \frac{Q-5}{2} \\ \frac{1}{2} \left(\frac{Q-3}{2}-1\right) (Q-3)+\frac{Q-3}{2} & 1 & \frac{Q-3}{2} & \frac{Q-3}{2} & 1 & 1 & \frac{3-Q}{2} & 1 & 0 & 0 & 0 & \frac{Q-7}{2} & 0 & \frac{Q-5}{2} & \frac{Q-5}{2} & 0 \\ Q-4 & 1 & 1 & 1 & Q-4 & 1 & -1 & 1 & 0 & 5-Q & 0 & 4-Q & 0 & 0 & 0 & Q-5 \\ Q-4 & 1 & 1 & Q-4 & 1 & 1 & -1 & 1 & 5-Q & 0 & 5-Q & -1 & 0 & 0 & Q-5 & 0 \\ Q-4 & 1 & 2 & 1 & Q-5 & 1 & -1 & 0 & 0 & 5-Q & 0 & 5-Q & 0 & 1 & 0 & Q-6 \\ Q-4 & 1 & Q-4 & 1 & 1 & 1 & -1 & 6-Q & 0 & 5-Q & 0 & -1 & 0 & Q-5 & 0 & 0 \end{array} \right]$$

Note that the feasible solutions should have all $$\epsilon_k^2\ge 0$$. So among those stationary points we can obtain the maximum: thus for $$Q = \{20, 21\}$$ we have the optimal values.

$$\left[ \begin{array}{ccccccc} f_5&d_1&d_2&d_3&d_4&d_5&Q\\ 65 & 8 & 9 & 1 & 1 & 1 & 20 \\ 81 & 1 & 1 & 9 & 9 & 1 & 21\\ 81 & 1 & 9 & 9 & 1 & 1 & 21 \\ \end{array} \right]$$