A Unifying Framework for Online Optimization with Long-Term Constraints
Authors: Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano, Nicola Gatti
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first best-of-both-world type algorithm for this general class of problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown stochastic model, and in the case in which they are selected at each round by an adversary. Our algorithm is the first to provide guarantees in the adversarial setting with respect to the optimal fixed strategy that satisfies the long-term constraints. In particular, it guarantees a ρ/(1 + ρ) fraction of the optimal reward and sublinear regret... If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] (c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A] (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] |
| Researcher Affiliation | Academia | Matteo Castiglioni Politecnico di Milano Andrea Celli Bocconi University Alberto Marchesi Politecnico di Milano Giulia Romano Politecnico di Milano Nicola Gatti Politecnico di Milano DEIB, Politecnico di Milano, {matteo.castiglioni, alberto.marchesi, giulia.romano, nicola.gatti}@polimi.it. Computing Sciences Department, Bocconi University, andrea.celli2@unibocconi.it. |
| Pseudocode | Yes | Algorithm 1 META-ALGORITHM(T, δ, ˆρ) ... Algorithm 2 LAGRANGIANGAME(RP, RD, v) ... Algorithm 3 META-ALGORITHM(T, T0, δ) |
| Open Source Code | No | The paper states 'If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]', indicating no code is provided for experimental results. The paper does not mention releasing open-source code for the described algorithms. |
| Open Datasets | No | The paper does not provide information about publicly available or open datasets for training, as it focuses on theoretical contributions and states '[N/A]' for experimental results and data assets. |
| Dataset Splits | No | The paper is theoretical and does not report empirical experiments, therefore it does not provide details on training, test, or validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and states '[N/A]' for questions regarding compute resources and hardware specifications used for experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies. It mentions types of regret minimizers like OMD or EXP3.P but not with reproducible version details. |
| Experiment Setup | No | The paper is theoretical and does not report empirical experiments, thus it states '[N/A]' for questions regarding training details and experimental setup. |