Group-realizable multi-group learning by minimizing empirical risk

Navid Ardeshir, Samuel Deng, Daniel Hsu, Jingwen Liu
1/23/2026
cs.LGstat.ML

No confident code implementation found for this paper.

Abstract

The sample complexity of multi-group learning is shown to improve in the group-realizable setting over the agnostic setting, even when the family of groups is infinite so long as it has finite VC dimension. The improved sample complexity is obtained by empirical risk minimization over the class of group-realizable concepts, which itself could have infinite VC dimension. Implementing this approach is also shown to be computationally intractable, and an alternative approach is suggested based on improper learning.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Multi-group Learning for Hierarchical Groups

83% match2026

Agnostic Multi-Group Active Learning

82% match2023

Group conditional validity via multi-group learning

81% match2023

Collaborative Learning with Different Labeling Functions

81% match2026

ShakyPrepend: A Multi-Group Learner with Improved Sample Complexity

80% match2026

Improved Sample Complexity for Multiclass PAC Learning

79% match2026

Cite this paper

@article{ardeshir2026grouprealizable,
  title  = {Group-realizable multi-group learning by minimizing empirical risk},
  author = {Navid Ardeshir and Samuel Deng and Daniel Hsu and Jingwen Liu},
  year   = {2026},
  eprint = {2601.16922},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2601.16922v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2601.16922.svg)](https://codeofpaper.com/paper/2601.16922)

Discussion