Adapting to Non-stationarity with Growing Expert Ensembles

When dealing with time series with complex non-stationarities, low retrospective regret on individual realizations is a more appropriate goal than low prospective risk in expectation. Online learning algorithms provide powerful guarantees of this form, and have often been proposed for use with non-stationary processes because of their ability to switch between different forecasters or ``experts''. However, existing methods assume that the set of experts whose forecasts are to be combined are all given at the start, which is not plausible when dealing with a genuinely historical or evolutionary system. We show how to modify the ``fixed shares'' algorithm for tracking the best expert to cope with a steadily growing set of experts, obtained by fitting new models to new data as it becomes available, and obtain regret bounds for the growing ensemble.

• Publication year

  2011

• Venue

  arXiv.org

• Publication date

  2011-03-04

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  arXiv 1103.0949
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

  2012cited by this paper
• Structural Macroeconometrics

  2011cited by this paper
• The Hodrick-Prescott Filter A Special Case of Penalized Spline Smoothing

  2010cited by this paper
• Sequential Anomaly Detection in the Presence of Noise and Limited Feedback

  2009cited by this paper
• Efficient learning algorithms for changing environments

  2009cited by this paper
• Dataset Shift in Machine Learning

  2009cited by this paper
• Extracting certainty from uncertainty: regret bounded by variation in costs

  2008cited by this paper
• Time series analysis and its applications

  2007cited by this paper
• Dynamic Weighted Majority: An Ensemble Method for Drifting Concepts

  2007cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• On the Non-parametric Prediction of Conditionally Stationary Sequences

  2005cited by this paper
• Time Series Analysis and Its Applications (Springer Texts in Statistics)

  2005cited by this paper
• An Ensemble Classifier for Drifting Concepts

  2005cited by this paper
• Using additive expert ensembles to cope with concept drift

  2005cited by this paper
• Online Learning of Non-stationary Sequences

  2003cited by this paper
• A streaming ensemble algorithm (SEA) for large-scale classification

  2001cited by this paper
• Universal Prediction

  1998cited by this paper
• Tracking the Best Expert

  1995influential reference
• UNIVERSAL SCHEMES FOR PREDICTION, GAMBLING AND PORTFOLIO SELECTION'

  1992cited by this paper
• How Sampling Reveals a Process

  1990cited by this paper
• Aggregating strategies

  1990cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Forecasting Non-Stationary Economic Time Series

  1966cited by this paper
• Probability inequalities for sum of bounded random variables

  1963cited by this paper

• Decentralized Funding of Public Goods in Blockchain System: Leveraging Expert Advice

  2024cites this paper
• Funding Public Goods with Expert Advice in Blockchain System

  2022cites this paper
• Learning to safely approve updates to machine learning algorithms

  2021cites this paper
• Contributions à l'apprentissage statistique : estimation de densité, agrégation d'experts et forêts aléatoires. (Contributions to statistical learning : density estimation, expert aggregation and random forests)

  2020cites this paper
• Learning how to approve updates to machine learning algorithms in non-stationary settings

  2020cites this paper
• Mathematics of Statistiscal Sequential Decision Making

  2019cites this paper
• Competitive Analysis for Machine Learning & Data Science

  2019cites this paper
• Mathematics of Statistical Sequential Decision Making. (Mathématique de la prise de décision séquentielle statistique)

  2019cites this paper
• Time-Varying Interaction Estimation Using Ensemble Methods

  2019influential citation
• Efficient tracking of a growing number of experts

  2017influential citation
• Multiple adaptive mechanisms for predictive models on streaming data

  2017cites this paper
• High-Dimensional Inference in Dynamic Environments

  2015cites this paper
• Online Convex Optimization in Dynamic Environments

  2015cites this paper
• DE2: Dynamic ensemble of ensembles for learning nonstationary data

  2015cites this paper
• Machine learning algorithms with applications in finance

  2014cites this paper
• Dynamic Ensemble of Ensembles in Nonstationary Environments

  2013cites this paper
• Investigation of Expert Addition Criteria for Dynamically Changing Online Ensemble Classifiers with Multiple Adaptive Mechanisms

  2013cites this paper
• Concept Drift-Oriented Adaptive and Dynamic Support Vector Machine Ensemble With Time Window in Corporate Financial Risk Prediction

  2013cites this paper
• Online Optimization in Dynamic Environments

  2013cites this paper
• Nonparametric Risk Bounds for Time-Series Forecasting

  2012cites this paper
• Estimating the historical and future probabilities of large terrorist events

  2012cites this paper
• Generalization Error Bounds for Time Series

  2012cites this paper
• Time series forecasting: model evaluation and selection using nonparametric risk bounds

  2012cites this paper
• Adapting to non-stationarity with growing predictor ensembles

  2011influential citation