# Parameter-free Algorithms for the Stochastically Extended Adversarial Model

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 46 references that are in the map.
- First posted on arXiv 6 Oct 2025.

## Builds on (most cited first, 30 of 33)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization](https://mlsanity.com/paper/2112.14368/) (2021)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Bandit Convex Optimization in Non-stationary Environments](https://mlsanity.com/paper/1907.12340/) (2019)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [No-Regret Learning in Time-Varying Zero-Sum Games](https://mlsanity.com/paper/2201.12736/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Prediction with Corrupted Expert Advice](https://mlsanity.com/paper/2002.10286/) (2020)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Accelerated Parameter-Free Stochastic Optimization](https://mlsanity.com/paper/2404.00666/) (2024)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)

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

- [Online Learning with Gradient-Variation Interval Regret](https://mlsanity.com/paper/2606.03831/) (2026)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search](https://mlsanity.com/paper/2606.01325/) (2026)

## Abstract (arXiv)

We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specific parameters, such as the diameter of the domain D and the Lipschitz constant of the loss functions G, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish a comparator-adaptive algorithm for the scenario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of tildeObig(|u|22 + |u|2(√σ21:T + √Sigma21:T)big), where u is the comparator vector and σ21:T and Sigma21:T represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this to the more general setting where both D and G are unknown, attaining the comparator- and Lipschitz-adaptive algorithm. Notably, the regret bound exhibits the same dependence on σ21:T and Sigma21:T, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.