Private Algorithms Can Always Be Extended

We consider the following fundamental question on ε-differential privacy. Consider an arbitrary ε-differentially private algorithm defined on a subset of the input space. Is it possible to extend it to an ε′-differentially private algorithm on the whole input space for some ε′ comparable with ε? In this note we answer affirmatively this question for ε′=2ε. Our result applies to every input metric space and space of possible outputs. This result originally appeared in a recent paper by the authors [BCSZ18]. We present a self-contained version in this note, in the hopes that it will be broadly useful.