Recursive Sketches for Modular Deep Learning

  • 2019-05-29 21:10:58
  • Badih Ghazi, Rina Panigrahy, Joshua R. Wang
  • 38

Abstract

We present a mechanism to compute a sketch (succinct summary) of how acomplex modular deep network processes its inputs. The sketch summarizesessential information about the inputs and outputs of the network and can beused to quickly identify key components and summary statistics of the inputs.Furthermore, the sketch is recursive and can be unrolled to identifysub-components of these components and so forth, capturing a potentiallycomplicated DAG structure. These sketches erase gracefully; even if we erase afraction of the sketch at random, the remainder still retains the `high-weight'information present in the original sketch. The sketches can also be organizedin a repository to implicitly form a `knowledge graph'; it is possible toquickly retrieve sketches in the repository that are related to a sketch ofinterest; arranged in this fashion, the sketches can also be used to learnemerging concepts by looking for new clusters in sketch space. Finally, in thescenario where we want to learn a ground truth deep network, we show thataugmenting input/output pairs with these sketches can theoretically make iteasier to do so.

 

Quick Read (beta)

Recursive Sketches for Modular Deep Learning

Badih Ghazi    Rina Panigrahy    Joshua R. Wang
Abstract

We present a mechanism to compute a sketch (succinct summary) of how a complex modular deep network processes its inputs. The sketch summarizes essential information about the inputs and outputs of the network and can be used to quickly identify key components and summary statistics of the inputs. Furthermore, the sketch is recursive and can be unrolled to identify sub-components of these components and so forth, capturing a potentially complicated DAG structure. These sketches erase gracefully; even if we erase a fraction of the sketch at random, the remainder still retains the “high-weight” information present in the original sketch. The sketches can also be organized in a repository to implicitly form a “knowledge graph”; it is possible to quickly retrieve sketches in the repository that are related to a sketch of interest; arranged in this fashion, the sketches can also be used to learn emerging concepts by looking for new clusters in sketch space. Finally, in the scenario where we want to learn a ground truth deep network, we show that augmenting input/output pairs with these sketches can theoretically make it easier to do so.

Sketching, Modular Network
\usetikzlibrary

calc \usetikzlibrarypositioning \usetikzlibraryshapes.geometric


1 Introduction

Machine learning has leveraged our understanding of how the brain functions to devise better algorithms. Much of classical machine learning focuses on how to correctly compute a function; we utilize the available data to make more accurate predictions. More recently, lines of work have considered other important objectives as well: we might like our algorithms to be small, efficient, and robust. This work aims to further explore one such sub-question: can we design a system on top of neural nets that efficiently stores information?

Our motivating example is the following everyday situation. Imagine stepping into a room and briefly viewing the objects within. Modern machine learning is excellent at answering immediate questions about this scene: “Is there a cat? How big is said cat?” Now, suppose we view this room every day over the course of a year. Humans can reminisce about the times they saw the room: “How often did the room contain a cat? Was it usually morning or night when we saw the room?”; can we design systems that are also capable of efficiently answering such memory-based questions?

Our proposed solution works by leveraging an existing (already trained) machine learning model to understand individual inputs. For the sake of clarity of presentation, this base machine learning model will be a modular deep network.11 1 Of course, it is possible to cast many models as deep modular networks by appropriately separating them into modules. We then augment this model with sketches of its computation. We show how these sketches can be used to efficiently answer memory-based questions, despite the fact that they take up much less memory than storing the entire original computation.

A modular deep network consists of several independent neural networks (modules) which only communicate via one’s output serving as another’s input. Figure 1 presents a cartoon depiction of a modular network for our example. Modular networks have both a biological basis (Azam, 2000) and evolutionary justification (Clune et al., 2013). They have inspired several practical architectures such as neural module networks (Andreas et al., 2016; Hu et al., 2017), capsule neural networks (Hinton et al., 2000, 2011; Sabour et al., 2017), and PathNet (Fernando et al., 2017) and have connections to suggested biological models of intelligence such as hierarchical temporal memory (Hawkins & Blakeslee, 2007). We choose them as a useful abstraction to avoid discussing specific network architectures.

Figure 1: Cartoon depiction of a modular network processing an image of a room. Modules are drawn as rectangles and their inputs/outputs (which we refer to as object attributes) are drawn as ovals. The arrows run from input vector to module and module to output vector. There may be additional layers between low level and high level modules, indicated by the dashed arrows. The output module here is a dummy module which groups together top-level objects.

What do these modules represent in the context of our room task? Since we are searching for objects in the room, we think of each module as attempting to identify a particular type of object, from the low level edge to the high level cat. For the reader familiar with convolutional neural networks, it may help to think of each module as a filter or kernel. We denote the event where a module produces output as an object, the produced output vector as an attribute vector, and all objects produced by a module as a class. In fact, our sketching mechanism will detail how to sketch each object, and these sketches will be recursive, taking into account the sketches corresponding to the inputs of the module.

Armed with this view of modular networks for image processing, we now entertain some possible sketch properties. One basic use case is that from the output sketch, we should be able to say something about the attribute vectors of the objects that went into it. This encompasses a question like “How big was the cat?” Note that we need to assume that our base network is capable of answering such questions, and the primary difficulty stems from our desire to maintain this capability despite only keeping a small sketch. Obviously, we should not be able to answer such questions as precisely as we could with the original input. Hence a reasonable attribute recovery goal is to be able to approximately recover an object’s attribute vector from its sketch. Concretely, we should be able to recover cat attributes from our cat sketch.

Since we plan to make our sketches recursive, we would actually like to recover the cat attributes from the final output sketch. Can we recover the cat’s sketch from final sketch? Again, we have the same tug-of-war with space and should expect some loss from incorporating information from many sketches into one. Our recursive sketch property is that we can recover (a functional approximation of) a sketch from a later sketch which incorporated it.

Zooming out to the entire scene, one fundamental question is “Have I been in this room before?” In other words, comparing sketches should give some information about how similar the modules and inputs that generated them. In the language of sketches, our desired sketch-to-sketch similarity property is that two completely unrelated sketches will be dissimilar while two sketches that share common modules and similar objects will be similar.

Humans also have the impressive ability to recall approximate counting information pertaining to previous encounters (Brannon & Roitman, 2003). The summary statistics property states that from a sketch, we can approximately recover the number of objects produced by a particular module, as well as their mean attributes.

Finally, we would like the nuance of being able to forget information gradually, remembering more important facts for longer. The graceful erasure property expresses this idea: if (a known) portion of our sketch is erased, then the previous properties continue to hold, but with additional noise depending on the amount erased.

We present a sketching mechanism which simultaneously satisfies all these desiderata: attribute recovery, recursive sketch, sketch-to-sketch similarity, summary statistics, and graceful erasure.

1.1 Potential Applications

We justify our proposed properties by describing several potential applications for a sketching mechanism satisfying them.

Sketch Repository. The most obvious use case suggested by our motivating example is to maintain a repository of sketches produced by the (augmented) network. By the recursive sketch and attribute recovery properties, we can query our repository for sketches with objects similar to a particular object. From the sketch-to-sketch similarity property, we can think of the sketches as forming a knowledge graph; we could cluster them to look for patterns in the data or use locality-sensitive hashing to quickly fish out related sketches. We can combine these overall sketches once more and use the summary statistics property to get rough statistics of how common certain types of objects are, or what a typical object of a class looks like. Our repository may follow a generalization of a “least recently used” policy, taken advantage of the graceful erasure property to only partially forget old sketches.

Since our sketches are recursively defined, such a repository is not limited to only keeping overall sketches of inputs; we can also store lower-level object sketches. When we perform object attribute recovery using the attribute recovery property, we can treat the result as a fingerprint to search for a more accurate sketch of that object in our repository.

Learning New Modules. This is an extension of the sketch repository application above. Rather than assuming we start with a pre-trained modular network, we start with a bare-bones modular network and want to grow it. We feed it inputs and examine the resulting sketches for emerging clusters. When we find such a cluster, we use its points to train a corresponding (reversible) module. In fact, this clustering may be done in a hierarchical fashion to get finer classes. For example, we may develop a module corresponding to “cat” based on a coarse cluster of sketches which involve cats. We may get sub-clusters based on cat species or even finer sub-clusters based on individual cats repeatedly appearing.

The modules produced by this procedure can capture important primitives. For example, the summary statistics property implies that a single-layer module could count the number of objects produced by another module. If the modules available are complex enough to capture curves, then this process could potentially allow us to identify different types of motion.

Interpretability. Since our sketches store information regarding how the network processed an input, they can help explain how that network came to its final decision. The sketch-to-sketch similarity property tells us when the network thinks two rooms are similar, but what exactly did the network find similar? Using the recursive sketch property, we can drill down into two top level sketches, looking for the pairs of objects that the network found similar.

Model Distillation. Model distillation (Buciluǎ et al., 2006; Hinton et al., 2015) is a popular technique for improving machine learning models. The use case of model distillation is as follows. Imagine that we train a model on the original data set, but it is unsatisfactory in some regard (e.g. too large or ensemble). In model distillation, we take this first model and use its features to train a second model. These stepping stones allows the second model to be smaller and less complex. The textbook example of feature choice is to use class probabilities (e.g. the object is 90% A and 10% B) versus the exact class found in the original input (e.g. the object is of class A). We can think of this as an intermediate option between the two extremes of (i) providing just the original data set again and (ii) providing all activations in the first model. Our sketches are an alternative option. To showcase the utility of our sketches in the context of learning from a teacher network, we prove that (under certain assumptions) augmenting the teacher network with our sketches allows us to learn the network. Note that in general, it is not known how the student can learn solely from many input/output pairs.

1.2 Techniques

The building block of our sketching mechanism is applying a random matrix to a vector. We apply such transformations to object attribute vectors to produce sketches, and then recursively to merge sketches. Consequently, most of our analysis revolves around proving and utilizing properties of random matrices. In the case where we know the matrices used in the sketch, then we can use an approximate version of isometry to argue about how noise propagates through our sketches. On the other hand, if we do not know the matrices involved, then we use sparse recovery/dictionary learning techniques to recover them. Our recovery procedure is at partially inspired by several works on sparse coding and dictionary learning (Spielman et al., 2012; Arora et al., 2014c), (Arora et al., 2014a) and (Arora et al., 2015) as well as their known theoretical connections to neural networks (Arora et al., 2014b; Papyan et al., 2018). We have more requirements on our procedure than previous literature, so we custom-design a distribution of block-random matrices reminiscent of the sparse Johnson-Lindenstrauss transform. Proving procedure correctness is done via probabilistic inequalities and analysis tools, including the Khintchine inequality and the Hanson-Wright inequality.

One could consider an alternate approach based on the serialization of structured data (for example, protocol buffers). Compared to this approach, ours provides more fine-grained control over the accuracy versus space trade-off and aligns more closely with machine learning models (it operates on real vectors).

1.3 Related Work

There have been several previous attempts at adding a notion of memory to neural networks. There is a line of work which considers augmenting recurrent neural networks with external memories (Graves et al., 2014; Sukhbaatar et al., 2015; Joulin & Mikolov, 2015; Grefenstette et al., 2015; Zaremba & Sutskever, 2015; Danihelka et al., 2016; Graves et al., 2016). In this line of work, the onus is on the neural network to learn how to write information to and read information from the memory. In contrast to this line of work, our approach does not attempt to use machine learning to manage memory, but rather demonstrates that proper use of random matrices suffices. Our results can hence be taken as theoretical evidence that this learning task is relatively easy.

Vector Symbolic Architectures (VSAs) (Smolensky, 1990; Gayler, 2004; Levy & Gayler, 2008) are a class of memory models which use vectors to represent both objects and the relationships between them. There is some conceptual overlap between our sketching mechanism and VSAs. For example, in Gayler’s MAP (Multiply, Add, Permute) scheme (Gayler, 2004), vector addition is used to represent superposition and permutation is used to encode quotations. This is comparable to how we recursively encode objects; we use addition to combine multiple input objects after applying random matrices to them. One key difference in our model is that the object attribute vectors we want to recover are provided by some pre-trained model and we make no assumptions on their distribution. In particular, their possible correlation makes it necessary to first apply a random transformation before combining them. In problems where data is generated by simple programs, several papers (Wu et al., 2017; Yi et al., 2018; Ellis et al., 2018; Andreas et al., 2016; Oh et al., 2017) attempt to infer programs from the generated training data possibly in a modular fashion.

Our result on the learnability of a ground truth network is related to the recent line of work on learning small-depth neural networks (Du et al., 2017b, a; Li & Yuan, 2017; Zhong et al., 2017a; Zhang et al., 2017; Zhong et al., 2017b). Recent research on neural networks has considered evolving neural network architectures for image classification (e.g., (Real et al., 2018)), which is conceptually related to our suggested Learning New Models application.

1.4 Organization

We review some basic definitions and assumptions in Section 2. An overview of our final sketching mechanism is given in Section 3 (Theorems 1, 2, 3). Section 4 gives a sequence of sketch prototypes leading up to our final sketching mechanism. In Section 5, we explain how to deduce the random parameters of our sketching mechanism from multiple sketches via dictionary learning. Further discussion and detailed proofs are provided in the appendices.

2 Preliminaries

In this section, we cover some preliminaries that we use throughout the remainder of the paper. Throughout the paper, we denote by [n] the set {1,,n}. We condense large matrix products with the following notation.

i=1nRi R1R2Rn
i=1nRi RnR2R1

2.1 Modular Deep Networks for Object Detection

For this paper, a modular deep network consists of a collection of modules {M}. Each module is responsible for detecting a particular class of object, e.g. a cat module may detect cats. These modules use the outputs of other modules, e.g. the cat module may look at outputs of the edge detection module rather than raw input pixels. When the network processes a single input, we can depict which objects feed into which other objects as a (weighted) communication graph. This graph may be data-dependent. For example, in the original Neural Module Networks of Andreas et al. (Andreas et al., 2016), the communication graph is derived by taking questions, feeding them through a parser, and then converting parse trees into structured queries. Note that this pipeline is disjoint from the modular network itself, which operates on images. In this paper, we will not make assumptions about or try to learn the process producing these communication graphs. When a module does appear in the communication graph, we say that it detected an object θ and refer to its output as xθ, the attribute vector of object θ. We assume that these attribute vectors xθ are nonnegative and normalized. As a consequence of this view of modular networks, a communication graph may have far more objects than modules. We let our input size parameter N denote twice the maximum between the number of modules and the number of objects in any communication graph.

We assume we have access to this communication graph, and we use θ1,,θk to denote the k input objects to object θ. We assume we have a notion of how important each input object was; for each input θi, there is a nonnegative weight wi such that i=1kwi=1. It is possible naively choose wi=1/k, with the understanding that weights play a role in the guarantees of our sketching mechanism (it does a better job of storing information about high-weight inputs).

We handle the network-level input and output as follows. The input data can be used by modules, but it itself is not produced by a module and has no associated sketch. We assume the network has a special output module, which appears exactly once in the communication graph as its sink. It produces the output (pseudo-)object, which has associated sketches like other objects but does not count as an object when discussing sketching properties (e.g. two sketches are not similar just because they must have output pseudo-objects). This output module and pseudo-object only matter for our overall sketch insofar as they group together high-level objects.

2.2 Additional Notation for Sketching

We will (recursively) define a sketch for every object, but we consider our sketch for the output object of the network to be the overall sketch. This is the sketch that we want to capture how the network processed a particular input. One consequence is that if an object does not have a path to the output module in the communication graph, it will be omitted from the overall sketch.

Our theoretical results will primarily focus on a single path from an object θ to the output object. We define the “effective weight” of an object, denoted wθ, to be the product of weights along this path. For example, if an edge was 10% responsible for a cat and the cat was 50% of the output, then this edge has an effective weight of 5% (for this path through the cat object). We define the “depth” of an object, denoted 0pt, to be the number of objects along this path. In the preceding example, the output object has a depth of one, the cat object has a depth of two, and the edge object has a depth of three. We make the technical assumption that all objects produced by a module must be at the same depth. As a consequence, modules M also have a depth, denoted 0pt[M]. To continue the example, the output module has depth one, the cat module has depth two, and the edge module has depth three. Furthermore, this implies that each object and module can be assigned a unique depth (i.e. all paths from any object produced by a module to the output object have the same number of objects).

Our recursive object sketches are all dsketch dimensional vectors. We assume that dsketch is at least the size of any object attribute vector (i.e. the output of any module). In general, all of our vectors are dsketch-dimensional; we assume that shorter object attribute vectors are zero-padded (and normalized). For example, imagine that the cat object θ is output with the three-dimensional attribute vector (0.6,0.0,0.8), but dsketch is five. Then we consider its attribute vector to be xθ=(0.6,0.0,0.8,0.0,0.0).

Symbol Meaning
b a bit in {±1}
d dimension size
𝒟 distribution over random matrices
f a coin flip in {±1}
h depth (one-indexed)
H 3maximum depth
I identity matrix
k #inputs
-th moment of a random variable
M module
N 3max(#modules,#objects)
q block non-zero probability
R random matrix
s sketch
S #samples
w importance weight
x attribute vector / unknown dictionary learning vector
y dictionary learning sample vector
z dictionary learning noise
δ error bound, isometry and desynchronization
ϵ error bound, dictionary learning
θ object
Table 1: Symbols used in this paper.

3 Overview of Sketching Mechanism

In this section, we present our sketching mechanism, which attempts to summarize how a modular deep network understood an input. The mechanism is presented at a high level; see Section 4 for how we arrived at this mechanism and Appendix D for proofs of the results stated in this section.

3.1 Desiderata

As discussed in the introduction, we want our sketching mechanism to satisfy several properties, listed below.

Attribute Recovery. Object attribute vectors can be approximately recovered from the overall sketch, with additive error that decreases with the effective weight of the object.

Sketch-to-Sketch Similarity. With high probability, two completely unrelated sketches (involving disjoint sets of modules) will have a small inner product. With high probability, two sketches that share common modules and similar objects will have a large inner product (increasing with the effective weights of the objects).

Summary Statistics. If a single module detects several objects, then we can approximately recover summary statistics about them, such as the number of such objects or their mean attribute vector, with additive error that decreases with the effective weight of the objects.

Graceful Erasure. Erasing everything but dsketch-prefix of the overall sketch yields an overall sketch with the same properties (albeit with larger error).

3.2 Random Matrices

The workhorse of our recursive sketching mechanism is random (square) matrices. We apply these to transform input sketches before incorporating them into the sketch of the current object. We will defer the exact specification of how to generate our random matrices to Section 5, but while reading this section it may be convenient for the reader to think of our random matrices as uniform random orthonormal matrices. Our actual distribution choice is similar with respect to the properties needed for the results in this section. One notable parameter for our family of random matrices is δ0, which expresses how well they allow us to estimate particular quantities with high probability. For both our random matrices and uniform random orthonormal matrices, δ is O~(1/dsketch). We prove various results about the properties of our random matrices in Appendix B.

We will use R with a subscript to denote such a random matrix. Each subscript indicates a fresh draw of a matrix from our distribution, so every R1 is always equal to every other R1 but R1 and Rcat,0 are independent. Throughout this section, we will assume that we have access to these matrices when we are operating on a sketch to retrieve information. In Section 5, we show how to recover these matrices given enough samples.

3.3 The Sketching Mechanism

Figure 2: Illustration of how to compute the sketch for a cat object from Figure 1. Attribute vectors (and e1) are drawn as ovals; note how they have been normalized and padded to dsketch=5 dimensions. Sketches are drawn as rectangles with a cut corner. The arrows run from vectors used to compute other vectors, and are labeled with the matrix that is applied in the process. For the purposes of this diagram, all random matrices happen to be the identity matrix.

The basic building block of our sketching mechanism is the tuple sketch, which we denote stuple. As the name might suggest, its purpose is to combine k sketches s1,,sk with respective weights w1,,wk0 into a single sketch (for proofs, we will assume that these weights sum to at most one). In the case where the k sketches are input sketches, these weights will be the importance weights from our network. Otherwise, they will all be 1/k. Naturally, sketches with higher weight can be recovered more precisely. The tuple sketch is formally defined as follows. If their values are obvious from context, we will omit w1,,wk from the arguments to the tuple sketch. The tuple sketch is computed as follows.22 2 Rather than taking a convex combination of (I+Ri2)si, one might instead sample a few of them. Doing so would have repercussions on the results in this section, swapping many bounds from high probability to conditioning on their objects getting through. However, it also makes it easier to do the dictionary learning in Section 5.

stuple(s1,,sk,w1,,wk)i=1kwi(I+Ri2)si

Note that I is the identity matrix, and we will define a tuple sketch of zero things to be the zero vector.

Each object θ is represented by a sketch, which naturally we will refer to as an object sketch. We denote such a sketch as sobject. We want the sketch of object θ to incorporate information about the attributes of θ itself as well as information about the inputs that produced it. Hence we also define two subsketches for object θ. The attribute subsketch, denoted sattr, is a sketch representation of object θ’s attributes. The input subsketch, denoted sinput, is a sketch representation of the inputs that produced object θ. These three sketches are computed as follows.

sobject(θ) (I+RM(θ),02)stuple(sattr(θ),sinput(θ),12,12)
sattr(θ) 12RM(θ),1xθ+12RM(θ),2e1
sinput(θ) stuple(sobject(θ1),,sobject(θk),w1,,wk)

Note that e1 in the attribute subsketch is the first standard basis vector; we will use it for frequency estimation as part of our Summary Statistics property. Additionally, θ1,,θk in the input sketch are the input objects for θ and w1,,wk are their importance weights from the network.

The overall sketch is just the output psuedo-object’s input subsketch. It is worth noting that we do not choose to use its object sketch.

soverallsinput(output pseudo-object)

We want to use this to (noisily) retrieve the information that originally went into these sketches. We are now ready to present our results for this sketching mechanism. Note that we provide the technical machinery for proofs of the following results in Appendix A and we provide the proofs themselves in Appendix D. Our techniques involve using an approximate version of isometry and reasoning about the repeated application of matrices which satisfy our approximate isometry.

Our first result concerns Attribute Recovery (example use case: roughly describe the cat that was in this room).

Theorem 1.

[Simplification of Theorem 9] Our sketch has the simplified Attribute Recovery property, which is as follows. Consider an object θ at constant depth h(θ) with effective weight wθ.

  1. (i)

    Suppose no other objects in the overall sketch are also produced by M(θ). We can produce a vector estimate of the attribute vector xθ, which with high probability has at most O(δ/wθ) -error.

  2. (ii)

    Suppose we know the sequence of input indices to get to θ in the sketch. Then even if other objects in the overall sketch are produced by M(θ), we can still produce a vector estimate of the attribute vector xθ, which with high probability has at most O(δ/wθ) -error.

As a reminder, error is just the maximum error over all coordinates. Also, note that if we are trying to recover a quantized attribute vector, then we may be able to recover our attribute vector exactly when the quantization is larger than our additive error. This next result concerns Sketch-to-Sketch Similarity (example use case: judge how similar two rooms are). We would like to stress that the output psuedo-object does not count as an object for the purposes of (i) or (ii) in the next result.

Theorem 2.

[Simplification of Theorem 10] Our sketch has the Sketch-to-Sketch Similarity property, which is as follows. Suppose we have two overall sketches s and s¯.

  1. (i)

    If the two sketches share no modules, then with high probability they have at most O(δ) dot-product.

  2. (ii)

    If s has an object θ of weight wθ and s¯ has an object θ¯ of weight w¯θ, both objects are produced by the same module, and both objects are at constant depth h(θ) then with high probability they have at least Ω(wθw¯θ¯)-O(δ) dot-product.

  3. (iii)

    If the two sketches are identical except that the attributes of any object θ differ by at most ϵ in 2 distance, then with probability one the two sketches are at most ϵ/2 from each other in 2 distance.

Although our Sketch-to-Sketch Similarity result is framed in terms of two overall sketches, the recursive nature of our sketches makes it not too hard to see how it also applies to any pair of sketches computed along the way. This is depicted in Figure 3.

Figure 3: A two-dimensional cartoon depiction of the Sketch-to-Sketch Similarity property with respect to the various sketches we produce from a single input. Each vector represents a sketch, and related sketches are more likely to cluster together.

This next result concerns Summary Statistics (example use case: how many walls are in this room).

Theorem 3.

[Simplification of Theorem 11] Our sketch has the simplified Summary Statistics property, which is as follows. Consider a module M which lies at constant depth h(M), and suppose all the objects produced by M has the same effective weight w.

  1. (i)

    Frequency Recovery. We can produce an estimate of the number of objects produced by M. With high probability, our estimate has an additive error of at most O(δ/w).

  2. (ii)

    Summed Attribute Recovery. We can produce a vector estimate of the summed attribute vectors of the objects produced by M. With high probability, our estimate has at most O(δ/w) -error.

Again, note that quantization may allow for exact recovery. In this case, the number of objects is an integer and hence can be recovered exactly when the additive error is less than 1/2. If we can recover the exact number of objects, we can also estimate the mean attribute vector.

Appendix Subsection D.4 explains how to generalize our sketch to incorporate signatures for the Object Signature Recovery property and Appendix Subsection D.5 explains how to generalize these results to hold when part of the sketch is erased for the Graceful Erasure property.

4 The Road to a Sketch

In this section, we present a series of sketch prototypes which gradually grow more complex, capturing more of our desiderata while also considering more complex network possibilities. The final prototype is our actual sketch.

We begin by making the following simplifying assumptions: (i) each object is produced by a unique module, (ii) our network is of depth one (i.e. all objects are direct inputs to the output pseudo-object), and (iii) we can generate random orthonormal matrices R to use in our sketches. In this section, we eventually relax all three assumptions to arrive at our final sketch, which was presented in Section 3. Orthonormal matrices are convenient for us due to the following two properties.

Isometry: If x is a unit vector and R is an orthonormal matrix, then |||Rx||22-||x||22|=0. One nice consequence of this fact is that RT is the inverse of R.

Desynchronization: If x and y are unit vectors and then R is drawn to be a random orthonormal matrix, then |Rx,y|O(logN/dsketch) with probability at least 1-1/NΩ(1) (i.e. with high probability).

When we later use block sparse random matrices, these properties are noisier and we need to carefully control the magnitude of the resulting noise. Roughly speaking, the absolute values in both definitions will be bounded by a parameter δ (the same δ as in Section 3). In Appendix A, we establish the technical machinery to control this noise.

Proof Ideas. Appendix C contains proof sketches of the claims in this section. At an even higher level, the key idea is as follows. Our sketch properties revolve around taking products of our sketches and random matrices. These products are made up of terms which in turn contain matrix products of the form R2TR1. If these two random matrices are the same, then this is the identity matrix by Isometry. If they are independent, then this is a uniform random orthonormal matrix and by desynchronization everything involved in the product will turn into bounded noise. The sharp distinction between these two cases means that Rx encodes the information of x in a way that only applying RT will retrieve.

Prototype A: A Basic Sketch. Here is our first attempt at a sketch, which we will refer to as prototype A. We use A superscripts to distinguish the definitions for this prototype. The fundamental building block of all our sketches is the tuple sketch, which combines k (weighted) sketches into a single sketch. Its input is k sketches s1,,sk along with their nonnegative weights w1,,wk0 which sum to one. For now, we just take the convex combination of the sketches:

stupleA(s1,,sk,w1,,wk)i=1kwisi

Next, we describe how to produce the sketch of an object θ. Due to assumption (ii), we don’t need to incorporate the sketches of input objects. We only need to take into account the object attribute vector. We will keep a random matrix RM for every module M and apply it when computing object sketches:

sobjectA(θ)RM(θ)xθ

Finally, we will specially handle the sketch of our top level object so that it can incorporate its direct inputs (we will not bother with its attributes for now):

soverallAstupleA(sobjectA(θ1),,sobjectA(θk))

where θ1,,θk are the direct inputs to the output pseudo-object and w1,,wk are their importance weights from the network.

Our first result is that if we have the overall sketch soverallA, we can (approximately) recover the attribute vector for object θ by computing RM(θ)TsoverallA.

Claim 1.

Prototype A has the Attribute Recovery property: for any object θ, with high probability (over the random matrices), its attribute vector xθ can be recovered up to at most O(logN/(wθd𝑠𝑘𝑒𝑡𝑐ℎ)) -error.

Our next result is that overall sketches which have similar direct input objects will be similar:

Claim 2.

Prototype A has the Sketch-to-Sketch Similarity property: (i) if two sketches share no modules, then with high probability they have at most O(logN/d𝑠𝑘𝑒𝑡𝑐ℎ) dot-product, (ii) if two sketches share an object θ, which has wθ in the one sketch and w¯θ in the other, then with high probability they have at least wθw¯θ-O(logN/d𝑠𝑘𝑒𝑡𝑐ℎ) dot-product, (iii) if two sketches have objects produced by identical modules and each pair of objects produced by the same module differ by at most ϵ in 2 distance and are given equal weights, then they are guaranteed to be at most ϵ from each other in 2 distance.

Prototype B: Handling Module Multiplicity. We will now relax assumption (i); a single module may appear multiple times in the communication graph, producing multiple objects. This assumption previously prevented the Summary Statistics property from making sense, but it is now up for grabs. Observe that with this assumption removed, computing RMTsoverallA now sums the attribute vectors of all objects produced by module M. As a consequence, we will now need a more nuanced version of our Attribute Recovery property, but we can leverage this fact for the Summary Statistics property. In order to estimate object frequencies, we will (in spirit) augment our object attribute vectors with a entry which is always one. In reality, we draw another random matrix for the module and use its first column.

sobjectB(θ)12RM(θ),1xθ+12RM(θ),2e1

where e1 is the first standard basis vector in dsketch dimensions.

We still need to fix attribute recovery; how can we recover the attributes of an object that shares a module with another object? We could apply another random matrix to every input in a tuple sketch, but then we would not be able to get summed statistics. The solution is to both apply another random matrix and apply the identity mapping. We will informally refer to (I+R2) as the transparent version of matrix R. The point is that when applied to a vector x, it both lets through information about x and sets things up so that RT will be able to retrieve the same information about x. Our new tuple sketch is:

stupleB(s1,,sk,w1,,wk)i=1kwi(I+Ri2)si

Our special overall sketch is computed as before.

soverallBstupleB(sobjectB(θ1),,sobjectB(θk))

Here is our more nuanced attribute recovery claim.

Claim 3.

Prototype B has the Attribute Recovery property, which is as follows. Consider an object θ with weight wθ. Then (i) if no other objects are produced by the same module in the sketch, with high probability we can recover wθ up to O(logNwθd𝑠𝑘𝑒𝑡𝑐ℎ) -error and (ii) even if other objects are output by the same module, if we know θ’s index in the overall sketch, with high probability we can recover wθ up to O(logNwθd𝑠𝑘𝑒𝑡𝑐ℎ) -error.

Sketches are still similar, and due to the e1 we inserted into the object sketch, two objects produced by the same module now always have a base amount of similarity.

Claim 4.

Prototype B has the Sketch-to-Sketch Similarity property, just as in Claim 2, except in case (ii) the dot-product is at least 14wθw¯θ-O(logN/d𝑠𝑘𝑒𝑡𝑐ℎ), in case (iii) the sketches are at most ϵ/2 from each other in 2 distance, and we have an additional case (iv) if one sketch has an object θ of weight wθ and the other sketch has an object θ¯ of weight w¯θ¯ and both objects are produced by the same module, then with high probability they have at least 116wθw¯θ-O(logN/d𝑠𝑘𝑒𝑡𝑐ℎ).

Finally, we can recover some summary statistics.

Claim 5.

Prototype B has the Summary Statistics property, which is as follows. Consider a module M, and suppose all objects produced by M have the same weight in the overall sketch. Then (i) we can estimate the number of objects produced by M up to an additive O(logNwd𝑠𝑘𝑒𝑡𝑐ℎ) and (ii) we can estimate the summed attribute vector of objects produced by M up to O(logNwd𝑠𝑘𝑒𝑡𝑐ℎ) -error.

Last Steps: Handling Deep Networks. We conclude by describing how to get from prototype B to the sketch we presented in Section 3. We have two assumptions left to relax: (ii) and (iii). We gloss over how to relax assumption (iii) here, since the push back comes from the requirements of dictionary learning in Section 5, and the exact choice of random matrices is not so illuminating for this set of results. Instead, we focus on how to relax assumption (ii) and make our sketches recursive. As a first point, we’ll be keeping the tuple sketch from prototype B:

stuple(s1,,sk,w1,,wk)i=1kwi(I+Ri2)si(=stupleB(s1,,sk,w1,,wk))

The main difference is that we now want object sketches to additionally capture information about their input objects. We define two important subsketches for each object, one to capture its attributes and one to capture its inputs. The attribute subsketch of an object what was the object sketch in prototype B:

sattr(θ)12RM(θ),1xθ+12RM(θ),2e1(=sobjectB(θ))

The input subsketch is just a tuple sketch:

sinput(θ)stuple(sobject(θ1),,sobject(θk),w1,,wk)

The object sketch just tuple sketches together the two subsketches and applies a transparent matrix. The idea is that we might both want to query over the input object’s module, or both the current object’s module and the input object’s module (e.g. summary statistics about all edges versus just edges that wound up in a cat). The transparent matrix means the information gets encoded both ways.

sobject(θ)(I+RM(θ),02)stuple(sattr(θ),sinput(θ),12,12)

One nice consequence of all this is that we can now stop special-casing the overall sketch, since we have defined the notion of input subsketches. Note that we do not want the overall sketch to be the output pseudo-object’s object sketch, because that would incorporate a Routput,2e1, which in turn gives all sketches a base amount of dot-product similarity that breaks the current Sketch-to-Sketch Similarity property.

soverallsinput(output pseudo-object)

5 Learning Modular Deep Networks via Dictionary Learning

In this section, we demonstrate that our sketches carry enough information to learn the network used to produce them. Specifically, we develop a method for training a new network based on (input, output, sketch) triples obtained from a teacher modular deep network. Our method is powered by a novel dictionary learning procedure. Loosely speaking, dictionary learning tries to solve the following problem. There is an unknown dictionary matrix R, whose columns are typically referred to as atoms. There is also a sequence of unknown sparse vectors x(k); we only observe how they combine the atoms, i.e., {y(k)=Rx(k)}. We want to use these observations y(k) to recover the dictionary matrix R and the original sparse vectors x(k).

While dictionary learning has been well-studied in the literature from both an applied and a theoretical standpoint, our setup differs from known theoretical results in several key aspects. The main complication is that since we want to apply our dictionary learning procedure recursively, our error in recovering the unknown vectors x(k) will become noise on the observations y(k) in the very next step. Note that classical dictionary learning can only recover the unknown vectors x(k) up to permutation and coordinate-wise sign. To do better, we will carefully engineer our distribution of dictionary matrices R to allow us to infer the permutation (between the columns of a matrix) and signs, which is needed to recurse. Additionally, we want to allow very general unknown vectors x(k). Rather than assuming sparsity, we instead make the weaker assumption that they have bounded 2 norm. We also allow for distributions of x(k) which make it impossible to recover all columns of R; we simply recover a subset of essential columns.

With this in mind, our desired dictionary learning result is Theorem 4. We plan to apply this theorem with N as thrice the maximum between the number of modules and the number of objects in any communication graph, S~ as the number of samples necessary to learn a module, and H as three times the depth of our modular network. Additionally, we think of ϵ1 as the tolerable input error while ϵH is the desired output error after recursing H times.

Theorem 4.

[Recursable Dictionary Learning] There exists a family of distributions {D(b,q,d𝑠𝑘𝑒𝑡𝑐ℎ)} which produce d𝑠𝑘𝑒𝑡𝑐ℎ×d𝑠𝑘𝑒𝑡𝑐ℎ matrices satisfying the following. For any positive integer N, positive constant H, positive real ϵH, base number of samples S𝑝𝑜𝑙𝑦(N), block size b𝑝𝑜𝑙𝑦(logN,logd𝑠𝑘𝑒𝑡𝑐ℎ,1/ϵH), nonzero block probability q𝑝𝑜𝑙𝑦(logN,logd𝑠𝑘𝑒𝑡𝑐ℎ,1/ϵH)/d𝑠𝑘𝑒𝑡𝑐ℎ, and dimension d𝑠𝑘𝑒𝑡𝑐ℎ𝑝𝑜𝑙𝑦(1/ϵH,logN,logS), there exists a sequence of errors (0<)ϵ1ϵ2ϵH-1(ϵH) with ϵ1𝑝𝑜𝑙𝑦(ϵH), such that the following is true. For any h[H-1], let Sh=SNh-1. For any unknown vectors x(1),,x(Sh)Rd𝑠𝑘𝑒𝑡𝑐ℎ×N with 2-norm at most O(1), if we draw R1,,RND(d𝑠𝑘𝑒𝑡𝑐ℎ) and receive Sh noisy samples y(k)[R1R2RN]x(k)+z1(k)+z(k) where each z1(k)Rd𝑠𝑘𝑒𝑡𝑐ℎ is noise with ||z1(k)||1O(d𝑠𝑘𝑒𝑡𝑐ℎ) (independent of our random matrices) and each z(k)Rd𝑠𝑘𝑒𝑡𝑐ℎ is noise with ||z(k)||ϵh (also independent of our random matrices), then there is an algorithm which takes as input h, y(1), …, y(Sh), runs in time 𝑝𝑜𝑙𝑦(Sh,d𝑠𝑘𝑒𝑡𝑐ℎ), and with high probability outputs R^1,,R^N,x^(1),,x^(Sh) satisfying the following for some permutation π of [N]:

  • for every i[N] and j[d𝑠𝑘𝑒𝑡𝑐ℎ], if there exists k[Sh] such that |x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1 then the jth column of R^π(i) is 0.2d𝑠𝑘𝑒𝑡𝑐ℎ-close in Hamming distance from the jth column of Ri.

  • for every k[Sh],i[N],j[d𝑠𝑘𝑒𝑡𝑐ℎ], |x(π(i)-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)-x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1.

5.1 Recursable Dictionary Learning Implies Network Learnability

We want to use Theorem 4 to learn a teacher modular deep network, but we need to first address an important issue. So far, we have not specified how the deep modular network decides upon its input-dependent communication graph. As a result, the derivation of the communication graph cannot be learned (it’s possibly an uncomputable function!). When the communication graph is a fixed tree (always the same arrangement of objects but with different attributes), we can learn it. Note that any fixed communication graph can be expanded into a tree; doing so is equivalent to not re-using computation. Regardless of the communication graph, we can learn the input/output behavior of each module regardless of whether the communication graph is fixed.

Theorem 5.

If the teacher deep modular network has constant depth, then any module M which satisfies the following two properties:

  • (Robust Module Learnability) The module is learnable from (α=𝑝𝑜𝑙𝑦(N)) input/output training pairs which have been corrupted by error at most a constant ϵ>0.

  • (Sufficient Weight) In a (β=1𝑝𝑜𝑙𝑦(N))-fraction of the inputs, the module produces an object and all of the input objects to that object have effective weight at least w.

can, with high probability, be learned from 𝑝𝑜𝑙𝑦(N) overall sketches of dimension 𝑝𝑜𝑙𝑦(1/w,1/ϵ)log2N.

Suppose we additionally know that the communication graph is a fixed tree. We can identify the sub-graph of objects which each have effective weight w in a (β=1𝑝𝑜𝑙𝑦(N))-fraction of the inputs.

Theorem 5 is proved in Appendix E. The main idea is to just repeatedly apply our recursable dictionary learning algorithm and keep track of which vectors correspond to sketches and which vectors are garbage.

5.2 Recursable Dictionary Learning: Proof Outline

The main idea of our recursable dictionary learning algorithm is the following. The algorithm proceeds by iteratively examining each of the dsketch/b blocks of each of the Sh received samples. For the th block of the ith sample, denoted by y(i)[(-1)b+1:b+1], it tries to determine whether it is dominated by the contribution of a single (σs,σc,σm) (and is not composed of the superposition of more than one of these). To do so, it first normalizes this block by its 1-norm and checks if the result is close to a point on the Boolean hypercube in distance. If so, it rounds (the 1-normalized version of) this block to the hypercube; we here denote the resulting rounded vector by y¯(i)[(-1)b+1:b+1]. We then count the number of blocks [dsketch/b] whose rounding y¯(i)[(-1)b+1:b+1] is close in Hamming distance to y¯(i)[(-1)b+1:b+1]. If there are at least 0.8qdsketch of these, we add the rounded block y¯(i)[(-1)b+1:b+1] to our collection (if it’s not close to an already added vector). We also cluster the added blocks in terms of their matrix signatures σm in order to associate each of them to one of the matrices R1,,RN. Using the matrix signatures as well as the column signatures {σc} allows us to recover all the essential columns of the original matrices. The absolute values of the x coordinates can also be inferred by adding the 1-norm of a block when adding its rounding to the collection. The signs of the x coordinates can also be inferred by first inferring the true sign of the block and comparing it to the sign of the vector whose rounding was added to the collection.

5.3 The Block-Sparse Distribution 𝒟

We are now ready to define our distribution 𝒟 on random (square) matrices R. It has the following parameters:

  • The block size b+ which must be a multiple of 3 and at least 3max(log2N,log2dsketch+3).

  • The block sampling probability q[0,1]; this is the probability that a block is nonzero.

  • The number of rows/columns dsketch+. It must be a multiple of b, as each column is made out of blocks.

Each column of our matrix is split into dsketch/b blocks of size b. Each block contains three sub-blocks: a random string, the matrix signature, and the column signature. To specify the column signature, we define an encoding procedure Enc which maps two bits bm,bs and the column index into a (b/3)-length sequence. Enc:{±1}2×[dsketch]{±1dsketchq}b/3, which is presented as Algorithm 4. These two bits encode the parity of the other two sub-blocks, which will aid our dictionary learning procedure in recovery of the correct signs. The sampling algorithm which describes our distribution is presented as Algorithm 5.3.

 blocks, each with b entries{[fs,1,1σs,1fs,1,2σs,2fs,1,3σs,30fs,1,dsketchσs,dsketchfc,1,1σc,1,1fc,1,2σc,1,2fc,1,3σc,1,30fc,1,dsketchσc,1,dsketchfm,1,1σmfm,1,2σmfm,1,3σm0fm,1,dsketchσm0fs,2,2σs,20000fc,2,2σc,2,20000fm,2,2σm000fs,3,1σs,1fs,3,2σs,2fs,3,3σs,3fs,3,4σs,40fc,3,1σc,3,1fc,3,2σc,3,2fc,3,3σc,3,3fc,3,4σc,3,40fm,3,1σmfm,3,2σmfm,3,3σmfm,3,4σm0fs,4,1σs,1fs,4,2σs,2fs,4,3σs,30fs,4,dsketchσs,dsketchfc,4,1σc,4,1fc,4,2σc,4,2fc,4,3σc,4,30fc,4,dsketchσc,4,dsketchfm,4,1σmfm,4,2σmfm,4,3σm0fm,4,dsketchσm00fs,,3σs,3fs,,4σs,4000fc,,3σc,,3fc,,4σc,,4000fm,,3σmfm,,4σm0]

Figure 4: Example block-random matrix from distribution 𝒟(b,q,dsketch). dsketch/b denotes the number of blocks.
{algorithm}

[h] Enc(j,bm,bs) \[email protected]@algorithmic[1] \STATEInput: Column index j[dsketch], two bits bm,bs{±1}, .
\STATEOutput: A vector σc{±1dsketchq}b/3.
\[email protected] \STATESet σc to be the (zero-one) binary representation of j-1 (a log2dsketch-dimensional vector).
\STATEReplace each zero in σc with -1 and each one in σ with +1.
\STATEPrepend σc with a +1, making it a (log2dsketch+1)-dimensional vector.
\STATEAppend σc with (bm,bs), making it a (log2dsketch+3)-dimensional vector.
\STATEAppend σc with enough +1 entries to make it a (b/3)-dimensional vector. Note that b3(log2dsketch+3).
\STATEDivide each entry of σc by dsketchq. \RETURNσc. {algorithm}[H] 𝒟(b,q,dsketch) \[email protected]@algorithmic[1] \STATEInput: Block size b+, block sampling probability q[0,1], number of rows/columns dsketch.
\STATEOutput: A matrix Rdsketch×dsketch.
\[email protected] \STATEInitialize R to be the all-zeros dsketch×dsketch matrix.
\STATESample a “matrix signature” vector σm from the uniform distribution over {±1dsketchq}b/3.
\FORcolumn j[dsketch] \STATESample a “random string” vector σs,j from the uniform distribution over {±1dsketchq}b/3.
\FORblock i[dsketch/b] \STATESample three coin flips fm,i,j,fs,i,j,fc,i,j as independent Rademacher random variables (i.e. uniform over {±1}).
\STATECompute two bits fm,i,jfm,i,jsign(σm[1]) and fs,i,jfs,i,jssign(σs,j[1]).
\STATECompute a “column signature” vector σc,i,jEnc(j,fm,i,j,fs,i,j).
\STATESample ηi,j to be a (zero-one) Bernoulli random variable which is one with probability q.
\IFηi,j=1 \STATESet R[b(i-1)+1:bi+1,j] to be fs,i,jσs,j concatenated with fc,i,jσc,i,j concatenated with fm,i,jσm.
\ENDIF\ENDFOR\ENDFOR\RETURNR.

6 Conclusion

In this paper, we presented a sketching mechanism which captures several natural properties. Two potential areas for future work are our proposed use cases for this mechanism: adding a sketch repository to an existing modular network and using it to find new concepts, and using our sketches to learn a teacher network.

References

  • Andreas et al. (2016) Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. Neural module networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 39–48, 2016.
  • Arora et al. (2014a) Arora, S., Bhaskara, A., Ge, R., and Ma, T. Provable bounds for learning some deep representations. In International Conference on Machine Learning, pp. 584–592, 2014a.
  • Arora et al. (2014b) Arora, S., Bhaskara, A., Ge, R., and Ma, T. Provable bounds for learning some deep representations. In Xing, E. P. and Jebara, T. (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 584–592, Bejing, China, 22–24 Jun 2014b. PMLR. URL http://proceedings.mlr.press/v32/arora14.html.
  • Arora et al. (2014c) Arora, S., Ge, R., and Moitra, A. New algorithms for learning incoherent and overcomplete dictionaries. In Conference on Learning Theory, pp. 779–806, 2014c.
  • Arora et al. (2015) Arora, S., Ge, R., Ma, T., and Moitra, A. Simple, efficient, and neural algorithms for sparse coding. In Proceedings of The 28th Conference on Learning Theory, pp. 113–149, 2015.
  • Azam (2000) Azam, F. Biologically inspired modular neural networks. PhD thesis, Virginia Tech, 2000.
  • Brannon & Roitman (2003) Brannon, E. M. and Roitman, J. D. Nonverbal representations of time and number in animals and human infants. 2003.
  • Buciluǎ et al. (2006) Buciluǎ, C., Caruana, R., and Niculescu-Mizil, A. Model compression. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 535–541. ACM, 2006.
  • Clune et al. (2013) Clune, J., Mouret, J.-B., and Lipson, H. The evolutionary origins of modularity. Proc. R. Soc. B, 280(1755):20122863, 2013.
  • Danihelka et al. (2016) Danihelka, I., Wayne, G., Uria, B., Kalchbrenner, N., and Graves, A. Associative long short-term memory. In Proceedings of the 33rd International Conference on International Conference on Machine Learning, pp. 1986–1994. JMLR.org, 2016.
  • Du et al. (2017a) Du, S. S., Lee, J. D., and Tian, Y. When is a convolutional filter easy to learn? arXiv preprint arXiv:1709.06129, 2017a.
  • Du et al. (2017b) Du, S. S., Lee, J. D., Tian, Y., Poczos, B., and Singh, A. Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima. arXiv preprint arXiv:1712.00779, 2017b.
  • Ellis et al. (2018) Ellis, K., Ritchie, D., Solar-Lezama, A., and Tenenbaum, J. Learning to infer graphics programs from hand-drawn images. In Advances in Neural Information Processing Systems, pp. 6059–6068, 2018.
  • Fernando et al. (2017) Fernando, C., Banarse, D., Blundell, C., Zwols, Y., Ha, D., Rusu, A. A., Pritzel, A., and Wierstra, D. Pathnet: Evolution channels gradient descent in super neural networks. arXiv preprint arXiv:1701.08734, 2017.
  • Gayler (2004) Gayler, R. W. Vector symbolic architectures answer jackendoff’s challenges for cognitive neuroscience. arXiv preprint cs/0412059, 2004.
  • Graves et al. (2014) Graves, A., Wayne, G., and Danihelka, I. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.
  • Graves et al. (2016) Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471, 2016.
  • Grefenstette et al. (2015) Grefenstette, E., Hermann, K. M., Suleyman, M., and Blunsom, P. Learning to transduce with unbounded memory. In Advances in neural information processing systems, pp. 1828–1836, 2015.
  • Hanson & Wright (1971) Hanson, D. L. and Wright, F. T. A bound on tail probabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics, 42(3):1079–1083, 1971.
  • Hawkins & Blakeslee (2007) Hawkins, J. and Blakeslee, S. On intelligence: How a new understanding of the brain will lead to the creation of truly intelligent machines. Macmillan, 2007.
  • Hinton et al. (2015) Hinton, G., Vinyals, O., and Dean, J. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015.
  • Hinton et al. (2000) Hinton, G. E., Ghahramani, Z., and Teh, Y. W. Learning to parse images. In Advances in neural information processing systems, pp. 463–469, 2000.
  • Hinton et al. (2011) Hinton, G. E., Krizhevsky, A., and Wang, S. D. Transforming auto-encoders. In International Conference on Artificial Neural Networks, pp. 44–51. Springer, 2011.
  • Hoeffding (1963) Hoeffding, W. Probability inequalities for sums of bounded random variables. J. American Statist. Assoc., 58:13 – 30, 03 1963. doi: 10.2307/2282952.
  • Hu et al. (2017) Hu, R., Andreas, J., Rohrbach, M., Darrell, T., and Saenko, K. Learning to reason: End-to-end module networks for visual question answering. In Proceedings of the IEEE International Conference on Computer Vision, pp. 804–813, 2017.
  • Joulin & Mikolov (2015) Joulin, A. and Mikolov, T. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in neural information processing systems, pp. 190–198, 2015.
  • Kane & Nelson (2014) Kane, D. M. and Nelson, J. Sparser johnson-lindenstrauss transforms. J. ACM, 61(1):4:1–4:23, January 2014. ISSN 0004-5411. doi: 10.1145/2559902. URL http://doi.acm.org/10.1145/2559902.
  • Levy & Gayler (2008) Levy, S. D. and Gayler, R. Vector symbolic architectures: A new building material for artificial general intelligence. In Proceedings of the 2008 Conference on Artificial General Intelligence 2008: Proceedings of the First AGI Conference, pp. 414–418. IOS Press, 2008.
  • Li & Yuan (2017) Li, Y. and Yuan, Y. Convergence analysis of two-layer neural networks with ReLU activation. arXiv preprint arXiv:1705.09886, 2017.
  • Oh et al. (2017) Oh, J., Singh, S., Lee, H., and Kohli, P. Zero-shot task generalization with multi-task deep reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 2661–2670. JMLR. org, 2017.
  • Papyan et al. (2018) Papyan, V., Romano, Y., Sulam, J., and Elad, M. Theoretical foundations of deep learning via sparse representations: A multilayer sparse model and its connection to convolutional neural networks. IEEE Signal Processing Magazine, 35(4):72–89, 2018.
  • Real et al. (2018) Real, E., Aggarwal, A., Huang, Y., and Le, Q. V. Regularized evolution for image classifier architecture search. arXiv preprint arXiv:1802.01548, 2018.
  • Sabour et al. (2017) Sabour, S., Frosst, N., and Hinton, G. E. Dynamic routing between capsules. In Advances in Neural Information Processing Systems, pp. 3856–3866, 2017.
  • Smolensky (1990) Smolensky, P. Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial intelligence, 46(1-2):159–216, 1990.
  • Spielman et al. (2012) Spielman, D. A., Wang, H., and Wright, J. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pp. 37–1, 2012.
  • Sukhbaatar et al. (2015) Sukhbaatar, S., Weston, J., Fergus, R., et al. End-to-end memory networks. In Advances in neural information processing systems, pp. 2440–2448, 2015.
  • Wu et al. (2017) Wu, J., Tenenbaum, J. B., and Kohli, P. Neural scene de-rendering. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  • Yi et al. (2018) Yi, K., Wu, J., Gan, C., Torralba, A., Kohli, P., and Tenenbaum, J. B. Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding. In Advances in Neural Information Processing Systems (NIPS), 2018.
  • Zaremba & Sutskever (2015) Zaremba, W. and Sutskever, I. Reinforcement learning neural turing machines-revised. arXiv preprint arXiv:1505.00521, 2015.
  • Zhang et al. (2017) Zhang, Q., Panigrahy, R., Sachdeva, S., and Rahimi, A. Electron-proton dynamics in deep learning. arXiv preprint arXiv:1702.00458, 2017.
  • Zhong et al. (2017a) Zhong, K., Song, Z., and Dhillon, I. S. Learning non-overlapping convolutional neural networks with multiple kernels. arXiv preprint arXiv:1711.03440, 2017a.
  • Zhong et al. (2017b) Zhong, K., Song, Z., Jain, P., Bartlett, P. L., and Dhillon, I. S. Recovery guarantees for one-hidden-layer neural networks. arXiv preprint arXiv:1706.03175, 2017b.

Appendix A Technical Machinery for Random Matrices

In this appendix, we present several technical lemmas which will be useful for analyzing the random matrices that we use in our sketches.

A.1 Notation

Definition 1.
Suppose we have two fixed vectors x,yRd𝑠𝑘𝑒𝑡𝑐ℎ and random matrices R1,,Rk drawn independently from distributions D1,,Dk. We have a random variable Z which is a function of x, y, and R1,,Rk. Z is a δ-nice noise variable with respect to D if the following two properties hold: 1. (Centered Property) 𝔼R1𝒟1,Rk𝒟k[Z]=0. 2. (δ-bounded Property) With high probability (over R1𝒟1,Rk𝒟k), |Z|δ||x||2||y||2.
Definition 2.
We say that a distribution D has the αD-Leaky δD-Desynchronization Property if the following is true. If RD, then the random variable Z=Rx,y-αDx,y is a δD-nice noise variable. If αD=0 then we simply refer to this as the δD-Desynchronization Property.
Definition 3.
We say that a distribution D has the αI-scaled δI-Isometry Property if the following is true. If RD and x=y, then the random variable Z=Rx,Rx-αIx,x is a δI-nice noise variable. If αI=1 then we simply refer to this as the δI-Isometry Property.
Since our error bounds scale with the 2 norm of vectors, it will be useful to use isometry to bound the latter using the following technical lemma.
Lemma 1.
If D satisfies the αI-scaled δI-Isometry Property, then with high probability: ||Rx||22(αI+δI)||x||22
Proof.
Consider the random variable: Z=Rx,Rx-αIx,x Since 𝒟 satisfies the αI-scaled δI-Isometry Property, Z is a δI-nice random variable. Hence with high probability: Rx,Rx-αIx,x δI||x||22 Rx,Rx (αI+δI)||x||22 This completes the proof. ∎
While isometry compares Rx,Rx and x,x, sometimes we are actually interested the more general comparison between Rx,Ry and x,y. The following technical lemma lets get to the general case at the cost of a constant blowup in the noise.
Lemma 2.
If D satisfies the αI-scaled δI-Isometry Property, then the random variable Z=Rx,Ry-αIx,y is a (3δI)-nice noise variable.
Proof.
This proof revolves around the scalar fact that (a+b)2=a2+2ab+b2, so from squaring we can get to products. This claim is trivially true if x or y is the zero vector. Hence without loss of generality, we can scale x and y to unit vectors, since being a nice noise variable is scale invariant. We invoke the αI-scaled δI-bounded Isometry Property three times, on x1=x+y, x2=x, and x3=y. This implies that the following three noise variables are δI-nice: Z1 =R(x+y),R(x+y)-αIx+y,x+y Z2 =Rx,Rx-αIx,x Z3 =Ry,Ry-αIy,y We now relate our four noise variables of interest. Z1 =[Rx,Rx+2Rx,Ry+Ry,Ry] -αI[x,x+2x,y+y,y] =Z2+2Z+Z3 Z =12Z1-12Z2-12Z3 Hence, Z is centered. We can bound it by analyzing the 2 lengths of the vectors that we applied isometry to. With high probability: |Z1| δI||x+y||22 δI(||x||2+||y||2)2 4δI |Z2| δI||x||22 δI |Z3| δI||y||22 δI Hence Z is also (3δI)-bounded, making it a (3δI)-noise variable, completing the proof. ∎

A.2 Transparent Random Matrices

For our sketch, we sometimes want to both rotate a vector and pass it through as-is. For these cases, the distribution Transparent(𝒟) is useful and defined as follows. We draw R from D and return R¯=(I+R2). This subsection explains how the desynchronization and isometry of 𝒟 carry over to Transparent(𝒟). This technical lemma shows how to get desynchronization.
Lemma 3.
If D satisfies the δD-Desynchronization Property, then Transparent(D) satisfies the (1/2)-leaky (δD/2)-Desynchronization Property.
Proof.
We want to show that if R¯ is drawn from Transparent(𝒟), then the following random variable Z is a (δD/2)-nice noise variable. Z =R¯x,y-12x,y =xT(I+RT2)y-12x,y =12xTy+12xTRTy-12x,y =12[xTRTy]Let this be Z. Since 𝒟 satisfies the δD-Desynchronization Property, we know Z is a δD-nice noise variable. Our variable Z is just a scaled version of Z, making it a (δD/2)-nice noise variable. This completes the proof. ∎
This next technical lemma shows how to get isometry.
Lemma 4.
If D satisfies the δD-Desynchronization Property and the δI-Isometry Property, then Transparent(D) satisfies the 12-scaled (12δD+14δI)-Isometry Property.
Proof.
We want to show that if R¯ is drawn from Transparent(𝒟), and x=y, then the following random variable Z is a (δD+12δI)-nice noise variable: Z =R¯x,R¯x-12x,x =xT(I+RT2)(I+R2)x-12xTx =14(xTx+xTRx+xTRTx+xTRTRx)-12xTx =12Rx,xLet this be Z1.+14(Rx,Rx-x,x)Let this be Z2. Since 𝒟 satisfies the δD-Desynchronization Property, we know Z1 is a δD-nice noise variable. Since 𝒟 satisfies the δI-Isometry Property, we know Z2 is a δI-nice noise variable. This makes our variable Z a (12δD+14δI)-nice noise variable, as desired. ∎

A.3 Products of Random Matrices

For our sketch, we wind up multiplying matrices. In this subsection, we try to understand the properties of the resulting product. The distribution Product(𝒟1,𝒟2) is as follows. We independently draw R1𝒟1,R2𝒟2 and then return: R~=R2R1 . This technical lemma says that the resulting product is desynchronizing.
Lemma 5.
If D1 satisfies the δD,1-Desynchronization Property, D1 satisfies the δI,1-Isometry Property, and D2 satisfies the δD,2-leaky αD,2-Desynchronization Property, then Product(D1,D2) satisfies the [δD,1+δD,21+δI,1]-Desynchronization Property.
Proof.
We want to show that if R~ is drawn from Product(𝒟1,𝒟2), then the following random variable Z is a [δD,1+δD,21+δI,1]-nice noise variable. Z =R~x,y-x,y =R2R1x,y-x,y We now define some useful (noise) variables. Z1 R1x,y-x,y Z2 R2R1x,y-R1x,y Z =Z1+Z2 From our assumptions about 𝒟1 and 𝒟2, we know that Z1 is a δD,1-nice noise variable and Z2 is a δD,2-nice noise variable. By Lemma 1 we know that with high probability, ||R1x||221+δI,1. Hence, with high probability: |Z1| δD,1||x||2||y||2 |Z2| δD,21+δI,1||x||2||y||2 |Z| |Z1|+|Z2| [δD,1+δD,21+δI,1]||x||2||y||2 Hence Z is a [δD,1+δD,21+δI,1]-nice noise variable, completing the proof. ∎
This technical lemma says that the resulting product is isometric.
Lemma 6.
If D1 satisfies the αI,1-scaled δI,1-Isometry Property and D2 satisfies the αI,2-scaled δI,2-Isometry Property, then Product(D1,D2) satisfies the (αI,1αI,2)-scaled [δI,2(1+δI,1)+αI,2δI,1]-bounded Isometry Property.
Proof.
We want to show that if R~ is drawn from Product(𝒟1,𝒟2), and x=y, then the following random variable Z is a [δI,2(1+δI,1)+αI,2δI,1]-nice noise variable. Z R~x,R~x-αI,1αI,2x,x =xTR~TR~x-αI,1αI,2xTx =xTR1TR2TR2R1x-αI,1αI,2xTx We now define some useful (noise) variables. x0 x x1 R1x0 x2 R2x1 Z1 R1x0,R1x0-αI,1x0,x0 =||x1||22-αI,1||x0||22 Z2 R2x1,R2X1-αI,2x1,x1 =||x2||22-αI,2||x1||22 Z is just a weighted sum of our random variables: Z2+αI,2Z1 =||x2||22-αI,2||x1||22 +αI,2||x1||22-αI,1αI,2||x0||22 =||x2||22-αI,1αI,2||x0||22 =Z Since 𝒟1 satisfies the αI,1-scaled δI,1-Isometry Property we know that Z1 is a δI,1-nice noise variable. Similarly, we know Z2 is a δI,2-nice noise variable. As a result, Z is centered; it remains to bound it. By Lemma 1, we know that with high probability ||x1||221+δI,1. Hence with high probability: |Z1| δI,1||x0||22 |Z2| δI,2(1+δI,1)||x0||22 |Z| |Z2|+αI,2|Z1| δI,2(1+δI,1)+αI,2δI,1 Hence Z is a [δI,2(1+δI,1)+αI,2δI,1]-nice noise variable, completing the proof. ∎

A.4 Applying Different Matrices

For the analysis of our sketch, we sometimes compare objects that have been sketched using different matrices. The following technical lemma is a two matrix variant of desynchronization for this situation.
Lemma 7.
Suppose that we have a distribution D which satisfies the αI-scaled δI-Isometry Property and the αD-leaky δD-Desynchronization Property. Suppose we independently draw R1D and R2D. Then the random variable Z=R1x,R2y-αD2x,y is a (δDαI+δI+αDδD)-nice noise variable.
Proof.
We define useful (noise) variables Z1 and Z2. x R1x Z1 x,R2y-αDx,y Z2 R1x,y-αDx,y Z =Z1+αDZ2 Since 𝒟 satisfies the αD-leaky δD-Desynchronization Property, we know that Z1 and Z2 are δD-nice noise variables. Since D satisfies the αI-scaled δI-Isometry Property, we can apply Lemma 1 to show that with high probability, ||R1x||22(αI+δI). Hence with high probability: |Z1| δDαI+δI |Z2| δD |Z| |Z1|+αD|Z2| δDαI+δI+αDδD Hence Z is a (δDαI+δI+αDδD)-nice noise variable, as desired. This completes the proof. ∎

Appendix B Properties of the Block-Random Distribution

In this section, we prove that our block-random distribution over random matrices satisfies the isometry and desynchronization properties required by our other results. In particular, our goal is to prove the following two theorems:
Theorem 6.
Suppose that q is Ω(blogNd𝑠𝑘𝑒𝑡𝑐ℎ) and d𝑠𝑘𝑒𝑡𝑐ℎ is 𝑝𝑜𝑙𝑦(N). Then there exists a δ=O(blogNd𝑠𝑘𝑒𝑡𝑐ℎ) such that the block-random distribution D(b,q,d𝑠𝑘𝑒𝑡𝑐ℎ) satisfies the δ-Isometry Property.
Theorem 7.
Suppose that q is Ω(blogNd𝑠𝑘𝑒𝑡𝑐ℎ). Then there exists a δ=O(blogNd𝑠𝑘𝑒𝑡𝑐ℎ) such that the block-random distribution D(b,q,d𝑠𝑘𝑒𝑡𝑐ℎ) satisfies the O(logNd𝑠𝑘𝑒𝑡𝑐ℎ)-Desynchronization Property.
Note that instantiating the theorems with the minimum necessary b gives us good error bounds.
Corollary 1.
Suppose that b=3max(log2N,log2d𝑠𝑘𝑒𝑡𝑐ℎ+3), q=(logN+logd𝑠𝑘𝑒𝑡𝑐ℎ)logNd𝑠𝑘𝑒𝑡𝑐ℎ, and d𝑠𝑘𝑒𝑡𝑐ℎ is 𝑝𝑜𝑙𝑦(N). Then the block-random distribution D(b,q,d𝑠𝑘𝑒𝑡𝑐ℎ) satisfies the O~(1d𝑠𝑘𝑒𝑡𝑐ℎ)-Isometry Property and the O~(1d𝑠𝑘𝑒𝑡𝑐ℎ)-Desynchronization Property.

B.1 Isometry

In this subsection, we will prove Theorem 6. Our proof essentially follows the first analysis presented by Kane and Nelson for their sparse Johnson-Lindenstrauss Transform  (Kane & Nelson, 2014). Our desired result differs from theirs in several ways, which complicates our version of the proof: Their random matrices do not have block-level patterns like ours do. We handle this by using the small size of our blocks. Their random matrices have a fixed number of non-zeros per column, but the non-zeros within one of our columns are determined by independent Bernoulli random variables: ηi,j. We handle this by applying a standard concentration bound to the number of non-zeros. Some of our sub-block patterns depend on the ±1 coin flips for other sub-blocks, ruining independence. We handle this by breaking our matrix into three sub-matrices to be analyzed separately; see Figure 5. For the sake of completeness, we reproduce the entire proof here. The high-level proof plan is to use Hanson-Wright inequality (Hanson & Wright, 1971) to bound the th moment of the noise, and then use a Markov’s inequality to convert the result into a high probability bound on the absolute value of the noise. Suppose we draw a random matrix Rdsketch×dsketch from our distribution 𝒟(b,q,dsketch). We split R into three sub-matrices: Rsdsketch/3×dsketch containing the random string sub-blocks, Rmdsketch/3×dsketch containing the matrix signature sub-blocks, and Rcdsketch/3×dsketch containing the column signature sub-blocks. [fs,1,1σs,1fs,1,2σs,2fs,1,3σs,30fs,1,dsketchσs,dsketchfc,1,1σc,1,1fc,1,2σc,1,2fc,1,3σc,1,30fc,1,dsketchσc,1,dsketchfm,1,1σmfm,1,2σmfm,1,3σm0fm,1,dsketchσm0fs,2,2σs,20000fc,2,2σc,2,20000fm,2,2σm000fs,3,1σs,1fs,3,2σs,2fs,3,3σs,3fs,3,4σs,40fc,3,1σc,3,1fc,3,2σc,3,2fc,3,3σc,3,3fc,3,4σc,3,40fm,3,1σmfm,3,2σmfm,3,3σmfm,3,4σm0fs,4,1σs,1fs,4,2σs,2fs,4,3σs,30fs,4,dsketchσs,dsketchfc,4,1σc,4,1fc,4,2σc,4,2fc,4,3σc,4,30fc,4,dsketchσc,4,dsketchfm,4,1σmfm,4,2σmfm,4,3σm0fm,4,dsketchσm00fs,,3σs,3fs,,4σs,4000fc,,3σc,,3fc,,4σc,,4000fm,,3σmfm,,4σm0] Figure 5: The proof of Theorem 6 involves three sub-matrices of a random block-random matrix. The first of these sub-matrices, Rs, is highlighted here in green. It consists of all the random string sub-blocks. Just as in Figure 4, dsketch/b is shorthand for the number of blocks. We fix δ=O(logNdsketch). Consider any one of these sub-matrices, R. We wish to show that for any unit vector xdsketch, with high probability over R𝒟(b,q,dsketch): ||Rx||22[13(1-δ),13(1+δ)] Since this would imply that with high probability (due to union-bounding over the three sub-matrices): ||Rx||22 ={s,c,m}||Rx||22 [1-δ,1+δ] We will use the variant of the Hanson-Wright inequality presented by Kane and Nelson (Kane & Nelson, 2014).
Theorem 8 (Hanson-Wright Inequality (Hanson & Wright, 1971)).
Let z=(z1,,zn) be a vector of i.i.d. Rademacher ±1 random variables. For any symmetric BRn×n and 2, 𝔼|zTBz-trace(B)|Cmax{||B||F,||B||2} for some universal constant C>0 independent of B,n,.
Note that in the above theorem statement, ||B||F is the Frobenius norm of matrix B (equal to the 2 norm of the flattened matrix) while ||B||2 is the operator norm of matrix B (equal to the longest length of A applied to any unit vector). Our immediate goal is now to somehow massage ||Rx||22 into the quadratic form zTBz that appears in the inequality. We begin by expanding out the former. Note that for simplicity of notation, we’ll introduce some extra indices: we use σs,i,j to denote σs,j and σm,i,j to denote σm so that all three types of sub-block patterns can be indexed the same way. Also, we’ll use dsketch/b to denote the number of blocks. Rx =j=1dsketch[η1,jf,1,jσ,1,jη2,jf,2,jσ,2,jη,jf,,jσ,,j]xj ||Rx||22 =xTRTRx =i=1j=1dsketchj=1dsketch(ηi,jf,i,jσ,i,jxj)T(ηi,jf,i,jσ,i,jxj) =i=1j=1dsketchj=1dsketchηi,jηi,jf,i,jf,i,jxjxjσ,i,j,σ,i,j As before, this can also be expressed as a quadratic form in the f variables. In particular, let the dsketch×dsketch block-diagonal matrix B is as follows. There are blocks B,i, each dsketch×dsketch in shape. The (j,j)th entry of the ith block is ηi,jηi,jxjxjσ,i,j,σ,i,j. As a result, ||Rx||22=fTBf, where f is the dsketch-dimensional vector (f,1,1,f,1,2,). It is important to note for the sake of the Hanson-Wright inequality that the matrix B is random, but it does not depend on the f variables. Of course, Bc depends on the f variables involved in Bs and Bm by construction, but not its own (and this is why we split our analysis over the three submatrices). All that remains before we can effectively apply the Hanson-Wright inequality is to bound the trace, Frobenius norm, and operator norm of this matrix B. We begin with the trace, which is a random variable depending on the zero-one Bernoulli random variables η. trace(B) =i=1j=1dsketchηi,j2xj2||σ,i,j||22 =i=1j=1dsketchηi,jxj2(b/3)(1dsketchq) =i=1j=1dsketchηi,jxj213q Let the random variable Xi,jηi,jxj213q. Since x was a unit vector, we know that the expected value of ijXi,j=13. Additionally, note that: i=1j=1dsketch(xj213q)2 =19q2j=1dsketchxj419 By Hoeffding’s Inequality (Hoeffding, 1963) we the probability that this sum (i.e. the trace) differs too much from its expectation: Pr[|trace(B)-13|δ6] exp(-2(δ/6)2i=1j=1dsketch(xj213q)2) exp(-3(δ)22) Hence there exists a sufficiently large δ=O(logN) so that we will have with high probability that the trace is within δ6 of 13. Next, we want a high probability bound on the Frobenius norm of B. ||B||F2 =i=1j=1dsketchj=1dsketch(ηi,jηi,jxjxjσ,i,j,σ,i,j)2 =i=1j=1dsketchj=1dsketchηi,jηi,jxj2xj2σ,i,j,σ,i,j2 i=1j=1dsketchj=1dsketchηi,jηi,jxj2xj2(1dsketchqb/3)2 =192q2j=1dsketchj=1dsketchxj2xj2i=1ηi,jηi,j We want to show that for any two columns j,j there aren’t too many matching non-zero blocks. The number of matching blocks is the sum of i.i.d. Bernoulli random variables with probability q2. By a Hoeffding Bound (Hoeffding, 1963), we know that for all t0: Pr[i=1ηi,jηi,jq2+t]exp(-2t2/) So the desired claim is true with high probability (i.e. polynomially small in both N and dsketch) as long as we can choose t to be on the order of log(Ndsketch). However, we want this to be O(q2). Since by assumption q is Ω(logN), we actually just want it to be O(logN). This is true since we assumed dsketch was poly(N) and 1. We can now safely union-bound over all pairs of columns and finish bounding the Frobenius norm (with high probability): ||B||F2 192q2j=1dsketchj=1dsketchxj2xj2||x||24=1O(q2) O(1) Finally, we want a high probability bound on the operator norm of B. The operator norm is just its maximum eigenvalue, and its eigenvalues are the eigenvalues of its blocks. We can write each block as a rank-(b/3) decomposition k=1b/3ui,kui,kT by breaking up the inner products by coordinate (each yielding a vector ui,k). Specifically, the vector ui,kdsketch is defined by (ui,k)j=ηi,jxjσ,i,j[k]. ||B||2 =maxi||B,i||2 =maxi||k=1b/3ui,kui,kT||2 maxik=1b/3||ui,kui,kT||2 =maxik=1b/3||ui,k||22 maxik=1b/31dsketchq||x||22 =b31dsketchq =13q Applying the Hanson-Wright inequality, Theorem 8, we know that with high probability: 𝔼|zTBz-13±δ2|Cmax{O(1/),O(1/(q))} Applying Markov’s inequality for an even integer: Pr[|zTBz-13±δ2|>δ6] <(6δ)Cmax{O(1/),O(1/(q))} Pr[|zTBz-13|>δ3] <(6Cδmax{O(1/),O(1/(q))}) We’ll need to choose a sufficiently large on the order of logN: Pr[|zTBz-13|>δ3] <(6Cδmax{O(logN),O(logNq)})Θ(logN) <(6CδO(logN))Θ(logN) We again used that q is Ω(logN). We conclude by choosing δ=O(logN), to make the base of the left-hand side a constant and achieve our polynomially small failure probability. This completes the proof of Theorem 6.

B.2 Desynchronization

In this subsection, we will prove Theorem 7. Suppose we draw a random matrix Rdsketch×dsketch from our distribution 𝒟(b,q,dsketch), and we have two unit vectors x,ydsketch. For convenience, we will index x using [dsketch] and y using {s,c,m}×[]×[b/3]. As in the previous section, we split R into Rs,Rc,Rm (see Figure 5) so that our random variables will be independent of the sub-block patterns. For one sub-matrix: yTRx=i=1j=1dsketchηi,jf,i,jσ,i,j,y,ixj We view this as a sum of dsketch random variables, which we will apply Bernstein’s Inequality to bound. Note that: |ηi,jf,i,jσ,i,j,y,ixj| b31dsketchq =13q i=1j=1dsketch𝔼[ηi,j2f,i,j2σ,i,j,y,i2xj2] =qi=1j=1dsketchσ,i,j,y,i2xj2 qi=1j=1dsketch||σ,i,j||22||y,i||22xj2 =qi=1j=1dsketchb31dsketchq||y,i||22xj2 =13 Combining these with Bernstein’s Inequality yields: Pr[yTRx>δ3]exp(-δ2/1813+19qδ3) We note that by assumption q=Ω(logN) and hence we can also choose a sufficiently large δ=O(logN) to make this probability polynomially small in N. This completes the proof.

Appendix C Proof Sketches for Sketch Prototypes

In this appendix, we present proof sketches for our sketch prototypes.

C.1 Proof Sketches for Prototype A

Recall Claim 1, which we will now sketch a proof of. See 1
Proof Sketch.
We multiply our overall sketch with RM(θ)T=RM(θ)-1. This product is θwθRM(θ)-1RM(θ)xθ. Our signal term occurs when θ=θ and is wθxθ. We think of the other terms as noise; we know from our orthonormal matrix properties that with high probability they each perturb any specific coordinate by at most O(wθlogN/dsketch). Taken together, no coordinate is perturbed by more than O(logN/dsketch). Dividing both our signal term and noise by wθ, we get the desired claim. ∎
Recall Claim 2, which we will now sketch a proof of. See 2
Proof Sketch.
Consider two overall sketches s=θwθRM(θ)xθ and s¯=θ¯w¯θ¯RM(θ¯)xθ¯. Their dot-product can be written as θθ¯wθw¯θ¯xθTRM(θ)TRM(θ¯)xθ¯. First, let us suppose we are in case (i) and they share no modules. Since orthonormal matrices are desynchronizing, each term has magnitude at most O(wθw¯θ¯logN/dsketch). Since the sum of each set of weights is one, the total magnitude is at most O(logN/dsketch). This completes the proof of case (i). Next, let us suppose we are in case (ii) and they share an object θ. Since orthonormal matrices are isometric, the term θ=θ¯=θ has a value of wθw¯θ. We can analyze the remaining terms as in case (i); they have total magnitude at most O(logN/dsketch). The worst-case is that the noise is negative, which yields the claim for case (ii). We need to analyze case (iii) a little differently. Since our objects are paired up between the sketches, we refer to the objects as θ1,,θk (in the first sketch) and θ¯1,,θ¯k (in the second sketch. Because they are close in 2 distance, we can write xθ¯i=xθi+ϵi, where each ϵi is a noise vector with 2 length at most ϵ. We can write our second sketch as s¯=iwθiRM(θi)(xθi+ϵi) (by assumption, the paired objects had the same weight and were produced by the same module). But then s¯=s+iwθiRM(θi)ϵi! Since orthonormal matrices are isometric and the weights sum to one, s¯ is at most ϵ away from s in 2 norm, as desired. ∎

C.2 Proof Sketches for Prototype B

Recall Claim 3, which we will now sketch a proof of. See 3
Proof Sketch.
We begin with the easier case (i). For case (i), we attempt to recover xθ via multiplying the sketch by RM(θ),1T. The signal component of our sketch has the form (I+Ri2)12RM(θ),1Txθ. The Ri/2 part can be considered noise, and the I/2 part gives us a quarter of the signal we had when analyzing sketch A. The noise calculation is the same as before because RM(θ) does not occur anywhere else, so we get the same additive error (up to a constant hidden in the big-oh notation). For the harder case (ii), we multiply the sketch by RM(θ)TRiT instead. This recovers the Ri/2 part instead of the I/2 part, but everything else is the same as the previous case. ∎
Recall Claim 4, which we will now sketch a proof of. See 4
Proof Sketch.
Case (i) is the same as before; the desynchronizing property of orthonormal matrices means that taking the dot-product of module sketches, even when transformed by I/2 or Ri/2, results in at most O(logN/dsketch) noise. Regarding case (ii), our new signal term is weaker by a factor of four. Notice that for both sketches, the object sketch sobject(θ) is still identical. We lose our factor of four when considering that a (I+Ri2) has been added into the tuple sketch; the I/2 lets through the information we care about, and compounded over two sketches results in a factor four loss. If the object were located at the same index in both sketches, we would only lose a factor of two. Regarding case (iii), the new module sketch is only half-based on attributes; the other half agrees if the objects have the same module. As a result, changing the attributes has half the effect as before. Case (iv) is similar to case (i), except only the e1 component of the module sketch is similar, resulting in an additional factor two loss from each sketch, for a final factor of sixteen. ∎
Recall Claim 5, which we will now sketch a proof of. See 5
Proof Sketch.
It is more intuitive to begin with case (ii). Consider what would happen if we performed case (i) of Attribute Recovery as in Claim 3. That claim assumed that there were no other objects produced by the same module, but if there were (and they had the same weight w), then their attribute vectors would be added together. This exactly yields the current case (ii). Next, for case (i), we simply observe that the object sketch treats xθ the same way as it treats e1, so we could use the same idea to recover the sum, over all objects with the same module, of e1. That is exactly the number of such modules times e1, so looking at the first coordinate gives us the desired estimate for the current case (i). ∎

Appendix D Proofs for Final Sketch

In this appendix, we present proofs for the properties of our final sketch. Recall that our final sketch is defined as follows. stuple(s1,,sk) i=1kwi(I+Ri2)si sobject(θ) (I+RM(θ),02)stuple(sattr(θ),sinput(θ),12,12) sattr(θ) 12RM(θ),1xθ+12RM(θ),2e1 sinput(θ) stuple(sobject(θ1),,sobject(θk),w1,,wk) soverall sinput(output pseudo-object) If we unroll these definitions, then the overall sketch has the form: soverall=θwθj=13h(θ)[(I+Rθ,j2)]sobject(θ) where h(θ) is the depth of object θ and (I+Rθ,j2) is the jth matrix when walking down the sketch tree from the overall sketch to the θ object sketch (i.e. alternating between input index, module matrix, and a one or two index into module versus inputs). Technical Assumptions. For this section, we need the following technical modification to the sketch. The Ri matrices for the tuple operators are redrawn at every depth level of the sketch, where the depth starts at one at the overall sketch and increases every time we take a tuple sketch. Additionally, we assume that we can guarantee δ14H by appropriately increasing the sketch dimension (in the typical case where H is constant, this just increases the sketch dimension by a constant); this section simply accepts a δ guarantee derived in Appendix B and does not tinker with sketch parameters.

D.1 Proofs for Attribute Recovery

Theorem 9.
Our final sketch has the Attribute Recovery property, which is as follows. Consider an object θ which lies at depth h(θ) in the overall sketch and with effective weight wθ. (i) Suppose no other objects in the overall sketch are also produced by M(θ). We can produce a vector estimate of the attribute vector xθ, which with high probability has an additive error of at most O(23h(θ)h(θ)δ/wθ) in each coordinate. (ii) Suppose we know the sequence of input indices to get to θ in the sketch. Then even if other objects in the overall sketch are produced by M(θ), we can still produce a vector estimate of the attribute vector xθ, which with high probability has an additive error of at most O(23h(θ)h(θ)δ/wθ) in each coordinate.
Proof.
We begin by proving the easier case (i). Suppose that our overall sketch is s. Let β=23h(θ)+1/wθ, and imagine that we attempt to recover the jth coordinate of xθ by computing βejTRM(θ),1Ts, which has the form: θβwθejTRM(θ),1Tj=13h(θ)[(I+Rθ,j2)]sobject(θ) When θ=θ, we get the term: 23h(θ)+1ejTRM(θ),1Tj=13h(θ)[(I+Rθ,j2)]sobject(θ) If we expand out each transparent matrix, we would get 23h(θ) sub-terms. Let’s focus on the sub-term where we choose I/2 every time: 2ejTRM(θ),1T[12RM(θ),1xθ+12RM(θ),2e1] By Lemma 2, we know that with high probability (note ej and xθ are both unit vectors): |2ejTRM(θ),1T×12RM(θ),1xθ-ejTxθ|3δ=O(δ) This half of the sub-term is (approximately) the jth coordinate of xθ, up to an additive error of O(δ). We control the other half using Lemma 7: |2ejTRM(θ),1T×12RM(θ),2e1|δ1+δ=O(δ) It remains to bound the additive error from the other sub-terms and the other terms. The other sub-terms have the form: 2ejTRM(θ),1TR~sobject(θ) where R~ is a product of one to 3h(θ) R matrices. By Lemma 1, we know that with high probability sobject(θ) and RM(θ),1ej have squared 2 norm at most (1+δ). We analyze R~ by repeatedly applying Lemma 5: we know that the distribution of one matrix satisfies δ-Desynchronization and δ-Isometry. Let γ=1+δ. Then the product distribution of two matrices satisfies [(1+γ)δ]-Desynchronization, the product distribution of three matrices satisfies [(1+γ+γ2)δ]-Desynchronization, and the product distribution of 3h(θ) matrices satisfies [γ3h(θ)-1γ-1δ]-Desynchronization. The last desynchronization is the largest, therefore no matter how many matrices are being multiplied, with high probability the absolute value of any other sub-term is bounded by: 2γ3h(θ)-1γ-1δ(1+δ) 2γ6h(θ)-1γ2-1δ(1+δ) 2(1+δ)3h(θ)-1δδ(1+δ) 2(1+O(h(θ)δ)-1)(1+δ) O(h(θ)δ) Note that we used the fact that (1+x)n1+O(xn) if xn12. Hence, the absolute value of the sum of the other sub-terms is bounded by O(23h(θ)h(θ)δ). We now bound the additive error from the other terms, which have the form: βwθejTRM(θ),1Tj=13h(θ)[(I+Rθ,j2)]sobject(θ) The plan is to use the desynchronization of RM(θ),1. To do so, we will need to bound the 2 length of sobject(θ) as it gets multiplied by this sequence of matrices. By Lemma 4 that the distribution of these matrices is 12-scaled (34δ)-Isometric. By repeatedly applying Lemma 1 we know that the squared 2 length is upper bounded by (12+34δ)3h(θ)(1+δ). By our assumptions, this is upper-bounded by a constant: (12+34δ)3h(θ)(1+δ) (1+δ)3h(θ)+1 (1+1/(2H))2H e Now, by the desynchronization of RM(θ),1, we know that with high probability the absolute value of the term indexed by θ is at most O(βwθδ). Hence with high probability the absolute value of all other terms is at most O(βδ). Plugging in our choice of β, it is at most O(23h(θ)+1δ/wθ). Hence we have shown that with high probability, we can recover the jth coordinate of xθ with the desired additive error. This completes the proof of case (i). We now prove the harder case (ii). Again, we let β=23h(θ)+1/wθ, and imagine that we attempt to recover the jth coordinate of xθ by computing βejTRM(θ),1Tj=13h(θ)[Rθ,jT]s, which has the form: θβwθejTRM(θ),1Tj=13h(θ)[Rθ,jT]   j=13h(θ)[(I+Rθ,j2)]sobject(θ) It is worth noting that we did not compute the alternative product βejTRM(θ),1Tj=13h(θ)[(I+Rθ,jT2)]s because the transparent matrices in the alternative would allow through information about other objects produced by the same module. When θ=θ, we get the term: 23h(θ)+1ejTRM(θ),1Tj=13h(θ)[Rθ,jT]   j=13h(θ)[(I+Rθ,j2)]sobject(θ) If we expand out each transparent matrix, we would get 23h(θ) sub-terms. Let’s focus on the sub-term where we choose R/2 every time: 2ejTRM(θ),1TR~TR~[12RM(θ),1xθ+12RM(θ),2e1] where R~=j=13h(θ)[Rθ,j]. As before, we expect to get some signal from the first half 12RM(θ),1xθ and some noise from the second half 12M(θ),2e1. Let us begin with the first half. The matrices involved match exactly, so it is a matter of repeatedly applying Lemma 6. Note that all matrices involved are δ-Isometric. Since at each step we multiply the isometry parameter by (1+δ) and then add δ, the isometry parameter after combining 3h(θ) times is: i=03h(θ)δ(1+δ)i =δ(1+δ)3h(θ)+1-11+δ-1 =(1+δ)3h(θ)+1-1 1+O(h(θ)δ)-1 O(h(θ)δ) Note that we used the fact that (1+x)n1+O(xn) if xn12 along with our assumption that δ<1/(4H). Hence the product of all (3h(θ)+1) matrices is O(h(θ)δ)-Isometric. By Lemma 2 this implies that with high probability: |R~RM(θ),1ej,R~RM(θ),1xθ-ej,xθ|O(h(θ)δ) We now control the noise half. By Lemma 7, with high probability: |RM(θ),1ej,RM(θ),2e1|δ1+δ=O(δ) We have already computed that the remaining 3h(θ) matrices is O(Hδ)-Isometric and hence approximately preserves this. Lemma 2 says that with high probability: |R~RM(θ),1ej,R~RM(θ),2e1   -RM(θ),1ej,RM(θ),2e1|O(Hδ) By the triangle inequality, we now know that with high probability, the sub-term where we choose R/2 every time is at most O(Hδ) additive error away from the jth coordinate of xθ. We now consider the other sub-terms. These other sub-terms are of the form: 2ejTRM(θ),1TR~TR~[12RM(θ),1xθ+12RM(θ),2e1] where R~ is still j=13h(θ)[Rθ,j] but R~ is now the product of a subsequence of those terms; we write it as j=13h(θ)[Sθ,j] where Sθ,j is either Rθ,j or the identity matrix. Next, we define xJj=J3h(θ)[Rθ,j]RM(θ),1ej and xJj=J3h(θ)[Sθ,j]sobject(θ). Additionally, when J=3h(θ)+1, xJ=RM(θ),1ej and xJ=sobject(θ). Our plan is to induct backwards from J=3h(θ)+1, controlling the dot product of the two. By Lemma 1, we know that all xJ and xJ have squared 2 length at most (1+δ)3h(θ)+1. Under our assumptions, this is less than e and is hence a constant. Lemma 7 and Lemma 2 already imply that for our base case of J=3h(θ)+1, the dot product of the two is at most O(δ) away from the jth coordinate of xθ. How does the dot product change from J to J-1? We either multiply xJ by a random matrix, or both xJ and xJ by the same random matrix. In the first case, the δ-Desynchronization of our matrices tells us that the new dot-product will be zero times the old dot-product plus O(δ) error. In the second case, the δ-Isometry of our matrices tells us that the new dot-product will be the old dot-product plus O(δ) error. Since the first case must occur at least once, we know that the final dot product when J=1 consists of no signal and O(h(θ)δ) noise. Hence, summing up our 23h(θ)-1 other sub-terms, we arrive at O(23h(θ)h(θ)δ) noise. It remains to consider the other terms. Unfortunately, we will need to analyze our other terms by breaking them into sub-terms as well, since otherwise we would need to consider the situation where R is applied to one vector and (I+R2) to the other. The other terms have the form: βwθejTRM(θ),1Tj=13h(θ)[Rθ,jT]   j=13h(θ)[(I+Rθ,j2)]sobject(θ) We break our terms into sub-terms, but only for the first 3h(θ) choices. Our analysis focuses on handling the case where θ is at a greater depth than θ; we handle the other case by inserting identity matrices and splitting them into I/2+I/2. We wind up with 23h(θ) sub-terms. Such a sub-term has the form: (2wθ/wθ)ejTRM(θ),1TR~TR~R~′′sobject(θ) where R~ j=13h(θ)[Rθ,j] R~ j=13h(θ)[Sθ,j] R~′′ j=3h(θ)+13h(θ)[I+Rθ,j2] and Sθ,j is either Rθ,j or the identity matrix. We define: xJ j=J3h(θ)[Rθ,j]RM(θ),1ej xJ j=J3h(θ)[Sθ,j]R~′′sobject(θ) When J=3h(θ)+1, we define xJRM(θ),1ej and xJ=R~′′sobject(θ). As usual, Lemma 1 guarantees that all xJ and xJ have constant 2 length. For our base induction case J=[max(3h(θ),3h(θ))+1], we would like to know the dot product of RM(θ),1ej with R~′′sobject(θ). We first analyze the dot product of RM(θ),1 with sobject(θ). Keep in mind that it may be the case that M(θ)=M(θ). In the same module case, we know by Lemma 2 and Lemma 7 that we get a signal of the jth component of xθ along with O(δ) noise. In the different module case, Lemma 7 is enough to tell us that there is no signal and O(δ) noise. As a reminder, the goal is to show that this signal does not get through, since we only want the jth component of xθ, not any other xθ. We know by Lemma 3 that our transparent matrices are 12-leaky O(δ)-Desynchronizing. Hence after applying all the transparent matrices, we know that at most we have our original signal (the jth component of xθ or nothing) and O(δ) noise (the noise telescopes due to the 12 leaking/scaling). This is the base case of our backwards induction, J=3h(θ)+1. We now consider what happens to the dot product of xJ and xJ as we move from J to J-1. We may either (a) multiply both by different random matrices, (b) multiply both by the same random matrix, or (c) multiply only one by a random matrix. Furthermore, we know that the sequences Rθ, and Rθ, differ at some point in the first 3h(θ) matrices, so we must end up in case (a) or case (c) at least once. For case (a), we know by Lemma 7 that the current dot-product will be multiplied by zero and O(δ) noise will be added. For case (b), we know by Lemma 2 that the current dot-product will be multiplied by one and O(δ) noise will be added. For case (c), we know by d-Desynchronization that the current dot-product will be multiplied by zero and O(δ) noise will be added. Since case (a) or (c) must occur at least once, we know that we get no signal and at most O(h(θ)δ) noise. Since each of our 23h(θ) sub-terms has a multiplier of (2wθ/wθ) on top of the dot product of x1 and x1, each term has noise bounded in magnitude (still with high probability) by O(wθ23h(θ)h(θ)δ/wθ). Summing over all objects θ, we get our final desired claim: with high probability, the total additive noise is bounded by O(23h(θ)h(θ)δ/wθ). This completes the proof. ∎
Proof Notes. Although our proofs were written as if we extracted one attribute value at a time, we can extract them simultaneously by computing the vector βRM(θ),1Ts, which is exactly a stacked version of the terms we were considering. Our technique is extendable to cases between (i) and (ii). For example, suppose we know that only one object in the overall sketch was both produced by the eye module and then subsequently used by the face module. We could recover its attributes by computing the vector βReye,1TRface,0Ts. Finally, the way we extract the attributes from the overall sketch is the same way we could extract attributes from a module sketch, meaning we do not need to know the precise sketch we are working with when attempting to extract information (although it will of course affect the error).

D.2 Proofs for Sketch-to-Sketch Similarity

Theorem 10.
Our final sketch has the Sketch-to-Sketch Similarity property, which is as follows. Suppose we have two overall sketches s and s¯. (i) If the two sketches share no modules, then with high probability they have at most O(δ) dot-product. (ii) If s has an object θ of weight wθ and s¯ has an object θ¯ of weight w¯θ and both objects are produced by the same module, then with high probability they have at least Ω(2-6h(θ)wθw¯θ¯)-O(δ) dot-product. (iii) If the two sketches are identical except that the attributes of any object θ differ by at most ϵ in 2 distance, then with probability one the two sketches are at most ϵ/2 from each other in 2 distance.
Proof.
We prove cases (i) and (ii) together. Suppose that our overall sketches are s,s¯. Then the dot-product of our sketches has the form: θθ¯wθw¯θ¯ sobject(θ)Tj=13h(θ)[(I+Rθ,jT2)] j=13h(θ¯)[(I+Rθ¯,j2)]sobject(θ¯) Our proof plan is to analyze a single term of this double-summation at a time. Fix θ and θ¯. We analyze this term with our toolkit of technical lemmas. The plan is to first understand sobject(θ),sobject(θ¯). There are two possibilities for this dot-product, depending on our two objects θ and θ¯. If these objects come from different modules, then we will want a small dot-product. If these objects come from the same module, then we will want a significant dot-product. Dot-Product Under Different Modules. Since the matrices are different, we know by Lemma 7 that with high probability, all of the following are true: |RM(θ),1xθ,RM(θ¯),1xθ¯|δ1+δ O(δ) |RM(θ),1xθ,RM(θ¯),2e1|δ1+δ O(δ) |RM(θ),2e1,RM(θ¯),1xθ¯|δ1+δ O(δ) |RM(θ),2e1,RM(θ¯),2e1|δ1+δ O(δ) Combining these statements and using the triangle inequality, we know that with high probability, |sobject(θ),sobject(θ¯)|O(δ) Dot-Product Under Same Module. Since the matrices are the same, we know by Lemma 2 that with high probability, both of the following are true: |RM(θ),1xθ,RM(θ¯),1xθ¯-xθ,xθ¯|3δ O(δ) |RM(θ),2e1,RM(θ¯),2e1-e1,e1|3δ O(δ) Also, we still know by Lemma 7 that with high probability, both of the following are true: |RM(θ),1xθ,RM(θ¯),2e1|δ1+δ O(δ) |RM(θ),2e1,RM(θ¯),1xθ¯|δ1+δ O(δ) Combining these statements with the triangle inequality, we know that with high probability, |sobject(θ),sobject(θ¯)-14xθ,xθ¯-14e1,e1|O(δ) Since attribute vectors are nonnegative, we know that: sobject(θ),sobject(θ¯)14-O(δ) We have successfully established our desired facts about the base dot-product and are now ready to consider what happens when we begin applying matrices of the form (I+R2) to both vectors in this dot product. We begin by controlling the 2 norm of the various vectors produced by gradually applying these matrices. By Lemma 1, we know that every vector of the form xJ=j=J3h(θ)[(I+Rθ,j2)]sobject(θ) where J{1,2,,3h(θ)} or of the form x¯J=j=J3h(θ¯)[(I+Rθ¯,j2)]sobject(θ¯) where J{1,2,,3h(θ¯)} has squared 2 norm at most (12+34δ)max(3h(θ),3h(θ¯))(1+δ). By our assumptions, this is upper-bounded by a constant: (12+34δ)max(3h(θ),3h(θ¯))(1+δ) (1+δ)max(3h(θ),3h(θ¯))+1 (1+1/(2H))2H e We have shown that our unit vectors maintain constant 2 norm throughout this process. This allows us to safely apply our desynchronization and isometry properties to any xJ or x¯J. From here, we plan to induct in order of decreasing depth. For homogeneity of notation, we will define xJ to be sobject(θ) when J>3h(θ) and x¯J to be sobject(θ¯) when J>3h(θ¯). We induct backwards, beginning with J=max(3h(θ),3h(θ¯))+1 and ending with J=1. In our base case, we know that these are two possibilities for xJ,x¯J. If we are in the different module case, then the magnitude of this quantity is O(δ). If we are in the same module case, then this quantity is at least 14-O(δ). To get from J to J-1, there are three possibilities. We either (a) multiply both xJ and x¯J by the same matrix, (b) multiply xJ and x¯J by different matrices, or (c) multiply only one of them by a matrix. Note that case (c) happens when one object is at a different depth than the other object, so our analysis first peels off the additional matrices to make them the same depth, then proceeds. This is an important point, because tuple matrices are only shared across the same depth. In any one of these lettered cases, we know from Lemma 3 and Lemma 4 that the distribution of the matrix(ces) is 12-leaky O(δ)-Desynchronizing and 12-scaled O(δ)-Isometric. In case (a), we apply Lemma 2 to show that with high probability, the new dot product is 12 times the old dot product plus O(δ) additive noise. In case (b), we apply Lemma 7 to show that with high probability, the new dot product is 14 times the old dot product plus O(δ) additive noise. In case (c), we use the fact that our distribution is 12-leaky O(δ)-Desynchronizing to show that the new dot product is 12 times the old dot product, plus O(δ) additive noise. Hence, if the objects were produced by different modules, then we begin with O(δ) noise and at every step we reduce by at least a factor of 12 before adding O(δ) noise. The total noise telescopes into O(δ) total. If the objects were produced by the same module, then we begin with at least 14 signal and O(δ) noise. The noise sums as before into O(δ) total, and the signal falls by at most 14 per step, resulting in a final signal of Ω(2-6h(θ)). However, our original term under consideration was actually a scaled version of what we just analyzed: wθw¯θ¯x1Tx¯1. Hence in the different module case, there is O(wθw¯θ¯δ) noise, and in the same module case there is Ω(2-6h(θ)wθw¯θ¯) signal and O(wθw¯θ¯δ) noise. Hence for case (i) which we were originally trying to prove, since the effective weights wθ sum to one and the effective weights w¯θ¯ sum to one, we wind up, with high probability, at most O(δ) total noise, as desired. For case (ii) which we were originally trying to prove, we get at least Ω(2-6h(θ)wθw¯θ¯)-O(δ) dot product. We conclude by proving case (iii). Suppose that in sketch s¯, the attributes of θ are xθ+ϵθ, where ||ϵθ||2ϵ for all objects θ. Let’s write the difference between the two sketches. s¯-s =θwθj=13h(θ)[(I+Rθ,j2)]12RM(θ),1ϵθ Applying Lemma 4, we know that (I+R2) is 12-scaled 34δ-Isometric. Repeatedly applying Lemma 2, we can conclude that with high probability: ||j=13h(θ)[(I+Rθ,j2)]RM(θ),114ϵθ||22 (12+34δ)3h(θ)(1+δ)14ϵ2 (12+38)3h(θ)+114ϵ2 14ϵ2 Taking the square root of the above and applying the triangle inequality yields the following. ||s¯-s||2 θwθ12ϵ 12ϵ This completes the proof of case (iii). ∎

D.3 Proofs for Summary Statistics

Theorem 11.
Our final sketch has the Summary Statistics property, which is as follows. Consider a module M which lies at depth h(M), and suppose all the objects produced by M has the same effective weight w. (i) Frequency Recovery. We can produce an estimate of the number of objects produced by M. With high probability, our estimate has an additive error of at most O(23h(M)δ/w). (ii) Summed Attribute Recovery. We can produce a vector estimate of the summed attribute vectors of the objects produced by M. With high probability, our estimate has additive error of at most O(23h(M)δ/w) in each coordinate.
Proof.
Let the overall sketch be s. We begin by proving case (i). As we did in case (ii) of Attribute Recovery, let β=23h(M)+1/w. We compute βe1TRM,1Ts, which has the form: θβwθe1TRM,2Tj=13h(θ)[(I+Rθ,j2)]sobject(θ) There are two types of terms in this sum: those objects produced by M, and those that are not. Consider some object θ produced by M. When θ=θ, we get the term: 23h(θ)+1e1TRM,2Tj=13h(M)[(I+Rθ,j2)]sobject(θ) If we expand out each transparent matrix, we would get 23h(M) sub-terms. Again, focus on the sub-term where we choose I/2 every time: 2e1TRM,2T[12RM,1xθ+12RM,2e1] By the δ-Isometry property of our distribution, we know that with high probability (note e1 is a unit vector): |2e1TRM,2T×12RM,2e1-e1Te1|δ This half of the sub-term (up to additive error O(δ)) contributes one to our estimate, representing one copy of an object produced by M. We control the other half of the sub-term using Lemma 7: |2e1TRM,2T×12RM,1xθ|δ1+δ=O(δ) Next, we bound the additive error from the other sub-terms of such a term θ. These other sub-terms have the form: 2e1TRM,2TR~sobject(θ) where R~ is a product of one to 3h(M) R matrices. As before, we apply Lemma 1 so that with high probability sobject(θ) and RM,2e1 have squared 2 norm at most (1+δ), and then conclude using Lemma 5 that the distribution of R~ satisfies O(δ)-Desynchronization (this was the worst case). Hence with high probability the absolute value of any other sub-term was bounded by O(δ), and the absolute value of the sum of the other sub-terms for θ is bounded by O(23h(M)δ). There are at most 1/w such objects, so the total error from these terms is O(23h(M)δ/w), as desired. It remains to show that the total error from the other terms is also O(23h(M)δ/w). These other terms have the form: βwθe1TRM,2Tj=13h(θ)[(I+Rθ,j2)]sobject(θ) We prove this using the δ-Desynchronization of RM,2. To do so, we will need to bound the 2 length of sobject(θ) as it gets multiplied by this sequence of matrices. As before, we use Lemma 4 to know that the distribution of these matrices is 12-scaled (34δ)-Isometric, and then repeatedly apply Lemma 6 to conclude that the squared 2 length is upper bounded by a constant. Hence the δ-Desynchronization of RM,2 implies that with high probability the absolute value of the term indexed by θ is at most O(βwθδ). Hence the absolute value of all other terms is at most O(βδ). Plugging in our choice of β, it is at most O(23h(M)δ/w), as desired. We have finished proving case (i); with high probability, we can recover the number of objects produced by module M, with the desired additive error. We now prove case (ii). We do exactly what we did in case (i), except that instead of computing βe1TRM,2Ts we compute βejTRM,1T. Instead of operating on the first coordinate of the e1 in our object sketch, we now operate on the jth coordinate of the xθ in our object sketch, and hence we can recover the jth coordinate of the sum of the attribute vectors of the appropriate objects to the same error as in case (i). ∎
Proof Notes. As when we were reasoning about the Attribute Recovery property, we can simultaneously extract the entire summed attribute vector at the same time by computing the vector βRM,1Ts. Additionally, we focus on more precise groups of objects than all those output by a particular module. For example, if we cared about objects produced by the eye module and then subsequently used by the face module, we could recover their approximate frequency and summed attribute vector by computing βe1TReye,2TRface,0Ts and βReye,1TRface,0Ts.

D.4 Generalizing for Object Signature Recovery

In this subsection, we explain how to also satisfy the Object Signature Recovery property through a small modification to our sketch. The key idea is that each object is given a “magic number” based on its attributes: mθ is a random (logN)-sparse unit vector whose entries are in {0,1logN}. We revise the sketch of object θ to be 13RM(θ),1xθ+13RM(θ),2e1+13RM(θ),3mθ. The process of recovering an object signature is the same as recovering its attribute vector, except that the signature is quantized and therefore as long as the additive error is less than 12logN, we can recover it exactly.

D.5 Generalizing for Graceful Erasure

In this subsection, we explain how to generalize our previous proofs for the Graceful Erasure property. We will need to better understand the behavior of our matrices when only a prefix of the result is considered. We can extend our definitions as follows:
Definition 4.
We say that a distribution D over random d𝑠𝑘𝑒𝑡𝑐ℎ×d𝑠𝑘𝑒𝑡𝑐ℎ matrices satisfies the dDE-prefix αDE-leaky δDE-Desynchronization Property if the following is true. If RD, then the random variable Z=i=1dDE(Rx)i(y)i-αDEx,y is a δDE-nice noise variable. If αDE=0 then we simply refer to this as the dDE-prefix δDE-Desynchronization Property.
Definition 5.
We say that a distribution D over random d𝑠𝑘𝑒𝑡𝑐ℎ×d𝑠𝑘𝑒𝑡𝑐ℎ matrices satisfies the dIE-prefix αIE-leaky δIE-Isometry Property if the following is true. If RD and x=y, then the random variable Z=i=1dIE(Rx)i2-αIEx,x is a δIE-nice noise variable. If αIE=1 then we simply refer to this as the dIE-prefix δIE-Isometry Property.
The next step is to extend our technical lemmas to reason about these prefixes. For example, we will again want to instead compare i=1dIE(Rx)i(Ry)i and x,y instead, so Lemma 2 turns into the following:
Lemma 8.
If D satisfies the dIE-prefix αIE-leaky δIE-Isometry Property, then the random variable Z=i=1dIE(Rx)i(Ry)i-αIEx,y is a (3δIE)-nice noise variable.
Proof.
The proof is the same idea as before. The claim is trivially true if x or y is zero, and then without loss of generality we scale them to unit vectors. We invoke the dIE-prefix αIE-leaky δIE-Isometry Property three times, on x1=x+y, x2=x, and x3=y. This implies that the following three noise variables are dIE-nice: Z1 =i=1dIE(R(x+y))i2-αIEx+y,x+y Z2 =i=1dIE(R(x))i2-αIx,x Z3 =i=1dIE(R(y))i2-αIy,y By construction, Z=12Z1-12Z2-12Z3, so Z is centered. We bound it by noting that ||x+y||224. We know that with high probability, |Z1|4δIE, |Z2|δIE, and |Z3|δIE. By the triangle inequality, Z is (3δIE)-bounded, making it a (3δIE)-noise variable and completing the proof. ∎
Using extended technical lemmas, it is possible to generalize our various properties to the case where we only have a prefix of the sketch. For example, the following claim generalizes case (i) of the Attribute Recovery property.
Claim 6.
Suppose we have an overall sketch s and we keep only a d𝑠𝑘𝑒𝑡𝑐ℎd𝑠𝑘𝑒𝑡𝑐ℎ prefix of it, s. Consider an object θ which lay at depth h(θ) and had effective weight wθ in the original sketch s. Suppose no other objects in s are also produced by M(θ). We can produce a vector estimate of the attribute vector xθ from s, which with high probability has an additive error of at most O(23h(θ)δE/wθ) in each coordinate.
Proof Sketch.
We have an overall sketch s and a version s where the last (dsketch-dsketch) coordinates have been replaced with zeros. We compute βejTRM(θ),1Ts. From our proof of case (i) of Theorem 9, there are three things to analyze: the primary signal sub-term, the other sub-terms, and the other terms. The primary signal sub-term is now the following. i=1dsketch[(12RM(θ),1xθ+12RM(θ),2e1)i(2RM(θ),1ej)i] Using dsketch-prefix isometry, we can show that the first half is a (scaled-down) of ejTxθ plus (scaled-down) small noise. Using a generalization of Lemma 7, we can show that the second half is (scaled-down) small noise. When analyzing the other sub-terms, we use the dsketch-prefix desynchronization of the final matrix in R~ to show the the sub-term is just (scaled-down) small noise. Finally, when analyzing the other terms, we use the dsketch-prefix desynchronization of RM(θ),1 to show that the term is just (scaled-down) small noise. ∎

Appendix E Proofs for Dictionary Learning

E.1 Proof of Network Learnability

In this subsection, we prove Theorem 5. Recall Theorem 5: See 5
Proof.
Our plan is to use Theorem 4 to unwind our sketching. Precisely, we invoke it with N as thrice the maximum between the number of modules and the number of objects in any communication graph, S~ as (α/β)logN=poly(N), H as three times the depth of our modular network, and ϵH as min(ϵ/4,1/4)2-Hw. This yields a sketch dimension dsketchpoly(1/ϵH)logNlogpoly(N) which is poly(1/w,1/ϵ)log2N as claimed. Additionally, it yields a base number of samples S=poly(N) and a sequence of errors ϵ1ϵ2ϵH-1ϵH. These are guarantees on an algorithm A which accepts an h[3 network depth] as well as Sh=SNh-1 samples with up to ϵh error and O(dsketch) 1 error. This base number of samples is why we will require poly(N) overall sketches. By construction, overall sketches are just input subsketches of the output psuedo-object. We know that no communication graph contains more than N/3 objects by the definition of N, so we can write all the overall sketches in the form: soverall=i=1Nxi+Rixi where xi is (wi/2)sobject(θi) if there actually was an ith input and the zero vector otherwise. We want to treat ixi as 1 noise, but how much do they contribute? We can only tolerate them contributing at most O(dsketch) 1 norm. In fact, we claim that any sketch vector has at most O(1) 2 norm, which would imply the desired statement by Cauchy-Schwartz and noticing that we are taking a convex combination of sketch vectors. We prove an 2 bound on sketch vectors as in Appendix D, but roughly the idea is that our error parameter δ, which we know to be O(logNdsketch), needs to be less than the constant 18H (recall that our network depth is constant). Since our sketch dimension already scaled with log2N, this is true up to making our sketch dimension a constant factor larger. We actually have no additional noise, which is under the ϵ1 requirement. Hence, we can safely apply A and retrieve (wi/2) times our object sketches (and some zero vectors), up to ϵ2 noise. Note that we now have a total of S~N vectors, since the procedure turns one vector into N vectors. If any of our retrieved vectors have less than ϵ2 norm, we declare them garbage and any further vectors that dictionary learning recovers from them as garbage. When learning modules, we will not use any garbage vectors. Now, we have several approximate, scaled object sketches and several garbage vectors. We note that the scaled object sketches, by definition, are of the form: wsobject(θ)=w(I+RM(θ),02)x  (+MM(θ)RM,00) where w is some weight from the previous step and x is w times a tuple sketch. Undoing the first matrix off an object sketch is exactly like the previous step; we handle the transparent matrix by noting that all sketches have constant 2 norm with high probability and hence it’s a matter of 1 noise for our algorithm. Our ϵ2 noise turns into ϵ3 noise. The garbage vectors can be thought of as noise plus the zero vector, which also decomposes nicely: 0=MRM,00 so the dictionary learning procedure can safely handle them. There are at most N/3 matrices involved (we can imagine the problem as padded with zero matrices and additional zero vectors). We recover S~N2 vectors, which are attribute subsketches, input subsketches, and garbage vectors. The process of undoing attribute subsketches and input subsketches is why we need N to be thrice the maximum between the number of modules and the number of objects in any communication graph. For attribute subsketches, there are up to two matrices for every module at this depth. For input subsketches, there is possibly a tuple matrix for every object at this depth. Still, there are at most N matrices involved, so we can recover our S~N3 vectors, which are object attribute vectors, e1’s, object sketches, and garbage vectors. Unlike previous steps, where we had one type of vector (and garbage vectors), we now have three types of vectors that we want to distinguish; we can only recurse on object sketches because we cannot guarantee that object attribute vectors or e1 can be written as the correct matrix-vector product form. We can get some helpful information by looking at which vectors produced which vectors in our dictionary learning procedure. By construction, we know that one object sketch gets turned into an attribute subsketch and an input subsketch. The former gets turned into an attribute vector and e1 while the latter gets turned into a series of object sketches. For example, if the input subsketch produces at least three non-garbage vectors, then we know which subsketch was which (the attribute subsketch only produces up to two non-garbage vectors with high probability). Of course, this idea won’t help us distinguish in general; an object might only have two input objects! The better test is to see which subsketch produces a vector that looks more like e1. To begin with, it’s worth noting that the two subsketches have the same scaling: the effective weight of object θ, wθ, times 2-2h(θ)+2. Now, let’s consider how small the first coordinate of the (scaled) e1 vector can be. It picks up an additional 1/2 scaling factor, so the vector we recover is wθ2-2h(θ)+1e1 up to ϵ3h(θ)-2 additional error. We know that ϵ3h(θ)-2<ϵH<w2-H, so the first coordinate is at least: wθ2-2h(θ)+1-w2-H Now, let’s consider how large the first (or any) coordinate of any object sketch could be. Due to Theorem 7, we know that any (at most unit in length) vector has a first coordinate of at most O(logNdsketch) after one of our block random matrices is applied to it. Furthermore, applying the various transparent matrices (I+R2) throughout our sketch increases this by at most a constant factor. The object sketch is just a convex combination of such vectors, so it also has at most O(logNdsketch) in its first coordinate. Since there is up to w2-H additional error in the recovery process and this vector is scaled too, we know that the recovered object sketch vector has first coordinate at most: wθ2-2h(θ)+2O(logNdsketch)+w2-H We require that O(logNdsketch)<18. As already discussed, since our sketch dimension already scaled with log2N, this amounts to making the sketch dimension at most a constant factor larger. Now, our recovered object sketch vector has first coordinate at most: wθ2-2h(θ)+1/4+w2-H Whether our two cases are distinguishable still depends on how θ’s effective weight wθ relates to the goal weight w. We could clearly distinguish the two if wθ2-2h(θ)+1 was at least 4w2-H, since then the first case would yield a value of at least 3w2-H and the second case a value of at most 2w2-H. Hence our test is the following: if some vector produced by the object sketch has a first coordinate of at least 3w2-H, then take the one with the largest first coordinate and decide that it was produced by the object attribute subsketch. If no vector produced by the object sketch has a first coordinate of at least 3w2-H, then swap them all for zero vectors and declare them garbage. Notice that if a recovered object sketch vector manages to have a first coordinate value of at least 3w2-H, then we know that wθ2-2h(θ)+1 is at least 8w2-H and hence the scaled e1 still beats all the recovered object sketch vectors. On the other hand, all the vectors are declared garbage, then we know that wθ2-2h(θ)+1<4w2-H and hence wθ<w (i.e. we don’t need to recover this object or any of its children). Hence our procedure works and we can continue to safely recurse. The result of this procedure is that for each module (we can tell which vectors belong to which modules due to shared final matrices) we recover unordered pairs of scaled (attribute vector, e1), at least every time the module produces an object with at least w weight (possibly more). We’ll consider the one with larger first coordinate to be e1, and divide the other vector by the first coordinate of e1 to unscale it. Note that both vectors have been scaled by wθ2-2h(θ)+1 and then face at most ϵH additional noise. note that we chose a ϵH<(ϵ/4)2-Hw and no vector could have passed our test unless wθ2-2h(θ)+12w2-H, i.e. w/wθ2H-2h(θ). Combining these facts, we know that a single instance of the noise messes up any (unscaled) coordinate by at most: 22h(θ)-1ϵH/wθ 22h(θ)-1(ϵ/4)2-Hw/wθ 22h(θ)-1(ϵ/4)2-H2H-2h(θ) =(ϵ/8) There are two cases: (i) we consider the correct vector to be e1 and (ii) we consider the object attribute vector to be e1. In case (i), our object attribute vector is scaled by a number which is within a multiplicative (1±ϵ/8) of correct. Additionally, its noise makes it off by an additive ϵ/8 in distance. Since we capped ϵ to be at most one, the multiplicative difference is at most (9/8)/(1-ϵ/8)-9/8956ϵ, for a total difference of 27ϵ distance. In case (ii), the original attribute vector had to have first coordinate at least 1-(ϵ/4). Since it has an 1 norm of at most one, we know that it is at most ϵ/4 in distance from e1. We imagine that the noised version of e1 is it; by triangle inequality this choice is at most 38ϵ from it. We again pick up at most a 956ϵ error from incorrect scaling, for a total of at most 1528ϵ error. We conclude the proof of the first half of our theorem by noting that since we started with (α/β)logN samples, with high probability we will have at least α samples where we recover an input/output pair for M within the robust module learnability conditions. Regarding fixed communication graphs, we can use this same algorithm to detect the entire path to an object with high probability (i.e. what modules produce each node along the path) if the object has effective weight w along this path. This means we can identify the entire sub-graph of objects which have effective weight w “often enough”. ∎

E.2 Proof of Recursable Dictionary Learning

In this subsection, we prove Theorem 4, which we restate next. See 4 We point out that the bound on the recovery error in Theorem 4 implies that the x vectors can be recovered exactly if they are quantized and the recovery error ϵh+1 is small enough.

Notation.

We next provide some notation that will be used in the proof of Theorem 4. Let H be a given positive constant and let Spoly(N) be a base number of samples. Fix h[H-1] and let Sh=SNh-1. For each sample index i[Sh], we divide the dsketch-dimensional real vector y(i) into dsketch/b contiguous blocks each of length b, with the th block being y(i)[(-1)b+1:b+1] for each [dsketch/b]. For any two points x,yn, recall that their -distance is defined as d(x,y):=y-x=maxi[n]|yi-xi|. Moreover, we define the symmetric -distance between x and y as min(d(x,y),d(x,-y)). For any vector yn and any finite subset L of n, we denote the -distance of y from L by d(y,L):=minxLy-x. If this distance is at least τ, then we say that y is τ-far in -distance from the set L. For any y,yn, we define their Hamming distance as Δ(y,y):=|{j[n]:yjyj}| and the symmetric Hamming distance as Δ¯(y,y)=min(Δ(y,y),Δ(y,-y)).

Algorithm.

Analysis.

Theorem 4 follows from Theorem 12 below which proves the guarantees on the operation of Algorithm 5.3.
Theorem 12 (Guarantees of Algorithm 5.3).
Let b, q and d𝑠𝑘𝑒𝑡𝑐ℎ satisfy b𝑝𝑜𝑙𝑦(logN,logd𝑠𝑘𝑒𝑡𝑐ℎ,1/ϵH), q𝑝𝑜𝑙𝑦(logN,logd𝑠𝑘𝑒𝑡𝑐ℎ,1/ϵH)/d𝑠𝑘𝑒𝑡𝑐ℎ, and d𝑠𝑘𝑒𝑡𝑐ℎ𝑝𝑜𝑙𝑦(1/ϵH,logN,logS). For any unknown vectors x(1),,x(Sh)Rd𝑠𝑘𝑒𝑡𝑐ℎN with 2-norm at most O(1), if we draw R1,,RND(b,q,d𝑠𝑘𝑒𝑡𝑐ℎ) and receive Sh noisy samples y(k)[R1R2RN]x(k)+z1(k)+z(k) where each z1(k)Rd𝑠𝑘𝑒𝑡𝑐ℎ is noise with ||z1(k)||1O(d𝑠𝑘𝑒𝑡𝑐ℎ) (independent of our random matrices) and each z(k)Rd𝑠𝑘𝑒𝑡𝑐ℎ is noise with ||z(k)||ϵh (also independent of our random matrices), then Algorithm 5.3, taking as inputs h, y(1), , y(Sh), and thresholds τ1=Θ(ϵh+1qd𝑠𝑘𝑒𝑡𝑐ℎ) and τ2=Θ(ϵh+12), runs in time 𝑝𝑜𝑙𝑦(Sh,d𝑠𝑘𝑒𝑡𝑐ℎ) and outputs matrices R^1,,R^NRd𝑠𝑘𝑒𝑡𝑐ℎ×d𝑠𝑘𝑒𝑡𝑐ℎ and vectors x^(1),,x^(Sh)Rd𝑠𝑘𝑒𝑡𝑐ℎN that, with high probability, satisfy the following for some permutation π of [N]: Matrix Recovery: For every column (i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j of the matrix [R1R2RN] (where i[N] and j[d𝑠𝑘𝑒𝑡𝑐ℎ]) for which there exists a sample index k[Sh] such that |x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1, the jth column of R^π(i) is 0.2d𝑠𝑘𝑒𝑡𝑐ℎ-close in Hamming distance to the jth column of Ri. Moreover, all the other columns of R^π(i) are zero. Input Recovery: For each i[N] and j[d𝑠𝑘𝑒𝑡𝑐ℎ], it is guaranteed that |x^(π(i)-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)-x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1.
We now define the permutation π of [N] that appears in the statement of Theorem 12. For each i[N], we let π(i) be the first index i* set in line 5.3 of Algorithm 5.3 for which σ^i*,m is 10ϵh+1-close in Hamming distance to σ^i,m. If no such i* exists, we define π(i) in an arbitrary way that doesn’t result in a collision. {algorithm} [H] Dec(z¯c) \[email protected]@algorithmic[1] \STATEInput: A vector z¯c on the hypercube {±1qdsketch}b/3.
\STATEOutput: A pair (j,f) where j is an index in [dsketch] and f is a sign.
\[email protected] \IFthe first coordinate of z¯c is negative \STATENegate each coordinate of z¯c. \ENDIF\STATESet t to log2dsketch. \STATELet σc be the binary vector obtained from z¯c[2:t+2] by replacing -1qdsketch by 0 and +1qdsketch by 1. \STATELet j be the non-negative integer whose binary representation is σc. \STATEIncrement j by 1. \STATESet f to the sign of z¯c[t+2]. \RETURN(j,f). {algorithm}[H] Recursable Dictionary Learning \[email protected]@algorithmic[1] \STATEInput: Positive integer h, observations y(1),,y(Sh) and thresholds τ1 and τ2. \STATEOutput: Matrices R^1,,R^Ndsketch×dsketch and vectors x^(1),,x^(Sh)dsketchN.
\[email protected] \FOReach sample index k[Sh] \FOReach block index [dsketch/b] \STATELet wk, be the product of q/b and the 1-norm of the th block of y(k). \IFwk, is not zero \STATELet zk, be the coordinate-wise normalization of the th block of y(k) by wk,. \STATELet zk,,s, zk,,c and zk,,m be the first, middle and last b/3 coordinates of zk, respectively. \ENDIF\ENDFOR\ENDFOR\STATEInitialize n to zero, R^1,,R^N to the all-zeros matrices and x^(1),,x^(Sh) to the all-zeros vectors. \FOReach i[N] \STATELet σ^i,m be a vector in {±1qdsketch}b/3 that is initialized arbitrarily. \ENDFOR\FOReach sample index k[Sh] \FOReach block index [dsketch/b] \IFwk, is zero \STATEcontinue \ENDIF\IFthe th block of y(k) has a coordinate whose absolute value is smaller than τ1 or larger than 2qdsketch \STATEcontinue \ENDIF\IFzk,,s is τ2-far in -distance from the hypercube {±1qdsketch}b/3 \STATEcontinue \ENDIF\STATELet Sk, be the set of all block indices [dsketch/b] for which wk, is non-zero, all the coordinates of the th block of y(k) are between τ1 and 2qdsketch and zk,,s is 2τ2-close in symmetric -distance to zk,,s. \IFthe cardinality of Sk, is less than (0.9)3qdsketch \STATEcontinue \ENDIF\STATELet z¯k, be the coordinate-wise rounding of zk, to the hypercube {±1qdsketch}b. \STATELet z¯k,,s, z¯k,,c, z¯k,,m be the most common first, middle and last b3 coordinates of {z¯k,:lSk,} respectively. \IFthere is i[n] such that σ^i,m is 0.01b-close in symmetric Hamming distance to z¯k,,m \STATESet i* to i. \ELSE\STATEIncrement n by 1 and set i* to the new value of n. \STATESet σ^i*,m to the matrix signature z¯k,,m. \ENDIF \STATE Let (j,f)=Dec(z¯k,,c) be the decoded column index and sign respectively. \IFthe sign of the first coordinate of z¯k,,m is the opposite of f \STATENegate wk, and each coordinate of z¯k,. \ENDIF\IFR^i*[:,j] is the all-zeros vector \FORSk, \STATESet R^i*[(-1)b+1:b+1,j] to z¯k,. \ENDFOR\ENDIF\STATESet x(i*-1)dsketch+j(k) to wk,. \ENDFOR\ENDFOR\RETURNR^1,,R^N and x^(1),,x^(Sh). Theorem 12 directly follows from Lemmas 9 and 10 below, applied in sequence. We point out that for simplicity of exposure, we chose large constants (which we did not attempt to optimize) in Lemmas 9 and 10.
Lemma 9.
For every absolute positive constant t and every given positive real number ϵh+1 satisfying ϵh+11d𝑠𝑘𝑒𝑡𝑐ℎ1/ζ where ζ is any positive constant, for any sufficiently large b satisfying b=Θ(logN+logd𝑠𝑘𝑒𝑡𝑐ℎ+logShϵh+12) and any sufficiently large q satisfying q=Θ(logN+logd𝑠𝑘𝑒𝑡𝑐ℎ+logShϵh+12d𝑠𝑘𝑒𝑡𝑐ℎ), for ϵh=Θ(ϵh+1c) where c is a sufficiently large positive constant, with probability at least 1-N-t, the following holds during the operation of Algorithm 5.3: Whenever i* is set in lines 5.3-5.3, then σ^i*,m is 0.001b-close in Hamming distance to the matrix signature σπ(i*),m. If moreover j is set in line 5.3, then the jth column of R^i* is ϵh+1d𝑠𝑘𝑒𝑡𝑐ℎ4-close in Hamming distance to the jth column of Rπ(i*). If furthermore line 5.3 is executed, then |x(π(i*)-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)-x(i*-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1.
Lemma 10.
For every absolute positive constant t and every given positive real number ϵh+1 satisfying ϵh+11d𝑠𝑘𝑒𝑡𝑐ℎ1/ζ where ζ is any positive constant, for any sufficiently large b satisfying b=Θ(logN+logd𝑠𝑘𝑒𝑡𝑐ℎ+logShϵh+12) and any sufficiently large q satisfying q=Θ(logN+logd𝑠𝑘𝑒𝑡𝑐ℎ+logShϵh+12d𝑠𝑘𝑒𝑡𝑐ℎ) and for ϵh=Θ(ϵh+1c) where c is a sufficiently large positive constant, the following holds. With probability at least 1-N-t, for all k[Sh], i[N] and j[d𝑠𝑘𝑒𝑡𝑐ℎ]: If |x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1, the jth column of R^π(i) is 0.2d𝑠𝑘𝑒𝑡𝑐ℎ-close in Hamming distance to the jth column of Ri. It is the case that |x^(π(i)-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)-x(i-1)d𝑠𝑘𝑒𝑡𝑐ℎ+j(k)|ϵh+1.

Proof Preliminaries.

To prove Lemma 9, we need the next two known theorems and the following two lemmas. Theorem 13 below provides asymptotically tight bounds on the expected moments of a linear combination of independent uniform Bernouilli random variables.
Theorem 13 (Khintchine Inequality).
Let {ϵn:n[N]} be i.i.d. random variables with Pr[ϵn=+1]=Pr[ϵn=-1]=1/2 for each n[N], i.e., a sequence with Rademacher distribution. Let 0<p< and let x1,x2,,xNR. Then, there exist positive absolute constants Ap and Bp (depending only on p) for which Ap(n=1Nxn2)1/2(𝔼|n=1Nϵnxn|p)1/pBp(n=1Nxn2)1/2.
The well-known Markov’s inequality allows us to lower-bound the probability that a non-negative random variable is not much larger than its mean. The next theorem allows us to lower-bound the probability that a non-negative random variable is not much smaller than its mean, provided that the random variable has finite variance.
Theorem 14 (Paley-Zygmund Inequality).
If Z0 is a random variable with finite variance and if 0θ1, then Pr[Z>θ𝔼[Z]](1-θ)2𝔼[Z]2𝔼[Z2].
We will also need the following two lemmas.
Lemma 11 (Separation Lemma).
Let v be a positive real number. Let X and Y be two random variables that are symmetric around 0 and such that the absolute value of each of them is larger than v with probability at least α. Then, there exist real numbers a1<a2<a3<a4 satisfying min(a2-a1,a3-a2,a4-a3)v and such that the sum X+Y lies in each of the intervals (-,a1], [a2,a3] and [a4,+) with probability at least α/4.
We will use the following multiplicative version of the Chernoff bound.
Theorem 15 (Chernoff Bound – Multiplicative Version).
Suppose X1,,Xn are independent random variables taking values in {0,1}. Let X:=i[n]Xi and let μ=E[X]. Then, For all 0δ1, Pr[X(1-δ)μ]e-δ2μ/2. For all δ0, Pr[X(1+δ)μ]e-δ2μ/(2+δ).
Proof of Lemma 11.
Define mX,- and mX,+ to be the medians of the negative and positive parts (respectively) of the random variable X conditioned on |X|>v (note that mX,-=-mX,+ although we will not be using this fact in the proof). Similarly, define mY,- and mY,+ to be the negative and positive parts (respectively) of the random variable Y conditioned on |Y|v. Setting a1=mX,-+mY,-, a2=mX,-+v, a3=mY,+-v, and a4=mX,++mY,+, the statement of Lemma 11 now follows. ∎
We are now ready to prove the correctness of Algorithm 5.3.

Proof of Lemma 10.

Fix k[Sh], i[N] and j[dsketch], and assume that |x(i-1)dsketch+j(k)|ϵh+1. For each [dsketch/b], we consider the random vector errk,i,,j :=i[N],j[dsketch]:ii or jjx(i-1)dsketch+j(k)Ri[(-1)b+1:b+1,j] +z(k)[(-1)b+1:b+1]+z1(k)[(-1)b+1:b+1]. We think of the b-dimensional real vector errk,i,,j as containing the coordinate-wise errors incurred by estimating x(i-1)dsketch+j(k)Ri[(-1)b+1:b+1,j] from the th block of y(k). Let Tk,i,j be the set of all block indices [dsketch/b] for which ηi,,j=1 and z1(k)[(-1)b+1:b+1]O(bdsketch). By an averaging argument, the Chernoff Bound (Theorem 15) and the union bound, we have that for every fixed k[Sh], i[N] and j[dsketch], with probability at least 1-e-0.005qdsketchb, it is the case that |Tk,i,j|>0.9qdsketchb. Henceforth, we condition on a setting of {ηi,,j:[dsketch/b]} for which |Tk,i,j|>0.9qdsketchb. We will upper-bound the probability, over the randomness of {ηi,,j:i[N],j[dsketch], such that ii or jj}, that the -norm of the random vector errk,i,,j is large, and then we will show, by again applying the Chernoff Bound (Theorem 15), that for at least a 0.9-fraction of the ’s in Tk,i,j, the -norm is small. We have that errk,i,,j |i[N],j[dsketch]:ii or jjx(i-1)dsketch+j(k)Ri[(-1)b+1:b+1,j]|+ϵh+O(bdsketch) :=ϵk,i,,j, where the first inequality above uses the assumption that z(k)ϵh. By the desynchronization property (Section B.2), the fact that the 2-norm of x(k) is guaranteed to be at most O(1) for all k[Sh], and the assumptions that qblogNdsketch and blogN, the expected value of ϵk,i,,j satisfies 𝔼[ϵk,i,,j] ϵh+O(bdsketch). By Markov’s inequality, we get that with probability at least 0.9, it is the case that ϵk,i,,j10ϵ1+O(bdsketch). (1) Since the random variables in the set {ϵk,i,,j:Tk,i,j} are independent, the Chernoff Bound (Theorem 15) implies that with probability at least 1-e-0.120.9|Tk,i,j|/21-e-0.004qdsketchb, for at least a (0.9)2-fraction of the ’s in Tk,i,j, it is the case that ϵk,i,,j satisfies Equation (1) and hence errk,i,,j10ϵh+O(bdsketch). For each of these values of , the block (k,) will fail the tests in lines 5.3 and 5.3 of Algorithm 5.3 as long as ϵh+1qdsketch-10ϵh-O(bdsketch)>τ1. (2) Moreover for each of these values of , the block (k,) will fail the test in line 5.3 of Algorithm 5.3 as long as 10ϵh+O(bdsketch)ϵh+1qdsketch-10ϵh-O(bdsketch)<τ2. (3) Furthermore for each of these values of , we will also have that |Sk,|>(0.9)3qdsketchb (as long as Equation (2) above holds) and hence the block (k,) will fail the test in line 5.3 of Algorithm 5.3. Thus, the block (k,) fails the tests in lines 5.3, 5.3, 5.3 and 5.3 of Algorithm 5.3 with probability at least 1-2e-0.004qdsketchb as long as Equations (2) and (3) above hold. In this case, a vector that is at a (symmetric relative) Hamming distance of at most 0.1 from rm,j will be added to the set of atoms (if no such vector was already present in the set). Moreover, the value of x(i-1)dsketch+j(k) will be recovered up to an absolute error of ϵh+1 as long as 10ϵh+O(bdsketch)ϵh+1qdsketch-10ϵh-O(bdsketch)<ϵh+1. (4) By a union bound, we get that with probability at least 1-2ShdsketchNe-0.004qdsketchb, the above recovery guarantees simultaneously hold for all k[Sh] and all i[N] and j[dsketch] for which |x(i-1)dsketch+j(k)|ϵh+1. This probability is at least the desired 1-N-t in the statement of Lemma 10 as long as 2ShdsketchNe-0.004qdsketchb<N-t. (5) Finally, we note that Equations (2), (3), (4) and (5) above are all simultaneously satisfied (assuming that t is a given positive absolute constant) if we let c be a sufficiently large positive constant and set τ1=Θ(ϵh+1qdsketch),  any τ2=Θ(ϵh+12), ϵh=Θ(ϵh+1c), b=Θ(logN+logdsketch+logShϵh+12), and q=Θ(logN+logdsketch+logShϵh+12dsketch), where b and q are sufficiently large.

Proof of Lemma 9.

We start by considering the special case where the “1 error” z1(k) is zero (for all k[Sh]). We will later generalize the proof to the case where we only assume that ||z1(k)||1O(dsketch). For each k[Sh] and [dsketch/b], we define x(k,)Ndsketch by setting x(i-1)dsketch+j(k,)=x(i-1)dsketch+j(k)𝟙[ηi,,j=1] for each i[N] and j[dsketch]. For each coordinate u[b], we consider the scalar random variable |y(k)[(-1)b+u]|=|i[N],j[dsketch]x(i-1)dsketch+j(k,)Ri[(-1)b+u,j]+z(k)[(-1)b+u]|. Let λ1 be a real parameter to be specified later. If x(k,)2ϵh+1/λ, then for each u[b/3], Khintchine’s Inequality (Theorem 13) with p=1, along with the fact that z(k)ϵh, imply that 𝔼[|y(k)[(-1)b+u]|] B2qdsketch(i[N],j[dsketch](x(i-1)dsketch+j(k,))2)1/2+ϵh B2ϵh+1λqdsketch+ϵh, where B2 is a positive absolute constant. By Markov’s inequality, we get that Pr[|y(k)[(-1)b+u]|>10B2ϵh+1λqdsketch+10ϵh]0.1. Since the coordinates u[b/3] are independent, the probability that all of them satisfy |y(k)[(-1)b+u]|>10B2ϵh+1/(λqdsketch)+10ϵh is at most (0.1)b/3. Thus, the probability that block (k,) will pass the test in line 5.3 of Algorithm 5.3 is at least 1-(0.1)b/3 as long as 10B2ϵh+1λqdsketch+10ϵh<τ1. (6) By a union bound, we get that with probability at least 1-Shdsketchb(0.1)b/3, (7) for all k[Sh] and all [dsketch/b] for which x(k,)2ϵh+1/λ, block (k,) will pass the test in line 5.3 of Algorithm 5.3. Henceforth, we assume that x(k,)2>ϵh+1/λ. Assume moreover that for all i[N] and j[dsketch] for which ηi,,j=1, it is the case that (x(i-1)dsketch+j(k))2gi[N],j[dsketch]:ii or jj(x(i-1)dsketch+j(k))2𝟙[ηi,,j=1], (8) where g>1 is an absolute constant to be specified later. Equation (8) is equivalent to saying that for all i[N] and j[dsketch], (x(i-1)dsketch+j(k,))2gi[N],j[dsketch]:ii or jj(x(i-1)dsketch+j(k,))2. (9) For each coordinate u[b/3], we can then break the sum into two parts i[N],j[dsketch]x(i-1)dsketch+j(k,)Ri[(-1)b+u,j] =(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j] +(i,j)[N]×[dsketch]𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j], (10) where 𝒲[N]×[dsketch] and such that each of these two parts has a weight vector with 2-norm at least ϵh+1/(λ2(g+1)), i.e., min((i,j)𝒲(x(i-1)dsketch+j(k,))2,(i,j)[N]×[dsketch]𝒲(x(i-1)dsketch+j(k,))2) ϵh+1λ2(g+1). Such a partition can be obtained by sorting the coefficients {(x(i-1)dsketch+j(k,))2:i[N],j[dsketch]} in non-increasing order and then including every other coefficient in the set 𝒲 (which will thus contain the largest, 3rd largest, 5th largest etc. coefficients). Applying Khintchine’s Inequality (Theorem 13) with p=1 and p=2, we get that A1qdsketch(i,j)𝒲(x(i-1)dsketch+j(k,))2 𝔼[|(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j]|] B1qdsketch(i,j)𝒲(x(i-1)dsketch+j(k,))2 (11) and A2qdsketch(i,j)𝒲(x(i-1)dsketch+j(k,))2 𝔼[|(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j]|2] B2qdsketch(i,j)𝒲(x(i-1)dsketch+j(k,))2, (12) where A1, B1, A2 and B2 are some positive absolute constants. Applying the Paley–Zygmund Inequality (Theorem 14) to the random variable Z=|(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j]| with θ=0.5, we get that Z>0.5𝔼[Z] with probability at least 0.25𝔼[Z]2𝔼[Z2]. Note that for our setting of Z, Equation (11) implies that ϵh+1A1λ2(g+1)qdsketchA1qdsketch((i,j)𝒲(x(i-1)dsketch+j(k,))2)1/2𝔼[Z]. Moreover, Equation (5.3) implies that 𝔼[Z2]B22qdsketch(i,j)𝒲(x(i-1)dsketch+j(k,))2. Putting these inequalities together, we get that |(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j]|>ϵh+1A12λ2(g+1)qdsketch with probability at least 0.25A12(i,j)𝒲(x(i-1)dsketch+j(k,))2B22(i,j)𝒲(x(i-1)dsketch+j(k,))2=0.25A12B22. Thus, v𝒲:=(i,j)𝒲x(i-1)dsketch+j(k,)Ri[(-1)b+u,j] is a random variable that is symmetric around 0 and whose absolute value is larger than v:=ϵh+1A1/(22