A Regression Approach to Learning-Augmented Online Algorithms
Authors: Keerti Anand, Rong Ge, Amit Kumar, Debmalya Panigrahi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem, thereby diverging from the use of off-the-shelf regression tools with standard bounds on statistical error. |
| Researcher Affiliation | Academia | Keerti Anand Department of Computer Science Duke University Durham, NC 27705 kanand@cs.duke.edu; Rong Ge Department of Computer Science Duke University Durham, NC 27705 rongge@cs.duke.edu; Amit Kumar Department of Computer Science Indian Institute of Technology Hauz Khas, New Delhi 110016 amitk@cse.iitd.ernet.in; Debmalya Panigrahi Department of Computer Science Duke University Durham, NC 27705 debmalya@cs.duke.edu |
| Pseudocode | Yes | Algorithm 1 DOUBLE; Algorithm 2 PREDICT-AND-DOUBLE; Algorithm 3 A general LEARNTOSEARCH algorithm; Algorithm 4 A LEARNTOSEARCH algorithm with accuracy parameter ϵ; Algorithm 5 Procedure to estimate F |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and discusses learning from 'a set of labeled samples of the form (x, z) from some (unknown to the algorithm) data distribution D' but does not specify or provide access information for any public or open dataset used for empirical training. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with specific datasets, therefore it does not mention training, validation, or test splits. |
| Hardware Specification | No | The paper does not specify any hardware details (like CPU/GPU models, memory, or cloud instances) used for running experiments. |
| Software Dependencies | No | The paper does not mention any specific software dependencies or versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical and discusses a 'hyper-parameter ϵ' within the algorithm design. However, it does not provide details on empirical experimental setup, such as specific hyperparameter values used in actual runs, training configurations, or system-level settings. |