Google Inc.

Sanjiv Kumar

Henry Allan Rowley

Xiaohang Wang

Farhan Shamsi

Yakov Okshtein

Marcus Quintana Mitchell

Xinnan Yu

Ruiqi Guo

Jose Jeronimo Moreira Rodrigues

Debra Lin Repenning

Alessandro Bissacco

Ananda Theertha Suresh

David Morris Simcha

Sashank Jakkam Reddi

Satyen Chandrakant Kale

Xiang Wu

Daniel Holtmann-Rice

Ameesh Makadia

Jeff Huber

Hugh Brendan McMahan

Manzil Zaheer

Jun Wang

Justin Max Scheiner

Leon G Palm

Krzysztof Marcin Choromanski

Zhifei Li

Felix Chern

Jose Moreira Rodrigues

Minyoung Kim

Ankit Singh Rawat

Quan Geng

Jay Yagnik

Andrew William Senior

Ignacio Lopez Moreno

Yang Li

Gideon S Mann

Ming Zhao

Eugene Weinstein

Corinna Cortes

David Alexander Majnemer

Peter Hazlehurst

Kishore A Papineni

Blake Alan Hechtman

Jakub Konecny

Seungyeon Kim

Bo Dai

Si Si

Zachary Alan Garrett

Cho-Jui Hsieh

John Keith Rush

Jiecao Chen

Afshin Rostamizadeh

Dmitry Storcheus

Shanshan Wu

Philip Wenjie Sun

Dave Dopson

Zachary Burr Charles

Jeffery Pennington

Nikhil Prasad Bhat

Brian Kernighan

Francisco Jose Claude Faust

Sashank Reddi

Jeffrey Pennington

Aditya Krishna Menon

Pei-Hung Chen

Enxu Yan

Felix Ren-Chyan Chern

Andrew Thomas Davis

Andreas Veit

Jingzhao Zhang

Praneeth Karimireddy

Justin Scheiner

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing a kNN computation using a hardware accelerator. One of the methods includes obtaining a set of one or more query vectors; obtaining a set of database vectors; and performing, on a hardware accelerator and for each query vector in the set, a search for the k most similar database vectors to the query vector, comprising: computing, by circuitry of the hardware accelerator and for each query vector, a respective similarity value between the query vector and each database vector; and for each query vector, identifying, by the hardware accelerator and for each bin, (i) an index of the most similar database vector within the bin and (ii) the respective similarity value for the most similar database vector within the bin.

Approximate k nearest neighbors on hardware accelerators

Generally, the present disclosure is directed to systems and methods that perform adaptive optimization with improved convergence properties. The adaptive optimization techniques described herein are useful in various optimization scenarios, including, for example, training a machine-learned model such as, for example, a neural network. In particular, according to one aspect of the present disclosure, a system implementing the adaptive optimization technique can, over a plurality of iterations, employ an adaptive effective learning rate while also ensuring that the effective learning rate is non-increasing.

Controlled adaptive optimization

Generally, the present disclosure is directed to systems and methods of quantizing a database with respect to a novel loss or quantization error function which applies a weight to an error measurement of quantized elements respectively corresponding to the datapoints in the database. The weight is determined based on the magnitude of an inner product between the respective datapoints and a query compared therewith. In contrast to previous work, embodiments of the proposed loss function are responsive to the expected magnitude of an inner product between the respective datapoints and a query compared therewith and can prioritize error reduction for higher-ranked pairings of the query and the datapoints. Thus, the systems and methods of the present disclosure provide solutions to some of the problems with traditional quantization approaches, which regard all error as equally impactful.

Systems and methods for weighted quantization

A computing system and method can be used to implement a version of federated learning (FL) that incorporates adaptivity (e.g., leverages an adaptive learning rate). In particular, the present disclosure provides a general optimization framework in which (1) clients perform multiple epochs of training using a client optimizer to minimize loss on their local data and (2) a server system updates its global model by applying a gradient-based server optimizer to the average of the clients' model updates. This framework can seamlessly incorporate adaptivity by using adaptive optimizers as client and/or server optimizers. Building upon this general framework, the present disclosure also provides example specific adaptive optimization techniques for FL which use per-coordinate methods as server optimizers. By focusing on adaptive server optimization, the use of adaptive learning rates is enabled without increase in client storage or communication costs and compatibility with cross-device FL can be ensured.

Federated learning with adaptive optimization

Example quantization-based approximate nearest neighbors (ANN) search methods and systems (e.g., search engines) are tuned to perform at the speed-recall pareto frontier. With a desired search cost or recall as input, embodiments employ Lagrangian-based methods to perform constrained optimization on theoretically-grounded search cost and recall models. The resulting tunings, when paired with the efficient quantization-based ANN implementation of the embodiments, exhibit excellent performance on standard benchmarks while requiring minimal tuning or configuration complexity.

Tuning approximate nearest neighbor search engines for speed-recall tradeoffs via Lagrange multiplier methods

Generally, the present disclosure is directed to systems and methods that perform adaptive optimization with improved convergence properties. The adaptive optimization techniques described herein are useful in various optimization scenarios, including, for example, training a machine-learned model such as, for example, a neural network. In particular, according to one aspect of the present disclosure, a system implementing the adaptive optimization technique can, over a plurality of iterations, employ an adaptive learning rate while also ensuring that the learning rate is non-increasing.

Adaptive optimization with improved convergence

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

Generally, the present disclosure is directed to systems and methods that perform adaptive optimization with improved convergence properties. The adaptive optimization techniques described herein are useful in various optimization scenarios, including, for example, training a machine-learned model such as, for example, a neural network. In particular, according to one aspect of the present disclosure, a system implementing the adaptive optimization technique can, over a plurality of iterations, employ an adaptive per coordinate clipping threshold to clip a current first moment of the coordinate to obtain a current update value that enables faster convergence for the machine-learned model when the noise in the stochastic gradients is heavy tailed.

Fast adaptive optimization

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

Growing community of inventors

White Plains, NY, United States of America

Sanjiv Kumar