The paper introduces a new framework called *agnostic federated learning* (AFL), which addresses the issue of bias in federated learning where the centralized model is trained based on data from multiple clients. The authors argue that the standard approach of using the uniform distribution over client data can lead to suboptimal or even detrimental performance, especially when the target distribution differs from the uniform distribution. They propose AFL, which optimizes the model for any possible target distribution formed by a mixture of client distributions, ensuring better fairness and adaptability to various scenarios. The paper presents theoretical guarantees for the AFL framework, including data-dependent Rademacher complexity bounds, and introduces a fast stochastic optimization algorithm to solve the optimization problem. The algorithm is analyzed for convergence under convex loss functions and hypothesis sets. Empirical results demonstrate the benefits of the AFL approach in several datasets. The framework and algorithm are also applicable to other learning scenarios such as cloud computing, domain adaptation, and drifting.The paper introduces a new framework called *agnostic federated learning* (AFL), which addresses the issue of bias in federated learning where the centralized model is trained based on data from multiple clients. The authors argue that the standard approach of using the uniform distribution over client data can lead to suboptimal or even detrimental performance, especially when the target distribution differs from the uniform distribution. They propose AFL, which optimizes the model for any possible target distribution formed by a mixture of client distributions, ensuring better fairness and adaptability to various scenarios. The paper presents theoretical guarantees for the AFL framework, including data-dependent Rademacher complexity bounds, and introduces a fast stochastic optimization algorithm to solve the optimization problem. The algorithm is analyzed for convergence under convex loss functions and hypothesis sets. Empirical results demonstrate the benefits of the AFL approach in several datasets. The framework and algorithm are also applicable to other learning scenarios such as cloud computing, domain adaptation, and drifting.