Title: SHORT AND DEEP: SKETCHING AND NEURAL NETWORKS

Abstract: Data-independent methods for dimensionality reduction such as random projections, sketches, and feature hashing have become increasingly popular in recent years. These methods often seek to reduce dimensionality while preserving the hypothesis class, resulting in inherent lower bounds on the size of projected data. For example, preserving linear separability requires Ω(1/γ 2 ) dimensions, where γ is the margin, and in the case of polynomial functions, the number of required dimensions has an exponential dependence on the polynomial degree. Despite these limitations, we show that the dimensionality can be reduced further while maintaining performance guarantees, using improper learning with a slightly larger hypothesis class. In particular, we show that any sparse polynomial function of a sparse binary vector can be computed from a compact sketch by a single-layer neural network, where the sketch size has a logarithmic dependence on the polynomial degree. A practical consequence is that networks trained on sketched data are compact, and therefore suitable for settings with memory and power constraints. We empirically show that our approach leads to networks with fewer parameters than related methods such as feature hashing, at equal or better performance.

1. INTRODUCTION:

In many supervised learning problems, input data are high-dimensional and sparse. The high dimensionality may be inherent in the domain, such as a large vocabulary in a language model, or the result of creating hybrid conjunction features. This setting poses known statistical and computational challenges for standard supervised learning techniques, as high-dimensional inputs lead to models with a very large number of parameters.

An increasingly popular approach to reducing model size is to map inputs to a lower-dimensional space in a data-independent manner, using methods such as random projections, sketches, and hashing. These mappings typically attempt to preserve the hypothesis class, leading to inherent theoretical limitations on size. For example, for linearly separable unit vectors with margin γ, it can be shown that at least Ω(1/γ 2 ) dimensions are needed to preserve linear separability, even if one can use arbitrary input embeddings (see Section D). It would therefore appear that data dimensionality cannot be reduced beyond this bound.

In this work, we show that using a slightly larger hypothesis class when decoding projections (improper learning) allows us to further reduce dimensionality while maintaining theoretical guarantees. In particular, we show that any sparse polynomial function of a sparse binary vector can be computed from a very compact sketch by a single-layer neural network. The hidden layer allows us to "decode" inputs from representations that are smaller than in existing work. In the simplest case, we show that for linearly separable k-sparse d-dimensional inputs, one can create a O(k log d δ )-dimensional sketch of the inputs and guarantee that a single-layer neural network can correctly classify 1 -δ fraction of the sketched data. In the case of polynomial functions, the required sketch size has a logarithmic dependence on the polynomial degree.

For binary k-sparse input vectors, we show that it suffices to have a simple feed-forward network with nonlinearity implemented via the commonly used rectified linear unit (Relu). We extend our results to real-valued data that is close to being k-sparse, using less conventional min and median nonlinearities. Furthermore, we show that data can be mapped using sparse sketching matrices.

Parameter reduction in deep learning. Our work can be viewed as a method for reducing the number of parameters in neural networks. Neural networks have become ubiquitous in many machine learning applications, including speech recognition, computer vision, and language processing tasks(see (Hinton et al., 2012; Krizhevsky et al., 2012; Sermanet et al., 2013; Vinyals et al., 2014) for a few notable examples). These successes have in part been enabled by recent advances in scaling up deep networks, leading to models with millions of parameters (Dean et al., 2012; Krizhevsky et al., 2012) . However, a drawback of such large models is that they are very slow to train, and difficult to deploy on mobile and embedded devices with memory and power constraints. Denil et al. (2013) demonstrate significant redundancies in the parameterization of several deep learning architectures, and they propose training low-rank decompositions of weight matrices. Cheng et al. (2015) impose circulant matrix structure on fully connected layers. Ba and Caruana (2014) train shallow networks to predict the log-outputs of a large deep network, and Hinton et al. (2015) train a small network to match smoothed predictions of a complex deep network or an ensemble of such models. Collins and Kohli (2014) encourage zero-weight connections using sparsity-inducing priors, while others such as LeCun et al. (1989) ; Hassibi et al. (1993) ; Han et al. (2015) use techniques for pruning weights. HashedNets (Chen et al., 2015) enforce parameter sharing between random groups of network parameters. In contrast to these methods, sketching only involves applying a sparse, linear projection to the inputs, and does not require a specialized learning procedure or network architecture.

3. SKETCHING:

For simplicity, we first present our results for sparse binary vectors, and extend the discussion to real-valued vectors to Appendix A. Let B d,k = {x ∈ {0, 1} d : x 0 ≤ k} be the set of ksparse d-dimensional binary vectors. We sketch such vectors using a family of randomized sketching algorithms based on the count-min sketch, as described next.

Given a parameter m and a hash function h : [d] → [m], the sketch S h (x) of a vector x ∈ B d,k is a binary vector y where each bit of y is the OR of bits of x that hash to it:

y l = i : h(i) = l x i .

We map data using a concatenation of several such sketches. Given an ordered set of hash functions h 1 , . . . , h t def = h 1:t , the sketch S h1:t (x) is defined as a m × t matrix Y , where the j th column corresponds to the sketch S hj (x). We define the following procedure for decoding the i th bit of the input x from its sketch Y :

D AND h1:t (Y, i) def = j∈[t]

Y hj (i)j .

(1) Thus, the decoded bit i is simply the AND of the t bits of Y that index i hashes to in the sketch.

The following theorem summarizes an important property of these sketches. As a reminder, a set of hash functions

h 1:t from [d] to [m] is pairwise independent if for all i = j ∈ [d] and a, b ∈ [m], Pr[h(i) = a ∧ h(j) = b] = m -2 . 1 Theorem 3.1. Let x ∈ B d,k and for j ∈ [t] let h j : [d] → [m]

be drawn uniformly and independently from a pairwise independent distribution with m = ek. Then for any i,

Pr[D AND h1:t (S h1:t (x), i) = x i ] ≤ e -t . Proof. Fix a vector x ∈ B d,k . Let E h (i) def = {i = i : h(i ) = h(i)} denote

the collision set of i for a particular hash function h. Decoding will fail if x i = 0 and for each of the t hash functions, the collision set of i for contains an index of a non-zero bit of x. For a particular h, the probability of this event is:

P r   i ∈E h (i) x i = 1   ≤ i :x i =1 Pr[h(i ) = h(i)] ≤ k m = 1 e ,

where the second inequality follows since the sum is over at most k terms, and each term is m -1 by pairwise independence. Thus Let w ∈ H d,s , x ∈ B d,k , and Y = S h1:t (x) for m, t satisfying the conditions of Corollary 3.2. We will now argue that there exists a one-layer neural network that takes Y as input and outputs w x with high probability (over the randomness of the sketching process).

Pr[Y hj (i) = x i ] ≤ e -

Let N n (f ) denote the family of feedforward neural networks with one hidden layer containing n nodes, nonlinearity f applied at each hidden unit, and a linear function at the output layer. We can construct a network in N s (Relu) such that each hidden unit implements D AND h1:t (Y, i) (i.e. decodes bit x i from the sketch) for each index i in the support of w. We can then set the output weights of the network to the corresponding non-zero weights w i to get w x.

It remains to show that a hidden unit can implement D AND h1:t (Y, i). Indeed, the AND of t bits can be implemented using nearly any non-linearity. With Relu(a) = max{0, a}, we can construct the activation for bit x i , a i = (l,j) V lj Y lj + B i , by setting the appropriate t weights in V lj to 1, setting remaining weights to 0, and setting the bias B i to 1 -t. Using Corollary 3.2, we have the following theorem. Theorem 4.1. For every w ∈ H d,s there exists a set of weights for a network N ∈ N s (Relu) such that for each x ∈ B d,k , P r h1:t [N (S h1:t (x)) = w x] ≥ 1 -δ , as long as m = ek and t = log(s/δ). Moreover, the weights coming into each node in the hidden layer are in {0, 1} with at most t non-zeros.

The final property implies that when using w as a linear classifier, we get small generalization error as long as the number of examples is at least Ω(s(1 + t log mt)). This can be proved, e.g., using standard compression arguments: each such model can be represented using only st log(mt) bits in addition to the representation size of w. Similar bounds hold when we use 1 bounds on the weight coming into each unit. Note that even for s = d (i.e. w is unrestricted), we get non-trivial input compression.

For comparison, we prove the following result for Gaussian projections in the appendix B. In this case, the model weights in our construction are not sparse. Theorem 4.2. For every w ∈ H d,s there exists a set of weights for a network N ∈ N s (Relu) such that for each

x ∈ B d,k , P r h1:t [N (Gx)) = w x] ≥ 1 -δ ,

as long as G is a random m × d Gaussian matrix, with m ≥ 4k log(s/δ).

5. SPARSE POLYNOMIAL FUNCTIONS:

For boolean inputs, Theorem 4.1 extends immediately to sparse polynomial functions. Note that we can implement the AND of two bits x i ∧x j as the AND of the corresponding decodings D AND h1:t (Y, i) and D AND h1:t (Y, j). Since each decoding is an AND of t bits, the overall decoding is an AND of at most 2t locations in the sketch. More generally, we have the following theorem: Theorem 5.1. Given w ∈ R s , and sets

A 1 , . . . , A s ⊆ [d], let g : {0, 1} d → R denote the polynomial g(x) = s j=1 w j i∈Aj x i = s j=1 w j i∈Aj x i .

Then there exists a set of weights for a network N ∈ N s (Relu) such that for each

x ∈ B d,k , P r h1:t [N (S h1:t (x)) = g(x)] ≥ 1 -δ ,

as long as m = ek and t = log(| ∪ j∈[s] A j |/δ). Moreover, the weights coming into each node in the hidden layer are in {0, 1} with at most t • j∈[s] |A j | non-zeros overall. In particular, when g is a degree-p polynomial, we can set t = log(ps/δ), and each hidden unit has at most pt non-zero weights.

This is a setting where we get a significant advantage over proper learning. To our knowldege, there is no analog of this result for Gaussian projections. Classical sketching approaches would use a sketch of x ⊗p , which is a k p -sparse vector over binary vectors of dimension d p . Known sketching techniques such as Pham & Pagh (2013) would construct a sketch of size Ω(k p ). Practical techniques such as Vowpal Wabbit also construct cross features by explicitly building them and have this exponential dependence. In stark contrast, neural networks allow us to get away with a logarithmic dependence on p.

Using polynomial kernels. Theorems 4.1 has a corresponding variants where the neural net is replaced by a polynomial of degree t. Similarly, the neural net in Theorem 5.1 can be replaced by a degree-pt polynomial when the polynomial g has degree p. This implies that one can use a polynomial kernel to get efficient learning. Deterministic sketching. A natural question that arises is whether the parameters above can improved. We show in App. C that if we allow large scalars in the sketches, one can construct a deterministic (2k + 1)-dimensional sketch from which a shallow network can reconstruct any monomial. We also show a lower bound of k on the required dimensionality.

Lower bound for proper learning. We can also show, see App. D, that if one does not expand the hypothesis class, then even in the simplest of settings of linear classifiers over 1-sparse vectors, the required dimensionality of the projection is much larger than the dimension needed for improper learning. The result is likely folklore and thus we present a short proof in the appendix for completeness using concrete constants in the theorem and its proof below.

Neural nets on Boolean inputs. We remark that for Boolean inputs (irrespective of sparsity), any polynomial with s monomials can be represented by a neural network in N s (Relu) using the construction in Theorem 5.1.

6. EXPERIMENTS WITH SYNTHETIC DATA:

In this section, we evaluate sketches on synthetically generated datasets for the task of polynomial regression. In all the experiments here, we assume input dimension d = 10 4 , input sparsity k = 50, hypothesis support s = 300, and n = 2 × 10 5 examples. We assume that only a subset of features I ⊆ [d] are relevant for the regression task, with |I| = 50. To generate an hypothesis, we select s subsets of relevant features A 1 , . . . , A s ⊂ I each of cardinality at most 3, and generate the corresponding weight vector w by drawing corresponding s non-zero entries from the standard Gaussian distribution. We generate binary feature vectors x ∈ B d,k as a mixture of relevant and other features. Concretely, for each example we draw 12 feature indices uniformly at random from I, and the remaining indices from [d] . We generate target outputs as g(x) + z, where g(x) is in the form of the polynomial given in Theorem 5.1, and z is additive Gaussian noise with standard deviation 0.05. In all experiments, we train on 90% of the examples and evaluate mean squared error on the rest.

We first examined the effect of the sketching parameters m (hash size) and t (number of hash functions) on sparse linear regression error. We generated synthetic datasets as described above (with all feature subsets in A having cardinality 1) and trained networks in N s (Relu). The results are shown in Figure 2 (left). As expected, increasing t leads to better performance. Using hash size m less than the input sparsity k leads to poor results, while increasing hash size beyond ek (in this case, ek 136) for reasonable t yields only modest improvements.

We next examined the advantages of improper learning. We generated 10 sparse linear regression datasets and trained linear models and networks in N s (Relu) on original and sketched features with We repeated the previous experiment for 10 polynomial regression datasets, generated with feature subsets in A of cardinality 2 and 3. The results are shown in Figure 2 (right). The linear model is a bad fit, showing that g(x) is not well approximated by a linear function. Neural networks applied to sketches succeed in learning a small model and achieve significantly lower error than a network applied to the original features for t ≥ 6. This suggests that reducing the input size, and consequently the number of model parameters, can lead to better generalization. Note that previous work on hashing and projections would imply using significantly larger sketch size for this setting.

We also compared our sketches to Gaussian random projections. We generated sparse linear and polynomial regression datasets with the same settings as before, and reduce the dimensionality of the inputs to 1000, 2000 and 3000 using Gaussian random projections and sketches with t ∈ {1, 2, 6}. We remark that in this comparison, the column headings correspond to the total sketch size mt. Thus, e.g., when we take t = 6, m is correspondingly reduced. We report the squared error averaged across examples and five datasets of one-layer neural networks in Table 1 . The results demonstrate that sketches with t > 1 yield lower error than Gaussian projections. Note also that Gaussian projections are dense and hence much slower to train.

7. EXPERIMENTS WITH LANGUAGE PROCESSING TASKS:

Linear and low degree sparse polynomials are often used for classification. Our results imply that if we have linear or a sparse polynomial with classification accuracy 1-ε over some set of examples in B d,k × {0, 1}, then neural networks constructed to compute the linear or polynomial function attain accuracy of at least 1 -ε -δ over the same examples. Moreover, the number of parameters in the new network is relatively small by enforcing sparsity or 1 bounds for the weights into the hidden layers. We thus get generalization bounds with negligible degradation with respect to nonsketched predictor. In this section, we evaluate sketches on the language processing classification tasks described below. AG-news Topic Classification. We perform topic classification on 680K articles from AG news corpus, labeled with one of 8 news categories: Business, Entertainment, Health, Sci/Tech, Sports, Europe, U.S., World. For each document, we extract binary word indicator features from the title and description; in total, there are 210K unique features, and on average, 23 non-zero features per document.

Experimental Setup. In all experiments, we use two-layer feed-forward networks with ReLU activations and 100 hidden units in each layer. We use a softmax output for multiclass classification and multiple binary logistic outputs for multilabel tasks. We experimented with input sizes of 1000, 2000, 5000, and 10,000 and reduced the dimensionality of the original features using sketches with t ∈ {1, 2, 4, 6, 8, 10, 12, 14} blocks. In addition, we experimented with networks trained on the original features. We encouraged parameter sparsity in the first layer using 1 -norm regularization and learn parameters using the proximal stochastic gradient method. As before, we trained on 90%

of the examples and evaluated on the remaining 10%. We report accuracy values for multiclass classification, and F1 score for multilabel tasks, with true positive, false positive, and false negative counts accumulated across all labels.

Results. Since one motivation for our work is reducing the number of parameters in neural network models, we plot the performance metrics versus the number of non-zero parameters in the first layer of the network. The results are shown in Figure 3 for different sketching configurations and settings of the 1 -norm regularization parameters (λ 1 ). On the entity type tagging task, we compared sketches to a single hash function of size 500,000 as the number of the original features is too large. In this case, sketching allows us to both improve performance and reduce the number of parameters. On the Reuters task, sketches achieve similar performance to the original features with fewer parameters. On AG news, sketching results in more compact models at a modest drop in accuracy. In almost all cases, multiple hash functions yield higher accuracy than a single hash function for similar model size.

8. CONCLUSIONS:

We have presented a simple sketching algorithm for sparse boolean inputs, which succeeds in significantly reducing the dimensionality of inputs. A single-layer neural network on the sketch can provably model any sparse linear or polynomial function of the original input. For k-sparse vectors in {0, 1} d , our sketch of size O(k log s/δ) allows computing any s-sparse linear or polynomial function on a 1-δ fraction of the inputs. The hidden constants are small, and our sketch is sparsity preserving. Previous work required sketches of size at least Ω(s) in the linear case and size at least k p for preserving degree-p polynomials. Our results can be viewed as showing a compressed sensing scheme for 0-1 vectors, where the decoding algorithm is a depth-1 neural network. Our scheme requires O(k log d) measurements, and we leave open the question of whether this can be improved to O(k log d k ) in a stable way. We demonstrated empirically that our sketches work well for both linear and polynomial regression, and that using a neural network does improve over a direct linear regression. We show that on real datasets, our methods lead to smaller models with similar or better accuracy for multiclass and multilabel classification problems. In addition, the compact sketches lead to fewer trainable parameters and faster training. the closest vector to x whose support size is k and the residue tail k

(x) = x -head k (x). Let R + d,k,c represent the set R + d,k,c = {x ∈ R d + : tail k (x) 1 ≤ c} , and let R d,k,c represent the set R d,k,c = {x ∈ R d : tail k (x) 1 ≤ c} .

For vectors in R + d,k,c , we use the following sketching and decoding procedures analogous to the binary case.

S h1:t (x) = [y 1 , ..., y t ] where y l = i:h(i)=l x i D MIN h1:t def = min j∈[t] (y hj (i) ) . Theorem A.1. Let x ∈ R + d,k,c

and let h 1 , . . . , h t be drawn uniformly and independently from a pairwise independent distribution, for m = e(k + 1 ε ). Then for any i,

Pr D MIN h1:t (S h1:t (x), i) ∈ [x i , x i + εc] ≤ e -t .

Proof. Fix a vector x ∈ R + d,k,c . To remind the reader, for a specific i and h, we have defined the set of collision indices E(i)

EQUATION

We can rewrite

D MIN h (S h (x), i) -x i = i ∈S(head k (x))∩E(i) x i + i ∈S(tail k (x))∩E(i) x i .

By definition of tail k (•), the expectation of the second term is c/m. Using Markov's inequality, we get that

Pr[ i ∈S(tail k (x))∩E(i) x i > εc] ≤ 1 εm .

To bound the first term, note that

Pr   i ∈S(head k (x))∩E(i) x i = 0   ≤ Pr   i ∈S(head k (x))∩E(i) 1 = 0   ≤ E   i ∈S(head k (x))∩E(i) 1   ≤ k m .

Recall that m = e(k + 1/ε), then, using the union bound establishes (2). The rest of the proof is identical to Theorem 3.1.

Corollary A.2. Let w ∈ H d,s and x ∈ R + d,k,c . For t = log(s/δ), and m = e(k + 1 ε ), if h 1 , . . . , h t are drawn uniformly and independently from a pairwise independent distribution, then

Pr | i w i • D MIN h1:t (S h1:t (x), i) -w x| ≥ εc w 1 ≤ δ .

The proof in the case that x may not be non-negative is only slightly more complicated. Let us define the following additional decoding procedure,

D MED h1:t (Y, i) def = Median j∈[t]

Y hj (i),j .

Theorem A.3. Let x ∈ R d,k,c , and let h 1 , . . . , h t be drawn uniformly and independently from a pairwise independent distribution, for m = 4e 2 (k + 2/ε). Then for any i,

Pr D MED h1:t (S h1:t (x), i) ∈ [x i -εc, x i + εc] ≤ e -t .

Proof. As before, fix a vector x ∈ R d,k,c and a specific i and h. We once again write

D MED h (S h (x), i) -x i = i ∈S(head k (x))∩E(i) x i + i ∈S(tail k (x))∩E(i)

x i .

By the same argument as the proof of Theorem A.1, the first term is nonzero with probability k/m.

The second term has expectation in [-c/s, c/s]. Once again by Markov's inequality,

Pr   i ∈S(tail k (x))∩E(i) x i > εc   ≤ 1 εm and Pr   i ∈S(tail k (x))∩E(i) x i < -εc   ≤ 1 εm .

Recalling that m = 4e2 (k + 2/ε), a union bound establishes that for any j,

Pr[|D MED hj (S hj (x), i) -x i | > εc] ≤ 1 4e 2 . Let X j be indicator for the event that |D MED hj (S hj (x), i) -x i | > εc. Thus X 1 , . . . , X t are binomial random variables with P r[X j = 1] ≤ 1 4e 2 . Then by Chernoff's bounds Pr D MED h1:t (S h1:t (x), i) ∈ [x i -εc, x i + εc] ≤ P r   j X j > t/2   ≤ exp - 1 2 ln 1/2 1/4e 2 + 1 2 ln 1/2 1 -1/4e 2 t ≤ exp - 1 2 ln 2e 2 + 1 2 ln 1 2 t ≤ exp(-t) .

Corollary A.4. Let w ∈ H d,s and x ∈ R d,k,c ,. For t = log(s/δ), and m = 4e 2 (k + 1 ε ), if h 1 , . . . , h t are drawn uniformly and independently from a pairwise independent distribution, then

Pr i w i D MED h1:t (S h1:t (x), i) -w x ≥ εc w 1 ≤ δ .

To implement D MIN (•) using hidden units in a neural network, we need to use a slightly nonconventional non-linearity. For a weight vector z and input vector x, a min gate implements min i:zi =0 z i x i . Then, using Corollary A.2, we get the following theorem. Theorem A.5. For every w ∈ H d,s there exists a set of weights for a network N ∈ N s (min) such that for each x ∈ R + d,k,c the following holds, P r h1:t |N (S h1:t (x)) -w x| ≥ εc w 1 ≤ δ .

as long as m = e(k + 1 ε ) and t = log(s/δ). Moreover, the weights coming into each node in the hidden layer are binary with t non-zeros.

For real vectors x, the non-linearity needs to implement a median. Nonetheless, an analogous result still holds.

B GAUSSIAN PROJECTIONS:

In this section we describe and analyze a simple decoding algorithm for Gaussian projections.

Theorem B.1. Let x ∈ R d , and let G be a random Gaussian matrix in R d ×d . Then for any i, there exists a linear function f i such that

E G (f i (Gx) -x i ) 2 ≤ x -x i e i Proof.

Recall that G ∈ R d ×d is a random Gaussian matrix where each entry is chosen i.i.d. from N (0, 1/d ). For any i, conditioned on G ji = g ji , we have that the random variable Y j |G ji = g ji is distributed according to the following distribution,

(Y j |G ji = g ji ) ∼ g ji x i + i =i G ji x i ∼ g ji x i + N (0, x -x i e i 2 2 /d

) . Consider a linear estimator for x i :

xi def = j α ji (y j /g ji ) j α ji ,

for some non-negative α ji 's. It is easy to verify that for any vector of α's, the expectation of xi , when taken over the random choices of G ji for i = i, is x i . Moreover, the variance of xi is

x -x i e i 2 2 d j (α ji /g ji ) 2 ( j α ji ) 2 .

Minimizing the variance of xi w.r.t α ji 's gives us α ji ∝ g 2 ji . Indeed, the partial derivatives are,

∂ j (α ji /g ji ) 2 -λ j α ji ∂α ji = 2α ji g 2 ji -λ ,

which is zero at α ji = λg 2 ji /2. This choice of α ji 's translates to

E[(x i -x i ) 2 ] = x -x i e i 2 2 d 1 j g 2 ji ,

which in expectation, now taken over the choices of g ji 's, is at most x-x i e i 2 2 /d . Thus, the claim follows.

For comparison, if x ∈ B d,k , then the expected error in estimating x i is k-1 d , so that taking d = (k -1) log 1 δ /ε 2 suffices to get a error ε estimate of any fixed bit with probablity 1-δ. Setting ε = 1 2 , we can recover x i with probability 1 -δ for x ∈ B d,k with d = 4(k -1) log 1 δ . This implies Theorem B.2. However, note that the decoding layer is now densely connected to the input layer. Moreover, for a k-sparse vectors x that are is necessarily binary, the error grows with the 2-norm of the vector x, and can be arbitrarily larger than that for the sparse sketch. Note that G x still contains sufficient information to recover x with error depending only on x -head k (x) 2 . To our knowledge, all the known decoders are adaptive algorithms, and we leave open the question of whether bounds depending on the 2-norm of the residual (x -head k (x)) are achievable by neural networks of small depth and complexity. Theorem B.2. For every w ∈ H d,s there exists a set of weights for a network N ∈ N s (Relu) such that for each

x ∈ B d,k , P r h1:t [N (Gx)) = w x] ≥ 1 -δ ,

as long as G is a random m × d Gaussian matrix, with m ≥ 4k log(s/δ).

C DETERMINISTIC SKETCHING:

First we show that if we allow large scalars in the sketches, we can construct a deterministic (2k+1)dimensional sketch from which a shallow network can reconstruct any monomial.

We will also show a lower bound of k on the required dimensionality.

For every x ∈ B d,k define a degree 2k univariate real polynomial by,

p x (z) = 1 -(k + 1) {i|xi=1} (z -i) 2 .

It is easy to verify that this construction satifies the following.

Claim C.1. Suppose that x ∈ B d,k , and let p x (•) be defined as above. If x j = 1, then p x (j) = 1. If x j = 0, then p x (j) ≤ -k.

Let the coeffients of p x (z) be a i (x) so that Proof. We have that

DecP oly d,k (DSk d,k (x), A) = j∈A 2k i=0 a x,i j i |A| = j∈A p x (j) |A| .

In words, the decoding is the average value of p x (j) over the indices j ∈ A. Now first suppose that j∈A x j = 1. Then for each j ∈ A we have x j = 1 so that by Claim C.1, p x (j) = 1. Thus the average DecP oly d,k (DSk d,k (x), A) = 1.

On the other hand, if j∈A x j = 0 then for some j ∈ A, say j * , x j * = 0. In this case, Claim C.1 implies that p x (j * ) ≤ -k. For every other j, p x (j) ≤ 1, and each p x (j) is non-negative only when x j = 1, which happens for at most k indices j. Thus the sum over non-negative p x (j) can be no larger than k. Adding p x (j * ) gives us zero, and any additional j's can only further reduce the sum. Thus the average in non-positive and hence the Relu is zero, as claimed.

The last theorem shows that B d,k can be sketched in R q , where q = 2k + 1, such that arbitrary products of variables be decoded by applying a linear function followed by a ReLU. It is natural to ask what is the smallest dimension q for which such a sketch exists. The following theorem shows that q must be at least k. In fact, this is true even if we only require to decode single variables. Theorem C.3. Let Sk : B d,k → R q be a mapping such that for every

i ∈ [d] there is w i ∈ R q satisfying x i = Relu( w i , Sk(x) ) for each x ∈ B d,k , then q is at least k.

Proof. Denote X = {w 1 , . . . , w d } and let H ⊂ {0, 1} X be the function class consisting of all functions of the form h x (w i ) = sign( w i , Sk(x) ) for x ∈ B d,k . On one hand, H is a sub-class of the class of linear separators over X ⊂ R q , hence VC(H) ≤ q. On the other hand, we claim that VC(H) ≥ k which establishes the proof. In order to prove the claim it suffices to show that the set A = {w 1 , . . . , w k } is shattered. Let B ⊂ A let x be the indicator vector of B. We claim that the restriction of h x to A is the indicator function of B. Indeed, we have that,

h x (w i ) = sign( w i , Sk(x) ) = sign(Relu( w i , Sk(x) )) = x i = 1[i ∈ B]

We would like to note that both the endcoding and the decoding of determinitic sketched can be computed efficiently, and the dimension of the sketch is smaller than the dimension of a random sketch. We get the following corollaries. For any such g, there exists a set of weights for a network N ∈ N s (Relu) such that for each

x ∈ B d,k , N (DSk h1:t (x)) = g(x).

Known lower bounds for compressed sensing Ba et al. (2010) imply that any linear sketch has size at least Ω(k log d k ) to allow stable recovery. We leave open the question of whether one can get the compactness and decoding properties of our (non-linear) sketch while ensuring stability.

D LOWER BOUND FOR PROPER LEARNING:

We now show that if one does not expand the hypothesis class, then even in the simplest of settings of linear classifiers over 1-sparse vectors, the required dimensionality of the projection is much larger than the dimension needed for improper learning. As stated earlier, the result is likely folklore and we present a proof for completeness. Theorem D.1. Suppose that there exists a distribution over maps φ : B d,1 → R q and ψ : B d,s → R q such that for any

x ∈ B d,1 , w ∈ B d,s , Pr sgn w x - 1 2 = sgn ψ(w) φ(x) ≥ 9 10 ,

where the probability is taken over sampling φ and ψ from the distribuion. Then q is Ω(s).

Proof. If the error is zero, a lower bound on q would follow from standard VC dimension arguments.

Concretely, the hypothesis class consisting of h w (x) = {e i x : w i = 1} for all w ∈ B d,s shatters the set {e 1 , . . . , e s }. If sgn(ψ(w) φ(e i )) = sgn(w x -1 2 ) for each w and e i , then the points φ(e i ), i ∈ [s] are shattered by h ψ(w) (•) where w ∈ B d,s , which is a subclass of linear separators in R q . Since linear separators in R q have VC dimension q, the largest shattered set is no larger, and thus q ≥ s.

To handle errors, we will use the Sauer-Shelah lemma and show that the set {φ(e i ) : i ∈ [s]} has many partitions. To do so, sample φ, ψ from the distribution promised above and consider the set of points A = {φ(e 1 ), φ(e 2 ), . . . , φ(e s )}. Let W = {w 1 , w 2 , . . . , w κ } be a set of κ vectors in B d,s such that, Such a collection of vectors, with κ = 2 cs for a positive constant c, can be shown to exist by a probabilistic argument or by standard constructions in coding theory. Let H = {h ψ(w) : w ∈ W } be the linear separators defined by ψ(w i ) for i ∈ W . For brevity, we denote h ψ(wj ) by h j . We will argue that H induces many different subsets of A.

Let A j = {y ∈ A : h j (x) = 1} = {x ∈ A : sgn(ψ(w j ) x) = 1}. Let E j ⊆ A be the positions where the embeddings φ, ψ fail, that is, E j = {φ(e i ) : i ∈ [s], sgn(w j e i -1 2 ) = sgn(ψ(w j ) φ(e i )}.

Thus A j = S(w j ) E j . By assumption, E[|E j |] ≤ s 10 for each j, where the expectation is taken over the choice of φ, ψ. Thus j E[|E j |] ≤ sκ/10. Renumber the h j 's in increasing order of |E j | so that |E 1 | ≤ |E 2 | ≤ . . . ≤ |E κ |. Due to the E j 's being non-empty, not all A j 's are necessarily distinct. Call a j ∈ [κ] lost if A j = A j for some j ≤ j.

By definition, A j = S(w j ) E j . If A j = A j , then the distance property implies that E j E j ≥ s 4 . Since the E j 's are increasing in size, it follows that for any lost j, |E j | ≥ s 8 . Thus in expectation at most 4κ/5 of the j's are lost. It follows that there is a choice of φ, ψ in the distribution for which H induces κ/5 distinct subsets of A. Since the VC dimension of H is at most q, the Sauer-Shelah lemma says that t≤q s t ≥ κ 5 = 2 cs 5 .

This implies that q ≥ c s for some absolute constant c .

Note that for the setting of the above example, once we scale the w j 's to be unit vectors, the margin is Θ( 1 √ s ). Standard results then imply that projecting to 1 γ 2 = Θ(s) dimension suffices, so the above bound is tight.

For this setting, Theorem 4.1 implies that a sketch of size O(log(s/δ)) suffices to correctly classify 1-δ fraction of the examples if one allows improper learning as we do.

E NEURAL NETS ON BOOLEAN INPUTS:

In this short section show that for boolean inputs (irrespective of sparsity), any polynomial with s monomials can be represented by a neural network with one hidden layer of s hidden units. Our result is a simple improvement of Barron's theorem (1993; 1994) , for the special case of sparse polynomial functions on 0-1 vectors. In contrast, Barron's theorem, which works for arbitrary inputs, would require a neural network of size d • s • p O(p) to learn an s-sparse degree-p polynomial. The proof of the improvement is elementary and provided for completeness. Then there exists a set of weights for a network N ∈ N s (Relu) such that for each x ∈ {0, 1} d , N (x) = g(x). Moreover, the weights coming into each node in the hidden layer are in {0, 1}.

Proof. The jth hidden unit implements h j = i∈Aj x i . As before, for boolean inputs, one can compute h j as Relu( i∈Aj x i -|A j | + 1). The output node computes j w j h j where h j is the output of jth hidden unit.

:

Such hash families can be easily constructed (see e.g.Mitzenmacher & Upfal (2005)), using a O(log m)bit seed. Moreover, each hash can be evaluated using O(1) arithmetic operations over O(log d)-sized words.

2 d

Figures and Tables:

x)z i . Define the deterministic sketch DSk d,k : B d,k → R 2k+1 as follows, DSk d,k (x) = (a x,0 , . . . , a x,2k ) (3) For a non-empty subset A ⊂ [d] and y ∈ R 2k+1 define DecP oly d,k (y, For every x ∈ B d,k and a non-empty set A ⊂ [d] we have j∈A x j = Relu(DecP oly d,k (DSk d,k (x), A)) .

Corollary C.4. For every w ∈ H d,s there exists a set of weights for a network N ∈ N s (Relu) such that for each x ∈ B d,k , N (DSk d,k (x)) = w x. Corollary C.5. Given w ∈ R s , and sets A 1 , . . . , A s ⊆ [d], let g : {0, 1} d → R denote the polynomial

(a) S(w i ) ⊆ [s] (b) Distance property holds: |S(w i ) S(w j )| ≥ s 4 for i = j.

Theorem E.1. Let x ∈ {0, 1} d , and let g : {0, 1} d → R denote the polynomial function g

Figure 2: Left: effect of varying t, m for sketched 1-hidden layer network. Center: sparse linear regression on sketched data with improper learning. Right: sparse polynomial regression on sketched data.

Table content: <table><tr><td>Mean squared error</td><td>0.2 0.3 0.4 0.5 0.6 0.7</td><td/><td>m=25 m=50 m=75 m=100</td><td>m=136 m=150 m=300 m=200</td><td>Mean squared error</td><td>0.25 0.10 0.15 0.20</td><td>linear N s (Relu)</td><td>Mean squared error</td><td>0.06 0.03 0.04 0.05</td><td>linear N s (Relu)</td></tr><tr><td/><td/><td/><td/><td/><td/><td>0.05</td><td/><td/><td/></tr><tr><td/><td>0.1</td><td/><td/><td/><td/><td/><td/><td/><td>0.02</td></tr><tr><td/><td>0.0</td><td colspan="3">1 2 4 6 8 10 12 14 t</td><td/><td>0.00</td><td colspan="3">1 2 4 6 8 10 12 14 no sketch t</td><td>1 2 4 6 8 10 12 14 no sketch t</td></tr><tr><td/><td/><td/><td>1K</td><td>2K</td><td/><td colspan="2">3K</td><td/><td/></tr><tr><td colspan="3">Gaussian</td><td colspan="5">0.089 0.057 0.029</td><td/><td/></tr><tr><td colspan="8">Sketch t = 1 0.087 0.049 0.031</td><td/><td/></tr><tr><td colspan="8">Sketch t = 2 0.072 0.041 0.023</td><td/><td/></tr><tr><td colspan="8">Sketch t = 6 0.041 0.033 0.022</td><td/><td/></tr><tr><td colspan="3">Gaussian</td><td colspan="5">0.043 0.037 0.034</td><td/><td/></tr><tr><td colspan="8">Sketch t = 1 0.041 0.036 0.033</td><td/><td/></tr><tr><td colspan="8">Sketch t = 2 0.036 0.027 0.024</td><td/><td/></tr><tr><td colspan="8">Sketch t = 6 0.032 0.022 0.018</td><td/><td/></tr></table>

Performance vs. number of nonzero parameters in 1st layer for Reuters (left), AG News (center), and type tagging (right). Each color corresponds to a different sketch size and markers indicate the number of subsketches t. We evaluate each setting for three values of the l 1 regularization parameter λ 1 .Entity Type Tagging. Entity type tagging is the task of assigning one or more labels (such as person, location, organization, event) to mentions of entities in text. We perform type tagging on a corpus of new documents containing 110K mentions annotated with 88 labels (on average, 1.7 labels per mention). Features for each mention include surrounding words, syntactic and lexical patterns, leading to a very large dictionary. Similarly to previous work, we map each string feature to a 32 bit integer, and then further reduce dimensionality using hashing or sketches. SeeGillick et al. (2014) for more details on features and labels for this task.

Table content: <table><tr><td/><td/><td/><td/><td>0.75</td><td/><td/><td/><td/></tr><tr><td/><td>0.92</td><td/><td/><td/><td/><td/><td>0.75</td><td/></tr><tr><td>F1 score</td><td>0.88 0.90</td><td>mt =1K</td><td>Accuracy</td><td>0.70 0.65</td><td>mt =1K</td><td>F1 score</td><td>0.70 0.65</td><td>mt =1K</td></tr><tr><td/><td>0.86</td><td>mt =2K mt =5K mt =10K original</td><td/><td>0.60</td><td>mt =2K mt =5K mt =10K original</td><td/><td>0.60</td><td>mt =2K mt =5K mt =10K hash 500K</td></tr><tr><td/><td>10 4 0.84</td><td>10 5 Non-zero parameters in 1st layer 10 6</td><td/><td/><td>10 5 Non-zero parameters in 1st layer 10 6</td><td>10 7</td><td/><td>10 5 Non-zero parameters in 1st layer 10 6</td></tr><tr><td colspan="3">Figure 3:</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2017):
Summary: This paper presents a novel sketching method in solving sparse polynomial function of a sparse binary vector within a single-layer neural network. Pros:1. The paper is written clearly. 2. I like the idea of using improper learning to reduce the dimensionality. 3. It*s novel to use neural network to do sketching decoding. Cons:1. The experiments part is kind of weak in comparison with other sketching/projection methods. 2. Any theoretical analysis to show why this approach needs fewer paramerters than feature hash, etc. My other concern is that since t and m are tunable, how to set these parameter for different problems? 3. The authors claim they have faster training. However it*s not shown in experiments. Comments: It may be interesting to compare with sparse feed-forward neural networks.