Abstract
We develop a versatile framework for statistical learning in non-stationaryenvironments. In each time period, our approach applies a stability principleto select a look-back window that maximizes the utilization of historical datawhile keeping the cumulative bias within an acceptable range relative to thestochastic error. Our theory and numerical experiments showcase the adaptivityof this approach to unknown non-stationarity. We prove regret bounds that areminimax optimal up to logarithmic factors when the population losses arestrongly convex, or Lipschitz only. At the heart of our analysis lie two novelcomponents: a measure of similarity between functions and a segmentationtechnique for dividing the non-stationary data sequence into quasi-stationarypieces.