publication . Preprint . Article . 2015

Privacy Preservation in Distributed Subgradient Optimization Algorithms

Youcheng Lou; Lean Yu; Shouyang Wang; Peng Yi;
Open Access English
  • Published: 29 Dec 2015
Abstract
Privacy preservation is becoming an increasingly important issue in data mining and machine learning. In this paper, we consider the privacy preserving features of distributed subgradient optimization algorithms. We first show that a well-known distributed subgradient synchronous optimization algorithm, in which all agents make their optimization updates simultaneously at all times, is not privacy preserving in the sense that the malicious agent can learn other agents' subgradients asymptotically. Then we propose a distributed subgradient projection asynchronous optimization algorithm without relying on any existing privacy preservation technique, where agents c...
Subjects
free text keywords: Computer Science - Distributed, Parallel, and Cluster Computing, Mathematics - Optimization and Control, Subgradient method, Linear programming, Distributed algorithm, Mathematics, Asynchronous communication, Dykstra's projection algorithm, Information sensitivity, Algorithm design, Convergence (routing), Mathematical optimization
Related Organizations
27 references, page 1 of 2

[1] A. Nedi´c and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Trans. Autom. Control, vol. 54, no. 1, pp. 48-61, Jan. 2009.

[2] A. Nedi´c, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and optimization in multi-agent networks,” IEEE Trans. Autom. Control, vol. 55, no. 4, pp. 922-938, Apr. 2010.

[3] S. S. Ram, A. Nedi´c, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” J. Optim. Theory Appl., vol. 147, no. 3, pp. 516-545, Jul. 2010.

[4] I. Lobel and A. Ozdaglar, Distributed subgradient methods for convex optimization over random networks, IEEE Trans. Automat. Control, 56 (2011) 1291-1306. [OpenAIRE]

[5] B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental subgradient method for distributed optimization in networked systems,” SIAM J. Optim., vol. 20, no. 3, pp. 1157-1170, 2010.

[6] J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” IEEE Trans. Autom. Control, vol. 57, no. 3, pp. 592-606, Mar. 2012.

[7] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, Jul. 2011.

[8] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin, “On the linear convergence of the ADMM in decentralized consensus optimization,” IEEE Trans. Sig. Proc., vol. 62, no. 7, pp. 1750-1761, Apr. 2014.

[9] Y. Lou, Y. Hong, L. Xie, G. Shi, and K. H. Johansson, “Nash equilibrium computation in subnetwork zero-sum games with switching communications,” IEEE Trans. Autom. Control, vol. 61, no. 10, Oct. 2016, to appear, A previous Arxiv version is available at http://arxiv.org/abs/1312.7050

[10] Y. Lou, G. Shi, K. H. Johansson, and Y. Hong, “Convergence of random sleep algorithms for optimal consensus,” Systems & Control Letters, vol. 62, no. 12, pp. 1196-1202, Dec. 2013.

[11] Y. Lou, G. Shi, K. H. Johansson, and Y. Hong, “Approximate projected consensus for convex intersection computation: Convergence analysis and critical error angle,” IEEE Trans. Autom. Control, vol. 59, no. 7, pp. 1722-1736, Jul. 2014.

[12] G. Shi and K. H. Johansson, “Randomized optimal consensus of multi-agent systems,” Automatica, vol. 48, no. 12, pp. 3018-3030, Dec. 2012.

[13] D. Jakovetic, D. Bajovic, N. Krejic, and N. Krklec-Jerinkic, “Distributed gradient methods with variable number of working nodes,” Available at http://arxiv.org/abs/1504.04049

[14] K. Srivastava and A. Nedi´c, “Distributed asynchronous constrained stochastic optimization,” IEEE J. Selec. Top. Sig. Process., vol. 5, no. 4, pp. 772-790, Aug. 2011.

[15] A. Nedi´c, “Asynchronous broadcast-based convex optimization over a network,” IEEE Trans. Autom. Control, vol. 56, no. 6, pp. 1337-1351, Jun. 2011.

27 references, page 1 of 2
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Article . 2015

Privacy Preservation in Distributed Subgradient Optimization Algorithms

Youcheng Lou; Lean Yu; Shouyang Wang; Peng Yi;