Year: 2018

Abstract:
Metric embeddings are immensely useful representations of associations between entities (images, users, search queries, words, and more). Embeddings are learned by optimizing a loss objective of the general form of a sum over example associations. Typically, the optimization uses stochastic gradient updates over minibatches of examples that are arranged independently at random. In this work, we propose principled methods of structuring the arrangements of training examples aimed at accelerating the training. Our arrangements consist of randomized microbatches of examples from a distribution that is guided by the structure of the example associations but respects a specified marginal distribution of training examples. We present efficient microbatch generators and experimentally demonstrate training time acceleration of 3-30%. Structured arrangements emerge as a powerful and novel performance knob for SGD that is independent and complementary to other SGD hyperparameters and thus is a candidate for wide deployment.

heading: 1 INTRODUCTION
text: Metric embeddings of entities that are trained to capture example associations are common representations that also allow for inference of associations not present in the data. Embeddings are used in complex learning tasks or directly applied for similarity and recommendations tasks. Example usage domains includes embeddings of text document from occurrences of words Berry et al. (1995); Dumais (1995); Deerwester et al. (1990), users and videos from watch or ratings Koren et al. (2009), words from co-occurrence frequencies in a corpus Mikolov et al. (2013), and nodes in a graph from co-occurrence in short random walks Perozzi et al. (2014). The example associations may involve entities of the same type (word co-occurrences, video co-watch, social) or different types (such as users and products) and often are distilled by reweighing frequencies of raw interactions Salton & Buckley (1988); Deerwester et al. (1990); Mikolov et al. (2013); Pennington et al. (2014).
Embeddings are computed by minimizing a loss objective of the form of a sum over example associations. The optimization starts with random initialization followed by gradient updates. In modern applications, the objective can have billions of terms or more, and the de facto method at such scale is stochastic gradient descent (SGD) Robbins & Siegmund (1971); Koren (2008); Salakhutdinov et al. (2007); Gemulla et al. (2011); Mikolov et al. (2013). The terms (examples) are randomly grouped into minibatches. Gradient updates, that are equal in expectation to the full gradient, are then computed sequentially for each minibatch. SGD is much more efficient than working with full gradients and the minibatch size determines the amount of concurrency. There are numerous tunable parameters and methods aimed to improve quality and speed of convergence. Some notable recent work includes per-parameter tuning of the learning rate Duchi et al. (2011) and altering the distribution of training examples by gradient magnitude Alain et al. (2015), negatives selection with triplet loss Schroff et al. (2015), clustering Fu & Zhang (2017) and diversity criteria Zhang et al. (2017).
In this work we introduce principled schemes that control the arrangement of examples into minibatches. Note that arrangement tuning is separate and orthogonal to optimizations knobs that alter the distribution of training examples, learning rate, or minibatch size. The baseline practice of independent arrangements places examples into minibatches independently at random. This practice is supported by classic SGD convergence analysis and has the upside of controlling the variance of the stochastic gradients. We make a novel case here for an antithesis of independent arrangements
which we term coordinated arrangements. Coordinated arrangements are much more likely to place corresponding associations in the same minibatch. We show that coordination offers different upsides: At the micro level, updates are more effective in pulling vectors of similar entities closer. At a macro level, the examples in small fractions of epochs encode (in expectation) the similarity structure in the full set of example associations whereas independent arrangement disperse that information. This “self similarity” of the training sequence effectively allows a single epoch to act as multiple passes.
We specify coordinated arrangements through a distribution on randomized subsets of associations which we refer to as microbatches. Basic coordinated microbatches co-place corresponding associations to the maximum extent possible while adhering to the marginal distribution of training examples. Locality Sensitive Hashing (LSH) maps allow for refining our microbatches so that corresponding associations are more likely to be co-placed when the overall similarity of the entities is higher. The LSH maps we apply leverage some available coarse proxy of entity similarity. A readily available first-order proxy is the similarity of the sparse association vectors. Another proxy is an embedding obtained by a weaker model. We present efficient generators of basic and refined microbatches for both LSH functions. Finally, microbatches are independently grouped into minibatches of desired size, which allows us to retain the traditional advantages of independent arrangements at the microbatch level. This design enables us to tune the microbatches to the problem and even the stage of training.
We compare the effectiveness of different arrangements through experiments on synthetic stochastic block matrices and on recommendation data sets. The stochastic block data, with its simplicity and symmetry, allows us to factor out the potential effect of other optimizations. We learn that basic coordination is always beneficial earlier in training whereas LSH refinements are more effective later on. We obtain consistent 3%-30% reduction in training with respect to the independent arrangements baseline that holds across other training hyperparameters.
The paper is organized as follows. Section 2 presents necessary background on the loss objective we use in our experiments and working with minibatches with one-sided gradient updates. In Section 3 we define LSH microbatches and coordinated minibatch arrangements. In We report our experiment results comparing different arrangement methods on stochastic blocks and on recommendation data sets in Section 4. In Section 5 we examine properties of coordinated arrangements that are helpful for faster convergence. We conclude in Section 6.

heading: 2 PRELIMINARIES
text: Our data has the form of associations between a set F of focus entities and a set C of context entities. In practice, the focus and context entities could be the same type or even two representations of the same set (say words or images) or different types (users and videos). We use κij as the association strength between focus i and context j. In practice, the association strength can be derived from frequencies in the raw data or from an associated value (for example, numeric rating or watch time).
An embedding is a set of vectors fi, cj ∈ <d that is trained to minimize a loss objective that encourages fi · cj to be larger when κij is larger. For concreteness, we focus here on Skip Gram with Negative Sampling (SGNS) loss Mikolov et al. (2013). Examples of positive associations (i, j) are drawn with probability proportional to κij . Random associations are then used as negative examples Hu et al. (2008): Each positive example (i, j) is matched with a set of negative examples of i with random context entities and similarly j with random focus entities. The negative examples provide an antigravity effect that prevents all embeddings from collapsing into the same vector. We use the notation nij for respective weights of negative associations.
The SGNS objective is designed to maximize the log likelihood of these examples. The probability of positive and negative examples are respectively modeled using
pij = σ(fi · cj) = 1
1 + exp(−fi · cj) and 1− pij = σ(−fi · cj) =
1
1 + exp(fi · cj) .
The likelihood function, which we seek to maximize, can then be expressed as Πij p κij ij Πij(1 − pij) nij . We equivalently can minimize the negated log likelihood that turns the objective into a sum:
L := ∑ ij κij log pij + ∑ ij nij log(1− pij) .
The optimization is performed by random initialization of the embedding vectors followed by stochastic gradient updates. The stochastic gradients are computed for minibatches of examples that include b positive examples, where (i, j) appears with frequency κij/|κ|1 and corresponding sets of negative examples.

heading: 2.1 ONE-SIDED UPDATES
text: We work with one-sided updates, where each minibatch updates only its focus or only its context embedding vectors, and accordingly say that minibatches are designated for focus or context updates. One-sided updates are related to alternating minimization Csiszar & Tusnády (1984) and to decomposition-coordination approaches Cohen (1980). For our purposes, one-sided updates facilitate our coordinated arrangements and also allow more precise matching of corresponding sets of negative examples to positive ones. In a focus-updating minibatch, we will generate a random set of λ context vectors C ′ and for each positive example (i, j) we generate λ negative examples (i, j′) for j′ ∈ C ′. The focus embedding fi is updated to be closer to cj but at the same time repealed (in expectation) from C ′ context vectors. With applicable learning rate η, the update has the form:
fi ← fi − η∇fi log σ(fi · cj) + ∑ j′∈C′ log σ(−fi · cj′)  . Symmetrically, for a context-updating minibatch we use a random set of focus vectors F ′ as our negative examples and for each positive example (i, j) we perform the update cj ← cj − η∇cj ( log σ(fi · cj) + ∑ i′∈F ′ log σ(−fi′ · cj) ) .

heading: 3 MINIBATCH ARRANGEMENT SCHEMES
text: Minibatch arrangement schemes determine how examples are organized into minibatches of specified size parameter b. At the core of each arrangement scheme is a distribution B over subsets of positive examples which we call microbatches. Our microbatch distributions have the property that the marginal probability of each example (i, j) is always equal to κij/||κ||1. However, subset probabilities vary between schemes and within a scheme we generally will have different distributions Bf for focus and Bc for context designations. Minibatches are obtained from microbatches as specified in Algorithm 1 for focus updates (a symmetric construction applies to context updates). The input is a microbatch distribution Bf , minibatch size parameter b, and a parameter λ that determines the ratio of negative to positive training examples. We draw independent microbatches until we have a total of b or more positive examples. We then draw λ random contexts C ′ and generate λ negative examples (i, j′) for j′ ∈ C ′ for each positive example (i, j). When training, we alternate between focus and context updating minibatches.
Algorithm 1: Minibatch construction (Focus updates) Input: Bf , b, λ // Microbatch
distribution, size, negative sampling
P,N ← ∅ repeat X ∼ Bf ; P ← P ∪X until |P | ≥ b C′ ← λ contexts selected uniformly
at random foreach example pair (i, j) ∈ P do
foreach j′ ∈ C′ do N ← N ∪ {(i, j′)}
return P ∪N
The baseline independent arrangement method (IND) can be placed in this framework using microbatches that consist of a single positive example (i, j) selected with probability κij/||κ||1 (see Algorithm 2). With coordinated arrangements, the microbatch distribution depends on designation. Algorithm 3 generates basic coordinated microbatches (COO) for focus-updates. These microbatches have the form of a set of positive examples with a shared context.
Basic microbatches have the property that if κij ≤ κi′j and the positive example (i, j) is included in a basic microbatch then the microbatch would also include the positive example (i′, j). It is instructive to consider the special case of κ with all positive entries being equal: Basic microbatches with focus designation have the form of some context j, and all (i, j) with positive κij . Our basic microbatches maximize the co-placement probability of two examples with a shared context while respecting the marginal probabilities. A sym-
metric construction applies to context-update microbatches that maximize the co-placement of two
examples with a shared focus. We establish that our microbatch generator respects the marginal probabilities, that is, example (i, j) is included with probability ∝ κij : Lemma 3.1. A positive example (i, j) is included in a basic coordinated microbatch (Algorithm 3) with focus designation with probability κij/M and in a microbatch with context designation with probability κij/N , where M := ∑ hMh with Mh := maxi κih for context h and N := ∑ hNh with Nh := maxj κhj for focus h.
Proof. Consider focus updates (apply a symmetric argument for context updates). The example (i, j) is selected if first context j is selected, which happens with probability Mj/M and then we have u ≤ κij/Mj for independent u ∼ U [0, 1], which happens with probability κij/Mj . Combining, the probability that (i, j) is selected is the product of the probabilities of these two events which is κij/M .
We preprocess κ and precompute the per-context maxima so that we can efficiently draw a random context with probability proportional to the column maxima. We also generate an index for efficient retrieval, for context j and a threshold value T , of all entries i with κij ≥ T . The preprocessing is linear in the sparsity of κ. Note that it is typical in applications to preprocess the data, in particular, to obtain κ by aggregating and reweighing the frequencies of associations in the raw data. The additional overhead imposed by our preprocessing is minimal. We can observe that given this preprocessing, the microbatch generator is very efficient: It draws a context according to the distribution (which is O(1) operation) and then uses T to index into the start point in the sorted “column.”

heading: 3.1 LSH MAPS
text: Placement of (i, j) and (i′, j) in the same focus updating microbatch results in pulling fi and fi′ closer together (see the micro-level property highlighted in Section 5). This is helpful when the entities i and i′ are similar in that they have a close target embeddings. Otherwise, the update is anyhow countered by other updates and the placement have undesirable effect that it increases the microbatch size and may increase variance of the stochastic gradients. In particular, since a large microbatch is processed by consecutive same-designation minibatches, it increases the effective minibatch size to microbatch size. This suggests that it would be useful to tune the quality of co-placements so as to decrease unhelpful ones while retaining as many helpful ones as we can. We do this using locality sensitive hashing (LSH) to compute randomized maps of entities to keys. Each map is represented by a vector s of keys for entities such that similar entities are more likely to obtain the same key. We use these maps to refine our basic microbatches by partitioning them according to keys. The refined microbatches (COO+LSH) are smaller and of higher quality, with a larger fraction of helpful co-placements (higher “precision”) but also fewer helpful co-placements over all (lower “recall”).
Ideally, our LSH modules would correspond to the similarity captured by the target embedding. This however creates a chicken-and-egg problem as the target embedding is not available at the start of training and is what we want to compute. Instead, we use LSH modules that are available at the start of training and are only a coarse proxy of the target similarity. The coarse embedding can come from a weak signal evident from feature vectors, a weaker (and cheaper to train) model, or from a partially-trained model. We work with two LSH modules based on Jaccard and on Angular LSH. The modules generate maps for either focus or context entities which are applied according to the microbatch designation. We will specify the map generation for focus entities, as maps for context entities can be symmetrically obtained by reversing roles.
Our Jaccard LSH module is outlined in Algorithm 4. The probability that two focus entities i and i′ are mapped to the same key (that is, si = si′) is equal to the weighted Jaccard similarity of their association vectors κi· and κi′· (For context updates the map is according to the vectors κ·j): Lemma 3.2. Cohen et al. (2009)
Pr[si = si′ ] = ∑ j min{κij , κi′j}∑ j max{κij , κi′j} .
Our angular LSH module is outlined in Algorithm 5. Here we input an explicit “coarse” embedding f̃i, c̃j that we expect to be lower quality proxy of our target one. (In our experiments we use angular
LSH with a lower dimension SGNS model.) Each LSH map is obtained by drawing a random vector and then mapping each entity i to the sign of a projection of f̃i on the random vector. The probability that two focus entities have the same key depends on the angle between their coarse embedding vectors: Lemma 3.3. Goemans & Williamson (1995)
Pr[si = si′ ] = 1− 1
π cos−1 cossim(f̃i, f̃i′) ,
where cossim(v,u) := v·u||v||2||u||2 is the cosine of the angle between the two vectors.
We can always apply multiple LSH maps to further refine basic microbatches. Each application decreases the microbatch size and increases quality (similarity level of entities placed in the same microbatch). More precisely, with r independent maps the probability that two entities are microbatched together decreases to Pr[si = si′ ]r – thus the probability decreases faster when similarity is lower. The number of LSH maps we apply can be set statically or adaptively to obtain microbatches that are at most a certain size (usually the minibatch size). We can also increase the number as training progresses. For efficiency, we precompute a small number of LSH maps in the preprocessing step and randomly draw from that set. The computation of each map is linear in the sparsity of κ.
Algorithm 2: Independent microbatch Input: κ Choose (i, j) with probability κij/||κ||1; return {(i, j)}
Algorithm 3: Basic coordinated microbatches (Focus updates) Input: κ // Preprocessing: foreach context j do
Mj ← maxi κij // Maximum entry for context j Index column j so that we can return for each t ∈ (0, 1], P (j, t) := {i | κij ≥ tMj}.
// Microbatch draw: Choose a context j with probability Mj∑ h Mh Draw u ∼ U [0, 1] return P (j, u)
Algorithm 4: Jaccard LSH (Focus updates) foreach context j do // i.i.d Exp distributed
Draw uj ∼ Exp[1] foreach focus i do // assign LSH bucket key si ← argminj uj/κij return s
Algorithm 5: Angular LSH (Focus updates) Input: {f̃i} // coarse d dimensional embedding Draw r ∼ Sd // Random vector from the unit sphere foreach focus i do // assign LSH bucket key si ← sign(r · f̃i) return s

heading: 4 ARRANGEMENT METHODS EXPERIMENTS
text: We train embeddings with different minibatch arrangement methods: The baseline independent arrangements (IND) as in Algorithm 2, coordinated arrangements with basic microbatches (COO) as in Algorithm 3, and the following coordinated arrangements with LSH partitioned microbatches (COO+LSH): (i) Jaccard: single Jaccard LSH map, (ii) Jaccard*: repeated partitions until the microbatch sizes are capped by the minibatch size b and (iii) angular*: angular LSH with respect to a pre-computed d = 3 dimensional embedding, applied repeatedly to obtain microbatches of size that is capped by b. We also evaluate tunable arrangements (MIX) that start with COO, may switch to (one variant) of COO+LSH or to IND, and may switch from COO+LSH to IND. This MIX design allows us to benefit from a higher recall (albeit lower precision) of helpful co-placements (COO) being more effective in early training regime and also allows for IND arrangements in the late training regime after the coarse similarity proxy used in our LSH maps exceeds its utility. The (at most) two switch points of each MIX method are hyperparameters that were determined once via a grid search and then used across repetitions (generated synthetic data and splits for recommendation data). The coordinated arrangement methods we implemented are not meant to be a comprehensive coverage of our approach and were not even selected to maximize performance. Our intention is to present and evaluate a sampler of basic simple methods in order to provide usage examples, understand the
potential of coordinated arrangements, and develop an understanding of what methods are more effective in different training regimes.

heading: 4.1 STOCHASTIC BLOCKS DATA
text: We generated synthetic data sets using the stochastic blocks model Condon & Karp (2001). This allowed us to explore the effectiveness of different arrangement methods when we vary the number and size of blocks. The simplicity and symmetry of this data (parameters, entities, and associations) allowed us to compare different arrangement methods while factoring out other potential optimizations and methods geared for asymmetric data such as per-parameter learning rates or alterting the distribution of examples.
The parameters for the generative model are the dimensions n×n of the matrix, the number of (equal size) blocks B, the number of interactions r, and the in-block probability p. The rows and columns are partitioned to consecutive groups of n/B, where the ith part of rows and ith part of columns are considered to belong to the same block. We generate the matrix by initializing the associations to be κij = 0. We then draw r interactions independently as follows. We select a row index i ∈ [n] uniformly at random. With probability p, we select (uniformly at random) a column j ∈ [m] that is in the same block as i. Otherwise (with probability 1 − p) we select a uniform column j ∈ [n] that is outside the block of i. We then increment κij . The final association κij is the number of
times the interaction (i, j) was drawn. In our experiments we set n = 104, r = 107,p = 0.7 and B ∈ {10, 20, 50, 100}.

heading: 4.2 IMPLEMENTATION AND METHODOLOGY
text: Our implementation was in Python using the TensorFlow library Abadi & et al. (2015) and building on the word embedding implementation of Mikolov et al. (2013)1 except that we used our methods to specify minibatches. The implementation included a default bias parameter and we trained embeddings with and without the bias parameter. The relative performance of arrangement methods was the same but the overall performance was significantly better with the bias parameter. We therefore report results of embeddings with bias parameters (updated in a two-sided manner). We used fixed and polynomially-decaying uniform learning rate with parameters that were tuned to perform well on the baseline independent arrangements and used with all arrangement methods. We worked with minibatch size parameter values b ∈ {4, 64, 246} (recall that b is the number of positive examples and λ = 10 negative examples are matched with each positive example), and embeddings dimension d ∈ {3, 5, 10, 25, 50, 100}.

heading: 4.3 QUALITY MEASURES
text: We use two measures of the quality of an embedding with respect to the blocks ground truth. The first is the cosine gap which measures average quality and is defined as the difference in the average cosine similarity between positive examples and negative examples. We generate a sampled set T+ of same-block pairs (i, j) as positive test examples and a sampled set T_ of pairs that are not in the same block as negative test examples and compute
1 |T+| ∑
(i,j)∈T+
cossim(fi, cj)− 1 |T−| ∑
(i,j)∈T−
cossim(fi, cj) . (1)
We expect a good embedding to have high cosine similarity for same-block pairs and low (around 0) cosine similarity for out of block pairs. The second measure we use, precision at k, is focused on the quality of the top predictions and is appropriate for recommendation tasks. For each sampled representative entity we compute the entities with top k cosine similarity and consider the average fraction of that set that are in the same block.

heading: 4.4 STOCHASTIC BLOCKS RESULTS
text: Representative results for d = 50, b = 64, and varying block sizes (B = 10, 20, 50, 100) are reported in Figure 1 (precision quality measure) and in Figure 2 (the cosine gap quality measure). For each configuration we show how quality increases in the course of training and also zoom on the early part of training. The x-axis in these plots shows the amount of training in terms of the total multiplicity of positive training examples that were used for gradient updates. Respective results for other minibatch sizes (b = 4 and b = 256) are reported in Appendix A.
We can observe that across all block sizes B and for the two quality measures our coordinated arrangement methods result in faster convergence than the baseline IND method.
The different COO+LSH methods trade off the microbatch size (recall of helpful co-placements) and co-placement quality (precision). We observe that the sweet spot for this tradeoff varies for different regimes in the training. In particular, higher recall is beneficial early on: When zooming on early training we see that COO (that has the largest recall) is dominant in the very early regime but may deteriorate later, in particular for larger blocks (B = 10) (that yield even larger basic microbatches).
Jaccard COO+LSH that uses a single map still generates large microbatches in particular with larger blocks but when used as part of a MIX (start with COO and ends with IND) the overall training is faster that any of the components alone. We can also see that the switch point for IND occurs in early-mid training and that the training gain obtained before that point is retained.
The Jaccard* and angular* COO+LSH methods which cap the microbatch size by the minibatch size perform well for b = 64 and for b = 256. For b = 4, they are outperformed in early training by COO
1https://github.com/tensorflow/models/blob/master/tutorials/embedding/ word2vec.py
(which provides a higher “recall” of helpful co-placements) and overall it is outperformed by MIX that start with COO continues with COO+LSH with a single Jaccard map, and ends with IND. The additional results reported in Appendix A for minibatch size parameters b = 4 and b = 256 indicate that (as expected) the relative advantage of the coordinated methods increases with minibatch size and consistently result int training gains of 5-30% over the baseline IND arrangements.
In Appendix B we consider training embeddings with different dimensions: We observe the same relative performance of arrangement methods as reported for d = 50. We also see that the peak quality is lower for d = 3, which justifies its use as a “coarse” proxy with angular LSH.

heading: 4.5 RECOMMENDATION DATA SETS AND RESULTS
text: LSH 0.75× peak 0.95× peak 0.99× peak %gain ×106 %gain ×106 %gain ×106 AMAZON: Gain of COO+LSH over IND (peak=0.33) Jac 4.29 3.50 6.86 5.83 11.02 7.17 Ang 10.00 3.50 13.38 5.83 16.04 7.17 MOVIELENS1M: Gain of MIX over IND (peak=0.40) Jac 2.13 1.41 0.58 1.73 1.55 1.93 Ang 4.96 1.41 8.67 1.73 11.92 1.93
retains only positive ratings and reweighs to prevent domination of frequent entities.
We created a test set T+ of positive examples by sampling 20% of the non zero entries with probabilities proportional to κij . The remaining examples were used for training. As negative test examples T− we used random zero entries. We measured quality using the cosine gap equation 1 and show results averaged over 5 random splits of the data to test and training sets and 5 runs per split. The MIX and COO+LSH Jaccardwere the respective best performers on MOVIELENS1M and AMAZON. Training gains (d = 50) with respect to the IND baseline are reported in Table 1. We observe consistent reduction in training which indicate that arrangement tuning is an effective tool also on these more complex real-life data sets.

heading: 5 EXPLAINING THE UPSIDE OF COORDINATION
text: We highlight two properties of coordinated arrangements that are beneficial to accelerating convergence: A micro-level property that makes gradient updates more effective by moving embedding vectors of similar entities closer and a macro-level property of preserving expected similarity in fractions of epochs.
�������
������
�����
����
��
��� ����
�� �� �� �� �� ���
�� ���
�� �� �
�� ������
�������� ��������
updates on corresponding examples (1, j) and (2, j) is performed with the same current parameters cj , which happens with COO (and with full gradients) but less so with IND arrangements that on average place the two examples half an epoch apart. Figure 3 shows the expected increase in cosine similarity E [cossim(f ′1,f ′2)− cossim(f1,f2)] for learning rates η = 0.02, 0.05 when the vectors f1, f2, and c are independently drawn from a product distribution N (0, 1)d of independent Gaussians.
Self similarity Coordinated arrangements preserve information on entity similarity in fraction of epochs. More formally, consider for two entities the weighted Jaccard similarity computed from examples in a small stretch of training that includes a very small number of examples with each entity. With COO, the expected similarity is equal to that of the full vectors whereas with IND, the similarity information disperses rapidly. This is because COO uses coordinated samples which maximize preserved similarity for the marginal distribution Cohen et al. (2009). It is instructive to consider two focus entities with Jaccard similarity J and M contexts with positive κij = c > 0. An α 1 fraction of an epoch will on average include αM sampled contexts from each focus entity. When the samples are independent then the sets would be highly dissimilar even when J is close to 1. When the samples are coordinated then the expected similarity in the sample corresponds to the similarity of the original vectors. We next demonstrate the self similarity quality experimentally with stochastic block matrices. We select small sets of positive training examples using independent and coordinated sampling schemes according to the same per-entity marginal distributions. We then train with this small set on multiple epochs until convergence as a way to gauge the “information” each set provides and its effect on training speed. We sample T = 5, 10, 15, 20 example interactions from each row (for focus updates) and symmetrically from each column (for context updates) of the association matrix. With independent sampling we select T independent examples for each row i by selecting a column j with probability κij/||κi·||1. For coordinated sampling we repeat the following T times. We draw uj ∼ Exp[1] for each column and select for each i column arg maxj κij/uj . Clearly the marginal distribution is the same, as the probability that column j is selected for row i is equal to κij/||κi·||1. Symmetric schemes apply to columns. We trained embeddings (with IND arrangements) on these smaller sets of examples on otherwise identical setups. Training was one-sided and alternated on each minibatch with row samples used for updating row embeddings and column samples for updating column embeddings. Representative results (b = 4) are reported in Figure 4. We observe that the coordinated selection of training examples consistently attains faster convergence in the earlier epochs. With fewer examples per entity, coordinated selection also had a higher peak quality than the respective independent selection. With more examples and larger blocks, the coordinated selection peaked lower, due to loss of the multi-hop expander structure.

heading: 6 CONCLUSION
text: We consider embedding computations with stochastic gradients and establish that the arrangement of training examples into minibatches can be a powerful performance knob. In particular, we introduced coordinated arrangements as a principled method to accelerate SGD training of embedding vectors. Our experiments focused on the popular SGNS loss and our methods were designed for pairwise associations. In future we hope to explore the use of coordinated arrangement with other loss objectives, deeper networks, and more complex association structures.

heading: A ADDITIONAL RESULTS FOR STOCHASTIC BLOCKS
text: We report here results for minibatch size parameter b = 4 and b = 256 for the same set of arrangement methods and combinations as reported for b = 64 in Section 4.4 (dimension d = 50 and block sizes B = 10, 20, 50, 100). Convergence with the precision quality measure is shown in Figure 5 (b = 4) and Figure 6 (b = 256). Convergence for the cosine gap quality measure are shown in Figure 7 (b = 4) and Figure 8 (b = 256). We observe that the training gain of coordinated arrangements over the baseline IND increases with minibatch size. The methods that cap the microbatch size by the minibatch size (Jaccard* and Angular*) perform much better with larger minibatches, as larger minibatches allow for a higher recall of helpful co-placements. In particular we can see that in early training on small minibatches (b = 4) these methods are outperformed by COO (which produces our largest (and unrefined) microbatches).
We quantify the gains of different methods over the baseline IND arrangements in the following tables. Results for precision at k = 10 are reported in Table 2 for Jaccard LSH MIX, in Table 3 for (pure) Jaccard*, and in Table 4 for angular* LSH MIX(where angular LSH is applied with respect to a d = 3 embedding). Results for cosine gap are reported in Table 5 for Jaccard LSH MIX and in Table 6 for angular* LSH MIX.
The tables report results for different minibatch sizes b and block sizes B. In each table we list the peak quality (cosine gap or precision) of the respective coordinated method and the amount of training used by IND to reach 0.75, 0.95, or 0.99 of that peak. We also show the reduction in training
that is gained by using the respective coordinated method instead of IND. Overall, we can see that the coordinated methods consistently had training gains of 5-30%. The gain is larger with smaller blocks and also with larger minibatches. The emphasized numbers in the Jaccard MIX and Jaccard* correspond to the method that provided the higher gain. We can see that Jaccard* performed better than Jaccard MIX for larger minibatch sizes.

heading: B EMBEDDING DIMENSION ANALYSIS
text: We report here results on the effect of the dimension on the embedding quality and convergence, focusing on training with IND arrangements. Figure 10 shows quality in the course of training for different dimensions for selected 104 × 104 stochastic block matrices. We show both the cosine gap and the precision with k = 10. Figure 9 shows the cosine gap and precision with k = 10 quality for the MOVIELENS1M and AMAZON data sets. The precision on the recommendation data sets is computed over focus entities (users) with at least 20 positive entries. The precision is the fraction of top k that are in the test set.
On all data sets we can observe slightly faster convergence with higher dimension in terms of number of training examples. The per-example training cost, however, increases much faster and proportionally to the dimension. This means that lower dimension is more effective in terms of computation in reaching a particular lower quality level. This supports methods like ours that leverage
coarser, lower quality, but much more efficient to compute embeddings to accelerate the training of more complex models.
On the recommendations data sets and for the precision quality measure on the stochastic blocks data we can see that the peak quality increases with the dimension. In particular, we can see that the peak quality for d = 3 is considerably lower than for d = 50. This means that higher dimension are effective in providing better peak quality. This supports our use in the experiments of the d = 3 embedding at the basis of angular* COO+LSH microbatches in order to accelerate the training of d = 50 embeddings, which are costlier to train but provide higher peak quality.

Review summaries:
The paper presents a method for improving the convergence rate of Stochastic Gradient Descent for learning embeddings by grouping similar training samples together. The basic idea is that gradients computed on a batch of highly associated samples encode related information in a single update that independent samples might take multiple updates to capture. These structured minibatches are constructed by independently combining subsets of positive examples called “microbatches”. Two methods are presented for constructing these microbaches; first by grouping positive examples by shared context (called “basic” microbatches), second by applying Locality Sensitive Hashing to further partition the microbatches into groups that are more likely to contain similar examples.