Oracle-Efficient Online Learning for Smoothed Adversaries
Authors: Nika Haghtalab, Yanjun Han, Abhishek Shetty, Kunhe Yang
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the design of computationally efficient online learning algorithms under smoothed analysis. Given access to an offline optimization (ERM) oracle, we give the first computationally efficient online algorithms whose sublinear regret depends only on the pseudo/VC dimension d of the class and the smoothness parameter σ. In particular, we achieve oracle-efficient regret bounds of O(Tdσ 1) for learning real-valued functions and O(Tdσ 1/2) for learning binary-valued functions. |
| Researcher Affiliation | Academia | University of California, Berkeley {nika,yjhan,shetty,kunheyang}@berkeley.edu |
| Pseudocode | Yes | Algorithm 1: Oracle-Efficient Smoothed Online Learning for Real-valued Functions ... Algorithm 2: Smoothed Online Learning based on Poisson Number of Hints |
| Open Source Code | No | The paper does not mention providing open-source code for the methodology described. The 'Check List' section indicates 'N/A' for code provision. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments with specific datasets. Therefore, no information about publicly available or open datasets for training is provided. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments with specific datasets. Therefore, no information about training/test/validation dataset splits is provided. |
| Hardware Specification | No | This paper is theoretical and does not report on empirical experiments, thus no hardware specifications are provided. |
| Software Dependencies | No | This paper is theoretical and does not report on empirical experiments, thus no software dependencies with version numbers are provided. |
| Experiment Setup | No | This paper is theoretical and does not report on empirical experiments, thus no experimental setup details like hyperparameters or training settings are provided. |