Parameter-free Regret in High Probability with Heavy Tails
Authors: Jiujia Zhang, Ashok Cutkosky
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present new algorithms for online convex optimization over unbounded domains that obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates. Previous work in unbounded domains considers only in-expectation results for sub-exponential subgradients. Unlike in the bounded domain case, we cannot rely on straight-forward martingale concentration due to exponentially large iterates produced by the algorithm. We develop new regularization techniques to overcome these problems. Overall, with probability at most δ, for all comparators u our algorithm achieves regret O(kuk T 1/p log(1/δ)) for subgradients with bounded pth moments for some p 2 (1, 2]. |
| Researcher Affiliation | Academia | Jiujia Zhang Electrical and Computer Engineering Boston University jiujiaz@bu.edu Ashok Cutkosky Electrical and Computer Engineering Boston University ashok@cutkosky.com |
| Pseudocode | Yes | Algorithm 1 Sub-exponential Noisy Gradients with Optimistic Online Learning; Algorithm 2 Gradient clipping for (σ, G) Heavy tailed gradients; Algorithm 3 Unit Ball Gradient clipping with FTRL; Algorithm 4 Dimension-free Gradient clipping for (σ, G) Heavy-tailed gradients |
| Open Source Code | No | The paper states "Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]" in the checklist section, indicating no code is provided. |
| Open Datasets | No | The paper states "If you ran experiments... [N/A]" in the checklist, meaning it does not involve data or experiments. |
| Dataset Splits | No | The paper states "If you ran experiments... [N/A]" in the checklist, meaning it does not involve data or experiments, hence no dataset splits are provided. |
| Hardware Specification | No | The paper states "If you ran experiments... [N/A]" in the checklist, meaning no hardware was used for experiments. |
| Software Dependencies | No | The paper states "If you ran experiments... [N/A]" in the checklist, meaning no specific software dependencies for experiments are relevant or listed with versions. |
| Experiment Setup | No | The paper states "If you ran experiments... [N/A]" in the checklist, meaning it does not involve experiments, hence no experiment setup details like hyperparameters are provided. |