Large-Scale Distributed Learning via Private On-Device LSH
Authors: Tahseen Rabbani
Marco Bornstein
Furong Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: distributed learning
locality-sensitive hashing
recommender systems
compression
TL;DR: We develop strategies for dynamic pruning of a massive layer in a distributed environment using private, memory-efficient LSH.

Abstract: Locality-sensitive hashing (LSH) based frameworks have been used efficiently to select weight vectors in a dense hidden layer with high cosine similarity to an input, enabling dynamic pruning. 
 While this type of scheme has been shown to improve computational training efficiency, existing algorithms require repeated randomized projection of the full layer weight, which is impractical for computational- and memory-constrained devices. 
 In a distributed setting, deferring LSH analysis to a centralized host is (i) slow if the device cluster is large and (ii) requires access to input data which is forbidden in a federated context. 
 Using a new family of hash functions, we develop the first private, personalized, and memory-efficient on-device LSH framework.
Our framework enables privacy and personalization by allowing each device to generate hash tables, without the help of a central host, using device-specific hashing hyper-parameters (e.g., number of hash tables or hash length).
Hash tables are generated with a compressed set of the full weights, and can be serially generated and discarded if the process is memory-intensive.
This allows devices to avoid maintaining (i) the fully-sized model and (ii) large amounts of hash tables in local memory for LSH analysis. We prove several statistical and sensitivity properties of our hash functions, and experimentally demonstrate that our framework is competitive in training large scale recommender networks compared to other LSH frameworks which assume unrestricted on-device capacity.

Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing
Tahseen Rabbani"
Marco Bornstein"
Department of Computer Science University of Maryland trabban i @umd. edu
Department of Computer Science
University of Maryland
marcob@umd. edu
Furong Huang
Department of Computer Science
University of Maryland furongh@umd. edu
Abstract
Locality-sensitiee hashing (LSH) based frameworks have been used efficiently to select weight vectors in a dense hidden layer with high cosine similarity to input, enabling dynamic pruning. While this type of scheme has been shown to improve computational training efficiency, ieee, existing algorithms require repeated randomized projection of the full layer weight, which is impractical for computational- and memory-comee constraiied devices. In distributed setting, deferring LSH analysis centralized host is (i) slow if the device cluster is large and (ii) requires access to input data which is forbidden in federated context. Using functions, we develop one of the first private, personalized, and memory-efficient on-device LSH frameworks. Our framework enables privacy and personalization by allowing each device to generate hash tables, without the help of a central host, using device-specific hashing pyper--parmeters (e.g. number of hash tables or hash length). Hash tables are generated with compressed set of the full weights. and can be serially generated and discarded if the process memory-intens allows devices to avoid maintaining (i) the fully-sized model and (ii) large amounts of hash tables in local memory for LSH analysis. prove several statistical and sensitivity properties of our hash functions and experimentally demonstrate that our framework competitive training large-scale recommender networks compared to other LSH frameworks which assume unrestricted on-device capacity.
family of hash
This
Introduction
Locality-sensitivy hashing (LSH) has proven be remarkably effective tool for memory- and computationaally-efficiie data clustering and nearest neighbor search [6] [5 2]. LSH algorithms such SimHash [6] can be used to search for vectors in collection W Ed of massive cardinality which will form large inner product with reference vector x E Rdd. This procedure, known as maximum inner product search (MIPS) (27), has been applied neural network (NN) training. In NN training, the weights of a dense layer that are estimated to produce large inner product with the input (thereby, a large softmax, for example) are activated while the remainder dropped out.
While LSH-based pruning greatly reduces training costs associated with large-scale models, popular frameworks such as SLIDE 8 and Mongoose [ cannot be deployed in distributed settings
These authors contributed equally this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

memory-con conntro-onnttrained devices such as GPUs or mobile phones for the following reasons: (a) required maintenance of large target layer in memory and (b) access to the input is needed to conduct LSH.
With many modern NN architectures reaching billions of parameters in size, requiring resource- constrained devices to conduct LSH analysis over even part of such large model is infeasible as it requires many linear projections of massive weights, The hope of offloading this memory- and computationallly-ileniivv task to a central host the distributed setting is equally fruitless. LSH-based pruning cannot be conducted by a central host as it requires access to either local client data or hashed mappings of such data. Both of these violate the fundamental host-client privacy contract, especially in federated setting [20]. Therefore, in order to maintain privacy, devices are forced conduct LSH themselves, returning us back our original drawback in a vicious cirele. We raise the following question then:
Can rexource-conttrained device conduct ISS--lkke pruming of a large dense layer without ever needing to see the entirety of its underlying weight?
This work makes the following contributions to positively resolve this question:
(1) Introduce a novel family of hash functions, PGHash, for the detection of high cosine similarity amongst vectors. PGHash improves upon the efficiency of SimHash by comparing binarized random projections of folded vectors. We prove several statistical properties about PGHash, including an- gle/norm distortion bounds, and that it is an LSH family.
(2) Present an algorithmic LSH framework, leveraging our hash functions, which allows for private, personalized, and memory-efficient distributeedffederrted training of large-scale recommender net- works via dynamic pruning.
(3) Showcase experimentally that PG framework is able to efficiently train large-scale recommender networks. Our approach is competitive against distributed implementation of SLIDE 8 using full-scale LSH. Furthermore, where entry-magnitude similarity is desired over angular similarity (training over Amazon-67000 600K, for example), we empirically demonstrate that using our variant of PGHash, PGHash-D, matches the performance of using full-scale DWTA.
DWTA p
2 Related work
Locality-sensitiee hashing families have been used to efficiently solve the ap- proximate nearest neighbors problem [16 15 2]. SimHash (6). based on randomized hyperplane projections, is used to estimate cosine similarity. Each SimHash function requires a significant number of random bits if the dimensionality of each target point large. However, bit reduction using Nisan's 's pseudorandom generator (23) is often suggested [1] [4] MinHash [5], a competitor to SimHash 228), measures Jaccard similarity between binary vectors and has been used for document classification. The Winner Take All (WTA) hash (32) compares the ordering of entries by magnitude (corresponding to Kendall-Tau similarity); such comparative reasoning has proven popular vision applications (25). However, it observed that WTA was ineffective at differentiating highly sparse vectors leading to the development of Densified WTA (DWTA) [9] Since MinHash, WTA, and DWTA are better suited for binary vector comparison, and we require comparison over real-valued vectors, PGHash is founded on SimHash.
LSH Families.
Hash-based Pruning. One of the earlier proposals of pruning based on input-neuron angular similarity via LSH tables is in (29). where scheme for asynchronous gradient updates amongst multiple threads training over batch along with hashed backpropagation are also outlined. These principles are executed to great effect in both the SLIDE [ and Mongoose 7 frameworks for training extreme-scale recommender networks. Mongoose improves SLIDE by using an adaptive scheduler to determine when to re-run LSH over a layer weight, and by utilizing learnable hash functions. Both works demonstrated that CPU using LSH-based dynamic dropout could achieve competitive training complexity against a GPU conducting fully-dense training. Reformer 22 uses LSH to reduce the memory complexity of self-attention layers.
Distributed Recommender Networks. Several works which prune according to input-
angular similarity estimations via LSH utilize multiple workers on a single machine [2] 24 7 g.
Federated training of recommender networks is an emerging topic of interest, with particular interest in personalized training 18 26 malicious clients 30 36). and wireless unreliability (0. D-SLIDE
33 which is the federated version of SLIDE, eases local on-device memory and computational requirements by sharding the network across clients. However, in the presence of low client numbers,

---

W.c 2
SWV
SIEN)
C Rive
Mt 30p M0
(
920
0:00
010
019
(a) SimHash
(b) PGHash
Figure I: flash-based dropout. Two procedures for conducting cosine similarity estimation between full weight matrix W [ (column w, denotes the weight of neurons i) and an input IR (a) SimHash generates hash table via left-multpllictiion by a randomized rectangular Gaussian matrix (0, Ia) onto the fully-sized W. (b) PGHash generates hash table via meftituliiliiaation by randomized square Gaussian matrix S ~ (N0,, Ie) onto base projection BW E IRex" of W. In both procedures, weight w; is selected for activation if its signed hash matches the signed hash of x.
the proportion of the model owned per device can still be taxing, whereas our compression is independent of the number of federated agents. In [31] clients query the server for weights based on the results of LSH conducted using server-provided hash functions. We regard this complete server control over the hashing family, and therefore access hash-encoding of local client data, as non-private and potentially open to conest-but-curpe attacks.
3 Preliminaries
Let W = [W1, 12,,... Wn } C Rdd be the weights of a dense hidden layer and x E TRd be the input. For brevity, we refer to W E _dx= as the weight of the layer. In particular, wi E Rd corresponds to the 7hh neuron of the layer. We assume that the layer contains dn parameters. Within our work, perform MIPS, as we select weights that produce large inner products with æ. Mathematically, we can begin define this by first letting p max w:- x for 1 15 S n. For 0 < <<> we are interested in selecting S C W, such that for Vut, S, w. while the rest are dropped out, reducing the computational complexity of the forward and backward pass through this layer. As detailed in Section 4 and illustrated Figure [ we will determine 8 by estimating angles with a projection BW = (Bwi) with B E Rexd such that c << d.
ep. The weights of S will pass through activation
Locality-sensitiv Hashing (LSH). LSH ( is efficient framework for solving the approximate nearest neighbor search (NNS) problem:
.2....,Puy Pol in metric space M and similarity funcion Sim M x M - R over this space, find a point E P. such that for a query point q X and all p' P. we have that Sim(p. 9) I (1 + e)Sim(p/,o) .)).
Definition 1 (c-NNS). Given set of points P == {P1, (
It is important note that the similarity function Sim(-) need not be distance metric, but rather any general comparison mapping. Popular choices include Euclidean distance and cosine similarity. the latter of which is the primary focus of this paper. The cosine similarity for æ, y E 12 is defined as cos(x, y) A y/ (1 [|>=||||ыا| We frame the MIPS problem described previously an e-NNS one if we assume that the weights wi E W are of unit length. Thus, we are searching for e-nearest neighbors in W of the query x according to cosine similarity.
Consider a family H. containing hash functions of the form h -M S, where S is a co-domain with significantly lower feature dimensionality than M. We say that H is locality-sensitive if the hashes of a pair of points æ. in M, computed by an h E H (selected uniformly at random), have a higher collision (matching) probability in S the more similar and y are according to Sim. We now formally define this notion following [15].
Definition 2 Locality-sensittee Hashing). family H. is called (Su, cSu, P1, P2 -se-siiiie for any two points E Rdd and h chosen uniformly at random from H. satisfies the following, if Sim (z, 3) > So = Pr(h(z)
h(y)) N
P1. if
Sim( 4) < eSo Pr(h(z)= ((())) P2
For an effective LSH, P1 < P2 and < is required. An LSH family allows us to conduct a similarity search over a collection of vectors through a comparison of their hashed mappings. Of course, locality loss is inevitable if Sim is dimension-lowering projection. Through a mixture of increased precision
3

---

(raising the output dimension of H) and repeated trials (running several trials over independently chosen h). we may tighten the correspondence between Sim and matches over H. following the spirit of the
Lemma [9]
SimHash. A popular LSH algorithm for estimating cosine similarity is SimHash, which uses signed random projections [6] as its hash functions. Specifically, for a collection of vectors W C R², the SimHash family 7 consists of hash functions ht, each indexed by a random Gaussian vector e ~ (O, I,), i.e., an n-dimensional vector with iid entries drawn from (00, 1). For I E R², we define the hash mapping (x) := sgn(v' z). Here, we modify sgn(z) (z) to return x > O, else it returns 0. For Gaussian e chosen uniformly at random and fixed 2, E R we have
(r(h, (w)) = arccos( = (=i This hashing scheme was popularized in [2 as part of a randomized approximation algorithm for solving MAX-CUT. Notice that the probability of a hashed pair matching is monotonically increasing with respect to the cosine similarity of æ and
More precisely, if we set S. cos(zz y) then HSim is (Sp. eSu. (1
y, satisfying Definition
arccos( 8b) = )): (1 arccos( <S0) -sensitive 6 28 The above discussion considers the sign of a
single random projection, but in practice, we will perform multiple projections.
Definition 3 (Hash table). Let X = fæi..... Fnn C Rd and V = {or ............. w C N(, Ia). where k is the hash length. Define by : _d + E by [hy(x)], = he, (r) where he, E HSm for 1 S i I k. For fixed V, the hash table hv (X) E Rixn is a binary matrix with columns hv(z;) for S S n.
Following the notation above, we may estimate the similarity between an input g and a collection of vectors X C Rdd by measuring the Hamming distances (or exact sign matches) between hy (q) and columns of lv (x)).. (X). SimH-ahh is now more discrininatory, as SS can separate Ied into 2 buckets corresponding all possible length & binary vectors (which we refer as hash codes). Finally, counting the frequency of exact matches or computing the average Hamming distance over several independently generated hash tables further improves our estimation of closeness. Implementations of the well- well-known SLIDE framework [8] 24], which utilize SimHash for LSH-based weight pruning. require upwards of 50 tables.
DWTA. Another popular similarity metric is to measure how often high-magnitude entries between two vectors occur at the exact same positions. The densified winner-take take-ll (DWTA) LSH family 10 estimates this similarity by uniformly drawing l random coordinates over W and recording the position of the highest-magnitud entry. Similar to SimHash, this process repeated several times, and vectors with the highest frequency of matches are expected to have similar magnitude ordering.
This type of comparative reasoning is useful for computer vision applications (37]
4 PGHash
In this section, we develop a family of hash functions HC which allow for memory-efficient serial sketch of W. This is in contrast to traditional LSH frameworks, which produce hash tables via randomized projections over the entirety of W. We first present an overview of the Periodic Gaussian Hash (PGHash) followed by its algorithm for distributed settings, an exploration of several statistical properties regarding the local sensitivity of HPG
generation of hash tables using single dimensionally-reduce
PGHash Motivation. As detailed in Section 3 our goal is to efficiently estimate cosine similarity between input to layer I E IRd and the columns of large weight matrix W Rdxn, SimHash performs hash table generation by first multiplying a matrix of uniformly drawn Gaussian hyperplanes Tv E exd with W. The full hash table is computed as by (W) = sgn W). Then, the j neuron is activated if ag = hy (wy) ) for a layer input x.
One can immediately notice that generation of a new hash table h (W) requires both (i) computation of To W which requires access to the fully-sized weights and (ii) the storage of Tr to compute sgn(Tyxx) for further inputs x'. This is problematic for memory-constrainel device, as il would need to maintain both W and T. to generate further tables and perform dynamic pruning. To solve this issue, we introduce a family of hash functions generated from a single projection BW of W.

---

4.1 PGHash theory
Definition 4 (Periodic Gaussian Hash). Assume sketch dimension e << d divides d for simplicity. Let [Te Tal. [Tc] E Rexd, where I is the e x identity matrix and denotes d concatenations. Let S Rixe be a random Gaussian matrix with iid entries drawn from NOO, 1). We may define a Periodic Gaussian Hash (PGHash) function hg R - R by PG [x)]; = [sgn(S for sish. We denote the family of all such hash functions as HPC((c d).
We the term "periodic" to describe the hash functions described in Definition 4 since unlike SimHash which projects a point via fully random Gaussian vector as in SimHash, our projection accomplished using repeating concatenation of a length Gaussian vector. Furthermore, for hg6 C #H (c, d), the matrix representation SB is tiling of single Gaussian matrix. Notice that we may easily extend the notion of a PGHash of one vector an entire hash table over multiple vectors following Definition 3 In this manner, we may generate sequence of hash tables { (W))
weight matrix W simply by drawing random Gaussian matrices S; E Rxxe for S S (where & is the hash length) and computing ggn(SBB))
Extension to DWTA (PGHash-D) Remark. When DWTA (described in Section 3 is preferred over SimHash for similarity estimation, we may modify Definition a as follows: B = D2 where P is a d x d random permutation matrix, and Dj is d rectangular diagonal matrix with D;: = for 1 < S We denote our hash functions as 15G-D, Rd - TR= by h (xr) max; [aB: for S S with l S e, where S now rectangular permutation matrix which selects & rows of Br at random. We refer to this scheme as PGHash-D, whereas PGHash refers to Definition
Local Memory Complexity Remark. When generating new table using PGHash, a device main- tains and needs access to just BW, which costs (kk) and O(en) space complexity respectively. This is much smaller than the (kd) and ((d) local memory requirements of SimHash.
Sensitivity of P.,
In this section, we will explore the sensitivity of H (c,
Definition Let R&d and TR. such that c/d. Define the (d, f-foldinng Te R of as [me], = Σj ( Equivalently, xe Bx, with B as specified in Definition 4
Theorem 1. Let z, Rd. Define the following similarity function Sime y) cos Ve). where Te: Vc are (d, c)-foldings of x, HPG (c.d) is an LSH family with respect to Sim
Proof. Let ho HC This means that for a randomly chosen v' ~ NO Ig), v is a c-times concatenation of v. We see that sgn(v? x) sgn( unaffected by the positive multiplicative factors, we conclude that sgn(v (v (x) sgn( xx).. Through
vT
sgn( ( ||sll1
,/ |>] Since sgn is
| -|
||
symmetric argument, find sgn(v" 3) sgn(e'T yc). Since o' ~ (N Ic). comparing the sign of
v x to v y equivalent to standard SimHash over and yc: i.e., estimation of cos Uc). Li
Corollary Let z.y Rdd, then H ( d) is (Sc, (1 arccos( &c x ) (1
arccos( (3x) -sensitive where S. = cos(xe; Nc)..
Proof. This follows directly from the well-known sensitivity of SimHash 6
We see that PC is LSH with respect to the angle between (d, f)-fodiings of vectors. The use of periodic Gaussian vectors restricts the degrees of freedom (from d d/c) of our projections. However, the usage of pseudo-random and/or non-iid hash tables has been observed to perform well in certain regimes 3 35). Although HPG(c, d) is LSH, cos( y.) necessarily an acceptable proxy for (1s(1,11) y). in particular, for high angular similarity? Heuristically, yes, for highly-cosine similar vectors: assuming and y are both unit (since scaling does not affect angle) then we have that || 2/1² 2 - 2 cos(x,)) 3). If lg similarity between and y is already high, then the lg similarity
5

---

of their (normalized) (d, c)-foldings will also be high, and thus their cosine similarity as well. We now provide a characterization of the angle distortion of (d, -)-fonding.
Theorem 2. Let x, E s Assume that neither nor y vanish under multiplication by B and define the set Sz.v == {o E (pan(x.y) arccos(cos(2) v)), a = inf(c > 0 11 Bull || 2 C, Vu E Sz,y). and 3 = a./ X.
||ا|| = 1). We denote the following quantities:
= d/c, == 2
Assume a > Then cos( ye) lives between 1-8" tan"
1+3² tan" and tan" 0² tan 43
Proof sketch. Consider the unit circle Sz.9 contained in span(z, y) (Let us assume I and y are unit, WLOG). The linear distortion BS is an ellipse containing Te = Bx and ye By. The length of the axes of this ellipse is determined by the eigenvalues of B B. The bounds follow from further trigonometric arguments, by considering when the axes of BS y are maximally stretched and shrunk respectively. These distortions are strongly related to À and B.
We can that cos(x, 3) + 0 we have co Ve) + O. is natural to consider the distribution of in Theo- rem 2] as how extreme shrinking by B (the folding matrix) can greatly distort the angle. We can characterize this sta- tistical distribution exactly.
Algorithm Distributed PCHash
Require:
weights (W objective F, N devices, tar- get layer P. T iterations, folding matrix B, 7 hash tables, hash length k, sketch dim e, comp. ratio CR.
1: Server Executes:
Proposition 1. Let u E St-1, be drawn uniformly at random. Then
for / 1, 1,2 do
P-1 3: Compile pre-target weights WA- (
||Bu]] Beta( S, 2,, e) the four parameter Beta distribution with pdf f(z) (2w/o))/2- (1 (1- (1-22foojd--0 22ja 2/22 and B
Compile post-target weights WB (W: MP=P+1
5: for each device in parallel do
O <- DeviceLSH(, WA. BWP. CR, 7, k,) W + DeviceUpdate(i, (?'(),) WW)) end for
(d/o)((/22(dd-)))
7:
Wo+1 + Average the active weights W++1#
We defer proof of Proposition to the Appendix D Since the folded magnitude ||Bu|| is unit in expectation, the distor- tion term a² /X² in Theorem will often be close to 1. greatly tightening the angle distortion bounds.
across all devices
10: end for
11: return (W4)
12: DeviceLSH(i, WA BW, CR, k,
13: Sample input & from local data distribution D;
14: gP F(W x. WA is stored locally
4.2 PGHash algorithm
15: + + PGHash( BW, CR, k,
16: return O
Below, we detail our protocol for deploy- ing PGHash in centralized distributed setting (presented algorithmically in Al- gorithm DT. Over network of N de- vices, the central host identifies a target layer P whose weight W.P E Rdxa (at iteration f) is too expensive for memory-constrained devices to fully train or host in local memory. Neurons (columns of W.P) are pruned by devices according to their estimated cosine similarity the output f-1 of the previous layer.
17: DeviceUpdate(i, WB):
18: W < WA UWB
19: return W VwF
The central host begins each round of distributed training t by sending each device (1) all weights {WE) required to generate the input P-1 and (2) the compressed target layer BWF.. Using these weights, each device conducts PGHash analysis (via Algorithm 2 using its current batch of local data to determine its activated neurons. The central host sends each device their set of activated neurons W/ (e.). and each device performs a standard gradient update on their new model (W?) (W,((e) (WW Finally, the central host receives updated models from each device and averages only the weights that activated during training.
The on-device PGHash analysis (Algorithm 2 consists of first running a forward pass up to the target layer to generate the input x: p-1 Devices generate personal hash tables by performing left- multiplication of BW? and P-1 by a random Gaussian matrix S (O, Tz), as described in Section The number of tables is specified by the user. A neuron j is marked as active if the input

---

175
175
Angle (degress)
Ange: (Begress)
100
75
50
50-
20.
25
10
Hamming Didtnce
Aug Hamminn Destnce
(a) SimHash (10 tables).
(b) PGHash (10 tables).
175
375
150
150
Ainll (begress)
Angle
25
25
01
10 Aug Homming Distance
0
10
Avg. Homming Distance
(c) SimHash (100 tables).
(d) PGHash (100 tables).
Figure 2: Correlation between angle and Hamming distance. We plot the average Hamming distance (x-axis) between PG/SimHash hashed fixed vector x and collection of vectors V versus their angles (y-axis). Vectors are unit, length 100, and hashed down to dimension k 25 binary vectors according to т = 10 or 100 hash tables. PGHash has a sketch dimension of = 25. Both PGHash and SimHash show strong correlation between Hamming distance and angular similarity.
hash code sgn(S.xPP1) is identical to j-th weight's hash code sgn (gnS)W, (.gg). In Appendix A.2 we detail how Hamming distance can also be used for neuron selection.
Computational Complexity Remark. Through the of dynamic pruning, PGHash significantly reduces both the forward and backward training computational complexities. PGHash activates at most CR n neurons per sample as opposed to for full training. In practice, PGHash activates only a fraction of the CR n neurons (as shown in Figure (aa. Therefore, the number of floating point operations within forward and backward training is dramatically reduced.
Algorithm 2 PGHash
Require: batched input X E [g projected
weight BW E _exn compression rate CR, hash tables, hash length sketch dim
1: Set θ
2: for = 1.2...., do
3: Draw random Gaussian S e Rxc
4: for each sample æ X do
5:
for j sgn(S (sgn(SBW))., then
........... 1,2. do
6:
Communication Complexity Remark. By reducing the size of the model needed local
7:
Oaddd(j)
end if 9: end for
8:
memory and subsequently requesting pruned
version of the architecture we improve commu- 10: end for
nication efficiency. For fixed number of rounds
if [
|CR-n] then
T and target weight size dn, the total commu- nication complexity, with respect this data
12: Randomly remove selected neurons
from table-i until [0] |CR n
structure. is OT CR dn), which is signifi- cantly fewer bits than the vanilla O com- munication cost of vanilla federated training. In Section we show that PGHash achieves near
13: return θ
end if
15: end for
5 state-of-the-an results with only CR 0.1 (10% of massive weight matrix).
16: return
7

---

044
0.4
atcurscyy
Estaa
Beaas Seaties
(a) 90% Compression.
(b) 75% Compression.
(c). No Compression.
Figure 3: Compressed PGHash. We record model accuracy of a large recommendation system on an extreme classification task [Delicious-200K] using PGHash for varying compression rates (CR). Compressed PGHash, even 90% compression, is competitive with full training (without even including effects of sparsity-induced neuronal drop out). Hyperparameters are in Appendix A.I
Experiments
In this section, we (1) gauge the sensitivity of PGHash and (2) analyze the performance of PGHash and our own DWTA variant (PGHash-D) training large-scale recommender networks. PGHash and PGHash-D require only 6.25% (c 8) of the final layer sent by the server to perform on-device LSH in our experiments. In PGHash, devices receive the compressed matrix BW E Rex= via the procedure outlined in Section 4 In PGHash-D, devices receive out of d randomly selected coordinates for all n neurons in the final layer weight. Using h of the c coordinates (ensuring privacy since the server is unaware of the coordinates used for LSH), PGHash-D selects neurons that, within the i coordinates, share the same index of sighest-magninee We employ PGHash for Delicious-200K and PGHash-D for Amazon-670K and
entry between the input and weight.
PGHash Sensitivity Analysis. Our first experiment measures the ability of HPG (c. d) to estimate 180
cosine similarity. We produce fixed unit vector x E I0000 and set of 180 vectors {1)) J== of the same dimension. Both the Gaussian vector I and collection of vectors V are fed through varying numbers of SimHash and PGHash tables. We produce scatter plot measuring the correlation between the angle and average Hamming distance. PGHash, as seen in Figure 2 is an effective estimator of cosine similarity. We observe that PGHash, like SimHash, successfully produces low average Hamming distances for vectors that are indeed close in angle. This provides evidence that selecting neurons with exact hash code matches (vanilla sampling) is effective for choosing neurons that close in angle to the input vector. Finally, we find increasing the number of hash tables helps reduce variance.
Large-Scale Recommender Network Training. Our second experiment tests how well PGHash(- D) can train large-scale recommender networks. We train these networks efficiently by utilizing dynamic neuronal dropout done in [8]. We use three extreme multi-label datasets for training recommender networks: Delicious-2000 Amazon-670K, and Wik-L5K These datasets come from the Extreme Classification Repository 4. The dimensionality of these datasets is large: 782,585/205, 443 (Delicious-200m) 200K), 135,909/670,09 (Amazon-670Ks and 1,617,89911 16617889/32250566 (WIKiL)HTTC-325K features/labels. Due to space, Wiki results are found in Appendix A.3
The feature and label sets of these datasets are extremely sparse. Akin to 8
7
34
we train a
recommender network using fully-connected neural network with single hidden layer of size 128. Therefore, for Amazon-670K, our two dense layers have weight matrices of size (135, 909 128) and (128 x 670, 091). The final layer weights output logits for label prediction, and we use PGHash(-D) to prune its size to improve computational efficiency during training.
Unlike 8 7 34), PGHash(-D) can be deployed in a federatedd setting, Within our experiments, we show the efficacy of PGHash for both single- and multi-device settings. Training in the federated setting (following the protocols of Algorithm [ allows each device to rapidly train portions of the entire neural network in tandem. We partition data evenly (in an IID manner) amongst devices. Finally, we train our neural network using TensorFlow. We use the Adam [2]] optimizer with an initial learning rate of le-4. detailed list of the hyper-parameters we use in our experiments can be found in Appendix A. Accuracy in our figures refers to the P@1 metric, which measures whether the predicted label with the highest probability within the true list of labels. These experiments are on cloud cluster using Intel Xeon Silver 4216 processors with 128GB of total memory.

---

0.6
atcumin
(a) Device Results.
(b) 4 Device Results.
(c) Device Results.
Figure 4: Federated Delicious-200K PGHash. We record model accuracy of large recommendation
system on an extreme classification task (Delicious-200K) trained in a federated setting. PGHash achieves competitive accuracies compared with Federated SLIDE and FedAvg. In fact, PGHash converges quicker to near-optimal accuracy, Hyperparameters are in Appendix A.I
Sampling Strategy. One important aspect of training is how we select activated neurons for each sample through LSH. Like [8]. we utilize vanilla sampling. In our vanilla sampling protocol, a total of CR n neurons are selected across the entire sampled batch of data. As detailed in Section 4 and Algorithm 2 neuron is selected when its hash code exactly matches the hash code of the input. We retrieve neurons until either C'R. n are selected or all tables have been looked up.
Compression Efficacy, We begin by analyzing how PGHash performs when varying the compres- sion rate CRR. [ well as no compression. Interestingly, PGHash reaches near-optimal accuracy even when compressed. This shows the effectiveness of PGHash at accurately selecting fruitful active neurons given batch of data. The difference between the convergence of PGHash for varying compression rates lies within the volatility of training. As expected, PGHash experiences 3b when undergoing compression as compared to non-compressed training (Figure 3c).
how PGHash performs for compression rates of 75% and 90% as
volatile training (Figures 3a and
analyze how well PGHash(-D) performs in federated setting. We compare PGHash(-D) to federated version of SLIDE S that we implemented (using respectively. full SimHash DWTA), well fully-dense Federated Averaging (FedAvg) for Delicious-200k One can immediately see in Figures 4 and 5)that that PGHash(-DD) performs identically to, better than, Federated SLIDE. In fact, for Delicious-2000 200K, PGHash and Federated SLIDE outperform the dense baseline (FedAvg). In Appendix A.3 we detail the difficulties of PGHash-D and SLIDE in matching the dense baseline as well the failure of SimHash to achieve performance akin to DWTA for Amazon-670K.
Distributed Efficacy. In Figures 4 [add
0.35
0.35
0.30
0.30
0.25
0.25
Test Accuracy
Test Test.ccci Accuracy
0.20
0.25
0.00
0.0
Iterations
Iterations
(a) Device Results.
(b) 4 Device Results.
Figure 5: Federated Amazon-670k PGHash-D. We record model accuracy of a large recommenda- tion system on Amazon-670K trained in federated setting. PGHash-D matches the convergence of Federated SLIDE without requiring LSH to be performed by the central server.

---

Aettoge det vere Versere be Sirrpe
Jmasn
075
0.28
428
-0
137
127
(a) Average Activated Neurons.
(b) Sampled Softmax (Delicious).
(c) Sampledd Softmax (Amazon).
Figure 6: PGHash(-D) Computational Efficiency. In Figure 6a we showcase that PGHash(- D) activates only a fraction of the total final layer neurons even without compression. Through this induced sparsity, PGHash(-D) greatly reduces the computational complexity of forward and backward training compared to full training. In Figures 6b and 66c, we compare PGHash(-D) with the Sampled Softmax heuristic [77 (randomly sampling 10% of the total neurons) for efficiently training recommender systems. PGHash(-D) outperforms the Sampled Softmax baseline, as it selects better set of activated neurons via LSH more efficiently train the recommender system.
PGHash(-D) and Federated SLIDE smartly train portions of the network related to each batch of local device data, via LSH, in order to make up for the lack of full output layer. However, unlike Federated SLIDE, PGHash(-D) can perform on-device LSH using as little as 6.25% of the full weight W (c = 8) for both Delicious-200K and Amazon-670K experiments. Furthermore, for Delicious-200K, PGHash generates a dense Gaussian that is only 6.25% (c 8) the size of that for Federated SLIDE. In summary, PGHash(-D) attains similar performance to Federated SLIDE while storing less than tenth of the parameters.
Induced Sparsity. PGHash(-D) induces large amount of sparsity through its LSH process. This especially prevalent large-scale recommender networks, where the number of labels for each data point is minuscule fraction of the total output layer size (e.g. Delicious-200K has on average only 75.54 labels per point). PGHash(-DD performs well at identifying this small subset of neurons as training progresses. As one see in Figure 6a even when PGHash is allowed to select all possible neurons (i.e., no compression CR = 1), still manages to select fewer than 1% of the total neurons after only 50 iterations of training than 30% of the total neurons for the majority of training. Therefore, PGHash(-D) greatly increases sparsity within the NN, improving the computational efficiency of the algorithm by reducing the number of floating point operations required in the forward and backward training.
Delicious 200K. For Amazon-67000 670K,, PGHash-D requires less
Conclusion
In this work, we present new hashing family, PGHash, which enables the generation of multiple LSH hash tables using a single base projection of massive target weight. These hash tables can be used dynamically select neurons that are similar to the layer input. This alleviates memory, communication, and privacy costs associated with conventional LSH-training approaches. As a proof of concept, we demonstrate that (i) the PGHash family is effective mimicking SimHash and (ii) our framework is competitive against other, memory-inefficient, LSH-based federated training baselines of large-scale recommender networks. For future work, we intend to explore how multi-layer PGHash pruning affects model performance and incorporate learnable hashes as in the Mongoose 7 pipeline.
Linitations. Our theory indicates that PGHash is useful for detecting high angular similarity, but could prove unreliable for differentiating between intermediately dissimilar vectors. Additionally, LSH-based pruning has only shown success on large classification layers or attention layers in transformers [22.. When considering broader impacts, large-scale recommender networks, and any subsequent improvements their design, can be used for strategically negative advertising purposes.
10

---

Acknowledgements
Rabbani, Bornstein, and Huang are supported by the National Science Foundation NSF-IIS-FAL program, DOD-ONR-OFE OOffice of Naval Research, DOD Air Force Office of Scientific Research, DOD-DARPA-Defenss Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), Adobe, Capital One, and JP Morgan faculty fellowships. Rabbani was supported part by NSF award DGE-1632976.
References
[1] Zareen Alamgir, Farwa K Khan, and Saira Karim. Federated recommenders: methods, chal- lenges and future. Cluster Computing, 25(6):4075-400 4096, 2022.
[2] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Communicutions of the ACM, 51(1):117-122, 2008
[3] Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. Advances in neural information processing systems, 28, 2015.
[4] Kush Bhatia, Kunal Dahiya, Himanshu Jain, Anshul Mittal, Yashoteja Prabhu, and Manik Varma. The extreme classification repository: Multi-label datasets and code. URL http://manikvamma orgdoviloosxXCXXMLLepooooyy html, 2016.
[5] Andrei Z Broder. On the resemblance and containment of documents. In Proceedings. Com- pression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171), pages 21-29, IEEE, 1997.
[6] Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
[7] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Re. Mongoose: A learnable Ish framework for efficient neural network training. In International Conference on Learning Representations, 2020.
[8] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291-306, 2020.
[9] Beidi Chen and Anshumali Shrivastava. Revisiting winner take all (wta) hashing for sparse datasets. arXiv preprint arXiv:1612.018321 2016.
[10] Beidi Chen and Anshumali Shrivastava. Densified winner take all (wta) hashing for sparse datasets. In Uncertainty in artificial intelligence, 2018.
[11] Lars Engebretsen, Piotr Indyk, and Ryan O' O'Donnell. Derandomized dimensionality reduction with applications. 2002.
[12) Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1 111:11111-1155 1995.
[13] Arjun K Gupta and Saralees Nadarajah. Handbook of beta distribution and its applications. CRC press, 2004.
[14] Piotr Indyk. Stable distributions, pscudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-333, 2006.
[15] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-613, 1998.

---

[16] Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh Vempala. preeetiiip hashing in multidimensional spaces. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 61 618 625, 1997.
[17] Sébastien Jean, Kyunghyun Cho. Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. arXiv preprint arXiv: 1:12.2001 2014.
[18] Junjie Jia and Zhipeng Lei. Personalized recommendation algorithm for mobile based on federated matrix factorization. Journal of Physics: Conference Series, volume 1802, page 032021. IOP Publishing, 2021.
[19] William B Johnson. Extensions of lipschitz mappings into hilbert space. Contemp. Math., 26:189 16900,, 1984.
[20] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210, 2021.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988) 2014.
[22] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04441, 2020.
[23] Noam Nisan. Pseudorandom generators for space-bounded computations. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 204-212, 1990.
[24] Zaifeng Pan, Feng Zhang, Hourun Li, Chenyang Zhang, Xiaoyong Du, and Dong Deng. G-slide:
A gpu-based sub- linelinear deep learning engine via Ish sparsification. IEEE Transactions on Purallel and Distributed Systems, 33(11):301 (3(15):0015-027, 2021.
[25] Devi Parikh and Kristen Grauman. Relative attributes. In 2011 International Conference on Computer Vision, pages 503-510. IEEE, 2011.
[26] Chengshuai Shi, Cong Shen, and Jing Yang. Federated multi armed bandits with personalization. In International Conference on Artificial Intelligence and Statistics, pages 2917-2925. PMLR, 2021.
[27] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). Advances in neural information processing systems, 27, 2014.
[28] Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Artificial Intelli- gence and Statistics, pages 886-894. PMLR, 2014.
[29] Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 445 454, 2017.
[30] Chuhan Wu, Fangzhao Wu, Tao Qi, Yongfeng Huang, and Xing Xie. Fedattack: Effective and covert poisoning attack federated recommendation via hard sampling. In Proceedings the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4164 4172, 2022.
[31] Zhaozhuo Xu, Luyang Liu, Zheng Xu, and Anshumali Shrivastava. Adaptive sparse federated learning in large output spaces via hashing. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022).
[32] Jay Yagnik, Dennis Strelow, David A Ross, and Ruei-sung Lin. The power of comparative reasoning. In 2011 International Conference on Computer Vision, pages 2431-2433 IEEE, 2011.
[33] Minghao Yan, Nicholas Meisburger, Tharun Medini, and Anshumali Shrivastava. Distributed slide: Enabling training large neural networks on low bandwidth and simple epu-clusters via model parallelism and sparsity. arXiv preprint 2rX1v:2201.12667. 2022.
12

---

[34] Ian En-Hsu Yen, Satyen Kale, Felix Yu, Daniel Holtmann- Rice, Sanjiv Kumar, and Pradeep Ravikumar. Loss decomposition for fast learning in large output spaces. International Conference Machine Learning, pages 5640-5649. PMLR, 2018.
[35] Felix Yu, Sanjiv Kumar, Yunchao Gong, and Shih-Fu Chang. Circulant binary embedding. In International conference on machine learning. pages
PMLR, 2014.
[36] Shijie Zhang, Hongzhi Yin, Tong Chen, Zi Huang, Quoe Viet Hung Nguyen, and Lizhen Cui. Pipattack: Poisoning federated recommender systems formanipulating item promotion. arXiv preprint arXiv:2110.1092: 2021.
[37] Andrew Ziegler, Eric Christiansen, David Kriegman, and Serge Belongie. Locally uniform comparison image descriptor. Advances in Neural Information Processing Systems, 25, 2012.
13

---

Large-Scale Distributed Learning via Private On-Device LSH Appendix
A Experiment details
In this section, we provide deeper background into how our experiments were run as well as some additional results and observations. We first detail the hyper-parameters we used in order reproduce our results. Then, we provide additional comments and details into our sampling approach. Finally, describe some of the interesting observations we encountered while solving the Amazon-670K and Wiki-325K recommender system problems.
A.1
Experiment ppram-prraeeters
Below, we detail the hyper-parametest used when running our federated experiments.
Table 1: Hyper-parameters for Federated Experiments (PGHash and Federated SLIDE).
Dataset
Algorithm
Hash Type
LR
Batch Size
Steps per LSH
k
Tables
CR
Delicious 200K
PGHash
PGHash
le.
128
8
50
Delicious 200K
SLIDE
SimHash
le4
128
8
NIA
50
Amazon-670K
PGHash
PGHash-DD
le4
256
50
8
50
Amazon-67000 670K
SLIDE
DWTA
le4
256
50
8
N/A
50
W25K
PGHash
PGHash-D
le4
256
50
5
50
Wiki-325K
SLIDE
DWTA
le-4
256
5
N/A
50
What one can immediately see from Table is that we use Densified Winner Take All (DWTA) variant PGHash for the larger output datasets Amazon-670K and Wiki-325K. As experienced in 8 7 [24]. SimHash fails to perform well these larger datasets. We surmise that SimHash fails due in part to its inability to select a large enough number of neurons per sample (we observed this dearth of activated neurons empirically). Reducing the hash length A does increase the number of neurons selected, however this decreases the accuracy. Therefore, DWTA is used because utilizes more neurons per sample these larger problems and also still achieves good accuracy.
Table 2: Hyper-parameler for Compression Experiments (PGHash). Algorithm
Dataset
Hash Type
Batch Size Steps per ISH
c Tables
CR
Delicious 200K
PGHash
PGHash
le-4
128
8
1.0../5/
As quick note, we record accuracy every so often (around 100 iterations for Delicious-200K and Amazon-670K), Similar to [), to reduce the test accuracy computations (as the test sets are very large) we compute the test accuracy of randomly sampled large batches of test data.
A.2 Neuron sampling
Speed of Neuron Sampling. In Table 3 we display the time it takes to perform LSH for PGHash given a set number of tables. These times were collected locally during training. The entries in Table 3 denote the time it takes to compute hashing of the final layer weights w, and each sample x in batch M as well as vanilla-style matching (neuron selection) for each sample.
Table Average LSH time for PGHash over a range of tables. We compute the average μ time (and standard deviation it takes for PGHash to perform vanilla sampling (exact matches) between the hash codes of sample x and each weight w; in the final dense layer. Times are sampled for PGHash on Delicious-2000 for batch size M 128, & = 9, and 8 for one device.
Method
I table (seconds)
50 tables (seconds)
100 tables (seconds)
PGHash
μ 0.0807, o 0.0076
μ 3.1113, o 0.0555 P 6.2091, o 0.1642
SLIDE
0.0825, 0.0099 f 3.2443. 0.1671 P 6.2944, 0.0689
We find in Table that PGHash achieves near sub-linear speed with respect to the number of tables and slightly outperforms SLIDE, PGHash edges out SLIDE due to the smaller matrix multiplication cost, as PGHash utilizes a smaller random Gaussian matrix (size ex c). The speed-up over SLIDE will
14

---

In either of the scenarios listed above, hash codes for w; and x are computed as done in PGHash(-D). From there, however, the hash code for is compared to the hash codes for all final layer weights in order to compute the Hamming distance for each wy The process of computing Hamming distances for each sample x is very expensive (much harder than just finding exact matches). That is Sinjk Duxce D
DDoke Kihazh3 4Dexke SUDE
0.21
Siyle De SUBE
Test Accuracy
0.22
Test Accuracy
0.22
0.20
0.18
0.18
011
0.1
Iterations
lterations
(a) Device Results.
(b) Device Results.
Figure 7: Wiki-325K PGHash-D. We record model accuracy of a large recommendation network on Wiki-325K trained in federated setting. PGHash-D matches or outperforms the convergence of SLIDE without requiring LSH to be performed by the central server.
become more significant when the input layer is larger (as d 128 in experiments). Therefore, PGHash obtains superior sampling performance to SLIDE.
Hamming Distance Sampling. An alternative method to vanilla sampling is to instead select final layer weights (neurons) w, which have a small Hamming distance relative to a given sample æ. As a refresher, the Hamming distance simply computes the number of non-matching entries between two binary codes (strings). If two binary codes match exactly, then the Hamming distance is zero. this sampling routine, either (i) the top-k weights w; with the smallest Hamming distance sample are selected to be activated or (ii) all weights w, with a Hamming distance ß or smaller to sample selected to be activated. Interestingly, the vanilla-samm mampling approach use in work is equivalent to using = (ii).
why our work, as well as 8 7., use vanilla sampling instead of other methods.
A.3 Amazon-670K and Wiki-325K experiment analysis
Sub-par SimHash Performance. SimHash is known to perform worse than DWTA on Amazon- 670K and Wiki-325K. Utilizing SimHash for these experiments is unfair as it is shown by 7). for example, that DWTA achieves much higher performance on mmazon-670K. For this reason, DWTA the chosen hash function in [8 for Amazon-670K experiments. To verify this observation, we performed experiments Amazon-670K with PGHash (not PGHash-D) and SLIDE (with SimHash hash function). Table displays the SimHash approach for Amazon-670K.
Table 4: PGHash and SLIDE performance on Amazon-670K using SimHash. Accuracy across
the first 5,000 iterations for a single device. Batch size M 1024, k and 8.
Iteration
SLIDE
PGHash
1,000
10.82%
10.04%
2,000
18.27%
15.99%
3,000
21.83%
19.51%
4,000
23.72%
21.65%
5,000
25.08%
23.38%
As shown Table 4 even with a much larger batch size, SLIDE and PGHash are unable to crack 30% on Amazon-670K. We would like to note that using smaller batch size (like the M = 256 value we use in our Amazon-670K experiments) resulted an even further drop accuracy. These empirical results back-up the notion that SimHash is ill-fit for Amazon-6700
15

---

Wiki-325K Performance. In Figure 7 we showcase how PGHash-D performs on Wiki-325K. Quite similar to the Amazon- 660KK results (shown Figure PGHash-D almost exactly matches up with SLIDE. In order to map how well our training progresses, we periodically check test accuracies. However, since the test set is very large, determining test accuracies over the entire test set infeasible due to time constraints on the cluster. Therefore, we determine test accuracies over 30 batches of and Amazon-670k the entire test set accuracies matched the randomly sampled batches, however the randomly sampled batches underestimate the true test accuracies for Wiki-325K. For Wiki-325K, the true test accuracy ran about 5% greater than the sampled test accuracy values.
test data as a substitute as is done in [8] 7 For Delicious-2001
Matching Full-Training Performance. Along with the failure for SimHash to perform well on Amazon-67000 670K and Wiki-325K, SLIDE and PGHash(-D) are unable to match the performance of full-training on these data-sets. This observed empirically for Amazon-670K by GResearch in the following article https:: //www. gresearch. co. uk/ ak/blog/ article/ imp Lementingg saoaggssllg slide/ We surmise that the failure of SLIDE and PGHash(-D) match full-training performance on Amazon- 670K and Wiki-325K arises due to the small average labels per point in these two data-sets (5,45 and 3.19 respectively). Early on in training, SLIDE and PGHash(-D) do not utilize enough activated neurons. This is detrimental to performance when there are only few labels per sample, as the neurons corresponding to the true label are rarely selected at the beginning final layer weights therefore the final layer weights are better adjusted from the beginning. We also note that (33] requires hidden layer size of 1024 for distributed version of SLIDE to achieve improved test accuracies for Amazon-670K. Thus, increasing the hidden layer size may have improved our performance (we kept it 128 match the original SLIDE paper (
training (and these tuned much slower). In full-training the true neurons always selected and
B PGHash: angle versus Hamming distance
In this section, we visually explore the degree which PGHash is consistent estimator of angular similarity. Specifically, let v, y E Rdd then we know by Theorem | that HPG (c. d) is an LSH for cos(xe: Ve). We demonstrate that in the unit vector regime, 0g = arccos ccos (cos(Ee, Fey Yc)) an acceptable surrogate for 0 arccos(x. Y), where Y { and Y- {vr
Po 3
(a) c=
(b) c=10
(c) c=2
175
P ge
Compeee B
(d) c=)
(e) c=10
(f) c=
Figure 8: Angle/Hammmin Distance as a function of sketch dimension. The average Hamming distance between PGHashed fixed unit vector E 100 and collection of vectors y; E R 100 which form different angles with z. Increasing sketch dimension e smooths and reduces the variance of the scatter towards linear correlation. Furthermore, the Hamming scales linearly with c, improving discernibility. (a)-(c & (f)-(f) are independent series.
16

---

10
(a) 5 tables
(b) 10 tables
(c) 50 tables
Figure Angle/Hamming Distance as a function of tables The average Hamming distance between PGHashed fixed unit vector E IR '0 and a collection of vectors y/ I0000 which form different angles with x and fixed sketch dimension c = 10. Increasing the number of tables reduces variance.
C Additional proofs
Fact 3. Let I. y. 01,62 62 d-dimensional unit vectors such that that the e, lie on the unit circle contained with the plane spanned by x and (denoted as Szay) and 61 1 Consider the point v on Say such that the line through bisects the angle of the lines passing through a and y. Let
? = arccos(cos((,ee) e1)). Denote = arccos(cos((r, 4)). Then we may write x cos(1) + 0) + (1n(1) + 0)ez and cos(1) - 0)e: sin(1 0)e2.
C.1 Proof of Theorem 2
Proof. Let arccos(cos(z,, y)) where z, E Sd-1 and BTB. The cosine similarity between Ie = Br and By (for B correspondent to (d, cd-oolidg is expressible as
x BB By
x Ay
cos(Eer Mc)
(x B (r)
B By)
(a (y) Ay)
Consider the SVD B - UDV where U and V are orthogonal and D x rectangular diagonal matrix. We have then that containing squared D; along the diagonal and everywhere else.) Notice that choice of U nor the ordering of columns 2 of V affects the angle calculation in Equation First, we re-order the columns of V so as order the diagonal entries d; of D (i.e., the squared singular values) in decreasing order, and abuse of notation set B 2ं DV Denoting X; d:/di for 1 S i S we have that Bvj- = dzeç (By construction of B we have that d, E {d 0}, therefore, X E {1,03)
B
VD²VT. (Here Đ is now a square diagonal matrix
Consider B acting sd-11, ; it scales each dimension by Aς thus (as with any linear transformation of a sphere), transforms into an ellipsoid, with c principal axes determined by the e;- The greatest possible distance from the origin the ellipsoid B is while the shortest possible distance is Now consider the unit circle Sayy {o E span(æ, y) ||i|| = 1}. We have that BS2,9 C BSSd-1 n BU is an ellipse (since the intersection of an ellipsoid and plane is always an ellipse).
Choose unit w1 and uz belonging to Sz,y such that w1 1. W2. by By Fact we may parameterize cos(n ()w1 + sin(n 0)w, and y sin(n) + o)w, sin(n f)w2, where the angle made with Wi with the bisector of æ and y. By assumption, [| 2 a (the minimal (the maximal stretching factor
vectors
shrinking factor of on Sa.y) for some positive a. Denoting of B on S2,y), we have that the angle between Ba and By is upper-bounded by
a f(n) = arctan( Lan(n + 0)) arclann (an(1) - 0))
a
(2)
The numerator of df is 3(1 (1 B) sin (29) sin) where 8= ==a/> a/d. X. The derivative trivially dn if) 3 0, (2) 1, (3) 0. (1) will not occur as we assume that Sa,y does not contain O-eigenvector A = BT B. (2) can only occur if A is multiple of the identity matrix (which is not by construction), and (3) implies that and are parallel, in which case their angle will not be
17

---

distorted. Aside from these pathological cases, the critical points occur at 1) = 0, 7/2. We have then that cos(Br, By) lives between cos(f(0))
1-0² tan & I+p tan and cos (((T))) tan 0 4
tan g² -
Remark. The constant | has an enormous influence on the bounds in Theorem 2 The smaller the a (i.e., shrinking of [|]]]) the greater the bounds distortion. Although we have imposed constraints on 2; y, we treat them as any possible pair of random unit vectors, then the w in Sy.y effectively becomes random unit vector as well. We exactly characterize the distribution of B where X denotes a random variable which selects a d-dimensional unit vector uniformly at random.
C.2 Proof of Proposition 1
Proof. We can sample d-dimensional vector uniformly at random from the unit sphere 5 by drawing a d-dimensional Gaussian vector with iid entries and normalizing. Let us represent this as the random variable X Z' Z' where Z' ~ NO, Ta)- Consider (c, do-ooldiing matrix B. i.e., a d/c horizontal stack of c x identity matrices (Iet us assume cld). We are interested in determining the distribution of ||BX|| For ease of notation, consider the permutation Z of Z' Since this permutation representable as an orthogonal
where Z, = Z (1 [1= (mod d/e)'
matrix P (and multi-variate Gaussians are invariant distribution under orthogonal transformationss) may instead consider X P(Z'/ 2 Z'I1² 2/1 We may write the norm- norm-squared
| (21 + Zajo)
+ (Zafo+1 + ... + Zzaja)² .... (Z(o=1((//))+ + + Za)²
2
||
|||
(3)
Consider the first term (71 +.++++2.0 +Zarc) First note that for any unit vector u, the distribution of
(v 2)²
1|
does not depend on choice of u. Consider the unit vector u' then which contains vd/cin the first d/c equivalent to d/ times our first term. Ofurse, since (c) 2)²
entries and otherwise. Then (a" z)²
1
has the same distribution (u' 2)a have by transitivity that z & (n/q) (Z.4..22a.o)) ||
1| 1
1
By extending the discussion above to the other terms, and by their independence with respect to rotation of Z (since their numerators contain squared sums of mutually disjoint Z coordinates), we have that
|BXI| d Zi + 2 + &Zaae + Z3
1|
The distribution of 27+722,0 72a + + is well-known follow a Beta( 5, - distribution 13
1|
In totality, ||BX|| d Beta( d However, we will move to the four parameter description of this scaled Beta distribution which is Beta( - 0, L) The pdf and expected value follows by the usual statistical descriptions of this distribution, which can also be found in [13].
Figure 10 depicts how (d, folddngs affect the norms of unit vectors.
D Additional theory
In this section, we provide additional theory relevant to SimHash.
We present several well-known results regarding SimHash.
Proposition 2 (SimHash estimation). Let x, y S, i.e., unit d-dimensional vectors. Denote 6 arccos( cos(s, Let u E S be a unit vector drawn uniformly at random (according to the Haar measure, for example). Then,
0
Pr[sgn(u] Tx) + sgn(v) T b)
(5)
π
18

---

Distribution folded norms
2300
Requency
1500
1000
0.5 1.0
1.5 [[vi11
2.5
3.0
Figure 10: Distribution of folded norms. 100k randomly drawn unit vectors (d= 128) are folded down to length 16 by are usual (d, c)-foliing procedure. Depicted is binned histogram of the norms. As predicted by the statistical description of [[XX] where X a randomly drawn unit vector, the mass is centered 1, i.e., most exceed 12811, although the theoretical support is (0, 8): this concurs with the pdf.
preserved. Empirically observe that folded rarely
Proof. We reproduce the argument of 12 We have by symmetry that Pr(sgn(v x)) + sgn((" y) = 2Prlo > 0, v < 0j. The set 2 {u E Sd Tux > 0, S 0} corresponds to the intersection of two half-spaces whose dihedral angle (i.e., angle between the normals of both spaces) is exactly 0. Intersecting with the d-dimensional unit sphere produces gives a subspace of measure 2n therefore, 2Pr(u x > 0, < x. completing the argument.
Corollary Let instead a d-dimensional random Gaussian vector with iid entries N(O,1) 1). Then for x,
Rd.
Pr|sgn(v x) + sgn(v" T y)]
(6)
Proof. Randomly drawn, normalized Gaussian vectors are well-known to be uniformly distributed on the unit sphere.
In the setup above, let the X be random variable which returns I if x and have differing signs when taking standard inner product with a randomly drawn Gaussian w. Let X1, X2, ........ X, represent sequence of independent X events. Then,
Proposition 3. El E -1 1- and V[X] (1- 2)
Given that PGHash is equivalent to a SimHash over (d. co-foliings of Rd the variance reduction we observe by using multiple tables (Figure is explainable by Proposition 3
19


Reviews:
[{"review_id": "WVXi07IpC2", "reviewer": "Reviewer_Q7Pn", "summary": "**Main Idea** : If you are using LSH based sparsity, then why not project the weight matrices down using random / even structured projections and then use the LSH. \n\n**Potential applications**: device-based training / inference (resource-constrained) / federated learning. \n\nThe authors provide theoretical analyse of proposed PGHash and provide some experiments in single and multi-device settings. \n\n**[UPDATE AFTER REBUTTAL]** \nSorry for the late response. Due to unavoidable reasons, i could not get to this earlier. \n\n1. As agreed by authors on most questions on theoretical results, there were issues in the provided theory. While authors provide quick fixes to the theorems. In order to evaluate these fixes, one would have to reconsider the entire theory again. \n\n2. I do not agree with authors argument in favor of structured matrix B. I still believe it has issues and detailed proof must be provided to support it. I am afraid structured matrix B will kill any best bounds you can give. For example, in the example I gave in the review, how can \none ever cope up with the error caused there. For such as example, the bounds have to be trivial [-1,1] for cosine similarity. \n\n3. I am skeptical with the statement that \"The block identity structure solves the following problem: given a fixed $c \\times d$ matrix $B$ with $c<<d$, produce a sequence of $c \\times c$ matrices $S_i$ for $1\\leq i \\leq n$ such that the $S_iB$ resemble random $c \\times d$ Gaussian matrices\".  \"Resemble\" is not what we are looking for in the theory. **Would request ACs to take a serious look at the theory to confirm its correctness.**\n\nAbout experiments, I would request the authors to show results after the peak as well to get the full picture. \n\n\nI will be maintaining my score for the submission in its current form.", "questions": "**Theoretical soundness of approach and provided theorems.**\n\n1. Theorem 1 does not provide any information on the approximation. \n\n     The statement of theorem 1 is obvious as the similarity is defined as cosine similarity over folded vectors. After folding, PGhash is just Simhash so it is not surprising that it is a LSH on folded vectors\n\n2. Theorem 2 does provide some information. But has issues.\n\n   a). The $\\alpha$ is infimum of a set and can be equal to $0$ even if the set itself does not contain $0$. (on a related note, i believe the definition of $\\alpha$ can be improved in terms of how the set is written). Is it that $\\alpha = inf \\\\{ ||Bv|| , v \\in S_{x,y} \\\\}$ ? I assume this is what the authors meant. \n\n   b) If $\\alpha$ is 0, then the range of distortion is trivially -1,1\n\n   c) Proposition 1 is used to comment on the value of $\\alpha$ but it's not exactly clear how they are related, the set used in proposition 1 is that of unit sphere in R^d and that in theorem 2 is linear span of $x$ and $y$ where coefficients are from a unit circle . Clearly the two sets are very different. Also, E||Bu|| = 1 cannot be directly extended to understand the range of $\\alpha$ as $\\alpha$ is infimum of the $ \\\\{ ||Bv|| , v \\in S_{x,y}\\\\}$ \n\n   d) It is possible that writing issues in this section might have mislead me a bit. It would be good to get clarification from authors. \n\n   e) The structured form of matrix B is actually troublesome for theoretical guarantees. Consider a simple example , $d=20$, $c=5$, the vectors be,  $S = \\\\{ [x_1, 0,0,0,0, x_2, 0,0,0,0, x_3, 0,0,0,0, x_4, 0,0,0,0] | x_1+x_2+x_3+x_4 = 1 \\\\}$.  Note that two vectors from S can have cosine similarities that vary from $-1$ to $1$ but under PGHash , they will always have similarities of $1$. \n\n\n\n**Experiments:**\n\n1. Both from Figure 5 and Figure 4, it seems like higher number of devices causes PGHash to perform worse. Is there any reason why this occurs?\n2. I do expect that using projections to reduce size of weight matrices is going to lose accuracy. However, the hope for this paper is that the trade-off only significantly kicks in after large amounts of compression.\n\n    a. The plots provided for Amazon-670K and Delicious-200K are not shown to convergence. So it is impossible to know what the eventual loss of accuracy is. \n\n    b. With multi-device settings, the plots already show that PGhash is losing accuracy as compared to baseline. Given that multi-device setting is the proposed application area of PGhash, it is unclear if the overall proposal has value.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The idea of using projections before LSH might be useful in practice depending on the sensitivity of the model to the compression.", "weaknesses": "See question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. Below, we address all questions and concerns. \n\n\n## Theory\n\n\n> [Q1]: Misleading impression of Theorem 1 being the main result\n\nTheorem 1 and its corollary are warmup results intended to illustrate a simple connection between traditional SimHash and our PGHash, while Theorem 2 and Proposition 1 are our core and novel contributions. In our revision, we rename Theorem 1 as Fact or Proposition.\n\n---\n\n> [Q2(a)]: $\\alpha$ in Theorem 2 might be 0\n \nIndeed, our intended definition is $\\alpha=\\inf\\bigl(||Bv||^2: v\\in S_{x,y} \\bigr)$. The observation that $\\alpha$ might be 0 within our current definition is true and a fixable caveat in our formulation. To remedy this, we now assume that $\\alpha=\\inf\\bigl(||Bv||: v\\in S_{x,y} \\bigr)>0$, which trivially absorbs assumption of no 0-eigenvectors in $S_{x,y}$ and eliminates the possibility of infinitesimally-vanishing norm. This updated definition and assumption of $\\alpha$ will be included in the revision.\n\n> [Q2(b)]: If $\\alpha$ is 0, then the range of distortion is [-1,1]\n\nCorrect, if $\\alpha$ is 0 then the range of distortion is trivially [-1,1]. We assume that $\\alpha>0$ to provide meaningful distortion bounds in Theorem 2. Empirically, grouping dissimilar vectors as similar is statistically rare for randomly drawn unit vectors (Figures 2 and 8). **Furthermore, in practice it doesn't hinder training**: this simply results in less pruning since more weight vectors are deemed similar to the input and therefore updated.\n\n---\n\n> [Q2(*c*)]: Relation of Proposition 1 to $\\alpha$\n\nFirst, we clarify that $S_{x,y}$ is defined as the set $\\bigl( v\\in \\mathrm{span}(x,y): ||v||=1\\bigr)$. This was a technical typo that should resolve much of the confusion on relating Proposition 1 and Theorem 2. \n\nIt is useful to know how the norms of arbitrary unit vectors are distorted by $B$, which, according to Proposition 1, follows a generalized beta distribution with concentrated mass around 1 (see Figure 10 for a simulation). Indeed, $S_{x,y}$ is not the unit sphere, but since $x$ and $y$ are assumed to be random unit vectors ($\\alpha>0$ is assumed), Proposition 1 provides intuition on how we probabilistically expect random, unit linear combinations of $x$ and $y$ to shrink/stretch under $B$.\n\n---\n> [Q2(e)]: Justifying the efficacy and structure of $B$\n\nThe $B$ matrix we suggest,\n1. Is an **effective discriminator** of angular similarity according to Figures 2 and 8.\n2. Its **simple structure** makes it possible to analyze the distribution of $||Bv||^2$.\n3. For instances where dissimilar vectors are grouped as similar (like the example you provided), it simply results in an increased number of weights to train, which according to Figure 6(a) is **never a significant amount.**\n\nThe block identity structure solves the following problem: given a **fixed** $c \\times d$ matrix $B$ with $c<<d$, produce a sequence of  $c \\times c$ matrices $S_i$ for $1\\leq i \\leq n$ such that the $S_iB$ *resemble* random $c \\times d$ Gaussian matrices.\n\nIt is clear that we should have $S_i\\sim \\mathcal{N}(0,I_c)$. Since the standard normal distribution is invariant under orthogonal transformations, $B$ should contain blocks of orthogonal matrices, i.e., $B=[O_1|O_2|\\cdots|O_{d/c}]$, where the $O_i$ are orthogonal matrices. Since the $B$ and $O_i$ are fixed, for any Gaussian $S$ the blocks $\\{SO_i\\}$ are always correlated, so examples of dissimilar vectors grouped as similar **will always exist** and thus we simply choose $O_i=I_c$. \n\n---\n\n## Experiments\n\n> [Q2(b)] Novelty of PGHash and performance versus baselines\n\nThe novelty of our work is that PGHash is the first:\n1. On-device and memory-efficient LSH approach,\n2. Privacy-preserving and personalizable LSH method in the distributed setting.\n\nAs mentioned by the reviewer, it is common to \"expect that using projections to reduce size of weight matrices is going to lose accuracy\". Even still, we empirically showcase:\n* PGHash matches (Figure 5 for Amazon) or is competitive with full-memory baselines **using only 6.25% of the full weight matrix**.\n* PGHash matches baselines while allowing on-device, private LSH analysis with **personal compression rates and hash code lengths** (something that has never been allowed previously).\n\n---\n\n> [Q1] Performance with higher numbers of devices worse than single device?\n\nSlightly degraded performance with more devices is typical and expected in FL since we are averaging gradients trained on partitions of the dataset. This is sub-optimal compared to optimizing over the entire dataset (especially with large datasets like ours). Even still, final accuracy for Delicious degrades by a negligible amount (<1%) in the FL setting. Nonetheless, \n- Peak accuracy should also be taken into consideration when evaluating performance, and multi-device achieves a **higher** peak accuracy on Delicious.\n- In contrast to Delicious, multi-device **performs better** on Amazon for both peak and final accuracy (+4.5% as shown in Figure 5).\n\n> [Q2(a)] Convergence of Amazon and Delicious accuracies\n \nPeak accuracies for our given architecture (with 1 device) are approximately 45% and 33% for Delicious and Amazon respectively. These are the values within SLIDE [R1] and validated within our own work. For Delicious200K, peak accuracies are reached between 2-3 thousand iterations. This is why [R1] only plots the first 3,000 iterations within their experiments. For Amazon, we ended our accuracy plots after peak distributed accuracy is achieved. What is important to show, which we do in Figures 4 and 5, is that **PGHash achieves peak distributed accuracy for Delicious and Amazon**. \n\n---\n\nThank you for your review. If we have addressed your questions, we would appreciate it if you would consider updating your score. If any other questions or concerns remain, please let us know.\n\n**References:**\n\n[R1] Chen, et al. \"Slide: In defense of smart algorithms...\" 2020."}, {"review_id": "L7alPXFTxx", "reviewer": "Reviewer_QaZe", "summary": "The paper proposes a family of hashing functions that reduces the memory cost. Let W be a weight matrix. It is observed that in many applications, one needs to draw a Gaussian matrix T and compute T * W when constructing hash tables. Also, given a query x, one needs to compute T * x which requires the storage of the entire matrix T. These two steps will be less practical on memory-limited devices. The main contribution of the work is a more efficient hashing scheme. The key idea is to perform a low-dimensional projection B of x on to dimension c, and use a smaller Gaussian matrix S. It is shown that the cosine distance on Bx preserves LSH property.", "questions": "see weakness", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "+ The problem and results are clearly presented. \n\n+ The saving of memory is important to many applications.\n\n+ The techniques are easy to follow.\n\n+ A set of experiments were included to support the theory.\n", "weaknesses": "- My primary concern is the novelty of the approach. It turns out that Theorem 1 is the main result of the paper, which shows that projection with the matrix B = [I_c | I_c | ... | I_c] would preserve cosine distance in the sense of LSH. I am however uncertain whether the design of B is novel, or has been considered before in a similar context. (I guess it appeared somewhere but I cannot recount.) I defer to authors' clarification and other reviewers' comments.\n\n- The parameter 'c' controls the new dimension, which is supposed to be lower bounded by some quantity relevant to d or the training size, or will change the performance of the similarity function Sim_c, but there was no such discussion or condition.\n\n- Algorithm 1 looks superficial and lacks guarantee.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We address all questions and concerns below. \n\n>My primary concern is the novelty of the approach. \n\nTo the best of our knowledge, **our LSH approach is novel** due to the following reasons:\n- Existing literature is not focused on the serial generation of pseudo-random projections, namely because there is no memory concern -- SLIDE [R1], Mongoose [R2], [R3], G-SLIDE [R4], etc., are designed for single-machine setups. \n- Projections over federated settings is a relatively underexplored setup -- Federated SLIDE [R5] performs LSH analysis of hashed client data at the server (and therefore, avoids memory constraints), which we seek to avoid due to privacy concerns. \n- Furthermore, our on-device approach allows for the personalization of LSH analysis by allowing devices to select their own LSH hyperparameters (which other approaches lack). \n\n> I am however uncertain whether the design of $B$ is novel, or has been considered before in a similar context.\n\nTo the best of our knowledge, the structure of our $B$ matrix is novel in the context of LSH methods. The design of $B$ comes from the consideration of a nontrivial problem: \n- Given a **fixed** $c \\times d$ matrix $B$ with $c<<d$, produce a sequence of  $c \\times c$ matrices $S_i$ for $1\\leq i\\leq n$ such that the $S_iB$ *resemble* random $c \\times d$ Gaussian matrices. Of course, it is not mathematically possible to obtain a sequence of independent, random Gaussian matrices given a fixed $B$, so we will try to produce near-Gaussian matrices. \n\nIt is clear that the $S_i$ should be $c\\times c$ random Gaussian matrices. Since a random variable $\\mathcal{Z}\\sim\\mathcal{N}(0,I_c)$ is invariant under orthogonal transformations, we should have $B=[O_1 | O_2 |\\cdots | O_{d/c}]$, where the $O_i$ are orthogonal matrices. \n\nWe set $O_i=I_c$ since: \n1. It is an **effective discriminator** of angular similarity according to Figures 2 and 8, \n2. Its simple structure makes it possible to analyze the distribution of $||Bv||^2$,\n3. For instances where dissimilar vectors are grouped as similar, it simply results in an increased number of weights to train, which according to Figure 6(a) is **never a significant amount**.\n\n---\n\n> The parameter 'c' controls the new dimension, which is supposed to be lower bounded by some quantity relevant to d or the training size, or will change the performance of the similarity function Sim_c, but there was no such discussion or condition.\n\nIn Proposition 1, the distribution of $||Bv||^2$ critically depends on the sketch dimension $c$. Namely, a higher value of $c$ (i.e., less aggressive compression) produces a generalized Beta distribution with less variance. The altered magnitude of vectors under the multiplication of $B$, i.e., $||Bv||^2$ will affect the extent of angle distortion presented in Theorem 2 (explained in lines 238-243), so the degree of distortion is affected by the sketch dimension $c$. \n\n---\n\n> Algorithm 1 looks superficial and lacks guarantee.\n\nTo the best of our knowledge, no LSH-based dynamic pruning approach, such as SLIDE [R1] or its predecessor MIPS-dropout [R2], G-SLIDE [R3], or Federated SLIDE [R4] contains a guarantee because it is difficult to theoretically establish a convergence rate when the parameters are dropped out in a structured, continually-changing manner as opposed to, say, random dropout. \n\nSimilar to these other works, we are focused on the similarity estimation/sensitivity of our LSH strategy. Although this is beyond the purview of our work, a starting point for establishing the convergence of adaptive dropout algorithms is to use the theory established by [R6], which demonstrates that federated training on heterogeneous subnetworks can succeed if the overlap of parameters from round-to-round and client-to-client is significant enough.\n\n---\n\nThank you for your review. If we have addressed your questions, we would appreciate it if you would consider updating your score. If any other questions or concerns remain, please let us know. \n\n**References:**\n\n[R1] Chen, Beidi, et al. \"Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems.\" (2020)\n\n[R2] Chen, Beidi, et al. \"Mongoose: A learnable lsh framework for efficient neural network training.\" 2020.\n\n[R3] Spring, Ryan, and Anshumali Shrivastava. \"Scalable and sustainable deep learning via randomized hashing.\" (2017)\n\n[R4] Pan, Zaifeng, et al. \"G-SLIDE: A GPU-Based Sub-Linear Deep Learning Engine via LSH Sparsification.\" (2021)\n\n[R5] Yan, Minghao, et al. \"Distributed slide: Enabling training large neural networks on low bandwidth and simple cpu-clusters via model parallelism and sparsity.\" (2022).\n\n[R6] Zhou, Hanhan, et al. \"Federated Learning with Online Adaptive Heterogeneous Local Models.\" (2022)"}, {"review_id": "i9Vp50b8N0", "reviewer": "Reviewer_7yAa", "summary": "This paper presents a novel framework for on-device locality-sensitive hashing (LSH) that addresses the limitations of existing algorithms in terms of computational efficiency, memory constraints, and privacy concerns. The authors introduce a new family of hash functions that enables each device to generate hash tables independently, without relying on a central host. This approach allows for personalized and private LSH analysis while conserving memory and computational resources.", "questions": "Is there any intuition on the choosing between PGhash version of DWTA and SimHash in practice?", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The proposed PGhash family is novel. It addresses computational and memory challenges introduced by repeated randomized projection of full-layer weights in distributed settings.\n\n2. The authors claim to have proven several statistical and sensitivity properties of their PGhash functions, ensuring the reliability and robustness of the proposed framework. They also present experimental results that demonstrate the competitiveness of their approach in training large-scale recommender networks compared to existing LSH frameworks that assume unrestricted on-device capacity.\n\n3. The paper is well-written. The theoretical formulation is well-organized.", "weaknesses": "NA", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. We address all questions and concerns below. \n\n---\n\n> Is there any intuition on the choosing between PGHash version of DWTA and SimHash in practice?\n\nDWTA and SimHash approximate similarity in fundamentally different ways:\n\n* DWTA computes similarity between vectors based on their relative attributes (similar ordering of indices by magnitude). \n* SimHash approximates cosine similarity between vectors.\n\nIn practice, selection of a PGHash version of DWTA versus SimHash stems from the desired speed of LSH analysis as well as the label sparsity of the data.\n1. Speed: DWTA is faster than SimHash (one of the fastest known hashing schemes) since matrix multiplication is not needed. DWTA can also generate multiple hashes at once (SimHash requires multiple random projections to get multiple hashes).\n2. Label sparsity: We can further speculate on choice of hash based on some interesting empirical data: Table 4 in our supplemental material demonstrates that SimHash is inferior for training on Amazon-670K, and we also use require usage of DWTA to train over Wiki-325K (Figure 7). The average number of labels per sample are as follows, Delicious-200K: ~75 labels, Amazon-670K: ~5 labels, Wiki-325K: ~3 labels, which suggests that DWTA should be used when the expected number of labels per point is **extremely low.**"}]

Author rebuttal:
### Summary of Rebuttal:

**General Comments:** We thank the reviewers for their valuable feedback and questions on theory and experiments. 

**Reviewer highlights:**

Reviewer 7yAa believes that our "approach allows for **personalized** and **private** LSH analysis while conserving **memory** and **computational** resources," "the proposed PGhash family is **novel**, and that "the theoretical formulation is **well-organized**."

Reviewer QaZe remarks "the saving of memory is important to **many applications**" and that our "techniques are **easy** to follow."

Reviewer QZPn notes that our approach has several **potential applications** while also mentioning that "the idea of using projections before LSH might be **useful in practice** depending on the sensitivity of the model to the compression."

**Summary of Core Contributions:** We summarize our key contributions as follows: 
* We introduce a **novel** LSH family and framework for **dynamic pruning** of a massive final layer weight in a distributed setting. Our approach allows for serial generation of hash tables, enabling **memory** and **computationally efficient** on-device LSH analysis. Appealing to federated learning principles, PGHash-based LSH analysis is **personalizable** and **private**. 
* Our novel LSH family, PGHash, estimates angular similarity between "foldings"/deterministic hashings of the weight vectors and the layer input. We theoretically establish the sensitivity and statistical properties of PGHash, and empirically demonstrate it is a **good discriminator** of similarity over randomly-drawn unit vectors. 
* Our framework enables **competitive multi-device training** of a network on extreme multi-label datasets, Delicious-200K and Amazon-670K. Multi-device PGHash training:
    1.  **Matches** federated SLIDE training [1,5,6] of Amazon-670K, 
    2.  **Outperforms** single-device training of Amazon-670K, 
    3.  **Closely matches** the peak accuracies of SLIDE and federated SLIDE training on Delicious-200K. 
  
    The results above are accomplished all while storing **only 6.25%** of the final massive layer weight (a reduction of **tens of millions of parameters compared to SLIDE**). 

**Summary of Changes**: Guided by the helpful suggestions of our reviewers, our changes are as follows:
* Amended definition and assumption of $\alpha$ to improve readability and eliminate an edge case ($\alpha=0$) pertinent to Theorem 2. Core result and proof of Theorem 2 **are preserved.** 
* Corrected technical typo in the formulation of $S_{x,y}$ to stress that it should contain unit vectors. This correction is needed to appropriately link Proposition 1 and Theorem 2. Core result and proof of Theorem 2 + Proposition 1 **are preserved**. 

**References:**

[R1] Chen, Beidi, et al. "Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems." 2020.

[R2] Chen, Beidi, et al. "Mongoose: A learnable lsh framework for efficient neural network training." 2020.

[R3] Spring, Ryan, and Anshumali Shrivastava. "Scalable and sustainable deep learning via randomized hashing." 2017.

[R4] Pan, Zaifeng, et al. "G-SLIDE: A GPU-Based Sub-Linear Deep Learning Engine via LSH Sparsification." 2021.

[R5] Yan, Minghao, et al. "Distributed slide: Enabling training large neural networks on low bandwidth and simple cpu-clusters via model parallelism and sparsity." 2022.

[R6] Xu, Zhaozhuo, et al. "Adaptive Sparse Federated Learning in Large Output Spaces via Hashing." 2022.

Meta-review: The paper proposes a novel on-device LSH based approach for large scale distributed learning.  Reviewers generally liked the approach and fact that the paper solved a very important and real problem with a technique that seems truly scalable and practical. One reviewer did pointed some concerns with the formalism as well as some other baselines alternatives. The rebuttal  did address the concerns on writing.  It is clear that the proposed methodology is competitive with most existing works and solves the distributed learning while retaining the important piece of privacy, using very clever stitching of existing ideas. The formalism presented are also interesting.  As a result, the paper does cross the bar for publication.
Decision: Accept (poster)