Machine Learning Department
School of Computer Science, Carnegie Mellon University


Optimizing Optimization: Scalable Convex Programming
with Proximal Operators

Matt Wytock

March 2016

Ph.D. Thesis


Keywords: Convex optimization, proximal operator, operator splitting, Newton method, sparsity, graphical model, wind power, forecasting, energy disaggregation, microgrids

Convex optimization has developed a wide variety of useful tools critical to many applications in machine learning. However, unlike linear and quadratic programming, general convex solvers have not yet reached sufficient maturity to fully decouple the convex programming model from the numerical algorithms required for implementation. Especially as datasets grow in size, there is a significant gap in speed and scalability between general solvers and specialized algorithms.

This thesis addresses this gap with a new model for convex programming based on an intermediate representation of convex problems as a sum of functions with efficient proximal operators. This representation serves two purposes: 1) many problems can be expressed in terms of functions with simple proximal operators, and 2) the proximal operator form serves as a general interface to any specialized algorithm that can incorporate additional l2-regularization. On a single CPU core, numerical results demonstrate that the prox-affine form results in significantly faster algorithms than existing general solvers based on conic forms. In addition, splitting problems into separable sums is attractive from the perspective of distributing solver work amongst multiple cores and machines.

We apply large-scale convex programming to several problems arising from building the next-generation, information-enabled electrical grid. In these problems (as is common in many domains) large, high-dimensional datasets present opportunities for novel data-driven solutions. We present approaches based on convex models for several problems: probabilistic forecasting of electricity generation and demand, preventing failures in microgrids and source separation for whole-home energy disaggregation.

145 pages

Thesis Committee:
J. Zico Kolter (Chair)
Ryan Tibshirani
Geoffrey Gordon
Stephen Boyd (Stanford University)
Arunava Majumdar (Stanford University)
Tom M. Mitchell, Head, Machine Learning Department
Andrew W. Moore, Dean, School of Computer Science

SCS Technical Report Collection
School of Computer Science