nips nips2012 nips2012-275 nips2012-275-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Martin J. Wainwright, Michael I. Jordan, John C. Duchi
Abstract: We study statistical risk minimization problems under a version of privacy in which the data is kept confidential even from the learner. In this local privacy framework, we establish sharp upper and lower bounds on the convergence rates of statistical estimation procedures. As a consequence, we exhibit a precise tradeoff between the amount of privacy the data preserves and the utility, measured by convergence rate, of any statistical estimator. 1
[1] A. Agarwal, P. Bartlett, P. Ravikumar, and M. Wainwright. Information-theoretic lower bounds on the oracle complexity of convex optimization. IEEE Trans. on Information Theory, 58(5):3235–3249, 2012.
[2] A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31:167–175, 2003.
[3] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. PrenticeHall, Inc., 1989.
[4] P. Billingsley. Probability and Measure. Wiley, Second edition, 1986.
[5] A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In Proceedings of the Fourtieth Annual ACM Symposium on the Theory of Computing, 2008.
[6] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[7] K. Chaudhuri, C. Moneleoni, and A. D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069–1109, 2011.
[8] T. M. Cover and J. A. Thomas. Elements of Information Theory, Second Edition. Wiley, 2006.
[9] J. C. Duchi, M. I. Jordan, and M. J. Wainwright. Privacy aware learning. URL http://arxiv.org/abs/1210.2085, 2012.
[10] C. Dwork. Differential privacy: a survey of results. In Theory and Applications of Models of Computation, volume 4978 of Lecture Notes in Computer Science, p. 1–19. Springer, 2008.
[11] C. Dwork and J. Lei. Differential privacy and robust statistics. In Proceedings of the Fourty-First Annual ACM Symposium on the Theory of Computing, 2009.
[12] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference, p. 265–284, 2006.
[13] A. V. Evfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the Twenty-Second Symposium on Principles of Database Systems, p. 211–222, 2003.
[14] R. M. Gray. Entropy and Information Theory. Springer, 1990.
[15] R. Hall, A. Rinaldo, and L. Wasserman. Random differential privacy. URL http://arxiv.org/abs/1112.2680, 2011.
[16] J. Hiriart-Urruty and C. Lemar´ chal. Convex Analysis and Minimization Algorithms. Springer, 1996. e
[17] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011.
[18] L. Le Cam. On the asymptotic theory of estimation and hypothesis testing. Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, p. 129–156, 1956.
[19] L. Le Cam. Convergence of estimates under dimensionality restrictions. Annals of Statistics, 1(1):38–53, 1973.
[20] A. Nemirovski and D. Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
[21] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
[22] R. R. Phelps. Lectures on Choquet’s Theorem, Second Edition. Springer, 2001.
[23] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.
[24] B. I. P. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in a large function space: privacypreserving mechanisms for SVM learning. Journal of Privacy and Confidentiality, 4(1):65–100, 2012.
[25] L. Sankar, S. R. Rajagopalan, and H. V. Poor. An information-theoretic approach to privacy. In The 48th Allerton Conference on Communication, Control, and Computing, p. 1220–1227, 2010.
[26] A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the Fourty-Third Annual ACM Symposium on the Theory of Computing, 2011.
[27] A. W. van der Vaart. Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. ISBN 0-521-49603-9.
[28] A. Wald. Contributions to the theory of statistical estimation and testing hypotheses. Annals of Mathematical Statistics, 10(4):299–326, 1939.
[29] S. L. Warner. Randomized response: a survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965.
[30] L. Wasserman and S. Zhou. A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489):375–389, 2010.
[31] Y. Yang and A. Barron. Information-theoretic determination of minimax rates of convergence. Annals of Statistics, 27(5):1564–1599, 1999.
[32] B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, p. 423–435. Springer-Verlag, 1997.
[33] S. Zhou, J. Lafferty, and L. Wasserman. Compressed regression. IEEE Transactions on Information Theory, 55(2):846–866, 2009.
[34] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on Machine Learning, 2003. 9