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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Unified Projection-Free Algorithms for Adversarial DR-Submodular Optimization
Authors: Mohammad Pedramfar, Yididiya Y. Nadew, Christopher John Quinn, Vaneet Aggarwal
ICLR 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We test our online continuous DR-submodular maximization algorithms for non-monotone objectives, a downward-closed feasible region, and both full-information and semi-bandit gradient feedback. We briefly describe the setup and highlight key results. See Appendix H for more details. We use online non-convex/non-concave non-monotone quadratic maximization following (Bian et al., 2017a; Chen et al., 2018b; Zhang et al., 2023), randomly generating linear inequalities to form a downward closed feasible region and for each round t we generate a quadratic function Ft(x) = 1/2x Hx + h x + c. Similar to (Zhang et al., 2023), we considered three pairs (n, m) of dimensions n and number of constraints m, {(25, 15), (40, 20), (50, 50)}. (...) Figure 2 shows both averaged regret within runs for a fixed horizon (top row) and cumulative regret for different horizons, averaged over 10 independent runs. |
| Researcher Affiliation | Academia | Mohammad Pedramfar School of Industrial Engineering Purdue University West Lafayette, IN 47907, USA EMAIL Yididiya Y. Nadew Department of Computer Science Iowa State University Ames, IA 50010, USA EMAIL Christopher J. Quinn Department of Computer Science Iowa State University Ames, IA 50010, USA EMAIL Vaneet Aggarwal School of Industrial Engineering Purdue University West Lafayette, IN 47907, USA EMAIL |
| Pseudocode | Yes | Algorithm 1: Generalized Meta-Frank Wolfe and Algorithm 2: Generalized (Semi-)Bandit-Frank Wolfe |
| Open Source Code | Yes | Source code for our algorithms is available at https://github.com/yididiyan/ unified-dr-submodular. |
| Open Datasets | No | We use online non-convex/non-concave non-monotone quadratic maximization... randomly generating linear inequalities to form a downward closed feasible region and for each round t we generate a quadratic function Ft(x) = 1/2x Hx + h x + c. The paper describes synthetic data generation for its experiments, rather than using a publicly available dataset with specific access information. |
| Dataset Splits | No | The paper describes an online learning setting where functions are generated per round, rather than using fixed training, validation, and test splits from a static dataset. Therefore, specific dataset split information is not provided in the traditional sense. |
| Hardware Specification | Yes | For the experiments we ran to generate Fig. 2, we used a compute cluster. The nodes had AMD EPYC 7543P processors. Individual jobs used 8 cores and 4 GB of memory. For the running times reported in Table 3, we conducted the experiments on a single desktop machine with a 12-core AMD Ryzen Threadripper 1920X processor and 64GB of memory. |
| Software Dependencies | Yes | We used Python (v3.8.10) and CVXOPT (v1.3.0), a free software package for convex optimization. |
| Experiment Setup | Yes | We use online non-convex/non-concave non-monotone quadratic maximization... randomly generating linear inequalities to form a downward closed feasible region and for each round t we generate a quadratic function Ft(x) = 1/2x Hx + h x + c. Here, the coefficient matrix H is a symmetric matrix whose entries Hi,j are drawn from a uniform distribution in [ 10, 0]... To make Ft non-monotone, we set h = 0.1 H u , where u Rn. Similar to (Zhang et al., 2023), we set u = 1. In addition, to ensure non-negativity, the constant term is set to c = 0.5 P... Like Zhang et al. (2023), we considered three pairs (n, m) of dimensions n and number of constraints m, {(25, 15), (40, 20), (50, 50)}. For a gradient query Ft(x), we generate a random noise vector nt N(0, 1) and return the noisy gradient e Ft(x) = Ft(x) + ϵ nt nt , with a noise scale ϵ = 0.1. We vary horizons between T = 20 and T = 500. |