Asymptotically optimal strategies for online prediction with history-dependent experts

DOI10.1007/S00041-021-09815-4MaRDI QIDQ2658736zbMATH OpenOpenAlexFDO

Authors Jeff Calder, Nadejda Drenska

Publication date 24 March 2021

Published in The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.13703

zbMATH Keywords

de Bruijn graphgraph Laplacianpartial differential equationsPoisson equationprediction with expert adviceviscosity solutions

Mathematics Subject Classification ID

PDEs in connection with game theory, economics, social and behavioral sciences (35Q91) Learning and adaptive systems in artificial intelligence (68T05) Portfolio theory (91G10)

Abstract: We establish sharp asymptotically optimal strategies for the problem of online prediction with history dependent experts. The prediction problem is played (in part) over a discrete graph called the $d$ dimensional de Bruijn graph, where $d$ is the number of days of history used by the experts. Previous work [11] established $O(varepsilon)$ optimal strategies for $n=2$ experts and $dleq4$ days of history, while [10] established $O(varepsilo{n}^{1/3})$ optimal strategies for all $ngeq2$ and all $dgeq1$, where the game is played for $N$ steps and $varepsilon=N^{-1/2}$. In this paper, we show that the optimality conditions over the de Bruijn graph correspond to a graph Poisson equation, and we establish $O(varepsilon)$ optimal strategies for all values of $n$ and $d$.

Recommendations

• Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case
• Leading strategies in competitive on-line prediction
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History‐Dependent Experts
• Leading Strategies in Competitive On-Line Prediction
• Finite-time 4-expert prediction problem

Cites work

• A decision-theoretic generalization of on-line learning and an application to boosting
• A deterministic-control-based approach to fully nonlinear parabolic and elliptic equations
• A deterministic‐control‐based approach motion by curvature
• A finite difference approach to the infinity Laplace equation and tug-of-war games
• Absolutely minimal Lipschitz extension of tree-valued mappings
• How to use expert advice
• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• On the asymptotic optimality of the comb strategy for prediction with expert advice
• Prediction with expert advice: a PDE perspective
• Prediction, Learning, and Games
• The limit shape of convex hull peeling
• The obstacle problem for the \(p\)-Laplacian via optimal stopping of tug-of-war games
• The weighted majority algorithm
• Towards optimal algorithms for prediction with expert advice
• Tug-of-War and Infinity Laplace Equation with Vanishing Neumann Boundary Condition
• Tug-of-war and the infinity Laplacian
• Tug-of-war with noise: a game-theoretic view of the \(p\)-Laplacian

Cited in

(10)

• On the asymptotic optimality of the comb strategy for prediction with expert advice
• Online calibrated forecasts: memory efficiency versus universality for learning in games
• Overview of the topical collection: harmonic analysis on combinatorial graphs
• scientific article; zbMATH DE number 7370589 (Why is no real title available?)
• Online Prediction with <scp>History‐Dependent</scp> Experts: The General Case
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History‐Dependent Experts
• Games on deBruijn graphs and cycle means
• Comparison for semi-continuous viscosity solutions for second order PDEs on the Wasserstein space
• Numerical solution of a PDE arising from prediction with expert advice
• Comparison of viscosity solutions for a class of second-order PDEs on the Wasserstein space

Describes a project that uses

Uses Software

• AdaBoost.MH

This page was built for publication: Asymptotically optimal strategies for online prediction with history-dependent experts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658736)