More Like this

1. Efficient, Noise-Tolerant, and Private Learning via Boosting

   Bun, Mark; Carmosino, Marco L.; Sorrell, Jessica (January 2020, Proceedings of Thirty Third Conference on Learning Theory)

   null (Ed.)

   We introduce a simple framework for designing private boosting algorithms. We give natural conditions under which these algorithms are differentially private, efficient, and noise-tolerant PAC learners. To demonstrate our framework, we use it to construct noise-tolerant and private PAC learners for large-margin halfspaces whose sample complexity does not depend on the dimension. We give two sample complexity bounds for our large-margin halfspace learner. One bound is based only on differential privacy, and uses this guarantee as an asset for ensuring generalization. This first bound illustrates a general methodology for obtaining PAC learners from privacy, which may be of independent interest. The second bound uses standard techniques from the theory of large-margin classification (the fat-shattering dimension) to match the best known sample complexity for differentially private learning of large-margin halfspaces, while additionally tolerating random label noise. 

   more » « less
2. Differential Privacy and Sublinear Time Are Incompatible Sometimes

   https://doi.org/10.4230/LIPIcs.ITCS.2025.19  

   Blocki, Jeremiah; Fichtenberger, Hendrik; Grigorescu, Elena; Mukherjee, Tamalika (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differentially private sublinear algorithms for many problems including graph parameter estimation and clustering, little is known regarding hardness results on these algorithms. In this paper, we initiate the study of lower bounds for problems that aim for both differentially-private and sublinear-time algorithms. Our main result is the incompatibility of both the desiderata in the general case. In particular, we prove that a simple problem based on one-way marginals yields both a differentially-private algorithm, as well as a sublinear-time algorithm, but does not admit a "strictly" sublinear-time algorithm that is also differentially private. 

   more » « less
3. 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
4. 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
5. Learning Differentially Private Mechanisms

   Roy, Subhajit; Hsu, Justin; Albarghouthi, Aws (January 2021, Proceedings of the IEEE Symposium on Security and Privacy)

   null (Ed.)

   Differential privacy is a formal, mathematical def- inition of data privacy that has gained traction in academia, industry, and government. The task of correctly constructing differentially private algorithms is non-trivial, and mistakes have been made in foundational algorithms. Currently, there is no automated support for converting an existing, non-private program into a differentially private version. In this paper, we propose a technique for automatically learning an accurate and differentially private version of a given non-private program. We show how to solve this difficult program synthesis problem via a combination of techniques: carefully picking representative example inputs, reducing the problem to continuous optimization, and mapping the results back to symbolic expressions. We demonstrate that our approach is able to learn foundational al- gorithms from the differential privacy literature and significantly outperforms natural program synthesis baselines. 

   more » « less