English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We derive an online learning algorithm with improved regret guarantees for`easy' loss sequences. We consider two types of `easiness': (a) stochastic losssequences and (b) adversarial loss sequences with small effective range of thelosses. While a number of algorithms have been proposed for exploiting smalleffective range in the full information setting, Gerchinovitz and Lattimore[2016] have shown the impossibility of regret scaling with the effective rangeof the losses in the bandit setting. We show that just one additionalobservation per round is sufficient to circumvent the impossibility result. Theproposed Second Order Difference Adjustments (SODA) algorithm requires no priorknowledge of the effective range of the losses, $\varepsilon$, and achieves an$O(\varepsilon \sqrt{KT \ln K}) + \tilde{O}(\varepsilon K \sqrt[4]{T})$expected regret guarantee, where $T$ is the time horizon and $K$ is the numberof actions. The scaling with the effective loss range is achieved undersignificantly weaker assumptions than those made by Cesa-Bianchi and Shamir[2018] in an earlier attempt to circumvent the impossibility result. We alsoprovide a regret lower bound of $\Omega(\varepsilon\sqrt{T K})$, which almostmatches the upper bound. In addition, we show that in the stochastic settingSODA achieves an $O\left(\sum_{a:\Delta_a>0} \frac{K^3\varepsilon^2}{\Delta_a}\right)$ pseudo-regret bound that holds simultaneouslywith the adversarial regret guarantee. In other words, SODA is safe against anunrestricted oblivious adversary and provides improved regret guarantees for atleast two different types of `easiness' simultaneously.

Adaptation to Easy Data in Prediction with Limited Advice