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

Weakness & Limitations: Lack comparisons with some other benchmark approaches

Re: We appreciate the suggestion. However, we must emphasize that our work is the first, to our knowledge, to address MOR under CDS. Existing tensor decomposition methods are not designed for this specific problem.

Following your suggestion, we have provided preliminary empirical support for our theory in tensor completion under missing not at random (MNAR) settings in comparison with some other benchmark approaches. Experimental results are shown in the PDF file.

In our revision, we will:

• Clarify why direct comparisons may not be appropriate given the novelty of our problem setting.
• Provide discussions on how our method uniquely addresses MOR under CDS compared to existing approaches.
• Where possible, adapt existing methods to our setting and provide limited comparisons.

Q1: Generalization to higher-order tensors

Re: Excellent question! First, our Ft-SVD framework, while designed for 3-order tensors, is not strictly limited to two-dimensional input cases. It is versatile enough to handle multi-dimensional inputs that can be divided into two distinct sets.

Second, extending Ft-SVD to higher-order cases is indeed non-trivial and presents significant challenges. In response to your insightful query, we've developed a preliminary attempt at a higher-order extension of Ft-SVD.

Proposition (Functional higher-order t-SVD, informal).

Let $F: X_1 \times X_2 \times \cdots \times X_N \to \mathbb{R}^K$ be a square-integrable vector-valued function, where $X_i \subset \mathbb{R}^{D_i}$. Then there exist sets of functions $\\{U^n_i\\}_{i=1}^\infty \subset L^2(X_n; \mathbb{R}^K), n = 1,\ldots,N$, and a core function $S: X_1 \times X_2 \times \cdots \times X_N \to \mathbb{R}^K$, satisfying:

$F(x_1,\ldots,x_N) = \sum_{i_1=1}^\infty \cdots \sum_{i_N=1}^\infty S(i_1,\ldots,i_N) \ast_M U^1_{i_1}(x_1) \ast_M \cdots \ast_M U^N_{i_N}(x_N)$

where the convergence is in the $L^2$ sense, and $\ast_M$ denotes the t-product.

• For each $n = 1,\ldots,N$, the set of functions $\\{U^n_i\\}$ satisfies the orthogonality condition: $\int_{X_n} U^n_i(x) \ast_M (U^n_j(x))^{\top} dx = \delta_{ij} M^{-1}(\mathbf{1}_t)$ where $\mathbf{1}_t \in \mathbb{R}^{1 \times 1 \times K}$ is the t-scalar with all entries equal to 1, and $M$ is the linear transform defining the t-product.

• The core function $S$ has the following properties:

  (i) all-orthogonality: for all $1 \leq n \leq N$, and $1 \leq \alpha \neq \beta < \infty$, we have $\int_{X_1} \cdots \int_{X_{n-1}} \int_{X_{n+1}} \cdots \int_{X_N} S(x_1,\ldots,x_{n-1},\alpha,x_{n+1},\ldots,x_N)^{\top} \ast_M S(x_1,\ldots,x_{n-1},\beta,x_{n+1},\ldots,x_N) dx_1\cdots dx_{n-1}dx_{n+1}\cdots dx_N = \mathbf{0}_t.$

  (ii) ordering: for all possible values of $n$, $\\|S_{x_n=1}\\| \geq \\|S_{x_n=2}\\| \geq \cdots$ where $\\|S_{x_n=\alpha}\\|$ is the $L^2$ norm of $S$ with the $n$-th mode fixed at $\alpha$.

The main idea of this preliminary extension is to generalize the two-way decomposition to a multi-way decomposition in the functional setting. This involves decomposing a function of multiple variables into a core function and multiple sets of basis functions, one for each variable, with their interactions governed by a generalized t-product. We invite further discussion on this topic, as developing higher-order extensions of Ft-SVD presents many challenges and opportunities for exploration.

Q2: Comparison with multi-output Gaussian Process regression

Re: The main advantage of our approach over alternatives like multi-output Gaussian Process regression is its specific design for handling CDS in MOR, which is not directly addressed by existing methods. Our framework provides:

• A natural way to handle combinatorial shifts
• Interpretable low-rank representations of the function
• Potential computational advantages in high-dimensional spaces under CDS conditions

We will expand on these points in our revision.

Q3: Rank selection for Ft-SVD

Re: This paper proposes the novel concept and properties of Ft-SVD for the first time, focusing on its theoretical foundations. As such, we haven't yet developed a systematic approach for rank selection. This challenge is particularly complex because rank selection remains a difficult and actively researched problem even for existing (discrete) tensor decomposition frameworks, being considered one of the hot topics in the field. Moreover, the continuous nature of Ft-SVD adds an additional layer of complexity to this already challenging issue, making it an even more intricate problem in our context.

In our current work, determining an optimal rank presents significant challenges. The high complexity of MOR under CDS and our limited knowledge of the t-singular values of ground truth embeddings prevent us from providing a closed-form solution of the rank based on minimizing the excess risk bound. Nevertheless, your suggestion about deriving an optimal rank is excellent and opens up a promising avenue for future research.

For general Ft-SVD, we can draw inspiration from rank selection methods for classical matrix or tensor decompositions. We propose the following approaches as potential starting points:

1. Analyzing t-singular value decay and selecting r based on a threshold.
2. Employing cross-validation to choose r that minimizes prediction error on held-out data.
3. Adapting information criteria such as AIC or BIC to the Ft-SVD setting.

While these ideas show promise, they require rigorous development and validation within the Ft-SVD framework. We greatly appreciate your valuable input, as it aligns with our goal of developing a more comprehensive and theoretically grounded approach to Ft-SVD implementation in future work.

Thank you for your thorough and constructive feedback. We address your concerns as follows:

W1 & Q1: Lack of real-data experiments

Re: We acknowledge the importance of real-world data experiments. However, the primary contribution of this paper is theoretical, as we provide the first formal definition and framework for the Combinatorial Distribution Shift (CDS) problem in multi-output regression (MOR). Our research introduces the Ft-SVD theorem and the ERM-DS algorithm, offering new theoretical insights, particularly addressing the unique challenges of MOR under CDS.

Nevertheless, we have provided preliminary empirical support through synthetic and real-world data in Missing Not at Random (MNAR) settings. These results offer initial insights into the application of our Ft-SVD framework for handling MOR tasks. The experimental results are included in the PDF file.

For future work, we plan to:

• Collaborate with domain experts to collect large-scale datasets reflecting CDS characteristics, especially in complex MOR scenarios.
• Design comprehensive experiments to evaluate our method's performance in real CDS scenarios, focusing on MOR.
• Explore the applicability of our theoretical framework across various practical domains, enhancing the robustness and performance of MOR models.

Q2: Missing references and detailed related methods discussion

Re: Thank you for pointing out the missing reference to the Function Tensor-Train (FTT) method [1]. This method presents a continuous analogue of the Tensor-Train decomposition, effectively representing multivariate functions using matrix-valued univariate functions. This approach efficiently captures local features or discontinuities without increasing computational cost.

We will also discuss other related methods, as recommended by Reviewer yp2H, including [Bigoni et al., 2016] (Tensor Train for functional data), [Luo et al., 2023] (Tucker decomposition with neural networks), and [Fang et al., 2024] (Bayesian CP/Tucker decomposition). These will be included in the related work section to provide a comprehensive overview of existing methodologies in functional tensor decomposition.

W3 & Q3: Lack of comparison with other functional tensor decomposition methods, either by theory or experiments

Re: We appreciate the suggestion to compare our work with existing functional tensor decomposition methods, including [1]. However, it is important to note that our study is the first to address the problem of MOR under CDS. Consequently, there are no directly comparable functional tensor decomposition methods available for experimental comparison in this specific context.

1. Function Tensor-Train (FTT) Method [1]: The FTT method efficiently represents multivariate functions, especially those with local features or discontinuities, using matrix-valued univariate functions. This allows for precise approximations without the need for fine discretization.
2. Comparison with Our Proposed Method: Our Ft-SVD method differs significantly from FTT and other existing methods. While FTT focuses on local feature approximation, Ft-SVD specifically addresses MOR under CDS. The Ft-SVD framework extends the t-SVD approach to continuous feature domains, providing novel solutions for the complexities inherent in MOR with CDS.
3. Differences in Theoretical Results (ERM Bounds): We provide explicit error bounds within the ERM framework under CDS, distinguishing our work from existing literature, including [1]. These bounds demonstrate the robustness of the Ft-SVD method in MOR tasks, especially in scenarios involving distribution shifts between training and testing data. Unlike most existing methods that assume consistent distributions between training and testing, our approach specifically addresses the additional challenges posed by distribution inconsistencies in MOR tasks. We analyze the impact of distribution shifts on the generalization ability of MOR models, using a rigorous mathematical framework. We show how model performance is affected by these shifts and propose strategies for model adjustment to minimize errors. Such detailed analysis is rarely covered in existing literature.

Innovation and Contribution: Our study proposes a novel Ft-SVD framework that extends the classical t-SVD, particularly for addressing the challenges of CDS in MOR. This framework provides new theoretical insights and rigorous performance guarantees, establishing a foundational understanding of how to manage distribution shifts in complex MOR scenarios. The theoretical contributions include explicit error bounds and a detailed analysis of the impact of distribution shifts on model generalization, setting our work apart from existing methodologies.

We will include these discussions in the related work section of our manuscript to better highlight the distinctions and advancements offered by our method. We believe these additions will help clarify our research contributions.

Many thanks for the thoughtful and constructive feedback.

W1: Insufficient introduction of CDS in MOR

Re: We acknowledge the need to better define and highlight the importance of Combinatorial Distribution Shift (CDS) in the context of multi-output regression (MOR). CDS occurs when training data covers only a limited subset of possible attribute combinations, while real-world applications often present new, unseen combinations. In MOR, CDS directly challenges model generalization by altering the joint distribution of outputs for unfamiliar input combinations, which traditional methods struggle to handle effectively.

The importance of addressing CDS has not been widely recognized for several reasons. First, many practical applications have not frequently encountered the challenge of new input combinations, leading to a lack of perceived urgency. Second, traditional MOR models often perform well under consistent data distributions, masking their limitations when faced with distribution shifts. Finally, the complexity and high costs of collecting and annotating data for new combinations have limited related research and empirical analysis, resulting in less attention to CDS issues in both academia and industry.

However, as AI technology advances and its application areas expand, CDS issues will become increasingly frequent and critical (potential application scenarios are detailed in Appendix A.1). In this context, our study provides a foundational framework and introduces novel methodologies to meet these evolving demands.

In the revision, we will refine the definition and introduction of CDS, emphasizing its importance in multi-output regression. Specifically, we will clarify how CDS complicates the learning process by causing variations in the joint distribution of outputs, which traditional methods struggle to manage. This will underscore the necessity of developing new approaches to effectively address CDS in MOR.

W2: Excessive detail in definitions and proofs

Re: We will streamline the main text as follows:

• Summarize core contributions and results concisely, avoiding excessive technical details. Key definitions and assumptions will be directly tied to the challenges posed by CDS.
• Move extensive technical explanations to the appendix, keeping the main discussion focused on central issues and contributions.
• Utilize practical examples and visual representations to illustrate the significance of our contributions without overwhelming the reader with complex details.

W3: Inadequate discussion of related work

Re: Thank you for your detailed review and feedback on our paper. We address the points regarding the lack of discussion on [Bigoni et al., 2016], [Luo et al., 2023], and [Fang et al., 2024] as follows.

1. [Bigoni et al., 2016]: This work proposed a functional tensor decomposition method based on classical Tensor Train decomposition, focusing on approximation problems in multidimensional data, especially in high-dimensional continuous spaces. The motivation was to efficiently handle high-dimensional function evaluations by reducing computational complexity through tensor decompositions. Unlike this approach, our research tackles the challenge of multi-output regression under CDS by introducing the Functional t-VSD method. This method extends the classical t-SVD framework to continuous feature domains, offering a novel perspective for solving multi-output regression problems.
2. [Luo et al., 2023]: This study utilizes Tucker decomposition combined with neural networks to model tensor mode functions, aiming to improve data recovery in multidimensional settings. The motivation behind this approach was to leverage the representational power of neural networks alongside tensor decompositions to handle complex data structures. While effective in deterministic settings, this work does not explicitly account for data uncertainty. In contrast, our work extends the t-SVD decomposition into the Ft-SVD framework and introduces the ERM-DS algorithm specifically designed to address the challenges of multi-output regression under CDS, thereby ensuring robust generalization capabilities.
3. [Fang et al., 2024]: This paper developed methods within the CP/Tucker decomposition framework with a Bayesian approach to manage multimodal data. The motivation was to incorporate uncertainty quantification and probabilistic modeling, making it particularly valuable in scenarios requiring robust predictions. However, these methods primarily focus on Bayesian modeling without directly addressing the complexities introduced by CDS. Our work distinguishes itself by introducing the Ft-SVD framework, specifically targeting the challenges posed by CDS in multi-output regression. This approach offers a robust solution for handling continuous feature domains, providing a theoretical foundation for mitigating the impact of distribution shifts.

Innovation and Contribution: Our approach significantly differs from the works of [Bigoni et al., 2016], [Luo et al., 2023], and [Fang et al., 2024] in terms of problem focus, motivation, and methodology. We propose an innovative Ft-SVD theoretical framework to address multi-output regression problems under CDS. By analyzing spectral properties, we design the ERM-DS algorithm, which not only captures the spectral decay characteristics in different sub-domains but also provides theoretical performance guarantees. These contributions fill a gap in the existing literature concerning CDS issues and offer effective tools for representing and analyzing multi-output functions.

We will include these discussions in the related work section of our manuscript and clarify the distinctions and advancements our method provides. We believe these additions will help better understand the context and contributions of our research.

Thanks for the constructive feedback.

W1: Lack of numerical experiments

Re: While our main contribution is theoretical, we've included proof-of-concept experiments on Page 9 in the submission. Additional results, including synthetic and real-world data, are in the attached PDF.

W2: Interesting idea, but not ground-breaking

Re: We appreciate your assessment that our paper presents an interesting idea. We'd like to highlight that all reviewers have recognized the novelty and significance:

• Rev. HXH7 characterized our approach as "rather novel" and praised our "series of solid theoretical analyses."
• Rev. yp2H noted our "clear and reasonable motivation" and "solid theoretical analysis," emphasizing that our method "effectively improves generalization capabilities."
• Rev. juWX described our functional t-SVD as "a decent contribution" with "solid theoretical analysis."

As NeurIPS values high quality, originality, clarity, and significance, we believe our work, while perhaps not "ground-breaking", aligns well with these criteria. Our paper makes fundamental contributions to an important and previously under-explored problem: MOR under CDS:

1. Functional t-SVD: Extending t-SVD to infinite and continuous domains, which Rev. HXH7 noted as "a novel approach when dealing with missing data issues for functional data."
2. First formal treatment of MOR under CDS: Providing a systematic definition and solution, addressing a crucial gap in current ML research.
3. ERM-DS algorithm: Derived from our Ft-SVD framework, offering new generalization bounds that Rev. yp2H described as "impressive" and "contributing significantly to the understanding and validation of the proposed methods."

Our work advances understanding of MOR under CDS and learning under complex distribution shifts. As Rev. yp2H noted, our approach "effectively improves generalization capabilities" for unseen feature combinations. While building on existing concepts, our application to MOR under CDS represents a foundational step forward in addressing this important ML problem. We believe our work lays a foundation for future research, potentially influencing the development of more robust ML models under combinatorial distribution shifts.

W3: Choice of transformation matrix $M$

Re: Thank you for this insightful observation. We would like to clarify our position:

1. Theoretical focus: Our paper primarily establishes a theoretical framework for Ft-SVD and its application to MOR under CDS. Following t-SVD literature conventions e.g. [21], we assume $M$ is given, allowing us to focus on core theoretical contributions.
2. Framework flexibility: While $M$ is assumed given, our framework accommodates various choices, enabling adaptation to different problem structures.
3. Empirical investigation: We've conducted preliminary numerical experiments comparing different $M$ options (DFT, DCT, data-specific). Results are in the attached PDF.
4. Future directions: Optimal $M$ selection opens new research avenues. We propose a potential approach:

A preliminary proposal.

• We seek the best $M$ in the feasible transformation set $\mathcal{M}$ (typically the orthogonal matrix group): $\min_{M \in \mathcal{M}} \Phi(M)$ where $\Phi(M)$ measures the quality of the Ft-SVD under $M$. For example, the reconstruction error $\Phi(M) = \int_{\mathcal{X}} \int_{\mathcal{Y}} \\|F(x,y) - F_k(x,y;M)\\|^2_F dx dy,$ where $F_k(x,y;M)$ is the rank-$k$ Ft-SVD approximation under $M$.

• To capture the interdependence between the transformation and the optimal functional representation, we employ a bilevel optimization approach:

  $\min_{M \in \mathcal{M}} \Phi(M) = \Phi(M, F(M))$ subject to $F(M) = \arg\min_{F \in \mathcal{F}} \Phi(M, F).$

  Here, $F$ represents the functional form of the data, and $\mathcal{F}$ is the space of square-integrable vector-valued functions. To solve this problem, we can use iterative methods such as gradient descent on $\mathcal{M}$.

The initial proposal may lack rigor and requires refinement and validation. It's beyond our current paper's scope, which focuses on establishing fundamental theory. Our work provides a foundation for future research, including optimal $M$ selection. By establishing theoretical groundwork, we enable future studies to investigate these aspects in depth.

Q: Clarity of Thm 4 and its relation to [37]

Re: We apologize for any lack of clarity. Let us address your questions:

Similarity: Both Thm 4 and [37] provide excess risk bounds for learning under CDS, with bounds structured to include approximation and statistical error terms.

Difference: Our results diverge from [37] in:

1. Framework: Introducing Ft-SVD for tensor completion in infinite-dimensional spaces.
2. Scope: Generalizing to multi-output MOR, addressing inter-output dependencies.
3. Characterization: Incorporating spectral decay patterns across frequency components.

Generalizations from [37]: The basic structure of the excess risk bound and the concept of analyzing learning under CDS.

Novel analysis: We introduce key theoretical innovations within our Ft-SVD framework to address MOR under CDS challenges:

1. Spectral analysis theory for Ft-SVD, extending t-SVD to infinite-dimensional spaces.
2. Tensor-based error decomposition for MOR based on Ft-SVD, which uncovers the intricate tensorial structure of MOR under CDS, revealing complexities not captured in matrix approaches [37].
3. Ft-SVD-specific measures of embedding quality, e.g.., generalizing the $\alpha$-conditioning conditions to tensor-structured infinite-dimensional spaces, enabling a more detailed understanding of model behavior under severe distribution shifts in MOR.

Modification: We will revise Thm 4 to highlight connections and differences with [37] more clearly. We'll also expand the related work section to better contextualize our contributions.