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

In this paper, we study oracle-efficient algorithms for beyond worst-caseanalysis of online learning. We focus on two settings. First, the smoothedanalysis setting of [RST11,HRS22] where an adversary is constrained togenerating samples from distributions whose density is upper bounded by$1/\sigma$ times the uniform density. Second, the setting of $K$-hinttransductive learning, where the learner is given access to $K$ hints per timestep that are guaranteed to include the true instance. We give the first knownoracle-efficient algorithms for both settings that depend only on the pseudo(or VC) dimension of the class and parameters $\sigma$ and $K$ that capture thepower of the adversary. In particular, we achieve oracle-efficient regretbounds of $ \widetilde{O} ( \sqrt{T d\sigma^{-1}} ) $ and $ \widetilde{O} (\sqrt{T dK} ) $ for learning real-valued functions and $ O ( \sqrt{Td\sigma^{-\frac{1}{2}} } )$ for learning binary-valued functions. For thesmoothed analysis setting, our results give the first oracle-efficientalgorithm for online learning with smoothed adversaries [HRS22]. This contraststhe computational separation between online learning with worst-caseadversaries and offline learning established by [HK16]. Our algorithms alsoachieve improved bounds for worst-case setting with small domains. Inparticular, we give an oracle-efficient algorithm with regret of $O ( \sqrt{T(d|\mathcal{X}|)^{1/2} })$, which is a refinement of the earlier $O (\sqrt{T|\mathcal{X}|})$ bound by [DS16].

Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries