# Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2015.

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

- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Covariance-adapting algorithm for semi-bandits with application to sparse rewards](https://mlsanity.com/paper/2604.13738/) (2026)
- [Block-Norm Geometries for Online Mirror Descent with Sparse Losses](https://mlsanity.com/paper/2602.13177/) (2026)
- [Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2608.15996/) (2026)

## Abstract (arXiv)

We demonstrate that, in the classical non-stochastic regret minimization problem with d decisions, gains and losses to be respectively maximized or minimized are fundamentally different. Indeed, by considering the additional sparsity assumption (at each stage, at most s decisions incur a nonzero outcome), we derive optimal regret bounds of different orders. Specifically, with gains, we obtain an optimal regret guarantee after T stages of order √Tlog s, so the classical dependency in the dimension is replaced by the sparsity size. With losses, we provide matching upper and lower bounds of order √Tslog(d)/d, which is decreasing in d. Eventually, we also study the bandit setting, and obtain an upper bound of order √Tslog (d/s) when outcomes are losses. This bound is proven to be optimal up to the logarithmic factor √log(d/s).