- Main
Efficient Algorithms for Modern Machine Learning Optimization
- Ding, Lisang
- Advisor(s): Osher, Stanley J.;
- Yin, Wotao
Abstract
The training of machine learning models is a central topic in modern computational research and is often formulated as an optimization problem. However, the optimization landscape in machine learning presents new and complex challenges. This dissertation addresses two related optimization problems: decentralized optimization, which arises in distributed training settings, and sum-of-minimum optimization, which emerges in mixed-model training.For the decentralized optimization problem, we revisit and construct a communication-optimal exact consensus scheme. This scheme is then judiciously integrated into the decentralized stochastic gradient descent algorithm. The proposed decentralized algorithm is scalable to any number of computing nodes and achieves state-of-the-art performance, which requires a transient iteration complexity of $\tilde O(n^3)$ and a communication overhead of one. For the sum-of-minimum optimization problem, we identify a novel connection to generalized clustering problems. Leveraging this insight, we develop a two-phase algorithm. In the initialization phase, we generalize the $k$-means++ clustering method; in the iteration phase, we apply a variant of the Lloyd algorithm. Theoretically, a tight initialization error bound and a convergence rate are provided. For both problems, extensive numerical experiments are provided to illustrate the empirical performance of the proposed algorithms.