# Parameter-Free Online Convex Optimization with Sub-Exponential Noise

arXiv: https://arxiv.org/abs/1902.01500 · HTML: https://mlsanity.com/paper/1902.01500/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Feb 2019.

## Built on by (most cited first, 28 of 28)

- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Mitigating LLM Hallucinations via Conformal Abstention](https://mlsanity.com/paper/2405.01563/) (2024)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Auditing Fairness by Betting](https://mlsanity.com/paper/2305.17570/) (2023)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Off-policy Confidence Sequences](https://mlsanity.com/paper/2102.09540/) (2021)
- [Model-X Sequential Testing for Conditional Independence via Testing by Betting](https://mlsanity.com/paper/2210.00354/) (2022)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Betting](https://mlsanity.com/paper/2305.14916/) (2023)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Implicit Parameter-free Online Learning with Truncated Linear Models](https://mlsanity.com/paper/2203.10327/) (2022)
- [Coin Sampling: Gradient-Based Bayesian Inference without Learning Rates](https://mlsanity.com/paper/2301.11294/) (2023)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Better-than-KL PAC-Bayes Bounds](https://mlsanity.com/paper/2402.09201/) (2024)
- [Generalization Bounds via Conditional f-Information](https://mlsanity.com/paper/2410.22887/) (2024)
- [Parameter-free Gradient Temporal Difference Learning](https://mlsanity.com/paper/2105.04129/) (2021)
- [STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals](https://mlsanity.com/paper/2505.22422/) (2025)
- [Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting](https://mlsanity.com/paper/2202.02406/) (2022)
- [Stochastic Gradient Descent Revisited](https://mlsanity.com/paper/2412.06070/) (2024)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch](https://mlsanity.com/paper/2602.11747/) (2026)
- [From Betting to Empirical Bernstein LIL](https://mlsanity.com/paper/2605.22124/) (2026)
- [Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference](https://mlsanity.com/paper/2605.31239/) (2026)

## Abstract (arXiv)

We consider the problem of unconstrained online convex optimization (OCO) with sub-exponential noise, a strictly more general problem than the standard OCO. In this setting, the learner receives a subgradient of the loss functions corrupted by sub-exponential noise and strives to achieve optimal regret guarantee, without knowledge of the competitor norm, i.e., in a parameter-free way. Recently, Cutkosky and Boahen (COLT 2017) proved that, given unbounded subgradients, it is impossible to guarantee a sublinear regret due to an exponential penalty. This paper shows that it is possible to go around the lower bound by allowing the observed subgradients to be unbounded via stochastic noise. However, the presence of unbounded noise in unconstrained OCO is challenging; existing algorithms do not provide near-optimal regret bounds or fail to have a guarantee. So, we design a novel parameter-free OCO algorithm for Banach space, which we call BANCO, via a reduction to betting on noisy coins. We show that BANCO achieves the optimal regret rate in our problem. Finally, we show the application of our results to obtain a parameter-free locally private stochastic subgradient descent algorithm, and the connection to the law of iterated logarithms.