CaltechTHESIS
  A Caltech Library Service

Frameworks for High Dimensional Convex Optimization

Citation

London, Palma Alise den Nijs (2020) Frameworks for High Dimensional Convex Optimization. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/db29-am33. https://resolver.caltech.edu/CaltechTHESIS:08162020-233437139

Abstract

We present novel, efficient algorithms for solving extremely large optimization problems. A significant bottleneck today is that as the size of datasets grow, researchers across disciplines desire to solve prohibitively massive optimization problems. In this thesis, we present methods to compress optimization problems. The general goal is to represent a huge problem as a smaller problem or set of smaller problems, while still retaining enough information to ensure provable guarantees on solution quality and run time. We apply this approach to the following three settings.

First, we propose a framework for accelerating both linear program solvers and convex solvers for problems with linear constraints. Our focus is on a class of problems for which data is either very costly, or hard to obtain. In these situations, the number of data points m available is much smaller than the number of variables, n. In a machine learning setting, this regime is increasingly prevalent since it is often advantageous to consider larger and larger feature spaces, while not necessarily obtaining proportionally more data. Analytically, we provide worst-case guarantees on both the runtime and the quality of the solution produced. Empirically, we show that our framework speeds up state-of-the-art commercial solvers by two orders of magnitude, while maintaining a near-optimal solution.

Second, we propose a novel approach for distributed optimization which uses far fewer messages than existing methods. We consider a setting in which the problem data are distributed over the nodes. We provide worst-case guarantees on the performance with respect to the amount of communication it requires and the quality of the solution. The algorithm uses O(log(n+m)) messages with high probability. We note that this is an exponential reduction compared to the O(n) communication required during each round of traditional consensus based approaches. In terms of solution quality, our algorithm produces a feasible, near optimal solution. Numeric results demonstrate that the approximation error matches that of ADMM in many cases, while using orders-of-magnitude less communication.

Lastly, we propose and analyze a provably accurate long-step infeasible Interior Point Algorithm (IPM) for linear programming. The core computational bottleneck in IPMs is the need to solve a linear system of equations at each iteration. We employ sketching techniques to make the linear system computation lighter, by handling well-known ill-conditioning problems that occur when using iterative solvers in IPMs for LPs. In particular, we propose a preconditioned Conjugate Gradient iterative solver for the linear system. Our sketching strategy makes the condition number of the preconditioned system provably small. In practice we demonstrate that our approach significantly reduces the condition number of the linear system, and thus allows for more efficient solving on a range of benchmark datasets.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:convex optimization; distributed optimization algorithms
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Wierman, Adam C.
Thesis Committee:
  • Low, Steven H. (chair)
  • Yue, Yisong
  • Anandkumar, Anima
  • Wierman, Adam C.
Defense Date:8 July 2020
Record Number:CaltechTHESIS:08162020-233437139
Persistent URL:https://resolver.caltech.edu/CaltechTHESIS:08162020-233437139
DOI:10.7907/db29-am33
Related URLs:
URLURL TypeDescription
https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/viewFile/17118/16589PublisherArticle adapted for ch.2
https://dl.acm.org/doi/pdf/10.1145/3366696DOIArticle adapted for ch.3
https://arxiv.org/abs/2003.08072arXivArticle adapted for ch.4
ORCID:
AuthorORCID
London, Palma Alise den Nijs0000-0001-6472-8293
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13856
Collection:CaltechTHESIS
Deposited By: Palma London
Deposited On:15 Sep 2020 15:37
Last Modified:22 Sep 2020 16:48

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

2MB

Repository Staff Only: item control page