Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties

By Feng Yan, Shreyas Sundaram, S. V. N. Vishwanathan, Yuan (Alan) Qi. 2010

300 citations recorded by the source corpus.

Online learning has become increasingly popular on handling massive data. The sequential nature of online learning, however, requires a centralized learner to store data and update parameters. In this paper, we consider online learning with distributed data sources. The autonomous learners update local parameters based on local data sources and periodically exchange information with a small subset of neighbors in a communication network. We derive the regret bound for strongly convex functions that generalizes the work by Ram et al. for convex functions. More importantly, we show that our algorithm has intrinsic privacy-preserving properties, and we prove the sufficient and necessary conditions for privacy preservation in the network. These conditions imply that for networks with greater-than-one connectivity, a malicious learner cannot reconstruct the subgradients (and sensitive raw data) of other learners, which makes our algorithm appealing in privacy-sensitive applications.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “Besides, Reference [37] provides necessary and sufficient conditions to preserve privacy for decentralized online learning methods, which be studied to extend our method in our future work.”
Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, background): “1 Decentralized algorithms are mainly studied as consensus optimization problems by the control community [Ram et al., 2010, Yan et al., 2013, Yuan et al., 2016] for the application scenario where only a decentralized network is available.”
Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “…algorithms have been studied as consensus optimization in the control community and used for preserving data privacy [Ram et al., 2009a, Yan et al., 2013, Yuan et al., 2016], for the application scenario where only the decentralized network is available, it is still an open question if…”
On the Convergence of Decentralized Gradient Descent (2013, background): “Compared to optimization with a fusion center that collects data and performs computation, decentralized optimization enjoys the advantages of scalability to network sizes, robustness to dynamic topologies, and privacy preservation in data-sensitive applications [7, 17, 22, 32].”
An Exact Quantized Decentralized Gradient Descent Algorithm (2018, background): “Furthermore, the decentralized consensus optimization problem has been considered in online or dynamic settings, where the dynamic cost function becomes an online regret function [22].”
On Nonconvex Decentralized Gradient Descent (2016, background): “Furthermore, although DGD is slower than DADMM, DLM and EXTRA on convex problems, DGD is simpler and thus easier to extend to a variety of settings such as [23], [38], [47], [64], where online processing and delay tolerance are considered.”
Quantized Decentralized Consensus Optimization (2018, background): “Furthermore, the decentralized consensus optimization problem has been considered in online or dynamic settings, where the dynamic cost function becomes an online regret function [20], [21].”
Prox-PDA: The Proximal Primal-Dual Algorithm for Fast Distributed Nonconvex Optimization and Learning Over Networks (2017, background): “…as document topic modeling and/or social network data analysis, oftentimes data corporas are stored in geographically distributed locations without any central controller managing the entire network of nodes; see (Forero et al., 2010; Yan et al., 2013; Rahmani & Atia, 2015; Aybat & Hamedani, 2016).”
A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, background): “These advantages lead to successful applications of decentralized optimization in robotic networks [14], [15], wireless sensor networks [4], [16], smart grids [17], [18], and distributed machine learning systems [19], [20], just to name a few.”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, background): “This definition of privacy is inspired by the privacypreservation definitions in [4], [39], [51]–[54] which take advantages of the fact that if a system of equations has infinite number of solutions, it is impossible to derive the exact value of the original input data from the output data.”
Multi-Agent Distributed Lifelong Learning for Collective Knowledge Acquisition (2017, background): “Distributed Machine Learning: There has been a growing interest in developing scalable learning algorithms using distributed optimization [40], motivated by the emergence of big data [6], security and privacy constraints [37], and the notion of cooperative and collaborative learning agents [8].”
Adaptation, Learning, and Optimization over Networks (2014, background): “Nevertheless, solution techniques that rely on the use of projection operations require the constraint conditions to be relatively simple in order for the distributed algorithm to be able to compute the necessary projections analytically (such as projecting onto the nonnegative orthant) [154, 227, 2”
Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication (2014, unknown): “Our work here also touches, albeit slightly, on the concept of privacy preservation, see e.g., [Weeraddana et al., 2013, Yan et al., 2013] for recent works in the context of distributed multi-agent optimization.”
Distributed Online Convex Optimization on Time-Varying Directed Graphs (2017, methodology): “This work builds on gradientdescent methods that have been used extensively for online convex optimization; see [12]–[14] for a recent survey.”
Online distributed optimization via dual averaging (2013, background): “in [14] introduced a decentralized online optimization based on dual averaging in which the agents are interacting over a weighted strongly connected directed graph.”
Excess-Risk of Distributed Stochastic Learners (2013, background): “Specifically, we will show that the strategies under study achieve a better convergence rate than noncooperative algorithms, and we will also explain why diffusion strategies outperform other distributed solutions such as those relying on consensus constructions or on doublystochastic combination po”
Online Learning over a Decentralized Network Through ADMM (2015, methodology): “In the numerical experiments, we compare oDM with two decentralized online learning algorithms: (1) Distributed online gradient descent (DOGD) [11]; (2) Distributed autonomous online learning (DAOL) [7].”
Adaptive Networks (2014, methodology): “…techniques that rely on the use of similar projection operations require the constraint conditions to be relatively simple in order for the distributed algorithm to be able to compute the necessary projections analytically (such as projecting onto the nonnegative orthant) [119], [120], [166].”
Asynchronous Decentralized Online Learning (2021, background): “The above bound can be further simplified under the bounded gradient norm assumption [27].”