Home
Resource
Random walk algorithms for private and decentralized learning on graphs
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Ayache, Ghadir. Random walk algorithms for private and decentralized learning on graphs. Retrieved from https://doi.org/doi:10.7282/t3-13bm-dk76

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleRandom walk algorithms for private and decentralized learning on graphs
NameAyache, Ghadir (author); El Rouayheb, Salim (chair); Sarwate, Anand (member); Yates, Roy (member); Gurbuzbalaban, Mert (member); Seferoglu, Hulya (member); Rutgers University; School of Graduate Studies
Date Created2022
Other Date2022-10 (degree)
SubjectComputer engineering, Electrical engineering, Computer science, Graph algorithms
Extent95 pages : illustrations
DescriptionDistributed Machine Learning has proven to be an essential framework for training machine learning models without moving the data from its local nodes, ensuring privacy and scalability. Our objective is to devise and study decentralized learning algorithms on the data distributed among the nodes of a graph with no parameter server (PS) involved. We focus on decentralized schemes that operate random walks on the graph nodes. In a random walk, the model is passed from one node to a randomly chosen neighbor and updated along the way by the local data at the visited nodes. We investigate tunable decentralization designs that adapt to multiple aspects such as privacy and data heterogeneity. Our objective is to achieve a desirable tradeoff between convergence rate, privacy (from other users and/or from PS) and communication cost.
In the first part of our work, we propose a random walk-based SGD algorithm in which the model is updated based on a biased random walk that performs importance sampling on the nodes. The transition probabilities are determined through a static importance metric that exploits available information on the users' data. The importance is precisely quantified through the gradient-Lipschitz constant of the local loss function. We provide a non-asymptotic analysis of the convergence rate, considering the constants related to the distributed data and the graph. Our numerical results show that our biased random walk learning algorithm performs better for high-variance data regimes than the oblivious sampling scheme that adopts a uniform strategy over the nodes.
In the second part, we look into a critical challenge in distributed systems which is the heterogeneity of the data across the different nodes. The non-IID distribution of the data imposes an inconsistency problem between the local and the global objectives, especially in a highly diverse network causing slower convergence or even divergence in some cases.
We devise a random walk learning algorithm that minimizes the local drift from the global objective in the model updates by visiting more frequently more informative nodes. Designing such an algorithm is confronted at an early stage by the uncertainty about the distribution of each node dataset. For this purpose, we propose an exploration-exploitation process that approaches the optimal sampling strategy by employing a multi-armed bandit model. We show the near-optimal convergence guarantees. We present numerical results for different graph settings to show that our algorithm outperforms state-of-art random walk design for speeding up the convergence under various heterogeneity levels.
The third part proposes a privacy-preserving random walk design that achieves local differential privacy using a novel Gamma noise-based mechanism. We show how this scheme attains the targeted stationary distribution and outperforms the additive state-of-art privacy mechanisms. We provide the tradeoff between the privacy level and the accuracy guarantees of our approach, and we numerically demonstrate its outperformance.
NotePh.D.
NoteIncludes bibliographical references
Genretheses
Persistent URLhttps://doi.org/doi:10.7282/t3-13bm-dk76
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024