Rethinking the Solution to Curse of Dimensionality on Randomized Smoothing

We thank the reviewer for the careful reading on the paper. However, according to reviews, our contributions are largely and comprehensively underesitmated.

1. The first title of this paper is actually 'Effects of Exponential Gaussian Distributions on Double Sampling Randomized Smoothing'. The major concern of this paper, as the reviewer mentioned, is on how changing the exponent $\eta$ influences the theoreical and practical results of certifications from (DS)RS. We emphasize that we are not trying to hide this intuition for the work.
2. About our Theorem 1. The Theorem 1 is definitely novel, or at least, absolutely a generalization for the conlusion from Li et al. (2022). This is because $\eta$ does not only appear in the concentration assumption, but also in the smoothing distributions. In other words, definition 2 and theorem 1 are distinctive things, where when $\eta=2$, the definition 2 reduces to the same thing in Li et al. (2022) (their definition 3). But theorem 1 is far from a copy, it is describing the fact that under the same concentration assumption in Li et al. (2022), $\eta \in (0,2)$ provides tigher constant factors than $\eta=2$, which is what we specifically describe in 'Study on the constant factor' in page 6. We maintain that this section should be more carefully read and understood.
3. About Theorem 4. Different with Theorem 1, the existence of theorem 4 is to show that the exponent $\eta$ can be formally introduced into the lower bound, rather than to prove the $\Omega({\sqrt{d}})$ once again. We have also learned the the concentration assumption here is stricter than that in theorem 1 (see Remark in page 24), and its fundamental equivalence to theorem 1 (top of page 6) or its logical naturalness. These are also why we put theorem 4 in the appendix instead of the text. However, we do not believe the equivalence of $\sigma \sqrt{d}$ to $\sigma_s d^{\frac{1}{\eta}}$ is an obvious conclusion to the community without any clarification, or only showing Eqn. (62)-(64).
4. The experimental results. Firstly, we don't understand why our method, that brings holistic improvements on extensive mainstream datasets and training methods to General Gaussian distribution is called 'margined'. Is it because the increment on CIFAR10 is not strong? If so, please also consider the ImageNet results. Overall, the contribution of our work is far beyond breaking the SOTA, because the deep and meticulous study on the smoothing distributions reveal the potenitial restrictions to the current solution the curse of dimensionality and the double-sampling method, and taking other $\eta$ effectively alleviates the limitation of the origin method, both theoretically and pratically.
5. The seemlingly contradictory conclusions for theories and experiments. Actually, we have deeply explored and explained this phenomenon in the text. In short, our theories tell that the smaller $\eta$ the better, while the experiments tell that the larger $\eta$ the better. One key insight of our paper is revealing that these findings are not incompatible, which comes from the concentration assumption. See the 2nd paragraph of analyses in page 9. Briefly, if the concentration assumption strictly holds (p=1), smaller $\eta$ is better, otherwise (p<1) larger $\eta$ is better. Our theory is based on the $p=1$ assumption, but the real classifiers can only satisfy $p<1$, which is the decisive reason of the seemingly opposite conclusions. Figure 10 further shows this extreme sensitivity to $p$ of the concentration assumption, that there is a large gap between effects of even $p=0.99999$ and $p=1$.
6. Ethic concerns. Our theorem 1 is defintely not found by Li et al. (2022), and is in essence considering the generalization from 2 to real numbers for DSRS. As we have mentioned, definition 2 is indeed the concentration assumption in Li et al. (2022), but we have clarified this in the next paragragh of definition 2. In fact, we feel deeply astonished, confused, and discontented on the statement of so-called '(im)proper reference' and ' integrity concern'.

Finally, the generalization from $\eta=2$ to $\eta\in\mathbb{N_+}$ is absolutely not a trivial improvement like deleting $2$ and press an another number on the keyboard to obtain the results. On the contrary, it needs thorough understanding on Li 2022, methods in Yang 2020 to figure out why we can improve the framework from the perspective of exponent of distribution. This perspective, as far as we are concerned, are never systematically investigated by the community. Moreover, contrary to what the reviewer said, there do exist difficulties for our derivation. In addition to the significant bar on mastering the precedent work, some core details for calculating the certified radius are blank on the Internet, especially on EGG and ESG distributions themselves. Furthermore, stepping into unknown fields for human beings, going deep and offering valuable insights inherently contains big challenges.

I thank the authors for their response.

1. I would like to apologize for my earlier misunderstanding. Now I can see the difference between Theorem 1 in this work, and Theorem 2 in Li et al. (2022). However, given that the difference is so subtle, I would like to suggest the authors particularly highlight this difference before or after this result. It was not until the fifth time I read these two statements that I finally found the difference, especially given that they have the exact same bound. Also, I still think that Theorem 2 of Li et al. (2022) has not been properly cited in your Theorem 1. I would suggest you change the name of Theorem 1 to "Generalization of Theorem 2 of Li et al. (2022)".

2. I would like to remove my comments of ethics concerns (openreview does not allow removing ethics comments though). But still, I think that the proof in your Appendix C is way too similar to the proof in Appendix F of Li et al. (2022). I don't know why there is a need to copy so many things from a previous paper. It would be sufficient for the authors to just describe how to extend Li et al.'s result from $\eta = 2$ to other $\eta$, for example using Yang et al.'s results, and I don't see why this has any significant technical difficulty.

3. And still, I cannot see how your results give tighter constant factors. Theorem 1 has the exact same bound as Li et al. (2022). And as for Theorem 4, like I mentioned in my review, it requires a stronger assumption.

4. Regarding the experiments and your fourth point: First, I do not understand why an improvement on CIFAR-10 from 57.4% to 57.6%, and sometimes even worse than DSRS, should be called anything other than "marginal" (by the way, reviewers Ba1f and 2qpb also call it "marginal"). And it is not surprising at all that EGG can be better than DSRS, because EGG with $\eta =2$ is exactly DSRS so you can never be worse than DSRS, and by adding one degree of freedom in hyperparameter tuning EGG can get better results without doubt. My point is that this improvement, from any scientific lens, is not significant.

5. Second, your theorem focused on $\eta \in (0,2)$, but your experiment shows that $\eta = 8.0$ is the best, which is contradictory to your theoretical results. I cannot understand your analysis on this contradiction in page 9, as well as the fifth point in your response. Let me make my question really simple: This paper is proposing "EGG", your theory says that "EGG with $\eta \in (0,2)$ is good", but your experiments say that "EGG with $\eta \in (0,2)$ is actually not good, but EGG with $\eta = 8$ is good". So what is exactly your proposal? EGG with $\eta \in (0,2)$ which is not verifiable in your experiments, or EGG with $\eta = 8$ which is not justified by your theory? Or if you are proposing both, do you have a practical, implementable method of selecting this $\eta$, other than testing over all $\eta$ and hand-picking the best one? If I select $\eta$ with a validation set, could I get the best $\eta$? If this is the case, then you will need to show this with experimental results.

6. Finally, I still recommend adding a detailed and careful comparison between your work and Li et al. (2022) given their great similarity, including a comparison on the theoretical results, their proofs and the experimental setups and results. This would definitely help anyone reading this work who is not extremely familiar with Li et al. (2022).

We thank the reviewer for the time spent on careful reading, deep thinking and writing the response on the paper.

The constant factor.

This is the right understanding. Taking Eqn. (30) as the example, we let

$F(r; \eta)=\mathbb{E}_u\Psi(\frac{T^2-(\sigma_g(2u)^{\frac{1}{\eta}}-r)^2}{4r\sigma_g(2u)^\frac{1}{\eta}})-\frac{1}{2}$.

Then, for a given $r$, if $F(r; \eta) > 0$, $r$ is certified, else $r$ is not certified. For the points:

$\cdot$ We have reorganized page 6 in the latest version: adding details for Eqn. (30) as Eqn. (8), and moving Theorem 1 to the appendix.

$\cdot$ We are sorry for the ambiguous presentation, and have deleted the confusing ‘binary search’ in the text.

$\cdot$ About little $\eta$. We have considered the mechanisms carefully on why small $\eta$ provides better theoretical results, but find this is beyond our intuition at present.

(1) One possible reason is that a concentration assumption becomes more and more strict for EGG when $\eta$ gets smaller. For this, we can consider fixing a $T$ in Figure 5 (left). Then, for EGG with smaller $\eta$, more mass of the distribution $(r<T)$ is contained by $T$ (meaning larger proportion of perturbed examples will be correctly classified on the base classifier). However, intuitively, the certified radius is not uniquely influenced by their PDF, it can also be affected by other geometric properties. We did not mention this in the text, since it is not systematic enough.

(2) By introducing an additional distribution, it is rational that the NP certification can be improved. This is because the NP lemma is always considering the most conservative case and constructing the 'worst smoothed classifier' based on known information (such as probabilities from MC sampling) of the given classifier. DSRS improves NP by bringing in extra information for the given classifier, and is capable of constructing a 'better worst smoothed classifier' to provide certification (as well as certified radius) for examples. The intuition to improve certification with additional information also appears in other papers. For instance, [1] and [2] improve the certifications by introducing gradient information of the base classifier.

Why focus on DSRS.

Yes, from our experiments, increasing $\eta$ in EGG improves the certification for both NP and DSRS. More specifically, our theoretical analysis sets $B=1$ (the concentration assumption is perfectly satisfied), finding smaller $\eta$ in EGG provides tighter lower bounds for DSRS. Besides, our experiments on real datasets and real base classifiers ($B<1$, the concentration assumption is not perfectly satisfied) show larger $\eta$ in EGG gives better certifications for NP and DSRS. In other words, $\eta$ performs great for DSRS both theoretically and practically, but we do not include specialized theories on NP. This is why we take DSRS as the principle line.

The concentration assumption.

$\cdot$ On the verification and practical use of concentration assumption. At the current stage, the perfectly satisfied concentration assumption is an ideal case, that we may only realize it by numerical simulation, such as setting $B=1$ when computing. Therefore, it is beyond our ability to train a classifier that gives absolutely right predictions for a noised real dataset, even if the level of the noise is restricted.

$\cdot$ Why our conclusions make sense.

(1) The large gap between 0.99 and 1 also appears in Li et al. (2022) (their figure 2a). In that figure, DSRS w/N = 1e7 is equal to B=0.9999993, DSRS w/N = 1e6 is equal to B=0.999993 in our paper (their probabilities was simulating the Clopper-Pearson lower bound, while we directly set them). As they showed, the large 'gap' between $B=0.99$ and $B=1.0$ exists, and the $B=1$ can provide very large certified radius, but DSRS w/N = 1e7 can only provide $r<3$.

(2) The essential reason for the gap is our Lemma C.3 or Li et al. (2022)'s Lemma F.2. The key point here is, if the assumption holds at 0.99, then it only takes effect on the specified distribution (say, Gaussian). But if it holds at 1, then it takes effect for every distribution, because the specified distribution has positive density everywhere.

(3) Our conclusions are based on rigor derivation and experiments, which are checked multiple times (codes included). We also want our results to look concise, but we must obey science and practice.

Refs:

[1] Mohapatra J et al. Higher-order certification for randomized smoothing[J]. NeurIPS, 2020, 33: 4501-4511.

[2] Levine A et al. Tight second-order certificates for randomized smoothing[J]. arXiv preprint arXiv:2010.10549, 2020.

We thank the reviewer for replying again. Here we have the following points to clarify:

1.Smoother smoothing distribution $\nRightarrow$ smoother classifier or better certification

The word 'smooth distribution' looks ambiguous. From the context, we speculate it refers to differentiability of the PDF of distributions. If this is the case, then the smoothness of distribution has no direct correlation with the smoothness of the classifier, and also, does not guarantee greater certified accuracy. A simple example: Laplace (ESG, $\eta=1$) is less smooth than Gaussian (ESG, $\eta=2$), but they basically provide similar certifications (Table 3). Likewise, in DSRS, we do not think truncated general Gaussian is smoother than general Gaussian. In other words, the smoothness of a distribution is not a significant factor for choosing the supplementary distribution.

2. The understanding of the mechanism is inaccurate.

(1) EGG with larger will not be more concentrated at $x_0$. Instead, it will be concentrated in a shell, at a distance from $x_0$ (which is the thin-shell phenomenon, Zhang et al. (2020)).

(2) In our work, we emphasize the existence of a gap between $B=0.99$ and $B=1$, and the distinct performance of EGG under very similar settings. The reviewers' intuition on $B=1$, is very close to our tentative explanation, which we believe is insufficient for understanding the behavior of EGG under $B<1$.

3. The concentration assumption. The concentration assumption is actually an extrapolation for an observed phenomenon, rather than fabricated from the thin air. It originated from Li et al. (2022), which is essentially enlightened by the observation of some real robust classifiers. For this, we recommend the reviewer to their Figure 4 and their Appendix J.1. In that figure, each blue curve represents the performance of a test data from ImageNet perturbed by 1000 random Gaussian noise on a pre-trained robust classifier. For example, a point (190, 0.99) on a curve means the robust classifier has a 99% accuracy on 1000 perturbed points, and the $l_2$ length of perturbations can reach up to 190. In addition, there are abrupt downfalls in most blue curves, most of which begin to plunge after the green peak in the figure, which is where the Gaussian noises gather. The observations above are why the concentration assumption was proposed. Moreover, even if the concentration assumption strictly holds, it does not mean the classifier is robust, because this robustness is not only a local property, but also limited to specific inputs.

4. We thank the reviewer for providing a prospective studying project for us, we will consider it in our future research.

Finally, We remark that our contributions are underestimated, and are not fully understood by the reviewer. But we still thank the reviewer for the plenty of time spent on our work.

Note: The Program Chairs have decided to reopen discussion on openreview until Dec 4. The following is my response to the authors' newest comments I wrote earlier.

I thank the authors for their discussion.

1. "Smooth" distribution: By "smooth", I was not talking about the PDF of the distribution. I was just saying that the distribution decays faster since it is more exponentially tailed, so when smoothifying a classifier with this distribution, it puts more weights on its neighborhood than points far away.

2. "Concentration": By "more concentrated at x", I meant that more masses of the distribution will be close to x. The authors are absolutely right that most masses will be distributed close to a shell, which further indicates why Definition 1 is not a reasonable assumption. Like I pointed out earlier, Eqn. (6) holding with probability 1 is equal to $f$ being a.e. constant in a ball, so if this shell lies within this ball, then the smoothified classifier will output the same class with very high probability, so that there is no point in doing certification with Monte-Carlo sampling.

3. Appendix J.1 in Li et al. (2022): I don't think the assumption in Li et al. (2022) is reasonable. Like I said earlier, "Eqn. (6) holding with strict probability 1" cannot be statistically verified with Monte-Carlo sampling. Appendix J.1 in Li et al. (2022) was still conducting Monte-Carlo sampling, so it cannot verify or justify "Eqn. (6) holding with strict probability 1". This assumption is equivalent to $f$ being a.e. constant within a neighboring ball, and with this strong assumption there is no point in doing certification. Like I said in the last message, a more reasonable assumption could be P(Eqn. (6)) > 1 - epsilon for some very small but positive epsilon. For instance, even P(Eqn. (6)) > 0.999999 is statistically verifiable, if given enough samples.

4. Why I am still voting to reject:

   • Soundness: My biggest concern is that the theoretical part of this work suggests using a small $\eta$, but your own experiments show that using a small $\eta$ is actually harmful, and the explanation is not convincing. As I have mentioned several times, I cannot see any plausible reason why a small $\eta$ would help. In my last reply, I pointed out that the illusion that a small $\eta$ could help might be caused by the not very reasonable concentration property, which requires P(Eqn. (6)) to be strictly 1. And indeed, the authors also observed a huge gap between P(Eqn. (6)) = 1 and P(Eqn. (6)) = 0.999999. I pointed out that the main claim that "using a small $\eta$ is beneficial" is unverifiable and unsound because it is based upon a flawed assumption, and thus suggested the authors to change your concentration assumption to P(Eqn. (6)) = 0.999999, from which you might be able to prove that a larger $\eta$ is better.
   • Contributions: The authors argue that the "contributions are underestimated". You are fully entitled to your own view, but from my perspective the analysis in this submission is not deep enough, mostly because your own empirical results contradict with your own theoretical results, and your explanation for this contradiction is not convincing at all. I am also pretty sure that many readers who are familiar with this field will get the same feeling. My take is that for any practical scenario, a small $\eta$ is harmful, while a large $\eta$ might be good, and I articulated my intuition in my last response.
   • Comparing to prior work: Finally, this work is still too similar to Li et al. (2022), and I suggest the authors include a full paragraph of comparison between the two papers. And I think that the notations in Li et al. (2022) are good enough, so I am not sure why there is a need to use a completely new set of notations. There is no need to hide the fact that your work is largely based on a previous work. It is totally fine if your new contributions are sufficient and deep enough.

We thank the reviewer for the time as well as the encouraging feedback. We would like to deal with the questions as follows.

$\cdot$ We have some additional materials for experiments on CIFAR10 in point 2 of the global response, please check it if necessary. In fact, the comparison between DSRS and EGG, $\eta=8.0$ is not totally fair, because DSRS takes $\mathcal{Q}\neq$ TEGG when providing the baseline for CIFAR10. If we pay attention to EGG, $\eta=2.0$, we can see the improvement brought by EGG, $\eta=8.0$ is significant.

$\cdot$ We have corrected these typos accordingly.

We hope our response has resolved your concerns on the paper, and would welcome any further discussion.

We provide thanks to the reviewer for the effort put into the review, and give our feedback as follows.

Weaknesses:

1. One of our initial motivations for the work, quite similar to what the reviewer mentioned, is to improve the order of $d$, and we did have the trial in our work (see the second paragraph on page 6). In our derivation, the exponent $\eta$ can be introduced into the order of $d$ to form $\Omega(d^{\frac{1}{\eta}})$. Despite it being proved an equivalent bound to $\Omega(\sqrt{d})$, our theorem shows EGG with $\eta\in(0,2)$ can improve the constant factors efficiently. We believe our theoretical results, though do not break the $\sqrt{d}$ order, can propel and enlighten future studies in this topic.

In fact, the initial title of this paper is 'Effects of Exponential General Gaussian on Double Sampling Randomized Smoothing'. That is to say, we emphasize a lot on thinking from the perspective of the exponent, and its effect on the (double sampling) randomized smoothing framework. In addition to the investigation on curse of dimensionality, our work also provide substantial insights on RS and DSRS including:

$\cdot$ Our experimental results for EGG show seemingly contrary rules with theoretical analysis. Specifically, our theorems reveal the lower bound improves as the $\eta$ in EGG gets smaller, while our experiments on real-world datasets show larger $\eta$ provides better certifications. However, this seemingly contrary phenomenon does not mean we made mistakes in the work. According to our further study, we find how $\eta$ influences the certifications is largely decided by whether the concentration assumption strictly holds. That is, if the concentration assumption strictly holds (i.e. B=1 in Problem (4), which is the case of our theorem 1 and Figure 1(a)), the lower bound provided by DSRS improves as the $\eta$ decreases. Otherwise, if the concentration assumption does not strictly hold (i.e. B<1 in Problem (4), which is the experimental case because no classifier perfectly satisfies the assumption), the certifications provided by EGG improves as the $\eta$ increases. Our Figure 10 further clarifies this point by simulating the cases where $B$ is very close to 1. It is clear in the figure that if $B=1$, $\eta=1$ performs better, but if $B<1$ (even if extremely close), $\eta=2$ performs better.

$\cdot$ Our results for ESG demonstrates that a mainstream view in the randomized smoothing community can be augmented. Concretely, the mainstream view (for example, Yang et al. (2020)) believes Gaussian distribution is the best distribution to provide certification in the RS framework. However, our finding is that many members of the ESG distribution can provide certification as great as Gaussian (Gaussian is a special case of ESG when $\eta=2.0$). We would like to recommend reading point 1 in the global response for more information on backgrounds and motivations for this paper.

2. It is a bit ambiguous for 'variance', here we talk about both the cases.

$\cdot$ If it refers to the variance of each distribution, such as $0.5, 1.0$. We can ensure that all variances in this work are aligned by keeping $\mathbb{E}r^2$ a constant (the convention from Yang et al. (2020) and Li et al. (2022)). This is also why we have the substitution variance in Table 1.

$\cdot$ If it refers to the variance between repetitive experiments. In our work, we find the errors on certified accuracy caused by randomness of experiments usually range between 0.0%-0.3%. It will definitely be great to show results of multiple experiments, but its impact may be limited for the theme of this paper. Actually, though our results for $\eta=8.0$ result does not significantly improve the DSRS baseline, the comparison is not fair. In Li et al. (2022), they reached the baseline by setting $\mathcal{Q}\neq TEGG$. If we consider a fair comparison, say comparing $\eta=2.0$ with $\eta=8.0$, then our improvement is significant.

3. Please check point 2 in the global response. From our perspective, compared to $\mathcal{P}=EGG, \mathcal{Q}=TEGG, \eta=2.0$, the setting $\mathcal{P}=EGG, \mathcal{Q}=TEGG, \eta=8.0$ provides holistic improvements, no matter which dataset (CIFAR10, ImageNet) and training method (standard, SmoothMix, Consistency) are used. Besides, our results can be further enhanced by letting $\eta$ larger (16, 32). We do not show them in the paper because their errors are more difficult to control than $\eta=8.0$.

Questions:

1, 2. We have improved these representations in the latest paper.

3. Yes, $\eta$ is the same for $\mathcal{P}$ and $\mathcal{Q}$. As for $\eta, k$, they definitely influence the bound (please check Eqn (51). and Table 4). Theorem 1 only shows the same bound provided by General Gaussian (Li et al. (2022)) can also be provided by EGG, and the section 'study on the constant factor' (page 6) further shows the factor grows as $\eta$ shrinks, for $d-2k$ except 1.

We thank the reviewer for the time and the consideration. Here we provide point-to-point explanations for the concerns.

1. Using 'point-to-point certified accuracy', we were trying to describe our experimental results as better than the baselines at almost every certified radius $r$. For this, please check figures for EGG on page 46-49, where the curves of EGG,$\eta=8$ envelop almost all their corresponing EGG,$\eta=2$. To reduce ambiguity, we now use the term certified accuracy following the convention in the RS community.

2,3. We have corrected these typos.

4. Here we wanted to show EGG is a potential choice for providing better certification results, where the word 'prospective' is indeed inaccurate. Currently, this sentence in the text has been rewritten into 'Overall, theoretical analysis above shows taking EGG as the smoothing distribution in DSRS, we are likely to obtain much tighter lower bounds for the certified radius on base classifiers, ...'. We hope the current expression clarifies our intention.
5. About $\eta, d, k$. The EGG distributions, defined as $\mathcal{G}(\sigma, \eta, k)$ in the paper, are all considered in discrete combinations of the parameters.

$\cdot$ The reason why $\eta$ belongs to a finite set is that it appears as an argument in the gamma function (for example, Eqn. (12)). As far as we are concerned, it is currently intractable to analyze the continuous property of $\eta$ considering the gamma function, which is also why Li et al. (2022) only considered discrete cases in their Proposition F.6.

$\cdot$ Yes, we do not need to add the restriction $d-2k\in [1,30]\cap \mathbb{N}$ if we just want to prove Lemma C.3, since $d-2k \geq 1$ can all satisfy Eqn. (24). The setting of 30 is following Li et al. (2022) (see their Proposition F.6), where they restricted $d - \frac{k}{2} \in$ {$0.5, 1.0, \cdots, 15.0$}. As we mentioned, the analysis on continous property of EGG distributions is intractable, so only the discrete combinations of $d, k, \eta$ is considered. Concretely, we show the proof for $(d-2k, \eta) \in$ {$1, 2, \cdots, 30$} $\times$ {$1, \frac{1}{2}, \frac{1}{3}, \cdots, \frac{1}{50}$}. For each combination of $d-2k$ and $\eta$, Theorem 1 proves its ability to give the $0.02\sigma\sqrt{d}$ lower bound. Here we take $d-2k = 2, \eta=\frac{1}{2}$ as an example. Specifically, we need to substitute $\mu=0.02, d-2k=2$ and $\eta=\frac{1}{2}$ into Eqn. (52), and check if the value is greater than 0.5. By checking Table 4, we find the value is 0.782, then the $0.02\sigma\sqrt{d}$ lower bound is proved. To sum it up, Table 4 contains all the discrete combinations of parameters we study (i.e. different EGG distributions), where $d, k, \eta$ appear simultaneously. $d, k, \eta$ also exist in other equations such as Eqn. (51). They do not appear in Theorem 1, because all the limited combinations of $(d-2k, \eta) \in$ {$1, 2, \cdots, 30$} $\times$ {$1, \frac{1}{2}, \frac{1}{3}, \cdots, \frac{1}{50}$} have been proved capable of offering the $\Omega(\sqrt{d})$ lower bound.

6. About Eqn. (4).

$\cdot$ A and B are both probabilities that the base classifier gives the right prediction for $x_0$, under different noise distributions.

$\cdot$ Just as the reviewer understands, there is an ‘outer-maximization’ after we obtain the best function $\tilde{f}_{x_0}$. This ‘outer-maximization’ is quite simple so that we can solve it only by binary searching on $||\delta||_2$.

To further clarify the definitions of $A,B$, we have rewritten the paragraph below Eqn. (4).

7. We have improved the statement of Lemma C.3 accordingly.
8. We agree with the review on 'closed-form', and now use 'integral form' to describe our theorem in the latest paper. To clarify the process of solving the DSRS problem, we have added Appendix F.2 in the latest paper, which is a short introduction considering the complete derivation is somewhat complicated and voluminous. For $\nu_1, nu_2$, we get their values from the DualBinarySearch algorithm from Li et al. (2022).
9. We are sorry for the confusion and puzzle. In fact, we have been trying to clarify the mechanisms in the paper as understandable as possible since we started to write this paper. This paper has been revised for more than 15 times before being submitted to the conference. However, limited to our writing skills, and the innate complexity of this work, sometimes it is still difficult to follow. We welcome further discussions on any confusion on or technical details of the paper, and promise we will carefully handle the questions at our best.