Faster Randomized Interior Point Methods for Tall/Wide Linear Programs
Authors: Agniva Chowdhury, Gregory Dexter, Palma London, Haim Avron, Petros Drineas
JMLR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluations verify our theoretical results on both real-world and synthetic data. Keywords: Randomized Linear Algebra; Linear Programming; Interior Point Methods. |
| Researcher Affiliation | Academia | Agniva Chowdhury EMAIL Computer Science and Mathematics Division Oak Ridge National Laboratory Oak Ridge, TN 37830, USA Gregory Dexter EMAIL Department of Computer Science Purdue University West Lafayette, IN 47907, USA Palma London EMAIL Operations Research and Information Engineering Cornell University Ithaca, NY 14853, USA Haim Avron EMAIL School of Mathematical Sciences Tel Aviv University Tel Aviv, Israel Petros Drineas EMAIL Department of Computer Science Purdue University West Lafayette, IN 47907, USA |
| Pseudocode | Yes | Algorithm 1 Solving eqn. (5) via CG or Chebyshev iteration Algorithm 2 Feasible IPM Algorithm 3 Infeasible IPM |
| Open Source Code | No | The paper does not provide a specific link to a code repository, an explicit statement of code release, or mention code in supplementary materials for the described methodology. The statement "The experiments were implemented in Python" refers to the tool used, not the release of their own code. |
| Open Datasets | Yes | Here we demonstrate the empirical performance of our algorithm on a variety of real-world data sets from the UCI ML Repository (Dua and Graff, 2017). More specifically, we consider two problems that were part of the Neur IPS 2003 feature selection challenge: ARCENE and DEXTER (Guyon et al., 2005). For the ARCENE data set, the task is to distinguish between cancer and normal patterns from mass-spectrometric data and DEXTER data set is for a text classification problem. Further, we consider Driv Face (Diaz-Chito et al., 2016), a problem concerned with identifying the gaze direction in photos of human subjects taken while driving, and a gene expression cancer RNA-Sequencing data set, accessible on the UCI ML Repository, which is part of the RNA-Seq (Hi Seq) PANCAN data set (Weinstein et al., 2013). |
| Dataset Splits | No | The paper mentions the use of several datasets (e.g., ARCENE, DEXTER, Driv Face, Gene RNA) and describes the problem types (e.g., binary classification), but it does not specify any training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | Yes | The experiments were implemented in Python and run on a server with Intel E5-2623V3@3.0GHz 8 cores and 64GB RAM. |
| Software Dependencies | No | The experiments were implemented in Python and we observed that the results for both synthetic data (generated as described in Appendix B.2) and real-world data were qualitatively similar. Thus, we highlight results on several representative real-world datasets. The experiments were implemented in Python and run on a server with Intel E5-2623V3@3.0GHz 8 cores and 64GB RAM. ... We also use CVXPY as a benchmark to compare the accuracy of the solutions |
| Experiment Setup | Yes | If not specified: τ = 10 9, tol CG = 10 5, and σ = 0.5. We evaluated a Gaussian sketching matrix, and the initial triplet (x, y, s) for all IPM algorithms was set to be all ones. |