Distributed private online learning for social big data computing over data center networks

Chencheng Li, Pan Zhou, Yingxue Zhou, Kaigui Bian, Tao Jiang, Susanto Rahardja

This paper, published in 2016, addresses the intersection of three major challenges in modern data science: distributed computing, high-dimensional feature spaces, and individual privacy. As social media platforms generate hundreds of terabytes of data daily across global data centers, the authors propose a framework to mine this "Social Big Data" efficiently and securely.

TL;DR

The authors present a distributed online learning algorithm that uses Lasso-based sparsity to handle high-dimensional social data while incorporating differential privacy to protect user information. Their approach achieves a standard $O(\sqrt{T})$ regret bound, proving that privacy and efficiency can coexist in large-scale, decentralized social networks.

What Problem Does This Paper Address?

Social big data is characterized by three "H's": it is Huge (volume), High-dimensional (thousands of features per user), and Highly distributed (stored in data centers worldwide).

Traditional centralized machine learning is often impossible due to the sheer cost of moving data and the privacy risks involved. Furthermore, while a user's profile might contain thousands of data points, only a few (like age or location) might be relevant to a specific prediction task (like "will they click this ad?"). Existing methods struggled to balance the need for sparsity (ignoring irrelevant features) with distributed optimization and differential privacy (preventing malicious actors from "reversing" model updates to steal user data).

Methods

The authors propose a Private Distributed Online Learning algorithm. Key components include:

  • Distributed Optimization: Instead of a central server, each data center maintains its own model parameter vector ($w$). Centers exchange these parameters with immediate neighbors in a communication graph.
  • Online Mirror Descent (OMD): The core learning framework used to update models as new data arrives in real-time.
  • Lasso ($L_1$ Regularization): To handle high dimensionality, the algorithm incorporates an $L_1$ penalty. This "pushes" irrelevant feature weights to zero, creating a sparse model that is computationally cheaper and less prone to overfitting.
  • Differential Privacy (DP): Before broadcasting model updates to neighbors, the algorithm adds Laplace noise. This ensures that the presence or absence of a single user's data in a data center doesn't significantly change the output, effectively masking individual identities from potential adversaries.

Datasets

The authors evaluated their algorithm using:

  • Real-world Social Data: A dataset consisting of 100,000 social data entries with 10,000 dimensions.
  • Preprocessing: Dimensions were normalized, and data points were labeled for classification tasks.
  • Simulation Environment: A distributed model designed via Hadoop on a Linux cluster (8 CPU cores, 64GB RAM).

Key Insights and Ideas

  • Sparsity is a Feature, Not a Bug: The authors found that inducing sparsity actually enhanced performance. By filtering out the "noise" of irrelevant high-dimensional features, the model became more accurate, not just faster.
  • The Privacy-Utility Trade-off is Manageable: While adding noise for privacy (decreasing $\epsilon$) naturally increases the "regret" (error) of the model, the authors proved mathematically and empirically that the performance hit is not catastrophic.
  • Topology Resilience: The specific way data centers are connected (the network topology) had no significant impact on the final utility of the algorithm, suggesting the method is robust for various global infrastructure layouts.

Key Results

  • Regret Bound: The algorithm achieves a regret bound of $O(\sqrt{T})$, which is the theoretical "gold standard" for online learning, indicating that the model's mistakes decrease significantly over time.
  • Accuracy Gains: Inducing sparsity through their method improved accuracy by nearly 18% compared to non-sparse distributed computing methods.
  • Scalability: Increasing the number of data centers resulted in only a minor decline in accuracy (roughly 4% for every 4 additional nodes), demonstrating that the system scales well to large, global networks.
  • Privacy Performance: Simulations showed that even with strict privacy requirements, the regret bound remained close to the non-private baseline.

Limitations and Future Work

  • Network Latency: The current model does not fully account for communication delays between data centers, which is a major factor in real-world global networks. The authors suggest "online learning with delay" as a critical next step.
  • Dynamic Data: While the model handles online data, the impact of rapidly shifting social trends (concept drift) on the sparse feature selection could be explored further.
  • Noise Optimization: Future work could investigate more sophisticated noise-adding mechanisms that might further reduce the gap between private and non-private model performance.

Summary updated

Abstract

With the rapid growth of Internet technologies, cloud computing and social networks have become ubiquitous. An increasing number of people participate in social networks and massive online social data are obtained. In order to exploit knowledge from copious amounts of data obtained and predict social behavior of users, we urge to realize data mining in social networks. Almost all online websites use cloud services to effectively process the large scale of social data, which are gathered from distributed data centers. These data are so large-scale, high-dimension and widely distributed that we propose a distributed sparse online algorithm to handle them. Additionally, privacy-protection is an important point in social networks. We should not compromise the privacy of individuals in networks, while these social data are being learned for data mining. Thus we also consider the privacy problem in this article. Our simulations shows that the appropriate sparsity of data would enhance the performance of our algorithm and the privacy-preserving method does not significantly hurt the performance of the proposed algorithm.
BibTeX
@inproceedings{li2016distributed,
  author = {Chencheng Li and Pan Zhou and Yingxue Zhou and Kaigui Bian and Tao Jiang and Susanto Rahardja},
  title = {{Distributed private online learning for social big data computing over data center networks}},
  booktitle = {ICC},
  year = {2016},
  url = {https://openreview.net/forum?id=Gk6rTfeBmE},
}

Loading related content...

Figure