Regarding your comments

"The experiments in the introduction....Additional explanation would be helpful."

Thanks for asking this insightful question. Before presenting our explanations, we want to clarify that the “normalized margin”, labeled in the y-axis of Figure 2, measures the distance between decision boundaries. We believe you're essentially asking two related questions:

(1) Why do better feature representations imply a larger margin?

This analysis relates to neural collapse theory. Figure 2 in [WZSW 24] shows that improved feature representations yield smaller feature shift vectors—measuring deviation from ideal neural collapse features—indicating that empirical features align more closely with the equiangular tight frame structure and exhibit larger margins. Accordingly, ViT-pretrained features display smaller shift vectors than those from ResNet-50, reflecting a larger margin.

(2) How does it relate to the increase of margin as outliers got removed?

The intuition is that removing outliers makes classes linearly separable, yielding a positive margin. Continued removal of boundary-near points increases the normalized margin (y-axis, Figure 2) until it stabilizes near the data margin—a trend clearly seen in Figure 3 (top-left). Models with better feature representations show larger margins, explaining the ordering in Figure 2: ViT > ResNet-50 > Raw.

[WZSW 24] Wang, C., Zhu, Y., Su, W. J., & Wang, Y. X. (2024). Neural collapse meets differential privacy: curious behaviors of NoisyGD with near-perfect representation learning. arXiv preprint arXiv:2405.08920.

Line 402, is 5m a typo?

Thank you for bringing up this question. Our intended message is as follows: suppose we have $K$ hyperparameters, each with $m$ possible choices. Using $A_{\text{iter}}$ incurs an overhead that scales as $m^{\mathcal{O}(K)}$, whereas employing the advanced tuning methods leads to an overhead that scales as $\mathcal{O}(Km)$.

Other comments

Thank you for pointing these out. We corrected the hyperlink and resolved the LaTeX \cite issues. Eq. 2 is defined as the geometric margin in Line 148.

Regarding your questions

Question 1

“Why this exhaustive collection is necessary? Could something like … be defined instead?”

Thank you for asking this thoughtful question. These definitions serve as tools for proving and stating the main theorem. For instance, they are directly used in the proofs of the margin preservation lemmas (Appendix B) and Lemma 6.4. (for proving adaptivity using a doubling grid). We found the definition you referenced is actually dependent on Definition 6.1. We assume you are referring to $\arg\min_{|S'|} \{ \gamma(S\/S') \geq \gamma \}$, which is equivalent to $\arg\min_{S \in S_{\text{out}}(\gamma)} |S|$, where $S_{out}(\gamma)$ is defined in Definition 6.1.

“Also, as I understand, the choice for S_{out} … So I think some infimum can be taken right?”

Yes, the infimum is indeed taken over all $S_{out}$ such that $\gamma (S \/ S_{out})>0$, as demonstrated in Theorems 6.5 and 6.7, specifically on the left-hand side of the inequality in each case.

“This is a minor point, but it seems to me that the bound depends..less conclusive”

We appreciate your thoughtful question. Our bound is data-adaptive. We explain our result using Theorem 6.5 as an example.

Since the dataset is finite, there must exist at least one optimal outlier subset $S_{out}^*$ that minimizes the upper bound: $\frac{1}{n\varepsilon\gamma(S_{out}^* )} + \frac{|S_{out}^*|}{n\gamma(S_{out}^*)}$ While the minimizer of the upper bound depends on the optimal subset, this dependency reinforces the fact that the bound is data-adaptive. This stands in contrast to previous results, which are data-independent and yield a fixed rate of $n^{0.5}$, as reported in Table 1.

Since this optimal subset is unknown—and identifying it via brute-force search is NP-hard—our algorithm, which runs in polytime can effectively adapt to it through a hyperparameter search over a logarithmic grid on the margin, as demonstrated in Theorem 6.5 and also pointed out by other reviewer.

Question 2

That's a good question. The order of k is determined by the JL lemma. The k is chosen to ensure every $\gamma$-level margin inlier set has preserved margin after projection with high probability.

Specifically, from the statement of Lemma 6.2, the probability is taken over the randomness of the Johnson–Lindenstrauss matrix $\Phi$. It can be interpreted as the following conditional probability: $P_{\Phi} ( \gamma ( \Phi S_{in} ) \geq \gamma/3 \mid S_{in} ) \geq 1 - \beta$ rather than $P_{\Phi} ( \forall S_{in} \in \mathcal{S_{in}} (\gamma), \gamma ( \Phi S_{in}) \geq \gamma/3 ) \geq 1-\beta$. We note that the second inequality is a stronger condition, which is what you mentioned in the question. However, throughout this paper, the first one is sufficient for our proof.

Thank you for your detailed review and thoughtful question. We appreciate your recognition of our work. We have corrected all the typographical errors you identified.

Regarding your question, you are indeed correct: $\tilde{w_t}$ in Algorithm 5 should indeed be $w_{t+1}$. We thank the reviewer once again for their careful reading and valuable feedback.

Regarding your comment on weaknesses

Weakness 1

We thank the reviewer for their valuable feedback. We agree that our work builds upon the JL transform and gradient descent (GD) techniques, which have been explored in prior works such as Nguyen et al. and Bassily et al. However, our algorithm introduces several key innovations that go beyond a straightforward combination of these tools:

(1) Novel Margin Definition and Analysis: Our analysis is based on a new definition of margin inliers/outliers, which, to the best of our knowledge, has not appeared in prior work. This definition is data-dependent (as discussed in Remark 3.1), in contrast to the confidence margin used in Bassily et al., which is data-independent. This distinction is not only conceptual but also technical: our data-dependent margin enables a new analysis technique that is not limited to the JL + GD setting (please refer to comments from Line 291 to Line 295). Most importantly, it leads to a data-adaptive generalization bound that avoids the hard $1/\sqrt{n}$ rate in the agnostic case that appears in Bassily et al.

(2) Practical and Efficient Private Margin Selection:

While Bassily et al. employs a grid search combined with the exponential mechanism, their approach involves a more complex score function. Additionally, the exponential mechanism appears hard to implement, as evaluating the score function requires solving non-convex optimization problems (Lemma F.3). In comparison, our method is computationally efficient and straightforward to implement.

Weakness 2

Thank you for the insightful question. To address it more generally, we note that the problem of tolerating a constant fraction of outliers—under certain additional assumptions on the noise model—remains open, as discussed in Section 8. We have also included a comparison between our bound and that of Bassily et al. in Lines 165 to 168.

Regarding your question

Thank you for this thoughtful question. First, we clarify that this section extends our main result by analyzing utility in the context of general hyperparameter sets, which may not be small. For completeness, we provide a utility analysis of hyperparameter tuning. Specifically, advanced tuning methods yield a utility bound with a $\log(|\Theta|)$ dependence, whereas naively evaluating all base mechanisms and selecting the best incurs a $|\Theta|$ dependence. However, in the small hyperparameter setting considered in our paper, the utility bound is not dominated by the $\log\log(n)$ as it is obscured by other $\log(n)$ factors (see Section 7.2). In addition, to the best of our knowledge, the explicit form of the utility bound has not been previously derived.

Lê Nguyễn, Huy, Jonathan Ullman, and Lydia Zakynthinou. "Efficient private algorithms for learning large-margin halfspaces." Algorithmic Learning Theory. PMLR, 2020.

Bassily, Raef, Mehryar Mohri, and Ananda Theertha Suresh. "Differentially private learning with margin guarantees." Advances in Neural Information Processing Systems 35 (2022): 32127-32141.