A New Alternating Direction Method for Linear Programming
Authors: Sinong Wang, Ness Shroff
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this paper, we propose a new variable splitting method of LP and prove that our method has a convergence rate of O( A 2 log(1/ϵ)). The proof is based on simultaneously estimating the distance from a pair of primal dual iterates to the optimal primal and dual solution set by certain residuals. In practice, we result in a new first-order LP solver that can exploit both the sparsity and the specific structure of matrix A and a significant speedup for important problems such as basis pursuit, inverse covariance matrix estimation, L1 SVM and nonnegative matrix factorization problem compared with the current fastest LP solvers. ... In this section, we examine the performance of our algorithm and compare it with the state-of-art of algorithms developed for solving the LP. ... Figure 1: The duality gap versus the number of iterations. From left to right figures are the BP, NMF, the L1 SVM and and the SICE problem. Table 1: Timing Results for BP, SICE, NMF and L1 SVM Problem (in sec. long means > 60 hours) |
| Researcher Affiliation | Academia | Sinong Wang Department of ECE The Ohio State University wang.7691@osu.edu Ness Shroff Department of ECE and CSE The Ohio State University shroff.11@osu.edu |
| Pseudocode | Yes | Algorithm 1 Alternating Direction Method of Multiplier with Inexact Subproblem Solver ... Algorithm 2 Efficiently Subproblem Solver |
| Open Source Code | No | The paper does not provide any concrete access information (e.g., repository link, explicit statement of code release) for the source code. |
| Open Datasets | No | The paper mentions specific datasets by name (e.g., bp1, arcene, real-sim, sonar, colon, w2a, news20) and states 'The data source and statistics are included in the supplementary material.' However, it does not provide direct links, DOIs, specific citations with authors/year, or repository names within the main text to access these datasets. |
| Dataset Splits | No | The paper does not specify exact dataset split percentages or sample counts for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., GPU/CPU models, memory) used for running the experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers. |
| Experiment Setup | Yes | In the experiments, we require that the accuracy of subproblem solver ϵk = 10 3 and the stopping criteria is that both primal residual A1xk + A2yk b and dual residual AT 1 zk + c is less than 10 3. All the LP instances are generated from the basis pursuit, L1 SVM, SICE and NMF problems. ... We set proximity parameter ρ = 1. ... The stopping criterion requires that the primal and dual residual and the relative duality gap is less than 10 3. |