  The well-established practice of time series analysis involves estimating
deterministic, non-stationary trend and seasonality components followed by
learning the residual stochastic, stationary components. Recently, it has been
shown that one can learn the deterministic non-stationary components accurately
using multivariate Singular Spectrum Analysis (mSSA) in the absence of a
correlated stationary component; meanwhile, in the absence of deterministic
non-stationary components, the Autoregressive (AR) stationary component can
also be learnt readily, e.g. via Ordinary Least Squares (OLS). However, a
theoretical underpinning of multi-stage learning algorithms involving both
deterministic and stationary components has been absent in the literature
despite its pervasiveness. We resolve this open question by establishing
desirable theoretical guarantees for a natural two-stage algorithm, where mSSA
is first applied to estimate the non-stationary components despite the presence
of a correlated stationary AR component, which is subsequently learned from the
residual time series. We provide a finite-sample forecasting consistency bound
for the proposed algorithm, SAMoSSA, which is data-driven and thus requires
minimal parameter tuning. To establish theoretical guarantees, we overcome
three hurdles: (i) we characterize the spectra of Page matrices of stable AR
processes, thus extending the analysis of mSSA; (ii) we extend the analysis of
AR process identification in the presence of arbitrary bounded perturbations;
(iii) we characterize the out-of-sample or forecasting error, as opposed to
solely considering model identification. Through representative empirical
studies, we validate the superior performance of SAMoSSA compared to existing
baselines. Notably, SAMoSSA's ability to account for AR noise structure yields
improvements ranging from 5% to 37% across various benchmark datasets.
