Multi-group agnostic learning is a formal learning criterion that is concernedwith the conditional risks of predictors within subgroups of a population. The criterion addresses recent practical concerns such as subgroup fairness andhidden stratification. This paper studies the structure of solutions to the multi-group learning problem, and provides simple and near-optimal algorithms for the learningproblem.