Communication efficient federated learning

FIELD

0001The present disclosure relates generally to machine learning. More particularly, the present disclosure relates to communication efficient federated learning.

BACKGROUND

0002As datasets grow larger and models more complex, machine learning increasingly requires distributing the optimization of model parameters over multiple machines. Existing machine learning algorithms are typically only applicable to controlled environments (such as data centers) where the data is properly distributed among machines, and high-throughput fiber networks are available.

0003<nplcit id="ncit0001" npl-type="s"><text>Hao Zhang et al: "Poseidon: A System Architecture for Efficiency GPU-based Deep Learning on Multiple Machines", arXiV:1512.06216V1</text></nplcit>, describes a scalable system architecture for distributed inter-machine communication in existing deep learning frameworks.

SUMMARY

0004Aspects and advantages of embodiments of the present disclosure will be set forth in part in the following description, or can be learned from the description, or can be learned through practice of the embodiments.

0005The present invention is defined by the appended claims. Particular embodiments are set out in the respective dependent claims. Embodiments which do not fall within the scope of the claims do not describe part of the present invention.

0006One example aspect of the present disclosure is directed to a computer-implemented method for communication efficient machine learning. The method includes obtaining, by a client computing device, global values for a set of parameters of a machine-learned model. The method includes 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. The update matrix is restricted to have a pre-defined structure. The local dataset is stored locally by the client computing device. The method includes communicating, by the client computing device, information descriptive of the update matrix to a server computing device.

0007Another example aspect of the present disclosure is directed to a client computing device. The client device includes 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. The operations include obtaining global values for a set of parameters of a machine-learned model. The operations include 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. The local dataset is stored locally by the client computing device. The operations include encoding the update matrix to obtain an encoded update. The operations include communicating the encoded update to a server computing device.

0008Another example aspect of the present disclosure is directed to 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. The operations include obtaining global values for a set of parameters of a machine-learned model. The operations include 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. The local dataset is stored locally by the client computing device The update matrix is restricted to be at least one of a low-rank matrix and a sparse matrix. The operations include encoding the update matrix to obtain an encoded update. The operations include communicating the encoded update to a server computing device.

0009Other aspects of the present disclosure are directed to various systems, apparatuses, non-transitory computer-readable media, user interfaces, and electronic devices.

0010Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following technical effects. For example, in various implementations, efficient processing may be achieved by training a machine-learned model locally at a plurality of client computing devices (e.g. user mobile devices), thereby leveraging the computational power of a plurality of devices. Furthermore, by training a machine-learned model by a client computing device based on a local dataset, the security of the training process can be improved. This is because, for example, the information of the model update is less sensitive than the data itself. User data that is privacy sensitive remains at the user's computing device and is not uploaded to the server. Instead, only the less sensitive model update is transmitted.

0011Moreover, due to the asymmetric property of internet connections, the uplink from client to server may be slower than the downlink from the server to the client, so that transmission of a full, unrestricted, model by each client device can be inefficient. However, by restricting the update matrix to have a pre-defined structure in accordance with various embodiments (e.g. by restricting the update matrix to be at least one of a low rank matrix and a sparse matrix), more efficient communication within a machine learning framework is achieved, e.g. from a network perspective, from a client device workload/resource perspective, and/or from the perspective of attempting to perform as many rounds of learning/update as quickly as possible.

0012These and other features, aspects, and advantages of various embodiments of the present disclosure will become better understood with reference to the following description and appended claims. The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate example embodiments of the present disclosure and, together with the description, serve to explain the related principles.

BRIEF DESCRIPTION OF THE DRAWINGS

0013Detailed discussion of embodiments directed to one of ordinary skill in the art is set forth in the specification, which makes reference to the appended figures, in which: <ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Figure 1</figref> depicts a block diagram of an example computing system according to example embodiments of the present disclosure.</li><li><figref idref="f0002">Figure 2</figref> depicts a block diagram of an example computing system according to example embodiments of the present disclosure.</li><li><figref idref="f0003">Figure 3</figref> depicts a flow chart diagram of an example method to perform communication efficient machine learning according to example embodiments of the present disclosure.</li><li><figref idref="f0004">Figure 4</figref> depicts a flow chart diagram of an example method to perform communication efficient machine learning according to example embodiments of the present disclosure.</li><li><figref idref="f0004">Figure 5</figref> depicts a flow chart diagram of an example method to perform communication efficient machine learning according to example embodiments of the present disclosure.</li><li><figref idref="f0005">Figure 6</figref> depicts plots of example experimental results according to example embodiments of the present disclosure.</li></ul>

DETAILED DESCRIPTION

Introduction

0014Generally, the present disclosure provides systems and methods that perform efficient communication within a machine learning framework. For example, the efficient communication techniques provided herein can be implemented within the context of a federated learning framework. However, the efficient communication techniques provided herein can be implemented in other machine learning frameworks as well. For example, the efficient communication techniques provided herein can be implemented in any instance in which a first computing device is tasked with computing an update to a model and/or communicating the update of the model to a second computing device.

0015More particularly, federated learning is a machine learning framework that enables training of a high-quality centralized model based on training data distributed over a large number of client computing devices. The clients typically have low computational power and/or slow/unstable connections to the network. Federated learning may also be referred to as "federated optimization" in certain instances.

0016A motivating example for federated learning arises when the training data is kept locally on users' mobile computing devices and such mobile computing devices are used as nodes for performing computation on their local data in order to update a global model. Thus, the federated learning framework differs from conventional distributed machine learning due to the large number of clients, data that is highly unbalanced and not independent and identically distributed ("IID"), and unreliable network connections.

0017Federated learning offers several distinct advantages compared to performing learning at a centralized server. For example, information of the model update is less sensitive that the data itself. Thus, user data that is privacy sensitive remains at the user's computing device and is not uploaded to the server. Instead, only the less sensitive model update is transmitted. As another advantage, federated learning leverages the computational power of a large number of computing devices (e.g., user mobile devices). In addition, a slight modification of the framework described above can lead to creation and use of personalized models for each user at their respective device.

0018In some implementations, systems implementing federated learning can perform the following actions in each of a plurality of rounds of model optimization: a subset of clients are selected; each client in the subset updates the model based on their local data; the updated models or model updates are sent by each client to the server; the server aggregates the updates (e.g., by averaging the updates) and improves the global model; and the server redistributes the global model to all the clients. Performing a plurality of rounds of the above actions iteratively improves the global model based on training data stored at the client devices.

0019In a basic implementation of the above framework, each client device sends a full model back to the server in each round. However, transmission of the full model by each client device is significantly "expensive" (e.g., from a network perspective, from a client device workload/resource perspective, and/or from the perspective of attempting to perform as many rounds of learning/update as quickly as possible). In particular, due to the asymmetric property of internet connections, the uplink from client to server is typically much slower than the downlink from the server to the client.

0020In view of such significant upload costs, the present disclosure provides systems and methods that perform efficient communication within a machine learning framework (e.g., within the federated learning framework discussed above). In particular, the present disclosure provides efficient communication techniques that reduce the cost of communicating the updated model or model update from the client device to the server.

0021More particularly, the present disclosure provides communication efficient approaches that include: 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. These approaches can be combined for example, by first learning a structured update and then sketching it.

Example Model Update Notation

0022Prior to discussing the communication efficient approaches provided by the present disclosure, a basic implementation of model updates in a federated learning environment will be discussed and notation will be introduced.

0023In an example federated learning framework, an objective is to learn a model with parameters embodied in a real matrix <maths id="math0001"><math display="inline"><mi mathvariant="normal">W</mi><mo>∈</mo><msup><mi>ℝ</mi><mrow><msub><mi>d</mi><mn>1</mn></msub><mo>×</mo><msub><mi>d</mi><mn>2</mn></msub></mrow></msup><mo>.</mo></math><img file="EP3494522B1_D0001.tif" /></maths> As examples, the model can include one or more neural networks (e.g., deep neural networks, recurrent neural networks, convolutional neural networks, etc.) or other machine-learned models.

0024In round <i>t ≥</i> 0, the server distributes the current model <i>W_t</i> to a subset <i>S_t</i> of <i>n_t</i> clients (for example, to a selected subset of clients whose devices are plugged into power, have access to broadband, and are idle). Some or all of these clients independently update the model based on their local data. The updated local models are <maths id="math0002"><math display="inline"><msubsup><mi mathvariant="normal">W</mi><mi>t</mi><mn>1</mn></msubsup><mo>,</mo><msubsup><mi mathvariant="normal">W</mi><mi>t</mi><mn>2</mn></msubsup><mo>,</mo><mo>…</mo><mo>,</mo><msubsup><mi mathvariant="normal">W</mi><mi>t</mi><mi>n</mi></msubsup><mo>.</mo></math><img file="EP3494522B1_D0002.tif" /></maths> Let the updates be: <maths id="math0003"><math display="block"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>=</mo><msubsup><mi mathvariant="normal">W</mi><mi>t</mi><mi>i</mi></msubsup><mo>−</mo><msub><mi mathvariant="normal">W</mi><mi>t</mi></msub><mo>,</mo><mi>i</mi><mo>∈</mo><msub><mi>S</mi><mi>t</mi></msub><mo>.</mo></math><img file="EP3494522B1_D0003.tif" /></maths>

0025Each client then sends the update back to the server, where the global update is computed by aggregating all the client-side updates. For example, one aggregation scheme can be as follows: <maths id="math0004"><math display="block"><msub><mi mathvariant="normal">W</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><msub><mi mathvariant="normal">W</mi><mi>t</mi></msub><mo>+</mo><msub><mi>η</mi><mi>t</mi></msub><msub><mi mathvariant="normal">H</mi><mi>t</mi></msub><mo>,</mo><mspace width="1ex" /><msub><mi mathvariant="normal">H</mi><mi>t</mi></msub><mo>:</mo><mo>=</mo><mfrac><mn>1</mn><msub><mi>n</mi><mi>t</mi></msub></mfrac><mstyle displaystyle="true"><msub><mo>∑</mo><mrow><mi>i</mi><mo>∈</mo><msub><mi>S</mi><mi>t</mi></msub></mrow></msub><mrow><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>.</mo></mrow></mstyle></math><img file="EP3494522B1_D0004.tif" /></maths>

0026In addition, in some implementations, a weighted sum might be used to replace the average based on desired performance. The server can also choose the learning rate <i>η_t.</i> For example, careful choice of the server-side learning rate can lead to faster convergence. However, in at least one example, <i>η_t</i> = 1 and no weighting is used.

0027In implementations in which deep learning is performed, a separate matrix W can be used to represent the parameters of each layer. Thus, each reference herein to a matrix (e.g., a model parameter matrix <maths id="math0005"><math display="inline"><msubsup><mi mathvariant="normal">W</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0005.tif" /></maths> or an update matrix <maths id="math0006"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0006.tif" /></maths>) should be understood as not being limited to a single matrix but instead refer to one or more matrices that may be used to represent a given model or update to such model. For example, a neural network with five layers can have five model parameter matrices W that respectively represent the parameters of such layers, and five update matrices <maths id="math0007"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0007.tif" /></maths> that respectively represent updates to the parameters of such layers.

0028In many instances, W and <maths id="math0008"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0008.tif" /></maths> are 2D matrices. W can be right-multiplied, e.g., <i>d</i>₁ and <i>d</i>₂ represent the output and input dimensions respectively. For example, the parameters of a fully connected layer form a 2D matrix by itself. However, the kernel of a convolutional layer is a 4D tensor of the shape #input × width × height × #output. In such case, W can be reshaped from the kernel to be of shape (#input × width × height) × #output.

0029According to aspects of the present disclosure, communication efficient techniques are provided that reduce the cost of sending <maths id="math0009"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0009.tif" /></maths> to the server. In particular, the present disclosure provides communication efficient approaches that include: structured update approaches in which <maths id="math0010"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0010.tif" /></maths> is restricted to be small or otherwise conform to a certain structure and sketched update approaches in which <maths id="math0011"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0011.tif" /></maths> is compressed or otherwise encoded before sending to the server.

Example Structured Update Techniques

0030A first type of communication efficient update provided by the present disclosure is a structured update in which <maths id="math0012"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0012.tif" /></maths> has a pre-defined structure. In particular, two types of structured update techniques will be described in further detail: a low-rank technique and a random mask technique.

0031In the low-rank structured update technique, each update <maths id="math0013"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0013.tif" /></maths> can be constrained or enforced to be a low-rank matrix (e.g., a low-rank matrix of at most rank <i>k,</i> where <i>k</i> is a fixed number). In some implementations, restricting the update <maths id="math0014"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0014.tif" /></maths> to be a low-rank matrix can be accomplished by expressing <maths id="math0015"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0015.tif" /></maths> as the product of two matrices.

0032As an example, <maths id="math0016"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>∈</mo><msup><mi>ℝ</mi><mrow><msub><mi>d</mi><mn>1</mn></msub><mo>×</mo><msub><mi>d</mi><mn>2</mn></msub></mrow></msup></math><img file="EP3494522B1_D0016.tif" /></maths> is a low-rank matrix with rank k. The update <maths id="math0017"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0017.tif" /></maths> can be expressed as the product of two matrices: <maths id="math0018"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>=</mo><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup><mo>,</mo></math><img file="EP3494522B1_D0018.tif" /></maths><maths id="math0019"><math display="inline"><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup><mo>∈</mo><msup><mi>ℝ</mi><mrow><msub><mi>d</mi><mn>1</mn></msub><mo>×</mo><mi>k</mi></mrow></msup><mo>,</mo></math><img file="EP3494522B1_D0019.tif" /></maths><maths id="math0020"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup><mo>∈</mo><msup><mi>ℝ</mi><mrow><mi>k</mi><mo>×</mo><msub><mi>d</mi><mn>2</mn></msub></mrow></msup><mo>,</mo></math><img file="EP3494522B1_D0020.tif" /></maths> where <maths id="math0021"><math display="inline"><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0021.tif" /></maths> is generated randomly and fixed, and <maths id="math0022"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0022.tif" /></maths> is optimized. In some implementations, the client device only needs to send <maths id="math0023"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0023.tif" /></maths> to the server, since <maths id="math0024"><math display="inline"><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0024.tif" /></maths> can be generated or otherwise known by the server. In particular, in some implementations, both the client and the server can have knowledge of a synchronized random seed. The client and the server can each use the random seed (e.g., along with a pseudo-random number generator) to separately produce <maths id="math0025"><math display="inline"><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup><mo>.</mo></math><img file="EP3494522B1_D0025.tif" /></maths> Thus, the client device only needs to send <maths id="math0026"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0026.tif" /></maths> to the server, since the server can reproduce <maths id="math0027"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0027.tif" /></maths> using the locally generated <maths id="math0028"><math display="inline"><msubsup><mi mathvariant="normal">A</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0028.tif" /></maths> and the <maths id="math0029"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0029.tif" /></maths> received from the client.

0033In some implementations, fixing <maths id="math0030"><math display="inline"><msubsup><mi mathvariant="normal">B</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0030.tif" /></maths> (e.g., randomly or deterministically) is also an option.

0034In some implementations, the low-rank structured update technique can provide a compression ratio of <i>k</i>/<i>d</i>₁<i>.</i> In one example, the seed can be 32 bits long.

0035In the random mask structured update technique, each update <maths id="math0031"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0031.tif" /></maths> can be constrained or restricted to be a sparse matrix. For example, each sparse matrix can follow a predefined sparsity pattern (e.g., a predefined random sparsity pattern such as a random mask). In some implementations, a different sparsity pattern is generated for each round and/or for each client within each round.

0036Similar to the low-rank approach, the sparse pattern can be fully specified or otherwise generated based on a random seed. Therefore, the client device is only required to send the values of the non-zero entries of <maths id="math0032"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>.</mo></math><img file="EP3494522B1_D0032.tif" /></maths> For example, a server that also has knowledge of the seed can generate the sparsity pattern and, based on such pattern, determine which communicated values correspond to which parameters.

Example Sketched Update Techniques

0037A second type of communication efficient update provided by the present disclosure is a sketched update in which the client encodes the update <maths id="math0033"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0033.tif" /></maths> in a compressed form prior to sending to the server. The client device can compute the full update <maths id="math0034"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0034.tif" /></maths> and then encode the update or can compute the update <maths id="math0035"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0035.tif" /></maths> according to a structured technique and then encode such structured update. The server can decode the update before aggregation.

0038Many different types of encoding or compression are envisioned by the present disclosure. For example, the compression can be lossless compression or lossy compression. Two example encoding techniques are described in further detail below: a subsampling technique and a quantization technique.

0039One way of encoding the updates is by sampling only a random subset of the parameters described by an update. Stated differently, instead of communicating the full update <maths id="math0036"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>,</mo></math><img file="EP3494522B1_D0036.tif" /></maths> each client device can communicate matrix <maths id="math0037"><math display="inline"><msubsup><mover accent="true"><mi mathvariant="normal">H</mi><mo>^</mo></mover><mi>t</mi><mi>i</mi></msubsup><mo>,</mo></math><img file="EP3494522B1_D0037.tif" /></maths> which includes only a subset of the values of <maths id="math0038"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>.</mo></math><img file="EP3494522B1_D0038.tif" /></maths> For example, the subset of values of <maths id="math0039"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0039.tif" /></maths> can be a random subset of scaled values of <maths id="math0040"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>.</mo></math><img file="EP3494522B1_D0040.tif" /></maths>

0040The server then aggregates the sampled updates (e.g., through averaging), producing the global update Ĥ<i>_t</i>. Sampling in a random fashion has the property that the average of the sampled updates is an unbiased estimator of the true average: <maths id="math0041"><img file="EP3494522B1_D0041.tif" /></maths>

0041In some implementations, the portion of parameters that are sampled can be selected through use of a random mask, for example, as described above. In particular, a seed can be used to form a parameter mask that identifies which parameters are sampled. A different mask can be generated for each round and/or for each client within each round. The mask itself can be stored as a synchronized seed. Perturbing the expected iterates of SGD by a random matrix of zero mean, which is what certain implementations of the subsampling strategy would do, does not affect this type of convergence.

0042Another way of encoding the updates is by quantizing the weights. For example, the weights can be probabilistically quantized.

0043First, an algorithm for quantizing each scalar value to 1 bit will be described. Consider the update <maths id="math0042"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup><mo>,</mo></math><img file="EP3494522B1_D0042.tif" /></maths> let <maths id="math0043"><math display="inline"><mi>h</mi><mo>=</mo><mfenced><msub><mi>h</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi>h</mi><mrow><msub><mi>d</mi><mn>1</mn></msub><mo>×</mo><msub><mi>d</mi><mn>2</mn></msub></mrow></msub></mfenced><mo>=</mo><mi>vec</mi><mfenced><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></mfenced><mo>,</mo></math><img file="EP3494522B1_D0043.tif" /></maths> and let <i>h</i>_max = max<i>_j</i>(<i>h_j</i>), <i>h</i>_min = min<i>_j</i>(<i>h_j</i>). Let the compressed update of <i>h</i> be <i>h̃,</i> which can be generated as follows: <maths id="math0044"><math display="block"><msub><mover accent="true"><mi>h</mi><mo>˜</mo></mover><mi>j</mi></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msub><mi>h</mi><mi>max</mi></msub><mo>,</mo><mspace width="1ex" /><mi>with</mi><mspace width="1ex" /><mi>probability</mi><mfrac><mrow><msub><mi>h</mi><mi>j</mi></msub><mo>−</mo><msub><mi>h</mi><mi>min</mi></msub></mrow><mrow><msub><mi>h</mi><mi>max</mi></msub><mo>−</mo><msub><mi>h</mi><mi>min</mi></msub></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>h</mi><mi>min</mi></msub><mo>,</mo><mspace width="1ex" /><mi>with</mi><mspace width="1ex" /><mi>probability</mi><mfrac><mrow><msub><mi>h</mi><mi>max</mi></msub><mo>−</mo><msub><mi>h</mi><mi>j</mi></msub></mrow><mrow><msub><mi>h</mi><mi>max</mi></msub><mo>−</mo><msub><mi>h</mi><mi>min</mi></msub></mrow></mfrac></mrow></mtd></mtr></mtable></mrow></math><img file="EP3494522B1_D0044.tif" /></maths>

0044It is easy to show that <i>h̃</i> is an unbiased estimation of <i>h.</i> When the uncompressed scalar values are described in 4 byte float, the 1 bit method described above provides 32x of compression.

0045Further, the above can be generalized to more than 1 bit for each scalar. For example, for <i>b</i>-bit quantization, [<i>h</i>_min, <i>h</i>_max] can be equally divided into 2<i>^b</i> intervals. Suppose <i>h_i</i> falls in the interval bounded by <i>h'</i> and <i>h".</i> The quantization can operate by replacing <i>h</i>_min and <i>h</i>_max in the above equation with <i>h'</i> and <i>h",</i> respectively.

0046In some implementations, the intervals are not necessarily evenly spaced, but instead can be dynamically spaced. For implementations that use dynamically spaced intervals, a table that identifies the max/min values for each interval can be provided by the client to the server. The client will typically transmit the min and max to the server regardless of whether dynamic spacing is used or not. In some implementations, incremental, randomized, and/or distributed optimization algorithms can be similarly used in the quantized updates setting.

0047According to another aspect of the present disclosure, the quantization techniques described above can be improved through the use of random rotations. More particularly, the above 1-bit and multi-bit quantization approaches work best when the scalars are approximately equal across different dimensions. As an example, when max = 100 and min = -100 and most of the values are 0, the 1-bit quantization will lead to large quantization error.

0048As such, according to an aspect of the present disclosure, performance of a random rotation of <i>h</i> before the quantization can resolve this issue. For example, the update can be multiplied by an invertible matrix R. For example, the rotation matrix can be an orthogonal matrix. Randomly rotating <i>h</i> before the quantization can more evenly distribute the scalar values across the intervals. In the decoding phase, the server can perform the inverse rotation before aggregating all the updates.

0049In some implementations, the dimension of <i>h</i> can be as high as <i>d</i> = <i>1M,</i> and it is computationally prohibitive to generate <img file="EP3494522B1_D0045.tif" /> and apply <img file="EP3494522B1_D0046.tif" /> to a rotation matrix. As such, according to another aspect of the present disclosure, a structured rotation matrix can be used. For example, the structured rotation matrix may not require explicit construction by the client computing device, but instead has a defined structure that enables computation using R without explicit construction. For example, the structured rotation matrix can be a product of a Walsh-Hadamard matrix and a binary diagonal matrix. This can reduce the computational complexity of generating and applying the matrix to <img file="EP3494522B1_D0047.tif" /> and <img file="EP3494522B1_D0048.tif" />.

0050In some implementations, the same rotation matrix is used for all client devices and/or for all rounds. In some implementations, the server can then perform some aggregation on the updates prior to inverse rotation of the aggregated update. In some implementations, the server decodes each update prior to aggregation.

Example Systems

0051<figref idref="f0001">Figure 1</figref> depicts an example system 100 for training one or more global machine learning models 106 using respective training data 108 stored locally on a plurality of client devices 102. System 100 can include a server device 104. Server 104 can be configured to access machine learning model 106, and to provide model 106 to a plurality of client devices 102. Model 106 can be, for instance, a linear regression model, logistic regression model, a support vector machine model, a neural network (e.g. convolutional neural network, recurrent neural network, etc.), or other suitable model. In some implementations, sever 104 can be configured to communicate with client devices 102 over one or more networks.

0052Client devices 102 can each be configured to determine one or more local updates associated with model 106 based at least in part on training data 108. For instance, training data 108 can be data that is respectively stored locally on the client devices 106. The training data 108 can include audio files, image files, video files, a typing history, location history, and/or various other suitable data. In some implementations, the training data can be any data derived through a user interaction with a client device 102.

0053Further to the descriptions above, a user may be provided with controls allowing the user to make an election as to both if and when systems, programs or features described herein may enable collection, storage, and/or use of user information (e.g., training data 108), and if the user is sent content or communications from a server. In addition, certain data may be treated in one or more ways before it is stored or used, so that personally identifiable information is removed. For example, a user's identity may be treated so that no personally identifiable information can be determined for the user, or a user's geographic location may be generalized where location information is obtained (such as to a city, ZIP code, or state level), so that a particular location of a user cannot be determined. Thus, the user may have control over what information is collected about the user, how that information is used, and what information is provided to the user.

0054Although training data 108 is illustrated in <figref idref="f0001">Figure 1</figref> as a single database, the training data 108 consists of data that is respectively stored at each device 102. Thus, in some implementations, the training data 108 is highly unbalanced and not independent and identically distributed.

0055Client devices 102 can be configured to provide the local updates to server 104. As indicated above, training data 108 may be privacy sensitive. In this manner, the local updates can be performed and provided to server 104 without compromising the privacy of training data 108. For instance, in such implementations, training data 108 is not provided to server 104. The local update does not include training data 108. In some implementations in which a locally updated model is provided to server 104, some privacy sensitive data may be able to be derived or inferred from the model parameters. In such implementations, one or more of encryption techniques, random noise techniques, and/or other security techniques can be added to the training process to obscure any inferable information.

0056As indicated above, server 104 can receive each local update from client device 102, and can aggregate the local updates to determine a global update to the model 106. In some implementations, server 104 can determine an average (e.g., a weighted average) of the local updates and determine the global update based at least in part on the average.

0057In some implementations, scaling or other techniques can be applied to the local updates to determine the global update. For instance, a local step size can be applied for each client device 102, the aggregation can be performed proportionally to various data partition sizes of client devices 102, and/or one or more scaling factors can be applied to the local and/or aggregated updates. It will be appreciated that various other techniques can be applied without deviating from the scope of the present disclosure.

0058<figref idref="f0002">Figure 2</figref> depicts an example computing system 200 that can be used to implement the methods and systems of the present disclosure. The system 200 can be implemented using a client-server architecture that includes a server 210 that communicates with one or more client devices 230 over a network 242. Thus, <figref idref="f0002">Figure 2</figref> provides an example system 200 that can implement the scheme illustrated by system 100 of <figref idref="f0001">Figure 1</figref>.

0059The system 200 includes a server 210, such as a web server. The server 210 can be implemented using any suitable computing device(s). The server 210 can have one or more processors 212 and one or more memory devices 214. The server 210 can be implemented using one server device or a plurality of server devices. In implementations in which a plurality of devices are used, such plurality of devices can operate according to a parallel computing architecture, a sequential computing architecture, or a combination thereof.

0060The server 210 can also include a network interface used to communicate with one or more client devices 230 over the network 242. The network interface can include any suitable components for interfacing with one more networks, including for example, transmitters, receivers, ports, controllers, antennas, or other suitable components.

0061The one or more processors 212 can include any suitable processing device, such as a microprocessor, microcontroller, integrated circuit, logic device, or other suitable processing device. The one or more memory devices 214 can include one or more computer-readable media, including, but not limited to, non-transitory computer-readable media, RAM, ROM, hard drives, flash drives, or other memory devices. The one or more memory devices 214 can store information accessible by the one or more processors 212, including computer-readable instructions 216 that can be executed by the one or more processors 212.

0062The instructions 216 can be any set of instructions that when executed by the one or more processors 212, cause the one or more processors 212 to perform operations. For instance, the instructions 216 can be executed by the one or more processors 212 to implement a global updater 220. The global updater 220 can be configured to receive one or more local updates and to determine a global model based at least in part on the local updates.

0063The instructions 216 can further include instructions that cause the server 210 to implement a decoder 222. The decoder 222 can decode an update that has been encoded by a client device 230 (e.g., according to one of the encoding techniques discussed above such as subsampling, quantization, random rotation, etc.).

0064As shown in <figref idref="f0002">Figure 2</figref>, the one or more memory devices 214 can also store data 218 that can be retrieved, manipulated, created, or stored by the one or more processors 212. The data 218 can include, for instance, local updates, global parameters, and other data. The data 218 can be stored in one or more databases. The one or more databases can be connected to the server 210 by a high bandwidth LAN or WAN, or can also be connected to server 210 through network 242. The one or more databases can be split up so that they are located in multiple locales.

0065The server 210 can exchange data with one or more client devices 230 over the network 242. Any number of client devices 230 can be connected to the server 210 over the network 242. Each of the client devices 230 can be any suitable type of computing device, such as a general purpose computer, special purpose computer, laptop, desktop, mobile device, navigation system, smartphone, tablet, wearable computing device, gaming console, a display with one or more processors, or other suitable computing device.

0066Similar to the server 210, a client device 230 can include one or more processor(s) 232 and a memory 234. The one or more processor(s) 232 can include, for example, one or more central processing units (CPUs), graphics processing units (GPUs) dedicated to efficiently rendering images or performing other specialized calculations, and/or other processing devices. The memory 234 can include one or more computer-readable media and can store information accessible by the one or more processors 232, including instructions 236 that can be executed by the one or more processors 232 and data 238.

0067The instructions 236 can include instructions for implementing a local updater configured to determine one or more local updates according to example aspects of the present disclosure. For example, the local updater can perform one or more training techniques such as, for example, backwards propagation of errors to re-train or otherwise update the model based on the locally stored training data. The local updater can be configured to perform structured updates, sketched updates, or other techniques. The local updater can be included in an application or can be included in the operating system of the device 230.

0068The instructions 236 can further include instructions for implementing an encoder. For example, the encoder can perform one or more of the encoding techniques described above (e.g., subsampling, quantization, random rotation, etc.).

0069The data 238 can include one or more training data examples to be used in solving one or more optimization problems. The training data examples of each client device 230 can be distributed unevenly among the client devices, such that no client device 230 includes a representative sample of the overall distribution of the training data examples.

0070The data 238 can further include updated parameters to be communicated to the server 210.

0071The client device 230 of <figref idref="f0002">Figure 2</figref> can include various input/output devices for providing and receiving information from a user, such as a touch screen, touch pad, data entry keys, speakers, and/or a microphone suitable for voice recognition.

0072The client device 230 can also include a network interface used to communicate with one or more remote computing devices (e.g. server 210) over the network 242. The network interface can include any suitable components for interfacing with one more networks, including for example, transmitters, receivers, ports, controllers, antennas, or other suitable components.

0073The network 242 can be any type of communications network, such as a local area network (e.g. intranet), wide area network (e.g. Internet), cellular network, or some combination thereof. The network 242 can also include a direct connection between a client device 230 and the server 210. In general, communication between the server 210 and a client device 230 can be carried via network interface using any type of wired and/or wireless connection, using a variety of communication protocols (e.g. TCP/IP, HTTP, SMTP, FTP), encodings or formats (e.g. HTML, XML), and/or protection schemes (e.g. VPN, secure HTTP, SSL).

Example Methods

0074<figref idref="f0003">Figure 3</figref> depicts a flow diagram of an example method (300) of determining a global model according to example embodiments of the present disclosure. Method (300) can be implemented by one or more computing devices, such as one or more of the computing devices depicted in <figref idref="f0001">Figures 1</figref> and/or 2. In addition, <figref idref="f0003">Figure 3</figref> depicts steps performed in a particular order for purposes of illustration and discussion. Those of ordinary skill in the art, using the disclosures provided herein, will understand that the steps of any of the methods discussed herein can be adapted, rearranged, expanded, omitted, or modified in various ways without deviating from the scope of the present disclosure.

0075At (302), method (300) can include determining, by a client device, a local model based on one or more local data examples. In particular, the local model can be determined for a loss function using the one or more data examples. The data examples may be generated, for instance, through interaction of a user with the client device. In some implementations, the model may have been pre-trained prior to local training at (302). In some implementations, structured update, sketched update, or other techniques can be used at (302) to render the learned local model or local update communication efficient.

0076At (304), method (300) can include providing, by the client device, the local model to a server, and at (306), method (300) can include receiving, by the server, the local model. In some implementations, the local model or local update can be encoded or compressed prior to sending the local model or update to the server.

0077At (308), method (300) can include determining, by the server, a global model based at least in part on the received local model. For instance, the global model can be determined based at least in part on a plurality of local models provided by a plurality of client devices, each having a plurality of unevenly distributed data examples. In particular, the data examples may be distributed among the client devices such that no client device includes a representative sample of the overall distribution of data. In addition, the number of client devices may exceed the number of data examples on any one client device.

0078In some implementations, as part of the aggregation process, the server can decode each received local model or local update.

0079At (310), method (300) can include providing the global model to each client device, and at (312), method (300) can include receiving the global model.

0080At (314), method (300) can include determining, by the client device, a local update. In a particular implementation, the local update can be determined by retraining or otherwise updating the global model based on the locally stored training data. In some implementations, structured update, sketched update, or other techniques can be used at (314) to render the learned local model or local update communication efficient.

0081In some implementations, the local update can be determined based at least in part using one or more stochastic updates or iterations. For instance, the client device may randomly sample a partition of data examples stored on the client device to determine the local update. In particular, the local update may be determined using stochastic model descent techniques to determine a direction in which to adjust one or more parameters of the loss function.

0082In some implementations, a step size associated with the local update determination can be determined based at least in part on a number of data examples stored on the client device. In further implementations, the stochastic model can be scaled using a diagonal matrix, or other scaling technique. In still further implementations, the local update can be determined using a linear term that forces each client device to update the parameters of the loss function in the same direction.

0083At (316), method (300) can include providing, by the client device, the local update to the server. In some implementations, the local model or local update can be encoded prior to sending the local model or update to the server.

0084At (318), method (300) can include receiving, by the server, the local update. In particular, the server can receive a plurality of local updates from a plurality of client devices.

0085At (320), method (300) can include again determining the global model. In particular, the global model can be determined based at least in part on the received local update(s). For instance, the received local updates can be aggregated to determine the global model. The aggregation can be an additive aggregation and/or an averaging aggregation. In particular implementations, the aggregation of the local updates can be proportional to the partition sizes of the data examples on the client devices. In further embodiments the aggregation of the local updates can be scaled on a per-coordinate basis.

0086Any number of iterations of local and global updates can be performed. That is, method (300) can be performed iteratively to update the global model based on locally stored training data over time.

0087<figref idref="f0004">Figure 4</figref> depicts a flow chart diagram of an example method 400 to perform communication efficient machine learning according to example embodiments of the present disclosure. For example, method 400 can be performed by a client computing device.

0088At 402, a client computing device obtains global values for a set of parameters of a machine-learned model.

0089At 404, the client computing device trains 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. The update matrix is restricted to have a pre-defined structure. The local dataset is stored locally by the client computing device. In some implementations, the update matrix is descriptive of updated values for the set of parameters and/or differences between the updated values and the global values.

0090In some implementations, the update matrix is restricted to be a low-rank matrix.

0091In some implementations, training the machine-learned model at 404 can include defining, by the client computing device, the update matrix as a product of a first matrix and a second matrix. The first matrix can include fixed values and the second matrix can include optimizable variables. The client computing device can train the machine-learned model based at least in part on the local dataset to obtain the second matrix.

0092In some of such implementations, the method 400 can further include, prior to training the model at 404: generating the first matrix based at least in part on a seed and a pseudo-random number generator. Both the client computing device and a server computing device can have knowledge of the seed such that the first matrix is reproducible by the server computing device.

0093In some implementations, the update matrix is restricted to be a sparse matrix.

0094In some implementations, training the machine-learned model at 404 can include training 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. In such implementations, the update matrix can be descriptive of only the updated values for the pre-selected portion of the set of parameters.

0095In some of such implementations, the method 400 can further include, prior to training the model at 404: generating a parameter mask that specifies which of the set of parameters are included in the pre-selected portion of the set of parameters. For example, generating the parameter mask can include 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.

0096At 406, the client computing device communicates information descriptive of the update matrix to the server computing device.

0097As one example, in implementations in which training the model at 404 includes optimizing a second matrix, communicating information descriptive of the update matrix at 406 can include communicating information descriptive of the second matrix to the server computing device.

0098<figref idref="f0004">Figure 5</figref> depicts a flow chart diagram of an example method 500 to perform communication efficient machine learning according to example embodiments of the present disclosure. For example, method 500 can be performed by a client computing device.

0099At 502, a client computing device obtains global values for a set of parameters of a machine-learned model.

0100At 504, the client computing device trains 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. The local dataset is stored locally by the client computing device. In some implementations, the update matrix is descriptive of updated values for the set of parameters and/or differences between the updated values and the global values.

0101At 506, the client computing device encodes the update matrix to obtain an encoded update.

0102In some implementations, encoding the update matrix at 506 can include subsampling the update matrix to obtain the encoded update. In some of such implementations, subsampling the update matrix can include: generating a parameter mask that specifies a portion of the set of parameters to be sampled; and subsampling the update matrix according to the parameter mask.

0103In some of such implementations, generating the parameter mask can include generating the parameter mask based at least in part on a seed and a pseudo-random number generator, wherein both the client computing device and a server computing device have knowledge of the seed such that the parameter mask is reproducible by the server computing device.

0104In some implementations, encoding the update matrix at 506 can include probabilistically quantizing one or more values included in the update matrix. In some implementations, encoding the update matrix at 506 can include performing probabilistic binary quantization for one or more values included in the update matrix to change each of the one or more values to a maximum value included in the update matrix or a minimum value included in the update matrix. In some implementations, encoding the update matrix at 506 can include: defining a plurality of intervals between a maximum value included in the update matrix and a minimum value included in the update matrix; and probabilistically changing each of one or more values included in the update matrix to a local interval maximum or a local interval maximum.

0105In some implementations, encoding the update matrix at 506 can include multiplying a vector of the update matrix by a rotation matrix to obtain a rotated update. In some of such implementations, encoding the update matrix can further include probabilistically quantizing one or more values included in the rotated update. In some implementations, the rotation matrix can be a structured rotation matrix that does not require complete generation of the rotation matrix by the client computing device.

0106At 508, the client computing device communicates the encoded update to the server computing device. The server computing device can decode the encoded update.

Example Experiments

0107Example experiments were conducted using federated learning to train deep neural networks for the CIFAR-10 image classification task (see,<nplcit id="ncit0002" npl-type="s"><text> Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009</text></nplcit>). There are 50,000 training examples, which were partitioned into 100 clients each containing 500 training examples. The model architecture was taken from the TensorFlow tutorial (Tensorflow convolutional neural networks tutorial. http://www.tensorflow.org/tutorials/deep_cnn, 2016), which consists of two convolutional layers followed by two fully connected layers and then a linear transformation layer to produce logits, for a total of over 1<i>e</i>6 parameters. While this model is not the state-of-the-art, it is sufficient for the goal of evaluating the compression methods described herein, rather than achieving the best possible accuracy on this task.

0108The Federated Averaging algorithm (<nplcit id="ncit0003" npl-type="s"><text>McMahan et al. Federated Learning of deep networks using model averaging. arXiv:1602.05629, 2016</text></nplcit>) was employed, which significantly decreases the number of rounds of communication required to train a good model. However, the techniques are expected to show a similar reduction in communication costs when applied to synchronized SGD. For Federated Averaging, on each round 10 clients were selected at random, each of which performs 10 epochs of SGD with a learning rate of <i>η</i> on their local dataset using minibatches of 50 images, for a total of 100 local updates. From this updated model the deltas for each layer of <maths id="math0045"><math display="inline"><msubsup><mi mathvariant="normal">H</mi><mi>t</mi><mi>i</mi></msubsup></math><img file="EP3494522B1_D0049.tif" /></maths> were computed.

0109Table 1 provides low rank and sampling parameters for the example CIFAR experiments. The Sampling Probabilities column gives the fraction of elements uploaded for the two convolutional layers and the two fully-connected layers, respectively; these parameters are used by StructMask, SketchMask, and SketchRotMask. The Low Rank column gives the rank restriction k for these four layers. The final softmax layer is small, so updates to it were not compressed. <tables id="tabl0001" num="0001"><table frame="all"><title>Table 1:</title><tgroup cols="5"><colspec colnum="1" colname="col1" colwidth="36mm" /><colspec colnum="2" colname="col2" colwidth="27mm" /><colspec colnum="3" colname="col3" colwidth="46mm" /><colspec colnum="4" colname="col4" colwidth="22mm" /><colspec colnum="5" colname="col5" colwidth="21mm" /><thead><row><entry align="center" valign="middle" /><entry align="center" valign="middle"><b>(Low) Rank</b></entry><entry align="center" valign="middle"><b>Sampling Probabilities</b></entry><entry align="center" valign="middle"><b>Model Size</b></entry><entry align="center" valign="middle"><b>Reduction</b></entry></row></thead><tbody><row><entry align="center" valign="middle"><i>Full Model (baseline)</i></entry><entry align="center" valign="middle">64, 64, 384, 192</entry><entry align="center" valign="middle">1, 1, 1, 1</entry><entry align="center" valign="middle">4.075 MB</entry><entry align="center" valign="middle">-</entry></row><row><entry align="center" valign="middle"><i>Medium subsampling</i></entry><entry align="center" valign="middle">64, 64, 12, 6</entry><entry align="center" valign="middle">1, 1, 0.03125, 0.03125</entry><entry align="center" valign="middle">0.533 MB</entry><entry align="center" valign="middle">7.6x</entry></row><row><entry align="center" valign="middle"><i>High subsampling</i></entry><entry align="center" valign="middle">8, 8, 12, 6</entry><entry align="center" valign="middle">0.125, 0.125, 0.0.125, 0.0.123</entry><entry align="center" valign="middle">0.175 MB</entry><entry align="center" valign="middle">23.3x</entry></row></tbody></tgroup></table></tables>

0110<figref idref="f0005">Figure 6</figref> depicts plots of example non-quantized results (left and middle columns), and results including binary quantization (dashed lines SketchRotMaskBin and SketchMaskBin, right column). Note the x-axis is on a log scale for top-right plot. Over 70% accuracy was achieved with fewer than 100MB of communication.

0111Medium and high low-rank/sampling parameterizations were defined that result in the same compression rates for both approaches, as given in Table 1. The left and center columns of <figref idref="f0005">Figure 6</figref> present non- quantized results for test-set accuracy, both as a function of the number of rounds of the algorithm, and the total number of megabytes uploaded. For all experiments, learning rates were tuned using a multiplicative grid of resolution <maths id="math0046"><math display="inline"><mo>√</mo><mn>2</mn></math><img file="EP3494522B1_D0050.tif" /></maths> centered at 0.15. Results for the learning rate are plotted with the best median accuracy over rounds 400 - 800. A multiplicative learning-rate decay of 0.988 was used, which was selected by tuning only for the baseline algorithm.

0112For medium subsampling, all three approaches provide a dramatic improvement in test set accuracy after a fixed amount of bandwidth usage; the lower row of plots shows little loss in accuracy as a function of the number of update rounds with the exception that the StructLowRank approach performs poorly for the high subsampling parameters.

0113The right two plots in <figref idref="f0005">Figure 6</figref> give results for SketchMask and SketchRotMask, with and without binary quantization; only the medium subsampling regime is considered, which is representative. Observe that (as expected) introducing the random rotation without quantization has essentially no effect. However, binary quantization dramatically decreases the total communication cost, and further introducing the random rotation significantly speeds convergence, and also allows convergence to a higher level of accuracy. A reasonable model is able to be learned (70% accuracy) in only ∼ 100MB of communication, two orders of magnitude less than the baseline.

Additional Disclosure

0114The technology discussed herein makes reference to servers, databases, software applications, and other computer-based systems, as well as actions taken and information sent to and from such systems. The inherent flexibility of computer-based systems allows for a great variety of possible configurations, combinations, and divisions of tasks and functionality between and among components. For instance, processes discussed herein can be implemented using a single device or component or multiple devices or components working in combination. Databases and applications can be implemented on a single system or distributed across multiple systems. Distributed components can operate sequentially or in parallel.

0115While the present subject matter has been described in detail with respect to various specific example embodiments thereof, each example is provided by way of explanation, not limitation of the disclosure. Those skilled in the art, upon attaining an understanding of the foregoing, can readily produce alterations to, variations of, and equivalents to such embodiments. Accordingly, the subject disclosure does not preclude inclusion of such modifications, variations and/or additions to the present subject matter as would be readily apparent to one of ordinary skill in the art. For instance, features illustrated or described as part of one embodiment can be used with another embodiment to yield a still further embodiment. Thus, it is intended that the present disclosure cover such alterations, variations, and equivalents.