Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm
Authors: Jacob Steinhardt, Percy Liang
ICML 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present an adaptive variant of the exponentiated gradient algorithm. Leveraging the optimistic learning framework of Rakhlin & Sridharan (2012), we obtain regret bounds that in the learning from experts setting depend on the variance and path length of the best expert, improving on results by Hazan & Kale (2008) and Chiang et al. (2012), and resolving an open problem posed by Kale (2012). Our techniques naturally extend to matrix-valued loss functions, where we present an adaptive matrix exponentiated gradient algorithm. To obtain the optimal regret bound in the matrix case, we generalize the Follow-the Regularized-Leader algorithm to vector-valued payoffs, which may be of independent interest. and The main contributions of this paper are: An interpretation of the multiplicative weights update... An improved exponentiated gradient algorithm obtaining best-known variance and path-length bounds... An adaptive matrix exponentiated gradient algorithm attaining similar bounds... A generalization of Follow-the-Regularized-Leader to vector-valued loss functions (Lemma 4.3). |
| Researcher Affiliation | Academia | Jacob Steinhardt JSTEINHARDT@CS.STANFORD.EDU Percy Liang PLIANG@CS.STANFORD.EDU Stanford University, 353 Serra Street, Stanford, CA 94305 USA |
| Pseudocode | Yes | Algorithm 1 Adaptive Optimistic Mirror Descent and Algorithm 2 Adaptive Optimistic Mirror Descent (specialized to corrections) |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |