More Like this

1. Privately Estimating Graph Parameters in Sublinear Time

   https://doi.org/10.4230/LIPIcs.ICALP.2022.82  

   Blocki, J; Grigorescu, E; Mukherjee, T. (January 2022, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022).)

   Mikołaj Boja´nczyk, Emanuela Merelli (Ed.)

   We initiate a systematic study of algorithms that are both differentially-private and run in sublinear time for several problems in which the goal is to estimate natural graph parameters. Our main result is a differentially-private $$(1+\rho)$$-approximation algorithm for the problem of computing the average degree of a graph, for every $$\rho>0$$. The running time of the algorithm is roughly the same (for sparse graphs) as its non-private version proposed by Goldreich and Ron (Sublinear Algorithms, 2005). We also obtain the first differentially-private sublinear-time approximation algorithms for the maximum matching size and the minimum vertex cover size of a graph. An overarching technique we employ is the notion of \emph{coupled global sensitivity} of randomized algorithms. Related variants of this notion of sensitivity have been used in the literature in ad-hoc ways. Here we formalize the notion and develop it as a unifying framework for privacy analysis of randomized approximation algorithms. 

   more » « less
2. Differentially Private Identity and Equivalence Testing of Discrete Distributions

   Aliakbarpour, Maryam; Diakonikolas, Ilias; Rubinfeld, Ronitt (July 2018, Proceedings of the 35th International Conference on Machine Learning (ICML 2018))

   We study the fundamental problems of identity and equivalence testing over a discrete populationfrom random samples. Our goal is to develop efficient testers while guaranteeingdifferential privacy to the individuals of the population. We provide sample-efficient differentially private testers for these problems.Our theoretical results significantly improve over the best known algorithms for identity testing, and are the first results for private equivalence testing. The conceptual message of our work is thatthere exist private hypothesis testers that are nearly as sample-efficient as their non-private counterparts. We perform an experimental evaluation of our algorithms on synthetic data. Our experiments illustrate that our private testers achieve small type I and type II errors with sample size sublinear in the domain size of the underlying distributions. 

   more » « less
3. Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget

   https://doi.org/10.1145/3219819.3220076  

   Lee, Jaewoo; Kifer, Daniel (August 2018, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining)

   Iterative algorithms, like gradient descent, are common tools for solving a variety of problems, such as model fitting. For this reason, there is interest in creating differentially private versions of them. However, their conversion to differentially private algorithms is often naive. For instance, a fixed number of iterations are chosen, the privacy budget is split evenly among them, and at each iteration, parameters are updated with a noisy gradient. In this paper, we show that gradient-based algorithms can be improved by a more careful allocation of privacy budget per iteration. Intuitively, at the beginning of the optimization, gradients are expected to be large, so that they do not need to be measured as accurately. However, as the parameters approach their optimal values, the gradients decrease and hence need to be measured more accurately. We add a basic line-search capability that helps the algorithm decide when more accurate gradient measurements are necessary. Our gradient descent algorithm works with the recently introduced zCDP version of differential privacy. It outperforms prior algorithms for model fitting and is competitive with the state-of-the-art for $(ε,δ)$-differential privacy, a strictly weaker definition than zCDP. 

   more » « less
4. Deciding Differential Privacy of Online Algorithms with Multiple Variables

   https://doi.org/10.1145/3576915.3623170  

   Chadha, Rohit; Sistla, A Prasad; Viswanathan, Mahesh; Bhusal, Bishnu (November 2023, ACM CCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security)

   We consider the problem of checking the differential privacy of online randomized algorithms that process a stream of inputs and produce outputs corresponding to each input. This paper generalizes an automaton model called DiP automata [10] to describe such algorithms by allowing multiple real-valued storage variables. A DiP automaton is a parametric automaton whose behavior depends on the privacy budget ∈. An automaton A will be said to be differentially private if, for some D, the automaton is D∈-differentially private for all values of ∈ > 0. We identify a precise characterization of the class of all differentially private DiP automata. We show that the problem of determining if a given DiP automaton belongs to this class is PSPACE-complete. Our PSPACE algorithm also computes a value for D when the given automaton is differentially private. The algorithm has been implemented, and experiments demonstrating its effectiveness are presented. 

   more » « less
5. Differentially Private Decomposable Submodular Maximization

   Chaturvedi, Anamay; Nguyễn, Huy Lê; Zakynthinou, Lydia (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance. 

   more » « less