提出新算法实现多组学习最优样本复杂度，理论更优且可证。
A One-Inclusion Graph Approach to Multi-Group Learning
- 基于广义二分图b匹配扩展一包含图策略
- 在组可实现下达到最优的log n / n收敛速度
- 适合关注公平学习与样本效率的研究者
我们证明了多组学习中样本复杂度的最紧上界。所提算法通过广义二分图b匹配扩展了一包含图预测策略。在组可实现设定下，我们给出了下界，确认该算法的log n / n收敛率在一般情况下是最优的。若将学习目标放宽为评估组在采样时未知，则该算法在组可实现条件下可达到最优的1/n收敛率。
原文摘要 · Abstract (English)
We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite $b$-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's $\log n / n$ convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal $1/n$ convergence rate under group-realizability.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。