Optimal anytime regret with two experts

DOI10.4171/MSL/38MaRDI QIDQ6062702zbMATH OpenOpenAlexFDO

Authors Nicholas J. A. Harvey, Christopher Liaw, Edwin Perkins, Sikander Randhawa

Publication date 6 November 2023

Published in Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

online learningprediction with expert advice

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) General considerations in statistical decision theory (62C05) Computational learning theory (68Q32)

Abstract: We consider the classical problem of prediction with expert advice. In the fixed-time setting, where the time horizon is known in advance, algorithms that achieve the optimal regret are known when there are two, three, or four experts or when the number of experts is large. Much less is known about the problem in the anytime setting, where the time horizon is not known in advance. No minimax optimal algorithm was previously known in the anytime setting, regardless of the number of experts. Even for the case of two experts, Luo and Schapire have left open the problem of determining the optimal algorithm. We design the first minimax optimal algorithm for minimizing regret in the anytime setting. We consider the case of two experts, and prove that the optimal regret is $gammasqrtt/2$ at all time steps $t$, where $gamma$ is a natural constant that arose 35 years ago in studying fundamental properties of Brownian motion. The algorithm is designed by considering a continuous analogue of the regret problem, which is solved using ideas from stochastic calculus.

Cites work

• A conditioned limit theorem for random walk and Brownian local time on square root boundaries
• A First Passage Problem for the Wiener Process
• A random walk analogue of Lévy’s Theorem
• Analysis of two gradient-based algorithms for on-line regression
• Brownian motion hitting probabilities for general two-sided square-root boundaries
• Finite-time 4-expert prediction problem
• Game theory, alive
• How to use expert advice
• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 3875656 (Why is no real title available?)
• scientific article; zbMATH DE number 5016447 (Why is no real title available?)
• scientific article; zbMATH DE number 53676 (Why is no real title available?)
• scientific article; zbMATH DE number 635670 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1515832 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3327773 (Why is no real title available?)
• scientific article; zbMATH DE number 3381619 (Why is no real title available?)
• Ito's formula for a random walk
• Minimax option pricing meets Black-Scholes in the limit
• On a Property of Real Plane Curves of Even Degree
• On the \(L^p\) norms of stochastic integrals and other martingales
• On the asymptotic optimality of the comb strategy for prediction with expert advice
• On the Hausdorff dimension of the Brownian slow points
• Online learning and online convex optimization
• Online trading algorithms and robust option pricing
• Optimal learning and experimentation in bandit problems.
• Prediction with expert advice: a PDE perspective
• Prediction, Learning, and Games
• Primal-dual subgradient methods for convex problems
• Probability
• Probability and random processes.
• Probability theory. A comprehensive course.
• Probability with Martingales
• The multiplicative weights update method: a meta-algorithm and applications
• The weighted majority algorithm
• Tight lower bounds for multiplicative weights algorithmic families
• Towards optimal algorithms for prediction with expert advice

Cited in

(1)

• Improving adaptive online learning using refined discretization

This page was built for publication: Optimal anytime regret with two experts

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