# snapvx_a_networkbased_convex_optimization_solver__3390d7cf.pdf

Journal of Machine Learning Research 18 (2017) 1-5 Submitted 9/15; Revised 10/16; Published 2/17

Snap VX: A Network-Based Convex Optimization Solver

David Hallac hallac@stanford.edu Christopher Wong crwong@cs.stanford.edu Steven Diamond diamond@cs.stanford.edu Abhijit Sharang abhisg@cs.stanford.edu Rok Sosiˇc rok@cs.stanford.edu Stephen Boyd boyd@stanford.edu Jure Leskovec jure@cs.stanford.edu Department of Electrical Engineering

Department of Computer Science

Stanford University, Stanford, CA, 94305

Editor: Cheng Soon Ong

Snap VX is a high-performance solver for convex optimization problems deﬁned on networks. For problems of this form, Snap VX provides a fast and scalable solution with guaranteed global convergence. It combines the capabilities of two open source software packages: Snap.py and CVXPY. Snap.py is a large scale graph processing library, and CVXPY provides a general modeling framework for small-scale subproblems. Snap VX oﬀers a customizable yet easy-to-use Python interface with out-of-the-box functionality. Based on the Alternating Direction Method of Multipliers (ADMM), it is able to eﬃciently store, analyze, parallelize, and solve large optimization problems from a variety of diﬀerent applications. Documentation, examples, and more can be found on the Snap VX website at http://snap.stanford.edu/snapvx. Keywords: convex optimization, network analytics, graphs, data mining, ADMM

1. Introduction

Convex optimization is a widely used approach of modeling and solving problems in many diﬀerent ﬁelds, as it oﬀers well-established methods for ﬁnding globally optimal solutions. Numerous general-purpose optimization software packages exist (Sturm, 1999; Byrd et al., 2006; Mosek, 2010; Diamond and Boyd, 2016), but they typically rely on algorithms that are diﬃcult to scale, so many modern machine learning problems cannot be solved by these common, yet general, approaches. Instead, solving large scale examples often requires developing problem-speciﬁc solution methods, which can be very fast but require signiﬁcant optimization expertise to build. Furthermore, they are limited in scope, as they must be ﬁne-tuned to only one particular type of problem and thus are hard to generalize. In this paper, we build on the observation that many large convex optimization examples follow a common form in that they can often be split up into a series of subproblems using a network (graph) structure. Nodes are subproblems, representing anything from timestamps in a time-series data set to users in a social network. The edges then deﬁne the coupling, or relationships between the diﬀerent nodes, and the combination of nodes and edges yields the

c 2017 David Hallac, Christopher Wong, Steven Diamond, Abhijit Sharang, Rok Sosiˇc, Stephen Boyd, and Jure Leskovec.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v18/15-492.html.

Hallac, Wong, Diamond, Sharang, Sosiˇc, Boyd, and Leskovec

original convex optimization problem. This representation can refer to problems deﬁned on actual networks, such as social or transportation systems, or questions classically modeled in other ways, such as control theory or time-series analysis. Here, we present Snap VX, a solver that is both scalable and general on optimization problems deﬁned over networks. It combines the graph capabilities of Snap.py (Leskovec and Sosiˇc, 2016) with the general modeling framework from CVXPY (Diamond and Boyd, 2016). We show how Snap VX works, present syntax and supported features, scale it to large problems, and describe how it can be used to solve convex optimization problems from a variety of diﬀerent ﬁelds. The full version of our solver, which is released under the BSD Open-Source License, can be found at the project website, http://snap.stanford.edu/ snapvx. In addition to the source code, the download contains installation instructions, unit tests, documentation, and several examples to help users get started.

2. Snap VX General Form

Consider an optimization problem on an undirected graph G = (V, E), with vertex set V and edge set E, of the form:

minimize x P

i V fi(xi) + P

(j,k) E gjk(xj, xk). (1)

Variable xi is associated with node i, for i = 1, . . . , |V| (the size of xi can vary at each node). In problem (1), fi is the cost function at node i, and gjk is the cost associated with edge (j, k). Constraints are represented by extended (inﬁnite) values of fi and gjk. Note that nodes and edges can also have local, private optimization variables (which can also vary in size). These remain conﬁned to a single node or edge, though, whereas the xi s are shared between diﬀerent parts of the network. We consider only convex objectives and constraints for fi and gjk, so the entire problem is a convex optimization problem. To solve problem (1), Snap VX uses a splitting algorithm based on the Alternating Direction Method of Multipliers (ADMM) (Boyd et al., 2011). With ADMM, each individual component of the graph solves its own subproblem, iteratively passing small messages over the network and eventually converging to an optimal solution. See the Snap VX developer documentation for more details on the underlying derivation. By splitting up the problem into a series of subproblems, Snap VX is able to solve much larger convex optimization examples than standard solvers, which solve the whole problem at once. ADMM also keeps the optimality beneﬁts that general solvers enjoy: not only are we guaranteed to obtain an optimal solution, but we also are given a certiﬁcate of optimality in the form of primal and dual residuals; see (Parikh and Boyd, 2014). Snap VX stores the network using a Snap.py graph structure. This allows fast traversal and easy manipulation, as well as eﬃcient storage. On top of the standard graph, each node/edge is given convex objectives and constraints using CVXPY syntax. To ﬁnd a global solution, Snap VX automatically splits up the problem and solves each subproblem using CVXPY, iteratively handling the ADMM message passing behind the scenes. Though wrapped in a Python layer, CVXPY uses ECOS and CVXOPT (two high-performance numerical optimization packages) as its primary underlying solvers (Andersen et al., 2014; Domahidi et al., 2013), so the Python overhead is not signiﬁcant and allows for easier interpretability and improved user interface. To parallelize the solver, a worker pool coordinates

Snap VX: A Network-Based Convex Optimization Solver

updates for the separate subproblems using Python s multiprocessing library. Snap VX is built to run on a single machine, parallelizing across multiple cores and allowing out-ofthe-box functionality on machines ranging from standard laptops to large-memory servers.

3. Syntax and Supported Features

We now present usage of Snap VX on a simple example. Complete documentation and more examples are available on the Snap VX website. Consider two nodes with an edge between them. We solve for a problem where each node has an unknown variable xi R1. The ﬁrst node s objective is to minimize x2 1 subject to x1 0, the second s is to minimize |x2 + 3|, and the edge objective penalizes the square norm diﬀerence between the two variables, x1 x2 2 2. The following code speciﬁes the optimization problem and solves it:

from snapvx import gvx = TGraph VX() #Create a new graph x1 = Variable(1, name= x1 ) #Create a variable for node 1 gvx.Add Node(1, Objective=square(x1), Constraints=[x1 <= 0]) #Add new node x2 = Variable(1, name= x2 ) #Repeat for node 2 gvx.Add Node(2, abs(x2 + 3), []) gvx.Add Edge(1, 2, Objective=square(norm(x1 x2)), Constraints=[]) #Add edge between nodes gvx.Solve() #Solve the problem gvx.Print Solution() #Print the solution on a node by node basis

As Snap VX is meant to be a general-purpose solver, it has many customizable options to help easily and eﬃciently solve a wide range of convex optimization problems. These include ADMM iteration limits, verbose mode (to list intermediate steps at each iteration), and deﬁning customized convergence thresholds. Two key features are highlighted below: Bulk Loading - Often, the objectives and constraints at each node or edge will share a common form. For example, all the nodes could be trying to minimize x ai 2 for diﬀerent values of ai. Rather than requiring users to manually input each of these values, Snap VX allows for bulk loading of data. The functions Add Node Objectives and Add Edge Objectives allow the user to specify the general form of the objectives and an external ﬁle with separate data, and Snap VX ﬁlls in the details. This functionality makes practical and signiﬁcantly speeds up the loading of very large data sets. ADMM ρ-update - The convergence time of ADMM depends on the value of the penalty parameter ρ (Nishihara et al., 2015), as it aﬀects the tradeoﬀbetween primal and dual convergence, both of which need to be obtained for the overall problem to be solved. Snap VX users are not only able to select the value of ρ (it defaults to ρ = 1), but can also deﬁne a function to update ρ after each iteration based on the primal and dual residual values (He et al., 2000; Fougner and Boyd, 2015).

4. Scalability

One of the biggest beneﬁts of Snap VX is that it allows us to solve large problems very eﬃciently. It does so by automatically parallelizing the ADMM updates across multiple cores of a single machine using Python s multiprocessing class. Note that Snap VX is meant to be run on a single machine, rather than in a distributed computing environment. Convergence time depends on the problem complexity, but we empirically observe that it scales

Hallac, Wong, Diamond, Sharang, Sosiˇc, Boyd, and Leskovec

105 106 107

Number of Unknowns

Time (Minutes) for Convergence

Convergence Time vs. Problem Size

ECOS Snap VX

# of Unknowns Snap VX Solution Time (Minutes) 100,000 0.79 500,000 2.95 1 million 6.06 5 million 27.30 10 million 55.42 20 million 106.33 30 million 161.95

Figure 1: Timing comparison of Snap VX and a general-purpose solver.

Table 1: Snap VX convergence time for several diﬀerent problem sizes.

approximately linearly with problem size. We compare Snap VX and a general solver for a problem on a 3-regular graph. Each node solves for an unknown variable in R9000, where the node objectives are sum-of-Huber penalties (Huber, 1964) and edges have network lasso penalties (Hallac et al., 2015). By varying the number of nodes, we can span a wide range of problem sizes. The time required for Snap VX to converge, on a 40-core CPU where the entire problem can ﬁt into memory, is shown in Table 1. Figure 1 displays a comparison to a general-purpose solver (ECOS, via CVXPY) in log-log scale.

5. Applications

Snap VX was created to allow users without signiﬁcant optimization expertise to solve large network-based convex optimization problems by taking advantage of the powerful and scalable ADMM algorithm. Common examples from many diﬀerent ﬁelds can be formulated in a Snap VX-friendly manner. Our software has been used to solve real-world machine learning problems ranging from housing price prediction (Hallac et al., 2015) to ride-sharing analysis (Ghosh et al., 2016) to high-dimensional regression (Yamada et al., 2016), often signiﬁcantly outperforming other commonly used approaches. Examples in the Snap VX download package and on the project website including ﬁnancial modeling, network inference, image processing, Page Rank, and time-series analysis guide users towards applying the software to a variety of applications. Both user and developer documentation help new users get started and, if they are interested, contribute to the code base. A robust set of unit tests ensures that the software has been properly downloaded and that the code is functioning as expected. Overall, our open-source software provides an easy-to-use ADMM solver that can scale to large problems and apply to a wide variety of examples. With an active user base and rising interest from a range of scientiﬁc and engineering ﬁelds, we hope that Snap VX can become a useful tool for convex optimization problems, both in research and industry.

Acknowledgments

This work was supported by NSF IIS-1149837, NIH BD2K, DARPA XDATA, DARPA SIMPLEX, Stanford Data Science Initiative, Boeing, Bosch, Lightspeed, SAP, and Volkswagen.

Snap VX: A Network-Based Convex Optimization Solver

M. Andersen, J. Dahl, and L. Vandenberghe. CVXOPT: A Python package for convex optimization, version 1.1.7. http://cvxopt.org/, 2014.

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3:1 122, 2011.

R. Byrd, J. Nocedal, and R. Waltz. KNITRO: An integrated package for nonlinear optimization. In Large-scale nonlinear optimization, pages 35 59. Springer, 2006.

S. Diamond and S. Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1 5, 2016.

A. Domahidi, E. Chu, and S. Boyd. ECOS: An SOCP solver for embedded systems. In European Control Conference, pages 3071 3076, 2013.

C. Fougner and S. Boyd. Parameter selection and pre-conditioning for a graph form solver. ar Xiv preprint ar Xiv:1503.08366, 2015.

S. Ghosh, K. Page, and D. De Roure. An application of network lasso optimization for ride sharing prediction. ar Xiv preprint ar Xiv:1606.03276, 2016.

D. Hallac, J. Leskovec, and S. Boyd. Network lasso: Clustering and optimization in large graphs. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 387 396, 2015.

B. He, H. Yang, and S. Wang. Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. Journal of Optimization Theory and Applications, 106(2):337 356, 2000.

P. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73 101, 1964.

J. Leskovec and R. Sosiˇc. SNAP: A general purpose network analysis and graph mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016.

Ap S Mosek. The MOSEK optimization software. Online at http://www. mosek. com, 2010.

R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. Jordan. A general analysis of the convergence of ADMM. In International Conference on Machine Learning, pages 343 352, 2015.

N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1: 123 231, 2014.

J. Sturm. Using Se Du Mi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization methods and software, 11(1-4):625 653, 1999.

M. Yamada, K. Takeuchi, T. Iwata, J. Shawe-Taylor, and S. Kaski. Localized lasso for high-dimensional regression. ar Xiv preprint ar Xiv:1603.06743, 2016.