Year: 2018

Abstract:
The gap between the empirical success of deep learning and the lack of strong theoretical guarantees calls for studying simpler models. By observing that a ReLU neuron is a product of a linear function with a gate (the latter determines whether the neuron is active or not), where both share a jointly trained weight vector, we propose to decouple the two. We introduce GaLU networks — networks in which each neuron is a product of a Linear Unit, defined by a weight vector which is being trained, with a Gate, defined by a different weight vector which is not being trained. Generally speaking, given a base model and a simpler version of it, the two parameters that determine the quality of the simpler version are whether its practical performance is close enough to the base model and whether it is easier to analyze it theoretically. We show that GaLU networks perform similarly to ReLU networks on standard datasets and we initiate a study of their theoretical properties, demonstrating that they are indeed easier to analyze. We believe that further research of GaLU networks may be fruitful for the development of a theory of deep learning.

heading: 1 INTRODUCTION
text: An artificial neuron with the ReLU activation function is the function fw(x) : Rd → R such that fw(x) = max{x>w, 0} = ( 1x>w≥0 ) · ( x>w ) .
The latter formulation demonstrates that the parameter vector w has a dual role; it acts both as a filter or a gate that decides if the neuron is active or not, and as linear weights that control the value of the neuron if it is active. We introduce an alternative neuron, called Gated Linear Unit or GaLU for short, which decouples between those roles. A 0− 1 GaLU neuron is a function gw,u(x) : Rd → R such that
gw,u(x) = ( 1x>u≥0 ) · ( x>w ) . (1)
GaLU neurons, and therefore GaLU networks, are at least as expressive as their ReLU counterparts, since fw = gw,w. On the other hand, GaLU networks appear problematic from an optimization perspective, because the parameter u cannot be trained using gradient based optimization (since ∇ugw,u(x) is always zero). In other words, training GaLU networks with gradient based algorithms is equivalent to initializing the vector u and keeping it constant thereafter. A more general definition of a GaLU network is given in section 2.
The main claim of the paper is that GaLU networks are on one hand as effective as ReLU networks on real world datasets (section 3) while on the other hand they are easier to analyze and understand (section 4).

heading: 1.1 RELATED WORK
text: Many recent works attempt to understand deep learning by considering simpler models, that would allow theoretical analysis while preserving some of the properties of networks of practical utility. Our model is most closely related to two such proposals: linear networks and non-linear networks in which only the readout layer is being trained.
Deep linear networks is a popular model for analysis that lead to impressive theoretical results (e.g. Saxe et al. (2013); Kawaguchi (2016); Lu & Kawaguchi (2017)). Linear networks are useful in order to understand how well gradient-based optimization algorithms work on non-convex problems. The
weakness of linear network is that their expressive power is very limited: linear networks can only express linear functions. It means that their usefulness to understand the practical success of standard networks is somewhat limited.
Training only the readout layer is an alternative attempt to understand deep learning through simpler models, that also gave theoretical interesting results (e.g. Saxe et al. (2011); Mairal et al. (2014); Daniely et al. (2016)). The idea is that all the layers but the last one implement a non-linear constant transformation, and the last layer is learning a linear function on top of this transformation. The weakness of this model is that there is a big practical difference between training all the layers of a network and training only the last one.
Our model is similar in certain aspects to both of those models, but it enjoys a much better practical utility than either one. See section 3 for an empirical comparison.

heading: 2 GALU NETWORKS
text: Recall the definition of a basic GaLU neuron given in equation 1. We consider a more general GaLU neuron of the form
gw,u,σ(x) = σ(x >u) · ( x>w ) for some non-linear scalar function σ : R → R. If σ is differentiable, we could train the vectors u with gradient based algorithms, but the focus of this paper is on untrained gates. That is, we assume that the vectors {u} are kept to their initial values throughout the optimization procedure and only the linear part of the GaLU neurons is being optimized.
GaLU networks with a single hidden layer have the following property: for any given example, the values of the gates in the network remain constant. In networks with more than one hidden layer this not true. Consider a standard fully connected feed-forward network, let x(0) be the input to the network and let x(1),x(2), . . . be the inputs to intermediate layers of the network. The output of a GaLU neuron at layer i will be σ(x(i−1)>u) · ( x(i−1)>w ) . So while the filter parameter vector, u, is not optimized upon, the value of the gate, σ(x(i−1)>u), can change as x(i−1) changes. This adds an additional complication to the dynamics of the optimization that we wish to avoid.
An alternative way to define a GaLU neuron at layer i is σ(x(0)>u) · ( x(i−1)>w ) . In that case, the value of the gate is determined by the original input, and only the linear part depends on the output of the previous layer of the network. We call such a neuron a GaLU0 neuron, and a GaLU0 network is a network where all the neurons are GaLU0 neurons. In GaLU0 networks the gate values remain constant along the training, producing simpler dynamics.

heading: 3 EMPIRICAL SUCCESS
text: In order to check the hypothesis that effectiveness of ReLU networks stems mostly from the ability to train the linear part of the neurons, and not the gate part, we tested both GaLU01 and ReLU networks on the standard MNIST (LeCun & Cortes, 2010) and Fashion-MNIST (Xiao et al., 2017) datasets. For both, we used PCA to reduce the input dimension to 64, and then trained a two hidden layers fully-conneted networks on them, with k hidden neurons at each hidden layer. Figure 1 summarizes the results, showing that GaLU0 and ReLU achieve similar results, both outperforming linear networks of the same size. Training only the readout layer of a ReLU network gave much poorer results (which were omitted from the graphs for clarity).
4 THEORETICAL SIMPLICITY: SOLVING Rd → R1 PROBLEMS WITH ONE HIDDEN LAYER NETWORKS
We now turn to some very basic theoretical analysis of GaLU networks with a single hidden layer. Our goal is to show that GaLU networks are simpler to analyze than standard networks.
1We used the logistic sigmoid function, as it gave better results on the test set than the binary gate function.
Consider a GaLU network with a single hidden layer of k neurons: N (x) = ∑k j=1 αjgwj ,uj (x). A convenient property of a GaLU neuron is that it is linear in the weights wj , hence, αjgwj ,uj (x) = gαjwj ,uj (x). It means that the network can be rewritten as
N (x) = k∑ j=1 αjgwj ,uj (x) = k∑ j=1 gαjwj ,uj (x) = k∑ j=1 gw̃j ,uj (x)
with w̃j = αjwj . Because we want to optimize over the weights w1, . . . ,wk, α1, . . . , αk, we might as well optimize over the reparameterization w̃1, . . . , w̃k without losing expressive power. It means that in a GaLU network of this form, it is sufficient to train the first layer of the network, as the readout layer adds nothing to the expressiveness of the network.
The previous term can be further simplified:
N (x) = k∑ j=1 gwj ,uj (x) = k∑ j=1 σ ( x>uj ) x>wj
= [ σ ( x>u1 ) x> σ ( x>u2 ) x> . . . σ ( x>uk ) x> ]  w1 w2
... wk  = Φu(x) >w
where
Φu(x) =  σ ( x>u1 ) x σ ( x>u2 ) x
... σ ( x>uk ) x
 , w =  w1 w2
... wk  , u = [u1 u2 . . . uk] . So it turns out that a GaLU network is nothing more than a random non-linear transformation Φu : Rd → Rkd and then a linear function.

heading: 4.1 EXPRESSIVITY
text: There are different notions for the expressivity of a model, and one of the simplest ones is the finitesample expressivity over a random sample. This notion fits well to our model, because we are not interested in the absolute expressivity of a GaLU network, but of the expressivity of a GaLU network with random filters. So the question is how well does a randomly-initialized network can fit a random sample. Note that given the constant filters, solving for the best weights is a convex problem.
Hence, there is no “expressivity – optimization gap” in GaLU networks – every expressivity results is immediately also an optimization result.
Let S = {(x1, y1), (x2, y1), . . . , (xm,ym)} be a random sample, such that x1, . . . ,xm ∼ N(0, Id) and y1, . . . , ym ∼ N(0, 1), all of which are independent. Clearly, it is impossible to generalize from the sample to unseen examples; the best possible test loss is 1, and is achieved by the constant prediction 0. However, it is an interesting problem because it allows us to measure the expressivity of GaLU networks, by showing how much overfit we can expect from the network for a non-adversarial sample. Equivalently, it tells us how well the network can perform memorization tasks, where the only solution is to memorize the entire sample. We train the network for the standard mean-squareerror regression loss.
Because the network is simply linear function over a constant non-linear transformation, and because we use the MSE loss, there is a closed form solution to the optimization problem minw 1 m ∑m i=1(N (xi)− yi)2 which is
X̄ =  Φu(x1) > Φu(x2) >
... Φu(xm) >  w∗ = X̄+  y1 y2 ... ym  with X̄+ being a pseudo-inverse of X̄ . This gives us
Theorem 1 Let x1, . . . ,xm ∈ Rd, u1, . . . ,uk ∈ Rd be arbitrary vectors. Define X̄ as above. Let y1, . . . , ym ∼ N(0, 1) be independent random normal variables. Define the expected squared loss on the training set, for weights w, as LS(w). Then,
E[min w
LS(w)] = 1− rank
( X̄ )
m .
Proof Every vector y = (y1, . . . , ym) ∈ Rm can be decomposed to a sum y = a + b where a is in the span of the columns of X̄ and b is in the null space of X̄ . It follows that minw LS(w) = ‖b‖2/m. The claim follows because if y ∼ N(0, Im) then the expected value of ‖b‖2 is m− rank ( X̄ ) .
It is always true that rank(X̄) ≤ min{m, kd}. Empirical experimentation shows that if x1, . . . ,xm,u1, . . . ,uk ∼ N(0, Id) then with high probability rank(X̄) = min{m, kd}.

heading: 4.1.1 COMPARISON TO RELU NETWORKS
text: The fact that the GaLU network turned out to be only a linear function on top of a non-linear transformation seems to be a peculiar mathematical accident, with little relevance to standard networks. So we empirically tested the behavior of both ReLU and GaLU networks on the above model. It turns out that ReLU outperforms GaLU by a small margin – it is never better than GaLU with double the number of neurons, and is often worse than that.
ReLU can outperform GaLU, even though it is less expressive, because we don’t train the value of the the filters u1, . . . ,uk at all for the GaLU networks. It turns out that SGD over a ReLU network converges to better filters than a simple random initialization. One way to measure how much better those filters are is by trying to improve the initial filters of the GaLU network by randomly replacing them. Consider for example the simple algorithm given in algorithm 1.
Running this algorithm improves the results of the GaLU networks, making them more competitive with the ReLU ones. Figure 2 summarizes our results.

heading: 4.2 GENERALIZATION
text: An important fact about artificial neural networks is that they have small generalization error in many real-life problems. Otherwise they wouldn’t be very useful as a learning algorithm. Zhang
Algorithm 1 Improve GaLU filters Input: A sample S, number of neurons k, number of iterations n.
Initialize u1,u2, . . . ,uk randomly. Find an optimal solution w1, . . . ,wk. for i = 1 to n do
et al. (2016) have shown empirically that many classical attempts, such as model capacity, explicit regularization and even the properties of the optimization algorithm cannot explain this behavior. One of the main experiments they run was to train the network over a sample with randomized labels, and to observe that the network still achieved small training loss (but large test loss, naturally). So any generalization bound that can be applied to the randomized sample is necessarily too weak to explain the generalization of the natural sample.
As our goal is to show that GaLU networks exhibit similar phenomena as ReLU networks, but may be easier to analyze, we first construct a similar experiment to that of Zhang et al. (2016) and compare the performance of GaLU and ReLU networks. Consider the following natural model. Let c1, . . . , cn ∼ N(0, Id) be n clusters centers, each one with a random labels b1, . . . , bn. A data point (x, y) is generated by picking a random index i ∼ Uniform {1, 2, . . . , n}, and setting x = ci + ξ for ξ ∼ N(0, σ2xId). y is a noisy version of bi. This model can be used for both regression problems (with bi ∼ N(0, 1) and y = bi + , ∼ N(0, σ2y)) and classification problems (with bi ∼ Ber( 12 ), and y = bi ⊕ , ∼ Ber(p)). We fixed the number of samples m = 1000, the input dimension d = 30, the number of clusters n = 30, the number of hidden neurons k = 30 and σx = 0.1. We calculated the train and test errors for different values of σy and p and for a GaLU and ReLU networks. The results are summarized in figure 3. We can clearly see that GaLU and ReLU have similar statistical behavior, and that while the train error is always small, as the labels become noisier the generalization error increases. This matches the spirit of experiments reported in Zhang et al. (2016).

heading: 4.2.1 GENERALIZATION ERROR AND NORMS
text: Next, we turn to an analysis of this phenomenon. Since one hidden layer GaLU networks can be cast as linear predictors, we can rely on classic norm-based generalization bounds for linear predictors. In particular, for p ∈ {1, 2}, consider the class of linear predictors Hp = {x 7→ x>w : ‖w‖p ≤ Bp}. Given a sequence of instances S = {x1, . . . ,xm}, where ‖xi‖∞ ≤ 1, the Rademacher complexity
Regression
Binary Classification
of all the predictions Hp induces on S is upper bounded by √ B22 maxi ‖xi‖22/m for p = 2 and by√
2 log(2d)B21 maxi ‖xi‖2∞/m, where d is the dimension, for p = 1. See for example Section 26.2 in Shalev-Shwartz & Ben-David (2014). This also induces an upper bound on the gap between the test and train loss (see again Shalev-Shwartz & Ben-David (2014) for Lipschitz loss functions and see Srebro et al. (2010) for the relation between Rademacher complexity and the generalization of smooth losses such as the squared loss). The question is whether the `1/`2 norm of w is correlated with the amount of noise in the data. To study this, we depict the gap between train and test error as a function of the norm of w for GaLU networks. As can be seen in figure 4, for both the `1 and `2 norm, there is a clear linear relation between ‖w‖2p and the generalization gap. While the constants are far from what the bounds state, the linear correlation is very clear.
Note that figure 4 deals with GaLU networks that were trained as linear functions (by using the closed form solution for the MSE loss), and indeed shows that such network with such training behave as the theory states for linear predictors. We do not get the same behavior when we (unnecessarily) train both layers of the network using SGD. This matches the discussion in Section 5 of Zhang et al. (2016), where the correlation between the `2 norm of the weights in a ReLU network and the test loss is discussed, and it is argued that there are more factors that affect the generalization properties. Indeed, many followup works show different capacity measures that may be more adequate for studying the generalization of deep learning (See for example Bartlett et al. (2017); Neyshabur et al. (2017b; 2018); Arora et al. (2018); Neyshabur et al. (2017a); Kawaguchi et al. (2017)). We next show a rather different analysis for a particular instance of linear regression.

heading: 4.2.2 ALTERNATIVE APPROACH
text: Consider a simple linear regression using the MSE, and denote the train and test loss by
LS (w) = 1
m ∑ (x,y)∈S ( x>i w − y )2 ; LD (w) = E(x,y)∼D ( x>w − y )2 .
Given a training set S, the MSE estimator is defined as w(S) := arg minw LS(w).
We start with the following lemma.
Lemma 1 (Follows from Corollary 2 of Rosset & Tibshirani (2018)) For a scalar σ ≥ 0 and a vector β ∈ Rd, letDσ,β be the distribution over Rd×R which is defined by the following generative
model: pick x ∼ N(0, Id), and pick y = x>β + σε where ε ∼ N(0, 1). Then, for m > d + 1, we have:
E S∼Dmσ,β [LS(w(S))] = σ 2
( 1− d
m ) E
S∼Dmσ,β
[ LDσ,β (w(S)) ] = σ2 ( 1 + d
m + d m d+ 1 m− d− 1
) .
This lemma provides a complete analysis for the following experiment, which is similar to the experiments reported by Zhang et al. (2016). We compare two distributions, the first is Dσ,β for some vector β ∈ Rd and for σ being close to 0, and the second isD1,0. Note that the first distribution corresponds to a case in which we would like to be able to generalize, while the second distribution corresponds to a case in which we are fitting random noise and do not expect to generalize. We set the training set size to be m = d + 2 and we analyze the MSE estimator, w(S). As the lemma shows, the expected training losses on the first and second distributions are
σ2 (
1− d m
) = 2σ2
m ;
2 m ,
respectively. Hence, the training loss should be small on both of the distributions. In contrast, the expected test loss on the first distribution is
σ2 ( 1 + d
m + d m d+ 1 m− d− 1
) ≤ (3 + d)σ2
while the expected test loss on the second distribution is( 1 + d
m + d m d+ 1 m− d− 1
) ≥ 1 .
We see that while the train loss can be small on both distributions, in the test loss we see a big gap between the first distribution (assuming σ 1/ √ d) and the second distribution of purely random labels. This is exactly the type of phenomenon reported in Zhang et al. (2016) — a sample with a small amount of noise achieves both small train and test losses, but a sample with random labels achieves a small train loss but a large test loss. Note that this is a natural property of the least squares solution, without any explicit regularization, picking a minimal-norm solution or using a specific algorithm for solving the problem.
Lemma 1 gives us a very sharp analysis of linear regression. Unfortunately, the assumptions of Lemma 1 (which are based on the assumptions of Corollary 2 in Rosset & Tibshirani (2018)) are too strong — we need that m > d+ 1 and that the instances will be generated based on a Gaussian distribution. While Rosset & Tibshirani (2018) also includes asymptotic results that are applicable for a larger set of distributions, we leave the application of them to GaLU networks for future work.
5 A FEW WORDS ABOUT Rd → Rd′ PROBLEMS WITH ONE HIDDEN LAYER NETWORKS
In the analysis of the Rd → R case we used the fact that a GaLU neuron gw,u is linear in the parameter w, and it allowed us to rephrase the problem as a convex problem. In the Rd → Rd′ case the situation is not as simple. In this case, every hidden neuron has d′ outgoing edges, and so we cannot use the same reparametrization trick as before.
Even so, the output of a GaLU neuron is still linear in the parameter w. It means that for convex loss functions, finding the optimal weights for the first layer, keeping the weights of the second one constant, is a convex problem. The same doesn’t hold for ReLU networks. Finding the optimal weights for the second layer, keeping the weights of the first one constant, is also a convex problem. Even more specifically, the optimization problem over the two layers is biconvex (see Gorski et al. (2007) for a survey). So instead of applying SGD, we can apply biconvex optimization algorithms, such as Alternate Convex Search (ACS). In the case of the MSE loss, there is a closed form solution for each step of ACS, and using it outperforms SGD for small enough samples2. Even though it is of limited practical use, this algorithm might be interesting for the derivation of theoretical bounds for such networks.
In addition, it turns out that as we increase the output dimension d′, GaLU and ReLU networks becomes more similar. In section 4.1.1 we measured the difference between ReLU and GaLU for the problem where all the variables are i.i.d. N(0, 1), and it turned out that ReLU outperforms GaLU to a small extent. We repeated this experiment with larger d′, and saw that the difference between the two vanished quickly (see figure 5).

heading: 6 CONCLUSION & FURTHER WORK
text: The standard paradigm in deep learning is to use neurons of the form σ ( x>w ) for some differentiable non linear function σ : R → R. In this article we proposed a different kind of neurons, σi,j · x>w, where σi,j is some function of the example and the neuron index that remains constant along the training. Those networks achieve similar results to those of their standard counterparts, and they are easier to analyze and understand.
To the extent that our arguments are convincing, it gives new directions for further research. Better understanding of the one hidden layer case (from section 5) seems feasible. And as GaLU and ReLU networks behave identically for this problem, it gives us reasons to hope that understanding the behavior of GaLU networks would also explain ReLU networks and maybe other non-linearities as well. As for deeper network, it is also not beyond hope that GaLU0 networks would allow some better theoretical analysis than what we have so far.
2As it requires inverting a matrix, it is infeasible for large samples.

Review summaries:
The paper introduces a GaLU activation function, which is the product of a random gate function and a learnable linear function. The authors argue that empirically, neural networks with the GaLU activation is as effective as that with the ReLU activation, but theoretically, the GaLU activation is easier to understand because of the separation of the non-linearity and the learnable parameters. The the paper analyzes neural networks with one GaLU layer. Essentially, the network is a random transformation followed by a linear projection. This property enables analysis that are well known for the linear models.

The authors propose a modified ReLU, the GaLU, where the nonlinearity gating role is decoupled from the linear weights. Similar ideas have been previously proposed. For example Tsai et al: http://papers.nips.cc/paper/6516-tensor-switching-networks: "The TS network decouples a hidden unit’s decision to activate (as encoded by the activation weights) from the analysis performed on the input when the unit is active (as encoded by the analysis weights)" and Veness et al: Online learning with gated linear networks, https://arxiv.org/abs/1712.01897.