Generalization error bounds from learning theory provide statistical
guarantees on how well an algorithm will perform on previously unseen data. In
this paper, we characterize the impacts of data non-IIDness due to censored
feedback (a.k.a. selective labeling bias) on such bounds. We first derive an
extension of the well-known Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, which
characterizes the gap between empirical and theoretical CDFs given IID data, to
problems with non-IID data due to censored feedback. We then use this CDF error
bound to provide a bound on the generalization error guarantees of a classifier
trained on such non-IID data. We show that existing generalization error bounds
(which do not account for censored feedback) fail to correctly capture the
model's generalization guarantees, verifying the need for our bounds. We
further analyze the effectiveness of (pure and bounded) exploration techniques,
proposed by recent literature as a way to alleviate censored feedback, on
improving our error bounds. Together, our findings illustrate how a decision
maker should account for the trade-off between strengthening the generalization
guarantees of an algorithm and the costs incurred in data collection when
future data availability is limited by censored feedback.

非独立同分布的数据和带有审查反馈的数据对学习理论中的泛化误差界限有影响，本文通过推导改进的 Dvoretzky-Kiefer-Wolfowitz 不等式来界定这种影响，并通过分析探索技术的有效性提供新的误差界限模型。

基于被审查反馈的学习泛化误差界

Generalization Error Bounds for Learning under Censored Feedback

Federated Learning (FL) has emerged to allow multiple clients to
collaboratively train machine learning models on their private data. However,
training and deploying large models for broader applications is challenging in
resource-constrained environments. Fortunately, Split Federated Learning (SFL)
offers an excellent solution by alleviating the computation and communication
burden on the clients SFL often assumes labeled data for local training on
clients, however, it is not the case in practice.Prior works have adopted
semi-supervised techniques for leveraging unlabeled data in FL, but data
non-IIDness poses another challenge to ensure training efficiency. Herein, we
propose Pseudo-Clustering Semi-SFL, a novel system for training models in
scenarios where labeled data reside on the server. By introducing Clustering
Regularization, model performance under data non-IIDness can be improved.
Besides, our theoretical and experimental investigations into model convergence
reveal that the inconsistent training processes on labeled and unlabeled data
impact the effectiveness of clustering regularization. Upon this, we develop a
control algorithm for global updating frequency adaptation, which dynamically
adjusts the number of supervised training iterations to mitigate the training
inconsistency. Extensive experiments on benchmark models and datasets show that
our system provides a 3.3x speed-up in training time and reduces the
communication cost by about 80.1% while reaching the target accuracy, and
achieves up to 6.9% improvement in accuracy under non-IID scenarios compared to
the state-of-the-art.

在资源受限环境中，通过介绍聚类正则化和全局更新频率适应的控制算法，我们提出了一种新的训练模型系统，用于解决联合学习中的数据非独立同分布和模型收敛性问题，该系统在减少训练时间和通信成本的同时提高了准确性。