Timezone: »
The covariance matrix of a dataset is a fundamental statistic that can be used for calculating optimum regression weights as well as in many other learning and data analysis settings. For datasets containing private user information, we often want to estimate the covariance matrix in a way that preserves differential privacy. While there are known methods for privately computing the covariance matrix, they all have one of two major shortcomings. Some, like the Gaussian mechanism, only guarantee (epsilon, delta)-differential privacy, leaving a non-trivial probability of privacy failure. Others give strong epsilon-differential privacy guarantees, but are impractical, requiring complicated sampling schemes, and tend to perform poorly on real data.
In this work we propose a new epsilon-differentially private algorithm for computing the covariance matrix of a dataset that addresses both of these limitations. We show that it has lower error than existing state-of-the-art approaches, both analytically and empirically. In addition, the algorithm is significantly less complicated than other methods and can be efficiently implemented with rejection sampling.
Author Information
Kareem Amin (Google Research)
Travis Dick (TTIC)
Alex Kulesza (Google)
Andres Munoz Medina (Google)
Sergei Vassilvitskii (Google)
More from the Same Authors
-
2021 : A Joint Exponential Mechanism for Differentially Private Top-k Set »
Andres Munoz Medina · Matthew Joseph · Jennifer Gillenwater · Monica Ribero Diaz -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2023 : RényiTester: A Variational Approach to Testing Differential Privacy »
Weiwei Kong · Andres Munoz Medina · Mónica Ribero -
2023 : A Unified Analysis of Label Inference Attacks »
Andres Munoz Medina · Travis Dick · Claudio Gentile · Róbert Busa-Fekete · Marika Swanberg -
2023 : A new Framework for Measuring Re-Identification Risk »
CJ Carey · Travis Dick · Alessandro Epasto · Adel Javanmard · Josh Karlin · Shankar Kumar · Andres Munoz Medina · Vahab Mirrokni · Gabriel H. Nunes · Sergei Vassilvitskii · Peilin Zhong -
2023 Poster: Easy Learning from Label Proportions »
Róbert Busa-Fekete · Heejin Choi · Travis Dick · Claudio Gentile · Andres Munoz Medina -
2023 Poster: A Unified Fast Gradient Clipping Framework for DP-SGD »
Weiwei Kong · Andres Munoz Medina -
2022 Poster: Private and Communication-Efficient Algorithms for Entropy Estimation »
Gecia Bravo-Hermsdorff · Róbert Busa-Fekete · Mohammad Ghavamzadeh · Andres Munoz Medina · Umar Syed -
2022 Affinity Workshop: LatinX in AI »
Maria Luisa Santiago · Juan Banda · CJ Barberan · MIGUEL GONZALEZ-MENDOZA · Caio Davi · Sara Garcia · Jorge Diaz · Fanny Nina Paravecino · Carlos Miranda · Gissella Bejarano Nicho · Fabian Latorre · Andres Munoz Medina · Abraham Ramos · Laura Montoya · Isabel Metzger · Andres Marquez · Miguel Felipe Arevalo-Castiblanco · Jorge Mendez · Karla Caballero · Atnafu Lambebo Tonja · Germán Olivo · Karla Caballero Barajas · Francisco Zabala -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Learning with Labeling Induced Abstentions »
Kareem Amin · Giulia DeSalvo · Afshin Rostamizadeh -
2021 Poster: Learning with User-Level Privacy »
Daniel Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2021 Social: Latinx in AI Social »
Andres Munoz Medina · Maria Luisa Santiago -
2021 : Closing Remarks »
Andres Munoz Medina -
2021 : Q&A Oral presentations »
Matias Valdenegro-Toro · Andres Munoz Medina · Johan Obando Ceron · Anil Batra -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2021 Affinity Workshop: LatinX in AI (LXAI) Research @ NeurIPS 2021 »
Maria Luisa Santiago · Andres Munoz Medina · Laura Montoya · Karla Caballero Barajas · Isabel Metzger · Jose Gallego-Posada · Juan Banda · Gabriela Vega · Amanda Duarte · Patrick Feeney · Lourdes Ramírez Cerna · Walter M Mayor · Omar U. Florez · Rosina Weber · Rocio Zorrilla -
2020 Poster: Sliding Window Algorithms for k-Clustering Problems »
Michele Borassi · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam -
2020 Poster: Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Ben Moseley · Philip Pham · Sergei Vassilvitskii · Yuyan Wang -
2019 : Pan-Private Uniformity Testing »
Kareem Amin · Matthew Joseph -
2019 : Coffee Break & Poster Session 1 »
Yan Zhang · Jonathon Hare · Adam Prugel-Bennett · Po Leung · Patrick Flaherty · Pitchaya Wiratchotisatian · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam · Theja Tulabandhula · Fabian Fuchs · Adam Kosiorek · Ingmar Posner · William Hang · Anna Goldie · Sujith Ravi · Azalia Mirhoseini · Yuwen Xiong · Mengye Ren · Renjie Liao · Raquel Urtasun · Haici Zhang · Michele Borassi · Shengda Luo · Andrew Trapp · Geoffroy Dubourg-Felonneau · Yasmeen Kussad · Christopher Bender · Manzil Zaheer · Junier Oliva · Michał Stypułkowski · Maciej Zieba · Austin Dill · Chun-Liang Li · Songwei Ge · Eunsu Kang · Oiwi Parker Jones · Kelvin Ka Wing Wong · Joshua Payne · Yang Li · Azade Nazi · Erkut Erdem · Aykut Erdem · Kevin O'Connor · Juan J Garcia · Maciej Zamorski · Jan Chorowski · Deeksha Sinha · Harry Clifford · John W Cassidy -
2019 Poster: Envy-Free Classification »
Maria-Florina Balcan · Travis Dick · Ritesh Noothigattu · Ariel Procaccia -
2018 : Poster Session »
Phillipp Schoppmann · Patrick Yu · Valerie Chen · Travis Dick · Marc Joye · Ningshan Zhang · Frederik Harder · Olli Saarikivi · Théo Ryffel · Yunhui Long · Théo JOURDAN · Di Wang · Antonio Marcedone · Negev Shekel Nosatzki · Yatharth A Dubey · Antti Koskela · Peter Bloem · Aleksandra Korolova · Martin Bertran · Hao Chen · Galen Andrew · Natalia Martinez · Janardhan Kulkarni · Jonathan Passerat-Palmbach · Guillermo Sapiro · Amrita Roy Chowdhury -
2018 : Posters 1 »
Wei Wei · Flavio Calmon · Travis Dick · Leilani Gilpin · Maroussia Lévesque · Malek Ben Salem · Michael Wang · Jack Fitzsimons · Dimitri Semenovich · Linda Gu · Nathaniel Fruchter -
2018 Poster: Maximizing Induced Cardinality Under a Determinantal Point Process »
Jennifer Gillenwater · Alex Kulesza · Sergei Vassilvitskii · Zelda Mariet -
2018 Poster: Completing State Representations using Spectral Learning »
Nan Jiang · Alex Kulesza · Satinder Singh -
2018 Poster: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2018 Spotlight: Data-Driven Clustering via Parameterized Lloyd's Families »
Maria-Florina Balcan · Travis Dick · Colin White -
2017 Poster: Repeated Inverse Reinforcement Learning »
Kareem Amin · Nan Jiang · Satinder Singh -
2017 Poster: Revenue Optimization with Approximate Bid Predictions »
Andres Munoz Medina · Sergei Vassilvitskii -
2017 Poster: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Spotlight: Fair Clustering Through Fairlets »
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii -
2017 Spotlight: Repeated Inverse Reinforcement Learning »
Kareem Amin · Nan Jiang · Satinder Singh -
2017 Poster: Statistical Cost Sharing »
Eric Balkanski · Umar Syed · Sergei Vassilvitskii -
2016 Poster: On Mixtures of Markov Chains »
Rishi Gupta · Ravi Kumar · Sergei Vassilvitskii