# Efficient online algorithms for fast-rate regret bounds under sparsity

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2018.

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

- [CRPS Learning](https://mlsanity.com/paper/2102.00968/) (2021)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Stochastic Online Convex Optimization. Application to probabilistic time series forecasting](https://mlsanity.com/paper/2102.00729/) (2021)
- [Sequential Counterfactual Risk Minimization](https://mlsanity.com/paper/2302.12120/) (2023)
- [Smoothed Bernstein Online Aggregation for Day-Ahead Electricity Demand Forecasting](https://mlsanity.com/paper/2107.06268/) (2021)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Fast Best-in-Class Regret for Contextual Bandits](https://mlsanity.com/paper/2510.15483/) (2025)

## Abstract (arXiv)

We consider the online convex optimization problem. In the setting of arbitrary sequences and finite set of parameters, we establish a new fast-rate quantile regret bound. Then we investigate the optimization into the L1-ball by discretizing the parameter space. Our algorithm is projection free and we propose an efficient solution by restarting the algorithm on adaptive discretization grids. In the adversarial setting, we develop an algorithm that achieves several rates of convergence with different dependencies on the sparsity of the objective. In the i.i.d. setting, we establish new risk bounds that are adaptive to the sparsity of the problem and to the regularity of the risk (ranging from a rate 1 / √ T for general convex risk to 1 /T for strongly convex risk). These results generalize previous works on sparse online learning. They are obtained under a weak assumption on the risk (Lojasiewicz's assumption) that allows multiple optima which is crucial when dealing with degenerate situations.