🌐 中文版：繁體中文

What is parallel computing?

Today’s deep neural network models have a huge number of parameters, and a big model also means more computation.

Big Model + Big Data -> Huge computation cost !

A year’s worth of computation on a single GPU can be done at once on 20 GPUs in parallel, reducing the time cost.

Linear Predictor

To be continued

Federated learning

It’s best to first have a foundation in parallel computing and distributed machine learning. You can refer to this video series: https://www.youtube.com/watch?v=gVcnOe6_c6Q&t=124s

Background

Problem background: Google wants to train a model using data on users’ mobile devices.

A possible solution: collect user data, upload it to a centralized learning platform, and train the model there.

The challenge faced: users refuse to upload data, especially sensitive data, to Google’s servers.

This kind of problem scenario also occurs at European/American enterprises with strict personal-privacy protection, or in medical environments.

Distributed learning and federated learning

The process of one iteration:

The worker node requests parameters from the parameter server
The server returns the parameters
The worker node computes the gradient locally based on the returned parameters
The worker node returns the gradient to the parameter server
The parameter server updates the parameters via the gradient

In this process, the worker’s data never leaves the node, and the server can’t see user data. This architecture solves the problem scenario above.

Federated learning is a kind of distributed learning, but it still differs from traditional distributed learning in several ways:

Users have control over their devices and data, whereas in traditional distributed learning the workers are controlled by the server
Worker nodes are unstable, since worker nodes are usually mobile devices (e.g. phones) with varying computing power, some fast and some slow
Federated learning has a high communication cost, usually due to low communication bandwidth or a large distance between the worker node and server
The data stored on a worker node isn’t IID (independent and identically distributed)
Federated learning’s node load is unbalanced: user A’s phone takes photos every day, user B’s phone takes a photo once every 10 days

Do more computation, less communication. Since communication is costly, a common research direction is to reduce the number of communication rounds.

Gradient descent

What the worker does

Receive the model parameters $w$ from the server
Compute the gradient $g_{i}$ from the model parameters $w$ and local data
Send $g_{i}$ to the server

What the server does

Receive the gradients $g_{1},…,g_{m}$ from different worker nodes
Compute $g=g_{1}+…+g_{m}$
Update the model parameters: $w \leftarrow w - \alpha \cdot g $ (this is gradient descent)

$\alpha$ is the learning rate

After the server finishes, the next iteration can proceed, until the algorithm converges.

Federated Averaging Algorithm (FedAvg)

Unlike the gradient-descent algorithm above, this is a communication-efficient algorithm. The first step is the same: the parameter server sends parameters to the worker nodes. But the subsequent steps start to differ.

What the worker does

Suppose this is the $i$-th worker node

Receive the model parameters $w$ from the server
Repeat the following:
a. Compute the gradient $g$ from the model parameters $w$ and local data
b. Do gradient descent locally: $w \leftarrow w - \alpha \cdot g$

a. and b. repeat for several epochs; one epoch processes the local data once, so repeating a, b N times is N epochs.

Send $\widetilde{w_{i}} = W$ back to the server (here $\widetilde{w_{i}}$ is the $w$ after local gradient descent)

With that, the node has finished computing.

What the server does

The server receives $\widetilde{w_{i}}$ ~ $\widetilde{w_{m}}$ from $m$ workers
Average or weighted-average: $w \leftarrow \cfrac{1}{m}(\widetilde{w_{i}} + … +\widetilde{w_{m}} ) $

The new model parameters are $m$.

So gradient descent has the worker return the gradient for the server to compute the model parameters, while FedAvg has the worker compute the local model parameters first and upload them directly, with the server averaging.

For the same amount of communication, FedAvg converges faster. FedAvg sacrifices the worker nodes’ computation for fewer communication rounds.

For the same number of epochs (one pass over the data by the worker, used to measure computation), FedAvg converges more slowly.

Communication-Efficient Algorithms

Approximate Newton’s algorithms
Primal-dual algorithms
One-shot averaging

Communication is a big problem in distributed machine learning, and many algorithms aim to reduce the number of communication rounds, basically trading lots of computation for fewer communication rounds.

Privacy protection

In distributed learning or federated learning, architecturally only the gradient is uploaded from local to the server, and user data stays local. Does this mean user privacy is safe? Actually not, since the gradient itself is computed from user data via a function:

Let’s look at how the stochastic gradient is derived. First, a least squares regression is:

\underset{w}{m i n} \sum_{i = 1}^{n} l (w, x_{i}, y_{i})

where

l (w, x_{i}, y_{i}) = \frac{1}{2} (x_{i}^{T} w - y_{i})^{2}

g_{i} = \frac{\partial l (w, x_{i}, y_{i})}{\partial w} = (X_{i}^{T} W - y_{i}) X_{i}

The top $l(w,x_{i},y_{i})$ is the least squares regression’s loss function, defined as the inner product of the data and model parameters, minus the label $y_{i}$, then squared. Computing the gradient means taking the derivative with respect to $w$, giving a vector, and the term in front of this vector,

(X_{i}^{T} W - y_{i})

is a real number, so it can be seen as scaling the original user data $X_{i}$. So the gradient is just a transformation of the original data, with no data-protection effect. The original data can be reconstructed from the gradient, so a privacy risk exists.

And in federated learning, both the server and workers can see the model parameters after each iteration, so federated learning leaks even more privacy.

How to defend?

This brings up differential privacy, whose concept is adding noise to the gradient or model parameters. But if the noise isn’t strong enough, the original data can still possibly be reversed; and if the noise is too strong, the loss function may fail to keep converging, so the model doesn’t learn well either.

Defending against Byzantine faults and malicious attacks

Byzantine faults are related to the Byzantine Generals Problem, a distributed-systems problem: if a node in a distributed system fails without going down, it drags down the other nodes in the system. Think of it as one of us being a traitor. If a node is malicious and modifies its own data and labels, it can send problematic gradients to the server, training a problematic model. This attack is called a Data Poison Attack, doable even in traditional neural networks, while the attack specifically targeting distributed machine learning is a model poisoning attack, which usually swaps local labels for wrong ones, naturally producing a wrong model.

One defense is for the server to take a gradient uploaded by a worker, update the model parameters, and compute accuracy on the server or a test machine; if a worker sends a wrong gradient, the test accuracy will necessarily drop. But this defense isn’t well-suited to federated learning, because the server can’t see user data, and workers’ statistical distributions differ, so even a non-malicious worker could cause accuracy to drop, and the server averages the model parameters anyway.

Current defenses are all based on user data being IID (independent and identically distributed), but federated learning’s reality is that user data isn’t IID, and individual workers’ statistical distributions differ, so current defenses aren’t very practical.

Summary

Federated learning is a kind of distributed learning
Its purpose is to let multiple users collaboratively train a model without sharing data, with user data never leaving local (the point is protecting user privacy)
Federated learning’s unique challenges:
- non-IID data
- slow communication

So important directions are: