SnapVX: A Network-Based Convex Optimization Solver
Authors: David Hallac, Christopher Wong, Steven Diamond, Abhijit Sharang, Rok Sosič, Stephen Boyd, Jure Leskovec
JMLR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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 fit into memory, is shown in Table 1. Figure 1 displays a comparison to a general-purpose solver (ECOS, via CVXPY) in log-log scale. |
| Researcher Affiliation | Academia | David Hallac EMAIL Christopher Wong EMAIL Steven Diamond EMAIL Abhijit Sharang EMAIL Rok Sosiˇc EMAIL Stephen Boyd EMAIL Jure Leskovec EMAIL Department of Electrical Engineering Department of Computer Science Stanford University, Stanford, CA, 94305 |
| Pseudocode | No | The following code specifies 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. This code snippet demonstrates usage rather than presenting the structured pseudocode for the underlying algorithm. |
| Open Source Code | Yes | 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. |
| Open Datasets | No | The paper mentions applying Snap VX to various problems like "housing price prediction (Hallac et al., 2015) to ride-sharing analysis (Ghosh et al., 2016) to high-dimensional regression (Yamada et al., 2016)", but it does not provide concrete access information (links, DOIs, repositories) for the datasets used in its own experiments or for these applications. The main scalability experiment uses a synthetically generated "3-regular graph" without specifying a public dataset. |
| Dataset Splits | No | The paper describes experiments on a synthetically generated "3-regular graph" with varying numbers of nodes to test scalability. This setup does not involve traditional training/testing/validation splits, and no specific dataset split information is provided. |
| Hardware Specification | Yes | The time required for Snap VX to converge, on a 40-core CPU where the entire problem can fit into memory, is shown in Table 1. |
| Software Dependencies | No | Snap VX 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. 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). While specific software packages are mentioned, their exact version numbers are not provided in the text. |
| Experiment Setup | Yes | ADMM iteration limits, verbose mode (to list intermediate steps at each iteration), and defining customized convergence thresholds. ... The convergence time of ADMM depends on the value of the penalty parameter ρ (Nishihara et al., 2015), as it affects the tradeoffbetween 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 define a function to update ρ after each iteration based on the primal and dual residual values (He et al., 2000; Fougner and Boyd, 2015). |