Parameter-Free Online Learning via Model Selection
Authors: Dylan J. Foster, Satyen Kale, Mehryar Mohri, Karthik Sridharan
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce an efficient algorithmic framework for model selection in online learning, also known as parameter-free online learning. Departing from previous work, which has focused on highly structured function classes such as nested balls in Hilbert space, we propose a generic meta-algorithm framework that achieves online model selection oracle inequalities under minimal structural assumptions. We give the first computationally efficient parameter-free algorithms that work in arbitrary Banach spaces under mild smoothness assumptions; previous results applied only to Hilbert spaces. We further derive new oracle inequalities for matrix classes, non-nested convex sets, and Rd with generic regularizers. Finally, we generalize these results by providing oracle inequalities for arbitrary non-linear classes in the online supervised learning model. These results are all derived through a unified meta-algorithm scheme using a novel multi-scale algorithm for prediction with expert advice based on random playout, which may be of independent interest. |
| Researcher Affiliation | Collaboration | Dylan J. Foster Cornell University Satyen Kale Google Research Mehryar Mohri NYU and Google Research Karthik Sridharan Cornell University |
| Pseudocode | Yes | Algorithm 3 procedure MULTISCALEFTPL(c, ) Scale vector c with ci 1, prior distribution . for time t = 1,...,n: do Draw sign vectors σt+1,...,σn { 1}N each uniformly at random. Compute distribution pt(σt+1 n) = arg min sup gt gt[i] ci σs[i]ci B(i) where B(i) = 5ci i n i . Play it pt. Observe loss vector gt. end for end procedure |
| Open Source Code | No | The paper does not contain any statement about making its source code publicly available or providing a link to a code repository. |
| Open Datasets | No | The paper is theoretical and does not mention the use of any datasets for training or evaluation, nor does it provide access information for any publicly available dataset. |
| Dataset Splits | No | The paper is theoretical and does not describe any dataset splits (training, validation, or test) as it does not involve empirical experiments. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |