  Federated learning (FL) is an emerging machine learning (ML) paradigm that
enables heterogeneous edge devices to collaboratively train ML models without
revealing their raw data to a logically centralized server. However, beyond the
heterogeneous device capacity, FL participants often exhibit differences in
their data distributions, which are not independent and identically distributed
(Non-IID). Many existing works present point solutions to address issues like
slow convergence, low final accuracy, and bias in FL, all stemming from client
heterogeneity. In this paper, we explore an additional layer of complexity to
mitigate such heterogeneity by grouping clients with statistically similar data
distributions (cohorts). We propose Auxo to gradually identify such cohorts in
large-scale, low-availability, and resource-constrained FL populations. Auxo
then adaptively determines how to train cohort-specific models in order to
achieve better model performance and ensure resource efficiency. Our extensive
evaluations show that, by identifying cohorts with smaller heterogeneity and
performing efficient cohort-based training, Auxo boosts various existing FL
solutions in terms of final accuracy (2.1% - 8.2%), convergence time (up to
2.2x), and model bias (4.8% - 53.8%).
