A One-Inclusion Graph Approach to Multi-Group Learning
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911577888784384 |
|---|---|
| author | Bergam, Noah Deng, Samuel Hsu, Daniel |
| author_facet | Bergam, Noah Deng, Samuel Hsu, Daniel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23208 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A One-Inclusion Graph Approach to Multi-Group Learning Bergam, Noah Deng, Samuel Hsu, Daniel Machine Learning 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. |
| title | A One-Inclusion Graph Approach to Multi-Group Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2603.23208 |