Certifiably Byzantine-Robust Federated Conformal Prediction

To continue the answer of Q1

From the evaluation perspective, we added more clarifications and illustrations on how we construct non-IID data of different levels and also added more evaluations on various approaches to non-IID data construction. We first added clarifications that we followed the standard evaluation setup of non-IID federated learning by sampling different label ratios for different clients from the Dirichlet distribution as the literature [4,5,6,7]. Concretely, we sample $p_{c,j} \sim \text{Dir}(\beta)$ and allocate a $p_{c,j}$ proportion of the instances with class $c$ to the client $j$. Here $\text{Dir}(·)$ denotes the Dirichlet distribution and $\beta$ is a concentration parameter ($\beta$ > 0). Dirichlet distribution is commonly used as the prior distribution in Bayesian statistics and is an appropriate choice to simulate real-world data distribution. An advantage of this approach is that we can flexibly change the imbalance level by varying the concentration parameter $\beta$. If $\beta$ is set to a smaller value, then the partition is more unbalanced. We fixed the imbalance level $\beta$ as $0.5$ in the evaluations before the rebuttal period. Following the suggestion, we added evaluations with different imbalance levels $\beta$ to show the effectiveness of Rob-FCP under different non-IID settings. The results in the following Table 1 demonstrate that under multiple degrees of data imbalance in non-IID federated conformal prediction, Rob-FCP consistently outperforms FCP in achieving a nominal marginal coverage level in the existence of Byzantine clients. We also consider alternative approaches to construct non-IID data with demographic differences in federated learning. Concretely, we split the SHHS dataset by sorting five different attributes: wake time, N1, N2, N3, REM. For example, we first sort the instances according to the wake time of patients and then assign them to 100 clients in sequence. Therefore, some clients are assigned patients with an early wake time, and some are assigned instances with late wake time. The results in Table 2 show that in this type of non-IID partition, Rob-FCP still demonstrates robustness and effectiveness compared to FCP.

Table 1. Marginal coverage / average set size with different non-IID imbalance level $\beta$, the parameter of Dirichlet distribution where the label ratios of clients are sampled from. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

Table 2. Marginal coverage / average set size on SHHS with non-IID data partition based on different attributes: wake time, N1, N2, N3, REM. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

[1] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." ICLR 2020.

[2] Park, Jungwuk, et al. "Sageflow: Robust federated learning against both stragglers and adversaries." NeurIPS 2021.

[3] Data, Deepesh, et al. "Byzantine-resilient high-dimensional SGD with local iterations on heterogeneous data." ICML 2021.

[4] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." International conference on machine learning. ICML 2019.

[5] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." NeurIPS 2020.

[6] Wang, Hongyi, et al. "Federated learning with matched averaging." ICLR 2020.

[7] Gao, Liang, et al. "Feddc: Federated learning with non-iid data via local drift decoupling and correction." CVPR 2022.

Q3: Could the authors also provide some numerical results to illustrate the sensitivity if the number of truthful agents is not correctly identified?

We thank you for the valuable suggestion. In the following Table 3, we provided evaluations of Rob-FCP with incorrect numbers of malicious clients. The results show that either underestimated numbers or overestimated numbers would harm the performance to different extents. Specifically, an underestimate of the number of malicious clients will definitely lead to the inclusion of malicious clients in the identified set $\mathcal{B}$ and downgrade the quality of conformal prediction. On the other hand, an overestimated number will lead to the exclusion of some benign clients. The neglect of non-conformity scores of those clients will lead to a distribution shift from the true data distribution in the calibration process, breaking the data exchangeability assumption of conformal prediction, and a downgraded performance. Therefore, correctly estimating the number of malicious clients is of significance, and this is why we propose the malicious client number estimator, which is sound both theoretically and empirically to achieve the goal.

Table 3. Marginal coverage / average set size under different Coverage attack with underestimated and overestimated numbers of malicious clients on TinyImageNet. The true ratio of malicious clients is $40\%~(K_m/K=25\%)$, while we evaluate Rob-FCP with different ratios of malicious clients $K’_m/K$ ranging from $5\%$ to $45\%$. The desired marginal coverage is $0.9$.

Q4: If the distributions of underlying agents are no-i.i.d., it is very likely that assumption 3.1 will be violated, even if the agents report the true non-conformity score. It seems the current algorithm may not handle this point very well.

We thank you for the interesting question. We can actually think about the effectiveness of Rob-FCP in the non-IID setting from two perspectives. (1) If the malicious clients attempt to disturb the quantile value of conformity scores to a large extent, they need to report a score vector far away from the cluster of score vectors of benign clients. Although the benign score vectors have some heterogeneity, the malicious score vector in this case is still distinguishable in the vector space and effectively excluded during the calibration. (2) If the malicious clients report score vectors close to the cluster of benign score vectors, then even if the Rob-FCP algorithm does not identify malicious clients exactly, the malicious score vectors can also characterize the structure of the benign score cluster, and thus, the computed quantile value would not deviate much. The two situations are exactly the important intuitions in the proof of Theorem 1 and Corollary 1, which rigorously formulates the coverage guarantee of Rob-FCP as a function of the non-IID degree $\sigma$.

Q1: It seems the results are derived based on either knowing the number of truthful agents or being able to consistently estimate this quantity. Could the authors establish some theoretical guarantees where the number of truthful agents is not correctly estimated? What will happen if they are underestimated or overestimated?

We thank you for the valuable comment. If the number of benign clients is overestimated, then there must be a portion of malicious clients in the output set of RobFCP $\mathcal{B}$. Those malicious clients will participate in the conformal calibration and distort the computed quantile value. In Theorem 6 in Appendix F, we added the analysis of this scenario. The theoretical results show that (1) compared to the bound with the correct number $K\_b$, the overestimate $K’\_b$ asymptotically looses the bound by a factor $1-K\_b/K’\_b$, and (2) a larger overestimate $K’\_b$ leads to worse coverage guarantees. If the number of benign clients is underestimated, we can always find a benign client not in the set $\mathcal{B}$, which makes the original proof smooth. Therefore, Theorem 1 and Corollary 1 still hold by plugging a smaller $K’\_b$ into the bound, but the coverage guarantee also becomes worse due the monotonicity regarding the number of benign clients $K\_b$.

Q2: The assumption on bounded distribution disparity could be relatively strong. There would be cases where the underlying distributions of different group of agents are not the same. In that case, this assumption can be easily violated.

We thank you for your valuable comments and suggestions. We added clarifications and improvements of Rob-FCP for the non-IID setting from both the theoretical perspective and the evaluation perspective.

From the perspective of theoretical analysis, we provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 based on the assumption of bounded disparity among benign clients in Assumption 3.1. We added clarifications that the assumption is quite standard, typical, and not simplified across the literature of non-IID federated learning analysis [1] and Byzantine analysis [2,3]. Concretely, Li et al. [1] quantify the non-iid degree (i.e., disparity) of local loss of clients with $\Gamma$ in Section 3.1 of [1] and accordingly provide the convergence guarantee of federated optimization in Theorem 1 of [1], which is a function of the disparity $\Gamma$. Park et al. [2] assume a bounded difference $\rho_1$ between the local loss of benign clients and global loss in Assumption 2 of [2] and provide the convergence analysis in federated Byzantine optimization in Theorem 1 of [2] as a function of $\rho_1$. Data et al. [3] have an assumption of bounded gradient dissimilarity $\kappa$ in Assumption 2 of [3] and prove a convergence guarantee in Theorem 1 of [3] regarding $\kappa$. Similarly, in our paper, we assume a bounded disparity of score statistics quantified with $\sigma$ in Assumption 3.1 and accordingly provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 as a function of $\sigma$. As we can see, the type of assumption is quite standard in the analysis setup of the line of non-IID analysis and Byzantine analysis. The assumption is also essential since without a quantity to restrict the disparity in local behavior, the local behavior can vary arbitrarily, and we can not control global performance quantitatively. From the results in Corollary 1, we can also see that as long as the disparity bound $\sigma$ is finite, the coverage bound in the non-IID setting is asymptotically valid and tight with sufficiently large benign sample sizes $n_b$. We added these clarifications and details in Section 3.3 in the revised manuscript.

Q6: In Theorem 1 and Corollary 1, $\epsilon$ appears in the bound. Is it possible to control it?

We follow FCP to introduce the notation $\epsilon$ to quantify the approximation error of the estimated quantile $\hat{q}\_\alpha$ by data sketching such that the rank of $\hat{q}\_\alpha$ is between $(1-\alpha-\epsilon)(N+K)$ and $(1-\alpha+\epsilon)(N+K)$. The approximation error $\epsilon$ affects the coverage bound of FCP as Equation (3) and accordingly affects the coverage bound in the Byzantine setting as Theorem 1. Since $\epsilon$ is a quantity dependent on the score distribution, we cannot explicitly formulate it without further assumptions. However, we can control the approximation error $\epsilon$ with the dimension of the characterization vector $H$. A large $H$ indicates a large number of subintervals for the histogram statistics and a fine-grained partition, which will lead to a more precise approximation and a low $\epsilon$. Therefore, we can empirically adjust $H$ to control the approximation error $\epsilon$. We included the discussions in the remarks of Theorem 1 in the revised manuscript.

[1] Lu, Charles, et al. "Federated conformal predictors for distributed uncertainty quantification." ICML 2023.

Q7: In the experiment how much time does it take to compute the quantile? (and for which $\epsilon$?)

We follow the suggestion to add the runtime of quantile computation in Rob-FCP in the following Table 1, which indicates the efficiency of federated conformal prediction with our method.

Table 1. Runtime of RobFCP quantile computation with $40\%$ malicious clients.

Q8: Is it possible/easy to extend Rob-FCP in order to have differential privacy guarantees?

We thank you for the valuable question. To provide differential privacy guarantees of Rob-FCP, one practical approach is to add privacy-preserving noises to the characterization vectors before uploading them to the server. Essentially, we can view the characterization vector as the gradient in the setting of FL with differential privacy (DP) and add Gaussian noises to the characterization vector with differential privacy guarantees as a function of the scale of noises, which can be achieved by drawing analogy from the FL with DP setting [1,2,3]. Therefore, practically implementing the differential-private version of Rob-FCP is possible and straightforward.

[1] Zheng, Qinqing, et al. "Federated f-differential privacy." AISTATS 2021.

[2] Andrew, Galen, et al. "Differentially private learning with adaptive clipping." NeurIPS 2021.

[3] Zhang, Xinwei, et al. "Understanding clipping for federated learning: Convergence and client-level differential privacy." ICML 2022.

Q1: More clarifications of sending all the characterization vectors $v^{(k)}$ to the server in the federated setting. Is it possible to compute the vector distance with a federated algorithm?

We added clarifications that the characterization vector $v^{(k)}$ is proposed exactly for the federated setting to reduce the privacy leakage of local scores and reduce communication costs. Concretely, in the federated conformal prediction context, each client $k$ computes the conformity scores of its $n_k$ local data samples $\\{s_j^{(k)}\\}$. However, sending all the conformity scores $\\{s_j^{(k)}\\}$ to the server is expensive and leaks much information about local data samples. Therefore, we characterize the scores $\\{s_j^{(k)}\\}$ with a histogram statistics vector $v^{(k)}$, which computes score frequency in $H$ equally partitioned subintervals. The characterization vector $v^{(k)}$ has a much smaller dimension than the universal scores $\\{s_j^{(k)}\\}$ ($H \ll n\_k$) and thus leaks much less private information during the communication between the server and clients. Thus, the characterization vector distance computation on the server side also obeys the principle of federated learning for privacy-preserving and communication efficiency. The characterization vector is an approximation of the universal scores and can induce an approximation error of federated calibration quantified by $\epsilon$ in Section 2.2. We also consider the influence of $\epsilon$ on the coverage guarantee in the Byzantine setting in Theorem 1 and Corollary 1, indicating a tradeoff between the tightness of conformal guarantee bound and the private information leakage/communication costs in federated settings.

Q2: More discussions of the factor of the minimal sample size of benign clients $1/\min n_i$.

We thank you for the valuable comment. The appearance of $1/\min n_i$ is indeed due to the artifact of the proof. In the derivation from Equation (36) to Equation (37) in the proof of Theorem 1, we lower bound the total sample sizes in $\mathcal{B}$ (benign client set identified by Rob-FCP) with the minimal benign sample size $\min_{k’ \in [K_b]} n_{k’}$. We can definitely replace $\min_{k’ \in [K_b]} n_{k’}$ with the total sample sizes of $K_b-K_m$ benign clients with the smallest sample sizes, which leads to a tighter bound in many scenarios. This will introduce more complex notations, but it is only meaningful for some extreme cases. In practice, if a benign client has an extremely small sample size, then the characterization vector is almost useless for malicious client identification, and the influence on the conformal calibrated quantile is also negligible as FCP performs a weighted calibration based on sample sizes of clients. Therefore, for the extreme case of some benign clients with extremely small sample sizes (e.g., less than 10), it is more meaningful to discard their scores and apply Rob-FCP to the remaining clients, which is more beneficial to malicious client detection and only leads to negligible error for conformal calibration. We added the discussions to the remark of Theorem 1, which is similarly applied to Corollary 1.

Q3: Citations are not always appropriate.

We follow the suggestions to fix citations of split conformal prediction in Section 2.1, citations of FCP in Sections 1,6, and citations of federated learning in Section 1.

Q4: More details of experiment settings.

We included more details of used parameters in the main text for a better understanding in Section 5.1. We evaluate on three types of malicious data of Byzantine clients (i.e., Byzantine attacks): (1) coverage attack (CovAttack) with which malicious clients report the upper bound th conformity scores (e.g., $1$ for the mostly used LAC score) to induce a larger conformity score at the desired quantile and a lower coverage accordingly, (2) efficiency attack (EffAttack) with which malicious clients report the lower bound of the conformity scores (e.g., $0$ for the mostly used LAC score) to induce a lower conformity score at the quantile and a larger prediction set, and (3) Gaussian Attack (GauAttack) with which malicious clients inject random Gaussian noises with standard deviation $0.5$ to the scores to perturb the conformal calibration.

We also included more details about the non-IID setting construction in the main text. we sample $p_{c,j} \sim \text{Dir}(\beta)$ and allocate a $p_{c,j}$ proportion of the instances of class $c$ to the client $j$. Here $\text{Dir}(·)$ denotes the Dirichlet distribution and $\beta$ is a concentration parameter ($\beta$ > 0). We select $\beta=0.5$ in evaluations without specification.

Q5: Notation errors.

We thank you for pointing out the notation issues. We fixed the notation error of marginal coverage, $\mathcal{Q}_\lambda$, and $N_m$ in the revised manuscript.

Q3: Improvement of the concentration bound of the empirical CDF and true CDF.

We thank you for the valuable suggestion! We added the underlying assumption of the binomial proportion confidence interval [1] in Theorem 1 and the proof. We also leveraged the more advanced DKW inequality [2] to bound the error between the empirical CDF and population CDF, and provided the results in Theorem 5 and Corollary 3 in Appendix E. With the DKW inequality, we can basically improve the concentration factor from $\dfrac{H\Phi^{-1}({1-\beta/2HK\_b})}{2 \sqrt{n\_b}}$ to $H\sqrt{\dfrac{\ln(2K\_b/\beta)}{2n\_b}} \left( 1+\dfrac{N\_m}{n\_b}\dfrac{2}{1-\tau} \right)$, which removes the necessity of applying union bound over $H$ subintervals. We referred to the results with DKW inequality in the remarks of Theorem 1 and Corollary 1 in the main text.

[1] Wallis, Sean. "Binomial confidence intervals and contingency tests: mathematical fundamentals and the evaluation of alternative methods." Journal of Quantitative Linguistics 20.3 (2013): 178-208.

[2] Dvoretzky, Aryeh, Jack Kiefer, and Jacob Wolfowitz. "Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator." The Annals of Mathematical Statistics (1956): 642-669.

Q4: How is the final $(1-\alpha)$ quantile computed? Is it simply combining all the clients non-conformal scores altogether and then calculating the (1-alpha)-quantile?

We added clarifications that we did not combine all the non-conformal scores of clients $\\{s_j^{(k)}\\}~(k \in {1,2,..,K})$ because sending all the conformity scores to the server is expensive and leak much information about local data samples in the federated setting. Therefore, we characterize the scores $\\{s_j^{(k)}\\}$ with a histogram statistics vector $v^{(k)}$, which computes score frequency in $H$ equally partitioned subintervals. The characterization vector $v^{(k)}$ has a much smaller dimension than the universal scores $\\{s_j^{(k)}\\}$ ($H \ll n_k$) and thus leaks much less private information during the communication between the server and clients. The characterization vector is an approximation of the universal scores and can induce an approximation error of federated calibration, quantified by $\epsilon$ in Section 2.2. We also consider the influence of $\epsilon$ on the coverage guarantee in the Byzantine setting in Theorem 1 and Corollary 1, indicating a tradeoff between the tightness of conformal guarantee bound and the private information leakage/communication costs in federated settings.

Q5: How can one tell if this distributional difference of some clients is due to their malicious behavior or truly inherent distributional difference?

We thank you for the interesting question. We can actually think about the effectiveness of Rob-FCP in the non-IID setting from two perspectives. (1) If the malicious clients attempt to disturb the quantile value of conformity scores to a large extent, they need to report a score vector far away from the cluster of score vectors of benign clients. Although the benign score vectors have some heterogeneity, the malicious score vector in this case is still distinguishable in the vector space and effectively excluded during the calibration. (2) If the malicious clients report score vectors close to the cluster of benign score vectors, then even if the Rob-FCP algorithm does not identify malicious clients exactly, the malicious score vectors can still characterize the structure of the benign score cluster, and thus, the computed quantile value would not deviate much. The two situations are exactly the important intuitions in the proof of Theorem 1 and Corollary 1, which rigorously formulates the coverage guarantee of Rob-FCP as a function of the non-IID degree $\sigma$.

Q1 (to continue): More clarification of the consideration of heterogeneity in analysis and evaluations.

Table 1. Marginal coverage / average set size with different non-IID imbalance level $\beta$, the parameter of Dirichlet distribution where the label ratios of clients are sampled from. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

Table 2. Marginal coverage / average set size on SHHS with non-IID data partition based on different attributes: wake time, N1, N2, N3, REM. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

[1] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." ICLR 2020.

[2] Park, Jungwuk, et al. "Sageflow: Robust federated learning against both stragglers and adversaries." NeurIPS 2021.

[3] Data, Deepesh, et al. "Byzantine-resilient high-dimensional SGD with local iterations on heterogeneous data." ICML 2021.

[4] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." International conference on machine learning. ICML 2019.

[5] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." NeurIPS 2020.

[6] Wang, Hongyi, et al. "Federated learning with matched averaging." ICLR 2020.

[7] Gao, Liang, et al. "Feddc: Federated learning with non-iid data via local drift decoupling and correction." CVPR 2022.

Q2: More clarifications of the comparisons between IID setting and non-IID setting.

We consider the standard IID and non-IID settings in federated learning literature. Specifically, the data of local clients are sampled from the same data distribution in the IID setting, while the data of clients are sampled from different data distributions in the non-IID setting. In the context of federated conformal prediction, IID data samples among clients can imply the IID non-conformity scores of clients, which implies that the characterization vectors of scores are sampled from the same multinomial distribution. Similarly, non-IID data samples among clients can also imply the non-IID non-conformity scores of clients, which implies that the characterization vectors are sampled from different multinomial distributions. In Assumption 3.1, we quantify the maximum disparity of different multinomial distributions with $\sigma>0$, and a larger $\sigma$ can induce a larger non-IID degree. Note that $\sigma=0$ is equivalent to the IID setting because $\sigma=0$ implies that the parameters of multinomial distributions are the same: $\overline{\rm{v}}^{(k\_1)} = \overline{\rm{v}}^{(k\_2)}, \forall k\_1,k\_2$. To conclude, $\sigma=0$ in Assumption 3.1 formally defines the IID setting in the context of federated conformal prediction, while Assumption 3.1 with $\sigma>0$ defines the non-IID setting with non-IID degree $\sigma$.

Q1: More clarification of the consideration of heterogeneity in analysis and evaluations.

We thank you for your valuable comments and suggestions. We added clarifications and improvements of Rob-FCP for the non-IID setting from both the theoretical perspective and the evaluation perspective.

From the perspective of theoretical analysis, we provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 based on the assumption of bounded disparity among benign clients in Assumption 3.1. We added clarifications that the assumption is quite standard, typical, and not simplified across the literature of non-IID federated learning analysis [1] and Byzantine analysis [2,3]. Concretely, Li et al. [1] quantify the non-iid degree (i.e., disparity) of local loss of clients with $\Gamma$ in Section 3.1 of [1] and accordingly provide the convergence guarantee of federated optimization in Theorem 1 of [1], which is a function of the disparity $\Gamma$. Park et al. [2] assume a bounded difference $\rho_1$ between the local loss of benign clients and global loss in Assumption 2 of [2] and provide the convergence analysis in federated Byzantine optimization in Theorem 1 of [2] as a function of $\rho_1$. Data et al. [3] have an assumption of bounded gradient dissimilarity $\kappa$ in Assumption 2 of [3] and prove a convergence guarantee in Theorem 1 of [3] regarding $\kappa$. Similarly, in our paper, we assume a bounded disparity of score statistics quantified with $\sigma$ in Assumption 3.1 and accordingly provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 as a function of $\sigma$. As we can see, the type of assumption is quite standard in the analysis setup of the line of non-IID analysis and Byzantine analysis. The assumption is also essential since without a quantity to restrict the disparity in local behavior, the local behavior can vary arbitrarily, and we can not control global performance quantitatively. From the results in Corollary 1, we can also see that as long as the disparity bound $\sigma$ is finite, the coverage bound in the non-IID setting is asymptotically valid and tight with sufficiently large benign sample sizes $n_b$. We added these clarifications and details in Section 3.3 in the revised manuscript.

From the evaluation perspective, we added more clarifications and illustrations on how we construct non-IID data of different levels and also added more evaluations on various approaches to non-IID data construction. We first added clarifications that we followed the standard evaluation setup of non-IID federated learning by sampling different label ratios for different clients from the Dirichlet distribution as the literature [4,5,6,7]. Concretely, we sample $p_{c,j} \sim \text{Dir}(\beta)$ and allocate a $p_{c,j}$ proportion of the instances with class $c$ to the client $j$. Here $\text{Dir}(·)$ denotes the Dirichlet distribution and $\beta$ is a concentration parameter ($\beta$ > 0). Dirichlet distribution is commonly used as the prior distribution in Bayesian statistics and is an appropriate choice to simulate real-world data distribution. An advantage of this approach is that we can flexibly change the imbalance level by varying the concentration parameter $\beta$. If $\beta$ is set to a smaller value, then the partition is more unbalanced. We fixed the imbalance level $\beta$ as $0.5$ in the evaluations before the rebuttal period. Following the suggestion, we added evaluations with different imbalance levels $\beta$ to show the effectiveness of Rob-FCP under different non-IID settings. The results in the following Table 1 demonstrate that under multiple degrees of data imbalance in non-IID federated conformal prediction, Rob-FCP consistently outperforms FCP in achieving a nominal marginal coverage level in the existence of Byzantine clients. We also consider alternative approaches to construct non-IID data with demographic differences in federated learning. Concretely, we split the SHHS dataset by sorting five different attributes: wake time, N1, N2, N3, REM. For example, we first sort the instances according to the wake time of patients and then assign them to 100 clients in sequence. Therefore, some clients are assigned patients with an early wake time, and some are assigned instances with late wake time. The results in Table 2 show that in this type of non-IID partition, Rob-FCP still demonstrates robustness and effectiveness compared to FCP.

Q1 (to continue):  The assumptions considered are over-simplified and may lead to failure in difficult cases. More details of the nonIID setting and different levels of being nonIID can be helpful.

Table 1. Marginal coverage / average set size with different non-IID imbalance level $\beta$, the parameter of Dirichlet distribution where the label ratios of clients are sampled from. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

Table 2. Marginal coverage / average set size on SHHS with non-IID data partition based on different attributes: wake time, N1, N2, N3, REM. The evaluation is done under different Coverage attack with $40\%~(K_m/K=40\%)$ malicious clients. The desired marginal coverage is $0.9$. 

[1] Li, Xiang, et al. "On the convergence of fedavg on non-iid data." ICLR 2020.

[2] Park, Jungwuk, et al. "Sageflow: Robust federated learning against both stragglers and adversaries." NeurIPS 2021.

[3] Data, Deepesh, et al. "Byzantine-resilient high-dimensional SGD with local iterations on heterogeneous data." ICML 2021.

[4] Yurochkin, Mikhail, et al. "Bayesian nonparametric federated learning of neural networks." International conference on machine learning. ICML 2019.

[5] Lin, Tao, et al. "Ensemble distillation for robust model fusion in federated learning." NeurIPS 2020.

[6] Wang, Hongyi, et al. "Federated learning with matched averaging." ICLR 2020.

[7] Gao, Liang, et al. "Feddc: Federated learning with non-iid data via local drift decoupling and correction." CVPR 2022.

Q1: The assumptions considered are over-simplified and may lead to failure in difficult cases. More details of the nonIID setting and different levels of being nonIID can be helpful.

We thank you for your valuable comments and suggestions. We added clarifications and improvements of Rob-FCP for the non-IID setting from both the theoretical perspective and the evaluation perspective.

From the perspective of theoretical analysis, we provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 based on the assumption of bounded disparity among benign clients in Assumption 3.1. We added clarifications that the assumption is quite standard, typical, and not simplified across the literature of non-IID federated learning analysis [1] and Byzantine analysis [2,3]. Concretely, Li et al. [1] quantify the non-iid degree (i.e., disparity) of local loss of clients with $\Gamma$ in Section 3.1 of [1] and accordingly provide the convergence guarantee of federated optimization in Theorem 1 of [1], which is a function of the disparity $\Gamma$. Park et al. [2] assume a bounded difference $\rho_1$ between the local loss of benign clients and global loss in Assumption 2 of [2] and provide the convergence analysis in federated Byzantine optimization in Theorem 1 of [2] as a function of $\rho_1$. Data et al. [3] have an assumption of bounded gradient dissimilarity $\kappa$ in Assumption 2 of [3] and prove a convergence guarantee in Theorem 1 of [3] regarding $\kappa$. Similarly, in our paper, we assume a bounded disparity of score statistics quantified with $\sigma$ in Assumption 3.1 and accordingly provide the coverage guarantees of Rob-FCP in the non-IID setting in Corollary 1 as a function of $\sigma$. As we can see, the type of assumption is quite standard in the analysis setup of the line of non-IID analysis and Byzantine analysis. The assumption is also essential since without a quantity to restrict the disparity in local behavior, the local behavior can vary arbitrarily, and we can not control global performance quantitatively. From the results in Corollary 1, we can also see that as long as the disparity bound $\sigma$ is finite, the coverage bound in the non-IID setting is asymptotically valid and tight with sufficiently large benign sample sizes $n_b$. We added these clarifications and details in Section 3.3 in the revised manuscript.

From the evaluation perspective, we added more clarifications and illustrations on how we construct non-IID data of different levels and also added more evaluations on various approaches to non-IID data construction. We first added clarifications that we followed the standard evaluation setup of non-IID federated learning by sampling different label ratios for different clients from the Dirichlet distribution as the literature [4,5,6,7]. Concretely, we sample $p_{c,j} \sim \text{Dir}(\beta)$ and allocate a $p_{c,j}$ proportion of the instances with class $c$ to the client $j$. Here $\text{Dir}(·)$ denotes the Dirichlet distribution and $\beta$ is a concentration parameter ($\beta$ > 0). Dirichlet distribution is commonly used as the prior distribution in Bayesian statistics and is an appropriate choice to simulate real-world data distribution. An advantage of this approach is that we can flexibly change the imbalance level by varying the concentration parameter $\beta$. If $\beta$ is set to a smaller value, then the partition is more unbalanced. We fixed the imbalance level $\beta$ as $0.5$ in the evaluations before the rebuttal period. Following the suggestion, we added evaluations with different imbalance levels $\beta$ to show the effectiveness of Rob-FCP under different non-IID settings. The results in the following Table 1 demonstrate that under multiple degrees of data imbalance in non-IID federated conformal prediction, Rob-FCP consistently outperforms FCP in achieving a nominal marginal coverage level in the existence of Byzantine clients. We also consider alternative approaches to construct non-IID data with demographic differences in federated learning. Concretely, we split the SHHS dataset by sorting five different attributes: wake time, N1, N2, N3, REM. For example, we first sort the instances according to the wake time of patients and then assign them to 100 clients in sequence. Therefore, some clients are assigned patients with an early wake time, and some are assigned instances with late wake time. The results in Table 2 show that in this type of non-IID partition, Rob-FCP still demonstrates robustness and effectiveness compared to FCP.

I am sorry but I feel this is a very dangerous assumption, and leads to increased prediction disparity when leaving out minority samples that are not intentional attack. What makes it really dangerous is that this decision is based on prediction quality, as a result, there is no way that you can even assess which samples during test are belonging to the left-out minority populations.

I am willing to increase my score if the authors can explain to me why this is not a concern in the settings considered.