Maximum number of weights in a neural network

Question

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$?

Answer 1

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] $$