File size: 8,410 Bytes
94769b3
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
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
/* Next Federation compute core: line-by-line port of fed_core.py (parameters stored as flat Float64Arrays). */
(function (root, factory) {
  if (typeof module === "object" && module.exports) module.exports = factory();
  else root.Core = factory();
})(typeof self !== "undefined" ? self : this, function () {
  "use strict";
  const DI = 64, DH = 32, DO = 10, N_PARAMS = DI * DH + DH + DH * DO + DO;
  const ASSETS = ["model.json", "digits.json"];
  const KEYS = ["w1", "b1", "w2", "b2"];

  function gammaSample(rng, a) {
    if (a < 1) { const u = Math.max(rng.random(), 1e-12); return gammaSample(rng, a + 1) * Math.pow(u, 1 / a); }
    const d = a - 1 / 3, c = 1 / Math.sqrt(9 * d);
    for (;;) {
      const x = rng.normal(); let v = 1 + c * x;
      if (v <= 0) continue;
      v = v * v * v; const u = rng.random();
      if (u < 1 - 0.0331 * (x * x) * (x * x) || Math.log(Math.max(u, 1e-300)) < 0.5 * x * x + d * (1 - v + Math.log(v))) return d * v;
    }
  }

  function partition(y, nClients, alpha, seed) {
    const rng = NLRT.mulberry32((seed * 977 + 13) >>> 0), clients = Array.from({ length: nClients }, () => []);
    for (let c = 0; c < 10; c++) {
      const idx = []; for (let i = 0; i < y.length; i++) if (y[i] === c) idx.push(i);
      for (let k = idx.length - 1; k > 0; k--) { const j = rng.randint(k + 1); [idx[k], idx[j]] = [idx[j], idx[k]]; }
      const g = []; for (let k = 0; k < nClients; k++) g.push(gammaSample(rng, alpha));
      let s = 0; for (const v of g) s += v;
      const cuts = []; let acc = 0;
      for (let k = 0; k < nClients - 1; k++) { acc += g[k] / s; cuts.push(Math.floor(acc * idx.length + 0.5)); }
      let lo = 0;
      for (let k = 0; k < nClients; k++) { const hi = k < nClients - 1 ? cuts[k] : idx.length; clients[k].push(...idx.slice(lo, hi)); lo = hi; }
    }
    return clients.map(cl => {
      const ids = cl.slice().sort((a, b) => a - b);
      for (let i = ids.length - 1; i > 0; i--) { const j = rng.randint(i + 1); [ids[i], ids[j]] = [ids[j], ids[i]]; }
      const nTest = ids.length >= 5 ? Math.max(1, Math.floor(ids.length / 5)) : 0;
      return { train: ids.slice(nTest), test: ids.slice(0, nTest) };
    });
  }

  function initParams(seed) {
    const rng = NLRT.mulberry32((seed * 131 + 5) >>> 0);
    const w1 = new Float64Array(DH * DI), w2 = new Float64Array(DO * DH);
    for (let i = 0; i < DH * DI; i++) w1[i] = rng.normal() * Math.sqrt(2 / DI);
    for (let i = 0; i < DO * DH; i++) w2[i] = rng.normal() * Math.sqrt(1 / DH);
    return { w1, b1: new Float64Array(DH), w2, b2: new Float64Array(DO) };
  }
  const copy = p => ({ w1: p.w1.slice(), b1: p.b1.slice(), w2: p.w2.slice(), b2: p.b2.slice() });

  function forward1(p, x, h, z) {
    for (let j = 0; j < DH; j++) { let s = p.b1[j]; for (let i = 0; i < DI; i++) s += x[i] * p.w1[j * DI + i]; h[j] = s > 0 ? s : 0; }
    for (let o = 0; o < DO; o++) { let s = p.b2[o]; for (let j = 0; j < DH; j++) s += h[j] * p.w2[o * DH + j]; z[o] = s; }
  }

  function accuracy(p, X, y, ids) {
    if (!ids.length) return -1;
    const h = new Float64Array(DH), z = new Float64Array(DO); let ok = 0;
    for (const i of ids) { forward1(p, X[i], h, z); if (NLRT.argmax(z) === y[i]) ok++; }
    return ok / ids.length;
  }

  function localTrain(p, X, y, ids, epochs, lr, batch, rng, mu, anchor) {
    const n = ids.length, order = []; for (let i = 0; i < n; i++) order.push(i);
    const h = new Float64Array(batch * DH), z = new Float64Array(DO), P = new Float64Array(batch * DO);
    const g1 = new Float64Array(DH * DI), gb1 = new Float64Array(DH), g2 = new Float64Array(DO * DH), gb2 = new Float64Array(DO), dh = new Float64Array(DH);
    for (let e = 0; e < epochs; e++) {
      for (let k = n - 1; k > 0; k--) { const j = rng.randint(k + 1); [order[k], order[j]] = [order[j], order[k]]; }
      for (let s = 0; s < n; s += batch) {
        const bs = Math.min(batch, n - s);
        g1.fill(0); gb1.fill(0); g2.fill(0); gb2.fill(0);
        for (let b = 0; b < bs; b++) {
          const x = X[ids[order[s + b]]], hb = h.subarray(b * DH, (b + 1) * DH);
          forward1(p, x, hb, z);
          let mx = -Infinity; for (let o = 0; o < DO; o++) if (z[o] > mx) mx = z[o];
          let sum = 0; for (let o = 0; o < DO; o++) { P[b * DO + o] = Math.exp(z[o] - mx); sum += P[b * DO + o]; }
          for (let o = 0; o < DO; o++) P[b * DO + o] /= sum;
          P[b * DO + y[ids[order[s + b]]]] -= 1;
          for (let o = 0; o < DO; o++) P[b * DO + o] /= bs;
        }
        for (let b = 0; b < bs; b++) {
          const x = X[ids[order[s + b]]], hb = h.subarray(b * DH, (b + 1) * DH);
          for (let o = 0; o < DO; o++) { const pv = P[b * DO + o]; gb2[o] += pv; for (let j = 0; j < DH; j++) g2[o * DH + j] += pv * hb[j]; }
          for (let j = 0; j < DH; j++) { let s2 = 0; for (let o = 0; o < DO; o++) s2 += P[b * DO + o] * p.w2[o * DH + j]; dh[j] = hb[j] > 0 ? s2 : 0; }
          for (let j = 0; j < DH; j++) { const d = dh[j]; gb1[j] += d; if (d === 0) continue; for (let i = 0; i < DI; i++) g1[j * DI + i] += d * x[i]; }
        }
        const G = { w1: g1, b1: gb1, w2: g2, b2: gb2 };
        for (const key of KEYS) {
          const w = p[key], g = G[key];
          for (let i = 0; i < w.length; i++) { let gi = g[i]; if (mu > 0) gi = gi + mu * (w[i] - anchor[key][i]); w[i] = w[i] - lr * gi; }
        }
      }
    }
    return p;
  }

  function run(X, y, parts, gIds, method, o) {
    const { rounds = 30, epochs = 2, lr = 0.1, batch = 20, mu = 0.1, p_drop = 0.0, seed = 0, onRound = null } = o;
    const rng = NLRT.mulberry32((seed * 7907 + 11) >>> 0), dropRng = NLRT.mulberry32((seed * 104729 + 3) >>> 0);
    const nc = parts.length; let g = initParams(seed);
    const curve = []; let commBytes = 0, uploads = 0;
    if (method === "local") {
      const models = parts.map(() => copy(g));
      for (let r = 0; r < rounds; r++) {
        for (let k = 0; k < nc; k++) if (parts[k].train.length) localTrain(models[k], X, y, parts[k].train, epochs, lr, batch, rng, 0, null);
        let s = 0; for (let k = 0; k < nc; k++) s += accuracy(models[k], X, y, gIds);
        curve.push(s / nc); if (onRound) onRound(r, curve);
      }
      return { curve, client_acc: parts.map((pt, k) => accuracy(models[k], X, y, pt.test)), comm_bytes: 0, uploads: 0 };
    }
    for (let r = 0; r < rounds; r++) {
      const updates = [];
      for (let k = 0; k < nc; k++) {
        commBytes += N_PARAMS * 4;
        const tr = parts[k].train, dropped = dropRng.random() < p_drop;
        if (!tr.length) continue;
        const local = localTrain(copy(g), X, y, tr, epochs, lr, batch, rng, method === "fedprox" ? mu : 0, g);
        if (dropped) continue;
        commBytes += N_PARAMS * 4; uploads++;
        updates.push([tr.length, local]);
      }
      if (updates.length) {
        let total = 0; for (const [n] of updates) total += n;
        const ng = {};
        for (const key of KEYS) {
          const out = new Float64Array(g[key].length);
          for (const [n, u] of updates) { const wgt = n / total; for (let i = 0; i < out.length; i++) out[i] += wgt * u[key][i]; }
          ng[key] = out;
        }
        g = ng;
      }
      curve.push(accuracy(g, X, y, gIds)); if (onRound) onRound(r, curve);
    }
    return { curve, client_acc: parts.map(pt => accuracy(g, X, y, pt.test)), comm_bytes: commBytes, uploads };
  }

  function init(assets) {
    const d = assets["digits.json"];
    return { X: d.pixels.map(r => r.map(v => v / 16)), y: d.y, pool: d.pool, test: d.global_test,
      hyper: assets["model.json"].meta.hyper };
  }

  // Partition the client pool (indices into the full array) like Python does.
  function makeClients(ctx, nClients, alpha, seed) {
    const ypool = ctx.pool.map(i => ctx.y[i]);
    return partition(ypool, nClients, alpha, seed).map(p => ({ train: p.train.map(i => ctx.pool[i]), test: p.test.map(i => ctx.pool[i]) }));
  }

  function runCase(ctx, input) {
    const parts = makeClients(ctx, input.n_clients, input.alpha, input.seed);
    const res = run(ctx.X, ctx.y, parts, ctx.test, input.method, { ...ctx.hyper, rounds: input.rounds, p_drop: input.p_drop, seed: input.seed });
    return { sizes: parts.map(p => p.train.length), curve: res.curve, client_acc: res.client_acc, comm_bytes: res.comm_bytes, uploads: res.uploads };
  }

  return { ASSETS, init, partition, makeClients, run, runCase, N_PARAMS };
});