File size: 6,297 Bytes
759bd70 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | """Next Federation: simulated federated learning on clients with unequal data.
Simulation only: all clients run in one process. Mirrored line by line in web/core.js.
Model: MLP 64 -> 32 (ReLU) -> 10, softmax cross-entropy, minibatch SGD.
Methods:
fedavg - clients run E local epochs from the global model; server averages uploads weighted by sample count
fedprox - same, plus proximal term (mu/2)||w - w_global||^2 in the local objective
local - every client trains alone for the same number of local epochs in total (no communication)
Client dropout: each round each client independently fails to return its update with probability p_drop.
"""
import math
import numpy as np
from nlrt import Mulberry32
D_IN, D_HID, D_OUT = 64, 32, 10
N_PARAMS = D_IN * D_HID + D_HID + D_HID * D_OUT + D_OUT
def gamma_sample(rng, a):
"""Marsaglia-Tsang gamma(a, 1); boosted for a < 1."""
if a < 1:
u = max(rng.random(), 1e-12)
return gamma_sample(rng, a + 1) * u ** (1.0 / a)
d = a - 1.0 / 3
c = 1.0 / math.sqrt(9 * d)
while True:
x = rng.normal()
v = 1 + c * x
if v <= 0:
continue
v = v * v * v
u = rng.random()
if u < 1 - 0.0331 * (x * x) * (x * x) or math.log(max(u, 1e-300)) < 0.5 * x * x + d * (1 - v + math.log(v)):
return d * v
def partition(y, n_clients, alpha, seed):
"""Dirichlet label skew: for each class, split its examples over clients with Dir(alpha) proportions."""
rng = Mulberry32(seed * 977 + 13)
clients = [[] for _ in range(n_clients)]
for c in range(10):
idx = [i for i in range(len(y)) if y[i] == c]
for k in range(len(idx) - 1, 0, -1): # Fisher-Yates
j = rng.randint(k + 1)
idx[k], idx[j] = idx[j], idx[k]
g = [gamma_sample(rng, alpha) for _ in range(n_clients)]
s = sum(g)
cuts, acc = [], 0.0
for k in range(n_clients - 1):
acc += g[k] / s
cuts.append(int(math.floor(acc * len(idx) + 0.5)))
lo = 0
for k in range(n_clients):
hi = cuts[k] if k < n_clients - 1 else len(idx)
clients[k].extend(idx[lo:hi])
lo = hi
out = []
for k in range(n_clients):
ids = sorted(clients[k])
for i in range(len(ids) - 1, 0, -1):
j = rng.randint(i + 1)
ids[i], ids[j] = ids[j], ids[i]
n_test = max(1, len(ids) // 5) if len(ids) >= 5 else 0
out.append({"train": ids[n_test:], "test": ids[:n_test]})
return out
def init_params(seed):
rng = Mulberry32(seed * 131 + 5)
w1 = np.array([[rng.normal() * math.sqrt(2.0 / D_IN) for _ in range(D_IN)] for _ in range(D_HID)])
w2 = np.array([[rng.normal() * math.sqrt(1.0 / D_HID) for _ in range(D_HID)] for _ in range(D_OUT)])
return {"w1": w1, "b1": np.zeros(D_HID), "w2": w2, "b2": np.zeros(D_OUT)}
def copy(p):
return {k: v.copy() for k, v in p.items()}
def forward(p, X):
h = np.maximum(X @ p["w1"].T + p["b1"], 0)
z = h @ p["w2"].T + p["b2"]
return h, z
def predict(p, X):
return forward(p, X)[1].argmax(1)
def accuracy(p, X, y):
if len(y) == 0:
return -1.0 # sentinel: client has no local test data
return float((predict(p, X) == y).mean())
def local_train(p, X, y, epochs, lr, batch, rng, mu=0.0, anchor=None):
n = len(y)
order = list(range(n))
for _ in range(epochs):
for k in range(n - 1, 0, -1):
j = rng.randint(k + 1)
order[k], order[j] = order[j], order[k]
for s in range(0, n, batch):
ids = order[s:s + batch]
xb, yb = X[ids], y[ids]
h, z = forward(p, xb)
z = z - z.max(axis=1, keepdims=True)
e = np.exp(z)
P = e / e.sum(axis=1, keepdims=True)
P[np.arange(len(ids)), yb] -= 1.0
P /= len(ids)
g2 = P.T @ h
gb2 = P.sum(axis=0)
dh = (P @ p["w2"]) * (h > 0)
g1 = dh.T @ xb
gb1 = dh.sum(axis=0)
grads = {"w1": g1, "b1": gb1, "w2": g2, "b2": gb2}
for key in ("w1", "b1", "w2", "b2"):
g = grads[key]
if mu > 0:
g = g + mu * (p[key] - anchor[key])
p[key] = p[key] - lr * g
return p
def run(X, y, parts, Xg, yg, method, rounds=30, epochs=2, lr=0.1, batch=20, mu=0.1, p_drop=0.0, seed=0):
"""Returns per-round global accuracy, final per-client accuracies and communication bytes."""
rng = Mulberry32(seed * 7907 + 11)
drop_rng = Mulberry32(seed * 104729 + 3)
nc = len(parts)
g = init_params(seed)
curve, comm_bytes, uploads = [], 0, 0
if method == "local":
models = [copy(g) for _ in range(nc)]
for r in range(rounds):
for k in range(nc):
tr = parts[k]["train"]
if tr:
local_train(models[k], X[tr], y[tr], epochs, lr, batch, rng)
curve.append(float(np.mean([accuracy(models[k], Xg, yg) for k in range(nc)])))
client_acc = [accuracy(models[k], X[parts[k]["test"]], y[parts[k]["test"]]) for k in range(nc)]
return {"curve": curve, "client_acc": client_acc, "comm_bytes": 0, "uploads": 0, "final": models}
for r in range(rounds):
updates = []
for k in range(nc):
comm_bytes += N_PARAMS * 4 # download of the global model
tr = parts[k]["train"]
dropped = drop_rng.random() < p_drop
if not tr:
continue
local = local_train(copy(g), X[tr], y[tr], epochs, lr, batch, rng,
mu=mu if method == "fedprox" else 0.0, anchor=g)
if dropped:
continue
comm_bytes += N_PARAMS * 4
uploads += 1
updates.append((len(tr), local))
if updates:
total = float(sum(n for n, _ in updates))
g = {key: sum((n / total) * u[key] for n, u in updates) for key in g}
curve.append(accuracy(g, Xg, yg))
client_acc = [accuracy(g, X[parts[k]["test"]], y[parts[k]["test"]]) for k in range(nc)]
return {"curve": curve, "client_acc": client_acc, "comm_bytes": comm_bytes, "uploads": uploads, "final": g}
|