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

Which classes can be learned properly in the online model? -- that is, by analgorithm that at each round uses a predictor from the concept class. Whilethere are simple and natural cases where improper learning is necessary, it isnatural to ask how complex must the improper predictors be in such cases. Canone always achieve nearly optimal mistake/regret bounds using "simple"predictors?  In this work, we give a complete characterization of when this is possible,thus settling an open problem which has been studied since the pioneering worksof Angluin (1987) and Littlestone (1988). More precisely, given any conceptclass C and any hypothesis class H, we provide nearly tight bounds (up to a logfactor) on the optimal mistake bounds for online learning C using predictorsfrom H. Our bound yields an exponential improvement over the previously bestknown bound by Chase and Freitag (2020).  As applications, we give constructive proofs showing that (i) in therealizable setting, a near-optimal mistake bound (up to a constant factor) canbe attained by a sparse majority-vote of proper predictors, and (ii) in theagnostic setting, a near-optimal regret bound (up to a log factor) can beattained by a randomized proper algorithm.  A technical ingredient of our proof which may be of independent interest is ageneralization of the celebrated Minimax Theorem (von Neumann, 1928) for binaryzero-sum games. A simple game which fails to satisfy Minimax is "Guess theLarger Number", where each player picks a number and the larger number wins.The payoff matrix is infinite triangular. We show this is the only obstruction:if a game does not contain triangular submatrices of unbounded sizes then theMinimax Theorem holds. This generalizes von Neumann's Minimax Theorem byremoving requirements of finiteness (or compactness), and captures preciselythe games of interest in online learning.

Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games