Research map / Learning theory and algorithms / Matrix and tensor methods

Generalized Tensor Decomposition for Understanding Multi-Output Regression under Combinatorial Shifts

NeurIPS 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Tensor network decompositions · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Formalizes multi-output regression under combinatorial distribution shift (CDS), proposes a functional t-SVD (Ft-SVD) theory and a double-stage ERM (ERM-DS) algorithm with excess-risk guarantees, validated only on small synthetic tensor experiments.

Problem

Multi-output regression must generalize to input feature combinations (x,y) that never appear in the training distribution (combinatorial distribution shift), where test samples have zero density under training.

Approach

Extends classical t-SVD to infinite continuous feature domains (Ft-SVD), casts CDS multi-output regression as low-rank tensor completion under MNAR, and uses a two-stage ERM with frequency-component-specific hypothesis classes that exploit per-frequency spectral decay.

Key results

• ERM-DS consistently achieves lower test risk than single-stage ERM across covariate shift intensities kappa in [0.1, 3] on synthetic tensors.
• The performance gap between ERM-DS and single-stage ERM widens as covariate shift intensity kappa increases.
• ERM-DS yields lower test risk than ERM across training-data percentages (50%-90%), including with limited samples.

Measured effects reported in the paper

Limitations

• Experiments are only a synthetic conceptual validation; robustness on real-world data is uncertain.
• Spectral methods may not capture the complexity of real-world data.
• Extension to more than two combinatorial features remains an open problem.

Experimental setup

Datasets: synthetic factor-tensor data Akiyo video frames (illustrative spectral decay figure only)

Benchmarks: synthetic tensor completion under CDS

Metrics: test risk

Baselines: single-stage ERM

Builds on: t-SVD ERM-DS (Simchowitz et al.) Eckart-Young theorem

Closest papers by meaning

• High-Dimensional Tensor Regression With Oracle Properties (ICML 2025 · similarity 0.87)
• Low-Rank Tensor Transitions (LoRT) for Transferable Tensor Regression (ICML 2025 · similarity 0.86)
• Solving Sparse \& High-Dimensional-Output Regression via Compression (NeurIPS 2024 · similarity 0.86)
• Efficient Nonparametric Tensor Decomposition for Binary and Count Data (AAAI 2024 · similarity 0.86)
• A Unified Comparative Study with Generalized Conformity Scores for Multi-Output Conformal Regression (ICML 2025 · similarity 0.86)
• Large-scale Multi-view Tensor Clustering with Implicit Linear Kernels (CVPR 2025 · similarity 0.86)