Anticipating the Moving Minimizer on Tensor-Train Manifolds

Many streaming data problems, such as air-quality sensor grids, traffic counts and user–item–time interactions, ask a model to keep a compressed multiway summary of data that keeps changing. The target is no longer a fixed answer but a moving one. Existing streaming tensor methods chase it reactively: when new data arrives, they take gradient steps toward where the best fit currently sits. Optimization theory for time-varying problems shows why this is a mistake. A method that only corrects toward the current optimum always trails it by an amount proportional to the time between updates. Methods that also predict where the optimum is heading shrink that lag to the square of the step. That result, however, has only been proven in flat vector spaces for convex problems. The compressed formats that make high-order tensors tractable are curved and non-convex, and no one has carried the prediction step over to them.

We propose to build that prediction step for the tensor train, a chain-of-small-cores format whose storage grows linearly rather than exponentially with the number of modes. At each update the method solves a small linear system in the space of allowed local changes of the current low-rank tensor, using the curvature of the current data. This estimates the velocity of the moving optimum. The method moves along that velocity and then applies one ordinary correction step. The central bet is narrow and falsifiable. A simpler alternative extrapolates the method's own previous displacement. Our prediction should beat it exactly when the drift changes direction, because it reads the new direction from fresh data rather than from memory. It should also cut tracking error from first order to second order in the sampling interval on high-order tensors that Tucker-style methods cannot hold.

Core Claim

Prediction–correction tracking, the scheme in Prediction-correction methods for time-varying convex optimization, keeps the optimality condition satisfied along time. The prediction uses the mixed time–space derivative of the objective, and a gradient or Newton correction follows. That paper proves $O(h^2)$ tracking error for the gradient variant and $O(h^4)$ for the Newton variant, against $O(h)$ for plain running gradient descent, where $h$ is the sampling interval. It also reports about $10^{-5}$ versus $10^{-2}$ worst-case error on scalar tracking. Its proofs need Euclidean space, strong convexity, and an explicit Hessian inverse.

We claim the same scheme can be run on the fixed-rank tensor-train manifold. The manifold is the set of tensors with given tensor-train ranks. Its tangent space is the set of first-order changes that keep those ranks, and it has dimension $O(D n r^2)$ for order $D$, mode size $n$ and rank $r$. Let $X_k$ be the current estimate at time $t_k$, $f(X,t)$ the time-varying loss, $\mathrm{grad}$ and $\mathrm{Hess}$ the Riemannian gradient and Hessian restricted to that tangent space, and $P_{T_X}$ the projection onto the tangent space. The prediction velocity $v_k$ then solves

$$ \mathrm{Hess}\, f(X_k,t_k)[v_k] \;=\; -\,P_{T_{X_k}}\!\big(\partial_t \nabla f(X_k,t_k)\big), \qquad \hat X_{k+1} \;=\; \mathcal{R}_{X_k}(h\, v_k), $$

where $\mathcal{R}$ is the retraction back onto the manifold, implemented as tensor-train rounding. A Riemannian gradient step on $f(\cdot, t_{k+1})$ follows as the correction.

The time derivative $\partial_t \nabla f$ is estimated as a finite difference of gradients at the same point $X_k$ across two consecutive data windows, in the spirit of the approximate variants in the prediction–correction paper. It therefore uses current data rather than past iterates. The system is solved with a few conjugate-gradient iterations using Hessian–vector products, so the cost is a small multiple of one gradient, and no dense Hessian is ever formed. This directly addresses the "cost of inversion" limitation noted for Newton tracking.

The expected result is that tracking error scales as $h^2$ times a constant that grows with the inverse of the smallest tensor-train singular value. The $h^2$ comes from cancelling the first-order Taylor term of the optimum's motion. The singular-value dependence comes from the manifold's curvature, which is large near rank-deficient points. We treat this as a hypothesis to test, under local strong convexity along the trajectory. We do not claim it as a result.

Research Program

Method pieces. The method reuses existing parts. The static convergence analysis and the tangent-space machinery come from Provable Tensor-Train Format Tensor Completion by Riemannian Optimization. That paper shows Riemannian gradient descent on this manifold converges linearly for a fixed batch of observed entries, with a contraction factor of at most 0.975 independent of condition number. It has no notion of drift, and we add one.

For rank changes we borrow augment-then-truncate rank adaptivity from A Parallel Basis Update and Galerkin Integrator for Tree Tensor Networks. That integrator evolves tree tensor networks under a known differential equation, updates all nodes in parallel, and stays robust to small singular values. It is only first-order accurate in $h$, and it integrates a given vector field rather than tracking a minimizer. Our prediction step is aimed at both gaps.

Analysis. We will prove, or fail to prove, a local tracking bound for the predicted scheme. The approach is to reduce the manifold problem to Euclidean prediction–correction in local coordinates. The curvature term of the Riemannian Hessian and the retraction error enter as perturbations of order $h^2/\sigma_{\min}$, where $\sigma_{\min}$ is the smallest tensor-train singular value.

Losses. The main setting is least-squares streaming completion with an exponentially discounted observation window. A secondary setting uses Poisson loss for count streams, following the generalized losses of Streaming Generalized Canonical Polyadic Tensor Decompositions.

Test environments. Three environments are used. The first is a synthetic generator of order-$D$ tensor-train targets for $D$ from 4 to 12. Their cores move along smooth trajectories with controllable speed, planted direction reversals and a controllable $\sigma_{\min}$, observed at a 10% entry rate. It borrows the drifting-target and planted-reversal logic of the drifting-quadratic setting in On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization, carried over to tensors. The second is the Beijing Air Quality streams used by Online Functional Tensor Decomposition via Continual Learning for Streaming Data Completion and Streaming Factor Trajectory Learning for Temporal Tensor Decomposition. For higher order, time-of-day and day are split into separate modes. The third is the synthetic concept-drift streams SDS1–SDS6 from Identifying and Alleviating Concept Drift in Streaming Tensor Decomposition, which test the rank-adaptive variant.

Baselines

Correction-only baseline. The naive reference point is running Riemannian gradient descent on the tensor-train manifold, the algorithm of the Riemannian completion paper, warm-started from the previous estimate. It is also run with multiple steps per interval, matched to our method's per-step compute. We count one conjugate-gradient iteration as one gradient evaluation and match wall-clock per update. This is the strongest competitor on the core question of whether prediction beats spending the same compute on more correction. No reported result was found on Lacuna for tensor-train tracking error under drift, so both methods are run fresh on the synthetic generator. We beat it if, at equal compute, tracking error has a log–log slope near 2 in $h$ against near 1 for this baseline. We also need lower absolute error for at least moderate $h$.

Key ablation. The ablation that isolates the key ingredient keeps everything identical but replaces the curvature-based velocity with the transported previous displacement, $v_k \approx (X_k - X_{k-1})/h$ moved into the current tangent space. This is constant-velocity extrapolation. It is a form of momentum, and the momentum paper predicts it inherits an inertia window at direction changes. Our method wins if it matches this ablation on smooth drift and shows a clearly smaller and shorter error spike after planted reversals.

Momentum variants. We run Riemannian heavy-ball and Adam at tuned momentum, because streaming tensor methods such as OnlineGCP use Adam. The momentum paper reports heavy-ball tracking error rising from about 0.34 to 401.37 as $\beta$ goes from 0.5 to 0.99 on a drifting quadratic, while vanilla SGD stays near 1.04. We expect the same ordering on tensors, and we tune $\beta$ on the same budget as our step sizes.

Real-data field. The strongest existing method on real data is OFTD from the online functional tensor paper. It fits CP factors as sine-activated coordinate networks with a long-tail replay buffer and reports a normalized reconstruction error of about 0.156 on Beijing Air Quality at 10% observed entries. We also run SFTL from the streaming factor trajectory paper, which gives each factor a Kalman-filtered Gaussian-process trajectory and reports 29–59 seconds on BeijingAir-2 at rank 7 versus about 137 seconds for continuous-time Tucker. OnlineGCP is included as well. All methods use the same stream order, observation mask and held-out entries, with an equal hyperparameter search budget.

Beating OFTD means a normalized reconstruction error below about 0.156 at comparable per-update latency. OFTD reports under 0.2 seconds per single-aspect update. Matching it while using an order-$D$ tensor train would already be informative. On SDS6 the rank-adaptive variant must beat SeekAndDestroy's reported relative error of about 0.208; OnlineCP reported about 0.238.

Why not just…?

Why not just run more correction steps per update? With enough inner iterations, a warm-started correction-only method can drive lag down arbitrarily. This is the most serious threat. The prediction–correction paper shows the lag is structural at fixed per-step work, 10⁻² versus 10⁻⁵ on scalar tracking, but that is Euclidean and convex. The equal-compute comparison and the error-versus-$h$ slope are designed to settle it on tensors. If correction-only matches us at equal compute, the prediction step is not worth its complexity, and we will report that.

Why not just extrapolate the last displacement, or use a Kalman velocity model? Extrapolation is almost free and will likely match our method under smooth drift. Its weakness is that it reads direction from the past, and the momentum paper shows memory-based updates are blind to direction changes for an inertia window that grows with conditioning. SFTL's Kalman prediction is similar: it propagates a fixed linear transition model rather than reading curvature from current data, and it costs cubic time in rank. The reversal experiment is the decisive test between the curvature-based velocity and extrapolation. If extrapolation recovers as fast as our method after reversals, we will drop the Hessian solve.

Why not just re-solve each window from scratch or bin time? The prediction–correction paper argues restarts are too slow for real-time streams and throw away temporal correlation. We include cold-start per-window Riemannian completion as a latency and accuracy reference to show the cost, not as a serious contender.

Why not just stay with CP or Tucker streaming methods? Continuous-time Tucker (Bayesian Continuous-Time Tucker Decomposition) carries a core of size $R^D$, and CP-based streamers such as OFTD and OnlineGCP are validated only at low order. On order-3 Beijing Air data they may simply win, and that is acceptable. The claim concerns the order-8 to order-12 synthetic regime, where these formats either cannot fit in memory or must use tiny ranks.

Decisive Experiments

Rate check. On the synthetic tensor-train stream we plot tracking error $\|X_k - X^*_{t_k}\|_F/\|X^*_{t_k}\|_F$ against $h$ over a decade of sampling intervals, for $D \in \{4, 8, 12\}$. A slope near 2 for the predicted method and near 1 for correction-only confirms the core claim. A slope near 1 for both refutes it.

Reversal check. At planted direction reversals, we measure the peak error and the recovery time for our method, extrapolation, and heavy-ball. We then vary conditioning to see whether the memory-based methods' recovery time grows as the momentum paper predicts, while ours does not.

Curvature check. Sweeping $\sigma_{\min}$ toward zero tests the predicted blow-up of the constant. It also tests whether switching on BUG-style rank augmentation and truncation removes that blow-up.

Real-data check. On Beijing Air, at order 3 and after re-tensorizing to higher order, and on SDS6, we report held-out normalized reconstruction error and per-update latency against the reported OFTD and SeekAndDestroy numbers. All other baselines are re-run under the shared protocol. On the NYC taxi Poisson stream no reported numerical result was found on Lacuna, so all methods there are run fresh.