Testing and reconstruction of Lipschitz functions with applications to data privacy

A function f:D → R has Lipschitz constant c if d _R(f(x),f(y) ) ≤ c·d _D(x,y) for all x,y in D, where d _R and d _D denote the distance functions on the range and domain of f, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note that rescaling by a factor of 1/c converts a function with a Lipschitz constant c into a Lipschitz function.) Intuitively, a Lipschitz constant of f is a bound on how sensitive f is to small changes in its input. We initiate the study of testing and local reconstruction of the Lipschitz property of functions. A property tester, given a parameter ε, has to distinguish functions with the property (in this case, Lipschitz) from functions that are ε-far from having the property, that is, differ from every function with the property on at least an ε fraction of the domain. A local filter reconstructs a desired property (in this case, Lipschitz) in the following sense: given an arbitrary function f and a query x, it returns g(x), where the resulting function g satisfies the property, changing f only when necessary. If f has the property, g must be equal to f. We consider functions over domains of the form {1, . . . , n} ^d, equipped with ℓ ₁ distance. We design efficient testers of the Lipschitz property for functions of the form f:{1, 2} ^d → δℤ, where δ ∈ (0, 1] and δℤ is the set of integer multiples of δ, and of the form f:{1, . . . , n} → R, where R is (discretely) metrically convex. We also present an efficient local filter of the Lipschitz property for functions of the form f:{1, . . . , n} ^d → ℝ. We give corresponding lower bounds on the complexity of testing and local reconstruction. The algorithms we design have applications to program analysis and data privacy. The application to privacy is based on the fact that a function f of entries in a database of sensitive information can be released with noise of magnitude proportional to a Lipschitz constant of f, while preserving the privacy of individuals whose data is stored in the database (Dwork, McSherry, Nissim and S mith, TCC 2006). We give a differentially private mechanism, based on local filters, for releasing a function f when a purported Lipschitz constant of f is provided by a distrusted client. We show that when no reliable Lipschitz constant of f is given, previously known differentially private mechanisms have either a substantially higher running time or a higher expected error, for a large class of symmetric functions f.