Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
From MaRDI portal
Publication:2851871
DOI10.1007/978-3-642-40328-6_26zbMATH Open1332.68061arXiv1407.2674OpenAlexW2805580603MaRDI QIDQ2851871FDOQ2851871
Authors: Amos Beimel, Kobbi Nissim, Uri Stemmer 
Publication date: 4 October 2013
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Abstract: We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure -differential privacy [Dwork et al. TCC 2006] and approximate -differential privacy [Dwork et al. Eurocrypt 2006]. We show that the sample complexity of these tasks under approximate differential privacy can be significantly lower than that under pure differential privacy. We define a family of optimization problems, which we call Quasi-Concave Promise Problems, that generalizes some of our considered tasks. We observe that a quasi-concave promise problem can be privately approximated using a solution to a smaller instance of a quasi-concave promise problem. This allows us to construct an efficient recursive algorithm solving such problems privately. Specifically, we construct private learners for point functions, threshold functions, and axis-aligned rectangles in high dimension. Similarly, we construct sanitizers for point functions and threshold functions. We also examine the sample complexity of label-private learners, a relaxation of private learning where the learner is required to only protect the privacy of the labels in the sample. We show that the VC dimension completely characterizes the sample complexity of such learners, that is, the sample complexity of learning with label privacy is equal (up to constants) to learning without privacy.
Full work available at URL: https://arxiv.org/abs/1407.2674
Recommendations
- Private learning and sanitization: pure vs. approximate differential privacy
- Comparing approximate and probabilistic differential privacy parameters
- Differentially Private Distributed Learning
- The Differential Privacy Frontier (Extended Abstract)
- Differential Privacy: A Survey of Results
- scientific article; zbMATH DE number 7650379
- A new analysis of differential privacy’s generalization guarantees (invited paper)
- Learning with differential privacy: stability, learnability and the sufficiency and necessity of ERM principle
- Sample-efficient proper PAC learning with approximate differential privacy
Learning and adaptive systems in artificial intelligence (68T05) Analysis of algorithms and problem complexity (68Q25) Authentication, digital signatures and secret sharing (94A62)
Cited In (99)
- Online local learning via semidefinite programming
- Title not available (Why is that?)
- Differentially private range query on shortest paths
- Testing surface area with arbitrary accuracy
- Differentially private learning of geometric concepts
- Differentially-private learning of low dimensional manifolds
- Optimal differentially private learning of thresholds and quasi-concave optimization
- Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing
- The average sensitivity of an intersection of half spaces
- Adversarially robust streaming algorithms via differential privacy
- Sample complexity bounds on differentially private learning via communication complexity
- On the existence of extractable one-way functions
- Title not available (Why is that?)
- Distributed approximation algorithms for weighted shortest paths
- Formulas vs. circuits for small distance connectivity
- Embedding and canonizing graphs of bounded genus in logspace
- Homological product codes
- The sample complexity of revenue maximization
- Smoothed analysis of tensor decompositions
- Query complexity of approximate nash equilibria
- Efficient density estimation via piecewise polynomial approximation
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Polynomial bounds for the grid-minor theorem
- Fingerprinting codes and the price of approximate differential privacy
- Simultaneous private learning of multiple concepts
- Strong hardness of privacy from weak traitor tracing
- Approximate distance oracles with constant query time
- Breaking the quadratic barrier for 3-LCC's over the reals
- Communication lower bounds via critical block sensitivity
- SENSITIVITY-INDEPENDENT DIFFERENTIAL PRIVACY VIA PRIOR KNOWLEDGE REFINEMENT
- Primal beats dual on online packing LPs in the random-order model
- Order-revealing encryption and the hardness of private learning
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- A characterization of strong approximation resistance
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
- Entropy, optimization and counting
- A characterization of locally testable affine-invariant properties via decomposition theorems
- A super-polynomial lower bound for regular arithmetic formulas
- How to delegate computations
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Economic efficiency requires interaction
- Comparing approximate and probabilistic differential privacy parameters
- Fingerprinting codes and the price of approximate differential privacy
- Turnstile streaming algorithms might as well be linear sketches
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Differentially private naive Bayes learning over multiple data sources
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Optimal error rates for interactive coding. I: Adaptivity and other settings
- Breaking the Minsky-Papert barrier for constant-depth circuits
- A strongly polynomial algorithm for generalized flow maximization
- Analytical approach to parallel repetition
- Coin flipping of any constant bias implies one-way functions
- Constant rank bimatrix games are PPAD-hard
- \(L_p\)-testing
- Satisfiability threshold for random regular NAE-SAT
- Distributed computability in Byzantine asynchronous systems
- Faster all-pairs shortest paths via circuit complexity
- How to use indistinguishability obfuscation
- Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
- Concentrated differential privacy: simplifications, extensions, and lower bounds
- The asymptotic \(k\)-SAT threshold
- The complexity of differential privacy
- On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
- Constant factor approximation for balanced cut in the PIE model
- On derandomizing algorithms that err extremely rarely
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
- Every list-decodable code for high noise has abundant near-optimal rate puncturings
- Private matchings and allocations
- Infinite randomness expansion with a constant number of devices
- Minimum bisection is fixed parameter tractable
- Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
- Community detection thresholds and the weak Ramanujan property
- Differentially Private Distributed Learning
- Zig-zag sort
- Private learning and sanitization: pure vs. approximate differential privacy
- Linear time construction of compressed text indices in compact space
- Shortest paths on polyhedral surfaces and terrains
- The limits of depth reduction for arithmetic formulas
- From average case complexity to improper learning complexity
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- An efficient parallel solver for SDD linear systems
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- Approximation algorithms for bipartite matching with metric and geometric costs
- Circuits resilient to additive attacks with applications to secure computation
- Rounding sum-of-squares relaxations
- Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints
- Computing with a full memory: catalytic space
- Non-malleable codes from additive combinatorics (extended abstract)
- A quantum algorithm for computing the unit group of an arbitrary degree number field
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Parallel algorithms for geometric graph problems
- Bandits with switching costs, \(T^{2/3}\) regret
- Fourier PCA and robust tensor decomposition
- Optimal competitive auctions
- Black-box non-black-box zero knowledge
This page was built for publication: Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851871)
