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

Joon Kwon, Vianney Perchet

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 di…