2020/07/31 by Nadejda Drenska, Drenska, Nadejda, Jeff Calder +1
Computer Science · Mathematics · #35D40 #49L25 #Analysis of PDEs (math.AP) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #cs.GT #cs.LG #math.AP #math.OC #msc:35D40 #msc:49L25
paper · pdf · doi:10.48550/arxiv.2008.00052
arxiv created 2020/12/29 · arxiv updated 2021/01/01
We study the problem of prediction of binary sequences with expert advice in the online setting, which is a classic example of online machine learning. We interpret the binary sequence as the price history of a stock, and view the predictor as an investor, which converts the problem into a stock prediction problem. In this framework, an investor, who predicts the daily movements of a stock, and an adversarial market, who controls the stock, play against each other over N turns. The investor combines the predictions of n≥ 2 experts in order to make a decision about how much to invest at each turn, and aims to minimize their regret with respect to the best-performing expert at the end of the game. We consider the problem with history-dependent experts, in which each expert uses the previous d days of history of the market in making their predictions. We prove that the value function for this game, rescaled appropriately, converges as N→ ∞ at a rate of O(N-1/6) to the viscosity solution of a nonlinear degenerate elliptic PDE, which can be understood as the Hamilton-Jacobi-Issacs equation for the two-person game. As a result, we are able to deduce asymptotically optimal strategies for the investor. Our results extend those established by the first author and R.V.Kohn [13] for n=2 experts and d≤ 4 days of history. To appear in Communications on Pure and Applied Mathematics.