A Gaussian Process-based Streaming Algorithm for Prediction of Time Series With Regimes and Outliers

• URL: http://arxiv.org/abs/2406.00570v1
• Date: Sat, 1 Jun 2024 22:55:33 GMT
• Title: A Gaussian Process-based Streaming Algorithm for Prediction of Time Series With Regimes and Outliers
• Authors: Daniel Waxman, Petar M. Djurić,
• Abstract summary: Recently proposed INTEL algorithm provides a product of experts approach to online prediction of time series under possible regime switching. We introduce LINTEL, which uses the exact filtering distribution at time $t$ with constant-time updates. We show experimentally that our proposed approach is over five times faster than INTEL under reasonable settings with better quality predictions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online prediction of time series under regime switching is a widely studied problem in the literature, with many celebrated approaches. Using the non-parametric flexibility of Gaussian processes, the recently proposed INTEL algorithm provides a product of experts approach to online prediction of time series under possible regime switching, including the special case of outliers. This is achieved by adaptively combining several candidate models, each reporting their predictive distribution at time $t$. However, the INTEL algorithm uses a finite context window approximation to the predictive distribution, the computation of which scales cubically with the maximum lag, or otherwise scales quartically with exact predictive distributions. We introduce LINTEL, which uses the exact filtering distribution at time $t$ with constant-time updates, making the time complexity of the streaming algorithm optimal. We additionally note that the weighting mechanism of INTEL is better suited to a mixture of experts approach, and propose a fusion policy based on arithmetic averaging for LINTEL. We show experimentally that our proposed approach is over five times faster than INTEL under reasonable settings with better quality predictions.

Related papers

• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  We consider a setting in which $N$ agents aim to speedup a common Approximation problem by acting in parallel and communicating with a central server. To mitigate the effect of delays and stragglers, we propose textttDASA, a Delay-Adaptive algorithm for multi-agent Approximation.
  arXiv  Detail & Related papers  (2024-03-25T22:49:56Z)
• Deep Ensembles Meets Quantile Regression: Uncertainty-aware Imputation for Time Series [49.992908221544624]
  Time series data often exhibit numerous missing values, which is the time series imputation task. Previous deep learning methods have been shown to be effective for time series imputation. We propose a non-generative time series imputation method that produces accurate imputations with inherent uncertainty.
  arXiv  Detail & Related papers  (2023-12-03T05:52:30Z)
• Distributional Hamilton-Jacobi-Bellman Equations for Continuous-Time Reinforcement Learning [39.07307690074323]
  We consider the problem of predicting the distribution of returns obtained by an agent interacting in a continuous-time environment. Accurate return predictions have proven useful for determining optimal policies for risk-sensitive control, state representations, multiagent coordination, and more. We propose a tractable algorithm for approximately solving the distributional HJB based on a JKO scheme, which can be implemented in an online control algorithm.
  arXiv  Detail & Related papers  (2022-05-24T16:33:54Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data [0.0]
  Streaming framework is analogous to solving optimization problems using time-varying mini-batches that arrive sequentially. We provide non-asymptotic convergence rates of various gradient-based algorithms. We show how to accelerate convergence by choosing the learning rate according to the time-varying mini-batches.
  arXiv  Detail & Related papers  (2021-09-15T06:58:23Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Stochastic Online Convex Optimization. Application to probabilistic time series forecasting [0.0]
  We prove algorithms such as online newton steps and a scale-free 10 version of Bernstein online achieve best-known rates in unbounded settings. Our fast-rate regret bounds are any-time valid.
  arXiv  Detail & Related papers  (2021-02-01T09:49:15Z)
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme [3.7565501074323224]
  We present a novel approach for the problem of frequency estimation in data streams that is based on optimization and machine learning. The proposed approach exploits an observed stream prefix to near-optimally hash elements and compress the target frequency distribution. We show that the proposed approach outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90% in terms of its expected magnitude of estimation error.
  arXiv  Detail & Related papers  (2020-07-17T22:15:22Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  We propose a reduced-space formulation with trained Gaussian processes trained on few data points. The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding. In total, we reduce time convergence by orders of orders of the proposed method.
  arXiv  Detail & Related papers  (2020-05-21T20:59:11Z)
• Deep combinatorial optimisation for optimal stopping time problems : application to swing options pricing [0.0]
  A new method for computation control based on neural networks and using randomisation of discrete random variables is proposed and applied to optimal stopping time problems. The proposed algorithm succeeds in pricing high dimensional American and swing options in a reasonable time, which is not possible with classical algorithms.
  arXiv  Detail & Related papers  (2020-01-30T10:39:20Z)

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.