Online DR-Submodular Maximization: Minimizing Regret and Constraint Violation
Authors: Prasanna Raut, Omid Sadeghi, Maryam Fazel9395-9402
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, in Section 5, we demonstrate the effectiveness of our proposed algorithm on simulated and real-world problem instances, and compare the performance of the OLFW algorithm with several baseline algorithms. We conduct numerical experiments, over simulated and real-world datasets in the following. Joke Recommendation |
| Researcher Affiliation | Academia | Prasanna Raut 1, Omid Sadeghi 2, Maryam Fazel 2 1Department of Mechanical Engineering, University of Washington 2 Department of Electrical and Computer Engineering, University of Washington {raut, omids, mfazel}@uw.edu |
| Pseudocode | Yes | Algorithm 1 Online Lagrangian Frank-Wolfe (OLFW) |
| Open Source Code | No | The paper does not provide an unambiguous statement or link for the open-sourcing of the code for the methodology described. |
| Open Datasets | Yes | Joke Recommendation We look at the problem of DRsubmodular function maximization over the Jester dataset1. 1http://eigentaste.berkeley.edu/dataset/ |
| Dataset Splits | No | The paper mentions using the Jester dataset but does not provide specific details on training, validation, and test splits (e.g., percentages or sample counts). |
| Hardware Specification | No | The paper does not provide specific hardware details (exact GPU/CPU models, processor types, or memory amounts) used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details, such as library names with version numbers, needed to replicate the experiment. |
| Experiment Setup | Yes | We choose X = {x R2 : 0 x 1} and for each t [T], we generate quadratic functions of the form ft(x) = 1 2x T Htx + h T t x where Ht R2 2 is a random matrix whose entries are chosen uniformly from [ 1, 0]. We let ht = HT t 1 to ensure the monotonocity of the objective. We let T = 1000. At each round, we randomly generate linear budget functions whose entries are chosen uniformly from [0.5, 2.5] and the mean vector is p = [1, 2]T . Also, we set the total budget to be BT = 2T. We vary δ, the parameter of the penalty function, in the range [0.1, 1000] and plot the trade-off curve i.e., P1000 t=1 ft(xt) versus BT P1000 t=1 p, xt for 100 chosen values of δ in Figure 2. In this example, our choice of δ in the OLFW algorithm, highlighted in the plot, achieves the highest possible cumulative utility while satisfying the total budget constraint. We run the OLFW algorithm for different choices of the step size µ and plot the cumulative utility and the total budget violation in Figure 3. Our OLFW algorithm chooses µ such that the overall utility and cumulative budget consumption are balanced. |