2026 Theses Doctoral

Advances and Algorithms for Multi-group Learning

Deng, Samuel

Multi-group learning is a formal learning theoretic model that generalizes various classical notions of learning (such as realizable PAC learning, agnostic PAC learning, and online learning), requiring predictors to perform well not just overall, but also simultaneously well on pre-specified subsets (“groups”) of the input space. Due to this simultaneous requirement over a potentially infinite collection of overlapping groups, the algorithmic techniques (e.g. empirical risk minimization) feasible in “single-group” statistical and online learning no longer suffice on their own. This thesis aims to advance our algorithmic and statistical understanding of multi-group learning by providing algorithms for various models of multi-group learning that achieve optimal or near-optimal rates. More concretely, we present:

1. An algorithm that achieves oracle-efficient multi-group learning in the sequential, online multi-group learning setting when the number of groups is infinite or too large to explicitly enumerate.

2. An algorithm that achieves near-optimal statistical rates for multi-group agnostic PAC learning when the groups are hierarchically structured, a natural assumption from domains such as medical diagnosis and fairness.

3. A concept class tailored to the multi-group learning setting over which empirical risk
minimization provides near-optimal statistical rates for the group-realizable setting of multi-group learning, which generalizes the classical realizability assumption in PAC learning. These results apply even when the family of groups is infinite, with bounded VC dimension.