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}