Projection-Free Online Convex Optimization with Time-Varying Constraints
Authors: Dan Garber, Ben Kretzu
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present an algorithm that, on a sequence of length T and using overall T calls to the LOO, guarantees O(T 3/4) regret w.r.t. the losses and O(T 7/8) constraints violation (ignoring all quantities except for T). We present a more efficient algorithm that does not require the latter optimization oracle but only first-order access to the time-varying constraints, and achieves similar bounds w.r.t. the entire sequence. Importantly, our regret bounds w.r.t. the loss functions f1, . . . , f T , both in the full-information and bandit settings, match up to logarithmic terms the current state-of-the-art bounds (in terms of the horizon T and dimension n) for projection-free OCO (i.e., without additional time-varying constraints)... |
| Researcher Affiliation | Academia | 1Technion Israel Institute of Technology, Haifa, Israel. Correspondence to: Ben Kretzu <benkretzu@campus.technion.ac.il>, Dan Garber <dangar@technion.ac.il>. |
| Pseudocode | Yes | Algorithm 1 Approximately-Feasible Projection Oracle via a Linear Optimization Oracle (see (Garber & Kretzu, 2023)) and Algorithm 2 Separating Hyperplane via Frank-Wolfe and Algorithm 3 LOO-based Drift-plus-Penalty Method and Algorithm 4 LOO-based Primal-Dual Method and Algorithm 5 LOO-based Bandit Primal-Dual Method. |
| Open Source Code | No | The paper does not provide any concrete access information for open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use or reference any specific public datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, thus no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an empirical experimental setup with concrete hyperparameter values or training configurations. |