Learning Sparse Graphs for Functional Regression using Graph-induced Operator-valued Kernels
Authors: Akash Saha
Balamurugan Palaniappan
Venue: Accepted by TMLR ()

Abstract: A functional regression problem aims to learn a map $\mathfrak{F}:\mathcal{Z}\mapsto\mathcal{Y}$, where $\mathcal{Z}$ is an appropriate input space and  $\mathcal{Y}$ is a space of output functions. When $\mathcal{Z}$ is also a space of functions, the learning problem is known as function-to-function regression. In this work, we consider the problem of learning a map of the form ${F}:{\mathcal{Z}}^p\mapsto\mathcal{Y}$, a many-to-one function-to-function regression problem, where the aim is to learn a suitable $F$ which maps $p$ input functions to an output function.  In order to solve this regression problem with $p$ input functions and a corresponding output function, we propose a graph-induced operator-valued kernel (OVK) obtained by imposing a graphical structure describing the inter-relationships among the $p$ input functions. When the underlying graphical structure is unknown, we propose to learn an appropriate Laplacian matrix characterizing the graphical structure, which would also aid in learning the map $F$. We formulate a learning problem using the proposed graph-induced OVK, and devise an alternating minimization framework to solve the learning problem. To learn $F$ along with meaningful and important interactions in the graphical structure, a minimax concave penalty (MCP) is used as a sparsity-inducing regularization on the Laplacian matrix. We further extend the alternating minimization framework to learn $F$, where each of the $p$ constituent input functions as well as the output function are multi-dimensional. To scale the proposed algorithm to large datasets, we design an efficient sample-based approximation algorithm. Further, we provide bounds on generalization error for the map obtained by solving the proposed learning problem. An extensive empirical evaluation on both synthetic and real data demonstrates the utility of the proposed learning framework. Our experiments show that simultaneous learning of $F$ along with sparse graphical structure helps in discovering significant relationships among the input functions, and motivates interpretability of such relationships driving the regression problem.

Published in Transactions on Machine Learning Research (03/2024)
Learning Sparse Graphs for Functional Regression using Graph-induced Operator-valued Kernels
Akash Saha IEOR, IT Bombay Mumbas India
akashsahaWiit..om
P. Balamurugan IEOR, IIT Bombay Mumbai, Indio
Reviewed on OpenReview: https: // openreview. net/ net/forum? id= f914esPKp/
Abstract
A functional regression problem aims to learn map 3 2 + Y, where 2 is an appropriate input space and y is a space of output functions. When Z is also a space of functions, the learning problem is known as function-to-funcee function regression. In this work, we consider the problem learning map the form F ZP + y, a many-to-one Iearn suitable F which maps p input functions to
centiion-t-fuuntiin
regression problem, where the aim an output function. In order to solve this regression problem with p input functions and corresponding output function, we propose graph-induced operator-valued kernel (OVK) obtained by imposing a graphical structure describing the inter-relationships among the p input functions. When the underlying graphical structure is unknown, we propose to learn an appropriate Laplacian matrix characterizing the graphical structure, which would also aid in learning the map F. We formulate a learning problem using the proposed graph-induced OVK, and devise an alternating minimization framework to solve the learning problem. To learn F along with meaningful and important interactions the graphical structure, a min- imax concave penalty (MCP) is used sparsity-inducing regularization matrix. We further extend the alternating minimization framework to learn F, where each of the constituent input functions as well as the output function are multi-dimensional. To scale the proposed algorithm to large datasets, we design an efficient sample- based ap- proximation algorithm. Further, we provide bounds on genoralization error for the map obtained by solving the proposed learning problem. An exlensive empirical evaluation on both synthetic and real data demonstrates the utility of the proposed learning framework. Our experiments show that simultancous learning of F along with sparse graphical struc- ture helps in discovering significant relationships among the input functions, and motivates interpretability of such relationships driving the regression problem.
the Laplacian
1 Introduction
Learning predict functional output from a suitable input is characterized a functional regression prob- lem, which aims at learning a function-valued function F Z - }, where Z is appropriate input space and ) is an output space of functions. In many scenarios, multiple inputs decide the value of output, which gives rise to functional regression problems of the form F 2n + y, where is the number of inputs considered. Even more interesting is the case where interactions among the inputs can be used in precise manner to predict y E y. In particular, we consider Z to be a space of functions, hence learning a map F: D + y called a many-to-one function-to-function regression problem. Without loss of generality, we refer to this many-to-one function-to-funttin regression problem the functional regression problem considered throughout this paper. Applications of this type of problems can be found in weather forecast-

---

Published in Transactions on Machine Learning Research (03/2024)
(1)
21
y
(t) A
t
v(t)
22
F
(t)
Z3
21
22
Z3
G
Figure 1: Illusrative example of a functional regression problem, where 21, 22, 23 represent atmospheric
pressure at stations a region, graph G depicts the inter-relationships among 21; 22, F3 and y represents the average temperature of the region. F maps 21, 22, 23 to y incorporating G.
ing where different weather parameters in stations measured at multiple timepoints across month can be characterized as functional inputs used to determine the average rainfall as a time-varying function in that month. Similarly, emissions from a factory in a day can be predicted as a function of time, based on the functional data obtained from readings of differrnt components involved in the manufacturing process at different timepoints in that day. In sports analytics, the movement data of different players throughout the game can let us know the influence of particular strategy in ball output over the duration of the game. Thus in all these applications, we notice situations where a set of output function. Even though digital data is discrete, systems where the inherent data produced is smooth and contimuuss by nature, can be modeled as functions over suitable domain [Ramsay
/mvoeemmnmmmmmmmen as a functional
input functions interact to produce
1982) to leverage the variations based on that domain.
Consider a simple functional regression problem illustrated in Figure [ where input functions 21, #2, 23 2 denote the atmospheric pressure measurements denotes the average temperature of the region, throughout particular day. For predicting y, considering the input functions 21, 22 and 23 without any relation among them may be restrictive inherent relations between the input functions may dictate the generation of In order to capture interactions among Z1, 22, #3; we introduce graph structure G between 21, 22 and 23 in Figure ! where the nodes of G represent 2, and the edges depict potential relations among them. The graph structure G will be useful in representing the influences and inter-relation among 2 which can be useful in the prediction of y E y using F. We propose a framework for combining the impact of 21, #2, 2p with the additional information of G to predict y. In determining the output function y, the graphical structure G on the input functions may be known from domain knowledge and possibly be directly incorporated to learn F. A more interesting case is when G' is unknown and needs to be learned along with F. Learning the graph structure G would help to discover interactions among 2, 's which facilitate predicting grow larger, the associated graph G might also become dense with many edges and incorporating such dense G might lead to computational difficulties and would also lead to spurious connections/ /edges which lack interpretability. Thus, learning a sparse graphical structure G on input functions becomes instrumental understanding the significant relationships that drive the functional regression problem to predict the output function.
nearby weather stations and the output function y E y
When the number of input functions 21, 22.
2

---

Published in Transactions on Machine Learning Research (03/2024)
In this work, we consider kernel methods to learn the map F 2 3/ either using a priori knowledge of G or by learning G along with F. Kernel methods have been popular class of methods that use kernel functions to associate inputs to a higher dimensional feature space and find applications in classification, clustering and regression [Shawo- Taylor ct al.) 2004). For a simple scalar-valued regression problem, the aim is to learn / X + Ik, where X is an appropriate input space of vectors. A scalar-valued kernel k: X X + R associates two inputs in X to a real number which provides a measure of similarity between those inputs. Scalar-valued kernels which are positive semi-defiitte are associated to a (unique) space H of candidate functions f mapping imput space X to R, H being referred to as a reproducing kernel Hilbert space (RKHS). The function f to be learned resides in the aforementioned space H. of functions which enables us to formulate a regularized loss minimization problem over H (Shawe-Taylor et al.) 2004), whose solution can be used to predict the desired output for input samples. On the other hand, for a functional regression problem, an extension of scalar-valued kernel to operator- kernel (OVK) of the form K Zxx Z + C()) associates two input functions to a bounded líncar operator on the output space of functions instcad of a real number (Kadri et al. 2016 [Saha& & Palaniappan 2020). An operalor-valued kernel K which is positive semi-definite is associated to a (unique) space H of candidate functions F mapppng input space Z to Y, HK being called a function-valuee reproducing kernel Hilbert space (Kadri et al. 2016). Similar to cealar-valuer kernel setting, in the operator-valuet kernel setting too, a regularized loss minimization learning problem can be formulated in the function-valued RKHS Hk. The reproducing property of OVKs (Definition A.1] helps in reformulating the learning problem in the output space V, enabling algorithms to be developed for solving the resultant learning problem.
In this paper, we consider another natural extension of this kernel-based framework which leads to case where p input functions and their interactions among themselves (captured by graph G) be used to predict the put function. To learn F: ZP + y/ we incorporate p input functions along with the underlying graphical structure to create graph-induced operator-valued kernel that induces a corresponding function- valued RKHS to facilitate learning of F. In order to use graph-induced OVKs in the task of functional regression based on p imput functions with unknown graphical structure, we propose to learn F simultaneously along with the graphical structure. Predicting output function based on a graph-induced OVK constructed using graphical structure G over p imput functions, to our knowledge, is a novel problem and has not been explored much in literature. In this context, we outline our major contributions below.
Contributions: We aim to address the following objectives in this work.
We propose a graph-induced OVK for solving a functional regression problem with p input functions to
21, 2p and their interactions represented using a graphical structure predict corresponding output function y. This is enabled by Proposition A.1 considering the Laplacian matrix (T.) of the underlying graph G.
For practical scenarios where the underlying graphical structure is unknown, we provide a construc- tion of graph-induced OVK and propose to jointly learn the functional regression map F, along with the graphical structure G represented by L and D, where is a diagonal matrix with non-negative entries signifying the impact of individual input functions on y- A regularized loss minimization problem is formulated using L, D and F in the function-valued RKHS associated with the graph- induced OVK.
We propose an alternating minimization framework for solving the designed regularized loss mini- mization problem to learn L, D and the map F. The functional regression map F is learned for a fixed L and D by adapting Operator based Minimum Residual (OpMINRES) algorithm (Saha & Palaniappan 2020) to solve linear operator system associated with the graph-induced OVK. For fixed F. matrices L and D are learned using projected gradient descent. To learn sparse L, we introduce minimax concave penalty (MCP) (Ying et al. 2020) as sparsity-inducing regularization on the Laplacian matrix L.
We further extend the proposed alternating minimization framework to solve a multi-dimensional functional regression problem, where each input function 2, E Z, i E (1.2.....p)) .p) and y E y are multi-dimensional.
3

---

Published in Transactions on Machine Learning Research (03/2024)
In order to scale the proposed alternating minimization framework to handle large datasets, we design an efficient sample-based approxination amgorithm which enables to solve the learning problem over only a carefully chosen subset of training samples.
We establish bounds on generalization error for the map F obtained by solving the proposed learning problem. Our generalization analysis also incorporates the learning of graph-induced OVK.
An extensive empirical evaluation on both synthetic and real data has been carried out and the comparison results demonstrate the efficacy of the proposed learning framework. Further our exper- iments show that simultaneous learning of sparse graphical structure along with the function-valur regression map F establishes interpretable relationships driving the functional regression problem.
2 Paper Organization
In Section 3 related works from the areas of functional data analysis, functional regression and graph learning are discussed. The notations used in this paper have been summarized in Section ! The proposed framework for solving a functional regression problem using a graphical structure is covered in Section 5 The graph- induced OVK is introduced and a representer theorem for the learning problem with an unknown graph structure is presented in Section 5.1 An alternating minimization framework is proposed in Section 5.1 for jointly learning an unknown graphical structure on the functional inputs and the map F. Inducing sparsity using a MCP regularization when learning the unknown graphical structure is also discussed in Section 5.1 An extension of the proposed framework for solving a sample-based approximation algorithm for scaling up to large training data are also presented in Section 5.1 In Section the bounds on generalization error of the learned map are established by incorporating learning of graph-induced OVK, Experiments using the proposed alternating minimization franework and comparative results have been illustrated in Section 7 Section g provides the conclusion of the paper.
caltiiddmensional functional regression problems and
3 Related Work
As our work lies in the confluence of various areas of research, we divide the related work based on the different areas below.
Functional Data Analysis: Continuous functions over time interval have been explored as the central part of functional data analysis (FDA) in (Ramsay 1982) and (Ramsay & Dalzell 2018). FDA techniques have evolved significantly with non non--orannen parametric approaches (Ferraty & Vieul 2006) and functional principal component analysis (FPCA) (Happ & Greven 2018) becoming prevalent tools. These approaches have found
applications in sparse longitudinal data (Yao et al. 2005). classification involving functional data (Rossi &
Villa 2006) and clustering for multivariate functional data (Jacques & Preda, 2014).
Functional Regression: In the context of functional regression, Oliva et al. 2015) uses projections on orthonormal basis systems for input and output spaces to estimate regression maps based random basis functions from random Fourier features (Rahimi & Recht 2007]. Operator-valued kernel methods have found applications for vector-valued data (Micchelli & Pontil 2005) and function-valued data (Kadri et al. 2016) for solving corresponding vector-valued and functional regression problems. The construction of a positive semi- definite operator- valued kernel used to learn a function- valued mapping in a corresponding reproducing kernel Hilbert space (RKHS) is considered in (Kadri et al., 2016), while Saha & Palaniappan (2020) uses indefinite operator-valued kernels to learn function-valued function in a corresponding reproducing kernel Krein space (RKKS). Hullait et al. 2021) uses robust functional linear regression model based on robust FPCA (Bali et al. 2011 to predict response function using predictor function without considering multiple input functional data and their graphical structure. Another approach in (Bouche et al. 2021) uses kernel-basod projection learning with a finite (not. necessarily orthogonal) basis for the output space. High dimensional functional data has been used in (Gahrooei et al.) 2020) to perform function-tas ter--to-fuuu to-function regression for a functional response output using a linear combination functional inputs considered as covariates. However, associations among the functional inputs have not been considered in (Gahrooei et al.) 2020). Functional deep learning methods have been developed to solve regression problems using functional direct neural network
4

---

Published in Transactions on Machine Learning Research (03/2024)
and functional basis neural network (Rao & Reimherr 2023 In functional direct neural network, continuous neurons interact with learned weight functions, whereas in functional basis neural network, basis functions are used to encode the continuous neurons as well as weight functions. Both functional direct neural network and functional basis neural network in [Rao & Reimherr 2023) require large amount of data for training. On the contrary, our work is related to a setting with limited number of training samples which is useful in various practical scenarios where data availability is restricted.
Graph Learning: Learning graph structure has been active area of research in machine learning. In Dong et al., 2016), Laplacian matrix corresponding to the graph structure the observed imput signals is learned by using vectorized optimization problem with a smoothness assumption over the signals. The graph Laplacian learning algorithm is based on an alternating minimization scheme for learning the Laplacian matrix as well as the missing/ /noisy signals. Pu et al. (2021b) extends this idea by using a kernel- basod learning problem for determining the Laplacian matrix of a graph structure for smooth input signals. Kernels are used to learn relationships between the input signals as well as the relaiioclai between covariates such as timestamp of recording an observation. Another popular approach for graph structure learning in (Qiao et al.] 2019) is based estimation of precision matrix (inverse of covariance matrix) for functional data corresponding to the p nodes in the graph, assuming that the data ariscs from a p-dimensional multivariate Gaussian process, A differential functional graphical model has been considered in (Zhao et al. 2019) which learns a differential graph to characterize the difference between conditional dependencies of two different populations which is determined using their respective samples. Extending the idea of determining precision matrix for capturing conditional dependence between the nodes, Qiao et al. (2020) proposes doubly functional graphical models to capture the evolving conditional dependence relationship among the sampled functions corresponding to the nodes. Instcad of learning single graph based the data, Pu et al. (022a)) learns a graph topology with topological difference variational autoencoder for graph learning.
A motivating work (Gómez et al.) 2021) addresses cenciion-tofuunctin linear regression problem with both known/unden unkknww directed graph structure where the main focus is on root canse analysis and the node representing output function is also a part of the graphical structure containing nodes corresponding to the input functions. The graph structure considered is learned based on a neighborhood selection method Meinshausen & Bühhlman 2006) to determine the set of candidate parents for each node in order to solve the linear regression problem. Multivariate Gaussian processes have been used with basis functions in (Gómez et al. 2021) to model a directed acyclic graph which enables solving function-to-fuuction linear regression problem. However, in our approach, the goal of learning an undirected graph structure only on the input fanctions is different from the parent-based directed acyelic graph structure assumption in (Gómez et al. 2021 Moreover, our OVK based approach helps to learn non-linear relations in comparison to the linear model considered in (Gómez et al., 2021).
4 Notations
We consider a functional regression problem with the input space as X' (L2 1)) and the output space as y = ((0, 1)), where p N and (3a, b)) denotes the space of equivalence classes of square integrable functions [a. b], a, E R and < b. The notation [n] denotes the the set (1, for n N. In order to denote elements of the input space X, use the notation x = (21, the graphical structure over the input functions æ1, ,2,,, Ip as G = (V, E),, where V is the set of p vertices corresponding to the functional input variables Ii, T2,...,... deg(v). K refers to an OVK mapping from X' x
E X. We denote
The degree of a vertex v E V is denoted by to L(Y), where L())) is the set of bounded linear operators over the output space y. For a matrix M E t where & E N, M.,, denotes the (i.j)-th element of M and M; E R** denotes the i-th column of M. Hence, we refer matrix M as [Ma,lt or [M1, Ma,..., .., MrJ. The d2) denotes a p X p diagonal matrix with
transpose of M is denoted by T The notation diag(d,, the diagonal entries as d, .......dp dp. where d, E IR for i E [p]. For a matrix D E R Diag(D) denotes the p x 1 vector containing the diagonal elements of D. Based on the context, other relevant notations will be introduced in the paper as required and suitable descriptions will be provided for them.
5

---

Published in Transactions on Machine Learning Research (03/2024)
5 Functional Regression based on a Graphical Structure
In this section, we introduce the functional regression problem with the aim of incorporating the graph structure to aid the regression task. To model the graphical structure, we assume that G = (V, E) represents an undirected graph where V denotes the node set with ( p) nodes and E denotes the edge set of G. Let s(t) = ( ...),........ (p(()) denote the functional variables for a given domain E T where each i; is represented by node v, E V, for [p]. Recall that [[ bl) denotes the space of equivalence classes of square integrable functions (a, b), a, E R and < b. For simplicity, assume 2; ( 1)), hence So' (f)ddtt < i E [p]. We discuss the realistic case of functional regression with an unknown graph structure here. For a related discussion on the case of a known graph structure, we refer the reader to Appendix A.1
5.1 Learning with Unknown Graph Structure
Consider system where a set of input functions determines the output (or response) function. Let the where x; E [20, 1)), E [p]- A functional response variable v()) is used to model output of the system where y E [2 1)). (Note that [0, 1] can be replaced with any closed time interval based on the application.)
system be modeled based on p input functional variables xz (t),
The undirected graph structure of the functional input variables is represented by a suitable graph G = (V, E), where = {vi, .2,....,........................ up and = {{0,, UyH/, connected to új, 1 S i,j S p} is the edge set which characterizes the underlying relationship between the variables. Note that the notation for an edge uses an unordered pair {uz, 32} which characterizes the undirected nature of the graph G. In order to model the relation between functional imput variables ø1, 22, .......,pp Fp and functional response variable y, we use the following map F:
y = F(11, 22, Fpp G).
Note that F now depends explicitly on the graph G in addition to the input functions æ ,,,,..
For most problems in real life, the underlying graphical structure encoding the inter-relationship among the input functions Iı, -2,; Tp is not known. In such situations, the underlying graph on the input functions has to be learned with simultaneous prediction of the functional response variable E y using (21, TI,)... E X. Considering an undirected simple graph structure on the functional variables may result in encountering an integer programming based optimization problem which will lead to a computationally harder problem in addition to the functional regression task. We consider a relaxation in this aspect by allowing weighted undirected simple graphs our approach. With a slight abuse of notation, let the graph structure be given by G (V, W), where |V] p and W E Rexp is symmetric with wij 2 O, where wiyj 0 whenever vertices i, and Vj not connected and Way 0 denotes the weight assigned to the edge between e and vy. Hence the graph Laplacian matrix can be represented as L D W, where ID = diag(DD.11 D2,,,,,,,,2............. D2,,,..,, Dppp) with D,, Σ/= Wig. It can be shown that I, is positive semi-definite by virtue of being diagonally dominant with non-negative diagonal entries (Golub & Van Loan 1996).
We consider the notations x = (2.., 2p) E X (= (LO, 11)))) and E y ( 1))) to represent an arbitrary sample (x, y). To learn the mapping F, consider the training data of n samples given as (a()),(())) ) where sx(() = (x 12 ......... _(² E X and yd E V. In order to learn F, we develop an operator-valued kernel which can leverage the structural information of G.
Definition 5.1 (Graph-induced Operator-valued Kernel), A graph-induced operator- valued kernel is defined as
(,, (h:00))))((()))) (x, S (2(ss))(s)ds
(2)
where 22 is a scalar-valued kernel on R is a graph associating the p imput functions in (I1,..., E X and kn defined as
ki(z,z';)) e - (LLD)))(((((__a)tt (L+D)(--)), 7 0,
6

---

Published in Transactions on Machine Learning Research (03/2024)
where L is the Laplacian matrix of graph G and D is diagonal matrix consisting of non-negative entries.
KG associates a pair x, E X with output function E y where is the graph which incorporates the interactions of p constituent input functions of x and x'. hy inside the Hihbert-Schmidt Integral (HST) operalor Jo (2,s, ds is scalar-valued kernel on R x R. The radial basis function (RBF) type kernel construction of ky involves L + D, where the addition of the Laplacian L with a diagonal matrix D with non-negative entries results in a diagonally perturbed Laplacian matrix (Bapat et al.) 2001 (see (Kurras et al. 2014 K is positive semi-definite and if 22 is positive semi-definite (implying that the HSI operator is positive semi- -efintei, then the construction in 2 is known to be positive semi-definite (Kadri et. al. 2016). The addition of diagonal matrix D (with non- negative entries) to L in (2) preserves the positive semi-deliniteness of the kernel K1. Note that the notation of the form x² Lad used k denotes an inner product structure given by x La = Eij= Ta5() (see Appendix A.1 for details regarding this inner product structure).
Aliakbarisani et al. 2022) for applications of perturbed Laplacians).
Without loss of generality, henceforth we refer to the graph- indpheindueed operator-valued kernel K as K for simplicity. The matrix I. = [T+,][a=1 satisfies the conditions: 1.1 = 0 and La.j = T,ja S 0, Vi + j. Note that the graph-induced operator-valued kernel (K(z, x (t) = kn (I,x'; fo ()(sss as defined in ( with by (x, GG) = "=< (L+t)))))))
> 0, x. x' E X.y E y is positive semi-definite (see proof of Proposition A.1 Appendix A. which ensures that there exists a unique function-valued RKHS HK induced by K (Theorem 1 (Kadri et al. 2016)). ) Now to simultaneously learn F including the graph structure represented by and D, the following optimization problem is formulated:
F,I,D=
arg min LEC,,
Σ
( F(x!0))13 + AIIFI + Pr. (0 Lx + DIE
(3)
where L (I E TX 0, Ii T, S V, + j} denotes the set of all matrices satisfying the constraints associated with Laplacian matrices of the graph G (V,W) with W [uej]l Note that D (D E Dr, 2 D., = 0, vi # j} denotes the set all diagonal matrices with non-negative diagonal entries, ||-]|r the Frobenius norm and A.PL. PD > The regularization of D in (3) using Frobenius norm provides control on the values in D. Note the absence of a Frobenius norm based regularizer for L in (3) A different smoothness term x Lz Ei Wis |2, - 15 is considered (a similar term is considered in Humbert et al. 2021) ), which provides an improved interaction-based data-oriented regularization instead of using a simple matrix norm based regularization of L.
Using the representer theorem A.2 and the reproducing property of OVK K, the minimization problem (3 is equivalently reduced to be in terms of u E y" instead of F E HK as follows (see Appendix A.2
= min J(FLL,D) FLD
(1 ((x + Al1F112 + +
Σ xr (1) (x(()) + D
(4)
T=1
min J(u u.L.D i=1
= Σ
(()))
K ((x 100,,,00)
+1 1-1=1
( (x((0) (l00)u..uh.
(5)
j=1
n
+ PL
Σ
L (0)
( + D
To solve 3 (or (5) cquivalently) we now propose an alternating minimization framework where J(u, L,, D) is optimized alternatively with respect to ymh L,m E L and E D. We now discuss the steps involved in alternating minimization of J(,, I., D).
5.1.1
Minimization with respect to for fixed L, D
Assuming fixed L, D, and from the reproducibility property of K and representer theorem A.2 from 5 simplifies to the following system of linear operator equations in (see Appendix A.8
Ju, L, D)
KK Nu==y
(6)
7

---

Published in Transactions on Machine Learning Research (03/2024)
where K = K(x(1) zb))u h (x(0),)) x0);; G)k2(u ()) Vu E y with ky (2, (I.
(t( is defined using an exponential kernel in ( as (2(u)(t) = Jo Toplo- u(s))s Yop > 0, 0, E R. u = [u1,uz,-.. u2,-..,,u,, E )m and y [y()) y(2) gO In our framework, consider particular choice of kernel l2 on IR² as (s) e Topls Top > O. The OpMINRES algorithm (Saha & Palaniappan,
2020) solves the system (6] by using an itcrative Krylov subspace minimal residual mothod. Consider
P == K + XI, OpMINRES minimizes ||y - Pullyn, where the norm is defined as ||El|>> E So ())d,, for (2.. y". The stops involved k-th iteration of OpMINRES algorithm are given below:
1. Transforming the linear operator system (K + X/)u into a linear system in R using a Lanczos- based method [Lanezos 1950), called Operator-valued Lanczos (or OpLanczos) scheme.
Solving the linear system of the previous step using QR decomposition.
Transforming the result obtained in step appropriately retrieve solution in y".
Using the Krylov subspace (P. = span(y, Py, P P p obtained at the k-th iteration, Op- MINRES obtains an approximation u to the original solution using the following:
u arg min Iyy Pollyn.
(7)
(P
The problem in 7 is transformed into a problem in TR by using OpLanezos method. The OpLanezos method at the k-th iteration, tridiagonalizes to get PQR = QuTk, where Tr has a tridiagonal structure given by
01
82
82
Q22
B3
83
003
(8)
Bk-2
Bk-1
0k-1
BR
0
By
ork
and Qx [g1, ............ qel, where the qss belonging to y" are orthonormal and a is generally assumed to be y //lyyly>. Further, the relation PQx = Q++1 Tv also satisfied for a suitably defined Tx. Using Qk, 0 E ym can be written as 0 Q& for appropriate & R² Hence we have:
min lly -O-oo min Iyy PQuolly min Ily Qu+ 2x012 (P.y)
(9)
SeRt
dERt
min BER*
||Qk+1 - -
(10)
(where B1 |yyly>, 61
Oo and 91 y/llylb>>)
min || T2l (where ||-112 the standard Euclidean norm.)
(11)
deRk
Equation 100 reduces to owing the orthonormality of {yr, 92...., 1 (columns of Qx+1). Solving T is done using QR decomposition. Now, the transformation from R
for d2 arg mingER+ |8pe back to ym to obtain u is achieved using the following: at Q&Oi Qx (arg minøeR= || Tu,ll2). In summary, we note that the minimization of J with respect to u is obtained by using OpMINRES for fixed L. and D. Now, we proceed to the next step in the alternating minimization of J(u, L, D).
5.1.2 Minimization with respect to L for fixed u, D
The minimization of J(u, L, D) with respect for fixed u, is simplified by considering the symmetry of L E L. To simplify the computations, we introduce vectorization of matrices and hall-vectorivation
8

---

Published in Transactions on Machine Learning Research (03/2024)
of symmetric matrices (eenderson & Scarle 1979 For matrix Z [Zapllas1 1R for 9 N, the vectorization of Z is defined as
veol Z) = 11, 2, 2,,, ................................ 22.2..... 1 2
The half-vectorization of symmetric matrix Z [Zislis-1 E Egx0 is the vectorization of the lower trian- gular part of Z given by
vech (2) 11, 7g 22, 2 1.. 7 7-g.5l
By introducing vectorization and vectorrcctiinnation of L, reduce the minimization of Ju, L, D) with respect to matrix L into minimization with respect to the vector vech(L.. To tackle the constraint set L, we can reduce it to a simpler form by using vectoricctoi and vectorization of given by vech(L) E R rint"" and vec(L) E R²², respectively. The following relations are used to relate vech(L) and vec(L) using an appropriate transformation matrix called duplication matrix M:
MVech(L) = vec(L), where M RR plp11)
The constraint set C can then rewritten as A vech (L) = 0, vech (L) < O, where A and B are matrices
2016 Pu et al., 2021b). The construction which handle L1 0 and Lig S i j, respectively (Dong ct al.,
and properties of A, B and M can be found in Appendix [A.5] For notational simplicity, we consider a slight abuse of notations when referring vech(L) and vech(D) can be used to represent L and D, respectively. Similarly, when considering fixed ve)h(L) or vech(D), we denote the function J as function of non-fixed entities, without referring to the fixed variables. For example, in the current step, since vech(L) is the non-fixed entity and u, vech(D) are fixed, we denote J(u, vech([.), vech(D)) simply as Ju.D(vech(L)). We employ a projected gradient descent procedure to solve min Ju, D (vech( The (k + 1)-th iterate vech(L) (+1 is obtained from the k-th iterate V by the following projected gradient descent step:
function Ju, I., D) to be equivalent to J(u, vech(T.), vech (D)
vech(T.) [T((vcc(T.)* TJ2. V
(12)
where nz > the learning rate for the descent step, Hc denotes the projection operator onto the set L. The expression for gradient term Ve has been derived in Appendix A.6 For fixed & E R pin+ the projection operator 1l. is defined as follows:
Ic(2) = arg min - 211 such that A2 = 0, B2
(13)
p(p+1)
=ER
The projection operator defined in 13 ensures that vech(L.) obtained satisfies the constraints of a Laplacian matrix of a graph. Projection operator II is evaluated by solving the quadratic program (13) using well- Andersen et al. 2012).
known interior point methods (Dikin 1967
For large matrix L, capturing meaningful relationships between input functions becomes important; oth- erwisc, elements of L may contain many non-zero values which are close to cach other in magnitude and may lead to lack of interpretabilily. Integrating sparsity-inducing regularizers most important interactions get captured and can improve the predictions for output function. The learned sparse graphs would then become useful for interpretation. In Section 5.1.4] we discuss about incorporating iparsity-inducing regularizers in the L-based minimization problem min Ju, (wwch(vvvhh))) gradient descent is proposed for minimization of with respect J. for a fixed u and D, we proceed with similar approach for the next step of the alternating minimization framework.
L would ensure that the
Now that projected
5.1.3 Minimization with respect to D) for fixed u,
Similar to the minimization of Ju, I., D) with respect to L for fixed u, D, as discussed the previous section, we proceed with the simplification of D E D using velf-veccoiization given as vech(D) R " min Ju, miech_( We further use notation Ding( D) to denote the vector containing diagonal elements of
solve
9

---

Published in Transactions on Machine Learning Research (03/2024)
D. In order to deal with the constraint D,, 2 0, Vi E [p] of D, we construct matrix C' R 20r1
which consists of 0's and I's satisfying Cvech(D) = Diag(D) D). Construction of suitable C has been discussed in projected gradient descent steps given by:
Appendix A.5 For solving min Ju, (voch(D)),
vech(D) [vvccch(D)* nu V vech(D) (voch(D)")),
(14)
where no is learning rate for the descent step, Tp denotes the projection operator onto the set DD and vech(D)* denotes the k-th iterate for vech(D). The required expression for gradient Vvech(D) has been
derived in Appendix A.6 The projection operator IIp is defined for E R 2 as
ll (d) arg min ||d - |d', such that Cd 2 O.
(15)
pip=12
dER
The explicit solution of
15 can be easily obtained for i [p(p + 1)/2], the following:
0, d; = max de 0), otherwise,
if E [p(p 1)/2) A
(16)
where the set J consists of indices j such that (vech(C))) = =1 (see Appendix A.5 5
Thus, the proposed alternating minimization framework discussed in Sections 5.1. 5.1.3 in the following steps:
can be summarized
Minimization with respect to HK (or u E y²)): Solving for u in (K + Af)u=
Minimization with respect to vech(L): Projected gradient descent of J with respect to vech(L) such that L E C.
3. Minimization with respect to vech(D): Projected gradient descent of J with respect to vech(D) such that D D.
5.1.4 Sparsity Inducing Regularization
The functional regression problem aims at predicting the output function based on the interactions and influences of the input functions. In a large-scale setting with numerous input functions influencing the output function, providing each interaction of a pair of input functions with similar weights may hamper the prediction capability as well as interpretability method. Sparse graphs ensure a focus on picking more pivotal associations between the pairs of input functions which drive the functional regression problem, as noisy interactions are given negligible weights and significant interactions contribute more to the prediction. A popular method to obtain sparsity the graph structure is to consider the trace of L as regularizer (Qiao et al. 2018). But as L is obtained based on solving constrained minimization problem [1] we introduce a constraint that can regularize the values
the proposed graph-induced operator-valued kernel
in L (Pu et al. 2021b). To facilitate this, we consider a vector e E IR "ir-" consisting of 0's and I's, such that veeh(L) trace(L) (Appendix A.5 Let (2 0) be a hyperparameter controlling the trace of L which is equivalent to controlling the off-diagonal entries of weight matrix W corresponding to the graph learned. As our formulation requires solving quadratic program in the projected gradient descent for L
(Section 5.1.2). direct way to control the trace of L involves modifying the quadratic program 13 to the following:
IL( arg min ||2 2--3 2|1 such that A 0, Marace Bz S 0, =ER 1(
where & E R 11 transformed quadratic program for projection operator Nl:
and Mtracc
0. The constraint z Murac is appended with Az = 0 to obtain the
TT(3)= arg min ||z 2|1? such that Às = 0, Bz
(17)
sER 2
2
10

---

Published in Transactions on Machine Learning Research (03/2024)
MCP(W) with Vmcp 1
MCP(w) with Amep
1.4
4
1.2
1.0
Amcp 0.5
Ymcp 0.5
MCP(w)
Amcp 1
MCP(w)
0.8
Vmcp 1
Amcp 2
Ymcp 2
Amep 3
0.6
Ymcp 3
0.4
0.2
0.0
5
5
Figure 2: Comparison of h(w) MCP(w) values for different Amep and "mep values for varying w. [Best viewed in color]
A c
where A and 0
For our experiments the value of mirace is considered as p/2 (discussed
Mirrace
in Section to promote sparsity in the learned graph structure. Assigning Murace the value p/2, allows cunulative weight of p/2 to be distributed among the edges in the learned graph, promoling sparsity. Though we have used Mirace p/2 for all our experiments, we showcase the impact of different values of Mirace in Appendix 10. which illustrate that Merace can be considerod as a hyperparameter.
In addition to restricting the trace of with miraces we also utilize a sparsity-inducing regularizer min,, p J (vvech(L)). Nonconvex regularizers have gained popularity in recent literature (Zhang al. 2020
Ying al. 2020 Vargas Vieyral 2022) for promoting sparsity in learned graphs. These nonconvex regu regulariz-
ers acting weights on individual graph edges are more effective than traditional l l-normm based graphical
lasso regularization which is classical approach in graph learning (Yuan & Lin 2007 Banerjee et al. 2008:
d' d'Aspremont et al.) 2008). nonconvex regularizer, minimax concave penalty (MCP) [Zhang 2010 denoted
by h is characterized by the definition of its derivative h' given by:
Ammpp
[0, Ymepdmephs mmmppmmpp 20);
N'(w)
Tmop
(18)
0
for Amep: Tmnp > The above definition of /'' with h(0) ensures that h is monotonically increasing the interval [0, 7mmppmmppp- The impact of Amep and Tmmpp on value of the regularizer has been compared in Figure 2 The illustration in Figure 2 shows that MCP function h magnifies the small values till Amep where Amop and Tmep control the slope and curvature of the truncated concave quadratic function h. This ensures that most smaller off-diagonal values are penalized by choosing proper Amep and the differences between large and small values are exaggerated which promoles sparsily. Though h in (18) (or equivalently h) defined over R., we overload the notation to define h(z) = [h(2){}{ where E R$. Ying et al, (2020) proposes MCP to obtain a nonconvex penalized maximum likelihood cstimation method for lcarning sparse Laplacian matrices for graphs. However, here we introduce MCP regularizer the projection step considered for vech(T.). Therefore, we reformulate the minimization problem with respect to L for fixed
11

---

Published in Transactions on Machine Learning Research (03/2024)
and D as follows:
min vech(L)eC vech(L)p.MeP
Ju, (vvec((((L)),,
(19)
where the constraint set is C = {2 E pict11
Az = 0, B2 50 and the property vech(L) & MCP signifies
that vech(L) is sparse in the sense of MCP regularization.
The MCP regularizer operates on the off-diagonal entries of L to induce sparsity. To solve 19
consider
two-level update procedure for vech(L). In the first level, use Ju (vech(())) to perform an iteration of gradient descent to obtain (q + 1)-th iterate from q-th iterato, as follows:
vech(L)ut1 vech(L) - mh V veecic))hu.(veeec(())
(20)
where V denotes the gradient of J with respect to (ec and nı > is the learning rate for the descent step. In the second level, we ensure that vech(L)9+1 obtained (20) is projected onto set. and is also sparse in the sense of MCP regularization captured using the property vech(L) MCP. To apply the MCP regularizer on off-diagonal entries of I, for vech(T.), we construct matrix H E R "inell ping comprising O's and I's such that Wvech(L) produces a vector having the same structure as vech with O's corresponding to diagonal entrics of L and the same off-diagonal entrics as in L (scc Appendix A.5 for the construction). Then we aim to solve the following minimization problem:
pic+1)
min
|| - vech(L)s+1122 + Σ (k(H(-2))), such that Äz = 0, B2 $ 0, Pip+
(21)
#ER
where the negative sign before z in MCP regularization used since h operates on non-negative entries and L contains negative weights corresponding to off off-diagonal entries. Further the product H--2) climinates the posilive diagonal entries of L. Note that the first term in the objective function of 21 is convex in and iterative approach, similar to (Ying et al.] 22200) to solve 21.. In each iteration I of this approach, we obtain majorization of the objective function in 21 using the linearization of concave function h at z! as:
the second term is concave in 2. Hence we adopt a majorization-miiniiaate
piP 11
|| - voch(L)
Σ (M(-EE))))
(22)
Then we solve a minimization step, which when combined with the linearization in 22 leads to the following quadratic program:
p(p+1)
241 arg min I|z- 1e
(((I(=))).(((==)) such that Az 0, Bz < 0.
(23)
pip-1)
=ER
We solve the problem 23 iteratively till convergence to obtain a sequence of 2's. The procedure for MCP based sparsity-inducing regularization has been summarized Algorithm [ The solution obtained from Algorithm is thus a valid Laplacian matrix of a graph, and satisfies trace constraint as well as MCP based sparsity-inducing regularization property captured by vech(L) & MCP. Note that other nonconvex regularizers such as smoothly clipped absolute deviation (SCAD) (Fan & Li 2001 Ying el. al., 2020) can also be used instead of MCP in approach which provide comparable sparse graph structures.
Using the learned u. L, D, the graph-induced operator-valued kernel is used to predict the output function corresponding to the input functions & = (01, Re,,,,,,,, ..p)) based on 114h given by
F(t)= = (*x 1,),s, where u, E
(24)
1=1
12

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 1 MCP Regularization of L
Input: vIch(L)
Output: vech(Lmep)
Initialize 2 vech [.), H
1=0
while stopping criteria for 2' not satisfied do
Find (H='))))
Find 2/+1 as the solution of 23 I 1+1+1
end while vech(T<mep)
Algorithm summarizes the entire alternating minimization procedure with sparsity-inducing regularization. For our experiments, vech(L) is initialized using a Laplacian matrix L with Li,- = -Mtrace/ - 1)), for j E [p] and L = mtrace/.. pp for i [p], which satisfies the muace condition in (17) The initial vech( is considered corresponding to D Ip, identity matrix of order p. Note that the objective function J in problem 19 is not jointly convex with respect to u, vech(L) and vech(D). To prove the convergence of alternating minimization of non-convex function J with respect to a heterogeneous collection of three variables where u;ss J and vech(L), vDch(D) E R " requires development of fundamental results which is out of scope of current work, and aim to take this up in future. However, we observed empirical convergence of the proposed alternating minimization framework in our experiments.
5.1.5 Extension of Learning Graph Structure for Multi-dimensional Outputs
In many scenarios, functional regression problem involves multi-dimensional input and output functions which requires learning multiple functions corresponding to each dimension in the output space. Consider X = (L, y = [=((0,))) 1)) with {(x(),))))))) { as the training data, where x(() E X", X",y(0 E )², for E [m]. Notice that the input space is now X" and output space is y's which are both multi--imeensonal.
In this case, have x()) (z] .22 ,...,2r 21") where 2) (a (6) (i) "f....... 2(0) X, [r] and y())
(1) (i)
(0)
where yj V.Vj E [s]. Consider setting where the imput space X" is mapped to output space ya by learning distinct maps of the from Fi X + V. for i [s]. Note that to find these maps Fd, an extension to the framework developed in Sections A.1 and 5.1 can be used, as long as the proposed graph-induced OVK framework is adapted to handle the muuti-dimensiona inputs x() For motivating example, consider the data of movement of players for fixed time interval in basketball game comprising the x and y coordinates of the playing area belonging to the input space X², Similarly, movement of the ball for the fixed time interval is characterized by x and y coordinates of the court which belong to the output space y2 The corresponding regression problem involves learning F = F2; X²2 + y.
(v1", 322
(0) (0) ........!") (d)
where F x22 + y and
For the multi-dimensional setting, we propose the following extension of the scalar-valued kernel based L and D as
hn xxxxxxx0) x0)))))))) - -Eim
( (= [
( 200)
(25)
where 7h > VK E [r] and k maps pair of elements from the input space X' to a real number. Now, hn (x(), x0);; G) can be appropriately used create a graph-basod aperator-value kernel in higher dimen- sions using the construction of suitable OVK as follows:
K (xx()xx x(i)) [t)]
1ht (('t",)))n(')dtt ki (xx) x0100)
(26)
K (x((), x(1) y (t)
Ag(ee' ())))))
13

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 2 Alternating Minimization of J
Input: {(=19, y (af) ,2 ................................ 1 E X. X.y ey
xl1)
Output: u, vech(L), vech(D)
Initialize v L, vech(D) (D) ED
- (2) ..(jjT
k =
while True do Compute & (219, x01i; G) = Rey ( Vi,j J E [n] using (137 in Appendix A.6
Solve for in (K + AT)u y to obtain u using OpMINRES if stopping criterion for u* satisfied then break from the outermost while loop end
/ /exitt based on convergence of iterates
4 =0
while stopping criterion for v)9 not satisfied do //stopping criterion is based on convergence vech(L) iterates
voch(I.)9+1 rech(L) "I Vvech(E) (e..u,..(..(())) (vech(L.)9)
voch(L) obtained based on MCP regularization using vech(L)o*1 input to Algorithm vech(L)9+1 vech L) mop
q g g
end while
vech(L)* + (L)
m 0
while stopping criterion for ve not satisfied do
//stopping criterion is based on convergence of vech(D) iterates
DDc vech(D) (D)*
(eeh(D)mtt m Il (vech((())" dL V (vecc( using 14
m < +1
end while
vech(D)* t D
& ++1
end while
u ut vech(L) vech(L)*
vech(D) vech()) (D)
where ki IR R R. for i E [s] are scalar-valued kernels on R2. In order to use the output functions
y(0) = (v) 1/2 ..... ) for learning maps from input space X" the output space V, the problem (3)
(
is extended as follows:
F. D.
arg min
11Bi (5)
Fx
F= F2. Fl LEC
(27)
(i) pkak Lay DI
where A, Pk: PD are positive reals, HK Hi Hh ... Hi. X +
for [s]. Consider
the objective function of (27 [[F, I, D). Similar to Sections 5.1.1 5.1.4. on applying an alternating minimization framework, the steps involved in D, minimization remain the same. In order to solve the
minimization problem in (27] (for fixed L, D) an extension of the representer theorem A.2 is required which follows based on the construction of graph-induced operator-valued kernel in 26
Theorem 5.1 (Extended representer theorem). Let K be an operator- valued kernel as defined in (6) and Hx H. H& x... Hi be its corresponding function-valued reproducing kernel Hilbert space based
14

---

Published in Transactions on Machine Learning Research (03/2024)
kernels h1, kg. ..... kg. The solution Fx E Hx of the regularized optimization problem:
Fx arg min
1lvi (0) (x)33 + 111
-
F=(F) F FTTTE 1=1
EH
where À >00, F. = [F', F² F.IT HKK Hi x Hi
x Hxx has the following form
E K' xx(x"),, (.)²
BAO)= =
where u, ,,,...,,u ui E y
(28)
=
Fx E K* ))u
Proof. The proof follows as consequence of the representer theorem proof in Appendix A.4
In order to solve the minimization problem 27
the representer theorem and reproducibility property of the OVKs K2, for I E [s]. The optimization problem in (27) is solved by using the alternating minimization of the objective function with respect to F [F F2 FJ E Hx, L E L and D E D. For a constant L and D, we use the representer theorem (Theorem 5.1 to transform the objective function in terms of Fl E H....., F E Hi to functions u! ................................
ug E v, [n], respectively. The objective function is
defined as the following (sce Appendix A.2
J(FL, F2 ...., F D.
Σ
11
(1) F (x) + 1I
Σ Pk k=1
Σ i=1
I
(3)
Lx
(1)
+ D
n
n
J(u ,
L, = Σ
y1
-
Σ xx(xx
(()))())
+
(K (k' (x(1) ,x(5) udyo
(1)
1=1
i===
(29)
n
Pk
(8) k
(1) Lx
+
DI
For solving the multi-dimennsioall functional regression problem, the alternating minimization framework discussed in Section 5.1 extended with the major difference in the step concerning minimization with respect to F = [FL, P p..... F.]T (or u², u² uu,.... ,...,, u²) for fixed L and D. The milti-dimeensonnlltty leads to solving the following system of linear operator equations:
.....
[K]] + AA)u²
(K* + + = =
0.],
(30)
where K (x x(0 = ki(x(), ()) Vu V. θ w/) y/ (2)
..... M1 | with ki
S'' - (l Top > 0, [s] and b,, E [0. For all K!, E [s], the scalar-valued kernel k (given in 25 used remains the same and is built on common L and D. Therefore, s possibly different graph-induced OVKs are obtained by using exponential kernels on IR. with Top. for E [s).
In order to solve for u², u², , u² in (30). we use the OPMINRES algorithm discussed in Section 5.1.1 to solve the systems (K' + A/ju yı. for TE [s). OpMINRES algorithm solves the s systems in parallel with stopping criteria which combines relative residuals.
Thus, for alternating minimization, the steps discussed can be summarized as:
Minimization with respect to == F= F2 Fe,..,, F E Hk (or u², uu......u y²): Solving for u u² ...., u² in
F2
[K] + +
(K + ADju]] [ e.].
15

---

Published in Transactions on Machine Learning Research (03/2024)
2. Minimization with respect to vech(L): Projected gradient descent of J with respect to vech (L) in L with sparsity inducing regularization.
3. Minimization with respect to vec Projected gradient descent of J with respect to vech(D) in D.
Using the learned grapheinddued operator-valued kernel the output function is used to predict for input functions & = (fi,,..,, &r), where &3 E X, for j E [r] as
E (x, 2)u}]
F(R)= = En (x 2)u
where ut,..., uz E V, for e [s].
5.1.6 Sample- based Approximation for Functional Regression Problem
The kernel-based alternating minimization framework proposed earlier in this section helps to learn appro- priate u. L,, and D for the prediction of functional output using (24). For setting where the mumber of training samples is large, the training can become computationally expensive as OpMINRES iteration scales in O(n"), where n is the number of training samples. This issue of scalability is a well-known problem in kernel methods, which becomes more pronounced in an OVK-based framework. There are many popular methods for handling scalability issues in kernel methods (Williams Seeger 2000 Meanti et al. 2020 Bach & Jordan 2005). In most cases, the approaches handling scalability issues for kernel mcthods are incorpo- rated into the learning problem for approximating the kernel Gram matrices arising in large datasets, by using low-rank Cholesky decomposition (Bach & Jordan 2005 Nyström approximation (Williams & Seeger
2000) and GPU-based acceleration and parallelization [Mennti et al. 2020). For vector-valued regression problems, random Fourier features have been used for building OVKs (Brault et al., 2016 Brault 2017) which cannot. be directly extended to functional regression problems due to the following reasons. Extension of the random Fourier features to a functional setting requires developing a new theoretical framework for a functional version of opcrator-valued Bochner's thcorem. Morcover, spectral docomposition of OVKs for functional data is beyond the scope of our current work, hence leave it for future work. In our approach, we aim for sample-based approximation heuristic algorithm which enables to perform a greedy sample selection procedure followed by the training with only those selected samples.
The motivation of the sample-basee based approximation lies in characterizing the action of the considered OVK on i-th sample (x:(), ()()) E E xxx) y. Recall the learning problem discussed in Section 5.1 given by
F, F,L,
arg min FEN..LEC.DED 1=1
Σ 0 F(2(0)) + A1IFIRR + Pz. Σ 20) La + Dp
which requires solving for u in (K + +T)u= in the first step of alternating minimization with respect to F (or u) for fixed and D. We consider the notations yi and K2 respectively as equivalent to y()) and K(a(),, -) in this section for simplicity. Though approximating u; E y in F()) = -E K corresponding to sample (z(1,, g()) may provide a better option for performing a sample- based approximation, we do not have the luxury to perform the inversion required in (K + X/)u y. One way to assess the importance of a training sample (z(0), () is to investigate the action of operator K with 2(()) on the output function (f)), Towards that we build K; X' + L()") by choosing samples which minimize the squared norm of the difference Eis | - Kl defined over the RKHS HK. A working set of samples is constructed iteratively from the training data to formulate K,y; linear combination of K2, V/, 's, where it's correspond to the indices of working set of samples in training data. Inspired by (Smola & Schölkopf 2000), we propose the following approach to construct K;'s iteratively. Consider indices in I = (41, 22, 4 C [n] as the set of indices for the working set Tw ((x(0) (0) : E 7) of samples from the training data. The aim is to
16

---

Published in Transactions on Machine Learning Research (03/2024)
approximate the action of K2 yi using samples in Iw
|1
Kiya
Σ
Tig Ki, for i E [n],
(31)
j=1
K18/1
Ti,1
T2,2
Ti.1
Ki, Uh Kighta
K5, Yis Kiy
K282
T2
T2.
T2,14
(32)
:
Kayn
T
Tn2
Kan Mini
Kig yhmn
where E R The values Kiy: - K.yk Hx are treated as residuals the approximation for the i-th training sample. Approximations K, corresponding to each sample (x ,,(0))())) for i E [n], created by the working set Iw of samples in (31) are bounded linear operators on the output space y. For every sample (x19), ()), where i [n], the action of operator K, on ys is approximated by using scalars Ti,1 Ti.,............ with Ki, HK. for j [[z]]- Minimization of Σ ||K,y/ K li ensures that the working set of samples can characterize closely the impact of Kay. The approximation of K,, Vi [n] using the working set of samples is described next.
A Approximation of Operators using Samples: Initially, suppose I= 0 and let i E [n] be the best candidate index. Then the index set I is updated as / = {41, and the working set Iw contains only single sample corresponding to the index i E T. Now the optimization problem is to determine Tı, .2.1...., Tu,1 in K,y, = Ki,,Ki, Vi E [n] and is given by
arg min Ta Toa 1=1
Σ
||
Kay - Kivill Hx =
Σ 1=1
|| Kays - Te, Ki 11
(33)
The solution of (33 is obtained as
(Kayi, K3, Vir)
T₂ (K Mar K Wea N
(34)
(Kay Ue Midy for i E [n].
(35)
(Kis Vi, Vyyy"
where Ka, K(x(0), (.)) and 34 is obtained by differentiating the objective function in (33 with respect to T₁ and equating it to 0, to obtain the minima for i [m]. The reproducing property of OVK is used to obtain 335 This construction of Tr, yields
(Kyy Ray, K2 9h, ). = 0, E [n].
(36)
The equality in (36) denotes that the space span (,y; K,y:), Vi E [m]} is orthogonal to K2 (denoted by span((K.g K)))), Vi [n]} K.,) Note that this orthogonality property holds for index i,. We shall show later that similar property indeed holds for all samples which will be added to the working set. In general, the number of samples for the functional regression problem can be large and searching for the best candidates in the complete training set may become costly and defeat the cause for developing sample based approximation. Hence we consider a random subset of R samples for an efficient approximation, where R < n and / < R.
For the iterative process to build the working set of indices I and samples Tw. let us assume that pold be the index set with |oll] k. (say) and Told E Baak be the matrix formed based on (31h for obtaining Koldy, y = Σj= Ki Mi, Vi E [n]. Suppose ix+1 the index of next best sample to added to get pnom pold U {i+tt} which provides Knew K.ldy, + Tr Tr,t F. Miees The minimization problem in
33 is written
arg min
|| Kay Knew wall
Σ
|| Kiyy Rold yi Ta Kiezi Moetalle 11
(37)
Ti T2
17

---

Published in Transactions on Machine Learning Research (03/2024)
where the solution of 37
results in
(Kyys K yk: Kin- Wor+s Me
Ta
(38)
(Kiet Vieti Ki 1 Hw
(Küngz Mis Vivilyy Ez=1 Tig KagKiginn Diys Vinrly for i E [m].
(39)
Ti,+1 in 338 is obtained similar to the procedure for (34) by differentiating the objective function in 37
with respect to Ti,+''s 's and equating it to O, obtaining the minima for i e [n]. Equation (39 follows from
properties of inner-product and reproducing property of OVK. The iterative construction ensures that the following property holds:
(K K Vi. Kigth,) O, Vi E [n], Vij E [ + 11
(40)
span (Ky Krew E [n]] 1 span Ki Vi, li E [ 1]}.
(41)
Similar to 136 the iterative procedure ensures that the orthogonality property is extended to [41 in HK: which will be used the iterative selection process discussed below. For each iteration, it remains to find the best sample from the randomly selected candidate set of samples, which be included Jw. We discuss this next.
Selecting the Best Samples Iteratively: In order to find the training sample which will minimize the residuals most effectively, let C be the candidate set of indices for training samples given by C [n] \ T. Suppose for a particular iteration, let = {ūr, ink and let the randomly selected candidate set of indices be C = {c1, c2...., ) For each or E C, we calculate the improvement in the sum of residuals which can result in including o in Assume Koldy, ys be given by
k
Reld yi =
Σ j=1
Tr, KigWig for i [n],
(42)
from which we obtain Knewys ys as follows:
KT V Koddd y1 Ke, ye,, for & E C.
(43)
In order to select the best sample index from the candidate set C, we need to find the index e, in C which best approximates E Kaya Kpewysll, when Inew yold U {c} is considered as the index set for the working set of samples. Let the improvement in the sum of residuals by adding o, in lold be denoted by Improvement(c.). given by
n = Σ
n
Improvement(c);
Kiyi K.M
Σ
[ - Kre yall 1xx
(44)
Σm=
[Kam Koldur, Ke, Ke.yee.HHk
(45)
(Ka, Ver. Ke, KenVendHe
Σm [Kic, Mir Norly Eb Thi TiikKin KiKk,,,,,i Berly
2
(46)
(Ke,e,Yer: Ve.ly
Equation quantifies the reduction in the residual value by the addition o, to working set of indices. Equation 45 is obtained from 444b by using the properties of inner product and Kyld, for E [n] and the orthogonality property 41 Equation (46) follows from the reproducing property of operator-valued kernel K. The sample which achieves the maximum improvement is considered to be the best sample to be added to the working set. In terms of indices, this selection becomes
Best Indext
arg max Improvement(c.).
c,E0
18

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 3 Sample-based Approximation
E. y E y Input: {(=(9) y 2()) = (zf 22 ..... 10)) E X.
Output: 1, the index set of working set of samples. Initialize vech(L)", voch(D)
1/ + - K, < K (xx(), .). Kij + (101), Vi,j E [n]
Initialize k = 0, I = 0, =
while stopping criterion based on residual (49 is not satisfied do
Construct C' by drawing random subset of M elements from [r] \ 1 (c..02....00 C2. Cc.,
Compute Tü,+1 (Kii 1 Wisthii100 E, (Ke 19, , 1 for i E [n]
(Ke+1'' *1+++++777 Mis Mi Improvement(cm) = Ei (Kiem Me Memtem by EE= Tio My mem >
for m E [M]
(Rome Mem Mom by
Best Indexe = arg cC Improvement(cm) == (Best Index;}
++ end while
Stopping Criterion: As the case for any iterative algorithm, an appropriate stopping criterion required for ending the sample selection process which may be based the number of iterations accuracy. For using accuracy-based stopping criterion, residual is calculated for the k-th iteration
Residual
(K; K,)y: Hx
(47)
(Kays, Ki
2
Σ Tr (K.y. Kiyyi,H
TíJ (Ki, Viys K4 Ki
(48)
n &
n T (K Vi. Bi,by
(Kays. way 2
Tr TKi,, Buly
(49)
Equation 48 follows from the properties inner product of RKHS and 49 is obtained using the repro- ducibility property of K. As the first part of the summation in 44 remains constant for each iteration, a threshold for residual value can be used to determine convergence of the last two terms. For very large set of training samples, budget imation. As the aim is to learn a kernel encapsulating the graphical structure between the input variables, the sample approximation can still be costly, An effective strategy is to start with an initial L representing a fully connected graph and an initial D which is the identity matrix. After the sample selection procoss, the final working set Iw of samples indexed by are used throughout in the alternating minimization framework. In our implementations, we used the residual calculation using validation set instead of the training set which provided faster convergence and better generalization. Algorithm g illustrates the sample- based approximation for functional regression problem.
the number of samples to consider
also be effective tool for approx-
6 Generalization Analysis
Let X' (I,, 1})}² be the input space and y [= 1)) be the output space. Consider the training
samples given as ((x(0) (9) i E [m]] X y = where z (ar(9) g ()) Vi [m] are drawn i.i.d. from probability distribution μ. The empirical error of learned function- valuud function F on the data
is given as the following:
((FF)
1 -
Σ
F(
Lly F(x
(50)
19

---

Published in Transactions on Machine Learning Research (03/2024)
where L: yyyy + R_ is loss function defined on the output space V. A typical learning problem involves estimating function-valued F which is the solution of the following problem:
min (FFF FERK
(51)
where 6x (F) + In our problem K is parameterized by L, D, Top and belongs to a class of OVKs KC and hence in this work, for the given data, we aim to learn the following:
(K,, P:) = arg ( K): K
(52)
The problem [22] can be reformulated as regularized empirical error minimization problem. Our focus is on the problem of bounding the generalization error of F., namely 6(F.) ((F)), where 6(F) is the expected error of F given by &(F) = (y, F(z)),, the expectation E is taken over the probability measure H,, and F is the target function defined as
F = arggin min ((P),
(53)
where the minimum is taken over all measurable functions F X + y
6.1 Error Bounds
In this section, we introduce quantities which will be useful for our generalization bound analysis. We use the approach in (Micchelli et al. 2016 Ying & Zhou 2007 Wu & Zhou 2006) and introduce sample error as the following:
- & (6) ((F)).
(54)
The sample error S.(m, A, F) in 54 consists of two terms 8 (F=) term & (F+)l is the difference between the expected value of L Fg (x)) with respect to and its empirical mean over a fixed random data set 2 S 3. To bound this term we use the notion of Rademacher averages which enables us to control and analyze the random variables 2; associated with the data S 3. Similarly, the second term (F) & (P)) denotes the difference between the empirical mean of L (y Fx)) for fixed z C 3 and its expectation with respect p. We follow the approach in (Miechelli el al. 2016 to bound both the terms.
8-
and (C_(F)-((F)) The first
In addition to the sample error, we introduce another quantity known as the regularization error R(F) for a function E HK defined as
- &(F) + F PK.
(55)
where F* is the target function. A regularized version of problem
53
is given by
(K) F))
mig (6(F) +||1 KKEK Hx]. KEK.FEHK
(56)
The regularization error of F denoted by (*) as follows:
Rd (A) = min min
KEk FEHx [8(F) - 6(F") +IFIFEE]
(57)
In order to determine generalization bound, we use the following result which enables us to relate gener- alization error using sample error and regularization error.
Proposition 6.1. For every K E K. F E HK, the following inequality holds
((F.) (FF))-(FF)) E(F*) S (m, + R(F).
(58)
Proof. In order to prove the inequality, we start with the generalization ertor,
((F,) 8(F*) =
- (())) Ss, A, F) + R(F) ((())) A1
X, F) + - AIIF FII
(59)
(60)
Semmm A, F) R(F).
(61)
20

---

Published in Transactions on Machine Learning Research (03/2024)
Equation 59 is obtained by adding and subtracting S,(m, F, and F1 Equation 60
follows
from the delinition of R(F) in 155 The inequality in [6 is obtained using the facts Xl F HK
0 and
(F)F) - (F) _ 0, as F3 = arg FEH (F)).
Now, we intend to bound the term - Rademacher average of a suitable class of functions.
- (F,) in 54 Towards this we define the following notion of
Definition 6.1 (Rademacher Average). Let F denote a class of functions from X' to V. Let denote the marginal distribution over the input space X. Consider a m-tuple of samples from input space as (x(1), x(2) x((,,,)()))))))). E Xmm; where x((1) ,xx E [m]. Then the Rademacher average of class is defined as
|1
R (m) E
1 PET m
sup
Σ (o60))
(62)
where ey' are Rademacher random variables uniformly distributed over [+1,-1} and E represents the expectation over both iid. Rademacher variables e,'s and iid. variables 200's based on μox-
Recall that for class of functions F from an input space X to R, and sample (2,., Fm) X the Radamacher average of F is defined as
A mR (F) = E
sup FEF
F(xs))
(63)
Comparing this expression with that in Definition 6.1 we note that a suitable norm used Definition 6.1 Thus our definition of suitable Radamacher average accommodates the nature of the function class F which contains maaueed functions, unlike F which is composed of simple real-valued functions.
In order to proceed with the upcoming proofs, we require some assumptions which we state next. Assume 3B > 0 such that Ilvlly < 3, Vy E y, which provides a uniform upper bound on the norm of the outputs. In addition, assume that the class IC is uniformly bounded, that is,
== sup sup sup || [K(x, .Jullx = sup sup sup v (K (x.x)) < oo. <0. KEX yEy
(64)
=e yeyy
This assumption holds for OVKs which satisfy the trace class assumption Kadri et al. 2016
For any K E K and F E Hk, we define the following norm
|F max max FEX yEy (F(z) max max (F, (z) S Fl ZEX DEy
(65)
where we use the reproducing property, (F, (z,.))) = (F(x), u)y and the incquality in 65 follows from Cauchy-Schwarz inequality. We define for / 2 0,
E(t) = sup sup Lyy. s). vEY |ز
(66)
The function E(t) provides bound on the loss function when the second argument in the loss function has restricted norm. E(t) enables bounding the norm of the function F via the loss function L by considering
= 0. Let L y + IR be defined as the following:
LL $1) -L(y, s2)l
L(t)
sup sup vEy |l sz sallyst
(67)
|| 8211y
L(t) provides Lipschitz constant for the loss function L with respect to the second argument when the norm of the argument is bounded by t.
Lemma 6.2. Let F be class of functions from y. Consider a m-tuple of samples from input space (1(11) (2) y. (m)) m Then the following hold:
21

---

Published in Transactions on Machine Learning Research (03/2024)
1. E supper | Em= F(x(0) - EFlly] I 2 m.
For every E A m:y (cF) |c|
For Φ: + R, if Φ a Lipschitz function with Lipschitz constant L, then LmR(doF) S L.B:y
Proof. The lemma has been proved as Lemma A.6 in Appendix A.9
We further define the following constants:
/=())A, kp,
(68)
which will be useful in the upcoming results. The forthcoming results will use the class of kernels given by:
Ku = {K wy: K E K, &.
(69)
The following result provides bound on the sample error which involves the Rademacher average of the class of kernels Ko. Theorem 6.3. If F Hi. then with confidence -- 8, where å e (0,1), there holds
log 2m
S. F) &
(E(T) =(1
(70)
The proof will be provided later a consequence of the results covered in the upcoming section. Theorem 6.3 provides probabilistic upper bound for the sample error in terms of Rademacher average for the class of graph-induced operator-valued kernels. Later in Section 6.3 we will consider IC to be the class of graph- induced OVKs and derive a bound on mm:y(Ko)
6.2 Estimating Sample Error
In this section, we derive results which aid in establishing the result in Theorem 6.3 We use Hoeffding inequality for bounding the term (F) (FF) using random data set 3 = X x y Lemma 6.4. Let be a bounded function. For every 5 E (0.1), 1), with confidence 8 there holds
log
-(FF)-((F) < ((1
(71)
2m
Proof. Consider the random variable (= I(y, F(x)). Note that o, = 1 Σm ((2;), where 2; = (,(0))'))))
m
and B(C). By our assumption, 0 < < (11=)) we have
- |<E]] s B(1 Using one-sided
Hoeffding inequality, we obtain
2mt²
Σ (C: - B(()) 21)
< exp
(72)
(11
i=1
Consider,
c exp (- (- (=(((
2mt²
2mt2
log
8 = Therefore, for every 8 E (0, 1), with confidence 1-6 the following holds:
log
(E((1))))))
- == t ===((1)])))))
(73)
2m
log
6,(F) ((F) < =(IF)l()) V
(74)
2m
22

---

Published in Transactions on Machine Learning Research (03/2024)
Now that the second term in the sample error (54) has been bounded, we focus on the first term by considering union of unit balls in the space Hx where the notion of Rademacher average can be defined for obtaining bounds. We define a function & such that
((P.) (7))-=((Pa)) (()))
sup (8(F) - ((F)))((P)) FEABE
(75)
where Bx the union of unit balls Hx over E K. given by
Bx ULFE Hx 1I S $1].
(76)
KEK
The supremum is defined over pBx in 75 by the following reasoning: A||F2 lxx S - -
+ X||Fall llr.. S 60) - 8 ((P)) S suPyEy (y, 0) sup supail (y,,)) = This gives a bound on [Flll note that Fg is the minimizer in problem 52p. In fact, using similar approach, for any general F HK, have | I (=())/ p which leads the set pBx in 75
Thus to bound ( (F2), find suitable upper bound on ((z) in the following lemma.
Lemma 6.5. Consider (z) suPFEpBe (6(F) (F)), then for every d E (0,1), with confidence - the following holds
log 1 2m
( [[O(=)] + +E(r)
(77)
Proof. Let 2 be the data set which is obtained by replacing i-th pair = (1))) of with (2/, v.) Then,
O(z)- 0(+))
sup
(8(F) (x(F))
sup FEPBx
- (6(F)-6x(FF)
(78)
FEPSx
< sup
(8+;(F) - (F))
(79)
repSx
1 sup (L(,), F(z))) - (0y (0)1,,((C F()(
(80)
m FEABx
1
< E()), m
(81)
where 79 is obtained by using propertics of supremum and 81 By interchanging and =/, we obtain
follows from the definition of k, and E.
- 0(()) =(()).
(82)
m
Using McDiarmid's inequality, we obtain
P (0((2) E(((2)) 2 20) S exp
(<>)T)) (-
2me2
(83)
Using a similar argument as in the proof of Lemma 6.4 the proof follows that for every 8 E (0, 1), with confidence 1 - 5 the following holds:
log 1
((=) [[)( < <ET)
(84)
2m
The next lemma helps to bound B(O(=)) using Rademacher average of the class Ko-
23

---

Published in Transactions on Machine Learning Research (03/2024)
Lemma 6.6. B[O(z)] is bounded above as follows:
[[O(2)] S 2pL(T) (9 (mm.(KKa)
Proof.
The lemma has been proved as Lemma A.7 in Appondix
A.9
Using Lemmas 6.4
6.5 and 6.6 the result in Theorem 6.3 is proved.
6.3
Learning with Graph-Induced Operator-valued Kenels
In this section, consider the following class of functions
Ko = {K(z, -y: K E E.DEE,
(85)
where is defined as the graph-induced OVK given by
S'" toplsst y())ds:
K(r,
(86)
=g(2, 2. x'yy,
(87)
with 7, Yop > L, E L and D E D. Note that g(x, x(0-x') (L+Di(E=)) and Ty So' - y() (s)ds..
Now, in order to bound the Rademacher average Am, (Ko), we follow an approach inspired by Maurer (0166) and split the OVK K using properties on and T. Consider the class of functions defined as G (g(x.)) e ((+t=)(((+)))===--- corresponding to the scalar-valued kernel on X' x X.
Hg (g(xx.)llz I Rg. L L, D,y 0} where Hg is the RKHS
m
]
(Ko.(Koo)
sup sup sup ked vEY'EX
(x
,
(88)
m
y2
S E
sup sup sup kEg yey 1E
Σ <xk((0000 1) IT
(89)
m
sup vEY
Tyyly
E sup sup REG
Σ ( 1))
(90)
sup vEy
TTyly
A m;R (9).
(91)
In Equation 91 H Rt (9) denotes Rademacher average involving absolute values of real-valued functions
in G. For bounding Rademacher average A+ m: (9), we use the notion of covering numbers. Next, we provide the definition of covering numbers.
Definition 6.2 (Covering Numbers). Let (I, d) be a pseudo-metric space and S be a subset of F. For every E > 0, the covering number S by balls of radius with respect to d, denoted by N(S, e, d) is defined as the minimal number of balls of radius whose union covers S, namely,
N(S, = min n n (s,))f C F such that S c U B(s
j=1
where B(s,,e e) = (s E F: d(s, 9;) c).
Let Q be class of bounded real-valued functions defined on X, x (x(1) [m]) nm and Qlx [(Q(=()) : [m]) Q E 2} C Rm.. For norm induced by d on X, we define the d-norm empirical covering number of Q associated with as Na(Q, e, m) supxexm (2 d,
24

---

Published in Transactions on Machine Learning Research (03/2024)
Let U =supeeg E.g²}. Using construction similar to 124 and 125 in Appendix A.3
we obtain
g(x, = e (-tl-= - -11
where VAV, for a diagonal matrix A with non-negative eigenvalues of L D and V a orthonormal matrix. Consider an appropriate bound as Elg"] I a, Vg which is reasonable owing to the RBF-based
construction of scalar-valued kernels in G. Based Corollary 2.2.8 in (Van Der Vaart & Wellner 1996
can bound the Rademacher average using covering number
MRR (9) - - La Nagg
(92)
V
S
Vlog Nag
(93)
mm
To bound Na(G, e, m), we use Remark 11 in (Cucker & Smale 2002 to state that there exists C and q such that
R₂C !
log e, v
(94)
Based on our assumptions, there exists K >> 0 such that supyey [|T'll s K. Using 193 and 994 in 91 we obtain
(RC
(Ko) S (2q -2 1)
(95)
Using the result in 995 with 70 we can establish the generalization bounds for the class of kernels con- peerator-valued kernels. For the problem considered in this work, the loss is defined as Lyy. y') = (v()) - y 2d with E(1) s (3 + 1)² and L(I) S 2(3 + l). We obtain the following
structed with graph-induced
for 1, (0, 1), with confidence as
1/4
log }/ 2m
(, S 4p(33 + 3//11
+ ((B + +)² +
|| )
(96)
(2q - 1)/m
4, VX
8 +
K3
1//4
2aql CRC/R))CF2)) 2/24
1/1
+2
B
KB
log 1 2m
(97)
VX
(2q 1) 1)vm
4.9/4
[agK[[g C/a)1/20
1/4
2,2
log
(m Vx)
(K + vX)²
(98)
(2q
1)ym
2m
81/4 (RoC/()
1/4
log
8a
+
Am max(4((x 1),
2(N 1)
(99)
(2g
2
The inequality 99 is obtained using p /3(0)/A S B/VA, T up and || S kp. Now, a common assumption for smooth kernels of logarithmic decay of regularization error, i.e, R*(2) & c'X", where E (0, 1] and d' > 0 (Micchelli et al. 2016). Then the generalization error is bounded by
((F.) (FF)) +cx".
(100)
Consider the function HF(A) = & + e'X, then the minimizer is obtained for X (c/me') (c/mm))1/(+m))) with # (x*) = (nc)) [1+ 1/n] ( Therefore, for d (0,1), with confidence 1 - 8 we obtain
8(F)) E(F)) S (/(4)) (1 + 1/n) [( [/014 (3000200((/00 (2gg((RoC/a)17 1/29 1/1 (2q 1)
(1++m)
log à
g2
1/8" X
(101)
25

---

Published in Transactions on Machine Learning Research (03/2024)
where 21 = max + 1), 2(x + 1) 1101 ensures an upper bound for the generalization error with the help of a bound on the Rademacher average for the problem (22) of learning the OVK K₂ and the functional map F& in the induced RKHS corresponding to K2 by using a ball Bx in corresponding RKHS with a fixed
radius (considered as 1). The task of establishing a bound on the regularization error R (A) in (Miccholli jet al. 2016) considers an example prescribing value for 7) based on the hyperparameter in the RBF kernel. A similar pursuit in our setting is not straightforward because of the functional nature of the input space. Hence, we leave it for future work.
7 Experiments
In order to illustrate the effectiveness of the developed framework, we have used functional regression problem with an unknown graph structure in the input data for both synthetic and real datasets. The task of predicting output functions with the help of a Laplacian matrix denoting the relationship between the set of p input functions has been illustrated in the experiments. As practical data is always available as discrete observations corresponding to functions, standard FDA techniques can be used for the conversion of functional data into vector representation using basis functions, c.g. Fourier basis, B-spline basis, etc. Let X' x= ([] (()) and y = [[(( d)) be the input and outpul spaces, respectively. For our experiments, the error metric used is residual sum of squares error (RSSE) (Kadri et al.) 2016) defined as RSSE Ex (t) - (t) where y(t) is the actual output function and g( is the predicted output function. RSSE is better suited to compare functional outputs. The integrals involved have been approximated by using numerical integration in our implernentatinn. The quadratic programs involved in (3 and 15 are
solved by using CVXOPT (ndersen et al. 2023).
Experimental Setting: All methods were coded in Python 3.7 and the codes are made public All experiments were run a Linux box with 182 Gigabytes main memory and 28 CPU cores. As methods to solve the problem of functional regression problem simultaneously with learning L and/or D are not available, we use popular algorithms to first determine L. Then for the learned L, we use our alternating minimization framework to learn D using projected gradient descent and u using OpMINRES. For the MCP- based L learning and D learning in the proposed alternating minimization framework, we use a decaying step in the projected gradient descent. The decaying step-size regime involves starting with an initial step-size (e.g. 10-4) and roducing it by fixed factor (e.g. 2) after set of iterations (e.g. 5) continuously till final step-size (e.g. 10-9). In order to illustrate the effectiveness, we consider the following methods for comparison.
L is determined using fglasso (Qiao et al. 2019), based on a Gaussian func- tional model which provides a precision matrix (inverse of covariance matrix) corresponding to the nodes with corresponding functional input data. The approach develops an extension of the glasso criterion (Yuan & Lin, (007) to fglasso for functional data. The learned L is then used with our alternating minimization regime for optimizing
and D. OpMINRES is used with ki (x, G) e >> (L+t)(a==x") and t) = e topls-111 where 7 E (10-6,10=* 1,005,10-4 1,,00,11100 4,103,,, 1,003,10"2 10-2, 11022100111001 1, 100} and Top E (100-6 10-5, 10-4 10-3 100 2,002,10-1,, 1, 10, 100).
KGI-OPMINRES-D. I. is obtained by using Kernel Graph Learning (KGL.) (Pu et al. 2021b) prob- lem with respect to two kernel Gram matrices obtained for input signals and their timestamps which have been used to establish the relationship between input functions. RBF kernels have been consid- ered for the input functions. The hyperparameters for KGL are tuned using cross-validation in our im- plementation. The learned L is then used with our alternating minimization regime for optimizing u and D. OpMINRES is used with
G) = e->(x=z") (L=-)) and k2(s,t) = =e- - where Y E (10-6, 1,055, 10-4, 10-3, 10-2,10-1,1 10, 100} and Top E (10-6, 10-5, 10-1,10-3 10-2,10-1 1, 10, 100)-
Sparse OPMINRES---D: This denotes our proposed method where we used Algorithm 2 to learn u, L and D. Projected gradient descent is used in minimization with respect to L and D based on a decaying step-size. The sparsity is aided by the MCP regularization considered in learning of L. The graph-induced operator-
Coodes used for the experiments can be found at
26

---

Published in Transactions on Machine Learning Research (03/2024)
valued kernels are obtained using (=) = e e~>(z=>)) (1+ and (s( e euylss-t) where E {10-9, 10-5, 10000,1100
10- 10-3, 10-2, 1, 100) and Yop E (10-6, 10 1,,1001110 10-3, 10-2 10-1 1010, 100)-
As our framework is developed for OVKs, the proposed alternating minimization is well adaptive to consider generalized non-positive semi-definite OVKs (Saha & Palaniappan 2020) as graph-induced OVKs. We call this extension Sparse Don-PPs-OOMMINRES...... gradient dcscent is used in minimization with respoct to L and using the docaying step-size similar to Sparse OpMINRES-L-D. The sparsity is aided by the MCP regularization considered in learning of L. and
Sparse
Here too, projected
The graph-induced operator-valued kernels are obtained using k (x,
= (=(o==""((4+D(ee=====
10 10,1,,,,11, 10, 1003 and Topls Top2 E (2(s,)) f) e 70pplll-t) 7opala-11, where 7 {10-6, 100-0-- 1004 1,100,0,,,000000 10
{10 00-6,, 1000 9,10 100110100000 10 2, 10100011 10, 100}. Note that k2 is not necessarily a positive cemi-tefintte kernel.
Stopping Criteria: We claborate on the stopping criteria for the different algorithms used in the alternating minimization framework in Algorithm 2
OpMINRES:
The stopping criterion for OpMINEES is based on the following condition: the loop exits if the value of relative residual norms between the current residual norm and the initial residual norm is less than a threshold (e.g. 10-3 was used in our implementation).
Projected Gradient Descent: The projected gradient descent steps for both vech(L) and vech D) in Algorithm 2 use similar stopping criterion where the norm of difference between two consecutive iterates is compared to be less than a threshold (e.g. 10-3 was used our implementation).
MCP Regularization: The sparsity-inducing MCP regularization of vech(L) in Algorithm com- pares the norm of difference between two consecutive iterates against a threshold (considered as 10-3 in our implementation) as the stopping criterion.
7.1 Experiments with synthetic data
For synthetic experiments, three sets of experiments have been considered with input functions for graph structures having 3-nodes, 12-nodes and 25-nodes, respectively. The input functions are generated based on weighted cosine functions and constant functions with random noise. The corresponding output function is based weighted sine functions sharing the weights between input functions and output function (details are given in Appendix A.10
Data Generation:
For all the methods, truncated trigonometric basis of L 2T)) with 30 basis functions has been consid- ered for encoding the functional data. The experiments were run for three settings where the data has been divided randomly into a training set, a validation set and a test set. The following data splits have been con- sidered: (80/20/20) 20/) (160/40/40) and (320/80/80), representing the number of training samples/validalles samples/ /test samples.
The results for synthetic data with 12 nodes are summarized in Tables that Sparse OpMINRES-T-D obtains comparable performance based mean RSSE on the test data in all three settings where 80 samples, 160 samples and 320 samples have been used for training. Both fglasso- OpMINRES-D and KGL-OPMINRES--D essentially predict a graph structure first and then use it for the functional regression problem. Sparse OpMINRES-LDD and Sparse unified approach which incorporates sparse graph learning with the functional regression task. In Table D the learned graphs are illustrated where darker colors of edges indicate larger edge weights. Table [ illustrates that -glass--OMMINESS- fails to differentiate between the interactions of input functions and results in fully connected graph consistently. Though, KGL-OPMINRES--LD in comparison to fglasso- OpMINRES-L-D produces sparser graph structure, SpaNN--OMIINRES---DD learns sparse graph structures exhibiting relations that can incorporate the associations enforced in the generation process. The learned associations provide required correlations which can benefit the functional regression task. Further details of the synthetic data including experiments for nodes and 25 nodes are given in Appendix [A.10] Sparse Non-Pos-Opp OpMINRES--LLDD also learns sparse graph structures which are informative of synthetic data used for the functional regression task.
From Table 2 observe
Pan-Pos-OPMINRES-E
present a
27

---

Published in Transactions on Machine Learning Research (03/2024)
Table 1: Graphs corresponding to learned I. for 12-node synthetic data, [Best viewed color)
Train/ Val/ Test samples
Sparse OpMINRES-L-D
fglasso- OpMINRES-D
KGL- OpMINRES-D D
Non-Pos- Pos- OpMINRES-LL
80/20/20
acalc
160/40/40
320/80/80
Additional Experiments: Appendix A.10.3 contains the results of experiments conducted as an ablation study in the 12-node setting.
7.2 Experiments weather data
Weather data dynamic and inter-rclationships between different parameters can be hard predict. As our problem solves functional regression problem based on a relationship between of input functions, we intend to showcase the effectiveness of the proposed algorithm by predicting average dew-point temperature
28

---

Published in Transactions on Machine Learning Research (03/2024)
Table 2: Mean RSSE results for 12-node synthetic data.
Mean RSSE
Train/Val/ Ves/TTest samples
Mothods
Train
Val
Test
Sparse OpMINRES--L-D
1.140691
1.780445
1.583640
80/20/20
(IlaSO-OOMMINRESS-
1.243734
1.821687
1.700265
KGL-OPMINRES-D
1.061473
1.775388
1.554853
Sparse Non-Pos OPMINEESLDD
1.167264
1.806093
1.618175
Sparse OpMINRES-LLD
0.888574
1.229568
1.385952
160/40/40
SplaSSo-OPMINREES-DD
0.956907
1.285154
1.305025
KGL-OPMINRES.
0.983432
1.260719
1.286481
Sparse Non-Pos-OOMMIREESLJJ
1.154356
1.362239
1.417921
Sparse OpMINRESSLLD
1.062102
1. 1.294110
1.239181
320/80/80
fglasso- OOABSO-SDMINNRESDDD
0.947426
1.336192
1.271646
KGI-OOMINRESS-D
0.980995
1,299266
1.252706
Sparse Non-Pos-
1.073292
1.295140
1.243346
(F) across 12 weather stations based on their respective air temperatures (F), We consider minnte data of Wyoming ASOS data collected from IEM ASOS One Minute Data (Iowa Environmental Mcsonet 2022). The data has been collected for an interval of hours for both input. functions and output function from Jamuary, 2022 to August, 2022. Data collected at one minute interval for different 12 weather stations in Wyoming pre-processed to create 2 hour interval data by disregarding intervals where data was missing in any of the 12 stations. A total of 718 samples have been collected after removing missing data.
For all the methods, a truncated trigonometric basis of [ 1]) with 80 basis functions has been considered for encoding the functional data. We segregate the weather data experiments into small weather data experiments (Appendix (A.10) by considering 120 samples and full weather data experiments. The following random data splits have been considered: (80/20/20) and (472/123/1) 123/113), representing the number of training validation samples/ /tstt samples in small weather data and full weather data scttings, respectively.
Tables B showcase the performance of the algorithms for full weather data considering all 718 samples. Sparse OpMINRES-L-D performs the best in terms of mean RSSE on the test data compared to fglasso- OPMINRES-LDD and KGGL-OPMINEES-LD (Table 4. The maps in Table 3 describe the geographic posi- tioning of the weather stations in Wyoming and the edges between them indicate potential inter-relations between the stations. In Table 3 fglasso-OpAin -OMasS--OMMNRRES-III nected graphs which do not provide much information regarding the impact of different weather stations the relationship of respective air temperature to the average dew point temperature. Sparse OpMINRES-LLD learns a sparse L. where stations BPI(1) and CPR(2). P60(7) and SHR(10) along with RIW(8) and WRI((1) are connected. [PI(() (42.58507, 111.1,,1111111110 -110.11115) and CPR(2) (42.908, -106.46442) are 300.7 km apart with an clevation of 2124 m and 1612 m, respectively. P60(7) (44.54444, 110.42111) and SHR(10) (44.77, 11777--166.0 106.97) are 274.85 km apart with an elevation of 2368 m and 1209 m, respectively. RIW(8) (43.06423, 1088445984 and WRL(12) (43.96571, 100.1107900000000 be observed that the connections in the learned graph structure have been established between stations with varying elevations lying in close proximity latitude-wit wise.
and (GLL-OMMNNESS-LA learn dense fully con-
are 108.28 28 km apart with an clevation of 1688 m and 1294 m. It can
To illustrate the utility of our proposed sample-based approximation algorithm, we use the full weather data and evaluate it to produce the results in Table 5 for all algorithms. The results in Table 5 show that the sample-basee based approximation algorithm provides comparable results using only a few samples. In 5 runs, out of 472 training samples, the number of samples in the working set of the sample-based approximation algorithm varies between 123 to 200. Sparse OpMINRES-L-D performs the best in terms of the mean RSSE test data.
29

---

Published in Transactions on Machine Learning Research (03/2024)
Table Graphs corresponding learned for full weather (472/123/123) data. [Best viewed in color
Sparse OpMINRES-I-D
(tlasso-OMMNNEES,
KGI-OPMINEES-
Log
Table 4: Mean RSSE results for full weather data.
Mean RSSE
Train/Val/Tie samples
Methods
Train
Val
Test
Sparse OpMINRES-L-D
0.002938
0.009891
0.010743
472/123/123
Bglasso-OpMINRER KGL-OPMINRES-D
0.021094
0.013476
0.044216
0.003474
0.010877
0.012797
Table 5: RSSE (mean + standard deviation) results over 5 runs for sample-based approximation algorithm using full weather data.
Mean RSSE
Methods
Full Train
Train subset
Test
Sparse OpMINRES-L-D
0.083688 + 0.011229
0.010584 0.006664
0.013568
0.000914
0.097118 0.01392
fglasso-O OPMINRES-DD
0.112057 1 0.004981
0.011457 + 0. 0.006908
0.014289 + 0.000710
0.130591 + 0.006171
KGL-OPMINRES-D
0.131076 0.016523
0.010166 0.005781
0.013702 0.000561
0.100619 0.017939
30

---

Published in Transactions on Machine Learning Research (03/2024)
Table 6: Mean RSSE results for NBA data.
Mean RSSE
Train/Val, Val/TTett Test samples
Methods
Train
Val
Test
233/50/59
Sparse OpMINRES-L-D
0.025200
0.087748 0.191459
0.106344 0.265513
OpMINRES-D
0.023261
Table 7: RSSE (mean + standard deviation) results for sample- based approximation algorithm for NBA
data.
Mean RSSE
Methods
Full Train
Train subset
Val
Test
Sparse OpMINRES-I-D OpMINRES-D
0.215943 0.002837 0.018371 0.001621 9.070595 + 0.138830
0.066631 0.003058
0.141214 0.004665 0.452081 + 0.020617
0.005005 + 0.002031
0. 0.180238 + 0.013531
7.3 Experiments on NBA data
The movement of basketball and 21 players involved on the court (x-y coordinates) in the Atlanta Hawks (ATL) vs Utah Jazz (UTA) match on November 15, 2015 has been considered in this experiment. This data is available in the Github repo NBA Movement Data (Seward) 2018). The data has been collected for different plays for both imput functions of 21 players and output function denoting the position of the ball, which includes missing data corresponding to some players in different plays. As plays a balketball game are of different time duration, we use truncated trigonomctric basis of L. ([0, 1]) with 80 basis functions sample the functions at fixed 100 points [0, 1]. A total of 351 samples have been collected after removing missing data. A random data split of 0523/59/55 representing the number of training samples/validattee /alidation samples/ton /tsst samples has been considered. The problem requires solving a multi-dimensional functional regression problem which is incompatible with fglasso and KGL algorithms, as both fglasso & KGL are based on single dimensional input functions. Hence, we compare our method with the algorithm OpMINRES-D where a fixed L is incorporated in our alternating minimization framework.
OPMINRES-DD A fixed L is considered corresponding to a fully connected network of 21 nodes. This decision was made fggassoo mostly learns fully connected graph in earlier experiments. Thus, a fixed L (with no sparsity-inducing MCP) is used in the proposed alternating minimization regime for optimizing u and D. OpMINRES is used with by (x, G) = ==>=(==²)) (L+D)(e-=' (<-))))("=="""(-((-->>>"">>>> and (s, = e o->opls-t1,,b (s, t) = e 1-21---1 where Tv E 10-5 10 10 20,10-220000 1001 1,,,,,,110,00,,,, 10, 100} and 7ap. Yop E {10-6, 6 10-5, 10-1 10-3, 10-2, 100-2,1000 10-1,111111000 10, 100).
Sparse OPMINRES-L-D. We consider the graph-induced operator-valued kernels using (1 x'; = e (=-2'') (L+D)(=->') - - " (L+D)(==-')) and (s, = = -opls ,, t) = e lstt where 7ax Tv E
{10-6, 6 1,05,, 10-4, 10-3, 10-2 1011,011,,, 10, 100} and Top 70p E (110-6,100 10-10- 101--,10--000 10-4,10-3,, 10020000-1,,,,011111111011000001 1,,,,, 10, 100). Projected gradient descent is used in minimization with respect to L and D based on a decaying step-size. The sparsity aided by the MCP regularization considered in learning of L.
The results are illustrated in Tables 0 and S where comparison method OpMINRES-D uses a fully connected graph, however Sparse Op.INNES-LLD performs better with sparse learned graph in terms of mean RSSE the test data. Observations for the match have been published in the match reports ESPN match recap and ESPN match scoreboard ESPN 2015a b). In Table g the depiction of basketball court is provided where the players have been arranged on the court with ATL players on the left. and UTA players on the
right. The graphical structure corresponding to the learned L in Table [] illustrates strategic relationships between players of both ATL and UTA. The connoction between Derrick been pivotal for Utah Jazz. The performance of Al Horford in (4-7) and Kent Bazemore in (2-11) for Atlanta. Hawks has been captured. Though the partnership of Alec Burks -Trey Burke (9-18) for Utah
Levorr-Trever Booker (6-8) had
Tarrs-Treey
31

---

Published in Transactions on Machine Learning Research (03/2024)
Jazz is not evident in the match reports, their ball carrying interactions may be the reason for being learned in L.
Table 8: Graphs corresponding to learned L for NBA data (233/59/50) of ATL (left) vs UTA (right) match using Sparse OpMINRES-LLE L-D. [Best viewed in color)
15
18
19
20
11
13
20
16
18
-2
Log scale
The performance of sasele-based approximation algorithm has been showcased on NBA data in Table 7 Using the sample-based approximation algorithm, out of 233 training samples, the number of samples chosen in the working set of samples runs varies between 57 to 62. Sparse OpMINRES-I-D performs the best in terms of the mean RSSE on test data. The remaining results and details of experiments are in Appendix A.10 The best. hyprrparameters for the experiments conducted have been listed in Appendix A.10.4
32

---

Published in Transactions on Machine Learning Research (03/2024)
8 Conclusion
In this work, we incorporate learning of suitable graphical structure which drives a functional regression problem where the output function depends the input functions and also upon their inter-relationships with each other. An alternating minimization based algorithm has been proposed to learn the Laplacian matrix L, a non-negative diagonal matrix D characterizing the graphical structure, along with the map from imput space to the output space. For a fixed L and D, the functional regression learning problem is formulated as an operator system of equations which is solved by using OpMINRES algorithm. Projected gradient descent is used to learn the Laplacian matrix and the non-negative diagonal matrix in the alter- nating minimization framework. A sparsity-inducing regularizer (e.g. MCP) in L has been incorporated during the alternating minimization, which helps in learning graphical structure and allows for improved interpretability and can highlight interactions which most relevant among imput functions useful for the prediction. To make the proposed algorithum scalable, sample-based approximation algorithm has been proposed which helps reduce the computations required for solving linear system of operator equations using OpMINRES algorithm. An extension of the alternating minimization framework has also been proposed to solve the limesiaimeniional functional regression problem assuming a single graphical structure on the input variables. The generalization analysis provides a bound on generalization error for learning a graph-induced OVK. Experiments establish the utility of proposed graph-induced operator-valued kernels in functional regression problems from diverse applications.
Broader Impact Statement
The framework and algorithms introduced the paper with graph-induced operator-valued kernels aid learning a sparse graphical structure which drives a functional regression problem where the output function depends on the input functions and their inter-relationships with each other. This will promote research in investigating more sophisticated techniques for handling functional data with inherent graphical structure ingrained among them. To the best of our knowledge, our work does not have any negative impact.
Acknowledgments
We thank our anonymous reviewers for their insightful comments and suggestions. We declare no competing interests.
References
Roya. Aliakbarisani, Abdorasoul Ghasemi, and M. Ángeles Serrano. Perturbation of the normalized laplacian matrix for the prediction of missing links in real networks. IEEE Transactions on Network Science and Engineering, 9(2):863 874, 2022. doi: 10. 10.100//TN5E.202133357588 231733762...
M. S. Andersen, J. Dahl, Z. Liu, and L. Vandenberghe. Interior-point methods for large-scale cone program- ming. In S. Sra, S. Nowozin, and S. J. Wright (eds.), Optimization for Machine Learning, volume 55-83. MIT Press, 2012.
Martin S Andersen, Joachim Dahl, Lieven Vandenberghe, el al. Cvxopt: python package for convex optimization. version 1.3, 2023. URL https://cvxopt..rg
Francis R. Bach and Michael I. Jordan. Predictive low-rank decomposition for kernel methods. In Proceedings of the 22nd International Conference Machine Learning, ICML, '05, pp. 33-40, New York, NY, USA, 2005. Association for Computing Machinery. ISBN 1595931805. doi: 10. 10.1145/1102351.110222 https://dbi.org//D0
URL
1102356.
Juan Lucas Bali, Gracicla Boente, David Tyler, and Jano-Ling Wang. Robust functional principal components: A projection-pursuit approach. The Annals of Statistics, 39(6):2852 2882, 2011. doi: 10.1214/11-409923, URL. https:///oii..... 0rg/10.1214/11-40522
33

---

Published in Transactions on Machine Learning Research (03/2024)
Onurcena Banerjee, Laurent El Ghaoui, and Alexandre d' d'Aspremont. Model selection through sparse maxi- mum likelihood estimation for multivariate gaussian or binary data. Jourmal of Machine Learning Research, 9(1):4885 516, 2008. URL http://ht....orrmo/oo////////aaa
R. B. Bapat, S. J. Kirkland, and S. Pati. The perturbed laplacian matrix of graph. Linear and Multi- linear Algebra, 49(3):219-242, 2001. doi: 10.1080 0030810000008186666 URL htttp:://6..org/100..0
03081080108818697
Dimitri Bouche, Marianne Clausel, François Roueff, and Florence d' A'Alché Buc. Nonlinear functional output regression: dictionary approach. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of
Machine Learning Research, pp. 235-243. PMLR, 13-15 Apr 2021. URL htttps:/pproceedings. .ml...mm.r.....................m
gress/vv30/boucche21a html
Romain Brault. Large-scale operator-valued kernel regression. Theses, Université Paris Saclay, July 2017.
URL https://hall sccce//eeeeee/////11711..1...
Romain Brault, Markus Heinonen, and Florence Buc. Random fourier features for operator-valued ker- nels. In Robert J. Durrant and Kee-Eung Kim (eds.), Proceedings of The 8th Asian Conference on Machine Learning, volune 63 of Proceedings of Machine Learning Research, pp. 110 125, The Universily Waikato, Hamilton, New Zealand, 16-18 18 Nov 2016. PMLR. URL https::/prooeedings. mlr htt.iiigggmmrrrrres///// v63/Brault39. html
Sou-Cheng Choi. Iterative methods for singular linear equations and least-squares problems. PhD thesis, Stanford University, 2006.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American malhemalical sociely, (9(1): (11):1149,.100
49, 2002.
Alexandre d' d'Aspremont, Onureena Banerjee, and Laurent El Ghaoui. First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and Applications, 30(1):56-66) 66, 2008. doi: 10.1137/060670985. URL
T.I. Dikin. Iterative solution of problems of linear quadratic programming. Doklady Akademiia Nauk SSSR, 174:674-675, 1967.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Picrre Vanderghoynst. Learning laplacian matrix smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23):6110 6173, 2016. doi: 10.1109/TSPP S.SP.2016.2602220
ESPN. Jazz beat hawks 97-96 to end 3-game skid. 400828035 2015a. Accessed: 15/10/2023.
ESPN. Atlanta hawks vs utah jazz box score. http:///wwweepppp.ccam//////oppr
400828035 2015b. Accessod: 15 15/10/0033
Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle prop- erties. Journal of the American Stalistical Associalion, 96(456):1348 1360, 2001. doi: 10.1198/ 016214501173382273 URL httpss://doi.
F. Ferraty and P Vieu. Nonparametric Fanctional Data Analysis, Theory and Practice. Springer Series in Statistics, New York, 2006.
Mostafa Reisi Gahrooei, Kamran Paynabar, Massimo Pacella, and Jianjun Shi. Process modeling and prediction with large number of nigh-dimensional variables using functional regression. IEEE Transactions on Automation Science and Engineering, 17(2):8846696 2020. doi: 10.1 20S.TTTSSE..........
Gene H. Golub and Charles F. Van Loan. Matriz Computations. Johns Hopkins University Press, 3rd ed edition, 1996.
34

---

Published in Transactions on Machine Learning Research (03/2024)
Ana María Estrada Gómez, Kamran Paynabar, and Massimo Pacella. Functional directed graphical models and applications in root-cause analysis and diagnosis. Journal of Quality Technology, 53(4):421 -437, 2021. 1800.0003000 URL httpp://oo...rr//....00000222222 2020 1805380
doi:
Clara Happ and Sonja Greven. Multivariate functional principal component analysis for data observed different (dimensional) domains. Journal of the American Statistical Association, 113( 659, 2018. doi: 10. 00.10000116214550 62011191119.000 20..2011..2122 URL
Harold V Henderson and SR Scarle. Vec and vech operators for matrices, with some uses in jacobians and multivariate statisties. Canadian Journal of Stalislics, 7(1):65 81, 1979.
Harjit Hullait, David S. Leslie, Nicos G. Pavlidis, and Steve King- Robust function-on-fuucctio regression. Technometrics, :3396 409, 2021. doi: 00..0880000001777.2200..22222230 URL https://doi. org/10, 1080/00401706. 2020 1802350
Pierre Humbert, Batiste Le Bars, Laurent Ondre, Argyris Kalogeratos, and Nicolas Vayatís. Learning laplacian matrix from graph signals with sparse spectral representation. Journal of Machine Learning Research, 22119)):1-47, 2021. URL http:://jmiie jttp://iwr.orrrrpppe////////////
html
Iowa State University Iowa Environmental Mesonet. Iem
Asos one minute data. https://nesonet.
agron. iastate. edu/reqquest/asoo//nnn phtml 2022. Accessed: 15/10/2023.
Julien Jacques and Cristian Preda. Model-based clustering for multivariate functional data. Computational Statistics 8 Data Analysis, 71:92-106, 2014. ISSN 0167-9473. doi: http::///b..orgg//0001/////// 2012. 12.004.
Hachem Kadri, Emmanuel Duflos, Philippe Preux, Stéphane Canu, Alain Rakotomamonjj, and Julien Au- diffren. aperator-valued kernels for learning from functional response data. Journal of Machine Learning Research, 17(20):1-54 54, 2016. URL http://jmlr.... http:///ww....pppp///////1//11-/
Sven Kurras, Ulrike Luxburg, and Gilles Blanchard. The I-adjusted graph laplacian: a diagonal modifica- tion with a geometric interpretation. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1530-1538, Bejing, China, 22-24 24 Jun 2014. PMLR. URL https://proceedings. .ml......r.... wtt.gsm..r...pes/3222.. press/v32/ kurras14 html
Cornelius Lanczos. An iteration method for the solution of the eigenvalue problem of linear differentiol and integral operators. United States Governm. Press Office Los Angeles, CA, 1950.
Heng Lian. Nonlinear functional models for functional responses in reproducing kernel hilbert spaces. Canadian Journal of Statistics, 35(4):597 606, 2007. doi:
URL
Renjie Liao. Notes on rademacher
Rademacher Crotmaahhhrrooopeiiittyyc .pdf 2020. Accessed: 28/10/2023.
Andreas Maurer. vector-contraction inequality for rademacher complexities. In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles (eds.), Algorithmic Learning Theory, pp. 3 17. Springer International Publishing,
2016. ISBN -78-3-319-46379-7
Giacomo Meanti, Luigi Carratino, Lorenzo Rosasco, and Alessandro Rudi. Kernel methods through the roof: Handling billions of points efficiently. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 14410-14422, Cur- Associates, Inc., 2020. URL http:://ppeeeelta...eeerrppeeppp B39ctb17788ae3333222556667666862
Nicolai Meinshauson and Peter Bühlmann. High-dimensional graphs and variable selection with the Lasso.
The Annals of Statistics, 34(3):1436 1462, 2006. doi: 001224/09903000000223. URL https:
35

---

Published in Transactions on Machine Learning Research (03/2024)
Charles A. Micchelli and Massimiliano Pontil. On learning valued functions. Neural Computation, 17 (1):177-204, 2005. doi: 10.1162/0899760052330000
Charles A. Micchelli, Massimiliano Pontil, Qiang Wu, and Ding- Xuan Zhou. Error bounds for learning the kernel. Analysis and Applications, 14(06):849--)) 8688,,86,.-10 2016. doi: 10.112250021955554440011. URL
htttps://di...o httgg//....///00/3335111...011
Junier Oliva, William Neiswanger, Barnabas Poczos, Eric Xing, Hy Trac, Shirley Ho, and Jeff Schneider. Fast Function to Function Regression. In Guy Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Bighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 717-725, San Diego, California, USA, 09-12 May 2015. PMLR. URL mlr. ptw.s/peeeeeeeeeeeee http//38//lll/ hlt.//vvvv1....mmm
Xingyue Pu, Tianyue Cao, Xiaoyun Zhang, Xiaowen Dong, and Siheng Chen. Learning to learn graph topologies. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4249 4262. Cur- ran Associates, Inc., 2021a. URL https::/ neurips. nowppp..ccppppprrrrr.. httprp/sscc/ppppr..ll//////////p fttps//aapp//2//////220
Xingyue Pu, Siu Lun Chau, Xiaowen Dong, and Dino Sejdinovic. Kernel-based graph learning from smooth signals: A functional viewpoint. IEEE Transactions on Signal and Information Processing over Networks, 7:192-207, 2021b. doi: N0.1109/TSIPN.N 20..3.000.30
Lishan Qiao, Limei Zhang, Songcan Chen, and Dinggang Shen. Data-driven graph construction and graph learming: review. Newrocomputing. 312:336 351, 2018. ISSN 0925-2312. doi: https://
1a..or///0..016/...neeeeem 20..000.00.. http:///p/pp////ooccccaacttttttr 50925231218336666
Xinghao Qiao, Shaojun Guo, and Gareth M. James. Functional graphical models. Journal of the American Statistical Association, 114(525):211 222, 2019. doi:
htRp::/p::///d
org/10.1090/01622100 1080/01621499 2017 1390466
Xinghao Qiao, Cheng Qian, Gareth M James, and Shaojun Guo. Doubly functional graphical models in high 431, 02 2020. ISSN 0006-3444. doi: 10.1093/ 10.1093/biomet bwoobooo/tttaaaaae /asz072. URL
dimensions. Biometrika,
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, vol- ume 20. Curran Associates, Inc., 2007. URL https://proceeedngss neurips cttppps.cccppaaae pccppappr/2007/f1eee .dff
J. O. Ramsay and C. J. Dalzell. Some tools for functional data analysis. Journal of the Royal Statistical Sociely: Series B (Methodological), 53(3):539 561, 12 2018. ISSN 0035-9246. doi: 10.1111/1.2517-6611.
1991.tb0184..x. URL https:://oii.ooo 10. 1111/j 2517-61611 111111112211111111111111 www.99.....1444.....
James O. Ramsay. When the data are functions. Psychometrika, 47(4):379-396, 1982.
Aniruddha Rajendra Rao and Matthew Reimherr. Modern non-linear function-onnfunetton regression. Statis-
tics and Computing, 33(6):1 12, 2023.
Fabrice Rossi and Nathalie Villa. Support vector machine for functional data classification. Neurocomputing 7937 742, 2006. ISSN 0925- 2312. doi: http:////bbioor///..l////uuuuuu www www.sciencedirect. http:////...ae.eeeerecc///////// 13th European Symposium on Artificial Neural Networks.
12.010. New Issues in Neurocomputing:
Akash Saha and Balamurugan Palaniappan. Learning with operator-valued kernels in reproduc- ing kernel krein spaces. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (ods.). Advances in Neural Information Processing Systems, volume 33, pp. 13856-13866. Curran Associates, Inc., 2020. URL httpss:/pproceedinng http://///pooonnnn..rrr...p..p. gr:19990aa71100000000055551000.0 pdf
36

---

Published in Transactions on Machine Learning Research (03/2024)
Neil Seward. Nba movement data github repo. http:///gghhaa.ooo///saeeeeeeeer 2018. Accessed: 15/10/2023.
John Shawo-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge university press, 2004.
Alexander J. Smola and Bernhard Schölkopf. Sparse greedy matrix approximation for machine learning. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Leorning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 July 2, 2000, pp. 911 918, Morgan Kaufmann, 2000.
Aad W Van Der Vaart and Jon A Wellner. Weak convergence and empirical processes: with applications to slatistics, volume Springer, 1996.
Mariana Vargas Vieyra. Robust estimation of laplacian constrained gaussian graphical models with trimmed non-convex regularization. In Antonio Salmerón and Rafael Rumí (eds.), Proceedings of The 1 11th International Conference on Probubilislic Graphicul Models, volume 186 of Proceedings of Machine Learning Research, pp. 85 96. PMLR, 05 07 Oct 2022. URL https::/pproceeddngs mlr. press/v186/ vargas vargas-vleyra22a.hr 2leyra22a.html
Christopher Williams and Matthias Seeger. Using the nyström method to speed up kernel machines. In T. Leen, T. Dietterich, and V. Tresp (eds.), Advances Neurul Information Processing Systems, vol- ume 13. MIT Press, 2000. URL https: https://pppet https/////ooeeeeg...eeoe
fwwesllllpaaaee silee//paper/200/f11ee
pdf
Qiang Wu and Ding-Xuan Zhou. Analysis of support vector machine classification. Journal of Compulational Analysis & Applications, 8(2), 2006.
Fang Yao, Hans- Georg Müller, and Jane-Ling Wang. Functional data analysis for sparse longitudi- nal data. Journal of the American Statistical Association, 100(470):577-590, 2005. doi: 10.1198/ 0162145040000017455, URL
Jiaxi Ying, José Vinícius de Miranda Cardoso, and Daniel Palomar. Nonconvex sparse graph learning under laplacian constrained graphical model. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances Newral Information Processing Systems, volume 33, pp. 7101 7113. Cur- ran Associates, Inc., 2020. URL https://proceddings wwwpiinnnnnnnuus... wwwpuriis.ccppppeeeee wtt.c/ppee..ieeeppppp//////////e fitees/paper/222//ELL 4ef (eff3800cc666510018856666666688-
pdf
Yiming Ying and Ding-Xuan Zhou Learnability of gaussians with flexible variances. Journal of Machine Learning Research, 8(9):249-217) 276, 2007. URL http://jmlr http::///l...r//pppppppreeeeeeee httpp//rrww...pppp////////////aa
Ming Yuan and Yi Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94 (1):19-35, 03 2007. ISSN 0006-3444. doi: 10.1093/bion 1.1093/biome///sm011.. URL https://doi. http::://doooor/100/// org/10.10933 1093/ biomet/asm018
Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statistics, 38(2):894 - 942, 2010. doi: 10.1214/09AA0572) URL https:://ai..rrg/// 1tt.://ooorrr...1111-1---00000 2214/09-A0S729
Yangjing Zhang, Kim-Chuan Toh, and Defeng Sun. Learning graph laplacian with mcp. arXiv preprint arXiv:2010.110 11559, 2020.
Boxin Zhao, Y. Samuel Wang, and Mladen Kolar. Direct estimation of differential functional graphical models. In Н. Wallach, Н. Larochelle, A. Beygelzimer, F. W'Alhé-Bucc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proocedings..t nwwriss..nr....... cctpappecccppppprr httprppp..//pppeee..ee/////////s T2604405507771110000044666666662
37

---

Published in Transactions on Machine Learning Research (03/2024)
A Appendix
A.1 Functonal Regression with Known Graph Structure
In this section, we motivate functional regression problem with known graph structure. Consider a system where a set of imput functions determines the output (or response) function. Let the system be modeled based on p imput functional variables z1 (2)) (t((t,,, where z; E (20 1),, E [p]. A functional response variable y(t) is used to model output of the system where y E [2( 1]). (Note that [o, 1] can be replaced with any closed time interval based on the application.)
The undirected graph structure of the functional input variables is represented by G (V, where V= fer. .2,..... Up} and E = ffus 12 Hu; is connected to ey, 1 I i,j S p) is the edge set which characterizes the underlying relationship between the variables. Note that the notation for an edge uses an unordered pair for, 2z} which characterizes the undirected nature of the graph G. In order to model the relation between functional input variables æ1, ......, Ip and functional response variable y, we use the following map F:
y = (2,,, G).
(102)
Note that F now depends explicitly on the graph G in addition to the input functions I1, T2,..... Zp. Here, we consider a scenario where G is known. Recall the example of a manufacturing factory, where the put of emissions depends on the metrics of different components involved in the manufacturing process. The graph G is determined in this case by understanding the components which are connected during the manufacturing process.
We consider the notations arbitrary sample (ar, (). To learn the mapping F, consider the training data of n samples given
(I1, 221,, X (= (I,, 1))) and y E V- ('), to represent
{(x1), ) where 2(()) = (a1 Th x...,,p x/
(*) E X and y1 E V. In order to learn F', we develop an operator-valuee kernel which can leverage the structural information of G.
(t)
Towards this, we first introduce an operator-valued kernel which maps the elements of X x X to set of bounded linear operators over the output space y, denoted by C(V). We formally define OVK as follows.
Definition A.1 (Operator-valued Kernel). (Kadri et al. 2016 An [()))-vlued kernel K on X2 is a function K ((.,.) X x X + L()), satisfying the following properties:
1. K is Hermitian, that is Vw, E X, K(,, 2) K K(zww) (* denotes the adjoint operator),
2. K is positive semi-definite on X2, that is K is Hermitian and for every natural number r and all ((w(), (e()) X V, the matrix with (i.5)-th entry given by (K(w(), w(l))(( u())) is positive semi-definite
Constructing an operator-valued kernel based Definition A.1 is challenge verifying both properties of being Hermitian and positive semi-definiteness becomes non-trivial. A construction of OVK that satisfies
both the propertics in Definition A.1 has been proposed in (Lian 2007 Kadri et al. 2016). The OVK construction in (Lian] 2007; Kadri et al.] (0166) uses a scalar-valued kernel kn on X' x X' and a Hilbert- Schmidt integral (HSI) operator defined on the output space y, and is given as follows:
= (x, S' ke(ss ())()sss,
(103)
where b2 inside the HSI operator So (s, t)y(s)ds is scalar-valued kernel on R x R. If h is positive semi-definite and if 22 is positive semi-definite (implying that the HSI operator is positive semi-definite), then the construction in 103) is known to be positive semiidefinite (Kadri et al. 2016). We will now adapt the OVK in [10pp to include the graph structure information present in G. An obvious choice for using the influence of graphical structure G in the functional regression task is to use the adjaconcy matrix of G. but the adjacency matrix of G not being necessarily positive semi- definte makes its utility restrictive. The Laplacian matrix of graph G, on the other hand is useful in this respect as it has the desired property of
38

---

Published in Transactions on Machine Learning Research (03/2024)
being positive semi-defiiite which is useful in a kernel-based learning framework. The Laplacian matrix of undirected graph G = (V, F.,, with V as the node set and E. as edge set is defined as I= ID A, where ID = diag(deg(v1)) deg(u2),... deg(u))) is the degree matrix and A is the adjacency matrix of the graph G. The elements of are given by
deg(
if =. j. if + j and tyr E E, otherwise.
Lij =
1,
(104)
0,
We propose to incorporate the graphical structure in Equation as follows:
103
within the scalar-valued kernel ky itself,
b (x, (z))) = = "L'LL', x <> 7>0,
(105)
=7 Σ +J=1
2,(t)Liza((tdds
(106)
The construction k 105 involves capturing the graphical structure of G using L x Lx'. We use an equivalent expression (z, Lx')p Lx', where the inner product (: X X' is defined (z, x¹) = So (t)d). The inner product (z,z"), measures the similarity between x and x' in X. Let 1= [1,, 1,, l2,..., Lp). where I represents the i-th column of L,, then Lx' is computed based on standard matrix-vector multiplication where elements of are multiplied with x' by using scalar multiplication and addition of functions as Lx' Ei= L,zy. Equation (105) provides a tool measure similarity between v, E X' where the interactions are encoded in the underlying graph G using the Laplacian matrix L. If k defined in (155) can be proved to be a valid positive semi-definite scalar-valued kernel X' x X, then OVK can be defined similar to the construction in Equation (103). Next, prove that such a construction is indeed possible.
Proposition A.1. For an underlying graph G = (V, with [V| p. functional variables x = T2,..,,...,42 E X' (I, 1))))) and functional response variable y E (= (20 consider an operator-valued kernel K : X L())) defined as
L. ke (r((st))(s)dd
(K (1) -
, > 0 and by is a positive semi-definite valued kernel on R. Then where kn (z)z 7x TxL, K is positive semi-definite.
Proof. Please see Appendix A.3 for the proof.
Recall the constouction of scalar-valued radial basis function (RBF) kernel defined over Rd Rd (d E Z,) as e ->>1lx=x'1 for > 0, x,x' E Rd based on the kernel x x. Similar to that construction, we now describe an extension for kernel y defined in (105). The kernel notation by (I, G) =x=" Lx' is overloaded to represent the following RBF-type kernel:
k (x -= M(- Mx==') ((x-))
0.
(107)
capturing the interaction of x' using L (see Appendix A.3 The RBF-type kernel in 107 is improved version of the kernel in (105). as it can approximate higher dimensional relationships better owing to the exponential nature and shift invariant property given by by (x+ +h; +h; G) = (z, x²; G), Vz, x', h E X. Note that when computing (x - =x)) L(x - x'), where x = "p)....,pp)... x' = (a',..., x,) E X, the interactions between the unlike pair (z,, 2)), # would negate the influence of the like pair (æ,, xf), because of the structure of L (defined in (104)). Therefore, we propose to use a diagonally perturbed Laplacian (Bapat) et al. 2001) aid the functional regression task performance. Perturbed Laplacians have found applications in spectral clustering, analysis of graphs (Kurras al. 2014) and missing link prediction in networks
39

---

Published in Transactions on Machine Learning Research (03/2024)
Aliakbarisani et al. 2022 A natural perturbation of Laplacian for the scalar-valued kernel hn in (077 involves the degree matrix D leading to the following definition for ly:
k1 (1 GG;) = v- (L+D)<==)) >>0, O, for x, E X.
(108)
Incorporating DD with L in kn improves the representation of individual components of x, x' in prediction of as the like pair (I,, 2)) gets weighed by Di, + Li, in the kernel expression which compensates for the negation effect described above. This enables us to define a family operator-valued kernels discussed next, which is induced by the graphical structure information.
Definition A.2 (Graph-induced Operator-valued Kernel for known G). A graph-induced operator- valued kernel is defined as
(K, (a (z, ( J. (2(s,))u(s)ds
(109)
where 22 is a scalar-valued kernel on R?, G is a graph associating the imput functions in (II,..., E X and kn is defined as
(1, G) "
for y > where L the Laplacian matrix and is the degree matrix of the graph G.
KC associates a pair x, X with output function y E y where G is the graph which incorporates the interaction of constituent input functions of and æ'. The addition of D to L in (108) preserves the positive semi-definiteness of the kernel 1 as ID is a diagonal matrix with positive entries. Using graph-indueed OVK for functional regression problem requires associating K with a function-valued reproducing kernel Hilbert space where the map from (102) resides. The existence of a bijection between the set of positive semi- definite (Mercer) operalor-valuud kernels and lunction-valued reproducing kernel Hilbert spaces has been established in (Kadri et al. 2016). A function-value reproducing kernel Hilbert space (RKHS) is defined as follows.
Definition A.3 (Function-valued RKHS) (Kadri et al. 2016 A Hilbert space H of functions from X to y is called a reproducing kernel Hilbert space if there is a positive semi-definite (()))-valud kernel K on 2 such that:
the function K (w, z)g belongs to H, Vw, X and Vg E v,,
for every F H. E X and g E V, (F, K(w, .gt' = (F(w).g)>
(reproducing property)
Property 1 in Definition provides association of OVK K with the space H which contains maps from X to y. The reproducing property in Definition A.3 helps to relate the inner product in H. to the inner product in y. Using Proposition A.1 and Definition A.3 the positive semi-definiteness of KG constructed using 119p ensures that there exists a unique RKHS Hga corresponding to KG (Theorem (Kadri et al. 2016)). This enables us to formulate a learning problem in Hxo as follows:
arg min F
Σ 11 F(x(") + XII Kgo
(110)
FEH g
where Hga is the function-valued RKHS induced by the graph-induced operator-valued kernel KG and || Ila denotes the norm in Hga. In order to solve the optimization problem, we utilize the reproducing property of opcrator-valued kernel (Definition A.3) given by
(F, (F,K((z, (()..)))H = (F(x), Myy, V X
(111)
The minimization problem in 110 is not tractable using a search based procedure over Hga hence the reproducing property of operator-valued kernel K in (111) can be leveraged to simplify the problem and characterize the solution of (110) using elements of the output space V. We now provide a representer theorem for the minimization problem [100 in the cnaction-valeed RKHS Hxo corresponding the operator- valued kernel KG
40

---

Published in Transactions on Machine Learning Research (03/2024)
Theorem A.2 (Representer thcorem). Let KG be an operator-valued kernel and Hgo be its corre- sponding function-valued reproducing kernel Hilbert space. The solution Fx E Hg of the regularized optimization problem: Fx arg min rin Di=1 Ily - |I + + where À >> O, Hga, has the following form
FA() Σ K (x(0 where u4 E..
(112)
Proof. Please find the proof in Appendix
A.4
Using the representer theorem with reproducing property of operator-valuet kernel, we provide below (Ap- pendix A.8 the linear system of operators to determine u4 for i E [n]:
(K AT)u=
(113)
where K is a block operator matrix given by Kig- (2(11), ,,)()) 1, "........ y T( A simple inversion of K + Al may not be straightforward to obtain in (113] for an arbitrary choice of OVK KC_ Saha & Palaniappan (2020) proposed an iterative operator minimum residual (OpMINRES) algorithm which adapts a Krylov subspace minimal residual (MINRES) algorithm to solve operator-based linear system of the form (113). We delve deeper into the details of OpMINEES Section 5.1.1 With the learned u obtained by solving 1133, for any sample X, the prediction is given by
[ui, u2..... Unn] and
(A Σ K (x((), ()us, where u, E..
(114)
In [14), functions u, E y for e [n], can be considered as basis functions for the space y and opera- tors k (x(), $) for i E [n], correspond to operator-valued coefficients of the basis functions. The term KG (z(1) 3)4, amounts to the total contribution of sample (0()) in determining the prediction for a.
A.2 Mathematical Derivations
We cover derivations which can transform the objective function where the optimization takes place over the output space y instead of the RKHS HK induced by the OVK K. The following derivation has been referred in Section 5.1 obtain 5 from where we simplify the expression J(F, D) to obtain J(u, L, D).
min J(F, L. D)
1 F(x +1|FFIRR + PP
Σ
200) Lx + DD
(115)
FLL.
1=1
1=1
+1 +x(5
min Ju, L, D) D
Σ
(i) Σ
k(x(it) (,b00)x)0))) 2:10) Ju,
Σ
K k(x((t) ,.)ui; Σ
(xxx))).))
K k(x(()) ,))g
(116)
j=l
1=1
Hx
(1) (1) + PDDlDD
+ PT.
i=1
2
n
n
n + Σ
K k(x(t) , )
(K(((()2()))a (0))), (1)))
(117)
j=1
n
(() La La(
+ PL
The expression 116) is obtained from 115 by using the representer theorem and the reprodueibility property
of K utilized to obtain [17
Similarly, we obtain the objective function from reproducibility property of K given as follows:
29 in Section 5.1.5 using representer theorem and the
41

---

Published in Transactions on Machine Learning Research (03/2024)
J(Ft, F F L. =
Σ 1/
( F² (x(x)) + Al1
Pt Σ 21
(t)
Lx(²) + P
J(u², u
u², L)D=
n
n
K (x) ((
+ Σ (x x00) K' (u)b)
(118)
91
1=1
(1)
(1) Labk
+ DDD1D11
Pk
11
y1
(1)
+ A
(K'(x xx uffe
(119)
j=1
i==1
y
Lark (f)
Pk
A.3 Positive cemi-definiteness of OVK
In this section, we cover the proof of Proposition A. in Section A.1 which helps in building a graph-induced OVK. The major contribution based on showing that the proposed cealar-valued kernel in graph-inducce OVK is a valid positive semi-definite kernel on X' x X. We recall Proposition A.I below.
Proposition A.3. For underlying graph G FV, with [V] p. functional variables x
(z1, (21, Tp) X(== (L((O, 1)))) and functional response variable y E y(= L3 IJ)), consider operator-valuct kernel K X x X + L()) defined as
(K(x, (t) =1( L. ka(s, ()s(s))s
La', y > 0 and lg is positive semi-definite scalar-value kernel R x R. Then where (1)zz'';G) yo To'
K is positive semi-definite.
Proof. In order to prove the positive semi-definiteness of K, it is sufficient to prove the positive semi- definitencss k based on the construction followed in (Kadri et al., 2016). We focus on the term x Lx! in K1. Let fa x² x', C X be a finite set of points. Consider any vector a e Ie and K be a I I kernel matrix given by K [k (a", : G)
Now, we recall that the space L (20 1)) has the following inner product and norm:
(f.g) S'' f(t)g(t)dt, f.g e L (10, 1)),
1/2 |1/I| = (S. m(s)))
We define (..)pp X X as
(x, w) (2), wi) + (122 W2) + (x wp))
(120)
L x. x,(()
(121)
42

---

Published in Transactions on Machine Learning Research (03/2024)
.......,,.p wp) E X. We can show that (1--)p is an inner product where x (#1, ;g.....;pp) Ip) X, (W1, u2 ................................ X' over the field IR.
The symmetry of (.--)p follows from the definition in equation 121 as:
(x, (r,w), = (w, -)pp
Linearity:
(ax + bw, z)p = (ar) + bwi, 21) + (aa2 + buz, 22) + ... + (axp + bw zp)
(azi(t) + (b))(t))=(tdtt
=
a (t)t) - Σ L' (t)d
= aa, 2)p + blw, 2)p
Positive semi-definiteness: For any non-zero a E X,,
x, = (1) + (12, + ... (Kip Tp)
p
Σ
(t
c 2 >
The norm induced by (p on X is given by
| = v (I, x)p
Σ / (t)
1/2
On considering ,',x' X, L RPxp, the quantity x² Lx can be defined as
L1.1
L1a2
Lip
L21
L22
L2æ
x. Lxd
(x)
x
x/p)
:
Lp11
Lp2
Lp
Lin + Lng20h + + Lip
Lz + L2202
+... + L2p
= [xx]
x
Lp,1 + Lyg20g t... L 1p.
(of Li
+ Li Li t... + LIn
(122)
+ (wgz 12 + L2 + .... L2p
+... + (a)) 1p + Lp22d .... Ipp.ptp)))
(x Lx p
(123)
Note that from equations 122 and 123 Lad E X. Now based on the positive semi-defiiiteesss we decompose I. V AV. where is orthogonal matrix and A is the diagonal matrix containing the
43

---

Published in Transactions on Machine Learning Research (03/2024)
non-negative eigenvalues.
x Lx (x', Ledhr = (at, VVAV2
=x" T VT
(124)
Consider A= VAV,
Lxd x² V VVVVV AV
x² A Axd
= (An', Arr) )p
(125)
T Note that x² Lxr (Ax', Ax o(x))) (say) which is characterization of kernels. For finite E N, let I E Rmxx be the Gram (kernel) matrix induced by using (Ax, Aw) kernel. Let B E R" then we have:
8'g3
3
(: ())(()))))()))))
Σ (,0(x)) ) Σ 230(x0)
==1
2
m
Σ 3,0(2))
This illustrates that x² Lad is positive semi-definite and defines scalar-valued kernel. Now, using the properties of scalar-valued kernel, yz Læ', with & 0 is valid positive semi-definite kernel. Thus the kernel given by
(1(2z'' yx T Lo', Vx, x' X, 0.
is a valid positive semi-definite scalar kernel on X' x X. Therefore, by the construction of OVK used in Kadri et al.] 2016),
()),)))))(((>)))>)))))))) J' (e(s,t)
(126)
defines vaerador-valued kernel on X X.
44

---

Published in Transactions on Machine Learning Research (03/2024)
Now, exponential of scalar-valued kernel provides another valid scalar-valued kernel et al. 2004), consider the following normalized version:
(Shawe- Taylor
exp(1x Lx')
T Lo - Lx 2x' Lx')
exp
7at
exp(xxx Lx)) exp(1x² Lx²)
4 La TL
x "L'' 2x Lxe')
eex
2
(1A + 11 - (AAx, Ax
exp
2
(Il Ar (1:)
exp
((A(s x'), A(x xz))pp)
exp
((A(I x'), d1))p))
= exp
124 (x x') L(x 2')
exp
(127)
As exponential of a scalar-valued kernel and normalization preserves the validity of a scalar-valued kernel, clain that the kernel in 127] defines a valid scalar-valued kernel. This illustrates that e=>(===") M(z=x') is a valid positive semi-definite scalar-valued kernel on X' x X' for y > 0 and an OVK with ('(x,';;)) = e )==-==) M(z=x)) Vx, x in (26) provides valid graph-induced OVK.
A.4 Proof of Representer theorem
We provide a proof for the Representer theorem (Theorem A.2 stated in Section A.1 In the proof use the Gateaux derivative in an associated function-valued reproducing kernel Hilbert space for an operator-valuee veauue kernel. We recall the theorem statement first and then provide proof.
Theorem A.4 (Representer theorem). Let KG be an operator-valued kernel and Hg be its corre- sponding function-valued reproducing kernel Hilbert space. The solution FA E HKo of the regularized optimization problem:
F
arg min FEH g
11 F(( + XII M
(128)
where À > 0, F E Hxa, has the following form
n
Fx() Σ K (2()))))) where us e y.
(129)
Proof. We use the Gateaux derivative to obtain the condition for stationary point of the functional Jx(... given by
JA(F) = Σ 10 (() + A||Fl YF E HKg.
In order to find the critical points in Hgo, we use Gateaux derivative Dg of Jx with respect to F in the direction H, which is defined by
JA(F + +TH Jx(F)
lim T-0
Let F be the operator in Hga such that
F = arg min Jx(P) = DFJ,(F, AH E Hgg.
FEH kG
45

---

Published in Transactions on Machine Learning Research (03/2024)
JA can be written
" 1 G((F) Jx(F) -
and as D) = (D))) YF,H E HgG, we obtain the following.
noitemsep L(F)= = =1F = HHo
Therefore we have
F (F, (H,F = =2( Hy
lim
DoL(F) =
noitemssep (F) = (1y((0) )1 Then we have
( F(x(1)) T -H (1( -10 - )( 2(y H(x()),H(xx)) H(x())))
lim
(130)
T-0
7
(x ,,)(0))))))))))))))))))() =(xx(1)),
H HHk
(131)
= (x( (,)s,, H) HiHKa' DgG.(F) = (z(0),
(132)
We obtain equation
131
from equation 130
using the reproducibility property. In 131 We use Us
g()) - (()(())) to get (132 Using 1, 2, and JA (P) = O, we obtain, F()) = Ei= K ( (s(0),.))ss .uu- The
constant 1 can be absorbed in functions u,'s, such that F()) Ei (x((0, .)ui
We provide a proof for the exlended represeneter theorem (Theorem 5.1 based on the arguments used in the earlier proof. We recall the theorem and then provide a proof.
Theorem A.5 (Extended representer theorem). Let K be an peeratorvvalued kernel defined in 26 and HK- H3 x H& X ... x Hi be its corresponding function-valued reproducing kernel Hilbert space based on kernels k1, k2, kg. The solution Fx E H. of the regularized optimization problem.
F
arg min
l1v1 (0) F' (x(x + XI1
F= F2 F2 PulT TEHN 1=1
where X= F=
FF |F|,F F2
F E HK = -Hk x H2 x ... x Hix has the following form
Σ K (2((()),
FxO)=
where ut uz .,,,..,, ug E y
(133)
D Kd (x(1 Jug
Proof. We use a similar argument as in case of the representer theorem proof. The Gateaux derivative is used to obtain the condition for stationary points which minimize Jx(F) written sum of J (F)), for E [s), given by
(A(F) = Σ J (F
1=1
|M
(x
VF E HK. A1
1=1
46

---

Published in Transactions on Machine Learning Research (03/2024)
In order to find the critical points in HK Hkk x Hz x... Hk, Gateaux derivative Dy of J with respect to Fl in the direction H E Hk, which is defined by
[AFF' TH) (FF
(F H)
lim T-0
T
Let Fl be the operator in Hx such that
F
arg min 11(1") = (F)) AH E Hxx 1 E [s].
FE
Now, JJ can be written as
J((FL) = > (((F)) xXL(FF')
and Do H) (D&J Ma VF, Hkx [s], obtain the following.
noitemsep L'(F") = |,221122,, = (F), mx Therefore we have
(F' + TH, T HHH, (F', F')H) =2(F', , H)
lim 7-0
(FL) = =2F"
noitemssp (F = 11b/ - F (x)
Then we have
1w (4) F(x(1) - -H( H(x( 11 F(x
lim -
-((1(" - (x (x()))) (134)
= =-2(K' (x (x..). ..) (0)
F(x( H Hy
(135)
= 2(K (x (.)bt Hy
(136)
(FG) = -2K' (x (x(()).))u).
We obtain equation 135
using the reproducibility property. In 135 we use uf (0) (x( get (36). Using 1, 2, and ( O, we obtain, F'(.) 1
from equation 134
x - K (x(1) .uf.. The constant 1 can be absorbed in functions uf's, such that Fi(.) = EE_ (x((()), E [s]. Therefore, we obtain the following:
P(()
Σ (2(x()),
FA()=
where ui, u?,...,uu E y
(x()
Σn (x(
A.5 Properties of A, B, H, and M matrices
This section deals with the rucston and properties of matrices A, B, C, H.C and M which have been used the framework.
Determining A:
A is matrix which is constructed to represent the constraint L1 A vech( (L) 0. For given vech
47

---

Published in Transactions on Machine Learning Research (03/2024)
can obtain the condition L1 0 with Av)
0 based the following construction:
p
0 0p-1
0p-2
02
01
cp-1
0p-2
02
01
p
p
p-1
cp-2
02
01
Lep
p-1
p-2
o2
61]
where 02 [0,0, o,.....J Rl*k denoles a row vector containing zeros, 6x = [1, I,..,, 1] RI denotes a row vector containing ones, of = and zeros elsewhere, resulting in A R piaj
0] Rxl denotes a row vector with 1 the i-th position
Determining B:
B is matrix which is constructed to represent the constraint T4,5 S 0, + as B vech(I.) S. For a given vech(L), we reformulate the condition Lig S 0, vi # j as Bvech(L) I 0. This can be achieved with the following construction:
0
0p-2
0g
02
01
B
0
Pp-1
0p-2
0g
02
01
P
0
0p-2
03
02
01
p
0p
0p-2
03
02
0,
p-1
0p-2
0g
02
Op
0
0p-1
0p-2
02
0:
Op
Pp-1
0p-2
02
01
O,
0p-1
0p-2
03
0,
Note that B E R pin-11, x pic+l)
Determining C:
In section 5.1.3 C a matrix which used deal with the constraint D& 2 0, Vi [p]. We construct a matrix C Bpx p(tt)) which consists of 0's and I's satisfying Cvech(D) Diag(D). For given vech(L),
we formulate the matrix C E Rpx (( using O's and 1's as follows:
C
f-
C2:
C
f-
Cs:
Cn
where the row C₁ E 11 pl++1) and C2 contains a in the
[1(++11) 2
-th position and zeros elsewhere.
Determining H:
In section 5.1.4 we require a matrix H E R a vector having the same structure as vech(L) with 0's corresponding to diagonal entries of L and the same off-diagonal entries as in L. For given vech(T.), formulate the matrix H RR"
pintil x p(nt
comprising 0's and I's such that Hvech(T) produces
pini1) plats)
using 0's and
48

---

Published in Transactions on Machine Learning Research (03/2024)
I's as follows:
H1:
H2.
H3:
H
H plnne)
where the rows H₃ E I 1x 2ir and H3 contains a 0 in the [((it1) ) -th position and I's elsewhere.
Determining
p(p+))) In section 5.1.4. we consider vector I 2 consisting of 0's and 1's, such that c vech(L) = trace( L).
p(++1)
The vector c E is defined for obtaining the diagonal entries of D from vech(D) using O's and I's such that
vech(D) = d1,1 + 22,2 + ... + dp
where is given follows:
c= [e1, . 1p
where c pip
such that O2 1x Rei)) has all 0's with (z(141) 2
-th element.
Determining M:
M is matrix which is constructed to transform vech(L) to vec(L) using Mvech(L) vec(L). Let the Laplacian of the graph of nodes be denoted by which is symmetric,
7,11
1
1,11
1.
l2.1
22,2
13.2
4.
L. =
13,1
13,2
1a.3
1p.3
L0.1
4.22
4.33
Lp.p.
Now, vec(L) [1,,1.... 1...,,,,,,,,,,,,,1,11,, 1... 14,2, ................................ 4p, ................................ mnppl obtained by stacking the columns and voch([.) = [4,1,.... 1p.11 1, 12..2222... 12.,....................... 1n. la.,,.... ................... 1pp
which is obtained by eliminating the ruper-diagone elements and then stacking them up. As illustrated, vec(L) E R and VLC E 1P((+1)/2 We can find matrix M which satisfies
vec(L) Mvech(L).
Hence observe that M E RD²x par 1) 2 Therefore,
M
Σ (v) 2
where Ui is vector of order pppp + 1) having the value in the (j - +in++ii }0( - 1)-th position and 0 elsewhere and Th is p x matrix with 1 in positions (i.j) and (j. i), and 0 elsewhere.
The following relations are used in order to write the expression of objective function in terms of vec(L).
(z(0) -000)x011 -200) ()(( - 2(0) vec((x (z - ,0)) J vec([ + D),
vec((x(1) - 2 (z)) ا(0) T (vee(L) + vec(D)).
x(1 (1) vec(z(()) ) vec(L),
||||| vec(D) vee D).
49

---

Published in Transactions on Machine Learning Research (03/2024)
A.6 Derivation of Gradients
In this section, we cover the derivation of V V) and V V) which are required in Algorithm 2 We use 103) and 108) in the following expression to find the gradients. Recall (t(u))t) = So e eopolls-t (uss ds, Yop > s,s,t E R in the following derivations.
J (u, L)
Σ
K(x()) ,(
A
(K(x 1 ,z00)), undy
T La + pDl1D1?
+ PL
Σ
Σ
k1 (x: ,00; (
+ Σ
(Ki (z((0) ;:1) GG)k2 ug)y
1
i=jj=1
+ P1 Σ
x (1)
(o + PD D12
1=1
2
"
Σ
((0)
(( -1)(6))0001) (0) (1+ kog()))
1
(((()) (1++))00)) Tog( ug)y PL Σ x(()) La!
DD
We consider the following variables for simplifying the computations:
Raj = vec((z - (x - x00) )T
(137)
R. ve 1) TTM.
Therefore,
(1)
Σ
R (vec((() 12 (u)
e
i=1
1=1
+ A
{e Rry (o un)y + PL.
R.vech(L) + DD) Povech(())))))))) T M Mvech(D)
1==1
(R (oo k2(w))
i=1
1=1
Rechh(L + PDvech(D) MT Mvech(D) y Riy Ruy(eehh())+++ec0)))661))))))(.) + PL
+
e
Σ
1 y(0)
-
>
e - Riy (vv(()((()))) (,0,,k((u)))
1=1
n
Σ
e (oae) (kz(w;), (ka(w;))ka((un))) k2(un))
+ Σ
(Ryy(vec((()+vveee()) (Tz((s)) ujyy JJ=1
+
JA=1
+ PL
R,vech(L) + T M Mvvch(D)).
50

---

Published in Transactions on Machine Learning Research (03/2024)
The expression above for J can be used to determine the gradient with respect to vech(L) and vech(D). The gradient of J with respect to vech(T.) for fixed u and D is given as follows:
V voch(()) 24
Σ
Ryje Riye ( (a((s)) y
i-j=1
Σ
(Ris + RRtt) RRa (k2( (ux)))
k.j.kml
xy
e (B + PL R
Similarly, for a fixed u and vech([) the gradient of J with respect to vech(D) can be written as
V DechhD))J=2y = 2y Σ RTJc-BRB(vec((L-eeeobb)) (2(s))),
i==1
(Rij + Rax) (Rxe://iixx//cc/h))))))owo (ka(u,)) (gguw))
7
i,,k=1
12
Raje y RBs (w us)y 2DDD Mvech(D).
Ay
1,j=1
For the experiments on NBA data, the approach in Section 5.1.5 with 2 and 2. The inputs
x = (a (3) x2 and out out puts y = (vi 1/22 (0) E y22 with (25 and (26). for E [m]] We consider the
following variables for simplifying the computations:
R voc((z 21 (2 - =(0) T MMM
R² = vec((z - 22 (2)
(1) (1) - -x0)) MMM
(1) (6) T
R vec(2]
TMM
11
R vec(z (1) (1)
122 TM..
51

---

Published in Transactions on Machine Learning Research (03/2024)
J(u L. D) =
V1
(1)
k(x x( x(xx0)x00))
K
+
Σ
1/2
(8)
Σ
k(x x y0
1=1
i=
j=1
+ A
[K(x(1) x x(00 u3ソy
(K (K(x!)) (0) x uu? ,5)0
1==1
+ P1
La
1
(3)
+ p2
22
Lag (
+ p1l
i=1
91
ki
(x 1 x 1
+
1/2
Σ
1=1
+
Σ
(x
; ,)
(x)
x00) (G)
==1,/=1
==1,1=1
+ P1
Lx
+ P2
Σ
Lx + D1l
iml
n
(==)) (L+ ((0-))))=)))))-------)---+--)))" Rg (u))
(1)
91
==1
n
( R2 kz(
+
Σ
1/2
j=l
(44-=11) ())) (+f (w))) uftn
A Σ
1/=1
( 7 (2/ (L+D) -- 22)) (1 ( - 2(3)) af)y
+ X
1-=1
+
La
+ P
222
La + p
1=1
The gradient of J with respect to vCch(L) for fixed u', u² and D is given by
V vooc((E)J=2 =2 Σ Ry + 7222?3) T RR, ((1P9.s(et)), bd(())) +
(1S, ,)
i,f=1
(n + 12 + RR + (2ll(x) Te (n (o tra + R/y tre (ooe))))))
Σ
(m Ryj + 722 71 R2xx R2y TT e-- (11 ni, + R Ri th Rl, the RE (ow
Σ
Ri + 12,) Te- (n (vecc())) (uf), (x)),
Σ
(m R! + R2,, (( (veck (83 u3) + P1
R
+ pz
R
1
52

---

Published in Transactions on Machine Learning Research (03/2024)
Similarly, for fixed u', u² and vech(L) the gradient of with respect to vech(D) can be written
n
((of) (u))), + ((
V vecc((D) = Σ
(n + 12122)) 1,=1
Σ
(n Riy + + R2g + 7 Rix + 72 Rix) e- (1s Ri tra Ri ti Bh toe (vocc (k)( ( (g(())))
W
(m Mig + 72 + R2 + 72 Rn +ra +m ut + the (oodd)))oo))) (
(,
Σ
Rij + )2)R);; T 1- 1 (wcck (x,)), ufiyy
(n + [o
(wve) (kg(u)) ug)y + 2pD Mvech(D).
A.7
OpMINRES Algorithm
A.7.1
OpLanczos Step
OpLanczos in OpMINRES is used to trigiagonalize the operator matrix P.
The vectors obtained from
OpLanczos form an orthonormal set. Using the OpLanczosStep Algorithm 5
we can obtain,
a1
32
0
B2
02
83
PQR Qk where Tk
33
00
Bu-2
8k-1
0r--1
8%
3x
and Qx 1g, 02... Me], where 's are obtained using OpLanczosStep Algorithm. belonging to ym are orthonormal and the following equation is satisfied:
The columns of Qx
Q1
B2
0
02
B3
03
PQr Q where T
Bk-2
Bk-1
ak-1
3k
Gk
Osk
0
Bx+1
We intend to solve Au= -u=y by obtaining a solution in the Krylov space (2,) span(y, Py. Jy.P?..... pt ph-1p formation Quú, where O E "" R.*
y). -
For each iteration k, we obtain the following equations using the trans-
min lly Polly min Ily PQu0 min Ily - Qk+. 0x01T (P
DERR
DERR
min DERk
1Q+t1 - -Tx0)
(138)
(where 31 = ||y|| [10 T and 91 =y)
min [| T20l12.
(139)
PER4
53

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 4 OpMINRES(P,5) (P,b, mariter)
Input: P.b. maxiter
Output: 0,0, X
|61|
Qo = 0
Q1 = A1
do TO 31
Xo =
6 ) O
= 1
= 0
do d-1 = 00 =0
h =
while stopping criteria not satisfied do OpLanczosStep(? Q--1, Bx) + agg Bk+1 4k+1
/last left. orthogonalization middle two entries in last column of 1,+1
(2) 10 (0 + 10K
1) sk- sk-10k
(1) 1
2k
/last left. orthogonalization to produce first two entries of T T 2++2k++1k41
k+1 -
++1 -
// /currett left orthogonalization to zero out 3x+1 (2) SymOrtho(1)) (1) ,x++1) Ck. Sk: 7
//iihht-hand side, residual norms
c
dr = SHŌN-1
(36 (1)))22 + (011)) )2
k- oz-11
// //update solution
Uk ( d 6/ d2-
(1)
O2 = Uz-1
+ Txdd
X = |10x
k ++1
end while
1 = Sr. Φ = Φk. + = du d (6 X
The change norms I1-Ib>>
138 to I|-I|a obtained based on the following arguments. Let z [21, .,, 2x+1] T e g++1 and Qk+1 [q1, 2..... (.41) where qi E y", for i 2.2.... 1, then we
have
11041224111m
||2191 2292 + + #x+19h+1lln
(t)))t .... 2 / (t)dt
2 Sg
(t + 2)
(140)
of
... + kk+1 +
(141)
= ||=||2-
Equation 140 reduces to (141) the qi 's are orthonormal in y Solving for 02. arg minger= || T12 be done using QR decomposition (Choi 2006) which has been discussed in the next section. Now, the
54

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 5 OpLanczosStep(P, qk. -,-1, BR)
Input: A, 9k: 1,-1, 5k
Output: Olk: 1 1
qk+1 Aqq 3k9k-1 1
0gk (7x+1, 9k)y"
4 9k+11 0..
3x+1 11ūh+1ll 11120
gh+1 Bell 4k+11
Algorithm SymOrtho(e,b) b)
Input: a
Output: &,
then
$
r |a|
if = 0 then c=1
else
c c= c= sign(a)
end
else if 0 then
c
s sign(b)
r [b]
else if [6] > |a| then
T a/b
8 = sign (b) /1 72
c 8T
r b/s
else if |a| |b| then
b/a
C sa /V
8 CT
r = a/c
end
transformation from R& back to ym to obtain u is achieved using by the following:
u - Qu00 Qx
(arg min degt
1| Tx0012)
55

---

Published in Transactions on Machine Learning Research (03/2024)
A.7.2 QR Decomposition
In order to apply QR decomposition on symmetric Tk, we use Givens rotation Sy obtain a upper-triangular system.
(1)
(1)
71
3
7/
R2
1/
SET =
(2)
(1) Sc(3161) =
0
7h
7k
(2)
7k
where Sy = Sk,++1.. ... S2,3S12 and S4,41 are Givens rotations created to annihilate the 3 i in sub-diagonal of Tk. The S4,41' involved in the product to obtain Sy are given by,
1:-1
C
8
S11+1 =
8i
Cs
Ik-i
The matrices S4441 are obtained using the SymOrtho Algorithm 02 arg minger [|ßier Tx002 as
The sub-problem can be rewritten with
02 arg min DER*
tx +
Rx 1
where to =[T1, .....,,.. ,x] TT]Tan and
61
C1
8102
C1
tx Φ
S. ... S2.3
81
-BS .... S3,1
$1C2
B1
8182
0k-1
0x-2
81 ... 8k Ckk
81 5k
A shorthand way to represent the action of S4,6+1 can be described as
Cc
Sk
7k
R41
0
ΦR
%
(2)
(1)
Tk
8k
ckk
B6+1
ax+1
8c42
0
1e+1
k42
Φ
OpMINRES computes x in Kx(PP y) as an approximate solution to the problem Pu y:
[--1]
tx-1
a Qu02 QuR 44
D₁
= [Da-1
dx]
Th
=1 + Tuck.
The relation satisfied by d, given by,
de
Uk 8 d+ 1
(1) de dx-2)
(2)
k
These details have been incorporated in OpMINRES Algorithm A. The OpMINRES Algorithm based on approximating an infinileddimenssoonal problem in 150 by finite-dimensional problem in As OpMINRES is based on MINRES algorithm CChoi 2006). the convergence of OpMINRES follows from the convergence of MINRES. The case of singular systems with OpMINRES needs more investigation. In our experiments, the value of relative residual norms Φx has been used as the stopping criteria for OpMINRES.
A.7 is
139
56

---

Published in Transactions on Machine Learning Research (03/2024)
A.8 Derivation of Linear system of operators
Derivation of [K + AL)u y: We obtain sufficient condition for stationary points for the optimization
problem in Theorem A.2
Using the representer theorem, the minimization problem can be equivalently formulated as the following problem:
ŭ arg min
y/ Σ ((x(t)
, 10
k(x(0) ;.)us, Σ K(xO),, ,.)us) (Σ K(ar(t), Eラ= ((ob6),
(142)
uEy
Hgo
We have the following simplification of the term
in problem
HxQ
142
We have
K(x (.)u,, E ((xl)),)) n
Σ k(x ..),, Σ
K K(x() ..)u) ()us)
Σ
(143)
==1
Hx
i=1
j=1
Hxo
K K(x(aa .Juss K ((xlt)).)us
(144)
Hx
k(x(00) x ,x(()) us
(145)
Note that Eq. 143) and Eq. 144) follow from the property of bilinear forms and Eq.
145
follows from
the reproducing property of K. Thus we have the following simplified formulation:
ú arg min
y1
K(x!0) Dl
+
Σ
(K 20) ug)y.
Ø=1
To solve this problem, we first construct the objective function J2 (u) given by
(u
Σ V/ K (1) (1
Σ
(K(x!0 200)a, uyyy, y"
i=1j==
Letting (u( = En
Dizl
G((n) + AL(),, we can find the directional derivative of Jx Jx(U) with respect to the
direction v as (u).
Ga(u G(( GG,u)
D,Gi(u)= lim
7-10
=-2 V/i
Σ
K K(ii,az)u;
Σ K K(x!!1) (,(0)))))00)))
1=1
I(u + TU) T((u)
D+L(u)= lim
T-10
T
n = =>Σ Σ (00(())))0)))))) uus Uz) A
Σ (K(x))) ((( 2000)) yer, uz). i.
As K is Hermitian from the definition of operator-valued kernel, we obtain
{K (t) (k(z)(),))))),, Uz) (u,, K K(x yo;), Vi,j [n].
(146)
57

---

Published in Transactions on Machine Learning Research (03/2024)
Therefore,
DvL(u)= = A Σ
(( (2(1))))))))a (ll)) U/) + Σ
K (z(10xx01))) 2001)),,, 2g)
1.
n
X
Σ
Uui K(x 1()10,,(01)) + A
Σ
(K (xt((t) x(11) ye
(147)
1.
A
Σ
(ui, K(x(1), ,r(1))ug) +
Σ
(uj, (x(())s))
(148)
2A
(149)
Eq. 147 follows from Eq-
146 and in Eq.
147 we symmetry of (3.) to obtain Eq. 149 In order
to minimize JA (u), its directional derivative (u) 0, Vu E y
(v)a(u)= 0
=0
D,Gi(u)+ (DxL(u)= =0
K (xx
x (000)) Mu, Σ k(x!(t) ,001)13
22 Σ
(ui (xx 2(00)))))))))) = 0
j=1
K ((x(() 100) yay
K k(w!11) .0(1)10s
(Aus K(x((t) ((()))zg)) =0 Σ
V/+
i.j
k(x(1) 2200)00 )
()x()) 1111 - Mi. Σ
K (1) (,00),,00000
Σ
Xutss Σ
((=(0,200000
j=1
j=1
n Σ
K( ()) ,00)un - Dt + Auas
((x 2000))0)))))
0, Vv E
1=1
The above condition can be reduced to
KK Al)u y,
(150)
where K is a matrix of operators formed by using K.
A.9 Results for Generalization Bounds
We recall the lemma 6.2 and provide the proof next.
Lemma A.6. Let FF be a class of functions from X' to V. Consider m-tuple of samples from input space as (2) 2(2) (.),...,((mm) E x Then the following hold:
supper Il E F(x(1)) - EFIly] S 28 (F.)....
2. For every E IR, R mmy((eF) = (c)
3. For o: y + R, if ④ is Lipschitz function with Lipschitz constant L, then Lm mmo(F S L.my(()).
..... xl)) E xm and another independent sample Proof. For part 1, we start with denoting S = (x(1) (?),...... as S = (I(1), z(2) x(m)) E x we have
Esnyy [F(x]] = Bz-az
P(Z
(151)
58

---

Published in Transactions on Machine Learning Research (03/2024)
We note that the Rademacher random variables (E1, Eg,...,Em uniformly distributed over {+1, -1] and every possible value they take has an equal probability of 1/2m. Without, loss of generality, we can always
permute $2, to obtain Ep, = Ep. = 1,8 -1, -,,... E.. = -1, where 0 - k S m and (Pr...., Pm is a permutation of [m]. Therefore,
1 Σ Es
(F(E F(E
Es
sup PEF m
k
=Egwuy
E B
sup
Σ F(x(()) F(x(1))
+
Σ =
(F - F(a!1)
FEF
i=1
m
Σ (F(z()) - F(z())) )
=Es~pg
sup FEF m
(152)
The expressions above hold as a0() and z(() are independent and symmetric. We obtain the following based the arguments made above.
m F (1)
E Bawwwxx F(x!0)
sup PEF
m
i=1
sup FEF
1 (1)
S
1
((
(153)
m
1=1
1 m
=ES~EP
sup
3 m
Σ ((x -F(x(())
FEF
y.
Esnux
sup FEF
F(x(0) - -F(
(154)
1=1
=Bg~pp
E Esnux
E
sup FEF m
Σ E: (F(x()) F(
(155)
y
<ESTEE
sup FEF m
Σ e, (()(
+ ES-H
E
sup FEF
Σ F.
(156)
=2 2.
Equation 153) follows from 151 Jensen's inequality is used to obtain 154 and 155 follows from 152
by the fact that using Rademacher variables does not change the value of the expression in 22 (see proof of Theorem 4.1 in (Lao 2020 The inequality (156) uses the fact that e; and -e; follow the same Rademacher distribution and triangle inequality for norm - with supremum.
For part 2,
RmFy(cF) = E
sup
Σ (x i=1
FEF
1 m
= |c[E
sup
(2)(
PEF
m
|c| m. (F).
59

---

Published in Transactions on Machine Learning Research (03/2024)
For part consider m-tuple of samples from imput space d' as (x(1), xx3) ..... (=())...,,,)))) xm and Rademacher
random variables e for i E [m]. We assume Φ : y IR and @b is a Lipschitz function with Lipschitz constant
L. Then
Fm =E
sup FEF
ei ()(()))
um (F) + em (c) I]]
=B, 1
Belen
Bs
sup
(157)
FEF
where um (F) = E.T e, (x(1).
From the definition of the supremum, for any emh > (note that is not exponent in this notation).
there exists PT", Fr E F such that
Um (P)) + (m FT (xr) 2 (1-c"))
sup um (F) + &m (0 (x)(m))
(158)
FEF
Um (PTT) Em 12" ) (m( 2 (1 mm)
sup um Em (0 (x)(m)) PEF
(159)
otherwise it leads to a contradiction to the supremum assumption.
Therefore,
(1 Ee,...
sup (F) em(óo (m))(())) .EeF
1
(1 )
sup um FEF
um((F (F) + (Ø (z(()) sup um (F) - (Ø F.) (2(()))
(160)
2
FEF
Um (PTT) (m PTT)) (x(()) + (P em mn(c (x (z))
(161)
2 Um (Pm)) ) + um ( + 5m (10 Pir (z((m)) - ( Fig ) (srlm))
(162)
1 S sup um (F) + 2 Em ( (Tm) (0 F (attml) )} FEF
(163)
Equation 160
is obtained by using the definition of Rademacher random variable Em- The incquality 161
is obtained using inequalities for FT and F in (158) and 1159. respectively. Inequality (163) is obtained
by introducing supremum in the terms um (FTT)) wc claim
um (FTT) As the inequality (163) holds for any et 0,
sup Um (F) + Em( (aaam)))
< sup um (F)(F) + cm ((0 (a:))) (0 F (ofmm))) (164)
E
FEF
FeF
Using 164 in 157
we obtain
am F) = 10
E
Eerem
Erm
sup um (F) + sm (m))
FEF
E E,00~
E Eerem
sup Um (F) +
Em (10 (2m - (o F (o)
(165)
LEF
2
E Ey0~E
1
Ee Eey(Em-iiim)
Bem
sup umm1 + Em- ( (c((m-1))
FEF
Cm ((0 (m)())
(Ø ( (arl)
(166)
60

---

Published in Transactions on Machine Learning Research (03/2024)
where um--1 SuP Ei= ((FoF))xx)) Now, for any cm-1 a similar approach is followed to obtain FTn-1 F2m-1 E F such that
Um (FTT))) ) + Em (00 Pr -1 (z. 2 (1 (1-6" (1-Em-1)
sup um (F) + 6m-i o F (x.(m
(167)
LFEF
Um 1 Cm (00 P (x((-1)) 2 (1-6m-)
sup Um 4m (F)
1 a F) F)
(168)
LPEF
Using
167
and
168
similar arguments made earlier help us to claim
Eg m-
sup um (FF) + Em- Em-1 F)(((-11) FEF
1 $ sup Um 1 (F) + 2 Em- Fim (((m)))((((m1))))) (0 F2n ( (x)(mm11)1 FEF
(169)
Inequality 169 with 166
provides the following
1
8 ( o F) s E3 1
Ee Beh(em-affm--omm
mmm-2
E
sup um-2 + em-2 (m FEF
m
Σ
&e ((doFi)(o))) (00 (x))))))))
(170)
where 4mm22 =SIPFEF E c: ())) We iterate till the last step where
am o F) < Ey By
1
Ee,
sup e (cb ((c(())) Feef
((0oFF)(z)) - (o (z)
(171)
For any cl 0, there exists Fl. F E F such that
(b o FT) 2 (1 (1)
sup Ei (1)
(172)
FET
(1 F 2 (1 - e
sup
-0 (z
(173)
FEF
Using 172
and 173
we obtain
Eg
sup FEF
( P)(
< 2
1
11 ((6 ((o - 100 (3)(
(174)
Next, we simplify
171
using
174
E: (1)( (0o - (((
(0o (2) 10 (()(1(
(175)
m
m
Σ
Ee (z) ( Σ
e F (x())))
(176)
17
Σ
E4 (z)
Ee (1)()(0))
(177)
< LE sup FEF
Σ & (z)()
(178)
61

---

Published in Transactions on Machine Learning Research (03/2024)
Inequality 175
is obtained by using Fi, Vi m which are obtained based the procedure for Ff" and F The dofinition of Φ is utilized to establish 176 Inequality 177 is obtained by using Tipschitz conti-
muity of 4 and (178) follows from the definition of supremum and expectation with respect to Rademacher random variables. Hence using (178) with 174 and 171,, we obtain
F) S (F)
Next, recall Lemma 6.6 and provide its proof.
Lemma A.7. (=)] is bounded above as lollows:
[[ (
(mm.(KK)))
Proof.
E [[()=]] E sup FEPBx
(8(F) - (2(F)
(179)
m
2E sup FEOBR
Ly F(a((1))
(180)
m
(T((T) 8 m, (bBx)
(181)
(TL(()) (T)))i)mm)) (Bx)) (Bx)-
(182)
Equation 179 involves a supremum of pBx as | is bounded by p and inequality 180 is obtained
by using Lemma A.9 in Appendix A.9 Part of Lemma 6.2 used with Φ.(.) Ly ,.) which has a
Lipschitz constant L(r) in order obtain
181
182 follows from Part of Lemma 6.2 Now,
m
(mx)(Bx)
sup PEBx m
Σ e (()
1/2
1
F(x(1)), (((a()) F(((O))
E
sup
EGEY
(183)
FEBx
f-==1
1/27
sup rEBx m
Σ 8:81 f.j=1
F. K(x00) ((())
(184)
1/27
m Σ
< sup
sup sup-
F,
S;e, K ((x((t) ..)y)
(185)
KeR FEBx yEy m
f,j=1
Hx
1/2
1
m
< sup sup
sup
||1|
Σ
,.)
(186)
KeK FEBx: yEy m [F] Mg $1
i.j=1
HK
1/2
m Σ h-/=
<
sup sup Ket yey m
E,e, K(c,K((())) ..)
(187)
M.K.
1/27
m
< sup sup Ket yey vm
Σ K (x(())
(.)
(188)
Hx
62

---

Published in Transactions on Machine Learning Research (03/2024)
1/47
1
m e
m ((x0) .)..
E
sup sup KEK yEY vm
Σ
ej K((o) ,.y
(189)
j=1
HK
1/4
m
$ //1/
sup sup sup KEK DEd vm
Σ
K (cr(tt)
,2))1/
(190)
1
1/47
3//A
sup sup sup KEK yEy NEX
1
Σ e K (xx() .2)2
(191)
B1/1
(192)
The steps in deriving L mm.y(Bx) S (mmmyyKo)) use properties of norm, inner product and reproducing
property of OVKs which have been discussed in Lemma A.8 (Appendix A.9 Therefore,
[[O())] S (2m
We discuss the steps involved in deriving (Bx) S 31/1 (Zo) Lemma A.8.
next.
A Bm.y(Bk) s B111 (Km))(Ko))
(193)
Proof.
R (mx)(Bx) = E
sup
1
Σ
(()(1
FEBx
==1
1/2
E
sup
1
(z)(1))
m
mm F(x(1))
(194)
FEBx
m
1/27
1
F(x(()), F(oo0)))
E
sup FEBK
(195)
1,1=1
E
sup
EmEm
F, ((K (.)(()))))((())
(196)
FEBx
1,1=1
HK
1/27
E
sup
F. Σ
EE m K K(x(1) (z))),)))(((())
(197)
FEB m
Hx
1/2
m
E
sup sup
F.
e K K(x(1) (.)((())))))))))))
(198)
KEK. FEB2 m
Hx
1/2
<
E
sup sup sup Kek: FEB yey m
1
F,
Σ
E K (zx!)) ,.)y
(199)
Hx
63

---

Published in Transactions on Machine Learning Research (03/2024)
1/27
S sup sup sup
1
|FFllaic
Σ
m
c K
(x((),))
(200)
KEK FEBx yey m
sw=1
Hxx
1/27
1
sup sup sup
||
Σ
6iEm K
(201)
KeR FEBR: yEy m [IFI MK MK S1
Hk
1/2
m
S
sup sup KeK yEy m
Σ 1-j=1
E m K (xx()) ..)9)
(202)
HK
1/27
E sup sup KeK yEy m
m
(x((( :-)9
(203)
Hx
1/2
1
S E
sup sup KEK yEy
Σ
pm
E
k(x
5.)9
(204)
i=1
Hx
1/27
= sup sup KeK KeKyEJ V
Σ
&KK(> ..)y
(205)
Hx
1/17
sup sup KEl yEy ym
E (x ,.),
Em
K K(x (2)1)).)1 ,))
(206)
j=1
Hx
1/4
m
sup sup Kel yEy m
Σ fJ=1
mm (K (x(1), (,(0),)) ,.)y. (()30),)))30x
(207)
1/47
m
E
sup sup KeR yEy ym
Σ (J=1
m. (K(x (K(!!) (,0,,,,0)000) viy
(208)
1/47
E sup sup KeK yEy /m
E K(z K(x (2(0))))))) (1 1
//,)
(209)
1,=1
3
1/4
< E
sup sup Kek yE) vm
Σ 1-1=1
E K
(z
2200)21
11///2
(210)
$ </1//
sup sup KEK vm
Σ
E K (x(())
(211)
i-j=1
m
m
3//4g
sup sup KEN yey m
Σ
Em
E, (2(( 2201)1 )
(212)
1/4
< </8B/AB
sup sup KeKyEJ /
Σ 5ml
Σ
((x (.000)0)
(213)
64

---

Published in Transactions on Machine Learning Research (03/2024)
1/4
m
m
B///E
sup sup KeR yEy vm
Σ
E (x(())
(214)
1/47
< 8//$E
sup sup sup Kek yEy ZE v'm
1
Σ
Σ
Ee K (xx(11) 220)
(215)
1/4
BB//
sup sup sup KEK WEK yEy m7
1
Σ
K (x) x)y
(216)
= Ba/1 (Km))(Ka))
(217)
Reproducing property of OVK K is used obtain (96) and 208 Inequalities 200 and 210 are obtained by using the Cauchy-Schwarz incquality. 202 is obtained by using the definition of 1x with || Hx S 1. The rest of the steps follow from the properties of inner-produce and norm in Hx and V
]
Lemma A.9.
E sup -((F)-8(1) < 2E FEpBK
sup FEABR
1 m 1=1
e; Ey ((),
Proof.
1 m
E sup FEPBx
(8(F) (x(F) Be33m
sup FEPBI
B 1 (2(F)
(218)
m
E2-3"
sup FEABx
LVV. F(z))
Lly F(z((1))
(219)
t=1
sup FEABx
1
L F(x)) Ey -ly0) F(z(()))
(220)
t=1
Consider a function dependent on two random variables X, Y in a class of functions F. Then
f(X,Y) sup f(X,Y) JEF
Ey Y < By (sup f(X, Y)]
JEF
sup By Br(f(X,))) < Ey fEF
(sup S(X, Y)]
JEF
Ex sup By [f( Y) S Ex
Ey jsu f(X,))
(221)
feF
feF
Therefore, using the property established in [221 we obtain
1
E sup [6(F) (F') = =En333 FEnBx
sup FENBI
Ex' 3m
- F(I
(222)
t=1
< E EBr33m. Ey..3mm
sup FEPBI m 1=1
- ((2)) -
F(z(1)))
(223)
= E BB,5//3m._
sup
E
(1/,, - 2(y() F(2(01))
(224)
FEPBE
i=1
65

---

Published in Transactions on Machine Learning Research (03/2024)
1 m
E
3m
sup FEpBK
& L1/ F(x)))
m
+ sup FEPBR
-e:)
Lt) (8) F F(u())))
(225)
m
1
E3 3m
sup FEpBI
E
L F(r!))
m
1
+ 3
sup FEpbRc
E
(1)0
(226)
m
1=1
=2E
FEPBR m Σ E, (yy F(())))))
sup
(227)
224] follows from 223 by the fact that using Rademacher variables does not change the value of the
expression in [233 see proof of Theorem 4.1 in [iio 2020))- (225) follows from (224) as -6; has the same
distribution as E;. 227 is obtained from 226
88 2 =and= z' follow identical distribution.
A.10 Details of Experiments
In order to illustrate the effectiveness of the developed framework, we have used functional regression problem with an unknown graph structure in the input data for both synthetic and real datasets. The task of predicting output functions with the help of Laplacian matrix denoting the relationship between the set of p imput functions has been illustrated in the experiments. As practical data is always available discrete observations corresponding to functions, standard FDA techmiques can be used for the conversion of functional data into vector representation using basis functions, c.g. Fourier basis, B-spline basis, etc. Let X' = ([I2((a, d)) and y ([c, d]) be the input and output spaces, respectively. For our experiments, the error metric used is residual sum of squares error (RSSE) (Kadri et al. 2016) defined as RSSE = (y) (t) (dt,, where y(t) is the actual output function and g(²) is the predicted output function. RSSE is better suited to compare functional outputs. The integrals involved have been approximated by using numerical integration in our implementation. The quadratic programs involved in (23 and 15 are
solved by using CVXOPT (Andersen et al. 2023).
Experimental Setting: All methods were coded in Python 3.7. All experiments were run on a Linux box with 182 Gigabytes main memory and 28 CPU cores. As methods to solve the problem of functional regression problem simultaneously with learning L and/or D are not available, we use popular algorithms to first determine L. Then for the learned L, use our alternating minimization framework to learn D using projected gradient descent and u using OpMINRES. For the MCP-based L lcarning and D learning in the proposed alternating minimization framework, we use a decaying step-size in the projected gradient descent. The decaying step-size regime involves starting with an initial step-size (e.g. 10 and reducing it by a fixed factor (e.g. 2) after a set of iterations (e.g. 5) continuously till a final step-size (e.g. 10-9). Section 7 includes the details of the mothods OpMINRES-L-D and Sparse OpMINRES-L-D which we in this section.
KGL-OPMINRES-DD, Sparse Non-Pos-
A.10.1 Experiments with synthetic data
For synthetic experiments, three sets of experiments have been considered with input functions for graph structures having 3-nodes, 12-nodes and 25-nodes, respectively. Here, discuss the data generation for all three settings and results for 3-nodes and 25-nodes setting. For all the methods, a truncated trigonometric basis of [[0, 2r)) with 30 basis functions has been considered for encoding the functional data. The experiments were run for three settings where the data has been divided randomly into a training set, validation set and a test set. The following data splits have been considered: (80/20/20). (160/40/40) 40/40) and (320/80/ 80/800, representing the number of training camples/validattes samples/tes samples. The data generation is discussed below.
Data Generation:
66

---

Published in Transactions on Machine Learning Research (03/2024)
x(9)
X201
xjir]
yio
My Wm w//l
Figure 3: Samples from the 3-node based synthetic data.
For 3-node setting,
P
x1 = Σ Wi (os()
x2(
Σ
wi cos(azt) +
xx((1) b,
P
v(1) = Σ
wi sin()a!),,
where t [0, 2T), wa b E U[[11,]), a, U(00, 1]), E O") for i [P]. E 0.25).. The functions are sampled at 100 points and normalization has been done after introducing Gaussian noise with 0.02 standard deviation for both input and output functions. Figure includes some samples generated from the dataset. For 12-node selting.
(1)
w cos cos(a?)))
17((1 = bi + noise
P Σ 2=1
r2(()
/ cos(a;t)
rs(() = b2 + noises
ra(()=
Σ
wi cos(a
z9(() bg + noises
1T(t)=
wi cos(a?t)
1io(t) bb
st(()=
Σ
w cos(a?t)
T11 (f) = bb
I6(t)
Σ
2 cos(a?t)
(12(1) = bb
67

---

Published in Transactions on Machine Learning Research (03/2024)
P Σ 1=1
v(1)
( + w + sin((a) + +o)))),
where [0, 2x), w b1, b2, by E U(-1, 1]); by bs. bb at E U[0, 1]). E N(O,, for E = 1,2,3, k. 1.2,a ( 0.25J) and noise; E N(,, 0.25*), 1, 3, for 1-th partition of [0, 2n). The functions are sampled at 100 points and normalized after Gaussian noise with 0.02 standard deviation being introduced for both. Figure 4 includes some samples generated from the dataset. Note that results for 12 node case have boen discussed in the main paper.
xy(0)
xy(()
Xy(t)
Xy
xg(t)
Xy(t)
Xxo(0
X1y(0
X12(t)
yta
W
#
Figure 4: Samples from the 12-node based synthetic data.
For 25-node setting,
P
P Σ
(t) Σ
h cos(( (f
x2(()=
wa cos (
ra(t) Σ
wi cos(att)
Ix(() Σ
// cos(a
1=1
2t(() Σ wi cos cos(att)
To(() Σ
wi cos (a?t)
P
(t( Σ
wp cos (a?t)
1x(() Σ
wis cos (ast)
[t(())
Σ
w cos(a?t)
Iio(t)
Σ
f cos(a?
i=1
i=1
68

---

Published in Transactions on Machine Learning Research (03/2024)
(t) b1 noise1
112(t) b2 nnisss
(t) bs + noises
Z14(t) b4 nooSs44
(t) by + noises
Tio(t) C1
(t)(t) = C2
(is(() C3
(t) C4
(2) -5
(2) d1
T22 (1) = d2
(2) = d3
x24(1) = d4
x25(1) ds
y(t) Σ (w) w/ + uw + )
sin((a) af)))).
where [0, 2m), wb,b, ([[-1,1]),o E U(0, 1),,, E U((00-1]e E N(O, for i [P].ú E [5), 1,2, E ([0, 0.25J) and noise; E (0, 0.25",, [5] for (-th partition of [0, 2 functions are sampled 100 points and normalization has been done after introducing Gaussian noise with 0.02 standard deviation for both input and output functions. Figure includes some samples generated from the clttaset.
roth
Kolfi 20133 wyth
Kalfi 2neO 2010
zutfi anstit wndd xmiifi sualt) zndto Jostil souit xppit soslft xxsift
Figure 5: Samples from the 25-node based synthetic data.
The results for synthetic data is summarized in Tables 9 13 where Sparse OpMINRES---D attains comparable performance with learned sparse graphs illustrating important relationships driving the functional regression. Table shows that Sparse OpMINRES-L-D provides comparable results to other methods with respect to the mean RSSE on test. data for 3-ndes setting. Table 10 contains the D values learned for experiments with nodes which improves the performance functional regression task in a regularized manner. For 3-nodes setting, the data generation process involves similar information corresponding to node 1 and 2, whereas node 3 involves random constants. Sparse OpMINRES-L-D captures relationship which includes sparse relation between nodes 1, 2 and 3. iglasso-OMIINRES... and KGI-OPMINRES-I.D learn fully connected graphs in Table
Table showcases the mean RSSE results for the functional regression problem for 25 no-sodes experiment where Sparse OpMINRES-L-D produces comparable results on the test data. In 25-nodes setting, the data generation process involves varied information in nodes 1-10, whereas nodes 11-25 contain information which does not impact the generation of the output function y. The graphs obtained for Sparse OpMINRES-T.-D in
69

---

Published in Transactions on Machine Learning Research (03/2024)
Table 9: Mean RSSE results for 3-node synthetic data.
Mean RSSE
Train/Val/ Vas/TTstt samples
Methods
Train
Val
Test
Sparse OpMINNEE--L-D
18888184
0.117119
0.104051
80/20/20
DDlasO-OPMINREES-D
0.109485
0.124759
0.124163
KGL-OPMINRES-D
0.086952
0.124781
0.183851
Sparse Non-Pos OP.MNEESLLD
0.064445
0.158646
0.149415
Sparse OpMINRES--LDD
0.040655
0.211139
0.198398
160/40/40
iglasso-OPMINRESSDD
0.062094
0.183526
0.193644
KGL-OPMINRES
0.07809
0.181575
0.201469
Sparse Non-Pos-OPMMINRESLJJ
0.089997
0.19503
0.218885
Sparse OpMINRES-L-D
0.046926
0.153285
0.274924
320/80/80
fglasso- Daaaso-OOMMNRRESDDD
0.095652
0.145256
0.281665
KGI--OMMIRRES-DD
0.057804
0.145889
0.271459
Sparse Non-Pos-OOMIINRES-LL
0.087422
0.150039
0.274598
Table 10: D for 3-node synthetic data.
Train/
Val/
Sparse OPMINRES-I-D
fglasso-Ophe OOIINS--MMINRESSDD
KGI-OPMINRES-D
Test
samples
80/20/20
0,011319
0.036068
0.119428
1.001583
1.002949
1.000191
1.000672
1.002477
0.999940
160/40/44 40
1.104571
0.747521
1.229991
1.008645
1.007241
1.001036
1.010710
1.009007
1.000914
320/80/88 880
1.227095
0.761956
0.956403
1.019795
1.012624
1.001624
1.026910
1.019523
1,004683
Table 11: Mean RSSE results for 25-node synthetic data.
Mean RSSE
Voain//Vll/esttt samples
Methods
Train
Val
Test
Sparse OpMINRES-LLDD
0.754677
1.567458
1.822983
80/20/20
Milasso-OPMINRRES.AA
0.905085
1.527465
1. 1.605906
KGL-OPMINRESS-D
0.934007
1.478522
1.594960
Sparse Non-Pos- OPM-IRESLLM
0.922789
1.53816
1.564855
Sparse OpMINRES-LLD
0.662029
1.549598
1.215493
160/40/40
0.678837
1.602842
1.231550
KGL-OPMINRES--D
0.742796
1.571745
1.212629
Sparse Non-Pos- OPMINRES-L-D
0.600849
1.573893
1.215729
Sparse OPMINRES-LLDD
0.767516
1.436166
1.436166
320/80/80
iglasso-OOMIINRESS..
1.063051
1.385366
1.429937
KGL-OPMINRES--D
1.069962
1.356429
1.425034
Sparse Non-Pos-O OOMPPOS-OOMINNES-LLL
0.668318
1.418141
1.437544
Table show connections majorly between nodes 1-15. Though the input functions for nodes 11-15 contain noisy random constant values, this information seems to be associated with input functions for nodes 5-10. Sparse Non-PPos-OpMIINRES.T.. also discovers relations in the clusters of nodes 1-10 and 11-25 majorly.
70

---

Published in Transactions on Machine Learning Research (03/2024)
Table 12: Graphs corresponding learned for 3-node synthetic data.
Train/ Val/ Test samples
Sparse OPMINRES-L-D
fglasso- OpMINRES-D
KGL- OpMINRES-D
Sparse Non-Pos
OpMINRES-L-D
80/20/20
160/40/40
320/80/80
A.10.2 Experiments on weather data
Weather data is dynamic and inter-relationships between different parameters can be hard to predict. As our problem solves a functional regression problem based on a relationship between a set of input functions, we intend to showcase the effectiveness of the proposed algorithm by predicting average dew-point temperature (F) across 12 weather stations based on their respective air temperatures (F). We consider minute data of Wyoming ASOS data collected from IEM ASOS One Minute Data (Iowa Environmental Mesonet 2022). The data has been collected for interval of hours for both input. functions and output function from
71

---

Published in Transactions on Machine Learning Research (03/2024)
Table 13: Graphs corresponding to learned L. for 25-node synthetic data. [Best viewed color)
Train/
Val/ Test samples
Sparse
fglasso- OpMINRES-D
KGL- OpMINRES-D D
Sparse Non-Pas- OpMINRES-L-D
OPMINRES-L-D
80/20/20
160/40/40
bcak
320/80/80
January, 2022 to August, 2022. Data collected at minute interval for different 12 weather stations in Wyoming was pre-processed to create 2 hour interval data by disrogarding intervals where data was missing in any of the 12 stations. A total of 718 samples have been collected after removing missing data. The following 12 weather stations in Wyoming have been considered: Big Piney (1), Casper/Natrone Natrona Intl (2), Cheyenne/ WWrren AFB (3), Gillette (4), Laramic/ /Gen. Brces (5), Lander Hander/Hunt Hunt Field (6), Yellowstone (7), Riverton (8), Rawlins Municipal (9), Sheridan Co. Airport (10), Torrington Municipal Airport (11), Worland Municipal (12).
72

---

Published in Transactions on Machine Learning Research (03/2024)
Table 14: Mean RSSE results for small weather data,
Mean RSSE
Mrain/Val/Tee Test samples
Methods
Train
Val
Test
Sparse OPMINRES-L-D
0.004302
0.041949
0.092553
80/20/20
OPaaSE-DMMI KGI-OPMINRES-D
0.001716
0.059419
0.082662
0.002357
0.049899
0.097951
For all the methods, a truncated trigonometric basis of (1 1]) with 80 basis functions has been considered for encoding the functional data. We segregate the weather data experiments into small weather data experiments by considering 120 samples and full weather data experiments. The following random data splits have been considered: (80/20/20) and (472/123) 1///122//12, representing the mumber of training samples/ samples//vliidation /validation samples/ haapllesttes test samples in small weather data and full weather data settings, respectively. We discuss the results for the small weather data here. Note that results for full weather data related experimements are already presented in the main paper.
Initially, we use a small dataset with 120 samples drawn at random from the considered 8 months. Tables [4 15 showcase the performance of the algorithms for small weather data. Sparse OpMINRES--L performs the and KGL-OPMINRESS-I
best in terms of mean RSSE on the test data compared to L-D and KGL-OPMMIRES-LL learn dense fully connected graphs which do not provide much information regarding the impact of different weather stations on the relationship of respective air temperature to the average dew point temperature. The plots illustrate location based relation between the 12 weather stations considered in Wyoming. Sparse OpMINRES-I-D learns a sparse L where stations CYS(3) and TOR(1I, GCC(4) and WRL()2), LND(6) and RIW(S) along with P60(7) and RWL(9) are connected. CYS(3) (41.15564, 1004.81047) and TOR(11) (42.06472, 1104.15277 are 114.89 km aparl with elevation of 1871 m and 1282 m, respectively. GCC(4) (44.34892, -105.53936) and WRL(12) (43.96571, - 107.955083 are 197.54 km apart with an elevation of 1230 m and 1294 m, respectively. LND(6) (42.81524, -108.729944 and RIW(S) (43.06423, - -108. -108.45984) are 35.37 km apart with an elevation of 1694 m and 1688 m. P60(7) (44.54444, - -110,42111) and RWL(9) (41.8056, 1107.19994) are 401.40 km apart with an elevation of 2368 m and 2077 m. Tt can be observed that the connections in the learned graph structure have been established between stations with varying distances lying in close proximity elevation- wise (in 3 out of 4 cases) and latitude-wise.
D (Table 14) In Table 15 SatassoOOOMINNESS-LL
A.10.3 Experiments on NBA data
The movement of basketball and 21 playors involved on the court (x-y coordinates) in the Atlanta Hawks (ATL) vs Utah Jazz (UTA) match on November 15, 2015 has been considered this experiment. This data is available in the Github repo NBA Movement. Data (Seward, 2018 The data has been collected for different plays for both input functions of 21 players and output function denoting the position of the ball, which includes missing data corresponding to some players in different plays. The data corresponding to the following players were used: Kyle Korver [ATT., G] (1), Thabo Sefolosha [ATL, G-F) (2), Paul Millsap ATLL, F] (3), Al Horford [ATL, C-F] (4), Tiago Splitter [ATL, F-CJ (5), Derrick Favors [UTA, F-CJ (6), Gordon Hayward [UTA, F] (7), Trevor Booker [UTA, F) (8), Alec Burks [UTA, G| (9), Shelvin Mack [ATL, G] (10), Kent Bazemore [ATL, F-G] (11), Chris Johnson [UTA, F] (12), Justin Holiday [ATL, G] (13), Dennis Schroder [ATL,, G] (14), Jeff Withey [UTA, CJ (15), Mike Muscala [ATT., F-C] (16), Rudy Gobert [UTA, C) (17), Trey Burke [UTA, G] (18), Raul Neto [UTA, GJ (19), Rodney Hood [UTA, GJ (20), Joe Ingles [UTA, F] (21), where the team, position and number assigned for the experiments has been provided. As plays in basketball game are of different time duration,
use a truncated trigonometric basis of L 1)) with 80 basis functions to sample the functions at fixed 100 points on [0. 1]. A total of 351 samples have been collected based on removing missing data. A random data split of (233/59/50 59) representing the number of training
/validation samples samples has been considered. The problem requires solving a multi-dimensional functional regression problem which incompatible with fglasso and KGL algorithms, as both fglasso & KGL are based on single dimensional input functions. Hence, we compare our method with the algorithm OpMINRES-D where a fixed I is incorporated in our alternating minimization framework.
73

---

Published in Transactions on Machine Learning Research (03/2024)
Table 15: Graphs corresponding learned for small weather data. [Best viewed in color)
Train/
Val/ Test samples
Sparse OpMINRES- L-D
fglasso OpMINRES-D
KGL-OPMINRES-D
80/20/20
OpMINRES-D: A lixed I. considered corresponding a fully connected network of nodes. This decision was made as fglasso mostly learns a fully connected graph in earlier experiments. Thus, a fixed L (with no sparsity-inducing MCP) is used in the proposed alternating minimization regime for optimizing u (L+))((==) and ki) (s, = 1oppl11 (. (s, = e - where Ya, Tv (10-6, 10-5, 10-1, 10-3 10-2 10-1, 1, 10, 100) and Top. 7op e {10-5 6 1,10- 101110-..100 10 10-3, 10-10 1011,00211111 1,1001,11 1, 10, 100}.
and D. OPMINRES is used with k (x, x'; G) = (==xx===))
Sparse OPMINRES-L-D: We consider the graph-induced operator-valucd kernels using kn (1 x': G)
(x-x'') (L+ = (L=+)(==-z) and (s, e -opp----) (3(s --plle--tl where Nas Tv E {10-6, 10 10 10-3 10 10-1 1, 10, 100} and Top: Top E {10-6, 10- 10-4, 10-3, 3, 10-0.-200 10-1001,1000 1, 10. 100). Projected gradient descent is used minimization with respect to L, and D based on a decaying step-size. The sparsity aided by the MCP regularization considered in learning L.
Table 17: Mean RSSE results for NBA data.
Mean RSSE Val
Train/Val samples
Methods
Train
Test
233/59/59
Sparse OPMINRES--DD
0.025200
0.087748 0.191459
0.106344
OpMINRES-D
0.023261
0.265513
The results are illustrated Tables T6 17 where comparison method OpMINRES-D uses a fully connected
graph, however Sparse OpMINRES-LLD performs better with a sparse learned graph in terms of mean RSSE on the test data. The following major relations are obtained for the game based on graph structure corresponding to the learned in Table 16
Derrick Favors [UTA, F-C] Trevor Booker [UTA, F] (6 8)
Al Horford [ATL, C-F]
Gordon Hayward [UTA, F] (4 7)
Alec Burks [UTA, G] G Burke [UTA, G] (9 18)
74

---

Published in Transactions on Machine Learning Research (03/2024)
Table 16: Graph corresponding learned L. for NBA data, [Best. viewed in color)
Train/ Val/ Test samples
Sparse OpMINRES-LE L-D
8
10
11
12
233/59/59
21
13
20
14
15
18
16
-5
-2
-1
Log scale
Thabo Sefolosha [ATL, G-F] Kent Bazemore [ATL, F-G] (2 11)
Dennis Schroder [ATL, G] Rodney Hood [UTA, G| (14-20)
Tiago Splitter [ATL, F-C] Jeff Withey [UTAA, F-C] (5-15).
From the match report published in ESPN match recap and ESPN match scoreboard (ESPN 2015a b). it is clear that the relation Derrick Favors Trevor Booker (6 8) had been pivotal the win of Utah Jazz. The performance of Al Horford and Kent Bazemore for Atlanta Hawks was mentioned and captured by the relations (4 7) and (2 11). Though the partnership of Alec Burks Trey Burke (9 18) for Utah Jazz is not evident in the match reports, their ball carrying interactions may be the reason for being learned in L.
A.10.4 Hyperparameters for Experiments
In this section, list the hyperparameters used for Sparse OpMINRES-L-D for different experiments illustrated in this work.
Common hyperparameters: Areg = 0.5, Treg = 1 (MCP), maxiter = 1000, tol 10-3 (OpMINRES). The decaying step-size regime for projected gradient descent in L and D-based minimization involves starting with an initial step-size 10-4 and reducing by a fixed factor after set of 5 iterations continuously till a final step-size (or learning rate) 1
As our proposed approach Sparse OpMINRES-LA aggregates many components, we provide some ablation studies to illustrate effectiveness in the next section.
75

---

Published in Transactions on Machine Learning Research (03/2024)
Table 18: Hyperparameters used for experiments with Sparse OpMINRES-L-D on different data sets
Experiment
No. of Training Samples
Yop
A
PL
PD
Mitrace
80
10
10
10
10
100
2
3-node
160
10
10-4
10-2
10-3
10
2
320
10
10-4
10-2
10
10
2
80
10-5
10-6
10-2
1000
6
12-node
160
10
10-6
10-6
10
10
6
320
10
10-4
10
10
10-3
6
80
10-1
10-3
10
10-1
10
13
2o-e
160
10
10
10 10-3
10
100
13
320
100
10-2
10
10-1
100
13
80
10-3
10-2
10
10
1
6
Weather Data
472
1
10-2
10-1
10-4
10-1
6
T = 100
7x = 0.5
NBA Data
233
10-2
102
102
11
Top = 100
Yy = 0.5
A.10.5 Experiments for Ablation Studies
In order to understand the impact of different components of Sparse OpMINRES-L-D, we have run experi- ments for 12-node synthetic data by varying different hyperparameters and switching off different components in our approach. In order to enforce sparsity of learned graphs, we introduce Mtrace based constraint in Sec- tion 5.1.4 In Table 19 we tabulate the graphs corresponding to learned L with Sparse OpMINRES-L-D for 12-node experiments using Mitraee E (0, 0.25p, 0.5p, 0. 0.75p, 0.9p) with p = From Table 19 that most of the edges are being retained as Miraaee value is increased. The connections learned are illustra- tive of the generation process of synthetic data in Section A.10. as Miraoe is increased. Choice of merace can be based on the error corresponding to the validation set as well the desired number of connections to be learned since the number of edges increases with increase in mtrace- Table 20 illustrates that the performance with different Mirraee is comparable and trade-off is expected when varying Merace
we observe
To illustrate the impact of choosing different kernels in our framework, we utilize different kernels as l/ in by utilizing the following:
ABS: (a(s,t) t) e 7oplls-1
DIFFABS: kz(s,t) -o7opp lo-t| - topglss-t
RBF: (s, Yomp
Tomp 18-
EPAN: (2, max (0, Topls -112),
with Top. Tops Tops E =1006 10-5 10-3,10-3, 10-2, 10-1 10-1, 10,0 Note that we use k as defined 108 which incorporates and of the learned graph. Table 21 showcases comparable performance of different kernels as l2, but Table 22 illustrates the graphs learned different connections for ABS, DIFFABS. We see that RBF and EPAN kernel choices learn different graphs which contain some useful connections which be related to the generation of the synthetic data. It can be interpreted that most of the connections learned by ABS, DIFFABS and RBF kernels better represent the generation of 12-node synthetic data.
Next, we study the impact of the Miraaee constraint in the sparsity regularization and the complete sparsity regularization framework as proposod Section 5.1.4. Table 23 illustrates comparable performance basod on mean RSSE error where mirace constraint removed and and D-based regularization removed by setting Pr. and pD O. Similarly, Table 24 illustrates comparable performance when MCP regularization is
76

---

Published in Transactions on Machine Learning Research (03/2024)
Table 19: Graph corresponding learned by considering miraae {0.1p, 0.25p, 0.5p, 0.75p, 0.9p) OpMINRES-L-D for 12-node experiments (p -p=10 12). [Best viewed color
Sparse
Train/ Val/ Test
Mirraee = 0.1p
Mitrace = 0.25p
Mirace 0.5p
Mitrace =
0.75p
Mirrce
0.9p
samples
80/20/20
Log
160/40/40
Log scale
320/80/80
-3
Log scale
completely removed and L and D-based regularization removed by sctting PL and pD as Although the performance is comparable in terms of mean RSSE error, however we note that Tables 25 and 26 illustrate the failure to learn meaningful graphs since most of the graphs have connections with equal weights providing relevant information. Without the mtrace constraint, Table 25 showcases negligible weights being assigned to each connection, while without the complete MCP regularization framework Table 26 showeases uniformly distributed weights across fully connected graphs.
77

---

Published in Transactions on Machine Learning Research (03/2024)
Table 20: Mean RSSE. results for mirace in p0.1p, 0.25p, 0.5p, 0.75p, 0.9p} using Sparse OpMINRES-I-D
12-node synthetic data (p- 12).
Mean RSSE
Train/ Crain/Va//unn samples
Mirrace in Sparse OPMINRES-L-D
Train
Val
Test
Miraace 0.1p
1.250593
1.727192
1.532670
Mirraee = 0.25p
1.234657
1.735397
1.587149
80/20/20
Mirraee 0.5p
1.140691
1 1.735397
1.583640
Mttraee 0.75p
1.092453
1.904231
1.636385
Mirraee 0.9p
1.075372
1.916426
1.640379
Mtrace 0.1p
0.873584
1.291735
1.380035
Mtrace 0.25p
0.886945
1.263236
1.368678
160/40/40
Mitrace: 0.5p
0.888574
1.229568
1.385952
Mtrace = 0.75p
0.849892
1.265577
1.412620
Mtrace 0.9p
0.831497
1.284316
1.425376
Mirace 0.1p
1.073370
1.291374
1.237471
Mitrace 0.25p
1. 1.071354
1.295419
1.238216
320/80/80
Miraaee 0.5p
1. 1.062102
1.294110
1,239181
Miraaee 0.75p
1.056678
1.295300
1.242216
Mtraaee 0.9p
1.053001
1.296809
1.241735
Table 21: Mean RSSE results for different kernels as l2 with 12-node synthetic data.
Mean RSSE
Train/ Ctain/Val/Ton Val/Testt samples
ly
Sparse OpMINRES-I-D
Train
Val
Test
ABS
1,140691
1.780445
1.583640
80/20/20
DIFFABS
1.167264
1.806093
1.618175
RBF
1.111369
2.092855
1.754655
EPAN
0.759214
2.035527
1.838925
ABS
0.888574
1.229568
1.385952
160/40/40
DIFFABS
1.154356
1.362239
1.417921
RBF
0.846649
1.236121
1.428687
EPAN
0.906656
1.260602
3. 3.626625
ABS
1.062102
1.294110
1,239181
320/80/80
DIFFABS
1.073292
1.295140
1.243346
RBF
0.931760
1.330628
1,283005
EPAN
1.026490
1.304147
1.247868
Further, we perform experiments where we utilize a lasso based regularization to induce sparsity instead of depending upon the proposed sparsity inducing framework. We introduce pp E DDul > 0 in (3)
instead of PL En z00) Lx(") + DI and ignore the proposed MCP rogularization framework. Table
28 illustrates comparable performance terms of mean RSSE error but Table 27 showcases the failure distinguish meaningful interactions in the learned graphs.
78

---

Published in Transactions on Machine Learning Research (03/2024)
Table 22: Graph corresponding to learned L by considering different kernels for ko in Sparse OpMINRES-LAA for 12-node experiments. Best viewed in color]
Train/ Val/ Test
ABS
DIFFABS
RBF
EPAN
samples
80/20/20
-5
Log scale
160/40/40
320/80/80
Log scale
79

---

Published in Transactions on Machine Learning Research (03/2024)
Table 23: Mean RSSE results for 12-node synthetic data using Sparse OpMINRES-L-D with no Miracee constraint and ablation of regularization with respect to L and D.
Train/ / Test samples
Mean RSSF
Methods
Train
Val
Test
Sparse OPMINRES-I-D
1.140691
1. 1.780445
1.583640
80/20/20
Sparse OpMINRES- L-D with no Meraae
1,274110
1. 1.729524
1.530376
Sparse OpMINRES-L-D with no Merace and Pt. =
1.273360
1.729269
1.530041
Sparse OpMINRES-LAA with no Mirace and pD = 0
0.790852
1.891594
1.407203
Sparse OpMINRES-
0.888574
1. L.229568
1. 1.385952
160/40/40
Sparsc OpMINRES-I-D with no Merace
0.896321
1,229568
1.371430
Sparse OpMINRESS-L-D with no Meroce and PL
0.896311
1. 1.280351
1.371432
Sparse OpMINRESS---D with Merace and PD 0
0.833068
1.291457
1.410686
Sparsc OpMINRES-LLD
1.062102
1.294110
1.239181
320/80/80
Sparse OpMINRES-LL) L-D with Meraoe
1.078058
1.291549
1.237178
Sparse OpMINRES- L-D with no Merace and
1.078026
1.291574
1.237129
Sparse OpMINRES-L-D with no Marace and PD = 0
1.078058
1.291550
1.237179
Table 24: Mean RSSE results for 12-node synthetic data using Sparse OpMINRES L-D without MCP regularization and ablation of regularization with respect to and D.
Train /Val/ Test samples
Mean RSSE
Methods
Train
Val
Test
Sparse OpMINRES-ILDD
1.140691
1.780445
1.583640
80/20/20
Sparse OpMINRES---DD with no MCP
0.911711
1.893550
1.481332
Sparse OpMINRES-L-D with no MCP and Pr. = 0
0.911711
1.893550
1.481332
Sparse OpMINRES L-D with no MCP and pD = 0
0.755296
1.892366
1,399945
Sparse OpMINRES-L-I
0.888574
1. 1.229568
1.385952
160/40/40
Sparse OpMINRES-L-D with no MCP
0.838759
1. 1.282838
1.397084
Sparse OpMINTRES-L-D with MCP and Pr 0
0.838759
1. 1.282838
1.397084
Sparse OpMINRES-L-D with MCP and PD 0
0.793097
1. 1.289822
1.429700
Sparse OpMINRES-L-D
1.062102
1.294110
1.239181
320/80/80
Sparse OpMINRES-I-D with no MCP
1.062727
1 1.298913
1.240176
Sparse OPMINRES---D with no MCP and = 0
1.062727
1.298913
1.240176
S Sparse OpMINRES-L-D with no MCP and pD = 0
1.062727
1.298926
1.240208
80

---

Published in Transactions on Machine Learning Research (03/2024)
Table 25: Graph corresponding learned T. by no Mirraee constraint and controlling pr I-based regular- ization and pD in D-based regularization for 12-node experiments. [Best viewed in color]
Train/ Val/
80/20/20
160/40/40
320/80/80
Test samples
No Mirrcc
Pr. = 0, no Mirace
-1
PD = 0, no Mitrace
-5
-1
Log scale
81

---

Published in Transactions on Machine Learning Research (03/2024)
Table 26: Graph corresponding learned L by switching off the MCP-based regularization and controlling
PL in L-based regularization and po in D-based regularization for 12-node experiments. [Best viewed in color]
Train Val/
80/20/20
160/40/400
320/ 220/88080
Test samples
No MCP
PL 0, no MCP
Log scale
PD 0, no MCP
Log scale
82

---

Published in Transactions on Machine Learning Research (03/2024)
Table 27: Graph corresponding to learned L by using only D-lasso based regularization without MCP-based sparsity inducing regularization instead of Sparse OpMINRES-L-D for 12-node experiments. [Best viewed in color]
Train Val/
80/20/20
160/40/40
320/80/88
Test samples
Sparse OPMINRES-I-D
D-lasso without MCP
Log
Table 28: Mean RSSE results for 12-node synthetic data using Sparse OPMINRES-L.D without MCP regularization and lasso regularization for D.
Train Val/ Test samples plmples
Mean RSSE
Methods
Train
Val
Test
80/20/20
Sparse OpMINRES---D
1.140691
1.780445
1.583640
Sparse OpMINRES-LLD with no MCP and D lasso
0.745433
1.891283
1.402357
160/40/40
Sparse OpMINRES-L-U
0.888574
1.229568
1.385952
Sparse OpMINRES-LLD with no MCP and D lasso
0.821067
1.284889
1.409910
320/80/80
Sparse OpMINRESTL-D
1.062102
1.294110
1.239181
Sparse OPMINRES-L-D with no MCP and D lasso
1.073490
1.297428
1.241109
83


Reviews:
[{"review_id": "sSY65i6c5I", "reviewer": "Reviewer_VaBc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1) A useful framework for learning structural associations between input features. I could imagine use cases of this framework for learning relations among the input features.\n\nS2) Overall, paper is clearly written and easy to follow.\n\nS3) Experiments are helpful for understanding the results.\n\n=========================\n\nW1) The paper is quite long and I find that lots of the content are unrelated to the main claims of the paper.\n\n- In Sec 5.1, this section focuses learning with known graph structure; is this setting used elsewhere in the paper? If I understand correctly, both settings in the experiments are in the case where the graph structure is not known.\n\n- In Sec 6, things like Definition 6.1 and Lemma 6.2 should probably be in the appendix (which look like textbook materials).\n\n- The proof of Lemma 6.6 should also be in the appendix (steps look standard).\n\nW2) Experiment codes are not available.\n\nW3) There are no ablation studies detailing each component of the algorithm. There is no ablation on the effect of the regularization penalty as well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors propose a approach to learn relational structures given multiple input variables. These variables may be features, or functions of input-output maps, etc. There is a label associated with reach realization of the inputs. The goal is to learn the mapping from the input variables to the output label.\n\nThe approach here is based on kernel methods. This kernel operates on the multiple input variables, with possible extensions such as adding regularization to the weights of the kernel map.\n\nOne of the main idea of this paper is to add a Laplacian matrix on top of this kernel. This Laplacian matrix takes an input graph, and then uses the Laplacian matrix product to associate the input variables.\n\n- In the setting where the graph is given, learning the kernel is straightforward, similar to standard kernel methods.\n\n- When the graph is not known, the paper designs an alternating minimization method, which learns the kernel and the Laplacian in an alternative fashion.\n\nSome theoretical analysis and experimental results are used to illustrate the above.\n- In particular, the theoretical analysis concerns the generalization error of learning the kernel.\n- The experiments apply the alternating minimization method on a weather forecasting dataset and an NBA player movement dataset. The results illustrate the presence of associations within the input features.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think this paper introduces a useful framework for learning relational maps given multiple variables. The algorithm design is sound. The experiment findings would be interesting to the community. At the same time, I think the paper requires some revision, for instance reducing supporting information from the main text that are irrelevant from the main claims. Besides, experiment codes should be released.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Cr2HuvycbA", "reviewer": "Reviewer_mn8m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. A strength of this research lies in its ability to incorporate the learning of an appropriate graphical structure within the context of functional regression.\n2. The incorporation of a sparsity-inducing regularizer in the Laplacian matrix enhances interpretability by highlighting the most relevant interactions among input functions. Additionally, the proposed sample-based approximation algorithm improves scalability, enabling efficient processing of the data.\n3. The research establishes a generalization error bound for the proposed approach.\n\nWeakness:\n1. The research does not extensively compare the proposed method with existing approaches in functional regression, e.g. functional PCA based approach or neural networks based approach.\n2. The theoretical results presented in the paper focus on the simplest case, without considering the incorporation of a sparsity-inducing regularizer or the use of a sample-based approximation algorithm.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This research focuses on the task of function-to-function regression, which involves learning a mapping from a set of input functions to an output function. The authors propose an innovative approach using a graph-induced operator-valued kernel to capture the relationships among the input functions. Even in cases where the underlying graphical structure is unknown, they present a method to learn an appropriate Laplacian matrix, enabling a comprehensive understanding of the connections. To tackle this learning problem, the authors develop an alternating minimization framework. This framework incorporates a min-max concave penalty that encourages meaningful interactions within the graphical structure, leading to more reliable results. The framework is also designed to handle complex scenarios involving multi-dimensional input and output functions. In addition, they introduce an efficient sample-based approximation algorithm, allowing for efficient processing of large datasets. The research also provides valuable insights into the generalization performance of the learned mapping. The authors establish bounds on the generalization error of the proposed method. Furthermore, through extensive empirical evaluations on both synthetic and real datasets, they demonstrate the effectiveness of their learning framework.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1.The numerical experiments involve only several hundred training examples, which leaves uncertainty regarding the assessment of scalability.\n\n2.The numerical experiments do not provide clear evidence on whether the proposed nonlinear model outperforms the linear model presented in (Gómez et al., 2021).\n\n3. It is a little bit strange that the convergence rate $m^{-\\eta/8(1+\\eta)}$ in (125) is independent of the covering number index $q$ in (118). Moreover, it is strong to assume that $F\\in\\mathcal{H}_{\\mathcal{K}}$ in Theorem 6.3.\n\n4. Any special reason to use MCP instead of LASSO?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "weMM2L52EA", "reviewer": "Reviewer_kJos", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Upsides:\n1. In general, this paper is well-written. Background information and relevant literature are adequately covered. Technical developments of the work are rigorous, intuitive, and well-founded from existing works. The mathematical quality of the work is good.\n2. The authors provided extensive examples and experiments for functional regression models with graph structures. This empirically shows the improvement of the authors' methods in some spatial-temporal functional regression problems.\n\n## Downsides:\n1. There is a lack of proof for the convergence of alternating minimization of a non-convex function $J$ proposed in this paper. The choice of hyperparameters, e.g. learning rates, in OpMINRES is not explicitly discussed in the paper to ensure convergence. \n2. Although the authors provided a generalization analysis, there is a lack of discussion on how the graph-induced kernel regression and sparsity of the graph change the generalization error bound for the regression problem. The interpretation of Theorem 6.3 and (125) should be expanded in the paper.\n3. In the kernel regression part, the authors chose specific kernels $k_1$ and $k_2$ in (2) without enough explanations on the choice of the kernels. There should be either empirical or theoretical comparisons with different kernels on this problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper outlines a novel approach to functional regression problems, where the objective is to map multiple input functions to a single output function. The key contributions and methodologies presented in the paper are as follows:\n\nThe authors introduced a graph-induced Operator-Valued Kernel (OVK) to solve functional regression problems, leveraging a graphical structure to represent interactions among input functions, especially a sparsity-inducing regularization on the Laplacian matrix. This framework assists in learning the regression map along with the graphical structure itself. The authors raised an alternating minimization framework for learning the map and the matrices representing the graphical structure through the Operator-based Minimum Residual (OpMINRES) algorithm and projected gradient descent and they extended the framework to address multi-dimensional functional regression problems. They also studied the generalization error bounds for the learned functional regression map, which also takes into account the learning of the graph-induced OVK.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The notation is (4) and below are confusing. Does this inner product stand for $x^\\top Lx'=\\sum_{i,j} \\int_0^1x_i(t) L_{ij} x_j'(t)dt$?\n2. Proposition 5.1: typo $L([0,1])$.\n3. Typo in (9).\n4. If we consider a graph $G$ without self-loops, then $L= D-A$ will determine $D$. In this case, we do not need regularization on $D$ in (13), right? This should simplify the algorithm. In the results of the experiments, I did not see self-loops for all vertices. So why do we need regularization on $D$?\n5. At the top of page 10, the authors mentioned a different regularization from Humbert et al., 2021. Is this smoothness term better than (13)? There should be more explanations here. \n6. In  (22), using upper indices to indicate the number of iterations is confusing with the powers of the quantities. \n7. In Section 5.2.4, you used the trace of Laplacian for sparsity-induced regularization, but why not use $\\ell_1$ minimization of $D$ for regularization? Besides, any insight into why you chose $m_{trace}=p/2$. The choice of $m_{trace}$ indicates the graph is extremely sparse but this hyperparameter should depend on the problem and datasets, which can be estimated in other ways.\n8. Please specify the hyperparameters in Algorithms 1 and 2. \n9. Typo above (73): $X^m$ should be $\\mathcal{X}^m$.\n10. In Section 7, you used KPL-OpMINRES-D in many places which should be KGL-OpMINRES-D.\n11. How do you explain the results in Section 7.2 on weather data? Sparse OpMINRES-L-D provided a sparse graph but should it be better if the graph has more edges for places close to each other? \n12. In A.9, you repeated the details of the experiments stated in Section 7, which is a redundancy. Maybe you should provide more details such as the learning rates, regularization parameters, and $m_{trace}$.", "broader_impact_concerns": "Not very applicable here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper formulates a new problem (many-to-one functional regression) and properly motivates it.  The paper provides a method to address this challenge, and demonstrates empirically that it is general and effective.  In some cases, convergence bounds are provided and proven.  The scope is clearly within machine learning.  

The reviewers felt the authors were appropriately responsive to their comments.  Ultimately, the improvements made were minor, and the paper is ready for publication.
Decision: Accept (poster)