Kernel methods compare every data point with every other through a similarity function, so they get expensive as data grows. When the data is a long time series, that similarity has structure at several time scales at once. At coarse scales, where similarity decays slowly, the full similarity matrix is nearly low-rank, meaning a few summary directions describe it and it compresses well. At fine scales, where similarity decays quickly, the matrix becomes nearly block-diagonal: each point resembles only a small group of others. Existing scalable kernel methods find those groups by clustering the inputs, and the resulting groups end up scattered across memory. This proposal argues that, for time series, the groups should instead be formed from the dominant periods of the series: daily, weekly, and so on, found with a single fast Fourier transform. If the series is folded by its main period, windows at the same phase in nearby cycles become the fine-scale blocks. Our hypothesis is that this one choice buys two things. It should approximate the fine-scale similarity at least as well as clustering, and it should place each block's data in adjacent memory, so a solver whose working data exceeds GPU memory can page it in without thrashing.
This matters because histories of 10^9 to 10^10 points (cloud telemetry, sensor streams, long simulations) are exactly where kernel methods could use far more history than a deep forecaster's fixed look-back window. They are also exactly where the solver's state no longer fits on the accelerator. Unified virtual memory, a single address space shared by CPU and GPU in which pages migrate to the GPU on demand, is the natural way to run such a solver. It also fails badly when memory is oversubscribed and accesses are scattered. The data layout, set by the choice of blocks, decides which of these two outcomes we get.
Core Claim
We build a multi-scale kernel ridge regression forecaster. Kernel ridge regression fits a weighted sum of similarities to training points by solving one regularized linear system. Its inputs are lag windows of a multivariate series, and its kernel is a sum of Gaussian kernels with learned length-scales $\ell_1 > \dots > \ell_S$. Each scale is approximated with the structure its length-scale implies:
$$K \approx \sum_{s \in \text{coarse}} C_s W_s^{-1} C_s^{\top} + \sum_{s \in \text{fine}} B_s^{\mathcal{P}}.$$
Here $K$ is the $n \times n$ similarity matrix over $n$ training windows. $C_s$ holds similarities between all windows and $m$ landmark windows at scale $s$, and $W_s$ holds similarities among the landmarks. This is the Nyström approximation. $B_s^{\mathcal{P}}$ is a block-sparse matrix whose blocks are defined by a partition $\mathcal{P}$ of the windows, with links kept only between adjacent blocks. The new element is $\mathcal{P}$. Instead of k-means clusters, the partition groups windows by phase within the dominant period and by nearby cycle index, with periods taken from an FFT of the training series, the same way TimesNet unfolds a series into a period-by-phase grid. Storage then follows the order of $\mathcal{P}$.
The claim has three parts, and each can be tested. First, at fine length-scales, period-folded blocks capture as much kernel mass per block as k-means blocks at equal block size, and more than plain contiguous time segments. Second, when the solver's vectors are 1.5 to 3 times larger than GPU memory, a conjugate-gradient solve over this layout runs within a small factor of hand-tiled explicit streaming using only default page migration plus coarse prefetch hints. The time-ordered and k-means-ordered layouts should thrash. Conjugate gradient is the iterative linear solver we use; it touches every block once per iteration. Third, on very long series, forecast error keeps falling as the history grows past the lengths deep multi-scale models can ingest.
Research Program
The approximation side builds on three prior works. Memory Efficient Kernel Approximation (MEKA) showed that shift-invariant kernels move from low-rank to block-diagonal as the scale parameter grows. It exploited this with k-means blocks, local Nyström bases, and link matrices. MEKA motivates our split into coarse and fine structure and supplies the block-plus-link technique. It was built for static data such as covtype and mnist2m, it never considers temporal order or memory placement, and its link storage grows quadratically with the number of clusters. Folding by period restricts links to neighbouring cycles, so link storage grows linearly. The comparative study of Nyström versus random features gives an $O(1/m)$ versus $O(1/\sqrt{m})$ generalization bound under an eigengap. That result supports using Nyström at coarse scales, where the eigengap exists, and not at fine scales, where it does not. Fast kernel methods reaches $O(n \log n)$ exact regression with non-uniform FFTs on up to 10^10 points. It is limited to input dimension $d \le 3$, or to additive models without interactions. Our lag-window inputs have $d$ in the tens to hundreds, so we cannot reuse its solver, though we compare against it on time-index inputs.
The multi-scale side builds on SiGMA. SiGMA learns continuous smoothing scales with a learnable discrete Gaussian and argues that fixed integer downsampling loses forecastability. We borrow that argument to justify learning the $\ell_s$ continuously, by validation-set gradient on a small subsample. SiGMA's operator is a dense $O(L^2)$ matrix acting on one bounded look-back window. Ours spans the entire history, and its fine-scale cost is linear in $n$ times the block size.
Memory is the constraint regime. UVMBench measured an average 34.2% slowdown for naive unified memory relative to manual copies, a residual 0.7% with explicit cudaMemPrefetchAsync, and slowdowns above 100x at 125% oversubscription under least-recently-used eviction. GPUVM showed that operating-system fault handling, not the interconnect, dominates at small pages. Together these tell us that locality and predictability of access, not raw bandwidth, determine whether an out-of-core solver survives. Gelado et al. explain why a shared address space helps here: the block lists and link structure are pointer-rich, and the host can build them in place without serializing them for the GPU.
The computation is matrix-free, and this design decision comes from simple arithmetic. Recomputing one kernel entry costs about $2d$ floating-point operations. Loading it over PCIe costs 4 bytes. With $d \approx 100$ that is roughly 50 operations per byte, far below a modern GPU's ratio of compute to PCIe bandwidth. So we never store Gram blocks. What lives in unified memory is the raw series, the dual coefficients, and the three or four conjugate-gradient vectors of length $n$. At 10^9 to 10^10 windows these total 20 to 200 GB. Each fine-block matrix-vector product reads the entries of these vectors that belong to the block and its linked neighbours. The layout therefore determines whether one iteration reads a few long contiguous page runs or many sparsely used pages. The coarse Nyström terms need only the $m$ landmarks, which stay resident.
We will build this forecaster in CUDA with unified memory. The host constructs the partition and the link lists, and the GPU runs the conjugate-gradient iterations. We will instrument page faults and migrated bytes with NVBit, following UVMBench's methodology. As a correctness check before any time-series work, we will reproduce MEKA's mnist2m operating point with our block code.
Baselines
The naive reference points are a seasonal-naive forecaster (repeat the value one dominant period ago) and in-core multi-scale kernel ridge regression on the longest history that fits in GPU memory. Beating the second is how full-history training justifies itself.
The strongest forecasting competitor is SiGMA. It reports best results in 13 of 16 long-term settings and 11 of 15 M4 short-term cases, training up to 5.3x faster with 3.8x less memory than AMD (SiGMA). We found no reported per-dataset MSE for SiGMA on Electricity or Traffic on Lacuna. We will therefore rerun it, and Pathformer (Pathformer), with the authors' released settings and the same splits, horizons, and GPU-hour budget. Each gets a hyperparameter search budget equal to the one we spend on the length-scales and the regularizer. On standard benchmarks, success means matching SiGMA's MSE within a few percent. On the extreme-length series, it means beating SiGMA's error at the history length where SiGMA's look-back is saturated.
The strongest kernel-approximation competitor is MEKA with k-means blocks, run at identical total memory, rank, and block size, alongside global Nyström and random Fourier features at matched memory. For calibration, MEKA reports test RMSE 0.2313 on mnist2m in 550 s under 500 MB, against over 2700 s and 2 GB for Nyström at similar error (MEKA). On lag-window data we win if period-folded blocks reach lower relative Frobenius error of the kernel approximation, and lower forecast MSE, at equal memory.
The systems baselines share one solver and differ in execution. The first is naive unified memory with time-ordered storage. The second adds explicit prefetch calls. The third is hand-written double-buffered explicit streaming, which we treat as the practical upper bound. The fourth is a fully in-core run on a subsample that fits, used to measure the slowdown per point.
The key ablation holds everything fixed and swaps only the partition: period-folded, contiguous time segments, or k-means. It is measured on both approximation error and page-fault volume. This isolates whether the period prior matters, as opposed to block structure in general.
Why not just…?
Why not just stream explicitly and skip unified memory? This alternative is a real threat. Given a fixed block order, a hand-tiled double buffer may match or beat on-demand paging, and UVMBench's 0.7% prefetch result suggests explicit control removes most of the overhead. We include it as the upper-bound baseline. If it wins by a wide margin, the contribution narrows to the layout, which is still what makes the tiling contiguous in the first place. In that case unified memory's value reduces to programmability for the pointer-rich block lists, and we will report exactly that.
Why not just store the Gram blocks, or recompute everything and keep all data in core? Storing blocks loses on arithmetic intensity, as argued above, so we recompute them. Keeping everything in core works until the solver vectors themselves exceed device memory, around 10^9 windows on a single GPU. The in-core subsample baseline shows where that limit falls, and the scaling runs start beyond it.
Why not just run SiGMA or Pathformer on a truncated window? This may be enough on ETT, Weather, and Electricity, where the histories are short. The accuracy-versus-history-length curve on the long series settles it. If kernel error plateaus at the same history length as the deep models' look-back, the full-history argument fails, and we will say so.
Why not just use MEKA's k-means blocks, global Nyström, or a time-index FFT solver? MEKA itself shows that global Nyström breaks down at fine scales. Random features carry the looser $O(1/\sqrt{m})$ bound. The partition ablation compares k-means directly against period folding on both accuracy and faults. The non-uniform FFT solver from Fast kernel methods handles a kernel on the time index exactly, but it cannot take lag windows with $d > 3$ except as an additive model. We run that additive variant to measure what the interactions between lags are worth.
Proposed Experiments
For forecasting accuracy we use Electricity, Traffic, Weather, and ETTh1/h2/m1/m2 at the standard horizons, reporting MSE and MAE. For long histories we use Pathformer's cloud-cluster dataset with more than 7 million timestamps. For scaling we generate Mackey-Glass series (as used in Scaleformer) and sums of nested periodic components, each at 10^8 to 10^10 points.
The first decisive check is the partition ablation. It plots kernel approximation error against block size for the three partitions at the learned fine length-scales. We will also report how fine-scale kernel mass divides between time-local neighbours and same-phase neighbours in other cycles; this measurement tells us whether folding by period is justified on each dataset.
The second check is out-of-core behaviour at 100%, 150%, 200%, and 300% oversubscription. We report wall-clock time per conjugate-gradient iteration, migrated bytes, and fault counts for each layout and execution mode. Success means the period-folded layout with prefetch hints stays within 1.5x of hand-tiled streaming, while the time-ordered and k-means layouts degrade toward the more-than-100x regime UVMBench describes.
The third check is test MSE as a function of training history length on the long series, compared against SiGMA and Pathformer at their maximum feasible look-back.
The proposal is falsified if either of two things happens. Period folding may fail to beat contiguous segments on kernel mass, which would mean the period prior adds nothing. Or longer history may fail to lower error, which would mean the systems work serves no forecasting need.
References
- Memory Efficient Kernel Approximation
- Nyström Method vs Random Fourier Features: A Theoretical and Empirical Comparison
- Fast kernel methods: Sobolev, physics-informed, and additive models
- Generalizing Multi-Scale Time-Series Modeling with a Single Operator
- UVMBench: A Comprehensive Benchmark Suite for Researching Unified Virtual Memory in GPUs
- GPUVM: GPU-driven Unified Virtual Memory
- An asymmetric distributed shared memory model for heterogeneous parallel systems
- Pathformer: Multi-scale Transformers with Adaptive Pathways for Time Series Forecasting
- Scaleformer: Iterative Multi-scale Refining Transformers for Time Series Forecasting