Algebraic and Geometric Structure in Machine Learning and Optimization Algorithms

摘要

As the scope and importance of machine learning applications widens, it becomes increasingly important to design machine learning and optimization methods that will efficiently and provably obtain desired outputs. We may wish to guarantee that an optimization algorithm quickly converges to a global minimum or that a machine learning model generalizes well to unseen data. We would like ways to better understand how to design and analyze such algorithms so that we can make such guarantees.;In this thesis, we take an algebraic and geometric approach towards understanding machine learning and optimization algorithms. Many optimization problems, whether implicitly or explicitly, contain large amounts of algebraic and geometric structure. This can arise from the feasible region of the problem or from the optimization algorithm being analyzed. A similar phenomenon occurs in machine learning, where there is geometric structure in both the loss function used to evaluate the machine learning algorithm, and in the method used to train the machine. As we develop more complicated models and methods (such as deep neural networks), this structure becomes more and more useful to start understanding important properties of our machine learning and optimization algorithms.;We show that various problems in both areas have algebraic or geometric structure and that we can use this structure to design more accurate and efficient algorithms. We use this approach in four primary areas. First, we show that by using underlying algebraic structure, we can design improved optimization methods for a control-theoretic problem. Second, we use the geometry of algebraic subspaces to address structured clustering problems, even in the presence of missing data. Third, we show that if certain geometric properties hold, we can directly bound the generalization error of learned models of machine learning algorithms. Finally, we show that we can use tools from linear algebra and random matrix theory to design more robust distributed optimization algorithms.