Testing the Feasibility of Linear Programs with Bandit Feedback
Authors: Aditya Gangrade, Aditya Gopalan, Venkatesh Saligrama, Clayton Scott
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conclude the paper by describing a heuristic implementation of EOGT, and its behaviour on the simple case of testing the feasibility of two linear constraints over the unit ball. The simulation is run for d [2 : 10]. In the varying Γ scenario, we fix d = 4, and impose the constraints x1 1/2 Γ for the feasible setting, and the constraints x1 Γ, x1 Γ in the infeasible case. The range Γ [0.2, 1] is studied at a grid of scale 0.1. Figure 2. Behaviour of the stopping time as d is varied for fixed Γ = 1/2 (left) and Γ is varied for fixed d = 4 (right) over the unit ball with m = 2. Averages and one-sigma error bars over 50 runs are reported. |
| Researcher Affiliation | Academia | 1Department of Electrical Computer Engineering, Boston University 2Department of Electrical Engineering and Computer Science, University of Michigan 3Department of Electrical Communication Engineering, Indian Institute of Science. Correspondence to: Aditya Gangrade <gangrade@bu.edu>. |
| Pseudocode | Yes | Algorithm 1 Ellipsoidal Optimistic-Greedy Test (EOGT) Algorithm 2 Tempered EOGT (T-EOGT) |
| Open Source Code | No | No explicit statement about the release of source code or a link to a code repository for the methodology was found. The paper only states 'The code was implemented in MATLAB' in the simulations section. |
| Open Datasets | No | The paper defines specific instances for simulation (e.g., 'the feasible instance x1 0, x2 0' or 'x1 1/2 Γ'), which are custom-defined for the experiments, not publicly available datasets with explicit access information. |
| Dataset Splits | No | The paper describes running simulations on defined instances but does not mention specific training, validation, or test dataset splits or cross-validation. |
| Hardware Specification | Yes | The code was implemented in MATLAB, and executed on a consumer grade Ryzen 5 CPU, with no multithreading, and took about 4 hours to run. |
| Software Dependencies | No | The paper states 'The code was implemented in MATLAB' but does not provide a specific version number for MATLAB or any other software dependencies. |
| Experiment Setup | Yes | Throughout, the feedback noise is independent Gaussian with standard deviation σ = 0.1 (the value of σ is used in the confidence radii, and in general, τ should be proportional to σ2). The parameter δ is set to 0.1, N = 1, and all results are averaged over 50 runs. |