Towards a Theoretical Understanding of Hashing-Based Neural Nets
Yibo Lin Zhao Song Lin F. Yang

	

Lin, Song, Yang

[
Towards a Theoretical Understanding of Hashing-Based Neural Nets



  Yibo Lin

  
  Zhao Song 

  
  Lin F. Yang 

  
  

UT-Austin
Harvard & UT-Austin
Princeton University
]



	



Parameter reduction has been an important topic in deep learning due to the ever-increasing size of deep neural network models and the need to train and run them on resource limited machines.
Despite many efforts in this area, there were no rigorous theoretical guarantees on why existing neural net compression methods should work.
In this paper, we provide provable guarantees on some hashing-based parameter reduction methods in neural nets.
First, we introduce a neural net compression scheme based on random linear sketching (which is usually implemented efficiently via hashing), and show that the sketched (smaller) network is able to approximate the original network on all input data coming from any smooth and well-conditioned low-dimensional manifold.
The sketched network can also be trained directly via back-propagation.
Next, we study the previously proposed HashedNets architecture and show that the optimization landscape of one-hidden-layer HashedNets has a local strong convexity property similar to a normal fully connected neural network.






We complement our theoretical results with empirical verifications. 







§ INTRODUCTION











In the past decade, deep neural networks have become the new standards for many machine learning applications, including computer vision <cit.>, natural language processing <cit.>, speech recognition <cit.>, robotics <cit.>, game playing <cit.>, etc.
Such model usually contains an enormous number of parameters, which is often much larger than the number of available training samples. 
Therefore, these networks are usually trained on modern computer clusters which have a huge amount of memory and computation power.
On the other hand, there is an increasing need to train and run personalized machine learning models on mobile and embedded devices instead of transferring mobile data to a remote computation center on which all the computations are performed.
This is because real-time processing of deep learning models on mobile devices brings the benefits of better privacy and less Internet bandwidth. 

However, mobile devices like smart phones do not have the memory or computation capability of training large neural networks or even storing these models. 




These trends motivate the study of neural network compression, with the goal of reducing the memory overhead required to train, store and run neural networks.
There is a recent line of research in this direction, for example <cit.>.
Despite their empirical effectiveness, there is little theoretical understanding on why these methods perform well.

The goal of this paper is to bridge the gap between theory and practice in neural network compression.
Our focus is on hashing-based methods, which have been studied empirically in e.g. <cit.>, with the hope that the randomness in hash functions helps preserve the properties of neural networks despite a reduction in the number of effective parameters.
We make this intuition formal by giving theoretical guarantees on the approximation power and the parameter recovery of such networks.


First, we propose a neural net compression scheme based on random linear sketching, which can be efficiently implemented using a hash function.
Similar idea has been proposed in <cit.> and demonstrated high performance empirically, but no formal theoretical guarantee was known.
We show that such compression has strong approximation power. Namely, the small network obtained after sketching can approximate the original network on all input data coming from any low-dimensional manifold with some regularity properties.
The sketched network is also directly trainable via back-propagation.
In fact, sketching is a principled technique for dimensionality reduction, which has been shown to be very powerful in solving various problems arising in statistics <cit.> and numerical linear algebra <cit.>.
Given its theoretical success, it is natural to ask whether sketching can be applied to the context of neural net compression with theoretical guarantees. Our result makes partial progresses on this question.
















Next we study HashedNets, a simple method proposed in <cit.> which appears to perform well in practice.
HashedNets directly applies a random hash function on the connection weights in a neural net and to enforce all the weights mapped to the same hash bucket to take the same value.
In this way the number of trainable parameters is reduced to be the number of different hash buckets, and training can still be performed via back-propagation while taking the weight sharing structure into account.

From the perspective of optimization, we show that the training objective for a one-hidden-layer hashed neural net has a local strong convexity property, similar to that of a normal fully connected network <cit.>.
Additionally, we can apply the initialization algorithm in <cit.> to obtain a good initialization for training.
Therefore it implies that the parameters in one-hidden-layer HashedNets can be provably recovered under milde assumptions.



















Below we describe our contributions in more detail.



  
Approximation Power
Our result on the approximation power of sketched nets is based on a classical concept, “subspace embedding”, which originally appears in numerical linear algebra <cit.>. Roughly speaking, it says that there exist a wide family of random matrices S ∈^s× n, such that for any d-dimensional subspace ⊂^n, with probability 1-δ we have ⟨ Sx, Sx' ⟩ = ⟨ x, x' ⟩±ϵx_2  x'_2 for all x, x' ∈, provided s = Ω((d+log 1/δ)/ϵ^2).
This result means that the inner product between every two points in a subspace can be approximated simultaneously after applying a random sketching matrix S, which is interesting if s≪ n.
There has been a line of work trying to do subspace embedding using different sketching matrices (e.g. <cit.>).
 Sparse matrices are of particular interests, since for a sparse matrix S, one can compute Sx more efficiently.
For example, <cit.> showed that it is possible to construct S with only Õ(1/ϵ) nonzero entries per column, which significantly improves the trivial upper bound Õ(d/ϵ^2).
Furthermore, many of these sketching matrices can be efficiently implemented by k-wise independent hash functions where k is very small, which only takes a small amount of space to store, and multiplying S with a vector can be computed efficiently.

We extend the idea of subspace embedding to deep learning and show that a feed-forward fully connected network with Lipschitz-continuous activation functions can be approximated using random sketching on all input data coming from a low-dimensional subspace.
Below we describe our result for one-hidden-layer neural nets, and this can be generalized to multiple layers.

Consider a one-hidden-layer neural net with input dimension n and k hidden nodes. It can be parameterized by a weight matrix W ∈^n× k and a weight vector v ∈^k, and the function this network computes is x ↦ v^⊤ϕ(W^⊤ x), where x∈^n is the input, and ϕ should be viewed as a nonlinear activation function acting coordinate-wise on a vector.
Our result says that under appropriate assumptions, one can choose a random sketching matrix S ∈^s× n, such that for any d-dimensional subspace ⊂^n, we have

    | v^⊤ϕ(W^⊤ x) - v^⊤ϕ(W^⊤ S^⊤ Sx)| ≤ϵ, ∀ x ∈, x_2≤1.

This result essentially says that the weight matrix W^⊤ can be replaced by W^⊤ S^⊤ S, which has rank s.
When s<n, this means that the effective number of parameters can be reduced from kn to ks.
As we mentioned, the sketching matrix S can be implemented by hash functions in small space and multiplying it with a vector is efficient.
The sketched network is also directly trainable, because we can train the s× k matrix Ŵ = SW, regarding another factor S in the decomposition W^⊤ S^⊤ S = Ŵ S as a known layer.

This result can be generalized to multi-layer neural nets, and we present the details in Section <ref>.
We also note that our result can be easily generalized to low-dimensional manifolds under some regularity condition (see Definition 2.3 in <cit.>), which is a much more realistic assumption on data.




  
Parameter Recovery.
It is known that training a neural net is NP-hard in the worst case, even if it only has 3 hidden nodes <cit.>. Recently, there has been some theoretical progress on understanding the optimization landscapes of shallow neural nets under special input distributions.
In particular, <cit.> gave a recovery guarantee for one-hidden-layer neural nets. They showed that if the input distribution is Gaussian and the ground-truth weight vectors corresponding to hidden nodes are linearly independent, then the true parameters can be recovered in polynomial time given finite samples.
This was proved by showing that the training objective is locally strongly convex and smooth around the ground-truth point, together with an initialization method that can output a point inside the locally “nice” region.
In this work, we show that local strong convexity and smoothness continue to hold if we replace the fully connected network by HashedNets which has a weight sharing structure enforced by a hash function.
We present this result in Section <ref>.





 §.§ Related Works




  
Parameter Reduction in Deep Learning.
There has been a series of empirical works on reducing the number of free parameters in deep neural networks:
<cit.> show a method to learn low-rank decompositions of weight matrices in each layer,
<cit.> propose an approach to use a hash function to enforce parameter sharing,
<cit.> adopt a circulant matrix structure for parameter reduction,
<cit.> study a more general class of structured matrices for parameter reduction.



  
Sketching and Neural Networks.
<cit.> show that any linear or sparse polynomial function on sparse binary data can be computed by a small single-layer neural net on a linear sketch of the data.
<cit.> apply a random sketching on weight matrices/tensors, but they only prove that given a fixed layer input, the output of this layer using sketching matrices is an unbiased estimator of the original output of this layer and has bounded variance; however, this does not provide guarantees on the approximation power of the whole sketching-based deep net.



  
Subspace Embedding.
Subspace embedding <cit.> is a fundamental tool for solving numerical linear algebra problems, e.g. linear regression, matrix low-rank approximation <cit.>, tensor low-rank approximation <cit.>.
See also <cit.> for a survey on this topic.



  
Recovery Guarantee of Neural Networks.
Since learning a neural net is NP-hard in the worst case <cit.>, many attempts have been made to design algorithms that learns a neural net provably in polynomial time and sample complexity under additional assumptions, e.g., <cit.>.
Another line of work focused on analyzing (stochastic) gradient descent on shallow networks for Gaussian input distributions, e.g., <cit.>.



  
Other Related Works
Instead of understanding the parameter reduction as our work, there are several results working on developing over-parameterization theory of deep ReLU neural networks, e.g. <cit.>. Thirty years ago, Blum and Rivest proved training neural network is NP-hard <cit.>. Later, neural networks have been shown hard in several different perspectives <cit.> in the worst case regime. 

Arora et al. proved a stronger generalization for deep nets via a compression approach <cit.>. There is a long line of works targeting on explaining GAN from theoretical perspective <cit.>. There is also a long line of provable results about adversarial examples <cit.>.




§ PRELIMINARIES


For any positive integer n, we use [n] to denote the set {1,2,⋯,n}.
Let a± b represent any number in the interval [a-b, a+b].



For any vector x∈ℝ^n, we use x_2, x_1 and x _∞ to denote its ℓ_2, ℓ_1 and ℓ_∞ norms, respectively.
For x, y ∈^n,
we use ⟨ x, y ⟩ to denote the standard Euclidean inner product x^⊤ y.



For a matrix A,
let (A) denote its determinant (if A is a square matrix), 
let A^† denote the Moore-Penrose pseudoinverse of A, 
and let A_F and A_2 denote respectively the Frobenius norm and the spectral norm of A.

Denote by σ_i(A) the i-th largest singular value of A. We use (A) to denote the number of non-zero entries in A.

For any function f, we define O(f) to be f·log^O(1)(f). In addition to O(·) notation, for two functions f,g, we use the shorthand f≲ g (resp. ≳) to indicate that f≤ C g (resp. ≥) for an absolute constant C. We use f g to mean cf≤ g≤ Cf for constants c,C.

We define the ℓ_1 and ℓ_2 balls in ^n as: 
	B_1(B,n) =  { x ∈^n  |  x _1 ≤ B }, 
	 B_2(B,n) = { x ∈^n  |  x _2 ≤ B }.
We also need the definitions of Lipschitz-continuous functions and  k-wise independent hash families.


	A function f : → is L-Lipshitz continuous, if for all x_1, x_2 ∈,
	| f( x_1 ) - f( x_2 ) | ≤ L | x_1 - x_2 |.



 
A family of hash functions H⊆{ h | h: U → [B] } is said to be k-wise independent if for any x_1, …, x_k ∈ U and any
y_1, …, y_k ∈ [B] we have
_h ∼ H [h(x_i) = y_i, ∀ i∈[k]] = 1/B^k.








§ 
THE APPROXIMATION POWER OF PARAMETER-REDUCED NEURAL NETWORKS



In this section, we study 
the approximation power of parameter-reduced neural nets based on hashing.

Any weight matrix W in a neural net acts on a vector x as Wx. We replace Wx by WS^⊤ S x for some sketching (#rows < #columns) matrix S defined in the following section.
Then the new weight matrix W S^⊤ has much fewer parameters.  
We show that if S is chosen properly as a subspace embedding (formally defined later in this section), the sketched network can approximate the original network on all inputs coming from a low-dimensional subspace or manifold. 
Our sketching matrix is chosen as a Johnson-Lindenstrauss (JL) <cit.> transformation matrix. 
In Section <ref>, we provide some preliminaries on subspace embedding.



In Sections <ref> and <ref>, we present our result on one-hidden-layer neural nets.



Then in Section <ref> we extend this result to multi-layer neural nets and show a similar approximation guarantee.
This provides a theoretical guarantee for hashing-based parameter-reduced networks used in practice.



 §.§ Subspace Embedding

We first present some basic definitions of sketching and subspace embedding. 
These mathematical tools are building blocks for us to understand parameter-reduced neural networks.

 
	
	A (1±ϵ) ℓ_2-subspace embedding for the column space of an n × d matrix U is a matrix S for which for all x ∈colspan(U),
	S x _2^2 = ( 1 ±ϵ )  x _2^2,
	or equivalently, for all x, x' ∈colspan(U),
	⟨ Sx, Sx' ⟩ = ⟨ x, x' ⟩±ϵx_2x'_2.

Constructions of subspace embedding can be found in e.g. <cit.> from which there is the following theorem.

	There is a (1±ϵ) oblivious[The construction of S is oblivious to the subspace U.] ℓ_2-subspace embedding for n × d matrix U with s = d ·log( d / (ϵδ) ) /ϵ^2 rows and error probability δ. Further, S · U can be computed in time O((U) log ( d / (ϵδ) ) /ϵ). We call S a SparseEmbedding matrix. 

There are also other subspace embedding matrices, e.g., CountSketch.
We provide additional definitions and examples in Section <ref>.

We remark that the subspace embedding in Definition <ref> naturally extends to low dimensional manifolds. 
For example, for a d-dimensional Riemannian submanifold of ^n with volumn V and geodesic covering regularity R (see Definition 2.3 in <cit.>), Theorem <ref> holds by replacing d with Rdlog(V).
For ease of presentation, we only present our results for subspaces. 
All our results can be extended to low-dimensional manifolds satisfying regularity conditions. 







By computing the derivative of the function, it is not hard to see the following standard result,

Let f : [-1,1] → denote a degree-t polynomial with all coefficients are bounded by O(1). Then for any x∈ [-1,1], we have

    | f(x+ϵ) - f(x) | ≤ O( ϵ t ).







 §.§ One Hidden Layer - Part 1


We consider one-hidden-layer neural nets in the form ∑_i v_i ϕ_i(w_i^⊤ x), where x is the input vector, w_i is a weight vector, v_i is a weight scalar, and ϕ_i: → is a nonlinear activation function.

In this subsection, we show how to sketch the weights between the input layer and the hidden layer with guaranteed approximation power. The main result is Theorem <ref> and its proofs are in Appendix <ref>.



Given parameters n_2 ≥ 1, n_1≥ 1 ,ϵ∈ (0,1), δ∈ (0,1) and n=max(n_2,n_1).
 Given n_2 activation functions ϕ_i :→ that are L-Lipshitz-continuous,
 
 a fixed matrix U ∈^n_1 × d, weight matrix W ∈^n_1 × n_2 with W _2 ≤ B, v ∈^n_2 with v_1 ≤ B. Choose a SparseEmbedding matrix S ∈^s × n_1 with s = O( d L^2 B^4 A^2 ϵ^-2log (n L B A / (ϵδ) )  ), then with probability 1-δ, we have : for all x ∈colspan(U) ∩ B_2(A, n_1), 

    | ⟨ v, ϕ(W^⊤ x) ⟩ - ⟨ v, ϕ(W^⊤ S^⊤ S x ) ⟩ | ≤ϵ.







 §.§ One-hidden layer - Part 2

In this section, we show the approximation power of the compressed network if the weight matrices of both the input layer and output layer are sketched. One of the core idea in the proof is a recursive ϵ-net argument, which plays a crucial role in extending the result to multiple hidden layer. The goal of this section is to prove the following theorem and present the recursive ϵ-net argument.

Given parameters n_2 ≥ 1, n_2≥ 1 ,ϵ∈ (0,1), δ∈ (0,1) and n=max(n_2,n_1).
 Given n_2 activation functions ϕ_i :→ with L-Lipshitz and normalized by 1/√(n_2), a fixed matrix U ∈^n_1 × d, and weight matrix W ∈^n_2 × n_1 with W _2 ≤ B,
v ∈^n_2 with v_2 ≤ B. Choose a SparseEmbedding matrix S_1 ∈^s_1 × n_1 and S_2 ∈^s_2 × n_2 with s_1,s_2 = O( d  L^2 B^4 A^2 ϵ^-2log (n L B A / (ϵδ) )  ), then with probability 1-δ, we have : for all x ∈colspan(U) ∩ B_2(A, n_1), 

    | ⟨ v, ϕ(W^⊤ x) ⟩ - ⟨ S_2 v, S_2 ϕ(W^⊤ S_1^⊤ S_1 x) ⟩|
    ≤ϵ  .



The high level idea is as follows. 
Firstly, we prove that for any fixed input x, the theorem statement holds with high probability. 
Then we build an sufficiently fine ϵ-net over the input space of x and argue that our statement holds for every input point x from the ϵ-net. 
Condition on this event, the statement holds by applying the Lipshitz continuity of the activation function.
The detailed proof is presented in Appendix <ref>.









 §.§ Multiple hidden layer

In this section, we generalize our approximation power result to a multi-layer neural network and delay the proofs to Appendix <ref>. Inspired by the batch normalization <cit.>, which has been widely used in practice[<https://www.tensorflow.org/api_docs/python/tf/nn/batch_normalization>], we make an additional assumption by requiring the activations to be normalized by 1/√(n_j+1) at each layer j. The way we deal with multiple hidden layers is, first recursively argue an ϵ-net can be constructed for all the layers with the same size.
Then we use triangle inequality to split error into q+1 terms and bounding them separately. The result is the following theorem. 


Given parameters q≥ 1, n_j ≥ 1,∀ j ∈ [q+1] ,ϵ∈ (0,1), δ∈ (0,1) and n=max_j ∈ [q+1] n_j. For each j ∈ [q], for each i ∈ [n_j+1]
let ϕ_j,i :→ denote an activation function  with L-Lipshitz and normalized by 1/√(n_j+1).
Given a fixed matrix U ∈^n_1 × d, q weight matrices W_j ∈^n_j+1× n_j, ∀ j ∈ [q] with (the i_j-th column of W_j) w_j,i_j∈ B_2(B,n_j), a weight vector v∈^n_j+1 with v ∈ B_2(B,n_j+1). For each j ∈ [q+1], we choose a SparseEmbedding matrix S_j ∈^s_j × n_j with 
 
    s_j= O( d q^2 L^2q B^2q+2 A^2 ϵ^-2log (n q L B A / (ϵδ) )  ).

Then with probability 1-δ, we have : for all x ∈colspan(U) ∩ B_2(A, n_1), 

    | ⟨ v, f^(q)(x) ⟩ - ⟨ S_q+1 v, S_q+1f^(q)(x) ⟩ | ≤ϵ,

where f^(q)(x) and f^(q)(x) are defined inductively. The base case is f^(0)(x) =  f^(0)(x) = x, and the inductive case is

    f^(j)(x)    =  ϕ_j(W_j^⊤ f^(j-1)(x) ), ∀ j ∈ [q] 
     and f^(j)(x)     =  ϕ_j(W_j^⊤ S_j^⊤ S_j f^(j-1)(x) ), ∀ j ∈ [q].


Note that similar results also hold for the case without using S_q+1. In other words, we only choose q matrices for q hidden layers.








§ RECOVERY GUARANTEE

In this section, we study the recovery guarantee of parameter-reduced neural nets. In particular, we study whether (stochastic) gradient descent can learn the true parameters in a one-hidden-layer HashedNets when starting from a sufficiently good initialization point, under appropriate assumptions.
We show that even under the special weight sharing structure depicted by the hash function, the resulting neural net still has sufficiently nice properties - namely, local strong convexity and smoothness around the minimizer.
Our proof technique is by reducing our case to that of the fully connected network studied in <cit.>.
After that, the recovery guarantee follows similarly. We present our result here and give the detailed proof in Appendix <ref>.






We consider the following regression problem : given a set of m samples
S = { (x_1,y_1), (x_2,y_2), ⋯, (x_m,y_m) }⊂^n ×.
Let D be an underlying distribution over ^n × with parameters w^* ∈^B
 and v^* ∈^k, such that each sample (x,y) ∈ S is sampled i.i.d. from this distribution, with
x ∼ N(0,I), y = ∑_i=1^k v_i^* ·ϕ ( ∑_j=1^n w_h(i,j)^* · x_j ).
Here h : [k] × [n] → [B] is a random hash function drawn from a t-wise independent hash family H, where t = Θ(log(nk)), and ϕ is an activation function.

Note that w^* has a corresponding matrix Ŵ^* ∈^k× n defined as Ŵ^*_ij = w^*_h(i, j), which is the actual weight matrix in the HashedNets with a weight sharing structure. 



Our goal is to recover the ground-truth parameters w^*, v^* given the sample S. Note that how to recover v^* has been discussed in <cit.>; their method also applies to our situation. Therefore we focus on recovering w^* in this section, assuming v^* is known.

For a given weight vector w∈^B,

we define its expected risk and empirical risk  as 
    F_ D(w)    = 1/2_(x,y) ∼ D[ ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j) · x_j ) - y )^2 ] ,  
    
        F_S(w)    = 1/2∑_(x,y) ∼ S[ ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j) · x_j ) - y )^2 ].







We first show a structural result for t-wise independent hash family, which says the pre-image of  each bucket is pretty balanced.

Given integers N and B ≲ N / log N. Let h : [N] → [B] denote a t-wise independent hash function such that 
_h ∼ H[ h(i) = j] = 1/B, ∀ i ∈ [N], ∀ j ∈ [B].
Then, if t = Θ(log N), with probability at least 1 - 1 / (N), we have for all j ∈ [B],
0.9 N/B ≤∑_i=1^N  1_h(i) = j≤ 1.1 N/B.


The previous work <cit.> showed that a fully connected network whose ground-truth weight matrix W^* ∈^k× n has rank k has local strong convexity and smoothness around W^* in its loss function (see their Lemma D.3).

 







Using Lemma <ref> as our core reduction tool, we can reduce HashedNets to a fully connected net and obtain the following result:
 



Suppose ( Ŵ^* ) = k.
Then we have 
    0.5 ( kn / B ) · A_min· I ≼∇^2 F_ D(w^*) ≼ 2 ( kn / B ) · A_max·  I,

where A_max and A_min are positive parameters that depend on Ŵ^* and the activation function ϕ.









	A crucial assumption in Theorem <ref> is that the weight matrix Ŵ^* has rank k.
	In Section <ref>, we use numerical experiment to verify this assumption in learned HashedNets.
	






For the empirical risk F_S, we can show that its Hessian ∇^2 F_S(w^*) at the optimal point also satisfies similar properties given enough samples. See Theorem <ref> for details.




Using the tensor initialization method in <cit.>, we can find a point in the locally “nice region” around w^*, and
then we can show that gradient descent on the empirical risk function F_S converges linearly to w^*.
The result is summarized as follows.
 
There exist parameters γ_1 and γ_2 that depend on Ŵ^* and ϕ such that the following is true.
Let w^c be any point satisfying 
w^c - w^* _2 ≤γ_1 w^*_2,
and let S denote a set of i.i.d. samples from the distribution D. 
Define
m_0 = Θ( kn/BA_min )  and  M_0 = Θ(kn/B A_max)
where A_max and A_min are the same ones in Theorem <ref>. 
For any t≥ 1, if we choose
|S| ≥ n · (log n, t) · k^2 γ_2
and perform gradient descent with step size 1/M_0 on F_S and obtain the next iterate,
w = w^c - 1/M_0∇ F_S(w^c),
then with probability at least 1-n^-Ω(t), we have
w - w^* _2^2 ≤ ( 1 - m_0 / M_0 )  w^c - w^* _2^2.

The above theorem states that once a constantly-accurate initialization point is specified, we can obtain a solution up to  precision exp(-(n)) in a polynomial number of gradient descent iterations.  This concludes the recovery guarantee. 
We give the formal statements and proofs in Section <ref>. 












§ EXPERIMENTS



In this section, we perform some simple experiments on MNIST dataset to evaluate the performance of HashedNets, as well as empirically verify the full rank assumption (as in Theorem <ref>) on weight matrices in HashedNets.
Each image in MNIST dataset has a dimensionality of 28 × 28. 
The HashedNets in the experiment have single-hidden-layer, i.e., two fully connected layers. 
To validate the effectiveness of HashedNets, we construct two baselines. 

    
  * SmallNets. A single-hidden-layer network is constructed with the same amount of effective weights as that of HashedNets. 
        For example, for a HashedNets with 1000 hidden units in the hidden layer with compression ratio 64, a corresponding SmallNets have ⌈1000/64⌉ =16 hidden units in the hidden layer. 
    
  * ThinNets. A two-hidden-layer network is constructed with the same amount of effective weights as that of HashedNets. 
        By replacing the first fully connected layer in HashedNets with a thin hidden layer, a same amount of weights can be achieved. 
        For example, for a HashedNets with 1000 hidden units in the hidden layer with compression ratio 64, a corresponding ThinNets have ⌈784 × 1000/(784+1000) × 64⌉ =7 hidden units for the first hidden layer and 1000 hidden units for the second hidden layer. 

The accuracy of HashedNets, SmallNets, and ThinNets is compared under various compression ratios. 


 










The HashedNets were implemented in Torch7 <cit.> and validated on NVIDIA GTX 1080 GPU. 
We used 32 bit precision floating point numbers throughout the experiments. 
Stochastic gradient descent was adopted as the numerical optimizer with a dropout keep rate of 0.9, momentum of 0.9, and a batch size of 50. 
ReLU was used as the activation function. 
We ran 1000 epochs for each experiment and experiments on two single-hidden-layer HashedNets with 500 and 1000 hidden units are conducted, respectively. 

The amount of units in SmallNets and ThinNets is adjusted to match the amount of weights in HashedNets. 































For different compression ratios, we plot the distribution of testing errors for 50 runs of HashedNets, ThinNets, and SmallNets with 50 different random seeds, as shown in Figure <ref>. 
Due to random initialization, SmallNets still gives different results with independent runs. 
In Figure <ref>(a), when the compression ratio is 1, which indicating no compression, the distributions for both HashedNets and SmallNets are very close, 
i.e., with means of 1.37% and 1.40%, standard deviations of 0.050% and 0.038%, respectively. 
ThinNets provides slightly better testing error with a mean of 1.27% and a standard deviation of 0.057%. 
In Figure <ref>(b), when the compression ratio is 8, HashedNets provides smaller testing errors than that of SmallNets, 
i.e., with means of 1.43% v.s. 1.76%, and standard deviations of 0.052% v.s. 0.070%, respectively. 
ThinNets provides slightly better testing errors than that of HashedNets, 
i.e., with means of 1.32% v.s. 1.44%, and standard deviations of 0.060% v.s. 0.056%. 
In other words, both HashedNets and ThinNets can achieve higher and more robust accuracy with improvements in both mean and standard deviation than SmallNets for this compression ratio. 
With the compression ratio increasing to 64, as shown in Figure <ref>(c), the benefit of HashedNets is more significant. 
The mean of testing errors for HashedNets degrades to 2.80%, while that for SmallNets increases to 6.09%. 
The errors for SmallNets are more instable due to larger standard deviations. 
Meanwhile, HashedNets can also provide better accuracy than ThinNets, 
i.e., with means of 2.80% v.s. 5.03%, and standard deviations of 0.090% v.s. 0.196%. 
When the compression ratio is 128, as shown in Figure <ref>(d), 
HashedNets achieves a mean accuracy of 4.20% and a standard deviation of 0.116%, 
which is much better than that of ThinNets, a mean accuracy of 11.09% and a standard deviation of 0.160%, 
and that of SmallNets, a mean accuracy of 10.28% and a standard deviation of 0.810%. 
In summary, from the aspect of accuracy degradation, when the compression ratio increases from 1 to 128, there is on average 2.83% degradation in accuracy for HashedNets, 
while the accuracy of SmallNets degrades by 8.88% and that of ThinNets degrades by 9.82%. 
ThinNets may achieve comparable error to HashedNet for small compression ratios (e.g., 1 and 8), while for large compression ratio, HashedNet tends to be more stable.

Figure <ref> plots the training curves of different networks under different compression ratios  with random seed 100.  
The testing errors align with the observation from Figure <ref>. 
That is, HashedNets provides high and stable accuracy across various compression ratios; 
ThinNets achieves good accuracy for small compression ratios (e.g., 1 and 8, the accuracy is close to that of HashedNets), 
while degrades significantly with the increase of compression ratios; 
SmallNets are also very sensitive to large compression ratios like ThinNets. 

We further verify the full rank assumption of weight matrices in HashedNets. 
Figure <ref> plots the distributions of minimum and maximum singular values, condition numbers, and stable ranks of the two weight matrices W_1 and W_2 in HashedNets with 1000 hidden units.
The dimensions of W_1 is 1000 × 784 and that of W_2 is 10 × 1000. 
The distributions are extracted from the aforementioned 50 runs. 
Figure <ref> (in the Appendix) gives one example of all singular values sorted from large to small in one experiment. 
All the singular values and condition numbers are distributed in reasonable scales, i.e., neither too close to zero, nor too large.  
This experiment indicates that the assumption of full rank holds in practice. 
Same set of figures are also provided for HashedNets with 500 hidden units, as shown in Figure <ref> (in the Appendix), 
where the dimensions of W_1 is 500 × 784 and that of W_2 is 10 × 500. 









§ CONCLUSION


In this paper, we study the theoretical properties of hashing-based neural networks.
We show that (i) parameter-reduced neural nets have uniform approximation power on inputs from any low-dimensional subspace or smooth  and well-conditioned manifold; (ii) one-hidden-layer HashedNets have similar recovery guarantee to that of fully connected neural nets.


We also empirically explore an alternative compression scheme, ThinNets, which is a very interesting direction for further study, 
so we plan to explore its property and theoretical insights in the future.




§ ACKNOWLEDGMENTS


This project was done while Zhao was visiting Harvard and hosted by Prof. Jelani Nelson. In 2017, Prof. Jelani Nelson and Prof. Piotr Indyk co-taught a class “Sketching Algorithms for Big Data”. One of the class project is, “Understanding hashing trick of neural network.” That is the initialization of this project. The authors would like to thank Zhixian Lei for inspiring us of this project. 

The authors would like to appreciate Wei Hu for his generous help and contribution to this project. 


The authors would like to thank Rasmus Kyng, Eric Price, Zhengyu Wang and Peilin Zhong for useful discussions.






























abbrvnat






§ APPENDIX



§ NOTATION


For any positive integer n, we use [n] to denote the set {1,2,⋯,n}.
For random variable X, let 𝔼[X] denote the expectation of X (if this quantity exists).


For any vector x∈ℝ^n, we use x_2 to denote its ℓ_2 norm.

We provide several definitions related to matrix A.
Let (A) denote the determinant of a square matrix A. Let A^⊤ denote the transpose of A. Let A^† denote the Moore-Penrose pseudoinverse of A. Let A^-1 denote the inverse of a full rank square matrix. Let A_F denote the Frobenius norm of matrix A. Let A denote the spectral norm of matrix A. Let σ_i(A) to denote the i-th largest singular value of A.


For any function f, we define O(f) to be f·log^O(1)(f). In addition to O(·) notation, for two functions f,g, we use the shorthand f≲ g (resp. ≳) to indicate that f≤ C g (resp. ≥) for an absolute constant C. We use f g to mean cf≤ g≤ Cf for constants c,C.


We state a trivial fact that connects ℓ_2 norm with ℓ_∞ norm.

For any vector x ∈^n, we have x _2 ≤√(n) x _∞.





§ NEURAL SUBSPACE EMBEDDING





 §.§ Preliminaries



A random matrix S∈^k× n forms a Johnson-Lindenstrauss transform with parameters ϵ,δ,f, or JLT(ϵ,δ,f) for short, if with probability at least 1-δ, for any f-element subset V ⊂^n, for all v,v'∈ V it holds that
	
    | ⟨ S v , S v' ⟩ - ⟨ v , v' ⟩ | ≤ϵ v _2  v' _2.



The well-known Count-Sketch matrix from the data stream literature <cit.> is a sub-space embedding and JL matrix. The definition is provided as follows.

Let S denote a s × n matrix. We choose a random hash function h : [n] → [s], and choose a random hash function σ : [n]→{-1,+1}. We set

    S_j,i =
    	σ(i)     if  j = h(i), 
    
    	0     otherwise.



Count-Sketch matrix gives the following subspace embedding result,

For any 0 < δ < 1, and for S a Count-Sketch matrix s = O(d^2 /(δϵ^2)) rows, then with probability 1-δ, for any fixed n × d matrix U, S is a (1±ϵ) ℓ_2-subspace embedding for U. The matrix product S · U can be computed in O((U)) time. Further, all of this holds if the hash function h defining S is only pairwise independent, and the sign function σ defining S is only 4-wise independent.



Suppose Π is a distribution on s × n matrices S, where s is a function of n,d,ϵ and δ. Suppose that with probability at least 1-δ, for any fixed n × d matrix U, a matrix S drawn from distribution Π has the property that S is a (1±ϵ) ℓ_2-subspace embedding for U. Then we call Π an (ϵ,δ) oblivious ℓ_2-subspace embedding.



<cit.> provides some other constructions for subspace embedding, 

Let S denote a s × n matrix. For each i,j, S_i,j∈{0, 1/√(t), -1/√(t)}. For a random draw S, let δ_i,j be a indicator random variable for the event S_i,j≠ 0, and write S_i,j = δ_i,jσ_i,j / √(t), where the σ_i,j are random signs. S satisfies the following two properties, for each j ∈ [n], ∑_i=1^s δ_i,j = t; for any set T ⊆ [s] × [n], [∏_(i,j) ∈ Tδ_i,j≤ (t/m)^|T|].




Let A = {^n  |  y = U x, ∀ x ∈^d,  y _2=1 }, for any 0 < γ < 1, there exists a γ-net N of A for which | N| ≤ (1+ 4/γ)^d.





 §.§ Proof of Theorem <ref>



Using Theorem <ref>, we choose s = d ϵ'^-2log (n d / (ϵ' δ)), with probability 1-δ, we have : for n_2 fixed vectors w_1,⋯,w_n_2 and for all x ∈colspan(U), 


    | ⟨ S w_i, S x ⟩ - ⟨ w_i, x ⟩ | ≤ϵ'  w_i _2  x _2,  ∀ i ∈ [n_1].

Using the Lipschitz property of ϕ_i, we can show that

    | ϕ_i(w_i^⊤ x) - ϕ_i( ⟨ S w_i, S x ⟩ ) | 
     ≤     L | w_i^⊤ x - ⟨ S w_i, S x ⟩ | 
    ≤     L ϵ'  w_i _2  x _2 
    ≤    ϵ' L B A,

where the first step follows by Property of function ϕ_i, the last step follows by w_i _2 ≤ B, x _2 ≤ A.
It remains to bound 

    | ∑_i=1^n_2 v_i ϕ_i( w_i^⊤ x ) - v_i ϕ_i( w_i^⊤ S^⊤ S x ) |
    ≤    ∑_i=1^n_2 |v_i| · | ϕ_i( w_i^⊤ x ) - ϕ_i( w_i^⊤ S^⊤ S x ) | 
    ≤     v _1 max_i ∈ [n_2]  | ϕ_i( w_i^⊤ x ) - ϕ_i( w_i^⊤ S^⊤ S x ) | 
    ≤     v _1 ϵ' L B A  ≤ ϵ' L B^2 A ≤ ϵ,

where the first step follows by triangle inequality, the third step follows by Eq. (<ref>), the fourth step follows by v _1 ≤ B, and the last step follows from ϵ' = Θ( ϵ / (B^2 A L) ). Therefore, it suffices to choose

    s = d B^4 A^2 L^2 ϵ^-2log (nBA L/(ϵδ)).





 §.§ Proof of Theorem <ref>


The proof includes three steps.
The first step is similar to the proof of Theorem <ref>. 
Using Theorem <ref>, we choose s_1 = d ϵ_1^-2log (n d / (ϵ_1 δ)), with probability 1-δ/2, we have : for n_2 fixed vectors w_1,⋯,w_n_2 and for all x ∈colspan(U),
| ⟨ S_1 w_i, S_1 x ⟩ - ⟨ w_i, x ⟩ |≤ϵ_1  w_i _2  x _2,  ∀ i ∈ [n_2].
Next, we consider the column space of U, which we call P_1, defined as follows

    P_1 = { y_1 ∈^n_1 |  y_1 = U x,  y_1 _2 ≤ 1 , ∀ x ∈^d }.

Let N_1 denote the γ_1-net of P_1, by Lemma <ref>, | N_1|= 2^O(d log ( 1/γ_1 )).
By definition, for each y_1 ∈ P_1, there exists a vector z ∈ N_1 such that
y_1 - z_1 _2 ≤γ_1.

Let P_2 and N_2 be defined as follows,

    P_2 =     { y_2 ∈^n_2 |  y_2 = ϕ( W^⊤ S_1^⊤ S_1 y_1) , ∀ y_1 ∈ P_1 }. 
     N_2 =     { z_2 ∈^n_2 |  z_2 = ϕ( W^⊤ S_1^⊤ S_1 z_1 ) , ∀ z_1 ∈ N_1 }.

Then we want to show the following claim. (The proof can be found in Appendix <ref>) 

cla:subspace_one_hidden_II_recursiveClaim(Recursive ϵ-net).
Let γ_2 = γ_1 / ( √(n_2) L (1+ϵ_1) B), then
N_2 is an γ_2-net to P_2.

cla:subspace_one_hidden_II_recursive



Now, we choose a sketching matrix S_2 ∈^s_2 × n_2 with s_2 = d ϵ_2^-2(n d / (ϵ_2 δ)), with probability 1-δ/2, we have : a vector v∈^n_2 and for all y_1 ∈ P_2,

    | ⟨ S_2 v, S_2 y_2 ⟩ - ⟨ v, y_2 ⟩ | ≤ϵ_2  v _2  y_2 _2 .

Using triangle inequality, we can bound the error term,

    | ⟨ v, ϕ(W^⊤ x) ⟩ - ⟨ S_2 v, S_2 ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | 
    ≤     | ⟨ v, ϕ(W^⊤ x) ⟩ - ⟨ v, ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | 
    
     +     | ⟨  v,  ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ - ⟨ S_2 v, S_2 ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | 
    ≲    ϵ_2 LB^2A + ϵ_1 B^2 A L ≤ ϵ,

 where the first step follows from triangle inequality, the second step follows from the Property of S_2, the third step follows from Claim <ref> and Claim <ref>, and the last step follows from ϵ_1, ϵ_2 ≲ϵ /( L B^2 A ).


We list the two Claims here and delay the proofs into Appendix <ref>.
cla:subspace_one_hidden_II_1Claim
| ⟨  v,  ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ - ⟨ S_2 v, S_2 ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | ≲ϵ_2 L B^2 A.

cla:subspace_one_hidden_II_1


cla:subspace_one_hidden_II_2Claim
| ⟨ v, ϕ(W^⊤ x) -⟨ v, ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | ≤ L B^2 A ϵ_1.

cla:subspace_one_hidden_II_2



 §.§ One hidden layer

In this Section, we provide the proofs of some Claims used for one hidden layer case.


cla:subspace_one_hidden_II_recursive

For each point y_2 ∈ P_2, there must exists a point y_1 ∈ P_1 such that
y_2 = ϕ (W^⊤ S_1^⊤ S_1 y_1).

Since y_1 ∈ P_1 and N_1 is the ϵ_1-net of P_1. Thus, there must exists a vector z_1 ∈ N_1 such that
y_1 - z_1 _2 ≤γ_1.

According to the definition N_2, there must exists a point z_2 ∈ N_2 such that
z_2 = ϕ(W_1^⊤ S_1^⊤ S_1 z_1).
Now, let's consider the y_2-z_2_2,


    y_2-z_2_2 
    ≤    √(n_2) y_2 - z_2 _∞
    
    =     √(n_2)ϕ(W^⊤ S_1^⊤ S_1 y_1) - ϕ(W^⊤ S_1^⊤ S_1 z_1) _∞
    
    =     √(n_2)max_i ∈ [n_2] | ϕ_i (w_i^⊤ S_1^⊤ S_1 y_1) - ϕ_i (w_i^⊤ S_1^⊤ S_1 z_1) | 
    ≤    √(n_2)max_i ∈ [n_2]  L | w_i^⊤ S_1^⊤ S_1 y_1 - w_i^⊤ S_1^⊤ S_1 z_1 | 
    
    =     √(n_2)max_i ∈ [n_2] L | ⟨ S_1 w_i, S_1 (y_1 - z_1) ⟩| 
    ≤    √(n_2)max_i∈ [n_2] L (1+ϵ_1)  w_i _2  y_1 - z_1 _2 
    ≤    √(n_2) L (1+ϵ_1) B γ_1 ≤ γ_2,

where the first step follows from ·_2 ≤√(dim)··_∞, the second step follows from definition of y_1 and z_1, the third step follows from the definition of ·_∞, the fourth step follows from the property of the activation function (L-Lipshitz), the sixth step follows from that S_1 provides a subspace embedding, and the last step follows from the definition of γ_2.


cla:subspace_one_hidden_II_1


    | ⟨  v,  ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ - ⟨ S_2 v, S_2 ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | 
    ≤    ϵ_2  v_2  ·ϕ(W^⊤ S_1^⊤ S_1 x) _2 
    ≤    ϵ_2  v_2  · L max_i∈ [n_2] | w_i^⊤ S_1^⊤ S_1 x | 
    ≤    ϵ_2  v_2 · L max_i∈ [n_2] (1±ϵ_1)  w_i _2  x _2 
    ≲    ϵ_2 L B^2 A,

where the first step follows from that S_2 is a (1±ϵ_2) ℓ_2 subspace embedding, the second step follows from the property of ϕ_i (L-lipshitz), the third step follows from that S_1 is (1±ϵ_1) ℓ_2 subspace embedding, the fourth step follows from that v _2,  W _2 ≤ B and x _2 ≤ A.


cla:subspace_one_hidden_II_2



    | ⟨ v, ϕ(W^⊤ x) -⟨ v, ϕ(W^⊤ S_1^⊤ S_1 x) ⟩ | 
    ≤    v _2 ·ϕ(W^⊤ x) -  ϕ(W^⊤ S_1^⊤ S_1 x) _2 
    ≤     v_2 ·  Lmax_i∈ [n_2] | w_i^⊤ x -  w_i^⊤ S_1^⊤ S_1 x | 
    ≤     v _2 L ϵ_1 max_i∈ [n_2] w_i _2  x_2 
    ≤     L B^2 A ϵ_1,

where the first step follows from Cauchy-Shawrz inequality, the second step follow by property of activation function, the third step follows from S_1 is an (1±ϵ_1) subspace embedding, and last step follows from that v _2, W _2 ≤ B, x _2 ≤ A.





 §.§ Two hidden layers

The goal of section is to present Theorem <ref>.

Given parameters n_3 ≥ 1, n_2 ≥ 1, n_2≥ 1 ,ϵ∈ (0,1), δ∈ (0,1) and n=max(n_3,n_2,n_1).
 Given n_2 activation functions ϕ_1,i :→ with L-Lipshitz and normalized by 1/√(n_2), n_3 activation functions ϕ_2,i : → with L-Lipshitz and normalized by 1/√(n_3), a fixed matrix U ∈^n_1 × d, two weight matrices W_1 ∈^n_2 × n_1 and W_2 ∈^n_3 × n_2 with (the i_1-th column of W_1) w_1,i_1∈ B_2(B,n_1) and (the i_2-th column of W_2) w_2,i_2∈ B_2(B,n_2), a weight vector v∈^n_3 with v ∈ B_2(B,n_3). Choose a SparseEmbedding matrix S_1 ∈^s_1 × n_1, S_2 ∈^s_2 × n_2, S_3 ∈^s_3 × n_3 with 
 
    s_1,s_2, s_3= O( d  L^4 B^6 A^2 ϵ^-2log (n L B A / (ϵδ) )  ) ,

 then with probability 1-δ, we have : for all x ∈colspan(U) ∩ B_2(A, n_1), 

    | ⟨ v, ϕ_2 (W_2^⊤ϕ_1(W_1^⊤ x) ) ⟩ - ⟨ S_3 v, S_3 ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | ≤ϵ  .



It follows by combining Section <ref> and Lemma <ref>.





  §.§.§ Recursive ϵ-net argument


Using Theorem <ref>, we choose s_1 = d ϵ_1^-2log (n d / (ϵ_1 δ)), with probability 1-δ/2, we have : for n_2 fixed vectors w_1,⋯,w_n_2 and for all x ∈colspan(U),

    | ⟨ S_1 w_i, S_1 x ⟩ - ⟨ w_i, x ⟩ |≤ϵ_1  w_i _2  x _2,  ∀ i ∈ [n_2].
 

We define P_1 as follows

    P_1 = { y_1 ∈^n_1 |  y_1 = U x,  y_1 _2 ≤ 1 , ∀ x ∈^d }.

Let N_1 denote the γ_1-net of P_1, by Lemma <ref>, | N_1|= 2^O(d log ( 1/γ_1 )).
By definition For each y_1 ∉ P_1, there exists a vector z ∈ N_1 such that

    y_1 - z_1 _2 ≤γ_1.


Let P_2 be defined as follows,

    P_2 = { y_2 ∈^n_2 |  y_2 = ϕ_1( W_1^⊤ S_1^⊤ S_1 y_1) , ∀ y_1 ∈ P_1 }.

We define N_2 to be 

    N_2 = { z_2 ∈^n_2 |  z_2 = ϕ_1( W_1^⊤ S_1^⊤ S_1 z_1 ) , ∀ z_1 ∈ N_1 }.

Then we want to show


Let γ_2 = γ_1 / ( L (1+ϵ_1) B), then
N_2 is an γ_2-net to P_2.




For each point y_2 ∈ P_2, there must exists a point y_1 ∈ P_1 such that

    y_2 = ϕ (W_1^⊤ S_1^⊤ S_1 y_1).

Since y_1 ∈ P_1 and N_1 is the ϵ_1-net of P_1. Thus, there must exists a vector z_1 ∈ N_1 such that

    y_1 - z_1 _2 ≤γ_1.

According to the definition N_2, there must exists a point z_2 ∈ N_2 such that

    z_2 = ϕ(W_1^⊤ S_1^⊤ S_1 z_1).

Now, let's consider the y_2-z_2_2,

    y_2-z_2_2
    ≤    √(n_2) y_2 - z_2 _∞
    
    =     √(n_2)ϕ_1 (W_1^⊤ S_1^⊤ S_1 y_1) - ϕ_1 (W_1^⊤ S_1^⊤ S_1 z_1) _∞
    
    =     √(n_2)max_i ∈ [n_2] | ϕ_1 (w_1,i_1^⊤ S_1^⊤ S_1 y_1) - ϕ_1 (w_1,i_1^⊤ S_1^⊤ S_1 z_1) | 
    
    =     max_i_1 ∈ [n_2]  L | w_1,i_1^⊤ S_1^⊤ S_1 y_1 - w_1,i_1^⊤ S_1^⊤ S_1 z_1 | 
    
    =     max_i_1 ∈ [n_2] L | ⟨ S_1 w_1,i_1, S_1 (y_1 - z_1) ⟩| 
    ≤    max_i_1 ∈ [n_2] L (1+ϵ_1)  w_1,i_1_2  y_1 - z_1 _2 
    ≤      L (1+ϵ_1) B γ_1 
    ≤    γ_2,

where the first step follows by ·_2 ≤√(dim)··_∞, the second step follows by definition of y_1 and z_1, the third step follows by definition, the fourth step follows by property of activation function (L-lipshitz and normalization), the sixth step follows by S_1 provides a subspace embedding, the last step follows by definition of γ_2.


It is obvious that |  N_2 | = |  N_1 |.


Let P_3 be defined as follows,

    P_3 = { y_3 ∈^n_3 |  y_3 = ϕ_2( W_2^⊤ S_2^⊤ S_2 y_2) , ∀ y_2 ∈ P_2 }.

We define N_2 to be 

    N_3 = { z_3 ∈^n_3 |  z_3 = ϕ_2( W_2^⊤ S_2^⊤ S_2 z_2 ) , ∀ z_2 ∈ N_2 }.

Then we want to show

Let γ_3 = γ_2 / ( L (1+ϵ_2) B ), then
N_3 is an γ_3-net to P_3.




For each point y_3 ∈ P_3, there must exists a point y_2 ∈ P_2 such that

    y_3 = ϕ (W_2^⊤ S_2^⊤ S_2 y_2).

Since y_2 ∈ P_2 and N_2 is the ϵ_2-net of P_2. Thus, there must exists a vector z_2 ∈ N_2 such that

    y_2 - z_2 _2 ≤γ_2.

According to the definition N_3, there must exists a point z_3 ∈ N_3 such that

    z_3 = ϕ(W_2^⊤ S_2^⊤ S_2 z_2).

Now, let's consider the y_3-z_3_2,

    y_3-z_3_2 
    ≤    √(n_3) y_3 - z_3 _∞
    
    =     √(n_3)ϕ_2 (W_2^⊤ S_2^⊤ S_2 y_2) - ϕ_2 (W_2^⊤ S_2^⊤ S_2 z_2) _∞
    
    =     √(n_3)max_i ∈ [n_3] | ϕ_2 (w_2,i_2^⊤ S_2^⊤ S_2 y_2) - ϕ_1 (w_2,i_2^⊤ S_2^⊤ S_2 z_2) | 
    
    =     max_i_2 ∈ [n_3]  L | w_2,i_2^⊤ S_2^⊤ S_2 y_2 - w_2,i_2^⊤ S_2^⊤ S_2 z_2 | 
    
    =     max_i_2 ∈ [n_3] L | ⟨ S_2 w_2,i_2, S_2 (y_2 - z_2) ⟩| 
    ≤    max_i_2 ∈ [n_3] L (1+ϵ_2)  w_2,i_2_2  y_2 - z_2 _2 
    ≤      L (1+ϵ_2) B γ_2 
    ≤    γ_3,

where the first step follows by ·_2 ≤√(dim)··_∞, the second step follows by definition of y_2 and z_2, the third step follows by definition, the fourth step follows by property of activation function (L-lipshitz and normalization), the sixth step follows by S_2 provides a subspace embedding, the last step follows by definition of γ_3.




  §.§.§ Bounding the error




    | ⟨ v, ϕ_2 (W_2^⊤ϕ_1(W_1^⊤ x) ) ⟩ - ⟨ S_3 v, S_3 ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | ≤ 2(ϵ_1 + ϵ_2 + ϵ_3 ) L^2 B^3 A.




    | ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ x) ) ⟩ - ⟨ S_3 v, S_3 ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    ≤     | ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    
    +      | ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    
    +      | ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) - ⟨ S_3 v, S_3 ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1(W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    ≤     2(ϵ_1 + ϵ_2 + ϵ_3) L^2 B^3 A,

where the first step follows by triangle inequality, and the last step follows by Claim <ref>, <ref>, <ref>.



| ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | ≤ϵ_1 L^2 B^3 A.


We have,

    | ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    ≤     v _2 ·ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ x) ) - ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) _2
    ≤     v _2 ·√(n_3)·max_i_2∈ [n_3]  | ϕ_2 (w_2,i_2^⊤ϕ_1 (W_1^⊤ x) ) - ϕ_2(w_2,i_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) )  | 
    ≤     v _2 · L ·max_i_2∈ [n_3] | w_2,i_2^⊤ϕ_1 (W_1^⊤ x) - w_2,i_2^⊤ϕ_1(W_1^⊤ S_1^⊤ S_1 x) | 
    ≤     v _2 · L ·max_i_2∈ [n_3] w_2,i_2_2 ϕ_1(W_1^⊤ x) - ϕ_1(W_1^⊤ S_1^⊤ S_1 x) _2 
    ≤     v _2 · L ·max_i_2∈ [n_3] w_2,i_2_2 max_i_1 ∈ [n_2]√(n_2) L | ϕ_1 ( w_1,i_1^⊤ x ) - ϕ_1 ( w_1,i_1^⊤ S_1^⊤ S_1 x ) | 
    ≤     v _2 · L ·max_i_2∈ [n_3] w_2,i_2_2 max_i_1 ∈ [n_2] L |  w_1,i_1^⊤ x  - w_1,i_1^⊤ S_1^⊤ S_1 x  | 
    ≤     v _2 · L ·max_i_2∈ [n_3] w_2,i_2_2 max_i_1 ∈ [n_2] L ϵ_1  w_1,i_1_2  x _2 
    ≤    ϵ_1 L^2 B^3 A,

where the first step follows by Cauchy-Shawrz inequality, the second step follows by Fact <ref>, the third step follows by property of activation function (L-Lipshitz and normalization), the fourth step follows by Cauchy-Shawrz inequality, the fifth step follows by Fact <ref>, the sixth step follows by property of activation function, the seventh step follows by S_1 is a (1±ϵ_1) ℓ_2 subspace embedding, and the last step follows by v_2,  w_2,i_2_2,  w_1,i_1_2 ≤ B, x _2 ≤ A.



| ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | ≤ 2 ϵ_2 L^2 B^3 A.



We have,

    | ⟨ v, ϕ_2 (W_2^⊤ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ - ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    ≤     v _2  ϕ_2 (W_2^⊤ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) ) - ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) )  _2 
    ≤     v _2 ·max_i_2 ∈ [n_3] √(n_3)· | ϕ_2( w_2,i_2^⊤ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) ) - ϕ_2( w_2,i_2^⊤ S_2^⊤ S_2 ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) ) | 
    ≤     v _2 ·max_i_2 ∈ [n_3]  L · | w_2,i_2^⊤ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) - w_2,i_2^⊤ S_2^⊤ S_2 ϕ_1 ( W_1^⊤ S_1^⊤ S_1 x ) | 
    ≤     v _2 ·max_i_2 ∈ [n_3]  L ·ϵ_2 · w_2,i_2_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) _2 
    ≤     v _2 ·max_i_2 ∈ [n_3]  L ·ϵ_2 · w_2,i_2_2 max_i_1∈ [n_2]√(n_2) | ϕ_1 (w_1,i_1^⊤ S_1^⊤ S_1 x) | 
    ≤     v _2 ·max_i_2 ∈ [n_3]  L ·ϵ_2 · w_2,i_2_2 max_i_1∈ [n_2] L | w_1,i_1^⊤ S_1^⊤ S_1 x | 
    ≤     v _2 ·max_i_2 ∈ [n_3]  L ·ϵ_2 · w_2,i_2_2 max_i_1 ∈ [n_2] (1+ϵ_1) L  w_1,i_1_2   x _2 
    ≤     2 ϵ_2 L^2 B^3 A,

where the first step follows by Cauchy-Shawrz inequality, the second step follows by Fact <ref>, the third step follows by property of activation function, the fourth step follows by S_2 is a (1±ϵ_2) ℓ_2 subspace embedding, the fifth step follows by Fact <ref>, the sixth step follows by property of activation function, the seventh step follows by S_1 is a (1±ϵ_1) ℓ_2 subspace embedding, and the last step follows by v _2,  w_2,i_2_2 ,  w_1,i_1_2 ≤ B and x _2 ≤ A.



| ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1(W_1^⊤ S_1^⊤ S_1 x) ) - ⟨ S_3 v, S_3 ϕ_2(W_2^⊤ S_2^⊤ S_2  ϕ_1 (W^⊤ S_1^⊤ S_1 x) ) ⟩ | ≤ 2 ϵ_3 L^2 B^3 A.



We have

    | ⟨ v, ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) - ⟨ S_3 v, S_3 ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W^⊤ S_1^⊤ S_1 x) ) ⟩ | 
    ≤    ϵ_3  v _2 ·ϕ_2 (W_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) )  _2 
    ≤    ϵ_3  v _2 · L max_i_2 ∈ [n_3] | w_2,i_2^⊤ S_2^⊤ S_2 ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) | 
    ≤    ϵ_3  v _2 · L max_i_2 ∈ [n_3] (1+ϵ_2)   w_2,i_2_2 ·ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) _2 
    ≤    ϵ_3  v _2 · L max_i_2 ∈ [n_3] (1+ϵ_2)   w_2,i_2_2 · L max_i_1 ∈ [n_2] | w_1,i_1^⊤ S_1^⊤ S_1 x | 
    ≤    ϵ_3  v _2 · L max_i_2 ∈ [n_3] (1+ϵ_2)   w_2,i_2_2 · L max_i_1 ∈ [n_2] (1+ϵ_1)  w_1,i_1_2   x _2 
    ≤     2ϵ_3 L^2 B^3 A,

where the first step follows by S_3 is a (1±ϵ_3) ℓ_2 subspace embedding, the second step follows by Fact <ref> and the property of activation function, the third step follows by S_2 is a (1±ϵ_2) ℓ_2 subspace embedding, the fourth step follows by Fact <ref>, the fifth step follows by S_1 is a (1±ϵ_1) ℓ_1 subspace embedding, and last step follows v_2,  w_2,i_2_2,  w_1,i_1_2 ≤ B and x _2 ≤ A.




 §.§ Multiple hidden layers


The goal of section is to present Theorem <ref>.

Given parameters q≥ 1, n_j ≥ 1,∀ j ∈ [q+1] ,ϵ∈ (0,1), δ∈ (0,1) and n=max_j ∈ [q+1] n_j. For each j ∈ [q], for each i ∈ [n_j+1]
let ϕ_j,i :→ denote an activation function  with L-Lipshitz and normalized by 1/√(n_j+1). Given a fixed matrix U ∈^n_1 × d, q weight matrices W_j ∈^n_j+1× n_j, ∀ j ∈ [q] with (the i_j-th column of W_j) w_j,i_j∈ B_2(B,n_j), a weight vector v∈^n_j+1 with v ∈ B_2(B,n_j+1). For each j ∈ [q+1], we choose a SparseEmbedding matrix S_1 ∈^s_j × n_j with 
 
    s_j= O( d q^2 L^2q B^2q+2 A^2 ϵ^-2log (n q L B A / (ϵδ) )  ).

Then with probability 1-δ, we have : for all x ∈colspan(U) ∩ B_2(A, n_1), 

    | ⟨ v, ϕ_q ( W_q^⊤⋯ϕ_2 (W_2^⊤ϕ_1(W_1^⊤ x) ) ) ⟩ - ⟨ S_q+1 v, S_q+1ϕ_q( W_q^⊤ S_q^⊤ S_q ⋯ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ) ⟩ | ≤ϵ.


To provide a clear proof, we define some notations to simplify the multiple hidden layer neural network,

We first define the base

    f^(0)(x) = f^(0)(x) = x.

Then we define the general case in a recursive way,

    f^(j)(x) =     ϕ_j(W_j^⊤ f^(j-1)(x) ), ∀ j ∈ [q] 
    f^(j)(x) =     ϕ_j(W_j^⊤ S_j^⊤ S_j f^(j-1)(x) ), ∀ j ∈ [q] 
    
    f^(j,l)∘f^(l-1)(x) =     ϕ_j(W_j^⊤⋯ϕ_l ( W_l^⊤f^(l-1)(x) ) ), ∀ j ∈ [q], l∈{1, ⋯, j +1}.

Note that f^(j,1)∘f^(0)(x) = f^(j)(x) and f^(j,j+1)∘f^(j)(x) = f^(j)(x).

Using the above definition, it is easy to see that

    ⟨ v , ϕ_q (W_q^⊤⋯ϕ_2 (W_2^⊤ϕ_1 ( W_1^⊤ x )  ) ) ⟩ = ⟨ v, f^(q)(x) ⟩,

and

    ⟨ S_q+1 v, S_q+1ϕ_q( W_q^⊤ S_q^⊤ S_q ⋯ϕ_2 (W_2^⊤ S_2^⊤ S_2  ϕ_1 (W_1^⊤ S_1^⊤ S_1 x) ) ) ⟩ = ⟨ S_q+1 v, S_q+1f^(q)(x) ⟩.

Thus, we have

    |  ⟨ v, f^(q)(x) ⟩ - ⟨ S_q+1 v, S_q+1f^(q)(x) ⟩ | 
    ≤    ∑_l=1^q | ⟨ v, f^(q,l)∘f^(l-1) (x) ⟩ - ⟨ v, f^(q,l+1)∘f^(l) (x) ⟩ | + | ⟨ v, f^(q)(x) - ⟨ S_q+1 v, S_q+1f^(q)(x)|.

Now the question is how to bound the above q+1 terms.


| ⟨ v, f^(q)(x) - ⟨ S_q+1 v, S_q+1f^(q)(x)| ≤ 4 ϵ_q L^q B^q+1 A^q.


We have,

    | ⟨ v, f^(q)(x) - ⟨ S_q+1 v, S_q+1f^(q)(x)| 
    ≤    ϵ_q+1 v _2 ·f^(q)(x) _2 
    ≤    ϵ_q+1 L^q B^q+1 A^q ∏_j=1^q (1+ϵ_j) 
    ≤     4 ϵ_q+1 L^q B^q+1 A^q,

where the first step follows by S_q+1 is a (1±ϵ_q+1) ℓ_2 subspace embedding, the second step follows by applying the argument in the proof of Lemma <ref> recursively, and the last step follows by ϵ_j < 1/q.


Similarly, we have

∀ l ∈ [q], | ⟨ v, f^(q,l)∘f^(l-1) (x) ⟩ - ⟨ v, f^(q,l+1)∘f^(l) (x) ⟩ | ≤ 4 ϵ_l L^q B^q+1 A^q.


We have 

    | ⟨ v, f^(q,l)∘f^(l-1) (x) ⟩ - ⟨ v, f^(q,l+1)∘f^(l) (x) ⟩ | 
    ≤    ϵ_l L^q B^q+1 A^q ∏_i=l-1^1 (1+ϵ_i) 
    ≤     4 ϵ_l L^q B^q+1 A^q,

where the first step follows by applying the argument in the proof of Lemma <ref> recursively, and the last step follows by ϵ_i < 1/p.

Putting it all together, 

    |  ⟨ v, f^(q)(x) ⟩ - ⟨ S_q+1 v, S_q+1f^(q)(x) ⟩ | ≤ 4 ( ∑_j=1^q+1ϵ_j ) L^q B^q+1 A^q.

Therefore, we can show the error is small.

We also need the ϵ-net argument for all j ∈ [q+1], it also follows by applying the proof of Section <ref> recursively. 

Therefore, we complete the proof.






§ RECOVERY GUARANTEE






 §.§ Preliminaries



Let k be an even integer, and let X be the sum of n k-wise independent random variables taking values in [0,1]. Let μ[X] and a >0. Then we have

    [ | X - μ | > a ] <      1.1 ( nk/a^2)^k/2, 
    [ | X - μ | > a ] <      8 (  k μ + k^2 /a^2)^k/2.






 §.§ Definitions


Let w∈^n × k denote the weights. Let w_i ∈^n denote the i-th column of w. Let w_i,j denote the j-th entry of w_i. Let h denote a hash function that maps [k] × [n] to [B]. Let w∈^B denote a vector. Then for each i∈ [k], j ∈ [n], we have w_ h(i,j)  = w_i,j.


[Property 3.2 in <cit.>]
Let α_q(σ) = _z∼ N(0,1)  [ ϕ'(σ· z) z^q ], ∀ q ∈{0,1,2}, and β_q(σ) = _ z ∼ N(0,1)  [ ϕ'^2(σ· z) z^q ], ∀ q ∈{0,2}. Let ρ(σ) denote

    min{β_0(σ) - α_0^2 (σ) - α_1^2(σ) , β_2(σ) - α_1^2(σ) - α_2^2(σ), α_0(σ) ·α_2(σ) - α_1^2 (σ) }.

The first derivative ϕ'(z) satisfies that, for all σ > 0, we have ρ(σ) >0.




 §.§ Local strong convexity

Recall the definition

    F_ D(w) = 1/2_(x,y) ∼ D[ ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j)· x_j ) - y )^2 ],


    F_S(w) = 1/21/|S|∑_(x,y) ∈ S[ ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j)· x_j ) - y )^2 ],

where ϕ is activation function. All of Section <ref> assumes that ϕ satisfies the Property 3.1, 3.2 and 3.3 in <cit.>.

We use 1_h(i,j) = p to denote the indicator function which means

    1_h(i,j) =
    
    1,     if  h(i,j) = p ; 
    
    0,     otherwise.

For each p∈ [B], we have

    ∂ F /∂ w_p  = _(x,y) ∼ D[ ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j)  x_j ) -y  )
    ·( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j )   )
     ].


For q ≠ p ∈ [B], have

    ∂^2 F /∂ w_p ∂ w_q  =     _(x,y) ∼ D[
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) . 
        ·( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = q· x_j ) ) 
         + ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j)  x_j ) -y  ) 
        ·. ( ∑_i=1^k v_i^* ·ϕ”( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ·( ∑_j=1^n  1_h(i,j) = q· x_j )   ) ] 
    
    =     _(x,y) ∼ D[
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) . 
        ·.
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = q· x_j ) ) ],

where the last step follows by ϕ” = 0.

For p = q ∈ [B], we have

    ∂^2 F /∂ w_p^2  =     _(x,y) ∼ D[
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) . 
        ·( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) 
         + ( ∑_i=1^k v_i^* ·ϕ( ∑_j=1^n w_h(i,j)  x_j ) -y  ) 
        ·. ( ∑_i=1^k v_i^* ·ϕ”( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j )   ) ] 
    
    =     _(x,y) ∼ D[
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) . 
        ·.
    ( ∑_i=1^k v_i^* ·ϕ' ( ∑_j=1^n w_h(i,j) x_j ) ·( ∑_j=1^n  1_h(i,j) = p· x_j ) ) ],

where the last step follows by ϕ” = 0.

Before presenting the main theorem, we provide some definition here,

Given w^* ∈^B and hash function h : [k] × [n] → [B]. The matrix w^* ∈^k × n is defined in Definition <ref>
For each i∈ [k], we use σ_i to denote the i-th singular value of matrix w^*. Let κ = σ_1 /σ_k, λ = (∏_i=1^k σ_i)/σ_k^k. We define v_max = max_i∈ [k] |v_i^*| and v_min = min_i∈ [k] |v_i^*|. For simplicity, let ν = v_max / v_min. Let function ρ(σ) be defined in Property <ref>. Let p be defined in Property 3.1 in <cit.>.


We present our main theorem here,

Let F_ D be defined in Eq. (<ref>). Let N= nk. Let H denote a family of Θ(log N)-wise independent hash functions that maps [N] → [B]. Then choosing h ∼ H, we have

    kn/2B· A_min· I_B ≼∇^2 F_ D(w^*) ≼2kn/B· A_max·  I_B

holds with probability at least 1-1/(N), where 

    A_min = Ω(  v_min^2 ρ(σ_k) /κ^2 λ ),  and   A_max = O(k v_max^2 σ_1^2p).



It follows by combining Lemma <ref> and Lemma <ref> directly.



The A_min and A_max are the exact same as <cit.>. Once we have reduced the Hessian of HashNet to the Hessian of Fully-connected Net, we run the analysis of <cit.> as a black-box.


Further we have


Choose a random hash function h, for each vector w, let matrix w be defined according to w and h(Definition <ref>).
For any w ∈^B with w - w^* ≤(1/k,1/λ,1/ν, ρ/σ_1^2p) ·w^*, let S denote a set of i.i.d. samples from distribution D and the activation satisfy Property 3.1,3.2,3.3 in <cit.>. Let F_S be defined as Eq. (<ref>). Then for any t≥ 1, if

    | S | ≥ n ·(log n, t, k, ν, τ, λ, σ_1^2p/p),

we have

    nk/2B A_min I ≼∇^2 F_S(w^*) ≼2nk/B A_max I

holds with probability at least 1-n^-Ω(t).





 §.§ Linear convergence of gradient descent


Finally, following the similar ideas in <cit.>, we can show

Let w^c be the current iterate satisfying

    w^c - w^* ≲(1/k,1/κ,1/λ,1/ν,ρ/σ_1^2p) · w^* .

Let S denote a set of i.i.d. samples from distribution D. Let the activation function satisfy Property 3.1, 3.2 and 3.3(a) in <cit.>. Let F_S be defined as Eq. (<ref>). Let m_0 = Θ( v_min^2 ρ(σ_k) / (κ^2 λ) ) and M_0 = Θ( k v_max^2 σ_1^2p). For any t≥ 1, if we choose

    |S| ≥ n · (log n, t, κ,λ, τ , ν , σ_1^2p/ρ)

and perform gradient descent with step size 1/M_0 on F_S(w^c) and obtain the next iterate,
w = w^c - 1/M_0∇ F_S(w^c),
then 
w - w^* _2^2 ≤( 1 - m_0 / M_0 )  w^c - w^* _2^2
holds with probability at least 1-n^-Ω(t).





 §.§ Lower bound on eigenvalues

The goal of this section is to prove Lemma <ref>.

Let F_ D be defined in Eq. (<ref>). Let N= nk. Let H denote a family of Θ(log N)-wise independent hash functions that maps [N] → [B]. Then choosing h ∼ H, we have

    ∇^2 F_ D(w^*) ≽1/2kn/B v_min^2 ρ(σ_k) /κ^2 λ,

holds with probability at least 1-1/(N).



Let a∈^B.
The smallest eigenvalue of the Hessian can be calculated by

    ∇^2 F(w^*) ≽    min_ a = 1 a^⊤∇^2 F(w^*) a · I_B
    
    =     min_ a  = 1_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ] · I_B,

where I_B is a B × B identity matrix.

The goal is to lower bound the above quantity, we can simplify it in the following way,

    min_ a  = 1, a ∈^B_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ].


For each i ∈ [k], j ∈ [n], we define b_i,j as follows

    b_i,j = ∑_p ∈ [B] a_p  1_ h_(i,j) = p .


Then we can rewrite Eq. (<ref>) by using the definition b in the following way,

    min_ a  = 1, a ∈^B_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ] 
    
    =     min_ a  = 1, a ∈^B_x[ ( ∑_i=1^k ∑_j=1^n ∑_p∈[B] a_p · 1_h(i,j)=p· x_j · v_i^* ·ϕ'( w_i^*⊤· x ) )^2 ] 
    
    =     min_ a  = 1, a ∈^B_x[ ( ∑_i=1^k ∑_j=1^n b_i,j· x_j · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] 
    
    =     min_ a  = 1, a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] 
    
    =     min_a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  /  a _2^2 
    ≥    min_a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  b _2^2 B / (kn) ) 
    
    =     min_b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  b _2^2 B / (kn) ) 
    
    =     min_ b _2^2 =1, b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  B / (kn) ) 
    
    =     kn/2B·min_ b _2^2 =1, b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] _A_min,

where the first step follows by swapping the sums, definition of 1_h(i,j)=p and the ground-truth weight matrix can be viewed in two ways (see Fact <ref>), the second step follows by ∑_p∈ [B] a_p · 1_ h(i,j) = p, the third step follows by ∑_j=1^n b_i,j x_j = b_i^⊤ x.

Now the term A_min is exact the same as the Equation (9) in page 34 of arXiv version of <cit.>.
Therefore, we can use Lemma D.6 in page 33 of <cit.>, it provides 
A_min≥ v_min^2 ρ(σ_k) / ( κ^2 λ ) .





 §.§ Upper bound on eigenvalues

The goal of this section is to prove Lemma <ref>.

Let F be defined in Eq. (<ref>). Let N= nk. Let H denote a family of Θ(log N)-wise independent hash functions that maps [N] → [B]. Then choosing h ∼ H, we have

    ∇^2 F(w^*) ≼ 2 kn/B k v_max^2 σ_1^2p I_B,

holds with probability at least 1-1/(N).


Let a∈^B.
The largest eigenvalue of the Hessian can be calculated by

    ∇^2 F(w^*) ≽    max_ a = 1 a^⊤∇^2 F(w^*) a · I_B
    
    =     max_ a  = 1_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ] · I_B,

where I_B is a B × B identity matrix.

The goal is to lower bound the above quantity, we can simplify it in the following way,

    max_ a  = 1, a ∈^B_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ].


For each i ∈ [k], j ∈ [n], we define b_i,j as follows

    b_i,j = ∑_p ∈ [B] a_p  1_ h_(i,j) = p .


Then we can rewrite Eq. (<ref>) by using the definition b in the following way,

    max_ a  = 1, a ∈^B_x[ ( ∑_p∈ [B] a_p ∑_i=1^k v_i^* ·ϕ'( ∑_j=1^n w_h(i,j)^* x_j ) ·∑_j=1^n  1_h(i,j) = p x_j )^2 ] 
    
    =     max_ a  = 1, a ∈^B_x[ ( ∑_i=1^k ∑_j=1^n ∑_p∈[B] a_p · 1_h(i,j)=p· x_j · v_i^* ·ϕ'( w_i^*⊤· x ) )^2 ] 
    
    =     max_ a  = 1, a ∈^B_x[ ( ∑_i=1^k ∑_j=1^n b_i,j· x_j · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] 
    
    =     max_ a  = 1, a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] 
    
    =     max_a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  /  a _2^2 
    ≥    max_a ∈^B_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  b _2^2 B / (kn) ) 
    
    =     max_b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  b _2^2 B / (kn) ) 
    
    =     max_ b _2^2 =1, b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ]  / ( 2  B / (kn) ) 
    
    =     kn/2B·max_ b _2^2 =1, b ∈^nk_x[ ( ∑_i=1^k b_i^⊤ x · v_i^* ·ϕ'( w_i^*⊤· x )  )^2 ] _A_max,

where the first step follows by swapping the sums, definition of 1_h(i,j)=p and the ground-truth weight matrix can be viewed in two ways (see Fact <ref>), the second step follows by ∑_p∈ [B] a_p · 1_ h(i,j) = p, the third step follows by ∑_j=1^n b_i,j x_j = b_i^⊤ x.

Now the term A_max is exact the same as the Equation in page 38 of arXiv version of <cit.>.
 Therefore, we can use Lemma D.7 in page 37 of <cit.>, which provides 
A_max≤ O(k v_max^2 σ_1^2p) .







 §.§ Analysis of Hashing schemes


With probability 1- 1 /  (nk), we have

    2  a _2^2 kn/B≥ b _2^2 ≥1/2 a _2^2 kn/B.



We consider the square of the entry-wise ℓ_2 norm of b (we define b in a matrix way, but we can view it as a vector),

    b _2^2 =     ∑_i=1^k ∑_j=1^n b_i,j^2 
    
    =     ∑_i=1^k ∑_j=1^n ( ∑_p∈ [B] a_p  1_ h(i,j) = p )^2 
    
    =     ∑_i=1^k ∑_j=1^n ( diagonal-term + off-diagonal-term) 
    
    =     ∑_i=1^k ∑_j=1^n ( ∑_p∈ [B] a_p^2  1_h(i,j) = p + ∑_p ≠ q a_p a_q  1_h(i,j)=p 1_h(i,j)=q) 
    
    =     ∑_i=1^k ∑_j=1^n ∑_p∈ [B] a_p^2  1_h(i,j) = p
    
    =     ∑_p∈ [B] a_p^2  ∑_i=1^k ∑_j=1^n  1_h(i,j) = p
    ≥    ∑_p∈ [B] a_p^2 ·1/2kn/B
    
    =     1/2 a _2^2 kn/B,

where the first step follows by viewing b as a vector, the last step follows by Lemma <ref>.




Given integers N and B ≲ N / log N. Let h : [N] → [B] denote a t-wise independent hash function such that 

    _h ∼ H[ h(i) = j] = 1/B, ∀ i ∈ [N], ∀ j ∈ [B].

Then,

(1), if t = Θ(log N), with probability at least 1 - 1 / (N), we have for all j ∈ [B],

    0.9 N/B ≤∑_i=1^N  1_h(i) = j≤ 1.1 N/B;

(2), if t = Θ(log B), with probability at least 1 - 1 / (B), we have for all j ∈ [B],

    0.9 N/B ≤∑_i=1^N  1_h(i) = j≤ 1.1 N/B.




First, notice that [ h(i) = p ] = 1/B. We can estimate the expectation,

    [ ∑_i=1^N h(i) = p ] = N/B≫ 1.


By Theorem <ref> for t-wise, we have

    [ | ∑_i=1^N  1_h(i) = p - N/B| > a ] < 8 ( t N/B + t^2/a^2)^t/2.

Choosing a = 0.1 N/B, we have

    [ | ∑_i=1^N  1_h(i) = p - N/B| > 0.1 N/B ] <      8 ( 100 N/ (N/B)^2  )^t/2
    
    =      8 ( t N/B + t^2/0.01 N^2/B^2 )^t/2
    ≤     8 ( 2t N/B/0.01 N^2/B^2)^t/2    by  N/B > t 
    
    =      8 (  200 t /  N/B  )^t/2
    ≤     8 (1/10)^t/2    by  N/B > 2000 t 
    ≤     1/(N)     by  t = Θ(log N).

The total number of p's is at most B and N ≥ B, thus by taking a union bound, we prove the part (1).

For part (2), the only change is setting t = Θ(log B). We can still take a union over all p, thus we complete the proof of part (2).






 §.§ Weight matrix is almost full rank

In this section, we explain that making the assumption that weight matrix is full rank is reasonable in both theory and practice.

Consider the situation where B=2, the following result indicates that, the weight matrix will be full rank with high probability.

Let M ∈^n× n denote a matrix where each entry is +1 with probability 1/2 and -1 with probability 1/2, then

    [ (M) = n ] ≥ 1 - ( 1/√(2) + o(1) )^n.



Using Theorem 9.2 in <cit.> and Lemma in <cit.>, we have that with high probability the above Theorem also holds for general B > 2.

In addition, we also run experiments, we do observe that condition number of the weight matrix is not too big.





§ EXPERIMENTS





























