Google Inc.

Xinnan Yu

Sanjiv Kumar

Ananda Theertha Suresh

Daniel Holtmann-Rice

Hugh Brendan McMahan

Ruiqi Guo

David Morris Simcha

Xiang Wu

Jakub Konecny

Dave Morris Bacon

Satyen Chandrakant Kale

Krzysztof Marcin Choromanski

Ankit Singh Rawat

Jiecao Chen

Dmitry Storcheus

Shanshan Wu

Enxu Yan

Afshin Rostamizadeh

Hugh Brendan Mcmahan

David Morris Bacon

The present disclosure provides systems and methods for communication efficient distributed mean estimation. In particular, aspects of the present disclosure can be implemented by a system in which a number of vectors reside on a number of different clients, and a centralized server device seeks to estimate the mean of such vectors. According to one aspect of the present disclosure, a client computing device can rotate a vector by a random rotation matrix and then subsequently perform probabilistic quantization on the rotated vector. According to another aspect of the present disclosure, subsequent to quantization but prior to transmission, the client computing can encode the quantized vector according to a variable length coding scheme (e.g., by computing variable length codes).

Systems and methods for communication efficient distributed mean estimation

Systems and methods for low bias negative sampling of classes according to the sampled softmax method are described herein. The systems and methods can include training a machine-learned model for classifying inputs into one or more classes of a plurality of classes, each of the plurality of classes having an associated class embedding in a plurality of class embeddings. The systems and methods can include selecting, by the one or more computing devices, one or more negative classes from the plurality of classes based at least in part on a probability distribution approximating a softmax distribution, wherein the probability distribution is determined based at least in part on a Random Fourier Features map.

Sampled softmax with Random Fourier features

Techniques of generating input for a kernel-based machine learning system that uses a kernel to perform classification operations on data involve generating unbiased estimators for gaussian kernels according to a new framework called Structured Orthogonal Random Features (SORF). The unbiased estimator Kto the kernel involves a linear transformation matrix Wcomputed using products of a set of pairs of matrices, each pair including an orthogonal matrix and respective diagonal matrix whose elements are real numbers following a specified probability distribution. Typically, the orthogonal matrix is a Walsh-Hadamard matrix, the specified probability distribution is a Rademacher distribution, and there are at least two, usually three, pairs of matrices multiplied together to form the linear transformation matrix W.

Structured orthogonal random features for kernel-based machine learning

A sparse dataset is encoded using a data-driven learned sensing matrix. For example, an example method includes receiving a dataset of sparse vectors with dimension d from a requesting process, initializing an encoding matrix of dimension k×d, selecting a subset of sparse vectors from the dataset, and updating the encoding matrix via machine learning. Updating the encoding matrix includes using a linear encoder to generate an encoded vector of dimension k for each vector in the subset, the linear encoder using the encoding matrix, using a non-linear decoder to decode each of the encoded vectors, the non-linear decoder using a transpose of the encoding matrix in a projected subgradient, and adjusting the encoding matrix using back propagation. The method also includes returning an embedding of each sparse vector in the dataset of sparse vectors, the embedding being generated with the updated encoding matrix.

Sparse recovery autoencoder

The present disclosure provides systems and methods that include or otherwise leverage use of a multiscale quantization model that is configured to provide a quantized dataset. In particular, the multiscale quantization model can receive and perform vector quantization of a first dataset. The multiscale quantization model can generate a residual dataset based at least in part on a result of the vector quantization. The multiscale quantization model can apply a rotation matrix to the residual dataset to generate a rotated residual dataset that includes a plurality of rotated residuals. The multiscale quantization model can perform reparameterization of each rotated residual in the rotated residual dataset into a direction component and a scale component. The multiscale quantization model can perform product quantization of the direction components of the plurality of rotated residuals, and perform scalar quantization of the scale components of the plurality of rotated residuals.

Multiscale quantization for fast similarity search

The present disclosure provides efficient communication techniques for transmission of model updates within a machine learning framework, such as, for example, a federated learning framework in which a high-quality centralized model is trained on training data distributed overt a large number of clients each with unreliable network connections and low computational power. In an example federated learning setting, in each of a plurality of rounds, each client independently updates the model based on its local data and communicates the updated model back to the server, where all the client-side updates are used to update a global model. The present disclosure provides systems and methods that reduce communication costs. In particular, the present disclosure provides at least: structured update approaches in which the model update is restricted to be small and sketched update approaches in which the model update is compressed before sending to the server.

Communication efficient federated learning

Implementations provide an efficient system for calculating inner products between high-dimensionality vectors. An example method includes clustering database items represented as vectors, selecting a cluster center for each cluster, and storing the cluster center as an entry in a first layer codebook. The method also includes, for each database item, calculating a residual based on the cluster center for the cluster the database item is assigned to and projecting the residual into subspaces. The method also includes determining, for each of the subspaces, an entry in a second layer codebook for the subspace, and storing the entry in the first layer codebook and the respective entry in the second layer codebook for each of the subspaces as a quantized vector for the database item. The entry can be used to categorize an item represented by a query vector or to provide database items responsive to a query vector.

Hierarchical quantization for fast inner product search

Systems and methods for evaluating a loss function or a gradient of the loss function. In one example embodiment, a computer-implemented method includes partitioning a weight matrix into a plurality of blocks. The method includes identifying a first set of labels for each of the plurality of blocks with a score greater than a first threshold value. The method includes constructing a sparse approximation of a scoring vector for each of the plurality of blocks based on the first set of labels. The method includes determining a correction value for each sparse approximation of the scoring vector. The method includes determining an approximation of a loss or a gradient of a loss associated with the scoring function based on each sparse approximation of the scoring vector and the correction value associated with the sparse approximation of the scoring vector.

Systems and methods for evaluating a loss function or a gradient of a loss function via dual decomposition

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for efficiently performing linear projections. In one aspect, a method includes actions for obtaining a plurality of content items from one or more content sources. Additional actions include, extracting a plurality of features from each of the plurality of content items, generating a feature vector for each of the extracted features in order to create a search space, generating a series of element matrices based upon the generated feature vectors, transforming the series of element matrices into a structured matrix such that the transformation preserves one or more relationships associated with each element matrix of the series of element matrices, receiving a search object, searching the enhanced search space based on the received search object, provided one or more links to a content item that are responsive to the search object.

Fast orthogonal projection

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for augmenting neural networks with an external memory. One of the methods includes receiving a plurality of high-dimensional data items; generating a circulant embedding matrix for the high-dimensional data items, wherein the circulant embedding matrix is a matrix that is fully specified by a single vector; for each high-dimensional data item, generating a compact representation of the high-dimensional data item, comprising computing a product of the circulant embedding matrix and the high dimensional data item by performing a circular convolution of the single vector that fully specifies the circulant embedding matrix and the high dimensional data item using a Fast Fourier Transform (FFT); and generating a compact representation of the high dimensional data item by computing a binary map of the computed product.

Growing community of inventors

Forest Hills, NY, United States of America

Xinnan Yu