Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
From MaRDI portal
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.
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
Cited in
(only showing first 100 items - show all)- On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
- Differentially private naive Bayes learning over multiple data sources
- Order-revealing encryption and the hardness of private learning
- SENSITIVITY-INDEPENDENT DIFFERENTIAL PRIVACY VIA PRIOR KNOWLEDGE REFINEMENT
- Concentrated differential privacy: simplifications, extensions, and lower bounds
- Strong hardness of privacy from weak traitor tracing
- Differentially Private Distributed Learning
- Sample complexity bounds on differentially private learning via communication complexity
- Fingerprinting codes and the price of approximate differential privacy
- scientific article; zbMATH DE number 6860834 (Why is no real title available?)
- The complexity of differential privacy
- Differentially private learning of geometric concepts
- Simultaneous private learning of multiple concepts
- scientific article; zbMATH DE number 7164746 (Why is no real title available?)
- Fingerprinting codes and the price of approximate differential privacy
- Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
- Private matchings and allocations
- Rounding sum-of-squares relaxations
- Constant factor approximation for balanced cut in the PIE model
- Entropy, optimization and counting
- Polynomial bounds for the grid-minor theorem
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
- On derandomizing algorithms that err extremely rarely
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Lower bounds for depth 4 formulas computing iterated matrix multiplication
- The limits of depth reduction for arithmetic formulas
- A super-polynomial lower bound for regular arithmetic formulas
- A characterization of locally testable affine-invariant properties via decomposition theorems
- L_p-testing
- Turnstile streaming algorithms might as well be linear sketches
- Linear time construction of compressed text indices in compact space
- Formulas vs. circuits for small distance connectivity
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
- Breaking the Minsky-Papert barrier for constant-depth circuits
- Economic efficiency requires interaction
- The sample complexity of revenue maximization
- Optimal competitive auctions
- Homological product codes
- A quantum algorithm for computing the unit group of an arbitrary degree number field
- Primal beats dual on online packing LPs in the random-order model
- Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints
- Minimum bisection is fixed parameter tractable
- An efficient parallel solver for SDD linear systems
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- Shortest paths on polyhedral surfaces and terrains
- Embedding and canonizing graphs of bounded genus in logspace
- Testing surface area with arbitrary accuracy
- Coin flipping of any constant bias implies one-way functions
- Infinite randomness expansion with a constant number of devices
- The average sensitivity of an intersection of half spaces
- From average case complexity to improper learning complexity
- Bandits with switching costs, \(T^{2/3}\) regret
- Online local learning via semidefinite programming
- How to use indistinguishability obfuscation
- How to delegate computations
- Circuits resilient to additive attacks with applications to secure computation
- On the existence of extractable one-way functions
- Black-box non-black-box zero knowledge
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
- Query complexity of approximate nash equilibria
- Constant rank bimatrix games are PPAD-hard
- Approximation algorithms for bipartite matching with metric and geometric costs
- Distributed approximation algorithms for weighted shortest paths
- Parallel algorithms for geometric graph problems
- Fourier PCA and robust tensor decomposition
- Smoothed analysis of tensor decompositions
- Efficient density estimation via piecewise polynomial approximation
- Analytical approach to parallel repetition
- A characterization of strong approximation resistance
- A strongly polynomial algorithm for generalized flow maximization
- Approximate distance oracles with constant query time
- Faster all-pairs shortest paths via circuit complexity
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Zig-zag sort
- Community detection thresholds and the weak Ramanujan property
- Distributed computability in Byzantine asynchronous systems
- Multiway cut, pairwise realizable distributions, and descending thresholds
- Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements
- Every list-decodable code for high noise has abundant near-optimal rate puncturings
- Non-malleable codes from additive combinatorics (extended abstract)
- Breaking the quadratic barrier for 3-LCC's over the reals
- Optimal error rates for interactive coding. I: Adaptivity and other settings
- The asymptotic \(k\)-SAT threshold
- Satisfiability threshold for random regular NAE-SAT
- Efficient deterministic approximate counting for low-degree polynomial threshold functions
- Communication lower bounds via critical block sensitivity
- Computing with a full memory: catalytic space
- Hitting sets for multilinear read-once algebraic branching programs, in any order
- Private learning and sanitization: pure vs. approximate differential privacy
- Differentially-private learning of low dimensional manifolds
- Comparing approximate and probabilistic differential privacy parameters
- Differentially private range query on shortest paths
- Optimal differentially private learning of thresholds and quasi-concave optimization
- Adversarially robust streaming algorithms via differential privacy
- Differentially private medians and interior points for non-pathological data
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)
