ECE PhD Dissertation Defense: Armin Moharrer

PhD Dissertation Defense: Leveraging Structural Properties for Large-Scale Optimization

Armin Moharrer

Location: Zoom Link

Abstract: Large scale optimization problems abound in data mining, machine learning, and system design. We address the challenges posed by such large scale optimization problems by providing efficient optimization algorithms. The scope of studied problems is quite broad; it includes applications such as experimental design, computing graph distances (dissimilarity scores), training auto-encoders, multi-target regression, and the design of cache networks. We leverage the structural properties present in these problems, e.g., sparsity or separability. In particular, we introduce some structural properties under which the Frank-Wolfe algorithm (FW) can be distributed over a cluster of computers. We show that the distributed FW running over 350 workers (CPUs) solves an instance of experimental design problem with 20M variables in 79 minutes, while the serial implementation takes 48 hours. Furthermore, we study a variant of FW for the design of cache networks. The problem is NP-hard, but we achieve a $1-1/e$ approximation ratio, by optimizing a non-convex relaxation via FW. We also propose a distributed Alternating Direction Method of Multipliers (ADMM) algorithm for computing graph distances. We observe speedups of 153 times when running over a cluster with 448 CPUs, in comparison with running over 1 CPU, for graphs with 2.4K nodes. Moreover, we study applications of ADMM in solving robust variants of risk minimization problems; in these variants we replace the typically chosen mean squared error loss with a general lp norm. We combine model based optimization with ADMM to minimize the resulting non-smooth and non-convex objectives. We show that a stochastic variant of ADMM converges with the rate O(log T/T) and is highly efficient for optimizing the corresponding model functions.