Response to reviewer hF98
We thank the reviewer for their time, and appreciate their constructive efforts in helping us strengthen our work.
We have attempted to address the novelty concerns in the common response above. Below we address the other questions raised by the reviewer:
1,2.: Thank you for pointing out the typos in the tree mechanism section, we appreciate the reviewer’s detailed review. The condition in Algorithm 1 should indeed be $k' \leq t$, and the expression in the fourth line of Proposition 2.5 should be $\sum_{j=1}^i M_j$. We have corrected these errors in the revised version.
The tree mechanism approach ensures that the algorithm maintains strong differential privacy guarantees while minimizing the error introduced by noise. It has become a standard tool in differential privacy and in private optimization, and further details can be found in lecture notes and textbooks. To clarify the tree mechanism, we provide a brief and non-technical explanation:
Suppose we are given a sequence of real numbers $X_1, X_2, \ldots, X_n$, where each $X_i$ lies in $[0, 1]$, and we aim to compute the cumulative sums $\sum_{j=1}^i X_j$ for all $i \in [n]$ while preserving differential privacy.
A naive approach would add independent Gaussian noise to each $X_i$, but this results in an error proportional to $\sqrt{n}$, which grows poorly with $n$. The binary tree mechanism improves on this by organizing the computations into a hierarchical structure:
- Binary Tree Construction: We construct a complete binary tree with $n$ leaves, where each leaf corresponds to one $X_i$. Each internal node of the tree represents the sum of the values of its descendant nodes. For instance: A node spanning the range $(u, v)$ represents $\sum_{j=u}^v X_j$; Its left child spans $(u, m)$, and its right child spans $(m+1, v)$, where $m$ is the midpoint of $[u, v]$.
- Adding Independent Noise: To privatize the sums, independent Gaussian noise is added to the output of every node in the tree. This means that, for any node spanning a range $(u, v)$, the privatized sum is:
$
\text{PrivSum}(u, v) = \sum_{j=u}^v X_j + N_{u,v},
$
where $N_{u,v}$ is Gaussian noise with an appropriate scale determined by the privacy parameters.
- Querying Cumulative Sums: To compute any cumulative sum $\sum_{j=1}^i X_j$, the mechanism selects at most $\log n$ nodes from the tree whose ranges cover $[1, i]$. The noisy outputs from these nodes are combined to produce the privatized result. This hierarchical structure ensures that the total error scales with $O(\log^2 n)$, which is significantly smaller than $\sqrt{n}$ for large $n$.
- Role of $\text{NODE}(t)$: In Algorithm 1, the function $\text{NODE}(t)$ determines the set of nodes needed to cover the range $[1, t]$ in the tree in a greedy way. These nodes are then used to determine which Gaussians should be added to compute the privatized sum.
We hope this explanation clarifies the tree mechanism and its implementation. Please let us know if you have additional questions or feedback.
3. These are precisely the same update rules in disguise, since the authors therein “subtract” the update whereas we “add” it, so they are defined as negations.
In detail, in remark 10 therein, they query the gradient at $z_n:=x_n+(s_n-1)\Delta_n$, and since $s_n\sim[0,1]$, it holds that $(s_n-1)\sim[-1,0]$, or in other words $z_n=x_n-s’_n\Delta_n$ where $s’_n\sim[0,1]$.
4. This is true. We therefore complement our results by a first-order algorithm (in Appendix C) with a substantially reduced oracle complexity which avoids this blow-up - see Remark C.5, and also our top-comment for further discussion.
We kindly ask the reviewer to consider reevaluating the rating in light of these corrections and clarifications, as they address the key concerns they raised.