Systems and methods of distributed optimization

Patent metadata

Field	Value
Publication number	US-12530427-B2
Application number	US-202117406377-A
Country	US
Kind code	B2
Filing date	Aug 19, 2021
Priority date	Oct 16, 2015
Publication date	Jan 20, 2026
Grant date	Jan 20, 2026

Abstract

Systems and methods of determining a global model are provided. In particular, one or more local updates can be received from a plurality of user devices. Each local update can be determined by the respective user device based at least in part on one or more data examples stored on the user device. The one or more data examples stored on the plurality of user devices are distributed on an uneven basis, such that no user device includes a representative sample of the overall distribution of data examples. The local updates can then be aggregated to determine a global model.

First claim

What is claimed is:

1 . A computer-implemented method of performing computationally-distributed optimization of a differentially private global model based on unevenly distributed data that is distributed across a plurality of user devices, the method comprising:
providing, by a central computing system comprising a server or data center, a global model to the plurality of user devices; receiving, by the central computing system, one or more local updates from the plurality of user devices, each local update being determined by the respective user device based at least in part on one or more data examples stored on the respective user device, wherein the one or more data examples stored on the plurality of user devices are distributed on an uneven basis, such that no user device includes a representative sample of an overall distribution of data examples, and wherein each respective user device has performed a differential privacy technique by adding random noise to its corresponding local update prior to transmission of the corresponding local update to the central computing system; aggregating, by the central computing system, the received local updates to determine a global update for the global model; and transmitting, by the central computing system, the global update to the plurality of user devices for respective use by the plurality of user devices in generating predictions at the plurality of user devices.

2 . The computer-implemented method of claim 1 , wherein each respective user device has added random noise to its corresponding local update prior to transmission of the corresponding local update to the central computing system.

3 . The computer-implemented method of claim 1 , wherein at least one of the local updates comprise a gradient vector associated with the data stored on the respective user device.

4 . The computer-implemented method of claim 1 , wherein the size of each local update is independent from the size of the data used to determine the local update.

5 . The computer-implemented method of claim 1 , wherein the one or more local updates are determined using one or more optimization algorithms.

6 . The computer-implemented method of claim 1 , wherein each local update is determined based at least in part on one or more stochastic iterations, each stochastic iteration having a stepsize that is inversely proportional to a number of data examples stored on the respective user device.

7 . The computer-implemented method of claim 6 , wherein the one or more stochastic iterations are determined at least in part by randomly sampling the data examples stored on the respective user device.

8 . The computer-implemented method of claim 1 , wherein the one or more local updates are determined using one or more diagonal scaling matrices.

9 . The computer-implemented method of claim 1 , wherein aggregating, by the central computing system, the received local updates to determine the global update for the global model comprises aggregating the received local updates based at least in part on the number of data examples stored on each user device, and wherein aggregating the received local updates includes determining a weighted average of the received local updates.

10 . The computer-implemented method of claim 1 , wherein the aggregating, by the central computing system, the received local updates to determine the global update for the global model comprises scaling the received local updates on a per-coordinate basis.

11 . The computer-implemented method of claim 1 , wherein aggregating, by the central computing system, the received local updates to determine the global update for the global model comprises aggregating the received local updates for at least one iteration.

12 . The computer-implemented method of claim 11 , wherein the at least one iteration is determined based at least in part on a threshold, and wherein the threshold is determined based at least in part on an amount of time required for communication of the one or more local updates.

13 . The computer-implemented method of claim 1 , wherein the number of data examples stored on each user device is smaller than the total number of user devices.

14 . The computer-implemented method of claim 1 , further comprising providing a gradient of a loss function to each of the one or more user devices.

15 . The computer-implemented method of claim 1 , wherein aggregating, by the central computing system, the received local updates to determine the global update for the global model comprises determining a weighted average of the received local updates.

16 . A computer-implemented method of updating a local machine learning model based on unevenly distributed data, the method comprising:
determining, by a user computing device, a gradient vector of a loss function associated with a global machine learning model; determining, by the user computing device, a local model update based at least in part on the gradient vector of the loss function and one or more locally stored data examples, wherein the distribution of the one or more locally stored data examples is not representative of an overall distribution of the data examples used to train the global machine learning model; performing, by the user computing device, a differential privacy technique by adding random noise to the local model update; and after performing the differential privacy technique, providing, by the user computing device, the local model update to the central computing system for use in determination of a global update to the global machine learning model, the global update to the global machine learning model being determined based on one or more local model updates received from a plurality of user devices; and receiving, from the central computing system, the global update, wherein the global update is used by the user computing device in generating predictions.

17 . The computer-implemented method of claim 16 , wherein determining, by the user computing device, a local model update comprises determining the local model update based at least in part on one or more stochastic iterations, each stochastic iteration having a stepsize that is inversely proportional to a number of data examples stored on the respective user device.

18 . The computer-implemented method of claim 17 , wherein the one or more stochastic iterations are determined at least in part by randomly sampling the data examples stored on the respective user device.

19 . The computer-implemented method of claim 16 , wherein determining, by the user computing device, a local model update comprises determining the local model update based at least in part on one or more diagonal scaling matrices.

20 . A computing system, comprising:
one or more processors; and one or more memory devices, the one or more memory devices storing computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations, the operations comprising:
determining a local model update associated with an objective function based at least in part on one or more local data examples stored by the computing system, the local model update being determined using one or more stochastic iterations, each stochastic iteration having a stepsize that is inversely proportional to the number of local data examples;
adding random noise to the local model update; and
after adding random noise to the local model update, providing the local model update to a ce

Assignees

• Google Llc

Inventors

• Mcmahan Hugh Brendan
• Konecny Jakub
• Moore Eider Brantly
• Ramage Daniel
• Aguera-Arcas Blaise H

Classifications

• G06F2111/02

  CAD in a network environment, e.g. collaborative CAD or distributed simulation · CPC title

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06F17/17 Primary

  Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method ({G06F17/18 takes precedence } ; interpolation for numerical control G05B19/18) · CPC title