The Power of Factorization Mechanisms in Local and Central Differential
  Privacy
  We give new characterizations of the sample complexity of answering linear
queries (statistical queries) in the local and central models of differential
privacy:
  *In the non-interactive local model, we give the first approximate
characterization of the sample complexity. Informally our bounds are tight to
within polylogarithmic factors in the number of queries and desired accuracy.
Our characterization extends to agnostic learning in the local model.
  *In the central model, we give a characterization of the sample complexity in
the high-accuracy regime that is analogous to that of Nikolov, Talwar, and
Zhang (STOC 2013), but is both quantitatively tighter and has a dramatically
simpler proof.
  Our lower bounds apply equally to the empirical and population estimation
problems. In both cases, our characterizations show that a particular
factorization mechanism is approximately optimal, and the optimal sample
complexity is bounded from above and below by well studied factorization norms
of a matrix associated with the queries.
