Communication efficient federated learning

• US 10,657,461 B2
• Filed: 09/07/2017
• Issued: 05/19/2020
• Est. Priority Date: 09/26/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: McMahan, Hugh Brendan, Bacon, Dave Morris, Konecny, Jakub, Yu, Xinnan
• Primary Examiner(s): Chang, Li Wu
• Application Number:
  US16/335,695
• Publication Number:
  US 20190340534A1
• Time in Patent Office: 985 Days
• Field of Search: None
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/0464 Convolutional networks [CNN, ConvNet]
• CPC Class Codes: G06N 3/0495 Quantised networks; Sparse networks; Compressed networks
• CPC Class Codes: G06N 3/084 Backpropagation, e.g. using gradient descent
• CPC Class Codes: G06N 3/098 Distributed learning, e.g. federated learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 67/01 Protocols

Abstract

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.

Claims

1. A computer-implemented method for communication efficient machine learning, the method comprising:

obtaining, by a client computing device, global values for a set of parameters of a machine-learned model;

training, by the client computing device, the machine-learned model based at least in part on a local dataset to obtain an update matrix that is descriptive of updated values for the set of parameters of the machine-learned model, wherein the update matrix is restricted to be a low-rank matrix, and wherein the local dataset is stored locally by the client computing device; and

communicating, by the client computing device, information descriptive of the update matrix to a server computing device for use by the server computing device in computation of a global update to the machine-learned model, wherein;

training, by the client computing device, the machine-learned model based at least in part on the local dataset to obtain the update matrix comprises;

defining, by the client computing device, the update matrix as a product of a first matrix and a second matrix, wherein the first matrix comprises fixed values and the second matrix comprises optimizable variables, and wherein the fixed values of the first matrix are known to the server computing device; and

training, by the client computing device, machine-learned model based at least in part on the local dataset to obtain the second matrix; and

communicating, by the client computing device, information descriptive of the update matrix to the server computing device comprises communicating, by the client computing device, information descriptive of the second matrix to the server computing device without sending the first matrix from the client computing device to the server computing device.

2. The computer-implemented method of claim 1, further comprising, prior to training, by the client computing device, the machine-learned model:

generating, by the client computing device, the first matrix based at least in part on a seed and a pseudo-random number generator, wherein both the client computing device and the server computing device have knowledge of the seed such that the first matrix is reproducible by the server computing device.

3. The computer-implemented method of claim 1, wherein the update matrix is restricted to be a sparse matrix.

4. The computer-implemented method of claim 1, wherein training, by the client computing device, the machine-learned model based at least in part on the local dataset comprises training, by the client computing device, the machine-learned model based at least in part on the local dataset such that updated values are determined only for a pre-selected portion of the set of parameters, the update matrix descriptive of only the updated values for the pre-selected portion of the set of parameters.

5. The computer-implemented method of claim 4, further comprising, prior to training, by the client computing device, the machine-learned model:

generating, by the client computing device, a parameter mask that specifies which of the set of parameters are included in the pre-selected portion of the set of parameters.

6. The computer-implemented method of claim 5, wherein generating, by the client computing device, the parameter mask comprises generating, by the client computing device, the parameter mask based at least in part on a seed and a pseudo-random number generator, wherein both the client computing device and the server computing device have knowledge of the seed such that the parameter mask is reproducible by the server computing device.

7. The computer-implemented method of claim 1, wherein the update matrix describes the updated values for the set of parameters or respective differences between the updated values and the global values.

8. A client computing device, comprising:

at least one processor; and

at least one non-transitory computer-readable medium that stores instructions that, when executed by the at least one processor, cause the client computing device to perform operations comprising;

obtaining global values for a set of parameters of a machine-learned model;

training the machine-learned model based at least in part on a local dataset to obtain an update matrix that is descriptive of updated values for the set of parameters of the machine-learned model, wherein the update matrix is restricted to be a low-rank matrix, and wherein the local dataset is stored locally by the client computing device; and

communicating information descriptive of the update matrix to a server computing device for use by the server computing device in computation of a global update to the machine-learned model, wherein;

training the machine-learned model based at least in part on the local dataset to obtain the update matrix comprises;

defining the update matrix as a product of a first matrix and a second matrix, wherein the first matrix comprises fixed values and the second matrix comprises optimizable variables, and wherein the fixed values of the first matrix are known to the server computing device; and

training machine-learned model based at least in part on the local dataset to obtain the second matrix; and

communicating information descriptive of the update matrix to the server computing device comprises communicating, by the client computing device, information descriptive of the second matrix to the server computing device without sending the first matrix from the client computing device to the server computing device.

9. At least one non-transitory computer-readable medium that stores instructions that, when executed by a client computing device, cause the client computing device to perform operations comprising:

obtaining global values for a set of parameters of a machine-learned model;

training the machine-learned model based at least in part on a local dataset to obtain an update matrix that is descriptive of updated values for the set of parameters of the machine-learned model, wherein the update matrix is restricted to be a low-rank matrix, and wherein the local dataset is stored locally by the client computing device; and

communicating information descriptive of the update matrix to a server computing device for use by the server computing device in computation of a global update to the machine-learned model, wherein;

training the machine-learned model based at least in part on the local dataset to obtain the update matrix comprises;

defining the update matrix as a product of a first matrix and a second matrix, wherein the first matrix comprises fixed values and the second matrix comprises optimizable variables, and wherein the fixed values of the first matrix are known to the server computing device; and

training machine-learned model based at least in part on the local dataset to obtain the second matrix; and

communicating information descriptive of the update matrix to the server computing device comprises communicating, by the client computing device, information descriptive of the second matrix to the server computing device without sending the first matrix from the client computing device to the server computing device.