On the Complexity of Prediction Strategies in Noisy and Changing Environments

In a noisy and dynamic world, it is important to learn from past experiences to predict future events. It is generally believed that in presence of unpredictable change-points this learning process must be adaptive to take into account the relevant past information. We show here that, for most change-point rates (h) and signal-to-noise ratios (S/N), performance of non-adaptive and adaptive strategies is comparable. When h>~0.1, adaptive models do not substantially improve over a constant learning rate delta-rule model. When S/N is very low or very high, the non-adaptive domain extends to lower h. Thus, simple strategies are widely preferable in extreme and opposite noise conditions. Increasing change-point rate beyond ~0.25 further reduces the complexity demands, such that both adaptivity and the memory of past history become largely irrelevant to make effective predictions. We characterize the optimal time scale of past data integration and unveil a phase transition at S/N = 1/Golden Ratio. In the high S/N regime, the time scale decreases with increasing h, whereas in the low S/N regime it shows a non-monotonic dependence on h and diverges at large h. Simple optimal solutions are again found for extreme and opposite (small and large h) conditions.