TY - JOUR
T1 - A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts
AU - Drenska, Nadejda
AU - Kohn, Robert V.
N1 - Publisher Copyright:
© 2022 Wiley Periodicals LLC.
PY - 2023/4
Y1 - 2023/4
N2 - The prediction of a binary sequence is a classic example of online machine learning. We like to call it the “stock prediction problem,” viewing the sequence as the price history of a stock that goes up or down one unit at each time step. In this problem, an investor has access to the predictions of two or more “experts,” and strives to minimize her final-time regret with respect to the best-performing expert. Probability plays no role; rather, the market is assumed to be adversarial. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves. Focusing on an appropriate continuum limit and using methods from optimal control, graph theory, and partial differential equations, we discuss strategies for the investor and the adversarial market, and we determine associated upper and lower bounds for the investor's final-time regret. When d ≤ 4 our upper and lower bounds coalesce, so the proposed strategies are asymptotically optimal. Compared to other recent applications of partial differential equations to prediction, ours has a new element: there are two timescales, since the recent history changes at every step whereas regret accumulates more slowly.
AB - The prediction of a binary sequence is a classic example of online machine learning. We like to call it the “stock prediction problem,” viewing the sequence as the price history of a stock that goes up or down one unit at each time step. In this problem, an investor has access to the predictions of two or more “experts,” and strives to minimize her final-time regret with respect to the best-performing expert. Probability plays no role; rather, the market is assumed to be adversarial. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves. Focusing on an appropriate continuum limit and using methods from optimal control, graph theory, and partial differential equations, we discuss strategies for the investor and the adversarial market, and we determine associated upper and lower bounds for the investor's final-time regret. When d ≤ 4 our upper and lower bounds coalesce, so the proposed strategies are asymptotically optimal. Compared to other recent applications of partial differential equations to prediction, ours has a new element: there are two timescales, since the recent history changes at every step whereas regret accumulates more slowly.
UR - http://www.scopus.com/inward/record.url?scp=85131234129&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85131234129&partnerID=8YFLogxK
U2 - 10.1002/cpa.22071
DO - 10.1002/cpa.22071
M3 - Article
AN - SCOPUS:85131234129
SN - 0010-3640
VL - 76
SP - 843
EP - 897
JO - Communications on Pure and Applied Mathematics
JF - Communications on Pure and Applied Mathematics
IS - 4
ER -