Oblivious Sketching-based Central Path Method for Linear Programming
Authors: Zhao Song, Zheng Yu
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we propose a sketching-based central path method for solving linear programmings, whose running time matches the state of the art results (Cohen et al., 2019b; Lee et al., 2019). Our method opens up the iterations of the central path method and deploys an iterate and sketch approach towards the problem by introducing a new coordinate-wise embedding technique, which may be of independent interest. Our framework for solving LP naturally generalizes to a broader class of convex optimization problems including empirical risk minimization. Theorem 1.1 (Main result). Given a linear program min Ax=b,x 0 c x with no redundant constraints. Assume that for any x 0 with Ax = b, we have x 1 R. Then for any accuracy δ (0, 1], our LP algorithm outputs a vector x 0 such that c x min Ax=b,x 0 c x + δ c R and Ax b 1 δ (R A 1 + b 1) in expected time nω+o(1) + n2.5 α/2+o(1) + n2+1/6+o(1) log(n/δ). |
| Researcher Affiliation | Academia | 1School of Mathematics, Institute for Advanced Study, United States 2Department of Operations Research and Financial Engineering, Princeton University, United States. |
| Pseudocode | Yes | Algorithm 1 Main algorithm (simplified) Algorithm 2 Sketching-based central path step Algorithm 3 Projection Maintenance Data Structure Algorithm 4 UPDATE Algorithm 5 QUERY |
| Open Source Code | No | The paper does not provide any explicit statements about open-source code availability or links to code repositories for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe experiments involving datasets, training, or public data availability. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits (e.g., training, validation, test sets). |
| Hardware Specification | No | The paper does not mention any specific hardware used for experiments. It focuses on theoretical algorithmic complexity. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical, describing an algorithm and its properties. It does not include details on an experimental setup, such as hyperparameters or system-level training settings. |