1) La descarga del recurso depende de la página de origen
2) Para poder descargar el recurso, es necesario ser usuario registrado en Universia

Opción 1: Descargar recurso

Detalles del recurso


We prove new upper and lower bounds on the sample complexity of (ε, δ) differentially private algorithms for releasing approximate answers to threshold functions. A threshold function cx over a totally ordered domain X evaluates to cx(y)=1 if y ≤ x, and evaluates to 0 otherwise. We give the first nontrivial lower bound for releasing thresholds with (ε, δ) differential privacy, showing that the task is impossible over an infinite domain X, and moreover requires sample complexity n ≥ Ω(log∗ |X|), which grows with the size of the domain. Inspired by the techniques used to prove this lower bound, we give an algorithm for releasing thresholds with n ≤ 2(1+o(1)) log∗ |X| samples. This improves the previous best upper bound of 8(1+o(1)) log∗ |X| (Beimel et al., RANDOM ’13). Our sample complexity upper and lower bounds also apply to the tasks of learning distributions with respect to Kolmogorov distance and of properly PAC learning thresholds with differential privacy. The lower bound gives the first separation between the sample complexity of properly learning a concept class with (ε, δ) differential privacy and learning without privacy. For properly learning thresholds in dimensions, this lower bound extends to n ≥ Ω( · log∗ |X|). To obtain our results, we give reductions in both directions from releasing and properly learning thresholds and the simpler interior point problem. Given a database D of elements from X, the interior point problem asks for an element between the smallest and largest elements in D. We introduce new recursive constructions for bounding the sample complexity of the interior point problem, as well as further reductions and techniques for proving impossibility results for other basic problems in differential privacy.

Pertenece a

Digital Access to Scholarship at Harvard  


Bun, Mark -  Nissim, Kobbi -  Stemmer, Uri -  Vadhan, Salil P. - 

Id.: 70848336

Idioma: inglés (Estados Unidos)  - 

Versión: 1.0

Estado: Final

Palabras clavedifferential privacy - 

Tipo de recurso: Conference Paper  - 

Tipo de Interactividad: Expositivo

Nivel de Interactividad: muy bajo

Audiencia: Estudiante  -  Profesor  -  Autor  - 

Estructura: Atomic

Coste: no

Copyright: sí

: open

Requerimientos técnicos:  Browser: Any - 

Relación: [References] doi:10.1109/FOCS.2015.45
[References] 2015 IEEE 56th Annual Symposium on Foundations of Computer Science

Fecha de contribución: 11-ene-2018


* Bun, Mark, Kobbi Nissim, Uri Stemmer, Salil Vadhan. 2015. Differentially private release and learning of threshold functions. IEEE 56th Annual Symposium on Foundations of Computer Science: 634-649. doi:10.1109/FOCS.2015.45.
* 978-1-4673-8191-8

Otros recursos del mismo autor(es)

  1. Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing Hypothesis testing is a useful statistical tool in determining whether a given model should be rejec...
  2. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space We give a deterministic O˜(log n)-space algorithm for approximately solving linear systems given by ...
  3. Locally testable codes and cayley graphs We give two new characterizations of ( 2-linear, smooth) locally testable error-correcting codes in ...
  4. Redrawing the boundaries on purchasing data from privacy-sensitive individuals We prove new positive and negative results concerning the existence of truthful and individually rat...
  5. On Learning vs. Refutation Building on the work of Daniely et al. (STOC 2014, COLT 2016), we study the connection between compu...

Otros recursos de la mismacolección

  1. Fatigue fracture of tough hydrogels Tough hydrogels of many chemical compositions have been developed in recent years, but their fatigue...
  2. “La fotografía es la misma muerte”: Ruina, espectro y testimonio de Antonio Machado en Guerra en España de Juan Ramón Jiménez From 1936 to 1954 poet, editor, translator, critic, and Nobel laureate Juan Ramón Jiménez (Spain, 18...
  3. Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing Hypothesis testing is a useful statistical tool in determining whether a given model should be rejec...
  4. The Berenson Collection: A Guide History of Art and Architecture
  5. Leibniz on Monadic Agency and Optimal Form Philosophy

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.