Online Learning via Sequential Complexities
Authors: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari
JMLR 2015 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider the problem of sequential prediction and provide tools to study the minimax value of the associated game. Classical statistical learning theory provides several useful complexity measures to study learning with i.i.d. data. Our proposed sequential complexities can be seen as extensions of these measures to the sequential setting. The developed theory is shown to yield precise learning guarantees for the problem of sequential prediction. In particular, we show necessary and sufficient conditions for online learnability in the setting of supervised learning. Several examples show the utility of our framework: we can establish learnability without having to exhibit an explicit online learning algorithm. |
| Researcher Affiliation | Academia | Alexander Rakhlin EMAIL Department of Statistics University of Pennsylvania Philadelphia, PA 19104 Karthik Sridharan EMAIL Department of Computer Science Cornell University Ithaca, NY 14853 Ambuj Tewari EMAIL Department of Statistics University of Michigan Ann Arbor, MI 48109 |
| Pseudocode | Yes | Algorithm 1 EWA (E1,E2,..., p1,p2,...) Initialize each w1 i pi for t = 1 to T do Pick randomly an expert i with probability wt i Play ft = ft i Receive xt Update for each i, wt+1 i = wt ie ηft i (xt) i wt ie ηft i (xt) end for |
| Open Source Code | No | The paper primarily presents theoretical results and derivations. It does not mention any specific source code release, repository links, or code availability for the methodologies described within this work. |
| Open Datasets | No | The paper focuses on theoretical aspects of online learning and sequential complexities. It does not conduct experiments with specific datasets, nor does it provide any information on public datasets or their access details. |
| Dataset Splits | No | The paper is theoretical and does not describe any experiments that would require dataset splits. No information on training, validation, or test splits is provided. |
| Hardware Specification | No | The paper is a theoretical work focusing on mathematical frameworks and proofs. It does not include any experimental results, and thus no hardware specifications for running experiments are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any software implementations of its proposed methods. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is purely theoretical, focusing on the mathematical underpinnings of online learning. It does not contain any experimental setup details, hyperparameters, or training configurations. |