From Enormous Structured Models to On-device Federated Learning: Robustness, Heterogeneity and Optimization

Thesis (Ph.D.)--University of Washington, 2022Artificial intelligence has been shaped by three revolutions in recent years: (1) differentiable programming, the practice of writing programs by chaining parameterized modules and learning these parameters from data, (2) an explosion of scale, where increasing model size consistently improves performance, and (3) federated learning, where model training moves to mobile devices, where the data is generated and resides. This dissertation presents diagnostic methods and new algorithms to measure and improve the robustness of machine learning models to heterogeneous operating circumstances across these revolutions. Differentiable programming and end-to-end learning from examples are challenged by applications that require combinatorial algorithms as a part of their computations. We overcome this problem with smoothed versions of combinatorial algorithms and rigorously show how to construct them from the top-$K$ best outputs. We leverage this smoothing to propose a family of accelerated optimization algorithms for structured prediction problems. Further, enormous language models have recently gained the ability to compose clear and coherent essays that are up to several hundred words long. We propose a comparison tool that directly measures how close the distribution of generated text is to that of human-written text. We show experimentally that the proposed measure correlates the strongest with human evaluations of machine text and can quantify many qualitative properties of machine-generated text, such as the effect of model size and decoding algorithms. Finally, the move to massively distributed on-device federated learning of models gives rise to new challenges due to the natural heterogeneity of underlying user data and privacy requirements of model aggregation. We propose federated learning method that is robust to corrupted updates sent by malicious users and proves effective where traditional outlier detection or filtering methods are not applicable due to privacy requirements. We also another federated learning method that improves performance for users who do not conform to population trends. In both cases, we introduce federated optimization algorithms that are both communication efficient and privacy-preserving