Generalized Tensor Decomposition for Understanding Multi-Output Regression under Combinatorial Shifts
Authors: Andong Wang
Yuning Qiu
Mingyuan Bai
Zhong Jin
Guoxu Zhou
Qibin Zhao
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-output regression
tensor singular value decomposition
tensor completion
Primary area: learning_theory
TL;DR: This paper tackles combinatorial distribution shift in multi-output regression using generalized tensor decomposition, Ft-SVD theorem, and a two-stage algorithm that exploits low-rank structure for better prediction under shifts.

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.

Generalized Tensor Decomposition for Understanding Multi-Output Regression under Combinatorial Shifts
Andong Wang RIKEN AIP
Yuning Qiu
Mingyuan Bai RIKEN AIP
RIKEN AIP
andong wangOriken jp
Brrinn.qiuuriken. jP
mingyuan. bai@riken. jp
Zhong Jin
Guoxu Zhou"
China University of Cetroleum-Beiiiiee Karamay ialonginSccupk.com edu. en
Guangdong University of Technology gx. gx.zhou@gdut. edu cn
Qibin Zhao RIKEN AIP
qibin waa...hhhoriiee....
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-SDD) theorem which extends the classical tensor SVD 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 the ground-tre truth embeddings, making the problem more tractable. To address the challenges posed by CDS in a tailored Double- 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 thcoretical foundation for multi-output regression under CDS.
regression, we develop
Introduction
In the realm of Multi-Outpu Regressions (MOR), systems designed to predict multiple related outputs from set of input features, unlike single-output regressions which neglect the relationship between targets. MOR is effective for various scientific problems [55] such river quality prediction [17], natural gas demand forecasting [5] and drug efficacy prediction [30]. In many MOR applications, is interactions among multiple features that the predictions are typically derived from. For example, to predict multiple outcomes such as risk scores and health outcomes of patients, the input features usually include healthcare costs and demographic variables (e.g., race) [40]. Similarly, predictions
Qibin Zhao and Guoxu Zhou the corresponding authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to new climate scenarios such as increased temperature and extreme weather events require new representative concentration pathways [12]. To enhance the generalization capability, often necessary to increase the diversity of training samples. However, in some scenarios, data from specific interactions remain inaccessible, such as risk scores of multiple diseases involving novel combinations of factors including age, physiological indicators, and biochemical markers (see Figure 1). Therefore, unseen feature combinations impose a significant challenge to precise predictions, especially when involving multiple outputs.
To this end, in this paper, we address this issue by reducing it to only a couple of input features. This issue is known as the Combinatorial Distribution Shift (CDS) problem [46]. Under CDS, the training data are i.i.d. sampled from the training distribution Drrain with corresponding label z,, where (z) C X x y are the input feature combinations from the feature domains X' and V and z; = h (Zi,, ys) E RRKK denotes the K outputs determined by the vector-valued ground truth function h² Then the problem reduces to predict the new interactions of input combinations (x, v) sample from Drest, where the probability density or mass of test samples (ar, y) under Dtrain may be zero. Therefore, the goal of the MOR problem becomes: how can generalize to the new feature combinations that have never appeared in the training distribution?
It should be noticed that the MOR community has low awareness of CDS and current methods struggle to ad- dress these challenges. Traditional models dependent on static datasets, fail to capture the variability practical applications, making them ineffective with new data com- binations. This research gap underscores the urgent need for dynamic MOR models that better adapt to the evolving input landscapes seen in real-world deployments.
Temperature
Training
E X
Distribution
?
To address this bottleneck, we formulate the issue as gen- eralized tensor completion problem, arranging the predic- tions into third-order tensor Z(z, ;.:) = h" (2, y) E R= Consequently, the prediction of test data can be intuitively interpreted as vector-valued predictions for Missing Not At Random (MNAR) [38] scenarios in multivariate func- tion (see Eq. (4) for more details). While low-rank tensor decomposition techniques, partieularly tensor Singular Value Decomposition (I-SVD) [27, 26, 61], have proven effective in recovering missing entries for discrete data, adapting these methods to the complex domain of possibly continuous multivariate functions requires a fundamental
Test Distribution
Muttile risk scores A (x) E R
Blood pressure y y
An example of MoR under CDS: prediction of multi-diseas risk scores for novel feature combinations of physiological parameters (e.g.. tempera- ture and blood pressure) that lie outside the training distribution.
Figure 1:
re-establishment of the existing t-SVD framework to address the inherent challenges posed by this transition.
Our contributions. This paper proposes novel tensor decomposition perspective for multi-output regression under CDS. It analyzes spectral properties that enable handling such shifts, and introduces an algorithm with theoretical guarantees to improve prediction accuracy. The key contributions are:
To the best of our knowledge, we are the first to identify and define the problem of multi-output regression under CDS, revealing the challenges that arise when the training distribution fails to cover all combinations of input features.
We propose a theoretical framework of Functional Tensor Singular Value Decomposition (Ft-SVD), which extends the classical t-SVD to infinite and continuous feature domains, providing a natural tool for representing and analyzing multi-output functions.
Under the Ft-SVD framework, formulate the multi-output regression problem under CDS as a low-rank tensor estimation problem under the MNAR setting, and introduce a series of assumptions about the true functions, training and testing distributions, and spectral properties of the embeddings, making the problem more tractable.
We develop a tailored Double-Stage Empirical Risk Minimization (ERM-DS) algorithm that uses specific hypothesis classes in each sub-domain to better capture the spectral decay patterns across different sub-domains, and provide theoretical guarantees for the algorithm's 's performance under CDS.
2

---

Brief related work. Our work is related to the areas of multi-output regression, tensor completion, and learning under distribution shift. Multi-output regression has been studied extensively, with approaches ranging from multi-task learning [13, 6] to shared representation learning [39], linear models [11], kernel methods [2], and neural networks [9]. However, these methods often assume that the training and test data come from the same distribution. Tensor completion has seen advance- ments with various decomposition techniques [24, 50, 41] and methods for handling non-random missing patterns [54, 14], but they do not consider the specific challenges of multi-output regression under CDS, Various types of distribution shifts, such as covariate shift [45], concept drift [19], and domain adaptation [44], have been studied, with recent work addressing distribution shift in multi-output regression by aligning distributions through invariant representations [33]. Recent func- tional tensor decomposition advancements include spectral tensor-train for high- sith-dmmmnsional function evaluations [7], Tucker-neural network for data recovery [37], Bayesian CP/Tucker approach for uncertainty quantification (18), guaranteed functional CP decomposition for functional data analysis [23], and functional Tensor-Train for efficient multivariate function representation [20]. Equivariant disentangled transformation for domain generalization under combination shift was studied through category theory [59]. Simchowitz et al. [46] proposed the ERM-DS framework for robust learning under CDS. Our work extends the ERM-DS framework to multi-output regression by representing vector-valued functions as embeddings in a Hilbert t-module and leveraging tensor algebra to capture interdependencies among multiple outputs.
Notations. We use lowercase boldface, and uppercase boldface letters to denote vectors, e.g., R and matrices, e.g., E Rmxx, respectively. A 3-way tensor of size 1 x 1 x K is also named a r-scalar, denoted by underlined lowercase, e.g., f. a 3-way tensor of size d x 1 X K is called I-vector and denoted by underlined lowercase boldface, e.g., t, whereas 3-way tensor of size m x n x K is also called f-matrix and denoted by underlined uppercase, e.g., T. For any tensor T E R we use ( to denote its i-th frontal slice. For A E IRm*m (A) 2 0 denotes its j-th largest singular value; for symmetric A, (A) denotes its j-th largest eigenvalue.
2 Functional t-Singular Value Decomposition for Multi-output Regression
2.1 A t-SVD Perspective of Multi-output Regression
Consider a simpler case where the feature domains X' and y are finite sets. Here, we can represent
the vector-valued ground truth h' as a tensor Z E R|<*|x(')* where each tube Z(iz:
h" h"(x, y) RR k corresponds to the K outputs for the input feature combination (z. y) indexed by (y). Then, the multi-output regression problem for a new feature combination (x', v') becomes a tensor completion task, where the goal is to estimate the missing tube of Z. at the index (i.)
To tackle general tensor completion problems, the framework of t-SVD [26, 27] offers an ideal tool [35, 32, 58). The motivation behind t-SVD stems from the observation that under certain linear transformations M, tensors may exhibit stronger low-rank characteristics than in their original domain. This enhancement of low-rankness often arises due intrinsic correlations within the data, which these transformations can exploit more effectively. Recent research has focused on using an orthogonal matrix M define the transform M due to its advantageous properties [34, 51], a convention that this paper also adopts?. Given an orthogonal matrix M E R K we define the associated linear transform (-) and its inverse M -1 (-) on any tensor T E R x= as follows:
M M = T X3 M, and M (T) == T X3 M-1
(1)
where X3 denotes the mode-3 tensor- matrix product [25]. In real applications, the choice of the transformation matrix M is often guided by the inherent characteristics of the signal being modeled. Popular choices include the Discrete Cosine Transform (DCT) matrix for smooth and periodic signals [34, 57, 32], the Discrete Wavelet Transform (DWT) matrix for multi-resolution analysis [49], data-dependent transformations that adapt to the dataset's specific characteristics [58], and graph spectral projection matrices for data structured in non-Euclide -uncllide spaces [16]. By selecting a transformation matrix that aligns with the signal properties, t-SVD can more effectively uncover the low-rank structure and enable efficient representation and processing of the data.
"e restrict M to be orthogonal matrix for simplicity of discussions. But our results still hold with simple extensions if necessary for unitary M used in [27].
3

---

Based on the linear transform M, the t-product is specifically defined.
Definition (1-product (25]). The t-product of tensors A E RuxxxX and B RuxkxK under the transform M in Eq. (1) is denoted by A *M B and defined as the tensor C E Bmxxxk such that M(C) = (A) & (B) in the transformed domain, where & denotes the lensor frontal fruntal-slice-wae product (see Definition 4).
This paper also follows the definitions of t-transpose, t-identity tensor, t-orthogonal tensor, and f-diagonal tensor given by [25]. Based on these definitions, the t-SVD is introduced as follows:
Definition 2 (t-SVD, tubal rank [25, 27D. The tensor singular value decomposition (t-SVD) of T T R mmxx K under the transform M in Eq. (1) is given by:
T=U*M
(2)
where U m and V E R are 1-orthogonal tensors, S E R is an f-diagonal tensor, and (.) denotes the 1-transpose. The tubal rank of tensor T is defined as the number of non-zero tubes in S in Eq. (2), i.e.
= Mi: S(i, o 0, S min(m, n}31-
Based on I-SVD, extensive tensor completion models [32, 58, 52] provide robust support for MOR with discrete combinatorial features. However, in many machine learning settings, feature domains X and y are infinite and potentially continuous sets, posing significant challenges to the traditional t-SVD. Here, t-SVD becomes inapplicable due to the potentially non-discrete nature of these domains, necessitating a novel approach to effectively handle infinite and continuous feature domains. This leads consider: how can extend the powerful t-SVD framework to address multi-output regression problems in the context of infinite and continuous feature domains?
2.2 Functional t-Singular Value Decomposition
To address the above challenge, we propose a novel theoretical framework that extends the founda- tional principles of t-SVD for infinite and continuous feature domains. By introducing new theorem, we enable the representation of data and functions defined on these domains while preserving the key properties of t-SVD. This extension allows us to employ t-SVD in a principled way for learning vector-valued functions and tackling related problems, opening new possibilities for applying such methods to a wider range of learning tasks.
Theorem 1 (Functional t-Singular Value Decomposition). Let F X x - R.K be square- integrable vector-valued function with Lipschitz-smooth domains X' C D: and C RD2 Then, there exist sets of functions {6,) LX;; and ( C L2(V; and sequence of r-scalars {g C NK with lim 2, = D, satisfying the functional t-Singular Value Decompo- sition (Ft-SVD):
F(a,y) Σ
* HM HM (v),
where the convergence is in the 2 sense. The functions b and v; are called the left and right singular functions, respectively, and the t-scalars o are called the r-singular values. The orthonor- mality conditions fx d (x) *M 2, (x)dde = 8, and Sy wi w:(y) *M 4 (5(ydd = 8ig M (1)
hold, where 1 E R x is the t-sealar with all entries equal to 1, and dis the Kronecker delta.
The proof is provided in Appendix B.2. The Ft-VV theorem provides a principled conceptual framework for decomposing multivariate function, which maps pairs of inputs from domains X' and y into a vector in R Essentially, this theorem states that such a function can be expressed as an infinite series of products of three components: t-singular functions from X' and y (Φ, and vi.- respectively), and series of t-singular values (a,). This decomposition is analogous to breaking down a complex multivariate relationship into simpler, interpretable modes of variation, where each mode is scaled by its importance, signified by the corresponding I-singular value Z.-
Witt a slight abuse of notation, we define the t-product between two vectors in R by treating them as g xxxxX t-scalars. For the sake of simplicity and clarity, we do not explicitly distinguish between ig and g 1x1xx when the context is clear and there risk of confusion.

---

Unlike t-SVD, which factorizes tensor using a finite number of t-rank-one components, representing the original function exactly using Ft-SVD may require an infinite number of t-rank-one components in Eq. (3). However, in most practical applications, an approximation with finite number of components often desired due to computational constraints and the need for more compact representation. The natural follow-up inquiry is: how can we achieve a finite approximation of the original function using Fr-SVD?
To address this question, we can leverage principles akin to the Eckart-Young theorem for t-SVD [27], which identifies the best low-tubal-rank tensor approximation by minimizing the Frobenius norm error. Building upon these principles, we demonstrate that an optimal rank-r approximation also exists for functions represented using Ft-SVD (see the proof in Appendix B.2.2):
Theorem 2 (r-term truncated Ft-SVD). Let F X x y - R be square-integrable function with the Ft-SVD given by Theorem 1. For any r E N, the r-term truncated Ft-SVD is defined as
(, = (v) + +M +M (1))).
Then, Fa y) is the best r-term appreximation to F(r. y) in the 1,2 sense within Ft-SVD framework. Moreover, the approximation error is given by: [[ y) Fr ( =Eir++ 11
This theorem highlights the optimality of the truncated Ft-SVD in approximating vector-values functions, making it potentially useful tool for function compression, denoising, and other appli- cations involving low-rank approximations of functions. However, the error term, an infinite sum Lizr+1 ||0,112, may still be difficult to bound in the worst case. This raises the question: are there situations where the error terms are well-controlled?
In many practical scenarios, the inherent spatial or temporal correlations within data often lead to significant smoothness in functions, trait crucial for applications in image processing, machine learning, computer vision, climate modeling, and time series analysis, and fluid dynamics [15, 36, 3, 29, 42]. This smoothness property can be leveraged to show that the r-term approximation error of Ft-SVD is indeed well-controlled. The following Theorem 3 shows that if the function components belong Sobolev space ()),,, which captures their smoothness, then the t-singular values of the function decay rapidly. This rapid decay effectively controls the approximation error, keeping it bounded and manageable. The proof can be found in Appendix B.2.3.
Theorem 3 (Spectral decay of smooth functions). Let y C D2 be domain satisfying the strong local Lipschitz condition, and let F: X x x + F (x, y), for all i E [K]. Suppose there exists constunt s >> 0 such that F(f) E LX H ())) for all i E [K]. where (V) denotes the s-order Sobolev space on Y Then, the singular values O; of F satisfy the polynomial decay rate |g,112 2 < 1 B.). Moreover, the optimal approximation
K be a vector-valued function with components
error of the truncated Fi-SVD with rank is upper bounded by +()++1)-- -)) in the L2 sense.
The rapid spectral decay in the Ft-SVD framework, as guaranteed by the Sobolev smoothness assumption on the output functions, has significant implications for the generalization performance of multi-output regression models. By promoting solutions with rapid spectral decay, the Ft-VD framework can effectively constrain the complexity of the learned function, striking a balance between fitting the training data and maintaining simplicity. The significance of the spectral decay property in the Ft-SVD framework becomes even more apparent when considering multi-output regression under CDS. In the next section, we will delve into how the approximate low-rankness of the multi-output ground truth, as implied by the rapid spectral decay, provides a key insight into the generalization under CDS Specifically, we will explore how the spectral decay of the ground truth in the Ft-SVD framework plays crucial role in enabling effective generalization under combinatorial shifts.
3
An Ft-SVD-based Framework For Multi-output Regression under CDS
3.1 Generalized Tensor Completion with MNAR for MOR under CDS
We propose a theoretical framework based on Ft-SVD to formulate the CDS problem in multi-output regression. The key idea is to represent multi-output functions as t-bilinear embeddings in a Hilbert t-Module, generalization of Hilbert spaces for handling vector-valuee functions. We introduce
5

---

a series of assumptions on the ground-truti functions, the training and test distributions, and the spectral properties of the embeddings. These assumptions allow us to characterize the multi-output regression problem under CDS low-rank tensor estimation problem under MNAR settings.
To set the stage, first define the concept of a Hilbert t-Module, which serves the foundation for our t-bilinear representation.
Definition 3 (Hillert t-Module). Let R. be the ring of K K-dimensional real vectors with 1-product. A Hilbert I-Module is a module M over R. equipped with an R-valued inner product (:s MMM which is complete with respect the ty-norm induced by the R-valued inner product."
Intuitively, Hilbert t-Module extends the classical Hilbert space to accommodate vector-valued functions, allowing us to perform inner products and norm calculations in a way that respects the tensor structure. This provides natural framework for representing multi-output functions. With the Hilbert t-Module in place, we can now state our key assumption on the ground -ruth functions:
Assumption 1 (t-Bilinear representation). We have the following assumptions on the ground truth:
(I) There is a Hilbert 1-Module (M, ( M)) and two embeddings f X - M and g' : - M satisfying that ht (x, ( (x), g" (v) is the Bayes optimal predictor on Draain and Drest. i.e., D [2] y) ED... 2. = h" (z, y). Hereafter, we call h (z. y) the ground truth.
(II) We also assume that for some B > O, such that IP Dll S B = 1, and max (supzex (x))l,, supgey (lg((() (v)ll S B.
This assumption postulates that the ground-trin truth functions admit t-bilinear representation in terms of two embeddings in Hilbert t-Module, and the inner product of these embeddings gives the Bayes optimal predictor for both the training and testing distributions. The t-bilinear form is natural extension of the bilinear form in Ref. [46], and it allows us to capture the multi-dimensional structure of the problem. While the t-bilinear representation is expressive, need additional assumptions on the training and test distributions to make the problem tractable under CDS:
Assumption 2 (Coverage of training and test distribution, Assumption 2.2 in Ref. [46]). There exist constants Kigt Kum > 0 and marginal distributions 1x Dx.2 over X, and 1y.1: Dy.2 over D, with product measures Draj := ax @ Dy.j. such that for all (x. E X x V, the following dD:or
Radon-Nikodym derivative conditions hold: (I) Training coverage:
I for (1. E
dDusin
1), (1, 1)}, and (II) Test coverage: Eijecra dDies(z.g)
d'ren (r.y)
Kist-
In words, this assumption requires that the training distribution covers the key feature combinations in D101, Dig2 and D281, while the test distribution is allowed to include unseen combinations in D2g2. The constants Kum Kis quantify the degree of coverage".
While Assumption 2 characterizes the relationship between the training and test distributions, does not directly control the impact of distribution shifts on the model's performance. For this, we introduce a further assumption on the covariate shift:
Assumption 3 (Controlled covariate shifts). There exists Keov 2 1 such that, for any y E M. the following inequalities hold: Ez~Dx IlI [T (z), [l²]] I Kioov EE- II (T (z), (x).)) and
Ey-Dy. (g* (v). v)MMl S Keov E Ey.Dy, (g (v). v).ll (.]
This assumption can be seen as a t-Module variant of Assumption 2.3 in Ref. [46]. It essentially bounds the worst-case impact of covariate shift on the model's ' performance, ensuring that the error on the unseen distribution D202 controlled by the error on the training distribution (up to constant Noow) This is a key ingredient that allows us to provide generalization guarantees under CDS.
Finally, to leverage the spectral structure of the embeddings, we make the following assumptions: Assumption 4 (Polynomial spectral decay). Consider the t-covariances Σ := EDxx [[' * (I') and E := Eppy. lgg * M (g*) T]. We have the following assumptions:
'The ez- fn-norm used here differs from the traditional C*Lalgebra norm in the definition of Hilbert -oodulssss as it does not satisfy the C* C*-equality ||æ||| = || (r. x).M m Despite this difference, we still refer to this structure Hilbert t-Module to emphasize its similarities with Hilbert C* mo-dolless. See Definition 12 for more details.
'We give a prohabilistic version of this assumption in Assumption 6.
A slacked version of Assumption can be found in Assumption 7.

---

(I) Balanced embeddings: The ground truth embeddings f and g" reside in an appropriate basis of M such that Σr- = Zg Eigi we also assume X1 (M ) )6) > holds for all E [K].
(1I) Polynomial spectral decay: Each of the K frequency components ( (0) of the t-covariance Tioı exhibits a polynomial singular value decay pattern, but potentially with different decay rates 7 > 0, i.e., (M(() S Cj- Vjj E N, Ni E [K].
Assumption 5 (Small low-rank approximation error of (r. g") on Prrain). Let P( denote the projection onto the top-k eigenspace of M( ("), which represents the i-th frequency compo- nent (Vi E [K]) of Σien induced by the operator M()) in Eq. (1). Define ApxEm (3) (a, () == (M(L" y)) (
( M(' ( as the error between the ground truth (x.,, y) and the optimal rank-k approximations of the ground truth embeddings (f gg)) over the training data Drrain all rank ks E N in each i-th frequency component. We assume that
EDanan [ApxErT (4) (I, v)1 S Kapx ED lApxEm (I, v)l. Vi [K].
Assumptions 4 and 5 postulate that the ground-truth embeddings have a favorable spectral structure. Specif- ically, they assume that the embed- dings are balanced in an appropriate basis, and their spectrum decays poly- nomially (possibly different rates for different frequency components). Fig. illustrates the varying rates of spectral decay exhibited by the DCT frequency components of the Akiyo video data". This empirical observa- tion serves as a compelling motiva- tion for Assumption 4-III). Assump- tion 5 implies that the training distri- bution Durain is sufficiently represen- tative of the true function h in each frequency component. It guarantees that we find embeddings that well approximate h" the training data, they will also perform well on the ref- erence distribution Diæ1.
loglayj: Singalar Values (Log Scale)
Spectral Decay of DCT Frequency Components
frequency
frequency
3-th frequency
4-th frequency
frequency
Index of Singular Values (usoatt:
Figure 2: An illustration of the varying rates of spectral decay across different frequency components following Discrete Cosine Transform (DCT). For this example, consider discrete tensor T E 240032005 which comprises the initial five frames of the reshaped Akiyo video sequence. This tensor serves as an instance of f in Assumption 4-(II), with the transform M represented by the DCT operation.
Formulating MOR under CDS as generalized tensor completion with MNAR. Based on the assumptions, we can formulate the MOR problem under CDS tensor completion problem under the MNAR setting. Specifically, given the training data { Yr, 2;) +=)= drawn from Dersin we aim to estimate the underlying embeddings I" and g" by solving the following problem:
min M.E.
Σ "
g().))
(4)
where ((.,)) a suitable loss function. Problem (4) can interpreted as a tensor completion problem with MNAR: (1) The t-bilinear form (f" (z), (3)) M encodes the function h (z, y) as (generalized) tensor. (2) The training data only covers subset of the feature combinations due to Assumption
(3) The goal is to estimate the complete tensor from the partially observed tensor entries. By solving Problem (4), we obtain the estimated embeddings f and g. which can be used to make predictions on
a new test point (x, y) via the t-bilinear form ((x), M()))..
3.2 Algorithms for Robust Generalization of Multi-output Regression under CDS
How does ERM-based multi-output regression perform under CDS? A natural approach to training a multi- oulti-output regression model is to fix target rank E N and compute an Empirical Risk
The original video be accessed at http: /ttaeeereeeeeeee/eeeeeeeeeeeeeee asu, edu/yuv/index html.
7

---

Minimizer (ERM) by
Corm 8 Berm
E argmin EEF,. 1L
[((a))) T *M ((Us) z
(S)
where (-) denotes the t-transpose (see Definition 6), and function classes F,,, Gr are given in Assumption 8. Assumption 8 ensures that the function classes Fr and 9, are sufficiently expressive to approximate the true embeddings f and g". while also having controlled complexity in terms of their covering numbers. With the assumption in place, we can obtain the following generalization guarantee for the ERM solution (see the proof in Appendix D.2):
Theorem 4 (Excess Risk Bound for ERM under CDS). Suppose the learned embeddings (eem Serm
a- a-conditioned and (Gmm CD aaccuaate embeddings satisfying" éD) _. /(40r) for all i [K] Then, under Assumptions to 5 and 8, the excess risk of the ERM solution on Drest can be bounded up to constant factor = poly pooyy(Fcovv (Feov: Kust Fun) with probability at least 8:
ar Σ (8210002 (r) r (tail or taita
ar
An
o²
statistical error
approximation errar
where a == max; [a;]. a == min:(87 > O, tail = Ei 22 1, (r, + log 3)/n with N (r, (F(FFe//(2B) 11-11b)) (NG.) c/BB), (llx)) Here, 6 07.00) == oy (M (0) denotes the j-th largest singular value of the i-th frequency component () (9) of the c-variaaeece operator Σigr. and N(F, l. (loo) denotes the covering number of fumction class at scale
Extending the framework of Ref. [46], this theorem bounds the excess risk of the ERM solution for multi-output regression under CDS, incorporating both approximation and statistical errors. Our key contribution, the Ft-SVD for iufinite-dimensionn tensor completion, addresses multi-output MOR while considering spectral decay across frequency components. However, Theorem 4 has two primary limitations: (1) assumes that the learned embeddings are a-conditioned and (Cum: CDi -accurate, which may not be achievable with ERM. (2) The theorem requires that the minimum singular value
o (x)(() is strictly positive for each frequency component E [K]. This condition may not hold for t-embeddings that exhibit varying spectral decay patterns across different frequency components. In practice, multi-output ground truths often demonstrate diverse spectral decay patterns, making it challenging for the hypothesis classes F, and G, capture precise low-rank structures across different frequency components (See Fig. for example).
ERM-DS: Addressing the limitations of single-stage ERM. To address the weaknesses of single- stage ERM, we propose the Double-Stage Empirical Risk Minimization (ERM-DS) algorithm. ERM- DS uses two-stage training process with hypothesis classes tailored to each frequency component, better capturing varying spectral decay patterns and balancing model complexity with generalization ability. Our work extends the ERM-DS framework, originally proposed by Simchowitz et al. for robust learning under CDS [46], to address the challenging setting of multi-output regression. By rep- resenting vector-valued functions embeddings in a Hilbert t-module and employing tensor algebra, we capture the complex interdependencies among multiple outputs, enabling robust generalization.
Unlike Assumption 8, the ERM-DS algorithm considers fine- graineg hypothesis classes satisfying Assumption 9, which defines function classes specifically for each frequency component to better capture the distinct decay behaviors exhibited by the ground truth in each frequency component, This allows ERM-DS to adapt to the varying spectral properties of the true embeddings across different frequency components, leading to improved generalization performance". The ERM-DS algorithm consists of four main steps:
'The a-conditioned embeddings and (Fum: 6D101 Jaccurate embeddings defined in Definition 17 and 200)
Definition 18, respoctively, We require PPig < 8 (r(() /(40r), where e is the i-th element vector 6D
the definition of (Fems <Digg --cccurate embeddings.
Pleasse refer to Appendix D.3 for the details of Assumption 9 and the ERM-DS algorithm.
8

---

1. Overparameterized Training:
Train an overparameterized model (f. g) to approximate the
unknown true predictive functions f" and g* by choosing their frequency components separately via K parallel ERM sub-problems (Eq. (18)).
2. I-Covariance Estimation: Estimate the t-covariances of the embeddings using additional unla- beled examples to capture the important directions of variation (Eq. (19)).
3. Dimension Reduction:
Compute low-rank projections using the estimated covariances and obtain reduced-rank embeddings by projecting the overparameterized embeddings onto the low-rank t-subspace (Eq. (20)).
4. Distillation:
Fine-tune the reduced-rant rank embeddings by approximating their frequency compo- nents separately in the transformed domain, minimizing combination of empirical risk and consistency with the reduced-rank embeddings (Eq. (21)).
The theoretical guarantees for the performance of the ERM-DS algorithm are provided in Theorem 5: Theorem 5 (Excess Risk Bound for ERM-DS under CDS). Under appropriate conditions on algorithm parameters and sample sizes " for any 8 > O, the ERM-DS solution achieves an excess risk bound of (e2 () )) with probability at least 1- 6. Here, d' = poly (Frov, Kig, kwa) is problem-dependent constant, c >> 0 is the desired accuracy level, fri i== are cutoff rank parameters in ERM-DS, and {7 are parameters related to spectral decay in Assumption 4.
1K
The proof is given in Appendix D.3. Theorem 5 provides a generalization error bound for the ERM-
DS algorithm in multi-output regression under CDS. The expected squared error between predicted and true outputs can be bounded by two main terms: the desired accuracy level e², adjustable by algorithm parameters and a term depending on the spectral decay properties of the true embeddings -27
K in each frequency component, represented by Σ (1 + 7 r which captures approximation error due to low-rank structure and target function complexity.
Numerical Experiments. As the first theoretical work the MOR problem under CDS, this paper proposes the novel Ft-SVD theoretical framework, along with related assumptions and algorithm design. The experiments conducted serve solely as a conceptual validation using synthetic data. We consider the settings when X' and y are finite, in which case MOR under CDS naturally degener- ates to tensor completion with MNAR tubes. We construct a ground truth tensor X composed of factor tensors'! !! A, B, Az. Bz, where rAn) C range(A,) and range (B2) C range(B, (B,). The singular values of ( (0, M (B, (() follow a power-law decay oj = --(1////2 while those of M (A, (0) M (B.) are set to of " where Cj E (0, 1) is a uniform random variable, controls the covariate shift, and the transform (-) is chosen as DFT. To simulate CDS, we perform two-stage sampling on X: first, we randomly sample entries with rate stan; second, we sample the top block X1, (A,,B) BB) with a lower rate 1T leaving the bottom block X,2 (A2, BB) as the unobserved test set. We compare the proposed ERM-DS algorithm with the single-stage one, evaluating their test risks under different CDS intensities (by varying the k parameter that controls the covariate shift) and different percentages of training data. As shown in Fig. 3, the ERM-DS algorithm consistently outperforms the single-stage ERM across all settings. On the left, we observe that as k increases, in- dicating more severe covariate shift, the test risk of both algorithms rises, but the ERM-DS algorithm maintains a significant advantage over the single-stage ERM. with the performance gap widening for larger values. On the right, the results demonstrate that the ERM-DS algorithm achieves lower test risks compared to the single-stage ERM under varying training data sizes, highlighting its robustness even with limited training samples. Overall, Fig. 3 shows the ERM-DS algorithm achieves lower test risks in handling the CDS problem across different covariate shift intensities and training data availabilities.
4 Extensions, Conclusion and Limitation
Extension to higher-order Ft-SVD, Our Ft-SVD framework, while designed for 3-order tensors, is not strictly limited to two-dimensional input cases. is versatile enough to handle multi multi-dimensional
Detailed conditions are provided Theorem 6, Appendix D.3.
Details of the experiments shown in Appendix A.3.

---

Test Risk Over
Test Risk Over the Size Training Data
LBM ERM
ERMO0
Test Riek (tokklogg scxie)
Test Flog-flog scale)
0.8
0.25
0.7
0.75
Porcentago of Training Data
Figure 3: Test risk under different experimental settings. (left) Comparison of test risk over
(covariate shift intensity) for single and double training approaches. (right) Test risk over the percentage of training data for ERM and ERM-DS.
inputs that can be divided into two distinct sets. Extending Ft-SVD to higher-order cases is indeed non-trivial and we show preliminary conjecture of a higher-order extension motivated by Ref. [53]:
Let F II X; R k be a gquare-integrable vector- valued function where X; D; for i = 1 ......,, N. Then there exist sets of functions { C T?2 RR.) for each n = 1,..., N, and a core function S II N + RK such that F can be represented as F(Z)...,,N)) TN)
II. U., (x.) Here, II. denotes the sequential t-product, which applies the t-product operation sequentially to the functions UT, (In). The convergence of this infinite sum is in the L sense. We also have
Ei S(n
Orthogonality: Vn E [N], the functions (UT) satisfy: [x, (U(())) 0
Core properties: The core function S has two key characteristics:
i) All-orthogonality: For all 1 < n S N and all a * B, we have |T X. S(. a(....
S(..,, .....) Ti dr; 0. This means that slices of the core tensor are t-orthogonal.
ii) Ordering: For all n = 1, N, we have ||Sz,=1llı> 2 ||Sa,, 12 2 where || 11 denotes the L norm of S with its ne-hh mode fixed a. This property en- sures unique ordering of the components.
This decomposition generalizes the concept of Ft-SVD to multilinear functions. is interesting to generalize the various higher-order variants of t-SVD [22, 31, 43, 1] to functional settings.
Conclusion. The paper addresses the challenge in multi-output regression where training distribution does not cover all input feature combinations, leading to CDS. We introduce a new methodology within generalized tensor decomposition framework, named Ft-SVD, tackle this challenge by treating the problem as tensor completion task under the cosssin-notaat-aamaa highlights the role of spectral decay of the true embeddings in enhancing model generalization and, through detailed analysis, establishes how multi-output models can manage combinatorial shifts, improving prediction accuracy for new and unseen input combinations.
setting. The paper
Limitation. This paper introduces tensor spectral theory framework to address MOR under CDS, marking early theoretical exploration in this field. However, several limitations are recognized. First, spectral methods may not fully capture the complexity of real-world data, and the robustness of controlled experimental results remains uncertain. We encourage future research refine these methods, aiming to develop more effective solutions. Furthermore, an open problem remains in extending the framework to accommodate more than two combinatorial features. Initial investigations suggest that the approach in Ref. [46] does not readily generalize to cases with more than two feature combinations, potentially requiring new mathematical tools to address this challenge.
Note: In the domain of F. II,h,, X, denotes the Cartesian product of the spaces X XN. not to be confused with the product operations used in the decomposition.
10

---

Acknowledgments
Our sincere appreciation goes both the area chair and reviewers for their unwavering dedication and meticulous attention given to this paper. This research was supported in part by National Natural Science Foundation of China under Grants 62103110, 62203124, 62073087, and 62071 1132, in part and in part by JSPS KAKENHI Grant
by RIKEN Incentive Research Project Numbers JP24K20849, JP24K03005, JP23K28109.
References
[1] S. Ahmadi-Asi, V. Leplat, A.-H. PHAN, and A. Cichocki. A new tensor network: Tubal tensor train network and its applications, 2024. 4
[2] M. A. Alvarez, L.. Rosasco, and N. D. Lawrence. Kernels for vector-valued functions: A review. Foundations and Trends in Machine Learning, 4(3):195-2666 266, 2012. A.2
[3] H. Antil and S. Bartels. Spectral approximation of fractional pdes in image processing and phase field modeling. Computational Methods in Applied Mathematics, 17(4):611-678, 2017. 2.2, B.2.3
[4] H. Antil and C. N. Rautenberg. Sobolev spaces with non-muckenhoupt weights, fractional elliptic operators, and applications. SIAM Journal on Mathematical Analysis, 51(3):247,-2533, 2019. 2.2, B.2.3
[5] H. Aras and N. Aras. Forecasting residential natural gas demand. Energy Sources, 26:463-472. 04 2004.
[6] B. Bakker and T. Heskes. Task clustering and gating for bayesian multitask learning. Journal of Machine Learning Research, 4:83-99, 2003. 1, A.2
[7] D. Bigoni, A. Karuu, and Y. M. Marzouk. Spectral tensor-train decomposition. SIAM Journal on Scientific Computing. 38445 2016.
[8] B. Blackadar. Operator algebras: theory of C*-algebras and von Neumann algebras, volume
122. Springer Science & Business Media, 2006. C.1.1
[9] H. Borchani, G. Varando, Bielza, and P. Larrañaga. survey on multi-output regression. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 56)):216-23,, 2015.
1, A.2
[10] Boucheron. O. Bousquet, and G. Lugosi. Theory of classification: A survey of some recent
advances. ESAIM: probability and statistics, 9:323-377 375, 2005. D.18
[11] L. Breiman. Bagging predictors. Machine Learning, 24(2):123-14) 1996. 1, A.2
[12] C. J. Carlson et al. Climate change will force new animal encounters and boost viral outbreaks. Nature, 605:20, 2022.
[13] R. Caruana. Multitask learning. Machine Learning, 28(1):41775, 1997. A.2
[14] Chen, C. Lu, Y. Li, H. Zhang, and J. Zhang. Nonconvex tensor completion from noisy data with guaranteed convergence rate. In International Conference on Machine Learning, pages 1489-1498. PMLR, 2020. 1, A.2
[15] L.-C. Chen, Papandreou, Kokkinos, Murphy, and Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(4):834-848 2017. 2.2
[16] I.. Deng, X.-Y. Liu, H. Zheng, X. Feng, and Y. Chen. Graph spectral regularized tensor completion for traffic data imputation. IEEE Transactions Intelligent Transportation Systems, 2099 2021. 2.1
[17] Džeroski, D. Demšar, and J. Grbović. Predicting Chemical Parameters of River Water Quality from Bioindicator Data. Applied Intelligence, 13(1):7-17, July 2000.

---

[18] S. Fang et al. Functional bayesian tucker decomposition for continuous-inded tensor data. arXiv preprint arXiv:2311.0482,, 2023. 1
[19] J. Gama, I. Zliobaitè, A. Bifet, M. Pechenizkiy, and A. Bouchachia. A survey concept drift adaptation. ACM Computing Surveys (CSUR), 46(4):1-37, 2014. A.2
[20] A. Gorodetsky, S. Karaman, and Y. Marzouk. A continuous analogue of the tensor-train decomposition. Computer Methods in Applied Mechanics and Engineering, 347:59-84, 2019. 1
[21] M. Griebel and G. Li. On the decay rate of the singular values of bivariate functions. SIAM Journal on Numerical Analysis, 56(2):974 993, 2018. B.2.3
[22] J. Han. p-order tensor products with invertible linear transforms.
arXiv preprint
2Xi::2005.11477, 2020.
[23] R. Han, P. Shi, and A. R. Zhang. Guaranteed functional tensor singular value decomposition. Journal of the American Statistical Association, -196546);955-0007, 2024. 1
[24] L. Hitchcock. The expression of a tensor or a polyadic as a sum of products. Journal of Mathematics and Physics, 6(1-4):164-18) 1927. 1, A.2
[25] E. Kernfeld, M. Kilmer, and S. Aeron. Tensor-tensor products with invertible linear transforms. Linear Algebra and its Applications, 485:545-570, 2015. 2.1, 1, 2.1, 2, 6, 7, 8, C.I.I
[26] M. E. Kilmer, K. Braman, al. Third-order tensors operators matrices: A theoretical and computational framework with applications imaging. SIAM J MATRIX ANAL A, 34(1):148- 172, 2013. 1, 2.1, B.1,
[27] M. E. Kilmer, L. Horesh, H. Avron, and E. Newman. Tensor-tensor algebra for optimal representation and compression of multiway data, Proceedings of the National Academy of Sciences, e
2021. 2.1, 2, 2.2, B.2.2
[28] G. Kolda and B. W. Bader. Tensor decompositions and applications. SIAM Review, 51()):455- 500, 2009, B.1
[29] J. Lai, Z. Li, D. Huang, and Q. Lin. The optimality of kernel classifiers in sobolev space. In The Twelfth International Conference on Learning Representations, 2024. 2.2, B.2.3
[30] H. Li, W. Zhang, Y. Chen, Y. Guo, G.-Z. Li, and X. Zhu. A novel multi multi-target regression framework for time-series prediction of drug efficacy. Scientific Reports, 7(1):0652,, Jan. 2017.
[31] S. Liu, X.-L. Zhao, J. Leng, B.-Z. Li, J.-H. Yang, and X. Chen. Revisiting high-order tensor singular value decomposition from basic element perspective. IEEE Transactions on Signal Processing, 2024. 4
[32] X. Liu, Aeron, Aggarwal, and X. Wang. Low-tubal-ranke tensor completion using alternat- ing minimization. IEEE TIT, 66(3):1114-1737, 2020. 2.1, 2.1, 2.1
[33] M. Long, Z. Cao, J. Wang, and M. I. Jordan. Conditional adversarial domain adaptation. In Advances in Neural Information Processing Systems, pages 1640-1650, 2018. 1, A.2
[34] C. Lu. Transforms based tensor robust pea: Corrupted low-rank tensors recovery via convex optimization. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1152, 2021. 2.1, 2.1
[35] C. Lu, J. Feng. W. Liu, Z. Lin, S. Yan, et al. Tensor robust principal component analysis with new tensor nuclear norm. IEEE TPAMI, 2019. 2.1,
[36] V. Lucarini and M. D. Chekroun. Theoretical tools for understanding the climate crisis from Hasselmann's programme and beyond. Nature Reviews Physics, 5(12):744-765, 2023. 2.2
[37] Y. Luo et Low-rank tensor function representation for multi-dimennional data recovery. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023. 1
12

---

[38] W. Ma and G. H. Chen. Missing not at random in matrix completion: The effectiveness of estimating missingness probabilities under low nuclear norm assumption. In H. Wallach, H. I Larochelle, A. Beygelzimer, F. d' d'Alché-Buu E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. 1
[39] I. Misra, A. Shrivastava, A. Gupta, and M. Hebert. Cross-stitch networks for multi learning. In IEEE Conference on Computer Vision and Pattern Recognition, pages 3994-4003, 2016. 1,
A.2
[40] Z. Obermeyer, B. Powers, C. Vogeli, and S. Mullainathan. Dissecting racial bias in an algorithm used manage the health of populations. Science, 366(6464):447 2019. 1
[41] I. V. Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295- 2317, 2011. 1, A.2
[42] K. Park and A. Stincheombe. Deep reinforcement learning of viscous incompressible flow. Journal of Computational Physics, 452:110916 2022. 2.2, B.2.3
[43] W. Qin, H. Wang, F. Zhang, J. Wang, X. Luo, and T. Huang. Low-rank high-order tensor completion with applications in visual data. IEEE Transactions on Image Processing, 31:2433- 2448, 2022. 4
[44] J. Quionero-Camte Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset shift in machine learning. The MIT Press, 2009. 1, A.2
[45] H. Shimodaira. Improving predictive inference under covariate shift by weighting the log- likelihood function. Journal of Statistical Planning and Inference. 90(2):227-244, 2000. 1,
A.2
[46] M. Simchowitz, A. Gupta, and K. Zhang. Tackling combinatorial distribution shift: A matrix completion perspective. The Thirty Sixth Annual Conference on Learning Theory, pages 3356-3466 PMLR, 2023. 1, 3.1, 2, 3.1, 3.2, 4, A.2, C.1.3, C.1.3, 6, C.1.3, C.2.2, D, D.I, D.1.2, D.1.4, D.11, D.3, D.3, 20, D.3, D.3, D.3, D.3.2, D.3.2
[47] J. Šimša. The best lz-approximation by finite sums of functions with separable variables. Aequationes Mathematicae, 43:248-263, 1992. B.2.2
[48] Smithies. The eigen-values and singular values of integral equations. Proceedings of the
London Mathematical Society, 2(1):255-279, 1938. B.2.2
[49] G. Song, M. K. Ng, and X. Zhang. Robust tensor completion using transformed tensor singular value decomposition. NUMER LINEAR ALGEBR, 27(3): 2020. 2.1
[50] L. R. Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 3163):27--11,, 1966. 1, A.2
[51] A. Wang, C. Li, M. Bai, Z. Jin, G. Zhou, and Q. Zhao. Transformed low-rank parameterization can help robust generalization for tensor neural networks. In Advances in Neural Information Processing Systems, volume 36, 2023. 2.1
[52] A. Wang, G. Zhou, Z. Jin, and Q Zhao. Tensor recovery via *y-spectral k-support norm. IEEE Journal of Selected Topics in Signal Processing, 15(3):522-534, 2021, 2.1
[53] Y. Wang and Y. Yang. Hot-svd: higher order t-singular value decomposition for tensors based on tensor-tensor product. Computational and Applied Mathematics, 41(:349,, 2022. 4
[54] W. Xiao, J. Sun, and J. Zhou. Tensor completion with side information: A riemannian manifold approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5051-505$ 2019. 1, A.2
[55] D. Xu, Y. Shi, I. W. Tsang, Y.SS. Ong, C. Gong, and X. Shen. Survey on multi-output learning. IEEE transactions on neural networks and learming systems, 31(7):2409-2429 2019.
[56] K. Yosida. Functional analysis, volume 123. Springer Science & Business Media, 2012. B.2.1
13

---

[57] X. Zhang, M. Bai, and M. Ng. Nonconvex-tv based image restoration with impulse noise
removal. SIAM Journal on Imaging Sciences, 106)::627-16677 2017. 2.1
[58] X. Zhang and K.-P. Ng. Low rank tensor completion with poisson observations. JEEE Transactions Pattern Analysis and Machine Intelligence, 2021. 2.1, 2.1,
[59] Y. Zhang, J. Wang, X. Xie, and M. Sugiyama. Equivariant disentangled transformation for domain generalization under combination shift. arXiv preprint arXiv:2208.02011 2022. 1
[60] 7.. Zhang and S. Aeron. Exact tensor completion using t-svd. IEEE TSP, 65(6):1511-1526
2017. 10
[61] Z. Zhang, G. Ely. S. Aeron, et al. Novel methods for multilinear data completion and de- de-noising based on tensor-svd. In CVPR, pages 3842-3849, 2014.
14

---

Supplementary Materials for
Generalized Tensor Decomposition for Multi-Output Regression with Combinatorial Distribution Shifts
Contents
1
Introduction
2 Functional t-Singular Value Decomposition for Multi-output Regression
2.1
A t-SVD Perspective of Multi-output Regression
2.2
Functional t-Singular Value Decomposition
An Ft-SVD-based Framework For Multi-output Regression under CDS
3.1
Generalized Tensor Completion with MNAR for MOR under CDS
3.2 Algorithms for Robust Generalization of Multi-output Regression under CDS
4 Extensions, Conclusion and Limitation
Prevalence MoR under CDS, Related Work, and Details of Experiments
19
A.I Prevalence of MoR under CDS across Domains
19
A.2 Detailed Related Work
20
A.3 Details of Experiments
20
B Functional t-Singular Value Decomposition
22
B.1 Preliminaries of t-Singular Value Decomposition
22
B.2
Functional t-Singular Value Decomposition
24
B.2.1
Proof of the Ft-SVD Theorem
24
B.2.2 Proof of the r-Term Truncated Ft-VD Theorem
27
B.2.3
Smooth Functions Exhibit Favorable Low-rank Approximability under Ft-SVD
28
C Additional Explanations of Ft-SVD Framework for MOR under CDS
31
C.I
More Explanations about the Hilbert (-Module, t-Bilinear Embeddings, and Assump- tions
31
C.1.1 About the Definition of Hilbert t-Module
C.1.2 One the Expressive Power of Hilbert t-Module and embeddings
33
C.1.3
More Explanations for the Assumptions
34
C.2
More Details of the Algorithms
36
C.2.1
Limitations of ERM for multi-output regression under CDS.
36
C.2.2
Double-Stage ERM (ERM-DS) for improved multi-output regression under CDS.
37
C.2.3
The Role of Balanced t- 1-Covariance Operator: Capturing Knowledge under CDS
40
D Analysis of the Proposed Algorithms
41
15

---

D.1 Error Decomposition
45
D.1.1
Key Error Terms
45
D.1.2 Error Decomposition Lemma
46
D.1.3 Proof of Lemma D.3
47
D.1.4
Proof of Lemma D.4
49
D.1.5
Key Blange-of-Measeee Lemmas
................................
52
D.1.6 Proof of Lemma D.5
54
D.1.7 Proof of LemmeD.6
................................
................................
55
D.2 Excess Risk Bounds for the ERM Model
................................
56
D.3 Excess Risk Bounds for ERM-DS
58
D.3.1 Lemmas From Statistical Learning Theory
64
D.3.2 A Lemma the Risk Bound for t-Bilinear Combinatorial Extrapolation
69
16

---

ERM-DS Algorithm
Inspires
Motivates
Addressed by
Multi-Ouipul Regression under CDS
Ft-VVD Framework
Formulares
Theoretical foundation
Tensor completion under MNAR
Figure 4: Overview of the core research content in this paper.
The appendix provides additional materials, detailed proofs, and extended discussions to support the main content of the paper Generalized Tensor Decomposition for Multi-Outpul Regression with Combinatorial Distribution Shifts. An overview of the core research content this paper is shown in Fig. 4. We summarize the notations in Table which provides comprehensive list of the main symbols, along with their descriptions. The symbols are categorized based on their roles, such as input and output spaces, distributions, embeddings, error terms, hypothesis classes, and algorithmic parameters.
The purpose of this appendix is to offer comprehensive and rigorous treatment of the theoretical foundations, algorithmic details, and experimental results that underpin the proposed Functional t-Singular Value Decomposition (Ft-SDD) framework for multi-output regression under CDS.
The appendix is organized follows:
In Appendix A, we discuss potential applications of the proposed Ft-SVD framework, provide detailed review of related work, and present details in the experiments.
Appendix delves into the theoretical foundations of the Ft-SVD framework. We start by introducing the preliminaries of t-Singular Value Decomposition (t-SVD) and then present the Functional t-SVD, along with the proofs of its key properties (Theorems and Theorem 2). We also discuss the low-tubal-rank approximability of smooth functions and provide the proof of Theorem 3.
Appendix C provides further explanations and insights into the Ft-SVD framework for multi- output regression under CDS. We offer more details on the Hilbert t-Module, t-bilinear embed- dings, and the assumptions used in our analysis. We also present more in-depth discussion of the proposed algorithms, including the Empirical Risk Minimization (ERM) and the Double-Stage ERM (ERM-DS).
In Appendix D, we present comprehensive analysis of the algorithms proposed in the main paper. We start by deriving an error decomposition that forms the basis for our theoretical guarantees. We then provide detailed proofs for the performance bounds of the ERM and ERM-DS algorithms, along with the necessary lemmas and change-of-measuee results. This appendix also includes a discussion on the risk bound for t-bilinear combinatorial extrapolation, which is key component of our analysis.
Broader effects. The paper provides tensor spectral perspective for the multi-output regression problem due to combinatorial distribution shift. It focuses solely on these technical aspects and does have potential societal impacts.
17

---

Table 1: Symbol table
Symbol
Description
X
Input space for the first feature Input space for the second feature Output space, where K is the number of outputs Linear transform induced by an orthogonal matrix M Rx in Eq. (1)
y
gx
M()
MTT or T
i-th frequency component of T in the M-domain
M
The Hilbert t-module (Definition 12) used in Assumption Inner product in the Hilbert t-module M
(
I.M
Norm induced by the inner product in the Hilbert t-module M (in & sense)
g
Ground truth embeddings, where f X + M and g" y + M
h"
Ground truth function, where ht" (ar, y) (f' (2:), "").g" (y))
Dersn
Training distribution over X' y x R2 Testing distribution over X' x 3 R Marginal distributions over Marginal distributions over y Product measure of xx. and Dy.j, where i, [1,2]
Duest
Dx.1, Dx.2
Dy,
Dioi
Liøl
t-covariance operator of the ground truth embeddings Di01 i-th frequency component of the t-covariance operator LiΦı
M (
jj
j-th largest singular value of M (
Polynomial decay rate of the singular values of M (Eie))
Pi
t-projection operator of multi-rank-K defined by Σis1
k g.g.
Ground truth embeddings truncated at multi-rank k
tail (ill)(()))) (k)
q-th power tail sum of singular values of M (Z (Iiss) starting from index
tail (k)
q-th power tail sum of singular values of M (iiio starting from multi-index k
lern: g Ber
Learned embeddings by ERM, where ferm X + M and Bemm
: M
L.s 8
Learned embeddings by ERM-DS, where fas X M and 8 y M
Rff.g: D)
Excess risk of embeddings (f. g) under distribution D Weighted error term for embeddings (f, g) at multi-rank k
Af k)
A (f. g..gg.
Unweighted error term for embeddings (f. g) at multi-rank
A2(f.g. k)
Factor recovery error term for embeddings (f. g) multi-rank k on D2g2
Aapx (k)
Approximation error at multi-rank k Error on the training distribution at multi-rank Conditioning vector for the learned embeddings Accuracy vector for the learned embeddings on Durain Accuracy vector for the learned embeddings D1s1
Atrain (k)
Cum
CD:81
6rm
((1)
Accuracy for the i-th frequency component the learned embeddings on Dirain
v(s)
Accuracy for the i-th frequency component of the learned embeddings on D1ø1 Cut-off singular value parameter for the i-th frequency component in ERM-DS Cut-off rank parameter the i-th frequency component in ERM-DS algorithm Parameter vector of cut-off singular values in the ERM-DS algorithm Parameter vector of cut-off ranks in the ERM-DS algorithm
Digi
Giont
Ti
Fent (ut H=
Teut
= (ri i=1
ERR (2)
(Ti,cut> (i,nut)
Error term for the i-th frequency component in the ERM-DS algorithm Hypothesis classes for the t-embeddings at rank
FR, G
(l)) 9
(())
Hypothesis classes for i-th frequency component the t-embeddings at rank k Covering number for the hypothesis classes (FR, Gk) at scale
N (b,,))
((())))
Covering number for the hypothesis classes (J . ( at scale
An
Statistical error term depending on the sample size n
a S.a
a S for some e most polynomial in the problem constants Kewv, Nurm Kapx
18

---

A Prevalence of MoR under CDS, Related Work, and Details of Experiments
A.1 Prevalence of MoR under CDS across Domains
The challenge of Multi- Regression under Combinatorial Distribution Shifts (MoR under CDS) pervasive across wide spectrum of real-world applications. The following examples illustrate the ubiquity of this problem in diverse domains:
In medical diagnostics, predicting patient's risk for multiple diseases (e.g., heart disease, diabetes) based various patient attributes (e.g., age, blood pressure, heart rate) constitutes multi-output regression problem. However, training data often comes from specific patient cohorts, covering only a subset of possible attribute combinations. When new patient groups (e.g., different age brackets or geographic regions) emerge, they introduce novel attribute combinations, leading combinatorial distribution shifts. Diagnostic systems must adapt to these new patient profiles to accurately predict disease risks.
Healthcare:
Predicting how different user segments respond to various marketing strategies (e.g., ad types, promotions) based on user attributes (e.g., age, income) and strategy attributes (e.g., ad themes, delivery channels) is a multi-output regression task. Training data typically covers common user-strategy combinations, but when new user groups or marketing strategies appear, they create unseen attribute combinations, resulting in combinatorial distribution shifts. Marketing prediction models need to transfer knowledge to these new scenarios to forecast user responses accurately.
Marketing:
Materials Science: Predicting the performance of material formulations across multiple metrics (e.g., hardness, conductivity) based on composition ratios is a multi-output regression problem. Due to experimental constraints, training data usually includes only subset of known formu- lations. When researchers explore novel composition ratios, they encounter new formulation combinations, leading to combinatorial distribution shifts. Material performance prediction systems must generalize to these unseen formulations to accelerate materials discovery.
Forecasting multiple traffic flow indicators (e.g., vehicle flow, pedestrian flow) for different areas and time periods based on area attributes (e.g., road network, land use) and temporal attributes (e.g., day of the week, holidays) is multi-output regression task. Training data may cover only typical area-time combinations, but when new arcas develop or novel temporal patterns emerge, they create unseen attribute combinations, causing combinatorial distribution shifts. Traffic prediction models must adapt to these new scenarios for effective transportation planning and management.
Transportation:
Environmental Monitoring: Predicting concentrations of various pollutants (c.g.. PM2.5, ozone) at different locations and seasons based on location attributes (e.g.. terrain, land use) and meteorological conditions (e.g., temperature, humidity) is a multi-output regression problem. Training data often comes from specific monitoring stations and time periods, covering a limited set of focation-weather combinations. When new monitoring stations are deployed or unusual weather patterns occur, they introduce new attribute combinations, leading to combinatorial distribution shifts. Environmental monitoring systems must generalize to these unseen scenarios to comprehensively assess environmental quality.
These examples summarized in Fig- 5 underscore the prevalence of MoR under CDS across various do- mains. In these scenarios, multiple prediction tasks share the same input space, but training distribution cov- ers only a subset of attribute combina- tions. The emergence of new attribute combinations constitutes a combina- torial distribution shift. Transferring knowledge from observed combina- tions to novel ones a common chal- lenge in these applications, and ad- dressing this problem is crucial for developing robust intelligent systems.
Figure 5: Examples of MoR under CDS across domains
Domain
Input
Output
CDS
Healthcare
Patient
Disease
New patient
attributes
risks
groups
Marketing
User & strat-
User
re-
New groups/s-
egy attr.
sponses
trategies
Materials
Composition
Material
Novel formu-
ratios
properties
lations
Transport
Area & tem- poral attr.
Traffic
New areas/pat-
flow
terns
Environment
Location & weather
Pollutants
New station-
s/weather
19

---

A.2 Detailed Related Work
Multi-Oufput Regression. Multi-output regression has been extensively studied in machine learning. with early works focusing on multi-task learning [13, 6] and recent approaches extending to shared representation learning [39], linear models [11]. kernel methods [2]. and neural networks [9]. How- ever, most of these methods assume that the training and test data come from the same distribution, which may not hold under distribution shifts. In contrast, our work specifically addresses the problem of multi-outpur regression under CDS by proposing a novel theoretical framework based on Ft-SVD and an extended version of the ERM-DS algorithm.
Tensor Completion. Tensor completion has seen significant advancements with the development of various tensor decomposition techniques [24, 50, 41] and methods that can handle non-random missing patterns [54, 14]. While these works provide a foundation for addressing tensor completion, they do not consider the specific challenges posed by multi-output regression under CDS, such as dealing with infinite and continuous feature domains. Our work aims to address this gap by formulating multi-output regression under CDS as a low-rank tensor estimation problem under the Missing Not At Random (MNAR) setting and developing a tailored ERM-DS algorithm with theoretical guarantees.
Distribution Shift. Various types of distribution shifts have been studied in machine learning, including covariate shift [45], concept drift [19], and domain adaptation [44]. Some recent works have addressed distribution shift in multi-output regression by aligning the distributions through learning invariant representations [33]. However, these methods typically require access to labeled data from the target domain, which may not always be available. In contrast, our work focuses on the specific case of CDS, where the training distribution covers certain marginal distributions of the input features, but the test distribution involves unseen combinations of these features. We address this challenge by leveraging the Ft-SVD framework and the ERM-DS algorithm, which do not require labeled data from the test distribution.
Simchowitz et al. [46] proposed the Double-Stage Empirical Risk Minimization (ERM-DS) frame- work to address single-output learning under CDS. Our work extends the ERM-DS framework to the multi-output regression setting by representing vector-valued functions as embeddings in Hilbert t-module and leveraging tensor algebra to capture the interdependencies among multiple outputs. The proposed Ft-SVD theoretical framework, the formulation of aulli-outpuut regression under CDS as a low-rank tensor estimation problem, and the tailored ERM-DS algorithm with theoretical guarantees aim to contribute to the existing literature on multi-output regression, tensor completion, and distribu- tion shift, by providing principled approach to address the specific challenges posed by CDS in multi-output regression.
A.3 Details of Experiments
As the pioneering theoretical study tackling the multi-output regression problem under combinatorial distribution shift, this paper proposes the novel Ft-SVD theoretical framework, along with related assumptions and algorithm design. To validate the proposed approach, we conducted a series of experiments synthetic tensor data, serving solely conceptual proof-of-concept. Considering finite feature domains X' and V, the MOR problem under CDS naturally degenerates to tensor completion with missing-not-at rradooo (MNAR) tubes. We conducted series of experiments using synthetic tensor data. The primary focus of our analysis was to compare the empirical risk of three algorithms: Single ERM in Eq. (5), Overparameterized Training (Step of ERM-DS), and the proposed ERM-DS. We generated a synthetic tensor X E (mm) (d
The tensor X was constructed using a combination of factor tensors A, E Rm xrx B E Bddxxxxx xrxk .Ag E R= x
and B2 E Rdd2 x where range (A,) C (A) and range (B,) C raageeB The singular value
tubes of A, and B, followed a power-law decay with rate 7, i.e., ((l")) [il repma((--(4-1)22 K) E R. xlxxx and the singular value tubes of A, and B, are set to be M(. repmot(ccxoo" K) e
I gxxi and c (0, 1) is the random variable following the uniform distribution. Therefore, the tensor data can be divided into four parts, namely, X11 gomixdixK X1 R x X21 Rm2xd, x K and X,2 E Rm2xd2xX, XK;
X X
X
A
Σ
B
T
1
2
=
A
*
Σ 22
#
B
(6)
1
22
20

---

Test Risk Over
Test Risk Over the Size Training Data
SPM ERM--D8
ERMO0
0.3
Test Riak (log 80100))
Test (lo scate)
0.
0.7
0.75
Parcentago of Training Data
Figure 6: Test risk larger-scale tensor of size 400 400 10 using DCT transformation. (left) Comparison test risk over и. (covariate shift intensity) for single and double training approaches. (right) Test risk over the percentage of training data for ERM and ERM-DS.
In this case, the factor tensor can be represented as the features in Eq., that is
(xx+)= = At")) and g" (usr) = B(j'),
and the tube be regarded ( 22y)) where z X(i'. j', :)), i' Nm=+t and j' Nd++d,
(f (1yr)) is regarded as the output. Therefore, the data sample can
To construct Daiin the training data are uniformly sampled from three parts, namely, ,,,, and 12 The sampling process performed in two steps. First, randomly sampled entries from the subtensor X11 with sampling rate st and from the subtensors X12 and X21 with sampling rates of 2r umin The block X22 left unobserved to be the test All experiments
implemented in MATLAB on a Linux server equipped with dual Intel E5 2640v4 and 128GB of RAM. The demo code be found at https / /ttptttttttttt//////////.. com/ www.coo//cccicc wwtpp//agaaawaaggg/ss//////////e wwS////AAAAWSSSSAOOO..SS
To generate the training and test data, we follow the above construction procedure by letting m. = d2 = 80 and m2 d2 = 120, and the rank sample ratio of X₁ is simply fixed to sr = 10%. The transform matrix M is adopted the DFT matrix. In the single training ERM and ever-parameter training step, the estimated rank is set to 2r and 4r, respectively. For simplicity, we let x e [0.1, and sr E [50%, 90%). For each experimental setting, randomly the experiments for four times and computed the average test risk and standard deviation.
15. The singular value decay y is fixed 1. The
In Figs. 3 and 6, we depict the test risk and standard deviation over and the percentage of training data. On the left, we observe that as & increases, indicating a more severe covariate shift, the test risk of both algorithms rises, but the ERM-DS algorithm maintains significant advantage over the single-stage ERM, with the performance gap widening for larger и values. On the right, the results demonstrate that the ERM-DS algorithm achieves lower test risks compared to the single-stage ERM under varying training data sizes, highlighting its robustness even with limited training samples.
Overall, the ERM-DS algorithm achieves lower test risks and stronger generalization capabilities compared to the single-stage ERM approach. is crucial note that these experiments serve only as conceptual validation of the proposed Ft-SVD theoretical framework, aiming to preliminarily verify the effectiveness of the theoretical methods handling CDS. Future work still needed further develop more effective and practical algorithms for improved performance on real-world data.
21

---

B Functional t-Singular Value Decomposition
This section provides a comprehensive exploration of the theoretical underpinnings of the Ft-SVD framework. It begins with an overview of the basics of t-SVD, setting the stage for the introduction of Ft-SVD. This section includes detailed proofs of key properties, as outlined in Theorems and 2. Additionally, the appendix examines the low-rank approximability of smooth functions and presents the proof of Theorem 3, highlighting the theoretical contributions and foundational aspects of Ft-SVD.
B.1 Preliminaries of t-Singular Value Decomposition
We first introduce some basic notations and concepts to lay the foundation for the subsequent discussions.
Basic notations. For any positive integer E N, let [n] :- (1. nn be the set of integers from 1 to n. We use lowercase bold letters (e.g., a E I?") for vectors, and uppercase bold letters (e.g., A R= for matrices. Following the standard notations in [26], we refer size 1 x x K as a t-scalar, denoted by an underlined lowercase letter, e.g., 2; a third-order tensor of size d x K as t-vector, denoted by underlined lowercase bold letter, e.g-, x: and third-order tensor of size m x n X K as a t-matrix, denoted by an underlined uppercase letter, e.g., X. For denotes its i-th largest singular value; for symmetric A, (A) denotes its i-th largest eigenvalue, and if A = 0, A 1/2 its matrix square-root.
third-order tensor of
A E
R x (A)
Given a tensor T. its ep-norm is defined as | p == | Dl).. and its F-norm is defined as T F == -[Ivec(T)]l, where v-e(-) denotes the vectorization operation of a tensor [28]. We also use I1-1 to represent the Eg-norm of vectors, F-norm of matrices and tensors for notation simplicity, For T T m=xxx we use T( or T(:, i, i) to denote its i-th frontal slice. The inner product between two tensors A and B is defined as (A, B) := vec(A) vec BB. denotes the absolute value of scalar or the cardinality of set, and denotes the function composition operation. For simplicity, let
M
denote the tensor obtained by applying the M transform to T, as defined in Eq. (1). In the following, we will frequently use (") and (-) (1)
represent (-) and M (-) (1), respectively. Here, (-) denotes the tensor or t-embedding after the M transform, while (-) (i) refers to its i-th frontal slice, i.e.,
the i-th frequency component (or the i-th sub-domain).
Concepts related to t-SVD. Due to space limitations, some concepts related to t-SVD were omitted in the main text. We provide additional explanations here, as these concepts are crucial for understanding the properties and operational rules of t-SD..
Definition 4 choonaa--slie--ee A E Rmxa K and B E Raxkxk K denoted by A @ B, is defined as tensor T such that
product [35]). The frontal-slice-wee product of any two tensors
T(;;;)) A(:,; i) B(;,;,), i [K],
where- denotes the standard matrix multiplication. The coontal-slice-wer product performs matrix multiplication on each frontal slice of the tensors, resulting in new tensor.
Definition 5 (M-block diagonal
-ll-boolk-diagonal matrix), The M bblock-diagonn matrix of any tensor T E m denoted by T, is the block diagonal matrix whose diagonal blocks are the frontal slices T == M(T):
T (Tiag(T)
(1)))
T (2)
RRRKKnn
R
This concept arranges the slices tensor in the frequency domain into block diagonal matrix, facilitating the thcoretical analysis of t-SVD.
22

---

We further provide some definitions and properties related to t-SVD: Definition 6 (125)). The t-transpose of tensor I Ruxnxk under the M transform (as shown in Eg. (1)), denoted by T satisfies
M( (M (1) i [K].
In other words, the t-transpose performs transpose on each slice the frequency domain and then transforms back to the time domain. This operation is one of the foundations of t-SVD theory.
Definition 7 ([25]). The t-identity tensor E Rmxmxk K under the M transform satisfies that each frontal slice of M() is an K x K identity matrix, i.e.,
M 1, i [K]
is easy to verify that T *M I T and I *M T = T hold for appropriate dimensions. The t-identity tensor plays role similar to the identity matrix in t-SVD.
Definition 8 ([25)). A tensor Q Rdxxxxaa is called I-orthogonal under the M transform if satisfies
Q M Q Q * = =
T-orthogonality is an important property of tensor transformations, ensuring that the inner product and norm of tensors remain invariant before and after the transformation.
Definition 9 ([26)). A tensor is called f-diagonal if all its frontal slices are diagonal matrices.
F-diagonal tensors play central role in t-SVD decomposition, similar to the singular value matrix in matrix SVD.
We present some basic facts about t-product:
(a) The t-product two t-scalars is commutative:
@ M M -1 (M()) @ M(b) M- (M(L) M(a) b @.
(b) The f--norm of t-scalar is defined
|a|| = (M)) = (M @ M(a]l = [| *M 11
(8)
(c) The square of the difference between two t-scalars satisfies ||g -bl N 2((aa] 10]l
(d) The square of the sum of three t-scalars satisfies ||a + b + c|| < 3(|a||2 + ||b|| + [|c|]?).
(e) For any f, E pmxxxx 1x we can upper bound ||[" *M g| by due to:
g
|M
* g)
(Orthogonality of M)
0
(Definition of (M))
2
(Cauchy-Schwaal inequality)
Σ 1
1|2
Σ
11
(Orthogonality of M)
The above inequalities characterize the properties of t-product from different perspectives and serve the foundation for subsequent theoretical analyses.
23

---

Tensor Tubal-rank and tensor multi-rank as measures of low-tankness in the transformed domain. The tensor singular value decomposition (t-SVD) of T R= under the transform M in Eq. (1) is given by:
T * S MM V
where U E | and V E | are t-orthogonal tensors, S E [@xx is an f-diagonal tensor, and (-) denotes the itranspose..
According to Definition 2, the tubal rank of tensor T is the number of non-zero tubes in S in Eq. (2), i..,
TT == Ki: iii, o 0, I minfm, n)}|-
The tubal rank is also equal to the maximum rank of the frontal slices of T. i.c.,
7 (T) (M ()))
which means that the tubal rank is a complexity measure of the low-rankness in the transformed domain. Within the context of t-SVD, we have another rank definition:
Definition 10 (Tensor multi-rank [60]). The multi-rank T E R under the transform M in Eq. (1) is defined as the vector of matrix ranks of all the frontal slices of M(T), i.e.
(TT (T (K))) NK
mul
The relationship between the tubal rank and multi-rank is given by
[|mmal
loo:
where || 1l denotes the -o-m of vector.
The multi-rank can be seen as a fine-grained low-rankness measure in the transformed domain compared to the tubal rank. It captures the notion of structural simplicity by assigning rank value to each frontal slice of the transformed tensor. A low rank value for a frontal slice suggests that the corresponding frequency component of the data can be -ppr-xppro by low-dimensional subspace, indicating a strong correlation or pattern within that slice. Conversely, a high rank value implies that the corresponding frequency component is more complex and requires a higher- dimensional subspace to capture its information content. The multi-rank provides a more detailed characterization of the low-rank structure of tensor in the transformed domain. While the tubal rank gives single value representing the overall low-rankness of the tensor, the multi-rank offers a vector of rank values, each corresponding a specific frontal slice. This allows for a more nuanced analysis of the tensor's 's complexity along its different frequency components.
B.2 Functional t-Singular Value Decomposition
B.2.1 Proof of the Ft-SVD Theorem
The Functional t-Singular Value Decomposition (Ft-SVD) in Theorem is an extension of the traditional t-SVD framework to infinite and continuous feature domains. This theoretical approach enables the representation of data and functions defined on these domains while preserving the core properties of t-SVD. By generalizing t-SVD to functional settings, Ft-SVD facilitates the development of efficient and robust algorithms for learning vector-valued functions, addressing complex interdependencies among multiple outputs, and solving related problems in unified and principled manner. We provide the proof of Theorem as follows.
Proof of Theorem I. The key idea of proving the Functional t-SVD to define appropriate Hilbert spaces and linear operators, and then the spectral theorem for compact operators to establish the existence and properties of the Functional t-SVD.
Step 1: Defining the t- i-Linear Operators. We first define MpxixK-valuee inner product, referred to as the t-inner product, along with the corresponding t-linear operators. Let T.2 xxxxXX and L (2) g. glxxxk] be the set of square-integrable vector-valued functions from X' and y to |XxI
24

---

respectively, The t-inner product is defined as:
(F, (X == / F(x) *M G(r)dr,
where *M denotes the t-product.
Define the t-linear operator T (IIIR + L2 as:
(TG)(z)== = F(r,y) *M G(y)dy,
and its adjoint operator T (P(XXIIXIXX - 12 as:
(T* = / Fxx, v) *M (x)drr.
To show that T is indeed the adjoint of T, verify that (TGRH)IXX (G, T RI
(TG, LOX (TG)(z) *M H()ddr
| (/S F(I,8) *M Gu)ddy *M H (x)dr
G(y) *M F(a.w) *M (x))dx dy
G(v) +M (T"
where we used the commutativity of the t-product for t-scalars to interchange the order of integration and the t-product.
Then, we establish the self-adjointness of the operators TT and T-T. Consider the operators TT [2; R (² l and TTT (2 RIXIK - (), I To
show that TT is self-adjoint, we verify that (TT*F, F.) = I)
(T F, = FT" G) (F,TT
(10)
where we used the adjoint property T in the first equality. The self-adjointness of T- can be shown similarly.
Step 2: Establishing Spectral Properties in the Transformed Domain. The next step to transform the operators the transformed domain defined by transform M in Eq. (1) and establish their spectral properties. Define t := M(T) L² RIxIxK) (2x; BIxxxk) and 7
M(T") (2;; Rlxxxk + (R 1x1X as the transformed operators for any vector-valued functions G T,2 RIXIX and H (,2; RxIIix),, respectively:
M(TG) := M ((TO)w)) and M(T'H)(z) = M ((TTH)())
where M is the invertible linear transform in Eq. (1). We similarly define operators M(TT") (2 + L (2 and M(T*T) (2) RIxIxK) [2 by
M(TT' M ((TTH))( and M(TTTG))) = M (TTTC))))
We proceed to show that:
and #T=M(TT))
25

---

To verify these identities, consider any H E L32 (2;
M((TT) (() (HTTT))(())
M ( (1s F(z.g) *M F( v)) *M H dz
( J (Ss F(z,y) o F(d,,)) v) H('))d dr
((T
where @ denotes the frontal slice-wise product, and step (i) applies the definition of the t-product, with the notation (z, v) M(F(z, v)). This verifies that - 1T* A similar approach confirms ((TTT)=TT =
We now characterize the rreuuencysppeciff behavior of TT* and T*T by performing eigende- compositions on each of their K frequency "component" (i.e., the "frontal slices" of operators T+ and T*,, respectively). Specifically, for any H (22; RIxIIK), we define the operator M ((T)))( () + (X'; by
(M(TT*) ( H ( (x) == M ((T))) i [
as the "i-th frequency componen" of TT* in the transformed domain induced by transform M().
Thus, we have:
(MTTT)(H (1) (1) ( ((z,)) F" 1) H( dy dr',
((2.)))
where denotes the standard multiplication.
(+) is a compact and self-adjoint operator on the Hilbert space L22 (I) Compactness: Note that one condition of Theorem I is that the vector-valued function F F(x, v) is square-integrable, implying that M (F(x, ()) satisfies the Hilbert-Schmidt condition:
Next, we show that MTT*))O
J (0)
Sx Σ M(F ()) Prddy
fx / (F(xF(x v)) dxdy
/ / [I ((r,))1)
(a)
where || Il denotes the 22-norm of t-scalars (i.c., vectors), (i) holds since M is an orthogonal matrix in Eq. (1), and (ii due to the gquare-integrabille of F F(x, y).
(2) Self-adjointness:
be readily verified that M (TT*)() is also self-adjoint operator on the Hilbert space (22;;' R), following equations analogous to Eq. (10), and thus we omit it.
Similarly, the operators M(T*T)
(9) also satisfics compactness and self-adjointness.
Then, by the spectral theory of compact linear operator in Hilbert spaces [56], there exist orthonormal eigenfunctions {ut., and (or,), and non-descending non-negative eigenvalues {wi,)] such that:
M M(TT)) (0 = Wig and ((T'T)(0 vi = Wi. v(i.) E [K] x N.
(11)
26

---

Then, for each i E [K], we can express F(x, using the eigenfunctions and eigenvalues as follows:
F(z
1/2 Wi un (b)(
Vi [K],
which is equivalent the slice- wise product formulation:
M(F) Σ $ 0 o
where 20)2), Eg. (2,(v) RRIII satisfy
1/2 2 10) = =
and - v(i.) [K] x.
Step 3: Transforming Back to the Original Domain. In this final step, we apply the inverse transform M from Eq. (1) to return to the original domain and construct the Functional t-SVD of F. The decomposition of F is given by:
F(x,,)
M J *M 2, (v),
(12)
j=1
where the t-singular values and t-singular functions are defined follows:
2 3 2,(x)
((3 and ~ッ(²) M 1 (v))
The orthonormality conditions
/ ( *M (x)de - M (0) *M b 6
result from the orthonormality of {uu and {eig)se (from Eq. (11)) and the properties of the transform M()) specified in Eq. (1). This concludes the proof.
B.2.2 Proof of the r-Term Truncated Fi-SVD Theorem
Theorem provides an extent of the Eckart Young theorem for t-SVD [27] to the proposed Ft-SVD framework. It highlights the optimality of the truncated Ft-SVD in approximating functions, making it valuable tool for applications such as function compression, denoising, and other tasks that benefit from low-rank approximations of functions. The proof is given follows.
valued
Proof of Theorem 2. LetGE E L2 V be an arbitrary r-term t-product expansion:
G(x,y) v)
Σ (q(x) X *M b,(y).
(13)
where a; E (XIII b,b, E LIII ) E RRIII
Our goal is to show that
|F - FrlleA(xx)aamwww S F - -I-GGLeEWWWRRREEE
for all G K,, where IC, is the set of all r-term t-product expansions.
Recall that F(0) (t, :, denotes the i-th (i E [K) frequency component of F in the transformed domain induced by Eq. (1). According to the construction of the functional t-singular
27

---

value decomposition in the proof of Theorem 1, we have:
(x,y) = Σ
20
(x)
(v), (z,)))
= Σ 5 3 (x) 1 ()))))
j=1
where the sequences (2) and (2) are in non-ascending order, and the sets (11) (8 1 (2, 1o-n (0) 3|=1 and
y= are orthonormal bases in their respective ر
spaces:
1 (m)gg (z)dx 65hn S 2 1 1002 85h, V(. E ENa,
[ (0) (x)der Öjk, [3 -sk, v(i E |r]2.
Now, let's consider the approximation error:
| - XXXRIXXX / / [1F(x,)) - G(x, Byddd
Jx ( [IM(F(2. v) G(x, b)) (lddd)
K
Σ / / (2000 - (x, (x,,)) dyde
1m1
K
|160 - (1XXXX))
1=
K
Σ
Σ
j=++1
to (0) (0)
The last equality holds due to the orthonormality of the bases in the sixth line becomes an equality when
1.m and f
gg The inequality
2 (x) a (x). 3 = E -/ Verliie (x) - az (z).
By == Ag. 20(0)= b,)), Vje
This choice of aj. A and by corresponds to the best L approxxmmaioo by finite sums of functions with separable variables [48, 47].
Therefore, we have shown that | - Fr (XIIIIIX Ejerth 1g which is the minimum
approximation error among all r-term t-product expansions. This completes the proof.
B.2.3 Smooth Functions Exhibit Favorable Low-rank Approximability under Ft-SVD
The Sobolev spaces are a family of function spaces that play crucial role in the theory of partial differential equations, signal processing and machine learning [3, 29, 42). They are defined by combining conditions on the function itself and its derivatives up to a certain order.
In our settings, let y IR Pa be domain satisfying the strong local Lipschitz condition, and let X x y R 1lxI be a vector-valued function with components (z, y), L,... K.
28

---

Suppose there exists constant 8 > 0 such that f(²) E H*())) for all i, where ())) denotes the s-order Sobolev space on V. The function class (2 H**)) is type of mixed-norm Sobolev space that arises when dealing with functions defined on a product domain X' x J' where X is domain in DR.D: and y a domain in RD satisfying the strong local Lipschitz condition. The strong local Lipschitz condition on a domain y C IK D2 requires that, locally around each boundary point yo E σy, there exists a Lipschitz parametrization of the boundary, ensuring certain level of regularity and avoiding pathological features like cusps, which is crucial for establishing various results in the theory of Sobolev spaces.
For vector-valued function f X y RxxxxX with components (1, y). = ,...., K, the condition f() E (x, H)))) means that each component function f()) belongs the mixed-norm Sobolev space (X, , ())). The space L2 H²))) is defined as the set of all vector-valued functions X x y - R xxxii with components g( (xt, v), such that for each i = 1,..., K, the following norm is finite:
1/2
119 0 Lox
(Z dx)
where ( (z, -) )l denotes the Sobolev norm of order s for the function g (z, considered as function of the variable alone, with treated as parameter. More precisely, the Sobolev norm (x (la is defined as:
1/2
Σ / (0 v)(² dy
(z, (1.-))
Ja|s
where De denotes the weak (or distributional) derivative of order a with respect to the variable, and the sum is taken over all
(A1. 02, o2,,...,aa .DD)) with |a| a1 + 02 +... aDD S s.
Theorem 3 quantifies the relationship between the smoothness of a vector-valued function and the decay of its t-singular values, as well as the approximation error of its truncated t-SVD. It provides a theoretical foundation for using t-SVD approximate smooth vector-valued functions and highlights the role of the function's 's smoothness and the domain's dimensionality in the approximation accuracy. The proof of Theorem is given follows:
Proof of Theorem 3. Let ʃ X' x y - BlxIxK be a vector-valued function with components (f) y), i = 1,..., K. The condition f(()) E (2, H²)))) implies that each component function f(0) belongs to the mixed-norm Sobolev space I.3 (X, HY))))
Consider the i-th frequency component f()) y) of ff in the transformed domain induced by the transform M defined in Eq. (1). By the definition of M(), have
K
(z. v) Σ
m,k (x) (x, y).
(14)
which is a linear combination of the component functions (()) (xx, y) in the original domain. Since each f(x) +I,(X, H+))), it follows that f(() 122XX, H²())) as well.
Next, we apply Theorem 3.2 from Ref. [21] to the function j(0) This theorem states that for function E (xx ()))), the singular values (g(9) satisfy the decay estimate
0g(g) < diam())) Cent 8),m (D2, s). |1 .j 1 8
(15)
where (),, 8) is the extension constant that depends on y and only, and Cem (D2, 8) is the embedding constant from (. (D,/(D+22),1 to (D given by
Cem (22, 8) 22/2 "T 1/2)+/
(16)
with I'(-) denoting the Gamma function.
29

---

Applying the estimate (15) to each frequency component f()) we obtain
(f = CZ
(120,)1)))))))) . 5 [
E.. N. (17)
Now, recall from the construction of the functional t-SVD in the proof of Theorem | that the t-scalars g satisfy
|,,1| - -=
Combining this with the previous estimate, deduce that
lB, 12 - Σo
S
Σ 11 10
1
Finally, according to Theorem 2. the rank-r approximation error of can be bounded as follows:
min |l - fl( fEF,
j=r+1
8)
Σ
(
(LAXX, -11- 35
j=++1
D2 (r + 1) 19
|| (00) L2(X
K Σ
D2 + 11 26 2s
diam())) Cene))))))) (Dm,
أ| 11
12,
which completes the proof.
30

---

C Additional Explanations of Ft-SVD Framework for MOR under CDS
C.1 More Explanations about the Hilbert t-Module, t-Bilinear Embeddings, and Assumptions
C.1.1 About the Definition of Hilbert t-Module
Definition 11 (Ring of K-dimensional vectors with t-product), Ler R : R be the set of all real t-scalars of K K-ddimensinnaliy which is isomorphic to IR For any a, b E R, we define their t-producc as:
h*Mb= b- o M(b)
where M R - R. is the linear transform induced by given K x K orthogonal matrix M in Eq. (1), and the dice-wise-product @ degenerates the element-wise product here.
(R, + forms a ring with the t-product and standard vector addition, which we call the ring of K K-ddimensional real vectors with t-product. Specifically, for any b. E R and a, 3 E IR, the following properties hold:
(Associativity of addition) (a + b) + = a cb+
2. (Commutatiivity of addition) a +
a
(Additive identity) There exists an element O E such that a + for all a E R.
4. (Additive inverses) For each E R, there exists an element R such that + (-a) =0
(Associativity of multiplication) (a R b) *M c = a * (b x e).
6. (Distributivityy of multiplication over addition) a*M (b+c) = - CC a *M c b M
7. (Multiplicatiie identity) There exists an element E R. such that a *M 1 = for all E R.
8. (Scalar multiplication) (aB)a a(()). ala + b)
ab, and (a + B)a
+ Sa.
Definition 12 (Hilbert t-Module over R), Let R the ring of K-dimensional real vectors with 1-product as defined above. A Hilbert 1-Module over R is module M over R equipped with an R-valued inner product (,, M : x M + satisfying the following conditions:
(Conjugate symmetry) M. (g. f) for all f.g E M, where the overline denotes the element-wise complex conjugate.
2. (Linearity in the second argument) (f.g + B,)M (L.g)) (f.g.) and (f. "M aim =
(f. M. M. as a for all f. E.g.g. M and R.
(Positivity) (f.fM (element-wise for all f E M, with equality if and only if iff=0. 0.
The Hilbert MoModuee M required to be complete with respect to the fz-norm induced by the R-valued inner product:
K
[ffl
(E.F))
where ((f, M) denotes the i-th component of the vector (f. f) M-
Remark. The Eg-norm used here differs from the traditional Ca-abgebra norm in the definition of
Hilbert Co-muuu,es, as it does not satisfy the C*-equality [| = (f. M |R [25, 8]. Despite this difference, we still refer to this structure as Hilbert t-Module to emphasize similarities with Hilbert modules..
Bin the case of real Hilbert (-Modules, this condition reduces to the usual symmetry property (L.g). (g, f.m.
31

---

The benefits of using f2-norm for multi-output regression instead of the standard C* norm The choice of the norn for Hilbert t-modules in the context of multi-output regression offers several advantages over the standard C* norm:
1. Geometric interpretation and learning theory: The 22 22-nomm as the Euclidean distance between vectors, provides natural and intuitive way measure the similarity between vector-valued functions. This geometric interpretation aligns well with the learning theory for vector-valued functions, where the goal is often to find function that minimizes the expected risk empirical risk, which are typically defined using the f--norm.
2. Computational efficiency and scalability: The f2-norm is computationally more efficient than the C* norm, especially for high-dimensional vector-valued functions. This computational advantage is crucial for large-scale multi-output regression problems, where the number of outputs and the dimensionality of the input space can be large. The εz-norm allows for the development of more scalable and efficient learning algorithms.
3. Theoretical foundations and connections: The é--norm is closely related to the theory of Hilbert spaces, which provides rich set of tools and results for studying vector-valued functions. By using the f2-nomm, Hilbert t-modules can leverage the well-established theory of Hilbert spaces, including concepts such as orthogonality, projection, and spectral decomposition. These theoretical foundations can guide the design and analysis of multi-output regression algorithms.
4. Practical applications and existing methods: The f2-norm is widely used in various practical applications, such as signal processing, computer vision, and control systems. Many existing aulti-output regression methods, such multi-task learning, multi-label classification, and multi- tartet regression, are based on the & no-no By adopting the f--nrmm, Hilbert t-modules can readily benefit from and contribute to these existing methods and applications.
Although the fz-norm may not satisfy all the properties of the standard C* norm, it offers significant benefits for multi- oulpit regression. The use of the fn-mr in Hilbert t-modules opens up new oppor- tunities for the development of efficient, scalable, and theoretically grounded multi-output regression methods. It also facilitates the integration of multi-output regression with other areas of machine learning and signal processing, where the fz-norm is widely used. The name "Hilbert t-module" highlights the connection to the well-established theory of Hilbert spaces while acknowledging the specific choice of the f2-nomm and the potential for further generalization and exploration in the context of multi-output regression.
Now we have a Hilbert t-Module M over the ring R of K K-dimensional real vectors with t-product. The elements of .M can be thought of vector-valued functions or tensors, and we consider a linear transform M induced by an orthogonal matrix M that allows us to represent these elements in the frequency domain. We also define the associated Hilbert space H, as follows:
Definition 13 (Hilbert space H2)) For each j = I...., ,, let H. be a Hilbert space over the field of real numbers R. We assume that for any element f E M, its j-th frequency component
(()) (f( belongs to Hy, ie., (()) E Hy. The Hilbert space Hz is equipped with an inner product (,,)H, Hy x Hy + R satisfying the following properties:
1. (Conjugate symmetry) (x, Y'u, = (y,,,,, for all x,y E Hij.
(Linearity in the second argument) (x + +22n, = -x,yi) + (x, Y2hn,, and (x, (x,0 = (x. Syu, for all x, N.:31 E Hi and a E R.
3. (Positivity) (x, x)H,, f.ror all E Hj. with equality if and only if O.
The Hilbert space H, is complete with respect to the norm induced by the inner product: ||x||,,, =
V (x, x)n, for all x E Hz.
In essence, Hj is a standard Hilbert space associated with the j-th frequency component of the elements in the Hilbert t-Module M. The inner product and norm in H, satisfy the usual properties of a Hilbert space, and the completeness ensures that limits of Cauchy sequences in Hj also belong to Hj-
This definition allows us to work with the frequency components of the elements in the Hilbert t- t-Module using the tools and properties of Hilbert spaces. In particular, it enables to apply the
32

---

Cauchy-Schwarz inequality in each H,, which is a key step in proving the inequality between the norm the inner product and the product of the norms in the Hilbert t-Module.
We also have a Cauchy-Schwarz-like inequality in Hilbert t-Modules as follows.
Lemma C.1 (Cauchy-Schward inequality in Hilbert t-Modules). It holds for any L.g M that
[ g) Mll <
[f 1g
Igl--
Proof. Let E .M be two elements of the Hilbert t-Module. We begin by expanding the left-hand side of the inequality:
(f. gf.g).m mll
g(f.))
(Definition of the 4--nrrm R)
K
K
Σ
May (fy B M,
H,
(Definition of the inner product on MM)
K
K
Σ
Σ m
Σ ( 8
(Cauchy- Schwarz inequality on IR)
K
Σ
U , /
(Orthogonality of M)
|fy 11:2
||8, 11
(Cauchy- inequality on H.j)
lir,
Σ l 1b2
||
(Definition of the norm on MM)
which completes the proof.
C.1.2 One the Expressive Power of Hilbert t-Module and embeddings
The Functional t-SVD theorem states that for a square- inteerrieteeeablee vector-valued function F X''y - IR x there exist orthonormal sets of functions {Ø jm C L2(,; RIIIK and { J C
10c Rlxxx such that L² (IXXKXX and sequence of t-scalars (a
F(a,y) Σ
d (x) *M * (1)
Now, consider the Ground Truth Representation assumption, which posits the existence of a Hilbert t-Module (M, ()x) and two embeddings f* X'' ト M and g' y +> M, such that the true function A (zx, y/ can be expressed as the inner product of these embeddings:
h (x y) = (f))) (v))
Assuming that the true function h" is square- integrritt,,,, i.e., h² I DIRIXIIK), the Functional t-SVD theorem implies that it admits a representation of the form
h (x. v)
(x) #M D. *M 25 (v).
33

---

In this context, the Hilbert t-Module M can be interpreted as the space spanned by the left singular functions {6, and the embeddings f* and g" can be defined as
(x) = (x *M M (M)
(*(v) Σ (0) M (
where the square root operation (-) performed element-wisely. With these definitions, the inner product of the embeddings in the Hilbert t-Module M recovers the true function:
(r()).g'()) (v)) = E (x) *M o. MM (1) h2" (x, v).
This demonstrates that, under the square-integrability assumption, the Functional t-SVD theorem provides a constructive way to obtain a Hilbert t-Module and embeddings that satisfy the t-bilinear representation assumption (Assumption 1). The theorem reveals a deep connection between the spectral decomposition of vector-valued functions and the geometric structure of Hilbert t-Modules, which can be exploited to develop efficient algorithms for multi-output regression and analysis. The use of the t-product (*M) highlights the role of the tensor structure in this framework. and the consistent notation for the singular functions (6, and v emphasizes their fundamental importance in the construction of the Hilbert t-Module and the associated embeddings.
C.1.3 More Explanations for the Assumptions
Explanation of Assumption 1. Assumption is the cornerstone of the proposed theoretical framework for multi-output regression under CDS. It establishes a connection between the ground truth function and the geometry of a Hilbert t-Module, which is generalization of Hilbert space that accommodates vector- valued functions.
Part (I) of the assumption postulates that the ground truth function h" (z, y) to veluue- outputs, admits a t-bilinear representation in Hilbert t-Module (M, M)). This means that there exist two embeddings.
(x, h"xx,, which maps input pairs
+ M and g' y - M, such that h (æ, y) allows us to capture the multi litti-iimenionall structure of the problem.
can be expressed as the inner product of these embeddings, i.e., h (z, y) = (z), g2) gg))))(()))))))))))))))))))))g (v) The t-bilinear form is natural extension of the bilinear form used (in single-output learning) [46), and it
The assumption further states that this t-bilinear representation is the Bayes optimal predictor on both the training distribution Ptrain and the test distribution Dusa. This means that among all measurable functions, the t-bilinear representation minimizes the expected loss on both distributions. This assumption provides clear learning objective and benchmark for the performance of any learning algorithm.
Part (II) of the assumption imposes regularity and boundedness conditions the output variable and the embeddings f" (I) and (v). It assumes that the squared f2-norm of z is bounded by B almost surely under the training distribution Derain. and the Hilbert t-Module norms of the embeddings uniformly bounded by the same constant B. These conditions are crucial for deriving theoretical guarantees and ensuring the pose-poss of the learning problem. They prevent pathological cases and ensure that the learning problem is tractable.
Intuitively, Assumption tells that the ground truth function has simple and interpretable structure (t-bilinear representation) that is optimal on both the training and testing distributions. Moreover, the output and the embeddings and provides clear target for any learning algorithm.
(bounded). This sets the stage for the learning problem
Assumption 2 characterizes the relationship between the training and testing distributions in the context of CDS. In real-world applications, it is common for the testing distribution to differ from the training distribution. CDS is a specific type of distribution shift where the testing distribution includes novel combinations of features that are not present in the training
Explanation of Assumption 2.
34

---

distribution. Following Ref. [46], we can also relax Assumption 2 through a probabilistic manner as follows:
Assumption 6 (Coverage of training and test distribution (probabilistic version), Assumption 2.2b in Ref. [46]). There exist constants Kigt fim > O, Thas 7m E (0, 1] and marginal distributions Dx.1, 2 over X, and Dy.1, Dy.2 over V. with product measures Dies Dx & Dy... such that the following conditions in Radon-Nikodyy derivatives hold for all (I,y) y) X x
dD dDeo,(2, 3)
PDis:
> Kam
Tmm:
(1,5) E (1,)
(Training coverage)
dD (I,
P
Eise dDicos (I, w)
Kist
S
Thst
(Test coverage)
Assumption 6 formalizes this notion by introducing marginal distributions 1x Dx,2 over the input space X' and Dy.1. Dy.2 over the output space y. The product measures Drøs == Dx.i & Dy. represent different combinations of these marginal distributions.
The assumption requires that the training distribution Dtrain covers the key feature combinations (1,1), (1,2), (2,1)) of these product measures, while allowing the testing distribution Drest to include unseen combinations (c.g., (2,2)). The coverage is quantified by the constants Kimn Kist Tun Thst which provide some flexibility in the assumption.
Intuitively, this assumption tells us that the training distribution should be diverse enough to cover the key aspects of the marginal distributions, but it doesn' need to cover all possible combinations. The testing distribution, on the other hand, can include novel combinations that are not present the training distribution. This is a realistic assumption in many practical scenarios.
Explanation of Assumption 3. Assumption 3 is a technical assumption that controls the impact of covariate shift on the model's performance. Covariate shift refers to the situation where the distribution of the input features changes between the training and testing distributions. Motivated by Assumptionn2..36 in Ref. [46] we can also consider a slacked version Assumption as follows.
Assumption 7 (Controlled covariate shifts, slacked version). There exists a ficov 1 and nlwo (0, 1] such that, for any v E M, the following inequalities hold:
E [IK (z), v) ml S Kewv EEWDx |II (f' (x), v) MM 9 + Mooo | 1
E EywDy (g (v)) v) Keov EyyDy. (1), v) 1 11 noov Seowllv/l ||
The assumption states that for any t-vector in the Hilbert t-Module M. the expected squared norm of the t-inner product between v and the embeddings f" (x) and g" (y) under the unseen distributions Dx,2 and Dy.2 is bounded by constant factor Kewv times the same quantity under the training distributions Dx,1 and Dy,1, plus a small constant Mov times the squared Hilbert t-Module norm of
Intuitively, this assumption ensures that the behavior of the embeddings doesn't change too much under covariate shift. It bounds the worst-case impact of the shift on the model's performance. This is a key ingredient in providing generalization guarantees under CDS.
Without this assumption, the model's performance on the testing distribution could be arbitrarily bad, even if it performs well on the training distribution. The assumption ensures that the performance degradation is controlled, which is essential for learning under distribution shift.
Explanation of Assumption 4. Assumption 4 postulates favorable spectral properties of the ground truth embeddings f and g. The spectral properties refer to the behavior of the singular values of the embeddings' t-covariance operators.
Part (I) of the assumption, termed "Balanced embeddings."" posits that the embeddings are balanced in an appropriate basis of the Hilbert t-Module, such that their t-covariances Σ,- and Σ equal common t-covariance Σisr This assumption might initially appear restrictive, but mathematically, is very mild. Specifically, we can always find a pair of invertible t-linear transformations Ty and T,
35

---

such that:
T *M Zr- RM T =Tg *M Zg. *M T 2is
In other words, by applying suitable transformations to the embeddings I" and g". their t-covariances be aligned common I-covariance Σist in a transformed basis of the Hilbert t-Module. Practically, the assumption of balanced embeddings can be viewed as a form of normalization or standardization. By aligning their t-covariances, ensure that the embeddings have similar scales and orientations in the Hilbert t-Module, facilitating the learning process and simplifying theoretical analysis.
Part (II) of the assumption, termed "Polynomial spectral decay," assumes that each frequency component of Σis in the transformed domain induced by the transform (-) exhibits polynomial singular value decay, potentially with different decay rates "/ for different components.
Intuitively. this assumption tells us that the information in the embeddings is concentrated in few principal directions (corresponding to the large singular values), and the importance of the remaining directions decays polynomially. This is a common assumption in many learning problems, and it allows us effectively approximate the embeddings using low-rank structures.
The polynomial decay assumption is more flexible than the often-used exponential decay assumption, it allows different frequency components to decay different rates. This particularly useful in the context of multi-output regression, where different outputs may have different spectral properties.
Explanation of Assumption 5. Assumption 5 essentially states that the error between the optimal rank-k embeddings and the ground truth function h" over the training data Dirain is bounded by constant factor Kapx times the error over a reference distribution Diæ1- This assumption ensures that the training data provides good approximation of the ground truth function in each frequency sub-domain.
Intuitively, this assumption implies that the training data Derain is sufficiently representative of the true function h- in each frequency sub-domain induced by the transformation M (-). It guarantees that if we find embeddings that well approximate ht on the training data, they will also perform well on the reference distribution DIøI- More specifically, ApxErc (+) (ar, y) measures the squared difference between the inner product of the optimal rank-k embeddings (P:M({ (z)) and Py M (g"()) (") and the i-th frequency component of the true function (M ()) for a given pair of inputs (z. y). By taking the expectation of this error over the training distribution Drrain and the reference distribution D101, obtain measure of how well the rank-k embeddings approximate the true function in each frequency sub-domain.
The assumption states that the expected approximation error over the training data is bounded by a constant factor Kapx times the expected error over the reference distribution, for all frequency sub-domains i E [K]. This means that the training data provides a good approximation of the true function in each sub-domain, relative to the reference distribution.
The significance of this assumption lies in its importance for generalization analysis under CDS. By ensuring that the training data adcquately represents the true function within each frequency sub-domain, it enables the learning of embeddings that effectively capture essential characteristics of the true function. This, in turn, allows the learned model generalize well unseen combinations of input features, provided that the spectral properties of the true function are favorable (e.g.. exhibiting polynomial decay as assumed in Assumption 4), thereby accommodating the multi-output nature of the problem.
C.2 More Details of the Algorithms
C.2.1 Limitations of ERM for multi-output regression under CDS,
In the ERM model (5), the function classes Fr. Gr are given as follows:
Assumption 8 (Hypothesis classes the ERM Model (5)). For each ks E N, there exist function classes Fg (X' + R and GR C ( gxxix satisfy:
36

---

(a) There exist some (f. (f.g) E F such that (f(z).(())) = (f(x)) *Mgg(v) = ( (V)) for all (z, v) X x V
(b) The fanction classes Fk and Gn have their e-covering numbers bounded as follows: log (og, e, Iloo) & (c) and log Ngk. e, Ilee) I (e), where Nex and Ng. non-decreasing functions of k and decreasing functions of 0.
(c) There exists some B 0, such that max {sup [(.))]lM, suPgEy [g())l.)) S B.
This assumption specifies the hypothesis classes F, and Gr used in the ERM problem (5), It ensures that these classes are sufficiently expressive to approximate the true embeddings f and gg. while also having controlled complexity in terms of their covering numbers. With these assumptions in place, obtain the generalization guarantee for the ERM solution in Theorem 4. However, the single-stage ERM approach has several limitations when applied to multi-output regression under CDS:
Lack of adaptivity to spectral decay patterns: The hypothesis classes Fr and Gr used in the single-stage ERM approach do not explicitly take into account the potentially varying spectral decay patterns of the ground truth embeddings along different frequency components of the transform M()). As a result, the learned embeddings may not adequately capture the distinct decay behaviors in different frequency sub-domains, leading to suboptimal approximations.
Global learning and complexity control: The single-stage ERM approach learns the embeddings ferm and 8 B globally, without considering the specific characteristics of different frequency sub- domains. This global learning approach may not be able to adapt to the nuances and variations in the decay patterns across sub-domains. Moreover, the complexity of the hypothesis classes F, and G. is controlled globally through their covering numbers, which may not provide a fine-grained enough complexity control capture the differences in the decay patterns.
Suboptimal generalization guarantees: Due to the limitations mentioned above, the single-stage ERM approach may result suboptimal generalization guarantees for multi-output regression under CDS. The learned embeddings may not generalize well to new feature combinations, particularly when the spectral decay patterns vary significantly across different frequency sub- domains.
C.2.2 Double-Stage ERM (ERM-DS) for improved multi-output regression under CDS.
To address these weaknesses, we propose Double-Stage Empirical Risk Minimization (ERM-DS) algorithm. This approach employs two-stage training process with more specific hypothesis classes to better capture the varying spectral decay patterns across sub-domains. By striking a balance between model complexity and generalization ability, ERM-DS aims overcome the limitations of the single-stage ERM approach and provide improved generalization guarantees for multi-output regression under CDS.
The framework of Double-Stage Empirical Risk Minimization is first proposed by Ref. [46] to address robust learning under CDS (for oingle-output learning), our work extends this framework to the more complex setting of multi-output regression with t-bilinear embeddings. By learning vector functions embeddings in Hilbert t-module and leveraging tensor algebra, capture the intricate dependencies among multiple outputs.
To more accurately capture the varying spectral decay patterns of the ground truth along each frequency component of the transform (.). the algorithm learns the t-bilinear embeddings and
g" by approximating their frequency components pr and (+(()) separately in each i-th frequency sub-domain. This is achieved by employing function classes specifically characterized for each sub-domain, allowing the algorithm to adapt to the distinct decay behaviors exhibited by the ground truth in each frequency range. By treating each sub-domain independently and using specialized function classes, the algorithm can better capture the nuances and variations in the decay patterns, leading to more precise approximation of the t-bilinear embeddings f" and g"
Assumption 9 (Function Approximation in Transformed sub-frequency components Separately). In any sub-frequency component i [K], for each k N, there exist function classes H(()) C {X +
R**} } and (1) C (2) R²} satisfy:
37

---

(a) sup se suPzex [lf())] & B and sup geot yuy |ل(())ll - B.
(b) There exist some (F.g) E F(l)
x g( such that (f(z). = ( (.),
(x),
for all
(a,y) E X y,, where fn
( (x). 10 (y) are the projections of (x) and g (y) in the top-k
(x.(0)
eigenspaces of M ( )0) respectively.
(c) The function classes F(( and gh have their e-covering numbers bounded as follows: log log.((Ft ,,1l Il S M (c)a()) and log .,lll lloo) I Mg (c), where M yso and
M gi are non-decreasing functions of k and decreasing functions of
The algorithm consists of the following key steps:
Step 1: Overparameterized Training. In the first stage, ERM-DS trains an overparameterizeed model (f. g) with high capacity to approximate the unknown true predictive functions f" and g". This allows the algorithm handle the uncertainty in the true predictive functions, which are unknown and potentially intricate. The pverpparameterized model is trained by minimizing the empirical risk on labeled training data {(x1.) M1.j x1.z) (,)) }
h-1 sampled i.idd from Dtrain Instead of training (f. g) within a single optimization problem as Eq. (5), we consider choosing their frequency components in the transformed domains induced by M (-), separately via K parallel ERM sub-problems as follows:
) E
argmin
Σ (((0)))) M)3, Vi [K].
(18)
(fa)e xg 71
represents the i-th frequency component of the overparameterized model ( g) the transformed domain, and ( and (( denote the function classes for and g. respectively. The objective to minimize the squared difference between the inner product of fx11.) .. and g and the i-th component of the transformed target variable M (Z1,), averaged over the training data.
In this equation, (1)) (0))
By solving these K parallel ERM sub-problems, the algorithm learns the frequency components of the overparameterized model in the transformed domains. This approach allows for more flexible and potentially more accurate approximation of the unknown true predictive functions, compared to training the model within single optimization problem.
Step 2: I-Covariance Estimation.
To leverage the assumption that the true predictive functions have low-rank structure (Assumption 4), the algorithm estimates the t-covariances of the embeddings using n2 additional unlabeled examples {(T2,) )2 sampled from D1g1
1 Σ
Σ
((2ss) #M ((
Σ
((23)) M ((y2.))
(19)
These covariance estimates capture the important directions of variation the learned embeddings and will be used for dimension reduction in the next step.
Step 3: Dimension Reduction. Using the estimated covariances, the algorithm computes low-rank projections (Q,. f) using the DimReduce function in Algorithm with a target ranks reut E N and cutoff parameters oeut k in each frequency domain:
Q f) + Di mReduce Σ + 1Ip Eg 1Tpp Feut, ceut);
(20)
where y is regularization parameter and is the t-identity tensor. The reduced-rank embeddings are then obtained by projecting the overparameterized embeddings onto the low-rank t-subspace: head (z. v) = f(x) Q g(v).
The high capacity the overparameterized model makes prone to overfitting, especially when the training data is limited. However, the true predictive functions can be effectively approximated using
38

---

Algorithm 1 Di DimReduce X, Y.r,o')
1: Input: Two t-covariances tensors X, Y E RPxpx r = (KI) E No, o'
(o)...., xkkT T E RRK
2: Initialize Q 0 E R2xxxx
3: for = 1 to K do
4: Compute W, == x (XF Y,x;) - where X; = M() Y; M(Y)
5: Compute Σ; Y,Y.W:
6: Set 8; < max s E [ri] o, (E;) 2 ",,) x*+1 [E) 2 (x(E;)
P1
7: Let P. denote the projection onto the top s; cigenvectors of Σ,
8: Compute Qa: = W, Pa. W and set Q(
Q..-
9: end for
10: Return (Q) where s = ($1, ($1,...,5K) E N
fewer dimensions due their low-rank structure. By projecting the embeddings onto a low-rank subspace, the algorithm reduces the model's complexity and mitigates overfitting. This dimensionality reduction step helps strike a balance between model capacity and generalization ability. enables the model to focus on the most important patterns in the data while discarding less informative directions. This step is crucial for improving the model's generalization performance and preventing it from memorizing noise or irrelevant details in the training data.
Step 4: Distillation. In the final stage, the algorithm
the reduced-rank embeddings Edl separately in the transformed domain induced by M(). This is achieved by minimizing combination of two loss functions:
(La ) by approximating their frequency components (1) %(t)
1 (f.9) + + (.
E
argmin
(21)
(fa))
xg
where (VI, px) R is vector of regularization parameters and the function classes 20 and ((0) have reduced complexity compared to F(()) and 9p
The first loss ( the empirical risk in the i-th frequency domain on ng additional labeled examples (1aa, U3 23.,) )- sampled from Derain:
1 ngg
(f.9)
Σ ((((aa)) - (1). ra j=1
By minimizing this loss, the algorithm ensures that the embeddings accurately capture the relation- ships between the input features and the target outputs.
The second loss ( is regularization term that encourages consistency with the reduced-rank embeddings h on n4 unlabeled examples " sampled from D1ø1:
1 > ((((E))) (h 84.))
(1) (f.9)
n44
By learning to match the reduced-ras -rank embeddings Lew on these unlabeled samples, the final model becomes more robust to distribution shifts.
Intuitively, the distillation step allows the model to learn from both labeled and unlabeled data, leveraging the information captured by the reduced-rand embeddings to improve its generalization ability. The regularization term acts as guide, encouraging the fine-tuned embeddings to maintain the important patterns and structures learned during the previous steps while adapting new feature combinations. By combining the empirical risk and the regularization term, ERM-DS strikes balance between fitting the labeled training data and being robust to distribution shifts. This helps the
39

---

model generalize well to unseen feature combinations and ensures stable performance even when the test distribution differs from the training distribution.
C.2.3 The Role of Balanced t-Covariance Operator: Capturing Knowledge under CDS
The t-covariance operator Eig is central to the Ft-SVD framework for multi-output regression under combinatorial distribution shift, capturing the spectral properties and low-rank structure of the predictive functions across K' frequency components. Defined as the common I-covariance of balanced embeddings f* and g' on DisI. Lie reflects the intrinsic low-dimensional structure and shared patterns across feature combinations. Its spectral decay, indicating the eigenvalue decay of its frontal slices in the transformed domain, guides the Ft-VD framework in aligning embeddings with principal eigenfunctions, enabling effective knowledge transfer under distribution shift.
Estimated from Di@1 == Dx,1 @ Dy.1, the t-covariance operator supports three main steps the ERM-DS algorithm:
Estimation: Using unlabeled samples from D Di@1 to identify significant variation directions in embeddings.
Employing spectral decay to compute low-rank projections that balance capacity and generalization.
Dimension Reduction:
Distillation: Constructing regularization term to align fine-tuned and reduced-rande embeddings, enhancing robustness.
At its core, Σien acts form of transferable "knowledge" for multi-output problems under combinatorial distribution shifts, capturing and transferring crucial patterns across feature com- binations. Its spectral properties and principal eigenfunctions encapsulate the -in-dimensional structure, guiding the model to focus on the most transferable features and achieve generalization in shifted distributions. Through Σisi. the Ft-SVD framework and ERM-DS enable effective knowledge transfer and address the complexities of combinatorial distribution shift.
40

---

D Analysis of the Proposed Algorithms
In this section, we embark on a comprehensive theoretical analysis of the ERM and ERM-DS algorithms for multi-output regression under the challenging setting of CDS. Our primary goal is to establish rigorous generalization guarantees for these algorithms.
Challenges. In the our settings of multi-output regression under CDS, several key challenges arise. Firstly, the algorithms must be able to effectively capture the complex relationships between the input features and the multiple output variables, even when the training data only covers limited range of feature combinations. Secondly, the spectral decay patterns of the true embeddings, which encode the intrinsic structure of the data, may vary across different sub-domains (i.e., frequency components), necessitating algorithms that can adapt to these variations. Finally, the presence of distribution shift between the training and test domains can significantly impact the generalization performance, requiring algorithms that can mitigate the effects of this shift.
Section organization. To address these challenges and provide comprehensive analysis of the ERM and ERM-DS algorithms, we organize this section into three key subsections.
First, we introduce technical tool that allows us decompose the excess risk of the algorithms into various interpretable terms, such as the approximation error, statistical error, and distribution shift terms in Appendix D.I. This decomposition forms the foundation of our subsequent analysis and provides valuable insights into the factors influencing the generalization performance.
Second, we focus on the theoretical analysis of the ERM algorithm in Appendix D.2. We present the main theorem that provides generalization guarantees for the ERM solution under certain conditions and outline the key steps in proving this theorem. Through this analysis, we highlight the limitations of the ERM approach, such as its lack of adaptivity to the spectral decay patterns and suboptimal generalization guarantees, motivating the need for a more sophisticated algorithm.
Third, we introduce the ERM-DS algorithm as a response to the limitations of the ERM ap- proach in Appendix D.3. We provide an overview of the key steps of the algorithm, including overparameterization, covariance estimation, dimension reduction, and distillation, and explain how each step contributes the improved generalization performance. Through hige-level sketch of the proof for the main theorem, we highlight the key ideas and techniques used in each step of the algorithm and discuss how the error terms are controlled by carefully selecting the algorithm parameters and sample sizes.
Addtional notations. To facilitate the analysis, we introduce some additional notations. We use S 6 to denote a S e- b for some absolute constant e; we use S. b to denote a S c for some c that is at most polynomial in the problem constants Keov, Nimms Napx.
Given a probability distribution on (x. v) E X' pairs, we define the excess risk of the embeddings (f. g) as Rf. g: D) == E(z.))>Dl (( - h" (x, v) [[]] which quantifies the expected squared difference between the product of the embeddings and the true relationship h (x. v) within a Hilbert t-module M. We often omit the function dependence on (I, y) in expectations for brevity. For all embeddings f,g E M and distribution D, decompose the risk as:
R(, g: D) == [[xx)) * g(y) (x. v)
E(z,))D ( ([(x)) * g(y) (x,,))
B(xa)DD [(x)
g(v)) (
27
B(z.)EDD
(z) (v) A (I.
K
BlawED
(z))
i (v) A (I.
41

---

In words, the risk R(f g: D) measures the expected squared difference between the predicted output [(x) *M g(y) and the output A (z, y) under the distribution D. It quantifies how well the embeddings f and g approximate the true relationship h* on average. The key idea in the risk decomposition is to transform the risk into the frequency domain using the transform M()) and then decompose it into sum of risks over individual frequency components, such that the tools developed in Ref. [46] can be applied. This is achieved by expressing the risk in terms of the frontal slices of the transformed embeddings f and g, and the transformed true output A By defining the
risk (f. g: D) for each frequency component we can analyze the performance of the embeddings in more fine-grained manner. This decomposition allows us study the behavior of the embeddings in different frequency components and identify the sources of error that contribute to the overall risk.
Finally, we can express the total risk Rf. g; Drest) as the sum of the risks R, (f. g: Drest) over all frequency components.
We also define some key quantities related to the spectral properties of the embeddings and the I-covariance operators, including the full-multi-rank embeddings, the t-singular values 2, (f. g) and
o, (L ), the tail sums tail (k), and tail; (k) as follows.
Full-multi-rank embeddings: Given a vector r = (ri...., (rk) E N we say that pair of xllnllxxxxxX -embeedddissn (f. g) are full-multi
if the ry-th singular value or, (I9), g
strictly positive for each frequency component E [K] This condition ensures that the embeddings have sufficient expressive power and that their spectral properties well-defined in each frequency component.
())) The t-singular values 2 (f. g) defined as the t-singular values 2, (f. g) and af $
t-singular values of the product of the square roots of the covariance operators Ex [ * ["] and Epy, g * g' g::
2 (f.)) =0 (Fxxa #M
f']à *as EDY., [g M g g
Similarly, (f g denotes the singular values of the product of the square roots of the covariance operators in the i-th frequency component:
oj (EDx, E T EDY,
E (0) )
These singular values capture the interactions between the left and right embeddings in each individual frequency component, providing a more fine-grained characterization their relation- ship.
Tail sums tail (*) (ail (k.). tail;, (k), and tail, (k): The tail sums measure the decay of the singular values in different frequency components and provide a way to quantify the complexity of the embeddings.
(a) tail denotes the sum of the y-th powers of the singular values beyond index k; in the
i-th frequency component:
tail (1) (k;) = Σ (0) 121,
(ail())
JeDks
where 8 Xy (M are the singular values of the covariance operator Σisl in the i-th frequency component.
(b) (k) denotes the sum of the q-th powers of the singular values beyond index & across all frequency components:
tail,
Σ
921
i=
42

---

(c) Given vector k
(k......kkp kx) E N* tail; (k) is more general version of tail; (k), where the summation is taken beyond index k; in each frequency component i:
tail (k) = Σ 1=1 J.2
J )
q 021. I.
These tail sums capture the complexity of the embeddings by measuring the decay of their singular values. A rapidly decaying spectrum (i.e., small tail sums) indicates that the embeddings have a low-rank structure and can be well-approximated by a small number of principal compo- nents. Conversely, slowly decaying tail sums suggest that the embeddings are more complex and require a larger number of components to capture their variability.
Furthermore, we introduce the multi-rank-k t-projection operator PK. which projects an embedding onto the top principal directions in each frequency component.
Definition 14 (Multi-rank- rank-k t-projection operator). Let (kI....kk)) . NK The multi-rank-k projection operator P .M- + M on the range of Lig satisfies
(M(P))) ( P Vi [K],
(22)
where Pk. is the orthogonal projection operator onto the top-k; eigenspaces rango (Ei ))) P projects the embedding onto the top k; principal directions in each frequency component, serving the purpose of dimensionality reduction and extracting key information.
Definition 14 introduces the concept of the multi-rank-K t-projection operator P which plays a crucial role in dimensionality reduction and information extraction within the Hilbert t-module framework. This operator is designed to capture the most significant components of an embedding f by projecting it onto the top k; principal directions in each frequency component.
The PK operator offers a principled approach tackle the CDS challenge by exploiting the low-rank structure of the multi-output functions in the transformed domain. By projecting the embeddings onto the top k; principal directions in each frequency component, P effectively captures the most significant patterns and correlations present in the data, even in the presence of CDS. The key idea is that the low-rank structure of the multi-output functions, as revealed by the spectral decomposition of the covariance operator Σ Σi@ remains relatively stable across different feature combinations. In other words, the principal directions along which the functions exhibit the highest variability or energy concentration are likely to be shared among different combinations of input features.
Lemma D.1 (Properties of P.). Let operator P M + M has the following properties:
(ki.... kk) T N The multi-rank-k projection
1. Selffaddoin::sss: ( = (f.
2. Idempotence:
PCP P.f.
Proof. By definition, we have
(P(.) ((M(()))) "g
(P
n. (
PA. 190
)
holds for all E [K] where (1 -hu, denotes the inner product of Hilbert space defined in Definition 13. Self-adjointness and idempotence reflect the basic properties of projection operators.
Definition 15 below introduces the concepts of the balanced t-embeddings and balancing t-operator. The main idea behind these concepts is to balance the left and right t-embeddings in a way that preserves their spectral properties while simplifying the analysis.
Definition 15 (Balanced t-embeddings, balancing t-operator). Given a fixed vector of integers For a pair of RR[I x1xK -emeediings xlbeddndedd (f.g). their 1-covariance tensors
r (F1," ... .TK) NK
EDx, f f f Epy, * [ 1T, then (f.g) is said to be balanced t-embeddings.
For full-multi-ranke Illl x1xK -embeddings (L. g). an operator I 1lllll x1xk + RR frll x1xK
is defined balancing t-operator satisfies: (a) the pair of t-embeddings (f.g) (T Tg) is
43

---

balanced, and (b) or, (M [[ * F (0))) = or, or, (M * g ( Jr, (1)) (() for all i E [K]
The key property of the balanced I-embeddings is that the r:-th singular values of the t-covariance in each frequency component E [K] are equal to the [ M and Edy.. g * #
tensors Epx..
ry-th singular value of the original embeddings (f() ())).. Intuitively, the balancing operator helps to align the spectral properties of the left and right embeddings, making them more compatible and easier to analyze. By balancing the t-embeddings, we can focus on their essential characteristies and ignore any irrelevant or redundant information that may complicate the analysis.
The balancing t-operator plays crucial role in the definition of aligned k-proxies.
Definition 16 (Aligned proxies for t-embeddings). Given fixed vector of integers r NK. We say 4r IRlrll xlxk + -M is t-isometric inclusion if preserves tiinee
(ri,"" .TK) T products, i.e., Y #M W = (vr()), (e(W) Let + Bllrll x1xX and g y + RlllllxxIIxX be full-multi-ranke We say (f.
aligned k-proxies for (f. if: (a) o where in TR. rl x1xk - .M is a 1-isometric inclusion, and T is the balancing 1-operator in Definition 15, and for't Pk being the multi-rank-k 1-projection operator defined by Ligt have
(1 T)
range
P C range(EDxx.l
(f * I'
(23)
The concepts of t-isometric inclusion and aligned k-proxies are essential for establishing the general- ization bounds for the ERM-DS algorithm. These concepts allow us to relate the learned embeddings to the true embeddings and control the approximation error.
Definition 17 (a- (a-Conditioned embeddings). Given vectors r= (r N and a = (at) E
K where og 2 1 for all i E [K], we say IR |rll xlxk -embeddings ( g) are a-conditioned with multi-rank if
2002 of, ( ( 1g Vi E [K].
where or 2 denotes the ri-th singular value of the learned embeddings (f. g) in the i-th fre- quency component, and o7, (1r(10) ge.(0) is the corresponding singular value of the true embeddings (f" gg))
The oe-oonitiooedd property ensures that the learned embeddings (f. g)) have singular values that are not too small compared to those of the true embeddings (f g").., up constant factor as in each frequency component i. This condition guarantees that the learned embeddings capture the essential spectral properties of the true embeddings and have sufficient expressive power to approximate the true relationship between the input features and the output variables. The constants a; > 1 provide flexibility in the condition, allowing for some discrepancy between the singular values the learned and true embeddings. Smaller values of a; indicate tighter condition, requiring the learned embeddings to be more closely aligned with the true embeddings in terms of their spectral properties. The R-conditioned property is important in the analysis of multi-output regression algorithms under CDS because it helps control the approximation error in the generalization bounds. By ensuring that the learned embeddings have sufficient expressive power, this condition enables the algorithms to effectively capture the intrinsic structure of the data and achieve good generalization performance.
Definition 18 ((Em, EDiea -accurate embeddings). Given vectors
(ri) E *NK, Eu Digs 2 0 for all i E [K], we say
K (0 F=1 E RRK, EDi::
(2()) (ig E RK where z(() ((i)
B xxxxxx K embeddings (f. g) are (Eum: EDi -accurate with tensor multi-rank if
Diruin) $ (2(0)))
E (K).
inf R
D1o1) (2 (1)
(101)
) Vi [K],
2r
"In case of non- uniqueness, any choice of the t-projections works.
44

---

where R (1 : is the excess risk relative to )= (1) g)((1)), top-block distribution Dioli
evaluated on the ...
R
; D101)= ((a,)) (x),
E. (x,
(24)
18
The (Fum) (Dig1) accuratee property ensures that the learned embeddings (f. g) closely approximate the true embeddings (f" g*) terms of the excess risk on both the training distribution Perain and the top-
block distribution D101- The first condition, (0) (1() . (0)); Dirain) - (zm)2 requires that the excess
risk of the learned embecdiings on the training distribution is bounded by (2(0) in each frequency component i. This condition ensures that the learned embeddings the training data well and capture
the underlying patterns in the data. The second condition, inf, R( (1() (();; Disi) S (2))0) )²
.g
requires that the excess risk of the learned embeddings on the top-block distribution, relative to the best rank-r' approximation of the true embeddings for any r' 2 is bounded by (z(6) (Dir )² in
each frequency component i. This condition ensures that the learned embeddings generalize well to the top-block distribution and can effectively capture the important spectral components of the
Di00 quantify the degree of accuracy, with smaller values true embeddings. The constants <un and (())
indicating better approximation, The (fum; cD1 )-accurate property is important in the analysis of multi-output regression algorithms under CDS because it helps control the estimation error in the generalization bounds. By ensuring that the learned embeddings closely approximate the true embeddings on the relevant distributions, this condition enables the algorithms to achieve good generalization performance and mitigate the impact of distribution shift.
D.1 Error Decomposition
In this section, we present a technical method that breaks down the excess risk of the algorithms into distinct, interpretable components, such as the approximation error, statistical variance, and terms capturing the effects of distribution shift. The main idea in this section builds on Ref. [46]. For completeness, we provide a detailed overview of the error decomposition framework used analyze the generalization performance of multi-output regression algorithms under CDS. Our objective is to establish an upper bound on the population risk Rf. g; Drest.) for the test distribution in terms of the training distribution risk and additional error terms that account for distribution shift.
To achieve this, we introduce key error terms that capture different aspects of the shift between training and test data, defining these terms address the challenges of CDS in multi-output regression. We then present a series of lemmas that bound the test risk in terms of these error terms, which collectively lead the final error decomposition. This culminates Lemma D.2, summarizing the decomposition and providing insights into the algorithm's generalization behavior under CDS.
D.1.1 Key Error Terms
Definition 19. Given functions f: X - M and g: : y + M and k = (ki, , define several key error terms as follows:
T e NK, we
(. g. k) max EDigs
[| 0h glml EDi
| [. Lg (weighted error)
A (f. (f.g. gg k) max
EDD., i 11f - fll2n, EDy, 11g 1gg-g1. gl
(unweighted error)
(2, k.
max EED., 11f fl E EDy, -
(D 22gg--eeooeo recovery error)
Aapx (k) R(E, ; Disi)
(approximation error)
Atrain (k) = R(i ; Durain).
(error on training distribution)
When it is clear from the context, we will use the shorthand notation Ag, Ar, A2. Daps and Arrain respectively, for convenience.
45

---

capture the These enror terms are essential for assessing the performance of embeddings f and g across different distributions:
Weighted Error (f. g, k): Measures discrepancies between true embeddings (G. g and learned embeddings (f. g) under Digt. focusing on the weighted differences along each direction.
Unweighted Error A (f. g k): Captures unweighted differences between true and learned embeddings under D1, assessing how well (L. g) approximate (L g without specific weighting.
D2ø2-Recovery Error 42 (f. g, k): Represents discrepancies under D202, evaluating differences between true and learned embeddings in this setting.
Approximation Error (k)): Mcasures how well the true embeddings (rr g
actual relationships under D181.
Training Error Atrain (k): Indicates the risk of true embeddings (fi g.) on the training distribu- tion Dtrain, reflecting their alignment with the training data.
D.1.2 Error Decomposition Lemma
Lemma D.2 (Error decomposition on Diest). Suppose Assumption 2 and Assumption hold. For any vector k- (k1, .kk)* satisfying k clement-wiselt with some fixed vector of integers -ri, .TK E NK, and any aligned k-proxies (f,g) of the IR Birll x1xX -embeddings (f. g).
denote Ao = (f, and A = -i((fg, Let a & minve(K] Tr, (80) 2(0) be a lower bound on Tr. ( which satisfies of E (0, tail
1 (k:)) Do Derain) for all i [K]. Then,
Rf..g Doest) S. A + (Aapx + Do + Atrain)
The proof closely follows that of Proposition 4.1b in Ref. [46] and proceeds by incrementally bounding the risk on the test distribution Dust through a sequence of lemmas. In these lemmas, rather than applying Assumption and Assumption directly, we employ their relaxed forms as given in Assumption and Assumption 7. This adjustment allows us to handle cases where coverage and covariate shift conditions hold only in a probabilistic approximate sense, thus broadening the applicability of the result.
First, we apply Lemma D.3 decompose the risk Drest into the risk the bottom-right block distribution D282 and the risk on the training distribution Dusinn
Lemma D.3 (Error decomposition on Drest). Under Assumption and Assumption 8, the following holds for any [ X + M and g MM
R(f. g: Drest) S. FiEsa (R( g: D202)= + 38mm Rf. g; Derain)) + 41B((sss + 3mm)))m))
Next, we focus bounding the risk on D202 using Lemma D.4. This lemma reveals that the dominant term in the risk decomposition is the weighted error Ag. while the unweighted errors A and A₂ contribute only quadratically:
Lemma D.4 (Error decomposition D202). Under Assumption 6, Assumption 7 and Assumption 8, for any : X + M. g: M, and k E NK:
R(, g; D202) S R2o (Do + (21)2 + Aapx) + (D2)² + KeooKKm Atrain + Ba Keov (Noov + Thm))
(1lov
where above we suppress error term dependence f, g,
To bound the term 22, leverage the assumption that (f. are aligned k- k-proxies of (f. g). along with the construction in Definition 16. This allows us to apply Lemma D.5 and obtain a bound on A2 in terms of the training error Atrain the weighted error Ao. and the approximation error Aapx (k):
Going forward, recall the construction in Definition 16 that
(0) = or (M f f ()),,, Vie [
46

---

where the positivity is consequence of the assumption that (f. g) are full-multi-rank. We may now bound 2
Lemma D.5 (Decomposition of A2). Suppose (f. g) are aligned k-proxies of (L. g). Then, we have
(min(or. (1() - {)) X train Ricwv (An + A Appx (k)) + B² (Naw ma))
where above we suppress dependence g. in all error terms.
Lastly, it is noteworthy that the multi-rank- k approximation error under the D1@1 distribution is precisely the tail term (k). We exploit this crucial fact by replacing the Appx (kpx(k) term in the previous error decompositions with tail (k).
Lemma D.6. We have Dapx (k) R(G (isi) (k).
Proof of Lemma D.2. First, we apply Lemma D.3 to decompose the risk on Drest into the risks on D282 and Draiin We then further decompose the risk on D282 into various error terms using Lemma D.4. Next, we bound A₂ by leveraging Lemma D.5 and the assumption that (f. g) an aligned k-agent of (f. g) Substituting the bound A₂ back into the risk decomposition D282, and applying Lemma D.6 replace Anpx (k) with tail; (k). Finally, combine the error terms using the condition on a to obtain the final result.
D.1.3 Proof of Lemma D.3
Lemma D.7. Under Assumption 6, have for any (i.5) (1,, (2,1)
Rf. g: Dios) S 4Bm + Kum Rf, g; Derain).
Proof of Lemma D.7. To bound the risk under Duej in terms of the training distribution, we introduce a density-based event and apply it to control expectations.
Define the event Etrain,ssj for any (i,j)= E {(1,1), (1. (2, 1)} as follows:
Etrain, = dDioo (x, 4)
<
dDurain (I.
This event limits the density ratio between Diooj and Derain. ensuring that Diesi does not deviate excessively from the training distribution.
Now, for any function h : X' x y + RIxII with ||[[,, v)ll < M, we proceed to bound the expectation under Diagi
ED [z] 1 < M L
ED [[|,(x (( H..
The first term represents cases where Etrain.is does not hold, bounded by M2PDiee L Etrain For the second term, leverage itrain, to express the expectation under Drrain:
dD dD dDuraiu (z, y)
ED [1]h(,, " =E E.
[1 II (Etraiin,
Since Ecrain,ty holds in this term, the density ratio is bounded by Kun- giving:
Epia: [ax, 1) < M 2 (- + Ep [Nam (z v) 19)
Substituting P Prie - Eiylin S Amm yields:
Ep,ey [1) y) 12 < 2 thm + rimm EDrna [1) 1
47

---

Now, let h(x,)) (f(z). g(v)) - (x, v). Note that
(x, y)1l (l((()).())), (x,
- (() (.))
(25)
- 4B*
Then, [_, y)ll2 bounded by 4B giving:
E [1(x, y)| & 4B mm + Kum R(f. g: Derain):
which completes the proof.
Proof of Lemma D.3. To bound the excess risk under Assuption 6, we decompose the expected norm of function under Duett by defining density-based event and applying control expectations.
First, we define the density-based event Etest to control the ratio between the density of Dust and mixture of reference distributions Disj:
dDuust (2,
Exest (E,eE(122) dDies (I,
S Kist
This event ensures that Drest does not deviate excessively from the reference distributions, allowing us to manage expectations over Drest using properties of the distributions Diæj.
Next, we bound the expected norm of any function h(x,, y) x y RIIXX with [1,(,, 3)11 = 2 under Deest. We decompose this expectation as follows:
ED [1) 1) < PP [uestt + D [{Ecest |Ll(,, y)
The first term accounts for cases where Eust. does not hold, bounded by M - Erest]. The second term, where Eust holds, allows us to use the density ratio to write:
d (2r, v)
EDi.u (L(ttest Hlii v)]
((a.))
1112
Σ
dD (1.))
11 1(Eaa)).
En dDico y)
i.jE(1.2)
Since Eveat holds in this term, the density ratio is bounded by Nist. leading to:
Ep,,a [1, v) & MPP Evest) + fist
[ ((a.)) [1(x,, 8)12
Σ (Dies(a.u))
(.jE(1.2)
We rewrite the integral using the expectations over Diaj. yielding:
Exina (Il (1) v) < M2P P Erest + Kist
Σ
(D [x]
(
Finally, noting that PD,.. Erest] Tists we have:
E Ep [11((1)))11] < 2 + Kist
Ep.,, (b(z,))11
Now, let h(x, v) (f(z). (())gg())) h-t h= v). where |1,(2, y) is bounded by 4 by Eq. (25).
This gives:
R(f. g: Drest) S 4B nu Huss Σ
E ED (M(,,,))1
1
48

---

By applying Lemma D.7, we further bound the sum over Diej for all pairs except (2, 2):
Σ
R(L. Dios) x 12B* 7/m + 3.mm R(. g; Derain).
(2,2)
Therefore, combining these results, conclude:
R.f. g: Diest) S Kist (R(f. g; D282) + 3m R(S, Perain)) 41 - 3.5m7)m))
D.1.4 Proof of Lemma D.4
Lemma D.4 establishes bounds on the risk under D222. highlighting that the primary contribution in the risk decomposition comes from the weighted error term Ag. In contrast, the unweighted errors A₁ and A₂ have only quadratic impact. Before proceeding with the proof of Lemma D.4, we first present a lemma that assists in expanding the risk term Rff, g; D282) by breaking it down into more manageable components.
Lemma D.8. For any function ht X x y IxxI and for 1 X + M and 8 82
M, we have
[1 8 )M 12
12 B M - + - L, f 8,) 61 -B) + - E1Bll B -2,
Proof of Lemma D.8. To simplify notation, let 4 = (L g M and h1 = (Le, 8 Our goal is to bound the expression ||, 112 using h2 and differences between f,,fe and 8.
We start by expanding ||, h" 12 || 1=1 as follows:
1/ 1 [/, - -12 (1, h
hn)
This identity allows to split the difference in terms of the inner products of h h2 and each of the terms h1 ht and fig- - ht" Next, applying the Cauchy- Schwarr inequality, we get:
||4 12 ||2 h 11 < ||h, - h₂1l2 + 2/ - h²1l ||h, - h2ll-
Expanding and rearranging terms, we conclude that:
1 11 < 2 12 + 2/2 - 112
To bound ||2 122l2 we expand this term
|/, h2ll [1 g..g,,
(L ml
= [f fg g, (f.. g
M (f, f. - gg),ll??
Using the Cauchy-Schwazz inequality on each term separately, we obtain:
1b 12 < (f, f, B 3|1 (2.g
g 3 3| fg.g, B,)mnl?
Finally, applying the Cauchy-Schwaad inequality again to the last term, we have:
4 h, 2 [. fg m
3/ (fe.g, B 3| 13 11
Combining this with our earlier bound on ||,, - 11 we arrive at the final result:
||4 2 g 261 - 16 - -1
This completes the proof.
O
49

---

Proof of Lemma D.4. The proof approach follows the structure of Lemma L2.b in Ref. [46]. The primary distinction that our proof deals with t-embeddings within the Hilbert t-Module M for multi-output regression, while Lemma 1.2.b in Ref. [46] addresses single-output learning.
Step Tackling covariate shift under D202.
To analyze the impact of covariate shift under D282. With this setup, we can apply Lemma D.8 to bound
let's set f = f. g, g, f22 f and 82 = S.
the difference in risk as follows:
Dzga (f. g)
ht [-] 2. III (G. ). 1-1
6 E BDasa |I [[[
Fh ) 12 + DD22 (G. M 21 + LE Deez Illf 11ff-511 Gl2ull - EilBul)
(1) 6/ieov (EDEI llf fi g .wll 11 + ED fG. sal??
61E
[I[ 11lll g + Toov 17oov
Offcor (EDrsillE
f g ml + EDIIs GG.g M))))
6EDx.
31l Ep Epy.all
=gll + 488B Noow
(68)
6Foco
(EDzeL (f
f g Mll? + EDIea - m2))l)) + 6(l2)) + 48B* Moows (26)
where each step is justified as follows:
In (i), we apply Lemma D.9 bound ED [[ fu MMll 112 and EDasall Kh. g*) MM1?
This is possible since lig - ll. I llg|l. + lg. IIm $ 2B and similarly, || F Iil S
[f]l + |M S 2B.
In (fi), we utilize the fact that D282 = xx,2 @ Dy.2 is product measure, allowing us to separate the expectations over Dx.2 and Dy.2.
In (tii). we introduce the term (A²)² (A2(f, g, k))2 to further simplify the expression.
Thus, Equation (26) provides the bound on the risk under D222, accounting for covariate shifts in the multi-output setting.
Step 2: Expanding Terms under Dise and D281. In this step, we expand the first two terms from Equation (26) further analyze their contributions.
Starting with (f f. ) M observe that:
(f (f- g M (f. g M h (f.g) h (T. g) = =f..) -MMM-Mi+H (F. B) (p- g. g)
With this, we can bound:
ED [k fr )
< 3E [l. - A1ll + 3E
[ff g"
=ll 33 Il - fr. g Mllll
(1)
3E Dagi (f. g) 1+] 3 Epig.
(TT g. g) M1 + 3D 11 - - -gl + 12B Mooxs
where in (i) we use Lemma D.9 to bound terms involving covariate shifts.
Next, expand and bound the product of norms term as follows:
E E 1 fli - glli
EDx,
lff
fll
EDy, |ls -gl
(EDx.2
I1 1122)
+
Kew
EEDy. l.. -g13d)
2Kam
2
(A2)²
Keov
(A1)2
2New
2
50

---

where we have used the definitions of A2 and A from Definition 19. Summing up these results, obtain:
Ep If - f g,..l
1 ((11)))
3 (A2)² + 1-12B yoov
< D (l) M bill + 3trco (EDig1 (G
(f.. g
g)
2
2Nic
Using similar argument, bound the other term
Epi (G. Mil
1 (Ai)))) +
3
3 Dio [L 4Tll + 3trcow EDDIS (f fi 8 ) 12
(A2)² + 12BB
Veav
215zov
Now, define:
off = EDi (.. 101--11111 + ED [l - -121
Thus, we can combine these results
2x (f
fx g. >ull + ED (Fx )m>
$ 3 D.
(f.g) - 1 + 3E [Il g) - 14 [
+ 3tea 22 |I fr. mm (A1) + (A2) 24B Aeav
Kiçov
3ffff + 31reur (2A0 + (A1)
+
(A2) + 24 Keov-
(27)
figov
Step 3: Consolidating Results. Combining Equation (27) and Equation (26), we obtain:
Eprea [Il[f.
- 1- fi. g M/)) 6(A2)² + 48B4 Mcov < 6bicov (D (f fr g.) M 2 + E ED
11' 2Ep Ill
_
22))) + (144ricov -48)BB Neov- < 18 Doft 18 (24g (A1)
Rearranging terms, we get:
E E (f.gg) - h01 < 18 (2A0 + (A,))) + 24(A2)² + (144 + 48) B
Now
+ 18 Doll + 2E [ g. M 111l3].
(28)
Step 4: Final Bound. To finalize, need to bound Equation (28). By Lemma D.10, have:
E III (1ll g)M 1-1 R( g D222) S 2 R(F g: Diø1) + 2ro
Similarly, for Aon. by Lemma D.10:
Aot == ED (f.g) 11 + ED,2 (f. g) 11
< 2E 2ED a2 (f.g) 4t' 11 21E D201 |I| [[. M
1 [12]
+ E ED,
|| 11 +2 E Ex00 |||ii h 1
RRl RRl (102)
(281)
< 2ED ([.)
11" 111 21E Dzes (I. 1''
+ 4rimo R R(P g:: D101) + 4n Ba
51

---

Thus,
18ticm offt + 2 220 [G. 7 M - 1=11²]]
(4-18+ 2) nm R Rx D (x1)) + (4 18 4) Ncov B
+ (2--18)mr Kow (EDiaa (.. g - 11] + ED ( 11)
=74 R( gx D181) + 76%cov foov B² + 36/s.ov
R g: D1s2) R(f g: D281)).
Using Lemma D.7:
R(f D182) + R(f g: D201) S R g: Duain) + 88 1Bmm T/ms
we get:
18 Doff 2 (fk g M M 11
74 R(. : D101) + 72 Rf. D Dtrain) + 288mmm/5cov B + 76 Fcov B
Summing everything up, we obtain:
E2 [|| g). - -111=]] < 18 (2 + (A1)²) + 24(A2)² + 72 Fim R(f. g: D
=Arrin
+ +668k B noov + 2880mm B + 74 R(f S. D181)
Aapx
Dropping constants, we conclude:
(f. g: D202) = Fo |ll (f.g) - 1." 11
S 2 (oo + (21)2 + Aapx) + (D2)² + Soovimm + Ba Kooo (Noor + Thm)
D.1.5 Key Change-of-Measure Lemmas
We begin by establishing some important change-of-measure results. Lemma D.9 (Change of Measure: Factor Estimation Error). Under Assumption 7 and Assumption 8, the following holds for any i, E {1, 2} and any (f. g).
EEiea [ g M < Keo D. |II (L. 5 M 12] + Yoor
EEx
(Ir
g M [2] & Keoy ss
[Il M 2| + B2
The same holds if E (resp. (x) are replaced by g := g" - o (resp. I. = - (resp. J").
Proof of Lemma D.9. We start by proving the first part under Assumption 7; the extension to the second part follows a similar approach. Specifically, we have:
Ep.g [ g 3 = Exx. [Byy.> [[. 50) [
(by Fubini's theorem)
EExx. [BDy. |I| [T, P(
Exx. (Noor EDy
[P... Neov P 3ul
(by Assumption 7)
< Exx. INem Epy...
[P( + Ncow I
(since P is a projection)
EDx, (Re Epy,
(l B² Tcovl]
(by Assumption 8)
Neav Ex (D
[Ptt.. /= + 1eow
(by Fubini's theorem)
= Keoy Ex (ll ((. noov.
52

---

The second part of the lemma follows similarly. To derive analogous bounds for g" & we note
that g" gx (I Pi)g", where I - P is also projection operator. A similar argument applies for bounding f Fx
Finally, the bounds for f* and g' are simpler to establish, as they do not require commuting the projection operator.
Lemma D.10 (Change of Measure: Approximation Error). The following bounds hold:
The risks the product distributions Dig2 and D201 are bounded by
R(s : D102) V R( g: D201)= I ricov Appo (k) ) Nooo B
Thhe risk on the product distribution D282 bounded by
R(G (2822) S Noo (ape(k) + 2Nicov Noow Neow B²
Proof of Lemma D.10. Introduce the shorthand 1 = I" and
g. Note that
r [I PWr, 8 (I Pi
which implies that both f and gx are B-bounded by Assumption 8.
Since P is an orthogonal projection, I- P is also an orthogonal projection, meaning it is self-adjoint and idempotent. Therefore, we can write:
h" (f g )
(f". /M (Pif" .')
((I Pi) gg)
((I PN) T(I (I ""f"
(29)
((I Pi)f" (I - P
Thus, by applying Lemma 10.9 and noting that F. is B-bounded, we have:
R(f B Diæ2) = Epioa I (fr M1]?]
ED g.
Bom (C5x 8 Mll + Be )
Similarly, we can bound R(f g D281) as:
R(G. g D281) Noo ED (1 )mll) Meav B².
Finally, applying Lemma D.9 twice, we find:
R ; D202) ED h (G. g. ml
Ep (E... 1|
S Kem EDi
(55 g / 1 neo B²
2 EDi
[[ g' MM] 2] + (New Tlc B2
2 ED
|l| [[5 B- k M 2] + 2ricow Noow B
(since Keov 2 1)
2 ED
11" (e g M 11 + 2 Ncow B²
2 R(E g Diss)) + 23
This completes the proof.
53

---

D.1.6 Proof of Lemma D.5
Proof of Lemma D.5. The lemma states that if (f. g) are aligned k-proxies of (f, g), then the following inequality holds:
(min or (0 (0))))22 x Aurain + Nicor + A
where A2 = max ED f - fll EDy, _ - -llim
Lemma D.5 expresses that under the aligned proxies condition, the deviation A₂ between (f, g) and their rank-k k approximations (fa g under distributions Dx Dy.2 can controlled by the error Atrain on the training distribution, the weighted embedding estimation error 4o, and k-approximation error aaxx (k), as long as the estimated embeddings (f. g) have positive minimum singular values on the corresponding modes. This lemma quantifies the effect of the aligned proxies condition.
The main idea of the proof is consider Dx -
f and EDy. llg gll separately and relate them to De. Apx [k); Arain using the properties of aligned proxies. Since the arguments for the two parts are symmetric, we focus on how handle E llg: ggl
Our aim to bound 22. We focus on bounding EDy a 1 gl. . for the bound on EDx, I 3 is analogous. Further, let us recall what it means for (f. g) to be aligned k-proxies. This means that (a) f= (1r o I g (4r g) where ip Bill x1xK - M is an isometric inclusion, and T is the balancing operator for tensors, and (b) for P being the multi-rank-k projection defined by Eisi. we have vi [K]:
range P rango(EDx... Dx
[f ff ) + rango(M((P)) S range
JD. (30)
Let V == range (x range(Epy.
TT). Since f.g are full full-multi-ranka V range (M,) DD. Moreover, range(En,, (i)
I ( T) rang
Vn.
Hence, by Lemma D.11 g (v). E (0())) V almost surely, and thus, g (w) g ( E V
with probability one. In addition, since has dimension r,, it follows that for any v V, and since or, (EDx.. I or, ( ((0) 0,
(1) T | or 10 (0)) [
EDx
Therefore
K
g gll =
(6)
(Transformed to M M-domain)
iml
(+)
((0)
Exxx1
g()) x(()
T(
(+)
g
(00
k;
1=
Tr,
K
ED
(.)
),
(0)
min; or, (1)
200))
Bk:
EDe [(g
min; or 1 200
Therefore,
Epy.alg; al
gll24 5 Edy,
EDx.. - - D']
1
ED [.. 3)
min, Cr, (1)
200)
54

---

In other words, we bound Epy, 1 - gllan by relating an expectation involving Dx,1. Now, we can further expand
(f. R
= -/. (f.g) = (.. - (ff.g). h1)
= (f f 5 - (1t M)) ((f.g) h^).
Hence,
min o, (f (0) ( -sx - -l
I D. [l fu g Ml 2| 3ED 11 (.. g Mll D.D (l.. 1111
$ $3D,, g2 Il f. 2 + 3R _xx D102) + 3R(f. g. D182).
By Lemma D.9 and the fact that || fillm M is Bobbdeded
Epi |l [[-
I. mll I Iie || - )'.g) + 4B"neew
Noor = Keov Do + 4B" Noov.
By Lemma D.10, R e D102)= I Keor R(L : Di01) + Moon 13t Neow Ncor + neo Finally,
by applying Lemma D.7,
Rff. g: D 102) < 4B* + R.f.ff. g: Derain) 4B* + Kin Atrain-
Thus, mins(or, ( ())) Epy,, g glla S 3ticol (Ao (Ao + 3 Arrain + 12B + 1ha-
Considering the symmetric argument for ED 1.f fl 34 and taking the maximum of the two bounds, we arrive at the conclusion of the lemma:
(min(or. ar. ()))) S Atrain + Koow + Dapx (k)) + Ba B" That..
This completes the proof.
Lemma D.11 (Lemma L.7 in Ref. [46]). Let Dx be distribution over X, let E = Epxiff 1, and let P be the orthogonal projection on range(E). Then Pj Dx-almost surely; that is, PDx (z) E range(E)] 1.
D.1.7 Proof of LemmeD.6
Proof of Lemma D.6. Since the t-projection operators self-adjoint and idempotent, begin by expressing the risk term as follows:
R(P g D1sI)= = ED.g.
| (z) #M g (v) (f()) (z))
Rewriting this in terms of projection operators, we have
R g D1@1) EDies
[|| [PT (z). (w) (v))
Epiel (PT (x) (x). g)) - (f()) ml)
EDios
[[] ( g" (+)
Next, switching to the M-domain by transforming into individual components, we find
R( 5: D181) = Epies 1e
Σ (a- 18
(x). ( (v)
Since expectation and summation are interchangeable, we can separate the components as
K
R(E 5: D101)= = Σ Epior
(a- p p (x). (0))
55

---

Using the trace operator to express this in matrix form, we get
K
R( :
D101)
Σ
EDx. (I-P")
{ [ (x) (w) (o)))()
(x) (1- p= LL
JEy 1 1 (2)g (v) T]
i=1
Since EDx.1 we obtain
(x)
(x) = (M( and
and Edy,1 g
(v)) (v)g (2) = -Mi
K
g :1001)
=
Σ Tr (1-P()) ((is)) (0
(I-P
M (MM())))))) (o)
Finally, by summing over the eigenvalues of the transformed covariance matrices, find
Σ E > ( (M(
g D101)
-tail (k).
i=
This completes the proof.
D.2 Exeess Risk Bounds for the ERM Model
In this section, we analyze the ERM algorithm for multi-output regression under CDS. Our primary objective is establish rigorous upper bound on the excess risk R. g Bem" DDesst of the ERM
solution (Cem Bern
obtained by Model (5).
Recall that Theorem 4 states the following: Given vectors r = (rt) E NNK a (at)
K E RK
Cum
(2()) RKK CDia: (c))
K D R where a, 2 1, and {( (6)
Dios
for all
E [K], suppose the learned embeddings (Cem 8ggmn are a-conditioned and (Emm: ED accuurate
(0) satisfying Pioo S 0 /(40r) for all i [K]. Then, under Assumptions 1 and 8, the excess
risk of the ERM solution on Diest can be bounded up to constant factor = poly (Ficov Vissts Kun) with probability at least 8:
2 Σ 03 + (r) + (r)) + or (rai)
ar o²
+ +r
A
o²
statistical error
approximation error
where max, N (r,c)= N(F=))((Fre((B). -1l NGG. 11,0).
min, > O. A.
(r, 2B/n) log f)/n with
To prove Theorem 4, we begin by applying Lemma D.2 with the multi-rank parameter r = (r......r) R where r is the tubal-rank parameter of the embeddings in the ERM formu- lation (5). This lemma provides general decomposition of the excess risk into several key error terms, each capturing different aspect of the learning problem:
R(fam 8.m: Drest) S.
A
o² (Aupx + Ao + Atrain)
This decomposition lays the groundwork for subsequent analysis, as it allows us focus bounding each error term separately.
Next, introduce set of conditions on the ERM solution to ensure its quality and enable more refined bounds. Specifically, we assume that the learned embeddings (fum B are a-conditioned and (Eum, (
formalized in Definition 17 and Definition 18, respectively.
Moreover, we impose constraint on the rank r of the embeddings, requiring that r < ((00()) for all i [K]. Under these assumptions, can leverage the powerful Lemma
56

---

D.22 to obtain more refined bound on the excess risk:
R( R(ferm Bern' Drest)
Σ
R
2(0) Corm: Berm: Drest)
K
(<D ) (Em (a + (tail) (1) (rr))²
Disi )² (0 + (tail (r))) (ta))) + +ag
S.
(σ,
1=1
S. r emr maxfas}
,² Σ6 (o (tail
1=1
Dioi ) Σ (cm) E, (tail) (+) (r))²
+ max(a:
(min, o, 20
err + (tail) (r))² r err ceri
.
(tail)(r))
S. r4 errisi + max(a;} 7² |2 + (r)? + maxfas}
(min; o, 30
; D D181) denote the accuracy Dirain and 1191 respectively. This bound reveals the intricate dependencies of the excess risk on various problem parameters, such as the accuracy of the learned embeddings (erriş) and errmm). the conditioning of the true embeddings (az), and the spectral properties of the embeddings (g/+1 (r), and (r)). However, to make this bound more explicit, still need control the error terms erTim and erT1@1-
where erim R(form Bem: D Purain) and erT1g1 R B
To this end, we use Lemma D.12 below to establish high-probability bounds on the excess risks R(fer Bemi Pursua) and (f Bemm' (1@1) of the empirical risk minimizers (fem Bem) ) These bounds are expressed in terms of the true risk R(" Derain). the tail sum tril and the covering number N (r,2B/n), which quantifies the complexity of the hypothesis class. By carefully balancing these terms, Lemma D.12 provides the key ingredients needed to control ertmm and e1f
Lemma D.12. Under Assumptions to 5 and 8, let (L. g) E Fp Gy be empirical risk minimizers i.i.d. samples (I Us. 2.) ~ Derain- Then, for any 8 E (0, 1), the followings hold with probability at least
368B4 (M (r, 2B/n) + log ?
Rffmm Bem' D Durain) S 2R g: Deesi))
11.
R( Bam" Derain) I tail + 368B* (r, 2B/n) log 3)
n1
R(fer Bamm D181) S Kim 2Kagpx tail + 368B*(AH (r, 2B/n) + log ()
where ((,,))=((Fr,/(/ (lxo) (()), bl,0)
Proof of Lemma D.12. The lemma is proved as follows:
The first inequality is direct consequence of Lemma D.19. Here, take the function class = F, x Gr. Moreover, by Assumption 8,
sup sup (f(x), g(y)) (f (z). (v)) 2B² geg. 2.2
Then, we can choose U = 2B2 and e 2B2 /n in Lemma D.19. Note that, according to Lemma D.20, it holds that
N/ 2B 12.B/nnl1l1 1n.11-11aa 11x) SN( 2B/n, (1xo) - BB/n|11 lloo).
57

---

The second inequality uses Assumption 8 to bound R( 5 Durain) I Kapx g 2 and noting the fact that (ppp. 5 Di@1) = (p) by Lemma D.6.
The third inequality uses Assumption 2, incurring an addition factor of Kim-
Now, we can proceed to derive more explicit bound on the excess risk.
Proof of Theorem 4. By combining the results of Lemmas D.2, D.22, and D.12, and introduc- ing some convenient shorthand notations (a = min, o, (()( 0, a = max, ag, and An =
8 ( (r.2B/)//) t),, we arrive at the following bound:
R( B.mm Drest)
S. errisi + max(o:} 191,,, 1l (tail, (r))² + max (r] frrffi + erri + (r)) (min; of 37
S. pd (r) 1er+1 +r² tail (r) (NN (r, (r,2B/n) r
log
n
+ 9b (r)
(BN (r, 2B/n) + log ?)
+a
n
ar tail; (r)
+ An + ar
S. r4 (ri + ar² E (zx10)) + + (T)
o² A
o²
statistical
approximation error
Limitations of the ERM Model. regression under CDS:
The ERM Model (5) faces several challenges in multi-output
Inflexibility in adapting to spectral decay patterns: The hypothesis classes F, and G, in single- stage ERM do not account for varying spectral decay patterns across different frequency com- ponents induced by the transform (-). Consequently, the learned embeddings may fail to capture distinct decay characteristics within each frequency sub-domain, resulting in suboptimal approximations.
Lack of localized learning and complexity control: The ERM approach learns the embeddings
frrm and å globally, disregarding the unique properties of each frequency sub-domain. This global learning strategy can miss the nuanced decay variations across sub-domains. Additionally, controlling the complexity of F, and G, through global covering numbers may be too coarse effectively capture these variations.
Limited generalization performance: Due these constraints, the single-stage ERM approach may offer limited generalization guarantees for multi-output regression under CDS. The embed- dings may struggle generalize to new feature combinations, especially when spectral decay patterns differ significantly between frequency sub-domains.
D.3 Excess Risk Bounds for ERM-DS
The ERM-DS algorithm is introduced to address the limitations inherent in the ERM approach. This ERM-DS algorithm. The algorithm consists of four main stages: overparameterization. I-covariance estimation, dimension reduction, and distillation. We analyze each stage separately and then combine the results to obtain an overall generalization bound. We first give detailed version for Theorem follows.
section provides comprehensive analysis
58

---

Theorem 6. For any Ti,out 2. poly(C/o7)) and c, > O, there exists choice of octt 0, p S+ (min; rmm for some universal > and sample sizes n4 satisfy Condition 8, such that with v4 r reut and μ B² /n,, the ERM-DS algorithm satisfies with probability at least 1 8:
K
((2,)) (x) *M B (v) 11' v)1l) S. 2 C
C2
Σ (1 + 7/ 3 Mr
Our proof follows the core idea and approach of Theorem 6 in Ref. [46]. The main steps of the proof provided as follows.
Analysis of Step 1 (Overparameterization) We begin with precise analysis of the first phase of the double-stage ERM. We first show that after the first step, we have the following upper bound on the excess risk Pirain and D1091-
Lemma D.13 (Guarantee for ERM-DS, Step 1). Let (f. be the obtained t-embeddings obtained via Step of ERM-DS on i..d samples (I1.) M1.j Z1,)) ) ~ Dtrain. Then, for any 8 E (0, 1), the
followings hold with probability at least 5:
368B [ M (p, 2B/11) + K Klog 2K
R(. g: Dirain) S 22R(L, ; Derain) +
11
( g: Dirain) s 2Aapx tail: + 368B* A (1) (p. 2B 2B/n /n + K log 2
T1
368B'(E 100 (p. 2B/mi) + K log 2K 8
R[L. g; D101) Kun
2K taill))
71
where A0 (p.c)) NN c/(2)). -V( e/(2B), 11
=
This lemma establishes upper bounds on the excess risk of the initial embeddings (I, g) obtained in Step 1 of ERM-DS for both the training distribution Drrain and distribution Dist. It refines Lemma 1.12. The main difference from Lemma D.12 lies in the covering numbers .P (p, 20,2B/m m)) which here relate specifically to the function classes H() and 3 in Assumption 9, rather than to F and G in Assumption 8. The proof is similar and leverages techniques from statistical learning theory, along with the specific properties of the function classes (() and 5(()
Proof of Lemma D.13. As R( Σ R D), prove the result by upper bounding the excess risk in all the transformed sub-domains. For all i E [K], let g0) J x Sp be empirical risk minimizers on nı i.idd samples (æ,, By =(()) ~ Durann Then, we will prove that for any 5 E (0, 1), the followings hold with probability at least 1 5/ K:
R (00; Dirain) S 21(
(+)
(0, Dirain) + 368B'(A (p. 2B 2B/m)) log 2K B
(1) (p) 368B4( (AF (8) (p. 2B/n + log 2K 5
R (0) -00); Derain) & 2Kapx
20, ; S Kam ( (p) 368 ( (p, 2B/m)) + log 2K
(0)
(31)
n1
The first inequality is a direct consequence of Lemma D.19. Here, take the function class = ( x (()) Moreover, by Assumption 9,
sup IK (x) (v)) F (x). (r))g)())))) (1)) < 2BB
sup ps P 2 e
a.y
59

---

Then, we can choose U = 2B and = 2B2/n1 1 in Lemma D.19. Note that, according to Lemma D.21, it holds that
N 2B2 //. -lolllo S B/m 1lw) NV B/m1. I| (loc).
to bound R( (1) x+((), Derain) S
The
second inequality
uses
Assumption
Rapx R
(8), D101), and noting the fact that R (0) D101) tail.
(1) (p).
The third inequality uses Assumption incurring an addition factor of Hum
Analysis of Step 2 (t-Covariance Estimation) and Step 3 (Dimension Reduction). Next, analyze the effect of the t-covariance estimation and dimension reduction steps in ERM-DS. Let (f. g) be the empirical risk minimizers from Step 1, and let Q, be the balancing projection onto the t-eigenvectors of M Egg) where i = (f1..... fx) E NN We define the following effective error term in each transformed sub-domain:
(p, (p,n1,,)) 6)2
(p) (368 + 2) (MF() (A (p, 20/m)/ + log 6K à
2kapx tail (1)
Vi Vi [K].
: Kim
Tb
To select the rank i for dimension reduction, we use parameters Ouu = ( E R and Teut = ( E K Motivated by Definition F.1 in Ref. [46], we consider the following "good" event Expec (i, cut, Teut), under which the choices of cet and reut are sufficient for finding suitable ranks F; for all the i-th frequency components (vi E [K]).
Definition 20 (Good spectral event in all the transformed sub-domains, adapted from Definition F.1 in Ref. [46]). For parameters cut = (Or,cut) K E TRK and reut = ( E NK used in Step of ERM-DS, we define Expex (f,, Tcut; Feut)) the event that the following inequalities hold in each frequency component E K]:
3 0. 2 4 L.cut oft1 S 30,
84 - Fit1
3ri
taill )** (f.)) S taill f1x (Fiteut) + 90 outt
tail (1 (fx)² < 18r2 18u oeau + " (ur)
The following lemma shows that under appropriate conditions, the excess risk of the reduced-rank embeddings (f. Q, *M g) can be bounded in terms of the effective error 200 (p, nı, 8). The proof involves a delicate balance between the eigenvalues of the estimated and ground truth covariance operators, as well as careful control of the approximation and estimation errors.
Lemma D.14 (Guarantee for Double-Training, (oi,eu) ) and Feut = (Fi,eut) f=1 satisfy ai,eut E [20 36 oi.b for all i E [K] Assume M1 2 2 2, ni 2 max; (B2 (p) n1, 5)2 < (6,r for all E [K]. Then, with probability at least f6, we have the following upper bound on the excess risk of hea((x y) to the multi-rank-i ground truth hद (G)T *M g on D1s1:
Training, Step 2 & Step 3). Suppose the parameters deu.. 2
f B² ///n,, n2 2 722 max; (r² In 1og(24PK/O) /8), and
R (L Q # g; D101) S 3000 r.ctt 2 (p. np. 8)2.
Moreover, on this event, supz,
1 (z)
(v))
S v 2n B² and Expor (f, Tcut. Feus) holds.
60

---

The derivation of Lemma D.14 utilizes Proposition F.2 from Ref. [46] across all K subdomains in parallel. This approach extends the proposition's application our specific multi-output regression context. As the adaptation follows directly, the detailed proof is omitted.
Analysis of Step 4: Distillation After Step 4 of ERM-DS, we obtain embedding (Las S.n satisfy the following lemma.
which
Lemma D.15. Suppose it holds that llop I 2m,, Vi [K]. Then, with probability at least P.. 1 - (3K), the regularized risk in the i-th frequency component satisfy
z(0)
R (0) 20. ds Eds Dtrain)
200 Bis
(101)
< Dappxtaily 10 (r:) 3
(0)
10) + 368 11+
2
nins
B B* log(12K/8))
[nd
114
V1
This lemma provides upper bounds on the training and testing risks of the final embeddings (Les 2
in terms of the tail sum tail (ri), the excess risk R(() number A n4. The proof of this lemma relies on a careful decomposition of the excess risk and the application of concentration inequalities. The proof of Lemma D.15 is provided in Appendix D.3.
( (0; Disi), and the covering
We now provide a sufficient condition for parameter settings and sample sizes to improve the bound Lemma D.15.
Lemma D.16. Suppose that the parameters in ERM-DS are chosen as μ =B²/r /2/ and other parameters (p. cut, ). the sample sizes n1,..., 14, and parameter = ( T satisfy that for some C S. Vi E [K]
Ji,cut
22
Ticus 3e
28 811. (p) S
Loou and p 2 Cri
n1 2 + C max 1, Bd) max; to Lo (1 (p. 2B/m1)Bmmm + log( K/8))}.
n2 2 722 max, (ri In log (24pK/8).
n4 2 ni max (28())3)
Then, with probability at least 5, the event Expec aeut, Tent) in Definition 20 holds and
R9
((0 =(0) Lis Bak Dirain) 8 (00
(Pe) (Lt ; P181)
(00) ((1)
S. tail () (Fi,ent) + Ficcut ofout + 2
2on taill (p)
B BM 28,, m1) log(K/)))
300 Ba (M 2B/n)/ + (Kg(K/
113
7h
Lemma D.16 follows from the application of Proposition F.1 in Ref. [46] to our context. The steps align closely with those in the referenced proposition, so the detailed proof is omitted here.
To ensure the successful application the ERM-DS algorithm, we must carefully select the parame- ters (9) to control the error terms. However, before diving into this crucial step, us first establish a refined set of sufficient conditions for the algorithm parameters and sample sizes, which will serve as the foundation for our analysis.
First, let us focus on the algorithm parameters, as outlined in Condition 7. We require that the parameters Fi.cut: Jieuut and p satisfy a series of intricate relationships. These relationships, expressed in parts (a), (b), and (c) of the condition, ensure that the algorithm's components are well- rell-balanced and can effectively capture the underlying structure of the data.
Condition (Algorithm parameters). Let 61 be some unspecified parameter satisfying S S+ We stipulate that the algorithm parameters (ai,out cit p) satisfy
61

---

(a) ri,cut 2 G11 and tail (ricat) S 2
Leue (or
G,1
(b) t (0) (p) 6x,1 F,em
(c) Jiout E [20 Tic 3e 011
Next, we turn our attention to the sample size requirements, as specified in Condition 8
Condition 8 (Sample size conditions). Let Cr22 be some unspecified parameter satisfying C12 S 1. We stipulate that, given 8 E (0.
The supervised sample sizes of nı, ng satisfy
K n1 2 p+ Bd max 100 (p.2B/nn) + log 5 )ri, )rijcut
K
ng 2 (G (ri,out, B/na) + log 8 )o
The unsupervised sample sizes n2, n4 satisfy
T22 2 722m (2ooggg22///00) (r, n4 n1ng max(ri
state the main result of our analysis, as presented in Theorem 9. This theorem provides a powerful guarantee for the performance of the ERM-DS algorithm, as measured by the risk function R(a.. &.s Dtest). The theorem asserts that, with high probability, this risk can be bounded by a sum of terms that depend on the parameters Ti,cuts Ciout. and the tail sums of the singular values, tail and tail (+)*
With these conditions in place,
Theorem 9. Suppose the parameters of ERM-DS satisfy deut. Feut, P. sample sizes T1,.... R44 and g(t) = rieew μ = B² /nn and fix a probability of error E (0, 1). Then, as long deut, Tout P satisfy Condition 7 and 11.4 satisfy Condition 8, it holds with probability at least 1- 8.
tail (0) (ri.cu:)
R(fass Bisi ; Duest) S.
2
iienut jeue + (Fi,cut)
(oi,cut)
The proof of this theorem relies on a careful analysis of the error terms and their relationships to the algorithm parameters and sample sizes. By leveraging the conditions we have established, along with advanced techniques from tensor algebra and empirical process theory, we can derive the stated bound on the risk function.
Proof of Theorem 9, Our goal is to bound the generalization ertor of the ERM-DS algorithm in each subdomain after transformation:
tail (rr, (o
3(0) ds Drest) S. r2 oe + tail (ri,out) )
Vie [K].
E:ER(()) (r.
The key to the proof is to leverage the properties each step in the algorithm and recursively bound the generalization error. While the overall proof strategy follows the ideas from [46], extend these results to the multi-output setting using tensor algebra, which requires handling the additional complexity introduced by the tensor structure and the Hilbert t-Module framework.
Step 1: Based on Lemma D.22, if the learned embeddings (+))
Has have risk (200) on (6)
(())
the training set Dusin and truncated risk (eb))g) )2 on distributio D101. and satisfy EDg1 S (+)() min(ō, (0n4,,.00/400...0 /40f,, 0 /4). then their generalization error the test distribution Prest be
62

---

bounded as (with a, - 2) for all E [K]:
R
((0) Duss)
(P9(C)) Dig1 ) +Z + tail (1) (f:))²
S+ (1
(107)19))))) +
(07 (8).
Step 2: Recall that in the ERM-DS algorithm, we choose fz ri, and ((() r rout- In this case,
long ((t) $ <min(87 (A0riit 87,000 /4], obtain for all E [K]:
Dioi
R do
(
20), Bik (rest)
(C
((2)) tail (+ (A:))²
S+ 100 (c ) tail (f:) ((0
Step 3: Conditioned on the occurrence of the good spectral event Espeo (f, cuts Fent) (Definition 20), we can further constrain the generalization error using the spectral properties provided by this event:
( Bus ; S+
(10) Dior )2 (((0)) ) + ri,ent (oi, (ricct)(ri (1 DiOI )2 Fo roout + tail (Fi,et))
(F)
(oi))
ii] Step 4: Substituting the specific forms of (Fim ) and Dia ) from Lemma D.16, and leveraging the high-probability event described in the same lemma, we can deduce:
Dies Diei 1 s 20) (E )2 )
S. tail!" 1* (rreat) + Ti,eu eut + r tail tail" (p)
BSM 2B BBBm)) - (og(K/0)) +
log(K/0) K/)))
S20? fout under Condition
S (tiil""((ria + o s,cut rf tail (p). (p).
This step involves balancing the algorithm parameters, sample sizes, and spectral decay rates across all sub-domains to ensure that the error terms well-controleed.
Step 5: Substituting the above inequality into the bound from Step yields the result stated in the theorem:
tail (ri.eut)2
R
x(0 Edd Drest) S. rccu o. + tail (ri,cut)
(oi,cut)²
provided that the small tail assumption tail, (* (p) S (oi.ea))
satisfied and that the conditions on
r
the algorithm parameters and sample sizes in Lemma D.16 hold, which are ensured by Conditions 7 and 8.
Lemma D.17. Suppose Assumption 4 holds, and that the algorithu parameters di,eut, Fi,cut, satisfy
Ji,cut (+) and the following (feasible) constraints
7+302 I127 jjcut
Tijeut 2 (eC.,,,,,,CC00000)
p G1
r.
Ji.uut 2 2Cr -(++%)
Then, Condition 7 holds and
ERB (Ti,cut, Ji,ttt S 7 + 21 2
(32)
63

---

The proof closely follows that of Lemma E.2 in Ref. [46] and is therefore omitted. This lemma establishes the relationship between the algorithm parameters (o ( p) and the error term (3) (Ti,cut, oi,tt), which plays a central role in bounding the excess risk of the algorithm.
ERRET
Proof of Theorem 6. Our goal is to achieve the desired accuracy level To this end, we let Cieuut max maxx(2Cr,,ni (2Cr, (117)) _e/(Kk//rr..u
We then invoke Equation (32), absorb absolute constants into the S. notation, and arrive at the following bound:
K R. Bas Drest) S. e² E( 3r
(33)
We confirm that both Condition and Condition 8 hold. Specifically, Condition 7 is satisfied as Ti,cut is large enough (as a polynomial in C/a7,(0) and remains within a constant power of Ti.cut- Suitable sample sizes ny, n2, ns, ng ensure Condition leading to the result by Theorem
D.3.1 Lemmas From Statistical Learning Theory
Lemma D.18 (Bernstein inequality [10]. Let Zi,..., Zn I be i.i.d. random variables with |z|| S M and [ar[Z:] < o². Then, with probability at least - 8,
20 log(1/6)
M log(1/6)
Σ 2 Z--BZ 1=1
n
3n
Lemma D.19. Let & be a function class with functions @ W - R& and let o² (w) be a target function defined on W. Assume there exists constant U >> O such that sup supse* (lo(w) o² (w)]l I U, and let N( (,,,] || |loo) be the e-covering number of Φ. Let be a joint distribution on W x I such that ||z - x0 (w)ll2 S U and [[|[[]] = =w"(w.. Define R(Ø) == EE--D -Ew-Dlll(w)) o² (w) [. in(d) == E ((((w;) - z; 112 and (w) = En(() Lm( Then for any
5 E (0, 1), with probability at least 1 5,
any & Φb satisfy:
R(ő) s R((O) + + 1)0 (l,))/)))
Va 0.
(34)
n
all empirical risk minimizers E arg mingeo (d) satisfy:
R(O) < 2 inf En((>(w) (ww)) 92U (ogg2N(0, U/n,, (bx)) + log 2)
(35)
Proof of Lemma D.19. For each @ 4 first define the loss function Ls W R*
(u 2) == [l@(w) - 2 =112-
Also, define the excess loss function A W x I + R as
Ala 2) == (s 2) ts- (w, 2) (1 =113 [1o"(() =112.
We then bound the excess loss function as follows. For any & E + and (w, E W x R²,, we have:
Alp =)
[1 - =113 1 =1121
[| o² (0((w + (w) =11 - [w0 - 2
(1))(w) - (w) + 2(((w) - o (w)) - 2)
S (lo(w) - 6² (w))l + x² (w))lllll (w) =||2
< U2 + 212 = 3
64

---

Here, the first inequality follows from the Cauchy-Schwarrs inequality, and the second inequality uses the assumptions that w suppeo lló(w) 6"() ll2 I U and ( U.
Next, we construct an c-cover of Φ. Let e > 0 be fixed. By the definition of covering numbers, there exists 6-cover & of & under the so norm, such that Φel A
c, || ll This means that for every ó E 2 there exists d, E 2 such that ||ó - lloo S e. We further bound the difference between the true and empirical excess risks for functions in the cover. For each o &.. define (Øx) ;= Alg. (wi, zi). Then we have: (a) (6)) = B( (w, [w, =: R(o.), (b) (o.) I 3U almost surely, and (c) E| ) S -U2R(()))
By Bernstein's 's inequality and union bound over o., we have with probability at least 6/2, for all de E 4.:
1 7
2 (U.. (4g(4 2.1/6)
U (og(4/2.1/0)
R(ó.)- Z((de)
Σ
S
71 i=1
n
n
lo) (D, e, 1l0)
U log(oN((,,,,,.. || 1loo)/0)
+
n
n
We then extend the bound to all functions in Q. For any & E 4, let Φ. E Q. be such that fé--bella- S Then, we have:
R(6)- - A Aa 2i)
1=1
1
Σ Z((6.) - Σ A Slllws (w; 2i)
< (R(0) RK o0)l + 1((b))
Z((o.)
+
1=1
18U2 1og(4N (1 e, 110)
+ (Plog(NN((,. Il 1l 3/0)
< 2 +
+ 2Ue
18U R(Φ) log ( 1/0)
U -1x 4Ue.
We will choose and simplify the bound. Set U/n. Then, with probability at least 8/2, for all á E $:
R(6)
Dls Des 2i)
n
1loo)/0) (8U'R(0) (og(4N(())) U/n, 1- 1100)/8) (2log(4N(Q,U//n, (l/oo)//)
4
n
n
m
1802 R()) log( (AN U/n || 1/0) 5U3 log(NN U/n, |1 11x))/0)
n
n
a (()) + (9/a + 5)U² log (AN U/n (l
5 2
for any a >0 0.
Next, we can bound the risk of the ERM solution. Let Ø E arg minger R(6) be a minimizer of the true risk. Then, the event of the previous step, we have:
R(O) R(Ø)- R(O) R., + (o) Ro) + (0) - R(Ø)
< (R()) - RT, + (o)
< 2 (R(() + +(()) +2 (9/a + 5)U² (og U/n, || 1lx))/8)
< al((0) +2 (9/a + U (M U/n, ll 1/0)
65

---

Here, Rn( Ei= Alp(w,, 2:) is the empirical excess risk, and the first inequality uses the fact that ( - 0 since @ minimizes the empirical risk. Choosing a 1/2, we get:
1 R(6) R( - 2 R(0) + (oolooo(4NN 4 U/n, 1lso)/))
Rearranging the terms, we obtain:
R(0) & 2R( + 92U2 log(NW M/n. |lx=//5)
2 inf ED((d(w) o0 - (w)) 220 (og(4NN0, (0,M/n M/n,Il 1loo)/0)
PEB
Lemma D.20. Let F and G be classes of embedding functions, where { E F maps from arbitrary domain X' to a Hilbert t-Module M and g E 9 maps from an arbitrary domain y to M. Let H be a class of functions of the form h( y) = ((y)) M. where E F and E G. Let Ny(() denote the e-covering number of F, F,(()) denote the c-covering number of g, and Nu(c) denote the e-covering number of H. If there exists constant B such that for all f E F, g. e. X, and y Y, have [[f(()))) < B and (lg())]lM B, then for any O, the following inequality holds:
NH(()) N
N
2B
2B
Proof of Lemma D.20. Let (f.................. . NZz) be an e cover of F and {g. .......... .Ng be an 2B 2B
cover
of G, where N5 = NNF 2B and Ng = Ng )2
For any & E H. there exist f E and g such that h(xx,) y) ((()) By the definition of the covering sets, there exist and g, such that for all X and y V. have [[[()) (x)lMM S
and ig y) B, (V)llM S 2B
Now, consider the function (,,(2,)) (G()), (1)) We have:
|1(11, v) Bey (x, w)ll
= -
= [f((() (()). -g, (1),mll
< [[(()) - [())
(v))vlll
< [[[(v) - [[+))l]]B[ [())lM (g(v) g (1)
S 2B
B +
2B =6.
This shows that the set (h.g
: 1 < N 15 S N₂) forms an 6-cover of H. The cardinality of
this set is Ny. Ng- = N 2B Ng
2B which implies that NH(e) & N 23 Ng 2B )
O
Lemma D.21. Let F and G be two classes of vector-valued functions, where E maps from an arbitrary domain X' to I²' and E G maps from an arbitrary domain y to RR.. Let H be a class of bivariate functions of the form h(x, y) = (f(x). gyy)) where f E and g E G. Let Ny(c) denote the e-covering number of F, -N((c) denote the c-covering number of G, and Nx(c) denote the e-covering number of H. If there exists constant B such that for all f E F.F,F g E G, x E X, and y E Y. we huve [xx]] < B and [[ S B, then for any >> O, the following inequality holds:
Nn(e) < N
E
Ng
E
2
2B
Proof of Lemma D.21. Let {fi,.... fNy, be an 28 cover of F and 191....,9N. } be an 2B cover
of G, where N, N (2B) and Ng Ng ( )
66

---

For any E H. there exist f E F and g E 9 such that h(x, y) = (f(x)) By the definition of the covering sets, there exist fi and 93 such that for all x X and y E we have [lf(() f((x)) - 2B and (ي و (v)l < 2B
Now, consider the function (1 v) (fi(z) We have:
1h(x,1) hig v)
((f(z),(()) -
1(f(x)) - ((())))())))(((()))) - -)(x))
1((xz) - + - -3(())
+
115(xx) -f(x))l -[(x)]l-[[[(v]]||++ (1x(v)))++ I[A(a]] (1(()) (1)l
s 2B
2B =
This shows that the set {hij.
:1 :15 i < No.1 S Ng) forms an c-cover of H. The cardinality of
this is N2. Ng- N/ 2B NNg (28). which implies that NH(()) s N (28) Ngg (2B)) C
be a class of Proof of Lemma D.15. Let 4b : {2,, v) + (f(z), g(y)) ((()).(()) e 3. ) bivariate functions for each i [K]. We define the following target functions:
(x,)) r (z). (.).gt(()))) (w))
(z, = (x)). g (v)),
for all E [K]. Let D3 be the distribution of (I,, U, =) Deran, and D4 be the distribution of (x', v/, 2²), where (u',2/) ~ Diœi and z' =0),) (x'; s/). We compute the following bounds:
sup max | v) 25. (r. .) s 2B²,
a.y dE
sup max | v) - 300 (z. w) < (1 + 22 B².
s.y dE
According to Lemma D.21, the covering number of d satisfies
llae) s (NAA, (U((Bn), ll
(l.) U/ Iloo).
We define the following covering numbers:
Ny.,s = N(((()) B/ng, (1xe) NC B/ng, |1- 11 Ny.,, : N(#() (1 B/n1 || (loo) -V( (1+ /211) || lloe).
For (3, 4), let Rs and i.k,gy Pu... denote the corresponding population and empirical excess risks as in Lemma D.19. By applying Lemma 1.19 with a = 1/2 and a union bound over all i E [K], have with probability least 6/(3K). for all & E T:
[R((0) Risnn (0) / Ro( + (9-2+5) (2B2) Kingg log( 12K/5))
71
(Ø) Ra,n, (0)) < R4(0) + (9: 2+5 5) ((1 22n1) B log 12K/0))
n4
Now, define the combined population risk R (0) = Rg(0) + (000 (o) Let
o E argmin La La, (0) - (7(() Li,,, (0)
argmin Ro (0) + ((() Rl (b)
dea
67

---

be an empirical risk minimizer, and let Φ E argmin dep (Ø) be a population risk minimizer. Then, have
RBco (ल) RRpc
4B* AB,,, + log(12K/8))
< 4 RBio (0) + Rew (b) + 299 2 2)
113
(2 + 4m1) ( B² (Nriin
+ -ollooo////0
29 2 5)
n4
$ 2 Rio (0) + 184 1 25 n1n3
Ba (Morin + +log( (og(122/0))
n4
n2
where the last inequality holds because n4 2 ny (2x(() ,3), Vi E [K] implies Nrins 2 Nr..ag.
Rearranging terms, we get
1 2000
Ba + (12K())))
Reco (0) s 2R (Ø) + 368
n2
713
To conclude the proof, we bound the terms Rgc (d) and Reco (d). First, for the population risk minimizer ã, we have
Ryco (Ø) = inf Rom (o) DE
= inf
(1 Derain) + 800 Booz (
(1 x
(1) Derain) EDie g
I Kapx R R00
(0) D1m1) 800 EDiol
1
800 5 )
Kapx tail (i)+ (rx) + R
20 Di01).
Second, for the empirical risk minimizer &. we have
800)
R10 (00 2(0) Derain) +
R(0)
200
Disi)
2
[r.]
((0
- f..:: D ) +
E ED
(0))
2
< R(0) (10) 2000 D
(raiu)
E
+ +E
-R( + 0 R4
Ó. D1s1)
= Rgo (5) 8 R())
(1)
g Dio1).
Combining the bounds for Rec (6) and Rom (Ø), we conclude
200 Drrain) 200
(101))
tr
< 2Km tail (1 (r:) + 3510 R
G..gg (1)
(n)
+ 368 1+ 2000n
Ba BA
(Mrrna + l1g(12K/6)
n4
n3
68

---

which completes the proof.
D.3.2 A Lemma on the Risk Bound for t-Bilinear Combinatorial Extrapolation
We now present a lemma on the risk bound for t-bilinear combinatorial extrapolation. This bound depends on the upper bound ém on the risk of the learned embedding (f. g) for the training distribution
D Prrain the upper bound f18 the risk for the top-block distribution D1ø1. and g,
Lemma D.22. Given vectors = (ri) E NK a (ass) RRRK 6a (c ) E RRK and
K
1ii (ED101 ) ER*, where a; 2 1, Gm Dis1 for all i E [K]. suppose (f. ( are
(2(i)
(i) .(1)
a-conditioned and (Eum, EDi01) )accuraee I | x1x embeddiings of tensor-multl-rank r, where
ri S (6) (400 ffr+ > 0, then
[00 ; Drest)
((((()))) (
(Em)) +tail (r:)²
S. ( )² a0i + (ri))" + as
(o
Drest) for each i-th frequency component of the learned embeddings on Dest. This bound depends the embedding rank rs+ PPe conditioning parameter a, and the singular values and tail sums of the true embeddings. The embeddings must be a-conditioned and (fim: (Di1) (-iee)-accurtee Jaccurate, with r; them to the multi-output setting using the tensor algebraic tools developed in our work.
Lemma D.22 provides an upper bound on the excess risk (1) g 00;
accuracy parameters <(t) and u(t)
limited relative to (() (u()) /ED10L"
Proof of Lemma D.22. The proof closely follows the arguments in Theorem of [46], extending
Lets ($1,
ssk)
N and (ě ,(k) be such that
inf
R(0 (1) 30), DIS1) = ED, en ((),0)) - (P: (0 P. g.g.r. 13
(0)9)
(36)
M Σ 18 )60 lop
(37)
407
where P", is the projection operator onto the top-s, cigenspaces of M (1)
Suppose (f. are full-multi-rank- Then there exists an index vector k (kI, ,k) NK with k E [min(rs, 8; 1}} for all i [K], and functions f: M and g y - M such that (f. g) are aligned k-proxies of gf. The construction of (f. (f.g) follows the same steps in the proof of Theorem 8(a) in [46], applied to each component
(()) separately. Specifically, we set
(() = (Ir,
g
(tr,
where 4r .T + M₁ a t-isometric inclusion, M; is the i-th component Hilbert space of M, and (() the balancing operator for (1)) ())) as defined in Lemma 15. The index k; is chosen as the
20.(0)
largest integer in [min(ri, 8 - 1}} such that ă
xx(()) 2 min The existence of such a kktt
k; is guaranteed by the gap condition (36) and the fact that (f9)) (.))) are full-rank, as shown in [46].
With the aligned proxies (f. g) constructed, we can bound their error terms using the same arguments as in the proof of Theorem 8(b) in [46], applied componentwise. This yields the bounds
ka) tail ( (kx) & tail (1) (s..) + कर + ()))
A (
g k:) S tail(* (s.) + (Vr + 27); + +,
69

---

Finally, suppose ? S (1 a ( (0) for some a; 2 1. Then, as shown in the proof of Theorem 8(c) in [46], we have or, g )2 (8r, /a;, and hence (f. g) necessarily full-multi-rank-rr
Combining these bounds and applying a refined error decomposition each i-th frequency component induced by the transform M-) in Eq. (1), we arrive at the risk bound
R
2 S Hoov
Ai( ,gg +
(tail) + Do(!" (1) .g ,k))) + Kico Nim R p 00 -erasn))
or, (1)) g00
(((E)) + (cm)) y1 + tail (1) (si)2
S. s/2 + +a,s?(07;
tail (s,) tas
(0%:1))32
(((()) ri ) (É + tail (1)
(r:)²
S. ( Dil + ani() + tail 0** (r:)) +a;
2
(o;
Here, in the last step, we used the fact that S and é S (0) factors into the S. notation. This completes the proof of the lemma.
Dior' and we absorbed the constant
70

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The paper introduces a tensor spectral theory approach to address multi-output regression challenges under combinatorial distribution shift (CDS), marking a pioneering theoretical exploration in this area.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: It acknowledges several limitations: the potential inadequacy of the spectral methods against real-world data complexity and the uncertain robustness of results from controlled experiments. We suggest future research refine these methods fostering the development of more effective solutions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
71

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The paper provide the full set of assumptions and a complete (and correct) proof for the theroetical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer:[ Yes]
Justification: This paper presents a pioneering theoretical exploration of multi-output regres- sion challenges under CDS using generalized tensor spectral theory. Since no existing algorithms address these specific models, our experiments use numerical simulations with synthetic data to validate preliminary results. Details are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
72

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide the code for our conceptually validation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/ Mublic/guides/Coree
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips wiips.cccppppp wwtppcccpc/ccccccccccccccccc cubbic/guidess gwwggeiideee/eeee /eddeSSuu wwwiiisssoooiiiiieee cesoonncyyy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We show the experiment details in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars and provides appropriate information about the statistical significance of the experiments, with results obtained from multiple repeated trials.
Guidelines:
73

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: For the experiment, the paper provides sufficient information the computer resources needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / /neurisuup..p// cc/ httpppplltttiiooo///eeppppppppet ctthhiihhhieeeleeeee
Answer: [Yes]
Justification:
This paper conforms in every respect with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
74

---

The paper provides new tensor spectral perspective for the multi- regression problem due to combinatorial distribution shift. focuses solely on these technical aspects and does not have potential societal impacts.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not describe safeguards for the responsible release of data or models because it focuses exclusively on the technical aspects of addressing combinatorial distribution shift in multi-output regression. Therefore, this question is not applicable (N/A).
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use any external assets such as code, data, or models. Therefore, the question regarding the crediting creators or original owners, as well as the respect for licenses and terms of use, is not applicable (N/A).
75

---

Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license ge.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi theode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:[NA)
This paper does not introduce any new assets. Therefore, the question regarding the documentation of new assets is not applicable (N/A).
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
This paper does not involve crowdsourcing experiments or research with human subjects. Therefore, the question regarding instructions, screenshots, and compensation details is not applicable (N/A).
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
76

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve study participants human subjects. Therefore, the question regarding potential risks, disclosures to subjects, and IRB approvals is not applicable (N/A).
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
77


Reviews:
[{"review_id": "G0uNx1fu5h", "reviewer": "Reviewer_1ZmA", "summary": "The authors propose a new model for decomposing vector-valued functions of two vector arguments. The proposed model considers a SVD decomposition of these functions in Hilbert space, effectively extending t-SVD to Hilbert spaces. Here t-SVD, short for tensor-SVD, consists of applying SVD to each matrix slice of a tensor, after multiplication by a unitary (although authors restrict these to orthogonal) matrix $M$ in the third dimension. They propose using this approach for Multi-Output Regression, and claim that the proposed approach is especially suited for generalizing pairs of arguments that are not present in the training data, in a similar fashion as t-SVD may be used for tensor completion.", "questions": "Overall, the statement of Theorem 4 is not very clear to me. On the other hand, it seems to be a generalization of reference [37] of the paper to multiple output regression. Can you explain what are the differences and similatities between both results? Which parts of the result in [37] generalize well to the new approach, and what were the novel analysis that needed to be developed?", "limitations": "I believe that the limitations are adequately addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method proposed in the paper appears to be very promising. The overall approach seems to be highly generalizable and it may possibly be used together with several function approximation techniques.", "weaknesses": "The biggest weakness is the lack of numerical experiments. The overall idea of the paper is interesting, but it is not ground-breaking. Without the multiplication by $M$, this is essentially a regression in each dimension. Here numerical experiments are needed as a way to investigate possible choices of $M$ in applications: should we choose well-known orthogonal basis given by DFT or DCT? Or should we do a data-driven approach?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the constructive feedback.\n\n**W1: Lack of numerical experiments**\n\n**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**.\n\n**W2: Interesting idea, but not ground-breaking**\n\n**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:\n\n- Rev. HXH7 characterized our approach as \"rather novel\" and praised our \"series of solid theoretical analyses.\"\n- Rev. yp2H noted our \"clear and reasonable motivation\" and \"solid theoretical analysis,\" emphasizing that our method \"effectively improves generalization capabilities.\"\n- Rev. juWX described our functional t-SVD as \"a decent contribution\" with \"solid theoretical analysis.\"\n\nAs 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:\n\n1. 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.\"\n2. First formal treatment of MOR under CDS: Providing a systematic definition and solution, addressing a crucial gap in current ML research.\n3. 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.\"\n\nOur 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.\n\n**W3: Choice of transformation matrix $M$**\n\n**Re:** Thank you for this insightful observation. We would like to clarify our position:\n\n1. 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.\n2. Framework flexibility: While $M$ is assumed given, our framework accommodates various choices, enabling adaptation to different problem structures.\n3. Empirical investigation: We've conducted preliminary numerical experiments comparing different $M$ options (DFT, DCT, data-specific). Results are in the **attached PDF**.\n4. Future directions: Optimal $M$ selection opens new research avenues. We propose a potential approach:\n\n> A preliminary proposal.\n> \n> - We seek the best $M$ in the feasible transformation set $\\mathcal{M}$ (typically the orthogonal matrix group):\n> $$\\min_{M \\in \\mathcal{M}} \\Phi(M)$$\n> 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$.\n> - To capture the interdependence between the transformation and the optimal functional representation, we employ a bilevel optimization approach:\n>     \n>     $\\min_{M \\in \\mathcal{M}} \\Phi(M) = \\Phi(M, F(M))$ subject to $F(M) = \\arg\\min_{F \\in \\mathcal{F}} \\Phi(M, F).$\n>     \n>     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}$.\n>     \n\nThe 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.\n\n**Q: Clarity of Thm 4 and its relation to [37]**\n\n**Re:** We apologize for any lack of clarity. Let us address your questions:\n\n*Similarity*: Both Thm 4 and [37] provide excess risk bounds for learning under CDS, with bounds structured to include approximation and statistical error terms.\n\n*Difference*: Our results diverge from [37] in:\n1. Framework: Introducing Ft-SVD for tensor completion in infinite-dimensional spaces.\n2. Scope: Generalizing to multi-output MOR, addressing inter-output dependencies.\n3. Characterization: Incorporating spectral decay patterns across frequency components.\n\n*Generalizations from [37]*: The basic structure of the excess risk bound and the concept of analyzing learning under CDS.\n\n*Novel analysis*:  We introduce key theoretical innovations within our Ft-SVD framework to address MOR under CDS challenges:\n\n1. Spectral analysis theory for Ft-SVD, extending t-SVD to infinite-dimensional spaces.\n2. 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].\n3. 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.\n\n*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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "on89bwirW1", "reviewer": "Reviewer_yp2H", "summary": "The paper introduces a novel approach to multi-output regression (MOR) under combinatorial distribution shifts (CDS) using a generalized tensor decomposition framework. The proposed Functional t-Singular Value Decomposition (Ft-SVD) extends classical tensor SVD to infinite and continuous feature domains, providing a new perspective on handling MOR tasks under CDS. The authors present a Double-Stage Empirical Risk Minimization (ERM-DS) algorithm designed to improve prediction accuracy in the presence of CDS. Through rigorous theoretical analysis, the paper establishes performance guarantees for the proposed algorithm and demonstrates its efficacy with synthetic data experiments.", "questions": "See weakness", "limitations": "See weakness", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tClear and Reasonable Motivation: The paper presents a clear and reasonable motivation for using tensor completion to address multi-output regression under combinatorial distribution shifts. By framing the problem as a tensor completion task, the method leverages the strengths of tensor decomposition techniques to manage the challenge of unseen feature combinations in MOR, effectively improving generalization capabilities.\n\n2.\tSolid Theoretical Analysis: The detailed proofs and theoretical guarantees offered in the paper are impressive and contribute significantly to the understanding and validation of the proposed methods. This rigorous approach ensures that the findings are well-supported and credible", "weaknesses": "1.\tThe paper's definition, introduction, and highlight of Combinatorial Distribution Shift (CDS) are insufficient. It is not clear why CDS poses a significant challenge in MOR and why it is important.\n\n2.\tThe relevant definitions, assumptions, and proofs are presented with excessive detail, which makes it difficult for readers to grasp the core issues and contributions. A more concise and focused explanation would help in conveying the importance and difficulty of CDS in MOR.\n\n3. The paper does not adequately discuss the existing body of work on functional tensor completion, such as [Bigoni et al., 2016], [Luo et al., 2023], and [Fang et al., 2024]. Including a more comprehensive discussion on related works and how the proposed method compares to them would provide better context and highlight the contributions more effectively. \n\nRef:\n- Bigoni, Daniele, Allan P. Engsig-Karup, and Youssef M. Marzouk. \"Spectral tensor-train decomposition.\" SIAM Journal on Scientific Computing 38.4 (2016): A2405-A2439.\n\n- Luo, Yisi, et al. \"Low-rank tensor function representation for multi-dimensional data recovery.\" IEEE Transactions on Pattern Analysis and Machine Intelligence (2023).\n\n- Fang, Shikai, et al. \"Functional Bayesian Tucker Decomposition for Continuous-indexed Tensor Data.\" arXiv preprint arXiv:2311.04829 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the thoughtful and constructive feedback.\n\n**W1: Insufficient introduction of CDS in MOR**\n\n**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.\n\nThe 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.\n\nHowever, 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.\n\nIn 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.\n\n**W2: Excessive detail in definitions and proofs**\n\n**Re:** We will streamline the main text as follows:\n\n- Summarize core contributions and results concisely, avoiding excessive technical details. Key definitions and assumptions will be directly tied to the challenges posed by CDS.\n- Move extensive technical explanations to the appendix, keeping the main discussion focused on central issues and contributions.\n- Utilize practical examples and visual representations to illustrate the significance of our contributions without overwhelming the reader with complex details.\n\n**W3: Inadequate discussion of related work**\n\n**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.\n\n1. [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.\n2. [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.\n3. [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.\n\n  **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.\n\n  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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IJnw5UuMz7", "reviewer": "Reviewer_juWX", "summary": "This paper proposes function t-SVD for multi-output regression under combinatorial shifts. Excess-risk bounds have been derived. Using simulation experiments risk bounds with combinatorial shifts has been compared with regular risk bounds.", "questions": "Lack of any real-world application is limitation of the paper. Since the paper is proposing a functional tensor decomposition methods, it would be useful give at least one application to understand its learning capability. Can authors provide some experiments on real-data set?\n\nSome references such as function tensor-train is missing [1]. Can authors provide more detailed related methods?\n\nHow does the proposed method compare with other functional tensor decomposition methods? How does the theoretical results (ERM bounds) compared with any existing results?  \n\n1 Alex Gorodetsky, Sertac Karaman, Youssef Marzouk, A continuous analogue of the tensor-train decomposition, Computer Methods in Applied Mechanics and Engineering, Volume 347, 2019, Pages 59-84,", "limitations": "Limitations listed but insufficient in my opinion due to any experiments with real-data.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) Proposal of functional t-SVD, which is a descent contribution.\n2) Solid theoretical analysis", "weaknesses": "1) Lack of any real-data experiments. It is hard to understand the usefulness of the proposed method in real-world application though the theoretical contribution may be high. \n2) Lack of comparison to other related function tensor decomposition methods either by theory or experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and constructive feedback. We address your concerns as follows:\n\n**W1 & Q1: Lack of real-data experiments**\n\n**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.\n\nNevertheless, 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**.\n\nFor future work, we plan to:\n\n- Collaborate with domain experts to collect large-scale datasets reflecting CDS characteristics, especially in complex MOR scenarios.\n- Design comprehensive experiments to evaluate our method's performance in real CDS scenarios, focusing on MOR.\n- Explore the applicability of our theoretical framework across various practical domains, enhancing the robustness and performance of MOR models.\n\n**Q2: Missing references and detailed related methods discussion**\n\n**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.\n\nWe 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.\n\n**W3 & Q3: Lack of comparison with other functional tensor decomposition methods, either by theory or experiments**\n\n**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.\n\n1. **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.\n2. **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.\n3. **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.\n\n**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.\n\nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RkpySQG4ud", "reviewer": "Reviewer_HXH7", "summary": "This paper investigates the problem of multi-output regression under combinatorial covariate shift, namely when the input domains in the testing set differ significantly from the training set. The authors view the functional mapping from the inputs to the vector-valued output, which is evaluated discretely in the input domain, as a tensor with missing tubes, and convert the problem of making test set predictions as a tensor completion problem. Utilizing the framework of low tubal-rank tensor decomposition, the paper generalizes this framework from the discrete case to the continuous case and proposes a functional t-SVD method that decomposes the functional mapping into a series of embedding functions with associated singular values. Then an empirical risk minimization (ERM) algorithm is proposed and evaluated with a toy example numerical experiment. The major contribution of the paper is a solid theoretical analysis of the approximability of the functional t-SVD as well as the excess risk of the ERM algorithm and the writing of the paper is clear.", "questions": "1. The tubal rank framework introduced in this paper, to the best of my knowledge, works for 3-order tensors. Does that indicate that the functional t-SVD framework considered mainly works for inputs with dimension 2? Is it possible to generalize the current approach to higher-order tensors (and thus higher-dimensional inputs)?\n\n2. The functional t-SVD framework in Theorem 1 resembles the Mercer decomposition of kernels. What is the main advantage of the current approach over some existing alternatives such as the multi-output Gaussian Process regression?\n\n3. Maybe I missed it in the manuscript, but is there a systematic approach for choosing the rank $r$ when implementing the functional t-SVD? Is there any sense of optimal $r$ that might be derived by minimizing the excess risk bound w.r.t. $r$?", "limitations": "1. Additional numerical experiments that demonstrate the effectiveness of the proposed functional t-SVD over existing benchmark methods can be informative and helpful.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper bridges the low-rank tensor decomposition in the discrete domain to a functional approximation problem in the continuous domain, which is a rather novel approach when dealing with missing data issues for functional data.\n\n* The paper provides a series of solid theoretical analyses regarding the approximability of the vector-valued functions as well as the excess risk bound of the empirical risk minimizer.", "weaknesses": "1. The empirical analyses of the paper lack comparisons with some other benchmark approaches, making it hard to evaluate the effectiveness of the proposed methodology. It would be interesting and informative to consider other tensor decomposition approaches (CP, Tucker, Tensor-Train, Tubal) as benchmarks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness & Limitations: Lack comparisons with some other benchmark approaches**\n\n**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. \n\nFollowing 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**.\n\nIn our revision, we will:\n\n- Clarify why direct comparisons may not be appropriate given the novelty of our problem setting.\n- Provide discussions on how our method uniquely addresses MOR under CDS compared to existing approaches.\n- Where possible, adapt existing methods to our setting and provide limited comparisons.\n\n**Q1: Generalization to higher-order tensors**\n\n**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.\n\nSecond, 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.\n\n> **Proposition (Functional higher-order t-SVD, informal).**\n> \n> \n> 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:\n> \n>   $$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)$$\n> \n> where the convergence is in the $L^2$ sense, and $\\ast_M$ denotes the t-product.\n>- For each $n = 1,\\ldots,N$, the set of functions $\\\\{U^n_i\\\\}$ satisfies the orthogonality condition:\n> $$\\int_{X_n} U^n_i(x) \\ast_M (U^n_j(x))^{\\top} dx = \\delta_{ij} M^{-1}(\\mathbf{1}_t)$$\n> 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.\n>\n>- The core function $S$ has the following properties:\n>\n>   (i) all-orthogonality: for all $1 \\leq n \\leq N$, and $1 \\leq \\alpha \\neq \\beta < \\infty$, we have \n>   $$\\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.$$\n> \n>   (ii) ordering: for all possible values of $n$, \n>    $$\\\\|S_{x_n=1}\\\\| \\geq \\\\|S_{x_n=2}\\\\| \\geq \\cdots$$\n>    where $\\\\|S_{x_n=\\alpha}\\\\|$ is the $L^2$ norm of $S$ with the $n$-th mode fixed at $\\alpha$.\n\nThe 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.\n\n**Q2: Comparison with multi-output Gaussian Process regression**\n\n**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:\n\n- A natural way to handle combinatorial shifts\n- Interpretable low-rank representations of the function\n- Potential computational advantages in high-dimensional spaces under CDS conditions\n\nWe will expand on these points in our revision.\n\n**Q3: Rank selection for Ft-SVD**\n\n**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.\n\nIn 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.\n\nFor 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:\n\n1. Analyzing t-singular value decay and selecting r based on a threshold.\n2. Employing cross-validation to choose r that minimizes prediction error on held-out data.\n3. Adapting information criteria such as AIC or BIC to the Ft-SVD setting.\n\nWhile 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewers' constructive feedback and provide a summary of contributions, the feedback, and responses.

**Contributions.** Our work proposes the novel Functional t-Singular Value Decomposition (Ft-SVD) framework, addressing the challenges of multi-output regression (MOR) under combinatorial distribution shifts (CDS) for the first time. Key contributions include:

1. **Ft-SVD Framework:** Extends traditional t-SVD to infinite and continuous feature domains, allowing for handling complex, high-dimensional data through a functional approach.
2. **Double-Stage Empirical Risk Minimization (ERM-DS) Algorithm:** Developed within the Ft-SVD framework, this algorithm is tailored for MOR under CDS, leveraging spectral properties and domain-specific hypothesis classes to improve prediction accuracy.
3. **Theoretical Insights:** Comprehensive theoretical analysis within the Ft-SVD framework, detailing approximability and excess risk bounds, enhances understanding of MOR models' generalization capabilities under CDS.

**Positive Feedback:**  The reviewers described the methodology as "promising and broadly generalizable" (Rev. 1ZmA) and appreciated the "clear motivation for using tensor completion in multi-output regression under combinatorial distribution shifts" (Rev. yp2H). The theoretical analysis was praised for its "rigor" and "detailed proofs and guarantees" (Rev. yp2H, HXH7). The innovation in combining low-rank tensor decomposition with functional approximation, as well as the extension of t-SVD to infinite and continuous feature domains, was highlighted (Rev. HXH7, yp2H). The clarity of the problem formulation was noted, and the potential impact of the work was seen as offering "new possibilities for a wider range of tasks" and "a new perspective on handling MOR tasks under CDS" (Rev. 1ZmA, yp2H).

**Common Concerns:** We provide responses to the common concerns as follows:

- **Numerical Experiments**: Need for more experiments (Rev. 1ZmA), especially with real-world data (Rev. juWX) and common benchmarks (Rev. HXH7).
    
    **Re:** We acknowledge the importance of real-world data experiments. However, the core focus and primary contribution of our paper is theoretical. Our work provides the first formal definition and comprehensive theoretical framework for the CDS problem in multi-output regression. This includes the novel Ft-SVD theorem and the ERM-DS algorithm, which offer new theoretical foundations and methodologies for understanding and solving the CDS problem.
    
    Nevertheless, we understand the need for real-world data validation and would like to address this concern. We have provided preliminary empirical support for our theory through:
    
    - Synthetic data experiments: We conducted more synthetic experiments, validating our method in a controlled environment.
    - Real tensor completion in missing not at random (MNAR) settings: We applied our method to real-world Velodyne LiDAR data.
    
    The additional experimental results are shown **in the attached PDF**. 
    
    For future work, we propose:
    
    - Collaborating with domain experts to collect large-scale datasets that reflect CDS characteristics in specific fields.
    - Designing and implementing more comprehensive experiments to evaluate our method's performance in real CDS scenarios.
    - Investigating the applicability of our theoretical framework and methods across a wider range of practical domains.
- **Clarification and Presentation** (Rev. yp2H, juWX): The need to clarify the significance of CDS in MOR and its unique challenges, as well as simplify the presentation of assumptions and technical proofs for better accessibility.
    
    **Re:** We will elaborate on the role and importance of CDS, highlighting how our approach addresses these challenges. Additionally, we will summarize key contributions more clearly, focusing the main text on core findings and moving more details to the supplementary materials for improved clarity.
    
**Specific Responses:** For specific concerns raised by individual reviewers, such as the exploration of different transformation matrices (Rev. 1ZmA), clarification on Theorem 4 and related work (Rev. yp2H), and the selection of rank and potential extensions to higher-order tensors (Rev. HXH7), please see the specific rebuttal where these issues are addressed in detail.

Meta-review: The paper presents the functional t-svd framework for multi-output regression problems. All the reviewers including this AC have appreciated the paper. One concern was the lack of experiments which the authors have addressed in their rebuttal (and that are sufficient for this paper). In the camera-ready version, please include all the changes that have been asked by the reviewers.
Decision: Accept (poster)