Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Oblivious Sketching-based Central Path Method for Linear Programming
Authors: Zhao Song, Zheng Yu
ICML 2021 | Venue PDF | 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. |