Distributed empirical risk minimization with differential privacy

Changxin Liu, Changxin Liu 0001, Karl Henrik Johansson, Yang ShiAutomatica 2024 · DOI

TL;DR

This paper introduces a novel distributed optimization algorithm that achieves differential privacy with significantly improved utility compared to existing methods. By strategically activating only a fraction of nodes at each step and perturbing their local gradients, the algorithm amplifies privacy guarantees, allowing for less noise and better model performance in distributed machine learning settings.

What Problem Does This Paper Address?

Training machine learning models often involves aggregating data from multiple sources, raising privacy concerns. Differential privacy (DP) offers a robust framework to protect individual data, but applying it to distributed optimization problems (like training a model across many devices) is challenging. Standard DP approaches in distributed settings require adding substantial noise to local computations to mask individual contributions, which severely degrades the model's accuracy (utility). This paper tackles the problem of achieving strong DP guarantees in distributed empirical risk minimization (ERM) while minimizing this utility loss.

Methods

The core contribution is a new class of Differentially Private Distributed Dual Averaging (DDA) algorithms. The key innovation lies in a node subsampling strategy: at each iteration, only a random fraction of the nodes are activated to perform local optimization. These activated nodes then compute their local stochastic subgradients and add carefully calibrated Gaussian noise to achieve DP. This subsampling mechanism effectively "amplifies" the DP guarantee, meaning the same level of privacy can be achieved with less noise compared to methods that require all nodes to participate and add noise. The algorithm also incorporates a private dual averaging update rule, which is analyzed for both general and strongly convex optimization problems.

Datasets

The paper evaluates its proposed algorithms on two benchmark datasets:

  • epsilon: A dataset with 400,000 samples and 2,000 features.
  • rcv1: A dataset with 677,399 samples and 47,236 features.

These datasets were used to train regularized Support Vector Machines (SVMs) with either L2 (ridge) or L1 (lasso) regularization. The data was distributed evenly among 20 simulated working nodes.

Key Insights and Ideas

  • Subsampling as a Privacy Amplifier: Randomly activating a subset of nodes is a surprisingly effective way to boost DP guarantees. This allows for less noise per node, leading to better utility.
  • Trade-off Between Connectivity and Noise: While activating more nodes (higher sampling ratio) improves network connectivity, it can also necessitate more noise to maintain DP, potentially outweighing the benefits. The optimal sampling ratio depends on the specific problem and privacy budget.
  • Improved Convergence for Non-Smooth Optimization: The paper claims to advance the state-of-the-art convergence rate for non-smooth stochastic optimization using DDA, achieving O(1/t) compared to previous O(1/√t) results.
  • DP's Impact on Utility: As expected, tighter DP constraints (smaller epsilon) lead to lower model accuracy (higher suboptimality), but the proposed method shows a more favorable trade-off than prior work.

Key Results

  • The proposed private DDA algorithm achieves improved utility (lower suboptimality and higher accuracy) compared to a prior state-of-the-art distributed DP algorithm ([19]) across various DP parameters (ε) and sampling ratios (ι).
  • For L2-regularized SVM, the algorithm demonstrates faster convergence and better accuracy, especially with tighter DP constraints.
  • For L1-regularized SVM (non-smooth case), the algorithm also shows superior performance, with utility loss decreasing as the sampling ratio (ι) increases (meaning fewer nodes are activated).
  • The theoretical analysis provides bounds on convergence and privacy-utility trade-offs, showing that the utility loss is comparable to centralized private algorithms.

Limitations and Future Work

  • Heterogeneous Data: The current analysis primarily assumes homogeneous data distribution across nodes. The authors suggest exploring scenarios with substantial variations in dataset size and Lipschitz constants.
  • High-Probability Convergence: The current theoretical results focus on expected convergence. Investigating high-probability convergence bounds would be a valuable extension.
  • Further Exploration of Sampling: The paper hints that the number of iterations might need to increase to achieve lower utility loss with subsampling, and further exploration of this dynamic is suggested.
  • Other Privacy Mechanisms: While Gaussian noise is used, exploring other DP mechanisms or combinations could be a future direction.

Summary updated

BibTeX
@article{liu2024distributed,
  author = {Changxin Liu and Changxin Liu and Karl Henrik Johansson and Yang Shi},
  title = {{Distributed empirical risk minimization with differential privacy}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2024.111514},
}
Figure