Theorem. Let S⊆RdS \subseteq \mathbb{R}^d be a symmetric convex body, and let x⃗∈S\vec{x} \in S and y⃗=x⃗+a⃗\vec y = \vec x + \vec a for some a⃗∈Rd\vec a \in \mathbb{R}^d. Set z⃗=arg⁡min⁡v⃗∈S∥v⃗−y⃗∥2\vec z = \arg \min_{\vec v \in S} \Vert \vec v - \vec y \Vert_2. Let c⃗=z⃗−x⃗\vec c = \vec z - \vec x. Then we must have

∥c⃗∥22≤4min⁡{∥a⃗∥22,∥a⃗∥S∗}, \Vert \vec c \Vert_2^2 \le 4 \min \Big\{ \Vert \vec a \Vert_2^2, \Vert \vec a \Vert_{S^*} \Big\},

where ∥z⃗∥S∗≐sup⁡v⃗∈S∣<v⃗,a⃗>∣\Vert \vec z \Vert_{S^*} \doteq \sup_{ \vec v \in S} | \left< \vec v, \vec a \right>|.

Proof. Let b⃗=z⃗−y⃗\vec b = \vec z - \vec y. Then

c⃗=a⃗+b⃗. \vec c = \vec a + \vec b.

  1. By the definition of z⃗\vec z, it holds that

    ∥b⃗∥2≤∥a⃗∥2. \Vert \vec b \Vert_2 \le \Vert \vec a \Vert_2.

    Hence, by triangle inequality,

    ∥c⃗∥2≤∥b⃗∥2+∥a⃗∥2≤2∥a⃗∥2. \Vert \vec c \Vert_2 \le \Vert \vec b \Vert_2 + \Vert \vec a \Vert_2 \le 2 \Vert \vec a \Vert_2.

  2. In the plot, we notices that <c⃗,b⃗>≤0≤<c⃗,a⃗>\left< \vec c, \vec b \right> \le 0 \le \left< \vec c, \vec a \right>. Formally,

    <c⃗,b⃗>=<b⃗,b⃗>+<a⃗,b⃗>=<a⃗,b⃗>+∥b⃗∥22≤<a⃗,b⃗>+∥a⃗∥22=<c⃗,a⃗> \begin{aligned} \left< \vec c, \vec b \right> &= \left< \vec b, \vec b \right> + \left< \vec a, \vec b \right> \\ &= \left< \vec a, \vec b \right> + \Vert \vec b \Vert_2^2 \\ &\le \left< \vec a, \vec b \right> + \Vert \vec a \Vert_2^2 \\ &= \left< \vec c, \vec a \right> \end{aligned}

    Hence,

    ∥c⃗∥22=<c⃗,c⃗>=<c⃗,a⃗>+<c⃗,b⃗>≤<c⃗,a⃗>+<c⃗,a⃗>=2<c⃗,a⃗>≤2∥c⃗∥S∥a⃗∥S∗ \begin{aligned} \Vert \vec c \Vert_2^2 &= \left< \vec c, \vec c \right> \\ &= \left< \vec c, \vec a \right> + \left< \vec c, \vec b \right> \\ &\le \left< \vec c, \vec a \right> + \left< \vec c, \vec a \right>\\ &= 2 \left< \vec c, \vec a \right>\\ &\le 2 \Vert \vec c \Vert_{S} \Vert \vec a \Vert_{S^*} \end{aligned}

    where ∥c⃗∥S≐inf⁡{r∈R≥0:c⃗∈rS}\Vert \vec c \Vert_S \doteq \inf \{ r \in \mathbb{R}_{\ge 0} : \vec c \in r S \} and the last inequality follows from Holder Inequality. As

    ∥c⃗∥S=∥z⃗−x⃗∥S≤∥z⃗∥S+∥x⃗∥S≤2, \Vert \vec c \Vert_{S} = \Vert \vec z - \vec x \Vert_{S} \le \Vert \vec z \Vert_{S} + \Vert \vec x \Vert_{S} \le 2,

    we get ∥c⃗∥S≤4∥a⃗∥S∗\Vert \vec c \Vert_{S} \le 4 \Vert \vec a \Vert_{S^*}.

Reference

[1] Nikolov, Aleksandar, Kunal Talwar, and Li Zhang. "The geometry of differential privacy: the sparse and approximate cases." In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 351-360. 2013.