Online Prediction With History-Dependent Experts: The General Case

• URL: http://arxiv.org/abs/2008.00052v2
• Date: Tue, 29 Dec 2020 21:49:27 GMT
• Title: Online Prediction With History-Dependent Experts: The General Case
• Authors: Nadejda Drenska, Jeff Calder
• Abstract summary: 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 the investor, which converts the problem into a stock prediction problem.
• Score: 1.52292571922932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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\geq 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\to \infty$ 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\leq 4$ days of history. To appear in Communications on Pure and Applied Mathematics.

Related papers

• Mind the Gap: A Causal Perspective on Bias Amplification in Prediction & Decision-Making [58.06306331390586]
  We introduce the notion of a margin complement, which measures how much a prediction score $S$ changes due to a thresholding operation. We show that under suitable causal assumptions, the influences of $X$ on the prediction score $S$ are equal to the influences of $X$ on the true outcome $Y$.
  arXiv  Detail & Related papers  (2024-05-24T11:22:19Z)
• Diffusion Variational Autoencoder for Tackling Stochasticity in Multi-Step Regression Stock Price Prediction [54.21695754082441]
  Multi-step stock price prediction over a long-term horizon is crucial for forecasting its volatility. Current solutions to multi-step stock price prediction are mostly designed for single-step, classification-based predictions. We combine a deep hierarchical variational-autoencoder (VAE) and diffusion probabilistic techniques to do seq2seq stock prediction. Our model is shown to outperform state-of-the-art solutions in terms of its prediction accuracy and variance.
  arXiv  Detail & Related papers  (2023-08-18T16:21:15Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times) The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set. We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
  arXiv  Detail & Related papers  (2023-03-03T04:39:53Z)
• A Regret-Variance Trade-Off in Online Learning [14.41667013062914]
  We show how variance of predictions can be exploited in learning. In online prediction with corrupted losses, we show that the effect of corruption on the regret can be compensated by a large variance. We extend our results to the setting of online linear regression.
  arXiv  Detail & Related papers  (2022-06-06T14:50:19Z)
• A Word is Worth A Thousand Dollars: Adversarial Attack on Tweets Fools Stock Prediction [100.9772316028191]
  In this paper, we experiment with a variety of adversarial attack configurations to fool three stock prediction victim models. Our results show that the proposed attack method can achieve consistent success rates and cause significant monetary loss in trading simulation.
  arXiv  Detail & Related papers  (2022-05-01T05:12:22Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  Online learning with expert advice is a fundamental problem of sequential prediction. The goal is to process predictions, and make a prediction with the minimum cost. An algorithm is judged by how well it does compared to the best expert in the set.
  arXiv  Detail & Related papers  (2022-04-21T01:22:18Z)
• Online Search With Best-Price and Query-Based Predictions [2.3204178451683264]
  We study learning-augmented algorithms in which there is a potentially erroneous prediction concerning the input. We provide experimental results on data obtained from stock exchange markets.
  arXiv  Detail & Related papers  (2021-12-02T20:18:37Z)
• Stock price prediction using BERT and GAN [0.0]
  This paper proposes an ensemble of state-of-the-art methods for predicting stock prices. It uses a version of BERT, which is a pre-trained transformer model by Google for Natural Language Processing (NLP) After, a Generative Adversarial Network (GAN) predicts the stock price for Apple Inc using the technical indicators, stock indexes of various countries, some commodities, and historical prices along with the sentiment scores.
  arXiv  Detail & Related papers  (2021-07-18T18:31:43Z)
• Asymptotically optimal strategies for online prediction with history-dependent experts [1.52292571922932]
  We establish sharpally optimal strategies for the problem of online prediction with history dependent experts. We show that the optimality conditions over the de Bruijn graph correspond to a graph Poisson equation.
  arXiv  Detail & Related papers  (2020-08-31T16:00:42Z)
• A PDE Approach to the Prediction of a Binary Sequence with Advice from Two History-Dependent Experts [0.6091702876917281]
  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. We consider the case when there are two history-dependent experts, whose predictions are determined by the d most recent stock moves.
  arXiv  Detail & Related papers  (2020-07-24T18:46:28Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  We consider a prediction problem with two experts and a forecaster. We assume that one of the experts is honest and makes correct prediction with probability $mu$ at each round. The other one is malicious, who knows true outcomes at each round and makes predictions in order to maximize the loss of the forecaster.
  arXiv  Detail & Related papers  (2020-03-18T20:12:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.