Lune

NeurIPS2024Top-tier venue

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

Andong Wang, Yuning Qiu, Mingyuan Bai, Zhong Jin, Guoxu Zhou, Qibin Zhao

Abstract

In multi-output regression, we identify a previously neglected challenge that arises from the inability of training distribution to cover all combinations of input features, leading to combinatorial distribution shift (CDS). To the best of our knowledge, this is the first work to formally define and address this problem. We tackle it through a novel tensor decomposition perspective, proposing the Functional t-Singular Value Decomposition (Ft-SVD) theorem which extends the classical tensor SVD to infinite and continuous feature domains, providing a natural tool for representing and analyzing multi-output functions. Within the Ft-SVD framework, we formulate the multi-output regression problem under CDS as a low-rank tensor estimation problem under the missing not at random (MNAR) setting, and introduce a series of assumptions about the true functions, training and testing distributions, and spectral properties of the ground-truth embeddings, making the problem more tractable. To address the challenges posed by CDS in multi-output regression, we develop a tailored Double-Stage Empirical Risk Minimization (ERM-DS) algorithm that leverages the spectral properties of the embeddings and uses specific hypothesis classes in each frequency component to better capture the varying spectral decay patterns. We provide rigorous theoretical analyses that establish performance guarantees for the ERM-DS algorithm. This work lays a preliminary theoretical foundation for multi-output regression under CDS.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

6 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Towards a Geometric Understanding of Tensor Learning via the t-Product cites Transforms based Tensor Robust PCA: Corrupted Low-Rank Tensors Recovery via Convex Optimization
  • Towards a Geometric Understanding of Tensor Learning via the t-Product cites Low-Rank Tensor Transitions (LoRT) for Transferable Tensor Regression
  • Towards a Geometric Understanding of Tensor Learning via the t-Product cites Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
  • Non-Convex Tensor Recovery from Local Measurements cites Transforms based Tensor Robust PCA: Corrupted Low-Rank Tensors Recovery via Convex Optimization
  • Non-Convex Tensor Recovery from Local Measurements cites Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
  • Non-Convex Tensor Recovery from Tube-Wise Sensing cites Non-Convex Tensor Recovery from Local Measurements
  • Non-Convex Tensor Recovery from Tube-Wise Sensing cites Transforms based Tensor Robust PCA: Corrupted Low-Rank Tensors Recovery via Convex Optimization
  • Non-Convex Tensor Recovery from Tube-Wise Sensing cites Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks
  • Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural Networks cites Transforms based Tensor Robust PCA: Corrupted Low-Rank Tensors Recovery via Convex Optimization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers6

  1. Towards a Geometric Understanding of Tensor Learning via the t-ProductAndong Wang, Yuning Qiu, Haonan Huang, Zhong Jin et al.NeurIPS 2025 · 3 citations
  2. Non-Convex Tensor Recovery from Tube-Wise SensingTongle Wu, Ying SunNeurIPS 2025 · 1 citation
  3. Non-Convex Tensor Recovery from Local MeasurementsTongle Wu, Ying Sun, Jicong FanAAAI 2025
  4. MTNL: A Unified Modeling Perspective for Enhancing Tensor Network LearningJunhua Zeng, Yuning Qiu, Binghua Li, Chao Li et al.ICML 2026
  5. Low-Rank Tensor Transitions (LoRT) for Transferable Tensor RegressionAndong Wang, Yuning Qiu, Zhong Jin, Guoxu Zhou et al.ICML 2025

Builds on4

  1. Transforms based Tensor Robust PCA: Corrupted Low-Rank Tensors Recovery via Convex OptimizationCanyi LuICCV 2021 · 29 citations
  2. Transformed Low-Rank Parameterization Can Help Robust Generalization for Tensor Neural NetworksAndong Wang, Chao Li, Mingyuan Bai, Zhong Jin et al.NeurIPS 2023 · 12 citations
  3. Functional Bayesian Tucker Decomposition for Continuous-indexed Tensor DataShikai Fang, Xin Yu, Zheng Wang, Shibo Li et al.ICLR 2024 · 8 citations
  4. The optimality of kernel classifiers in Sobolev spaceJianfa Lai, Zhifan Li, Dongming Huang, Qian LinICLR 2024 · 1 citation

Related papers

  1. Nonlinear System Identification via Tensor CompletionNikos Kargas, Nicholas D. SidiropoulosAAAI 2020 · 15 citations
  2. T-SVDNet: Exploring High-Order Prototypical Correlations for Multi-Source Domain AdaptationRuihuang Li, Xu Jia, Jianzhong He, Shuaijun Chen et al.ICCV 2021 · 55 citations
  3. Large-scale Multi-view Tensor Clustering with Implicit Linear KernelsJiyuan Liu, Xinwang Liu, Chuankun Li, Xinhang Wan et al.CVPR 2025
  4. High-order Complementarity Induced Fast Multi-View Clustering with Enhanced Tensor Rank MinimizationJintian Ji, Songhe FengACM MM 2023 · 14 citations
  5. Enhanced Tensor Low-Rank and Sparse Representation Recovery for Incomplete Multi-View ClusteringChao Zhang, Huaxiong Li, Wei Lv, Zizheng Huang et al.AAAI 2023 · 83 citations
Dusk over the sea between two cliffs drawn in fine vertical lines