CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning

I. INTRODUCTION

• CodedPrivateML uses information-theoretic privacy and distributed computation, encoding data and model parameters to reduce communication overhead and training complexity.Its framework targets colluding workers while distributing computation across multiple workers.Source: §I · p. 1
• CodedPrivateML combines stochastic quantization and Lagrange coding with polynomial approximation of the sigmoid so workers can compute gradients on encoded data.The master decodes gradients and updates the model between training rounds.Source: §I · pp. 1–2
• Up to 5.2× speedup over the MPC baseline was reported for CIFAR-10 and GISETTE logistic-regression training, with comparable accuracy.Experiments used Amazon EC2 machines, up to N=50; MPC can provide a higher privacy threshold T.Source: §I · p. 2

A. Other related works

• Homomorphic encryption offers computationally based privacy but is described as much slower, while differential privacy targets protection when model parameters are publicly released.The paper distinguishes its focus on information-theoretic privacy during training from differential privacy’s noisy release approach.Source: A. Other related works · p. 2

II. SYSTEM MODEL

• The system models a master offloading logistic-regression gradient computations to N workers and protecting the dataset against up to T colluding workers.A T-private protocol prevents those workers from learning information about the original dataset; linear regression is also supported with minor modifications.Source: §II · p. 3

III. THE CODEDPRIVATEML PROTOCOL

• CodedPrivateML has four stages: quantization, encoding, polynomial-approximation gradient computation, and gradient decoding with model update.The master repeats weight quantization and encoding at each iteration.Source: §III · p. 3

A. Quantization

• Stochastic quantization converts real-valued data and weights into integers embedded in a finite field, enabling random masking for information-theoretic privacy.The dataset is quantized element-wise; the finite field supports the protocol’s encoding and decoding operations.Source: A. Quantization · p. 3
• Independent stochastic quantizations of each weight vector are used so gradients computed from quantized weights are unbiased estimators of true gradients, supporting convergence analysis.The number of quantized vectors r equals the degree of the sigmoid polynomial approximation.Source: A. Quantization · p. 4
• The quantization parameters trade rounding error against overflow risk: larger values reduce rounding error but increase the chance of overflow.The prime-field size must also be large enough to avoid wrap-around during intermediate multiplications.Source: A. Quantization · p. 4

B. Encoding the Dataset and the Model

• Increasing K as the number of workers N grows can reduce each worker’s computation and communication overhead, while the encoding protects the dataset against T colluding workers.K is tied to computation load because each worker receives an encoded dataset one Kth the size of the original.Source: B. Encoding the Dataset and the Model · p. 4
• The master also quantizes and encodes the current weights with the same evaluation points, preventing direct transmission of model estimates that carry information about the training set.The encoded weights use the same Lagrange-coding construction as the dataset.Source: B. Encoding the Dataset and the Model · pp. 4–5
• The master partitions the quantized dataset into K blocks and uses Lagrange interpolation with random values to form an encoding polynomial.The polynomial encodes the data blocks and random masks before evaluation at worker points.Source: B. Encoding the Dataset and the Model · p. 4

C. Polynomial Approximation and Gradient Computation

• A polynomial approximation of the sigmoid makes the nonlinear gradient computation compatible with Lagrange coding.The polynomial coefficients are obtained by fitting the sigmoid via least-squares estimation.Source: C. Polynomial Approximation and… · p. 5
• Using r independent quantizations of the weights makes the resulting gradient estimator unbiased for the approximated sigmoid output.The passage identifies this unbiasedness as fundamental to the convergence analysis.Source: C. Polynomial Approximation and… · p. 5
• CodedPrivateML is stated to converge to the optimal loss even when the update substitutes the polynomial approximation for the sigmoid.Source: C. Polynomial Approximation and… · p. 5

D. Decoding the Gradient and Model Update 푓

• (2r+1)(K+T−1)+1 workers are required for successful decoding.The passage names this minimum the protocol’s recovery threshold.Source: D. Decoding the Gradient and Model… · p. 5
• The master interpolates h(z) from worker evaluations and evaluates the recovered polynomial at β_i to recover the encoded gradients.The degree of h(z) is at most (2r+1)(K+T−1).Source: D. Decoding the Gradient and Model… · p. 5
• After decoding, the master converts the result from the finite field to the real domain and updates the weights.Workers compute locally and send their results to the master; the algorithm describes this per iteration.Source: D. Decoding the Gradient and Model… · pp. 5–6

IV. THEORETICAL RESULTS

• For the quantized dataset, the cost-function gradient is L-Lipschitz, a property used in the theorem’s step-size condition.Source: §IV · p. 6
• The gradient estimate is asymptotically unbiased as polynomial degree r increases, and its variance is bounded.Source: §IV · p. 6
• For distributed logistic-regression training with CodedPrivateML and constant step size η=1/L (L defined in Lemma 2), dataset X remains information-theoretically private against any T colluding workers when N≥(2r+1)(K+T−1)+1.Source: §IV · p. 6
• With N workers, the condition N≥(2r+1)(K+T−1)+1 constrains the achievable privacy threshold T and parallelization parameter K.The passage states that both K and T can increase linearly as N increases.Source: §IV · p. 6
• CodedPrivateML’s convergence rate is O(1/J), while its constant-step-size bound retains a residual term that can be made arbitrarily small with a decreasing learning rate.The passage identifies the residual term as σ²/L.Source: §IV · p. 6
• The theorem also applies to linear regression, with a proof following the same steps.Source: §IV · p. 7

A. Complexity Analysis

• O(mdN(K+T)) is the total cost of encoding the dataset across N workers.Each encoding combines K+T matrices.Source: A. Complexity Analysis · p. 7
• O(dJNK) is the master’s total cost for decoding gradients across J iterations and K decoded gradients.Source: A. Complexity Analysis · p. 7
• O(md²/K) is the worker computation cost, corresponding to 1/K of conventional logistic regression’s computation cost.Source: A. Complexity Analysis · p. 7
• A worker’s communication cost for sending local computations to the master is O(dJ).Source: A. Complexity Analysis · p. 7

Training time

• Up to 4.4× speedup on CIFAR-10 and 5.2× on GISETTE over MPC baselines, with the same privacy threshold as the benchmarks.The comparison uses Case 2; Fig. 3 plots total training time against worker count.Source: §V · p. 8, Figure 3 · p. 8
• With N=10 workers, all schemes have similar performance because each worker stores one-third of the whole dataset; this corresponds to K=3 for CodedPrivateML and G=3 for the benchmark.Source: §V · p. 8
• Adding workers reduces CodedPrivateML's per-worker computation through increased parallelization, but increases master encoding time and can eventually saturate runtime gains.The authors also attribute lower computation and communication overhead to each worker processing 1/K of the dataset rather than one-third as in the MPC baselines.Source: §V · pp. 8–9
• Up to 22.5× speedup over BGW on CIFAR-10 with 50 workers; BGW requires extra worker communication for degree reduction at each multiplication.The authors attribute the speedup to avoiding that additional communication phase.Source: §V · p. 9

Accuracy

• At 50 iterations, accuracy is 81.35% versus 81.75% on CIFAR-10 and 97.5% for both methods on GISETTE.These comparisons are between CodedPrivateML with degree-one polynomial approximation and conventional logistic regression.Source: Figure 4 · p. 8, §V · p. 9
• CodedPrivateML converges at a comparable rate to conventional logistic regression on GISETTE despite polynomial approximation and quantization.The comparison uses cross-entropy loss; the conventional setup uses the sigmoid without polynomial approximation or quantization.Source: §V · p. 9

Conclusion

• CodedPrivateML distributes computation across workers and reduces per-worker computation as more workers become available.The paper reports theoretical convergence guarantees and trade-offs among worker count, privacy protection, and scalability.Source: §VI · p. 9

Discussion

• The work focuses on logistic regression as a first step toward more complex models, with deeper neural networks and collaborative learning left as future directions.The authors frame extension beyond logistic regression as future work.Source: §VI · p. 9
• Finite-field quantization creates challenges in selecting the field size and avoiding accuracy degradation from quantization or overflow error.The paper identifies analog coded computing as a possible future direction for addressing these challenges.Source: §VI · p. 9

A. Proof of Lemma 1

• For bounded weights, the sigmoid can be approximated by a polynomial with arbitrarily small error, supporting the proof's approximation step.The stated condition is that the weight vector has norm at most B.Source: A. Proof of Lemma 1 · p. 12

B. Proof of Lemma 2

• The proof identifies the logistic-regression cost function's Lipschitz constant using the largest eigenvalue of its Hessian.Source: B. Proof of Lemma 2 · p. 12

• (2r+1)(K+T−1)+1 worker results suffice for decoding, and the worker count N must meet this threshold.The master interpolates h(z) from worker evaluations and uses the recovered polynomial to decode.Source: C. Proof of Theorem 1 · p. 12
• The convergence proof targets w* and uses convexity, an L-Lipschitz gradient, and an unbiased gradient estimate with bounded variance.It takes expectation over quantization noise and assumes an arbitrarily large r for the stated variance bound.Source: C. Proof of Theorem 1 · pp. 12–13
• The proof concludes that the original dataset remains information-theoretically private against T colluding workers.Source: C. Proof of Theorem 1 · p. 14

Multiplication

• O(N) communication for, trades against significant offline computation and per-worker storage, while BGW has O(N^2) communication.The latter protocol uses offline random masks to reduce communication during multiplication.Source: D. Details of the Secure Multi-Party… · pp. 14–15

• Shamir secret sharing embeds each secret in a degree-T polynomial with random coefficients, protecting it against collusion among up to T workers.Worker i receives the polynomial evaluation h(i) as its share.Source: D. Details of the Secure Multi-Party… · p. 14

Addition

• Addition is computed locally by adding workers’ shares and applying a modulo operation.Source: D. Details of the Secure Multi-Party… · p. 14

Multiplication

• BGW multiplies shares locally, producing a degree-2T polynomial, then reduces its degree to T to prevent excessive degree growth across multiplication gates.Its communication overhead is O(N^2).Source: D. Details of the Secure Multi-Party… · pp. 14–15
• Protocols, use offline random shares to mask the degree-2T product; workers broadcast masked values, decode the masked product, then obtain degree-T shares.The random mask cancels out in the final shares.Source: D. Details of the Secure Multi-Party… · p. 15