  We propose a three-stage framework for forecasting high-dimensional
time-series data. Our method first estimates parameters for each univariate
time series. Next, we use these parameters to cluster the time series. These
clusters can be viewed as multivariate time series, for which we then compute
parameters. The forecasted values of a single time series can depend on the
history of other time series in the same cluster, accounting for intra-cluster
similarity while minimizing potential noise in predictions by ignoring
inter-cluster effects. Our framework -- which we refer to as
"cluster-and-conquer" -- is highly general, allowing for any time-series
forecasting and clustering method to be used in each step. It is
computationally efficient and embarrassingly parallel. We motivate our
framework with a theoretical analysis in an idealized mixed linear regression
setting, where we provide guarantees on the quality of the estimates. We
accompany these guarantees with experimental results that demonstrate the
advantages of our framework: when instantiated with simple linear
autoregressive models, we are able to achieve state-of-the-art results on
several benchmark datasets, sometimes outperforming deep-learning-based
approaches.
