Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A survey of Algorithms and Analysis for Adaptive Online Learning
Authors: H. Brendan McMahan
JMLR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present tools for the analysis of Follow-The-Regularized-Leader (FTRL), Dual Averaging, and Mirror Descent algorithms when the regularizer (equivalently, proxfunction or learning rate schedule) is chosen adaptively based on the data. Adaptivity can be used to prove regret bounds that hold on every round, and also allows for data-dependent regret bounds as in Ada Grad-style algorithms (e.g., Online Gradient Descent with adaptive per-coordinate learning rates). We present results from a large number of prior works in a unified manner, using a modular and tight analysis that isolates the key arguments in easily re-usable lemmas. This approach strengthens previously known FTRL analysis techniques to produce bounds as tight as those achieved by potential functions or primal-dual analysis. Further, we prove a general and exact equivalence between adaptive Mirror Descent algorithms and a corresponding FTRL update, which allows us to analyze Mirror Descent algorithms in the same framework. The key to bridging the gap between Dual Averaging and Mirror Descent algorithms lies in an analysis of the FTRL-Proximal algorithm family. Our regret bounds are proved in the most general form, holding for arbitrary norms and non-smooth regularizers with time-varying weight. |
| Researcher Affiliation | Industry | H. Brendan Mc Mahan EMAIL Google, Inc. 651 N 34th St Seattle, WA 98103 USA |
| Pseudocode | Yes | Algorithm 1 General Template for Adaptive FTRL Parameters: Scheme for selecting convex rt s.t. x, rt(x) 0 for t = 0, 1, 2, . . . x1 arg minx Rn r0(x) for t = 1, 2, . . . do Observe convex loss function ft : Rn R { } Incur loss ft(xt) Choose incremental convex regularizer rt, possibly based on f1, . . . ft Update xt+1 arg min x Rn s=1 fs(x) + |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code, nor does it provide links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on algorithms and analysis for online convex optimization. It describes problem settings and gives abstract examples (e.g., online logistic regression, linear SVMs) but does not conduct empirical studies using specific datasets, thus no dataset access information is provided. |
| Dataset Splits | No | This paper is theoretical and focuses on algorithms and analysis. It does not conduct experiments on datasets, therefore, it does not specify any dataset splits. |
| Hardware Specification | No | The paper is theoretical and presents algorithms and their analysis; it does not describe any experimental evaluations that would require specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on the algorithms and their analysis. It does not implement or run experiments, thus no specific software dependencies or versions are mentioned. |
| Experiment Setup | No | The paper is theoretical, providing algorithms and their analysis, rather than describing empirical experiments. Although Appendix D includes a "One-Dimensional Example" with parameters like learning rate η and L1 penalty λ, these are theoretical parameters for an illustrative scenario, not details of an actual experimental setup or hyperparameters used in an empirical evaluation. |