   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 the use of {\em structured arrangements} through randomized {\em microbatches} of examples that are more likely to include similar ones. We make a principled argument for the properties of our arrangements  that accelerate the training and present efficient algorithms to generate microbatches that respect the marginal  distribution of training examples.   Finally, we observe experimentally that our structured arrangements accelerate training by 3-20\%. 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. 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 BID2 ; BID9 ; BID7 , users and videos from watch or ratings BID15 , words from co-occurrence frequencies in a corpus BID16 , and nodes in a graph from co-occurrence in short random walks BID19 . 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) ; BID7 ; BID16 ; BID18 .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) ; BID14 ; Salakhutdinov et al. (2007) ; BID11 ; BID16 . 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 BID8 and altering the distribution of training examples by gradient magnitude BID1 , negatives selection with triplet loss Schroff et al. (2015) , clustering BID10 and diversity criteria BID10 .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. 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. . 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).0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00Training ( 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 TAB2 for Jaccard LSH MIX, in Table 3 for (pure) Jaccard*, and in TAB6 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 0.00 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00Training ( 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.
Accelerating SGD by arranging examples differently The paper presents a method for improving the convergence rate of Stochastic Gradient Descent for learning embeddings by grouping similar training samples together. Proposes a non-uniform sampling strategy to construct minibatches in SGD for the task of learning embeddings for object associations.