"""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}