Efficient Covariance Estimation for Sparsified Functional Data
Authors: Sijie Zheng
Fandong Meng
Jie Zhou
Venue: Submitted to ICLR 2023 (2023)
Keywords: functional data
covariance estimation
spatial correlation
convergence rate

Abstract: To avoid prohibitive computation cost of sending entire data, we propose four sparsification schemes Random-knots, Random-knots-Spatial, B-spline, Bspline-Spatial, and present corresponding nonparametric estimation of the covariance function. The covariance estimators are asymptotically equivalent to the sample covariance computed directly from the original data. And the estimated functional principal components effectively approximate the infeasible principal components under regularity conditions. The convergence rate reflects that leveraging spatial correlation and B-spline interpolation helps to reduce information loss. Data-driven selection method is further applied to determine the number of eigenfunctions in the model. Extensive numerical experiments are conducted to illustrate the theoretical results. 

Under review as a conference paper at ICLR 2023
EFFICIENT COVARIANCE ESTIMATION FOR SPARSIFIED FUNCTIONAL DATA
Anonymous authors Paper under double-blind review
ABSTRACT
To avoid prohibitive computation cost of sending entire data, we propose four sparsification schemes RANDOM-KNOTS, DANDOM-KNOTS-SPATIAN B- SPLINE, BSPLINE-SPATIAL, and present corresponding nonparametric estimation of the covariance function. The covariance estimators asymptotically equiva- lent to the sample covariance computed directly from the original data. And the estimated functional principal components effectively approximate the infeasible principal components under regularity conditions. The convergence rate reflects that leveraging spatial correlation and B-spline interpolation helps to reduce in- formation loss. Data-driven selection method is further applied to determine the number of eigenfunctions in the model. Extensive numerical experiments are con- ducted to illustrate the theoretical results.
INTRODUCTION
Dimension reduction has received increasing attention to avoid expensive and slow computation. Stich et al. (2018) investigated the convergence rate of Stochastic Gradient Descent after sparsifica- al. (2021) focused the mean function of vector containing only subset of the original vector. The goal of this paper is to estimate the covariance function of sparsified functional data, which is set of sparsified vectors collected from distributed system of nodes.
tion. Jhunjhunwala
Functional data analysis (FDA) has become an important research area due to its wide applications. Classical FDA requires large number of regularly spaced measurements per subject. The data takes the form {zx,,j/d) < i < n, S j S d} in which (-) is a latent smooth trajectory,
xrx()) m(-) + Z.(-).
(I)
The deterministic function m-)) denotes the common population mean, the random (-(.) are subject- specific small variation with (.), ()) = 0. Both m (-) and Z, (-) are smooth functions of time t j/d which is rescaled to domain D [0, 1]. Trajectories 2x(-) are identically distributed realizations of
the continuous stochastic process {ar(t), E D), EsuPtED (x=(t)) < +00 which can be decomposed
as x-)) = m--) + Z(), (t) 0. The true covariance function is G (t, = Cov {t(t), Z (t'))
Let sequences {A+ (> k-1 and { be the eigenvalues and eigenfunctions of (t, respec- tively. in which A 2 A > ... 2 0. Ex=1
k= d < cc. { form an orthonormal basis of [,2 1}. see Hsing & Eubank (2015). Mercer Lemma entails that the the 's are continuous and G (t,,')= ar()) allows Karhunen-Loève 2 representation sx.) m(.)+ Ex (adu(-), in which the ran- dom coefficients, εx. called functional principal component (FPC) scores, are uncorrelated with mean and variance The rescaled eigenfunctions, ós. called FPC, satisfy dy V and [a((t) m(t)} (t)dt = ΛsEE, for à 2 1. Although the sequences {A {ox) and ) jiml, exist mathematically, they are either unknown or unobservable.
Ei=r (t) (t') (t, the (t') dt' Atvx(t). The standard process
1.1 MAIN CONTRIBUTION
In FDA, covariance estimation plays a critical role in FPC analysis (Ramsay Silverman (2005).
Li & Hsing (2010)), functional generalized linear models and other nonlinear models (Yao et al.
'The code is attached the supplementary material and will he publicly available once accepted.

---

Under review as a conference paper at ICLR 2023
2005b)). We propose four sparsification schemes, SANDOO--NOTTE & RANDOM-KNON KNOTS-SPATIAL can be classified as RANDOM- SAADDOMSPAASIIICATUUI where knots are selected uniformly from the entire points at random. B SPLLIIN& & ESPLINE-SPATIAN are called SAEED-SPRSSIIIATION intercepting knots at fixed positions in each dimension of the vector. For all sparsification modes, we construct the two-step covariance estimator G (--)), where the first step involving sparsified trajectories and the second step plug-in covariance estimator by using the estimated trajectories in place of the latent true trajectories. The statistic is further multiplied by an appropriate constant to ensure unbiased- ness. The covariance estimator G (+.-) enjoys good properties and can effectively approximates the sample covariance function G (---) computed directly from the original data. This paper improves the performance of statistics from the following two aspects, requiring little or no side information and additional local computation.
SPATIAL CORRELATION: We adjust the fixed weights assigned to different vectors to data- driven parameters that represent the amount of spatial correlation. This family of statistics naturally takes the influence of correlation among nodes into account, which can be viewed as spatial factor Theoretical derivation reveals that the estimation error can be drastically reduced when spatial factors among subjects are considered.
B-SPLINE INTERPOLATION: To fill in the gap between equispaced knots, we introduce spline interpolation method to characterize the temporally ordered trajectories of the func- tional data. The estimated trajectory obtained by B-spline smoothing method is as effi- cient the original trajectory. The proposed covariance estimator has globally consistent convergence rate, enjoying superior theoretical properties than that without interpolation. Superior the covariance estimation leveraging tensor product B-splines, our two-step estimators are guaranteed to be the positive semi-definite.
In sum, the main advantage of our methods is the computational efficiency and feasibility for large- scale dense functional data. is practically relevant since curves or images measured using new technology are usually of much higher resolution than the previous generation. This directly leads to the doubling of the amount of data recorded in each node, which is also the motivation of this paper to propose sparsification before feature extraction, modeling, or other downstream steps.
The paper is organized as follows. Section 2 introduces four sparsification schemes and the corre- sponding unbiased covariance estimators. We also deduce the convergence rate of the covariance estimators and the related FPCs. Simulation studies are presented in Section 3 and application in All technical proofs are involved in the Appendix.
domain clustering in Section 4
1.2 RELATED WORK
Considerable efforts have been made to analyze first-order structure of function-valued random el- ements, i.e., the functional mean m (-). Estimation of mean function has been investigated in Jhun- jhunwala et al. (2021), Garg et al. (2014). Suresh et al. (2017). Mayekar et al. (022] and Brown al. (2021). Cao et (2012) and Huang al. (2022) considered empirical mean estimation using B-spline smoothing. The second-order structure of random functions covariance function G (..
the next object of interests. To the best of our knowledge, spatial correlation across nodes has not yet been considered in the context of sparsified covariance estimation. The research on sparsi- fication has received wide attention recently, for instance Alistarh et al.) (2018), [Stchh et al. (2018) and (Sahu et al. (202T). Sparsification methods mainly focus sending only a subset of elements of the vectors, yet no existing method combine sparsity method with B-spline fitting. Moreover, there has been striking improvement over sparse PCA. |erthhe & Rigollet (2013b) and Choo & d' O'Osi (2021) have analyzed the complexity of sparse PCA; & Rigollet (2013a) and Deshpande & Montanari (2014) have obtained sparse principle components for particular data models. Since estimation methods are innovative, the related study of PCA is proposed for the first time.
2
MAIN RESULTS
We consider geographically distributed nodes, each node generates d-dimensional vector J; (Zil...., F.a) for i E (1, .1.,,...,11) n... The mean and covariance functions could be estimated
"The superseript SPAT is applied distinguish whether the statistic considering spatial factor.
2

---

Under review as a conference paper at ICLR 2023
by (t)
-=1 Zz (t) and G (t,t') = Ei= (1, (t) m (t)) (a, (t') - (t')), see Brockwell & Davis 2009) For q E N. μ E (0, 1], write H((-m) [0, 1] as the space of μ-Hölder continuous func-
((() (a)) (v) +00
tions, i.e., H((a-)) [0, 1] = p [0, 1] R || sup...yelo.)....
---5/"
Notations: In this paper, Op (or o.) denotes a sequence of random variables of certain order in probability and by Oa.s. (or O....) almost surely O (or o). For sequences a, and b,. denote an x by if on and b, are asymptotically equivalent. For any Lebesgue measurable function 6(x) on domain D, let ||0|| 0o suDxed [6(x). For any L integrable functions o(x) and (xxx,, D, take (0, 12) Jo (x with || (Ø, Φ). For simplicity, || = 1|
We next introduce some technical assumptions.
Assumption 1: There exists integer q > 0 and constant μ (0, 1], such that the regression
function m(-) E: H/aa [0. In the following, we denote p' = q μ for simplicity.
Assumption 2: The covariance function satisfies sup(a.))) G (t,tt)
< C, for some positive
constant C' and min G (t, t') > 0.
Assumption 3: There exists constant 0 >> 0, such that as d + o0 n(d) + n (d').
Assumption 4: The rescaled FPCs (x(() E Holoo 1] with Ex= (110klla.4 + 110xalooe < +00; for increasing positive integers [kn] O (n²) for some w > 0.
00, Ex. l O (n- and kn
Assumption 5: The FPC scores {Eik (2ik)21421 are independent over & 2 1. The number of distinct
distributions for all FPC scores {Es } 1211211 is finite, and max1sk<0e E < do for ro > 4.
Assumption 6: The number of knots J, x d'Ca for some with Ca CJ - O (log" d) as -+ 00, 7 2 for RANDOM- SAADOMMSPARSIIIIATION,, 7 > 2p" + Tap"
for TINED-SPARSFFICATTON.
Assumptions 1-5 are standard requirements for obtaining mean and covariance estimators in lit- erature. Assumption guarantees the orders of the bias terms of the spline smoothers for m (-). Assumption 2 ensures the covariance G (::)) is uniformly bounded. Assumption implies the di- mension of vectors d diverges to infinity for dense functional data and all the following asymptotics are developed as both the number of nodes and dimensionality d tend to infinity. Assumption 4 concerns the bounded smoothness of FPC and Assumption 5 ensures bounded FPC scores, for bounding the bias terms in the spline co- variance estimator. The smoothness of our estimator is controlled by the number of knots, which is specified in Assumption 6.
- oc, which is well-developed asymptotic scenario
Remark 1. These assumptions are mild conditions that can be satisfied in many practical situations. One simple and reasonable setup is: q + u = p = 4, 0 = 1, = 5/8, Ca x log log d. We set obtain cubic spline estimation and p = for FIXED-
p for LANDOM-SPARSIFICAN SPARSIFICATION to get estimates without interpolation. These constants are used as defaults in numerical studies.
2.1
SANDOM-SPARSIIIATTION
Elements in each vector are randomly setting to zero with probability 1 1 1 Under this sparsi- fication scheme, HANDOM--NOTH and RANDOM- LANDOM-KNOTS-SPAA KNOTS-SPATIAL covariance estimators are pro- posed, where temporal dependence exhibited in functional samples is ignored. Proportion 1 depicts the difference of data volume before and after sparsification, reflecting the degree of sparsification.
RANDOM-KNOTE (RK) As shown in Figure 2.2 (a), the left are original vectors {x.) and right are sparsified vectors {h.),- randomly containing J, elements of the original vector with 3, d 6, J/ = 3. This definition tells that P (hiy 0) 1 24 P (hz, I.5)) 4. The estimator generated from {hr ) is called sparsified estimator which is obtained by replacing orig- inal trajectory I; = (I.1, Tta)) with sparsified h, = (har..., hww) T i.. in A 4 J, Σm= h;
and G = 1/2
d Σi (he Ti) (h+- T)) where = #/4 En hs is d-dimensional vector. J,
3

---

Under review as a conference paper at ICLR 2023
The next theorem states the mean squared error (MSE) of the estimator tends to zero -
Theorem 1. (RK Estimation Error) Under Assumptions 1-5, MSE of estimate G produced by the R1 where
RK sparsification scheme described above is given by El|G - G| = n (( (1) -1)
R1 = -E= n I|: ml|" Assumption 6 further guarantees that -
_ = Op (1-1
RANDOM- WHEIOMM-KNOT-SSSS SPAAIALL (RK-SPAT) Denote by M, the number of nodes that send their j-th
coordinate to describe the correlation between nodes. It is obvious that M, a binomial random variable that takes values in the range (0.1,....77) _n} with P (M1 = m) = (m)p" (1 -1-17 (1-p)" p)" P
2. If M2 0, none of the nodes have drawn the j-th element, and the information at position is completely missing.
If nodes are highly correlated, the estimator is accurate position j even if few points at that position are selected. Consider a special case where vectors of all nodes are the same, i.e., I1 = I2
Σn- The j-th coordinate of mean can be exactly estimated as mn M, Σ hij
1
whenever Mj And the exact covariance function is G55² Mj Ei=1 (huj h2) (he - hy).
h2 is the j-th element of the d-dimensional vector j' * j. Simple mathematical derivation implies that h m, under this situation. Hence, the fixed scaling parameter 2/2 is not necessary.
If nodes are lowly correlated, small M, may lead to a large MSE. Consider (i) vectors corresponding to n - nodes follow sine distribution Tij- = sin (2 () 2). s n - 1, 1 J S d and the outlier node follows cosine distribution Fnj cos (2mr) )) (ii) the outlier vector has a jump at j-th position Tnj sin (2 4) 8, Inz' sin 2 / 8
for j' { 1, + I,...,d, .d} while other n 1 nodes follow standard sine distribution. In special case that only the outlier vector is selected for position j. the estimation at this position is bound to have large deviation. Therefore, the correlation between nodes is an important indicator to measure the accuracy of estimators.
We propose RK-SPAT estimator wherein the fixed scaling parameter 1/ is replaced by a function of M, such that the spatial correlation between nodes is taken into account. Specifically, the mean estimator for j-th element is SPAT
1 E -i=1 hag. Covariance function at position (J,j") is
n T(M,)
B
ČSPAAT
(hy-hg) (hey hyy)
((M)) ((M
where the introduced function T (M₁) changes the scaling parameter and 3 is
J. J' d M,,
( n
J d )
J3 n-r
3 We prove that the RK-SPAT covariance estimator is unbiased. Proposition (RK-SPAT estimator Unbiasedness) E&SPAT G.
)
1
(3)
T(M))
The following theorem measures the approximate quality of RK-SPAT estimator, Theorem 2. (RK-SPAT Estimation Error) Under Assumptions 1-5, MSE of estimate produced by
2 the RK-SPAT family is El|(GSPAN - -G112 = 1/2 (4+ - Ri + + ((1-22) c22) 11) Rg.
where R1 = Em ||: mll R 2
(1z;- mm (xx - m))) and B is defined
(m;-m))
in 3. The parameters C₁. 02 depend on the choice of (-) as
= 82
J.
r (-11
n 1)
(
J1
1
J p-r d
dT
d
d
J.
J2 nn- 2
J,
r-2
(1
Js
c = Σ
PT(r)² r -- 2/
d
d
2
| - c = Op (n-1/2).
Assumption 6 further guarantees that
4

---

Under review as a conference paper at ICLR 2023
can be further simplified as B|JGSPAT - G112 = + ( 201 J. - -1)
Theorem 2
+
R +
1 n² (c2 202) R2. The MSE of SSSAT covariance estimator ensures to be lower than that of RK
estimator whenever (c) 2c1 J. R1 < (2c2 (3) R2, i.. R2/R1 > (ct + 2c 4; / (2c² G))
In general, since the MSE depends on the function T(-) through e₁ and C2. we can define T(-) to ensure that RK-SPAT estimate is more accurate than RK estimate.
Theorem 3. (RK-SPAT minimum MSE) The optimal RK-SPAT estimator that minimizes the MSE
2 1/2
in Theorem can be obtained by setting T*
Rs
for E (1,2,-...,1
R
Jhunjhunwala et al.
(2021) claimed that optimal RK-SPAT mean estimator is obtained when (r) 1 Ri a-11 which is perfect for tasks involving only mean function, such as K-means but cannot guarantee the optimal estimation covariance function. It is significant to get accurate covariance estimate by setting 7 (-) as Theorem 3 In this way, the extracted features computed from eigenequation would improve the efficiency of downstream tasks, such as PCA. Meanwhile, the nodes number n and dimension d yield the amount of computation for R1 and Rg. We pro-
Ha
1 (==)²
1/2
pose the RK-SPAT (AVG) f(r)
as a default setting to avoid complicated
computation about R1 and R2.
2.2 FIXED-SPARSIFICTTION
We retain elements at J. fixed positions and set the rest to zero This dimensionality reduction method only utilizes values at fixed positions in the vector and has several disadvantages. (i) Each step only leverages the subset of data with size n x Ja. while the size of the origin data set is n x d. The fact that J4 < d resulting in serious loss of information. (ii) Approximate quality of the estimator depends on the selected points, and is difficult to control if the selected knots deviate from the overall distribution. (iii) Even if suitable knots are determined by adding penalty terms or selecting artificially, these knots may not be suitable for another node.
B-SPLINE (BS) As shown in Figure 2.2 (b), B-spline interpolation reduces the loss of information by fitting the values between fixed knots. It is worth noticing that the choice of basis functions and other smoothing methods (polynomial, kernel and wavelet smoothing) do not affect the large- sample theories. We choose standard B-spline bases because they are more computationally efficient and numerically stable in finite samples compared with other basis functions such as the truncated power series and trigonometric series. The B B-spline estimation is suitable for analyzing large data sets without uniform distribution, see SSchumaker (2007).
Denote by (tel/= a sequence of equally-spaced points, t = (J 0 41 < ... < +
t,. 1. called interior knots, which divide the interval [0. into (Ja +1 equal subintervals
to = O, = tJ,+p be auxiliary knots, and S(x-2) S(P 20 1] be the polynomial spline space of order p on Le, E [O.....Ja}; which consists of all (p 2) times continuously dif- ferentiable functions on [0. 1] that are polynomials of degree (p 1) on subintervals Te. Denote by (Be,(t), ( + p} the p-th order B-spline basis functions of S(r-2), hence S(p-2)
In = (0,t,), = [te, 12+1),
(l.....J, 1}. I, = [t.. 1]. Let ti-p
1= tJ,+1 =
JotD Dep de, E ER 11. (
The unknown trajectory x.(-) is estimated by h²(+) =
migming()esss Ej { - 9 (2,)3²² Edotp de B.,())). Coefficients estimation follows Ej=1 {x - Ed Be, (
B = (B
n.d The BS covariance estimator is obtained by replacing (hiz (hi))mmiss) with B-spline trajectories.
n.d ASPLINEE-SPATIAN (BS-SPAT) We replace (hiy) (hig)==i.ji in RK-SPAT estimator with B-spline esti- mation of trajectories. The BS-SPAT estimator not only considers the correlation among nodes, but also the correlation within a single node.
Next theorem states the convergence rate of BS and BS-SPAT estimators.
5

---

Under review as a conference paper at ICLR 2023
feurely
Search
(a) RK (RK-SPAT) Sparsification
(b) BS (BS- SUS-SPAT) Sparsification
Theorem 4. (BS (BS-SPAT) Estimation Error) Under Assumptions 1-6, the BS (BS-SPAT) esti- mator in(-) is asymptotically equivalent m(.)) up to order n/2 and similar conclusion holds for covariance function, i.e., as n - DC.
(i) I| -
100mmmlaa 0o = Da... (n 1/21. I1.: - Glloo = =Op 1//2)
(ii) | moll Op (12)). ||C Gl Op (1-1)
2 and 3 reflect that BS (BS-SPAT) covariance estimator converges faster to G than RK (RK- SPAT) estimator and the result uniformly holds on the interval D. It is obvious that the estimation performance of the proposed estimator is significantly improved by applying B-spline interpolation. This conclusion also confirmed the simulation.
Remark 2. The convergence rates in Theorems 7
2.3 CONVERGENCE OF PRINCIPAL COMPONENT
The estimates of eigenfunctions and eigenvalues are obtained by solving the eigenequations f (2, x') th (x') dx' Swain (a:), the consistency which then obtained.
Theorem 5. As + for le E N, we have
(i) (Convergence rate of eigenfunctions) | vra =Op
Op (n (1-2))))
(ii) (Convergence rate of eigenvalues) Ae X Opp (1-1/2);
(iii (Convergence rate of FPC scores) maxisisn fuu Esk Op (n-1/2)
is worth noticing that the orthonormal basis of the eigenmanifold corresponding to {Ax ) may be obtained by rotation, seeDauxois et al. (1982). Therefore, the unique form of the eigen- function should determined by minimizing the estimation error through the loss function L(ōk. Φx) = min.e(+11-1)) 1 - s
(ox. Φx) for Φk. Ob E {v E R" ||v|| = 1}. This is required because the estimated principal components { { j=1 are only identifiable up to a sign. Analogous results can obtained for alternate loss functions such as the projection distance: (ōk. ox) 1/2 @ O 1| / (0r,
3 SIMULATION
We conduct simulation studies to illustrate the finite-sample performance of the proposed methods.
3.1 KNOTS SELECTION
The number of knots is treated as unknown tuning parameters, and the fitting results can be sensitive it. Since the insample fitting errors cannot gauge the prediction accuracy of the fitted function, we select criterion function that attempts to measure the out-of out-of-sample performance of the fitted model. The formula based selection strategy as stated in Remark T we seek J, satisfies J, = dd Ca. Therefore, we suggest J. [od" log log d for some positive constant c, and 5/8.
Apart from this, minimizing Akaike information criterion (AIC) is one computationally efficient approach to selecting smoothing parameters. The candidate pool is all the integers between 1 and Jar, where Jz min ( (10, [ed2 log log d]) Specifically, given any data set (zi h/d/ d) (=) 1=111 from

---

Under review as a conference paper at ICLR 2023
model 1 denote the estimator for response 2ij by ha (J). The trajectory estimates depend on the knot selection sequence, which are sparsified vectors for RK (RK-SPAT) estimator and B-spline smoothing vectors for BS (BS-SPAT) estimator. Then, Ja,, for the i-th curve is the one minimizing AIC,
Ja,- = argmin Jrg.mn J..) (J),
where ATC = (RS(/))/ 2 (J p) /d. with the residual sum of squares RSS Ej=1 (Tig - hay (J)}². Then, J, is set as the median of { i=1
3.2 ACCURACY OF COVARIANCE ESTIMATOR
Data is generated from model:
Jaj m (i/d) + Σ Euds (i/d), 1sjsd, isisn, 121,
(4)
where m(t) sin (2 1/2)), (x(t) (t) A (1/4)l4/21, (t)) v2 cos(2k
(22 (t) sikkktt.. {Ew} follow standardized normal distribution. The infinite series (1, Σx=1 Φx (1) (t') is well approximated by finite sum (t,)t") Elen (t) (t"), according to the fraction of variance explained (FVE) criteria, FVE: = 1000 A Ei=1 dE > 1 1-10-10 10-10 see Yao et al. (0055)). (or n) is set to vary equally between 50 and 400 with fixed 200 (or d 200). Each simulation is repeated 1000 times.
Denote by G% (G the s-th replication of covariance & (G) at position (i.j") and G the true covariance function. The average mean squared error (AMSE) is computed to assess the performance of the covariance estimators G(.,)) and G(,,)), which is defined as AMSE(G) =
1 Ez (Gi.) -Oi,) AMSE (G) 1000d Eie Ejsz (G' Gz.)²
1000d
Figure shows that AMSE(G) decreases as n increases, consistent with Theorems and
AMSE G) reveals slow downward trend with the increase of d, mainly because the number of knots changes with d, affecting the performance of the covariance estimator. By setting T (-) as Theorem 3 AMSE of estimator that takes spatial factor into account is generally lower than estima-
tor that does not. AMSE of BS (BS-SPAT) covariance estimator confirms Theorem and estimation accuracy of the estimator is significantly improved by spline interpolation. Results on AMSE (G)
consistent with the fact that G converges G at the rate of (n-12)). Visualization of covari- ance functions is in Figure H in Appendix.
3.3 ACCURACY OF PRINCIPLEE COMPONENTS
Spectral decomposition is truncated at λ = 5 according to the standard criteria called "pseudo-AIC", see Mu et al. (2088). The selected eigenvalues can explain over 95% of the total variation. That is,
K = argmin, 1-psegJ, Ei=r-p dv/ Ex de 0.95] where { {^e
J.
k=1-p are all nonnegative eigenvalues estimated in FPC analysis. Figure 3 iillsstrates the first five eigenfunctions which ac- count for 68.2%. 17.0%, 4.3%, 4.3%, 4.0% of the total variation. The first figure shows a large difference overall the curve, depicting the trend of the covariance. The other four graphs have great fluctuations, and the frequency of fluctuations increases with k. The gap between the estimated FPC computed from the covariance estimators and the true FPC also increases with k.
Denote by Ař 6% the s-th replication of dE. G.. AMSES of eigenvalues Å 's and the eigen-
(Xg Au 2
functions Pox. 's are defined as AMSE(Å) = 1000N ΣlS Ei= - (b)) (1/1)22
AMSE(A) =
1000dw 1000
{
sdd: Random-knon AMSE(C) changes with and Õ is the RK estimator; "n: Random--nnots-pattaa" AMSE(G) changes with and G is the RK-Spat estimator. Other curves are defined similarly.
7

---

Under review as a conference paper at ICLR 2023
Figure reveals that AMSE(A) decreases with the increase of n, while the change with d is small, ( exhibits the same regularity AMSE(A), in accordance with Theorem | Whether or not to consider spatial factors has greater impact on the accuracy of cigenvectors than eigenvalues.
Figure 1: Left, middle: AMSE(G) as function of d, n. Right: AMSE (G) as function of d, n.
Figure 2: Row 1: AMSE(A) as function of d, Row 2: AMSE(O) function of d,
M
Figure Eigenfunctions computed from the true covariance and four covariance estimators.
4 APPLICATION
We seek to harness our method for downstream task domain data selection. The multi-domain corpus proposed Koehn & Knowles (2077) includes parallel text German and English from five domains: translations of the Koran, subtitles. medical, legal and IT-related text, available via OPUS (Allmo & Tiedemann 2019)). split as Aharoni & Goldberg (2020).
We encode multi-domain data at the sentence level into vector representations by pre-trained models.
(i) MLM- based model: BERT (Devlin et al. (2018)), DistilBERT (Sanh et al. (2019)) and RoBERTa
Liu et al. (2019)). in both the base and large versions; (ii) autoregressive model: GPT-2 (Radford
ct al. (2018) and XLNet (Yang et al. (2019);; (iii) baseline model: word2vex (Mikolov et al. (2013)). the implementations from the HuggingFace Transformers toolkit (Wolf et al.
In all cases
8

---

Under review as a conference paper at ICLR 2023
Pre-trained Model
without PCAA
PCA
RK
RK-SPAT
BS
BS-SPAT
word2vec
45.93
54.37
58.56
49.76
52.24
49.16
BERT-base
85.81
78.98
87.45
87.27
86.13
86.42
BERT-large
72.25
88.00
87.91
87.59
72.54
86.89
DistilBERT
73.35
87.53
87.03
86.84
85.83
85.94
GMM-5
RoBERTa-base
70.21
78.95
79.02
79.08
72.79
61.86
RoBERTa-large
59.32
73.74
80.94
73.51
73.38
86.15
GPT-2
37.82
70.25
68.97
68.96
69,42
69.47
XLNet
30.35
56.31
56.86
56.92
51.29
$1.19
word2vec
65.80
71.13
66.43
68.29
63.76
66.44
BERT-base
84.65
88.76
88.50
88,45
86.34
87.71
BERT-large
84.32
88.21
86.71
86,83
86.24
87.55
DistiBBERT
86.00
83.17
86.16
87.62
84.22
85.12
GMM-10
RoBERTa-baa
79.26
88.72
86.84
86.32
84.51
86.06
RoBERTa-large 81.17
88.13
89.27
89.21
88.67
89.29
GPT-2
40.26
84.34
83.47
83.09
83.50
83,36
XTNNet
36.57
70.47
68.92
68.37
64.43
55.64
Table Clustering Purity for unsupervised domain clustering. Best results each row are marked in bold. Explanatory variables involved in GMM-k are set to be original data without PCA, standard PCA and FPC scores computed from RK(-SPAT) & BS((SPAT) sparsified covariance estimators.
2019) ) We cluster these vector representations through a Gaussian Mixture Model (GMM-K) where the number of predetermined clusters. The estimated FPC scores are naturally independent random variables and converge the infeasible
FPC scores the rate of n n-122/22 in probability, see Theorem 5 (iii). It is reasonable to set the estimated FPC scores explanatory variables in GMM-k step, which are computed from É. X--1/2 (h, (t) m (t)) dhx (t) dt with Å and vix the estimates of cigenvalues and eigenfunctions of covariance estimator. We also set original vectors and FPC scores computed from standard PCA method explanatory variables for comparison. To evaluate whether the resulting clusters indeed capture the domains, we measure the Clustering Purity, which a well-known metric for evaluating clustering, see Schütze al. (2008).
Table shows MLM-base based models dominate over word2vec and auto-regressive models. Mainly because ML-M-bsed models use the entire sentence context when generating the representations, while auto-regressive models only use the past context, and word2vec uses limited window con- text. Direct modeling with data without dimensionality reduction has the worst results, and PCA significantly improves the performance in all cases. The last four columns of Table reflect that Pu- rity of the domain-clustering task is not sacrificed and even slightly improves in some cases. Hence, modeling FPC scores computed from sparsified covariance estimators shown to be efficient and effective. In sum, by applying our sparsification methods and related covariance estimation, we achieve the same performance standard PCA on the basis of accelerating computation speed.
CONCLUSIONS AND LIMITATION
In this paper, RK (RA-SP) estimator converges to averaged sample estimator without sparsi- and BS (BS-SPAT) estimator converges at the rate of Op(n
fication at the rate of We further characterize the uniform weak convergence of the corresponding estimation of eigen- values and eigenvectors. It is necessary to take spatial factor into account when correlation across nodes is non-negligible, thus standard approach to averaging sample vectors can lead to high esti- mation error. And spline interpolation is carried out to avoid the loss of overall data information. Theoretical results are backed by simulation and application.
A few more issues still merit further research. The AIC selection method works well in practice, but a stronger theoretical justification for its use is still needed. Our work focuses on the approximation and estimation, while in recent years, there has been great deal of work on deriving approximate distribution, which is crucial for making global inference. is also worth exploring to extend our novel sparsification methodology to functional regression model and large- longitudinal model, which is expected to find more applications in various scientific fields. Covariance estimation such models is significant challenge and requires more in-depth investigation.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Roce Aharoni and Yoav Goldberg. Unsupervised domain clusters in pretrained language models. arXiv preprint arXiv:2004, 200::2004000105,, 2020.
Dan Alistarh, Torsten Hoefler, Mikacl Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. Advances in Neural Information Pro- cessing Systems, 31, 2018.
Mikko Aulamo and Jörg Tiedemann. The opus resource repository: An open package for creating parallel corpora and machine translation services. In 22nd Nordic Conference on Computational Linguistics (NoDal.iDa). Linköping University Electronic Press, 2019.
Quentin Berthet and Philippe Rigollet. Optimal detection of sparse principal components in high dimension. The Annals of Statistics, 1184):1780-188 2013a.
Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Conference on learning theory, pp. 1046-1066. PMLR, 2013b.
Peter Brockwell and Richard Davis. Time series: theory and methods. Springer science &
business media, 2009.
Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance-aware private mean estimation without private covariance estimation. Advances in Neural Information Processing Systems, 34:7950-7964, 2021.
Guanqun Cao, Lijian Yang, and David Todem. Simultaneous inference for the mean function based on dense functional data. Journal of nonparametric statistics, 24(2):359-377, 2012.
Davin Choo and Tommaso d' O'Ori.. The complexity of sparse tensor pea. Advances in Neural Infor- mation Processing Systems, 11:7993--805, 2021.
Jacques Dauxois, Alain Pousse, and Yves Romain. Asymptotic theory for the principal compo- nent analysis of a vector random function: some applications to statistical inference. Journal of multivariate analysis, 12(1):136-154, 1982.
Yash Deshpande and Andrea Montanari. Sparse pea via covariance thresholding. Advances in Neural Information Processing Systems, 27, 2014.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint trXiv:1810.0480) 2018.
Ankit Garg, Tengyu Ma, and Huy Nguyen. On communication cost of distributed statistical estima- tion and dimensionality. Advances in Neural Information Processing Systems, 27, 2014.
Peter Hall, Hans-Georg Müller, and Jane-Ling Wang. Properties of principal component methods for functional and longitudinal data analysis. The annals of statistics, 341)) 2006.
Tailen Hsing and Randall Eubank. Theoretical foundations of functional data analysis, with an introduction linear operators, volume 997. John Wiley & Sons, 2015.
Kun Huang, Sijie Zheng, and Lijian Yang. Inference for dependent error functional data with appli- cation to event-related potentials. TEST, pp. 1-21, 2022.
Divyansh Jhunjhunwala, Ankur Mallick, Advait Gadhikar, Swanand Kadhe, and Gauri Joshi. Lever- aging spatial and temporal correlations in sparsified mean estimation. Advances in Neural Infor- mation Processing Systems, 34:1 4280- 2021.
Philipp Kochn and Rebecca Knowles, Six challenges for neural machine translation. arXiv preprint arXiv: 03872, 2017.
Yehua Li and Tailen Hsing. Uniform convergence rates for nonparametric regression and principal component analysis functional/longitudiaal data. The Annals of Statistics, 383))3331-3351, 2010.
10

---

Under review as a conference paper at ICLR 2023
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1tXh::1977.11992 2019.
Prathamesh Mayekar, Ananda Theertha Suresh, and Himanshu Tyagi. Wyner-zi ziv estimators: Effi cient distributed mean estimation with side-information. In International Conference Artificial Intelligence and Statistics, pp. 3502-3510. PMLR, 2021.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
Hans-Georg Mu et al. Functional modeling of longitudinal data. In Longitudinal data analysis, pp. 237-266. Chapman and Hall/CRC, 2008.
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language under- standing by generative pre-training. 2018.
JO Ramsay and BW Silverman. Principal components analysis for functional data. Functional data analysis, pp. 147-172, 2005.
Atal Sahu, Aritra Dutta, Ahmed M Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification as total error minimization. Advances in Neural Infor- mation Processing Systems, 34:8133-8144 8146, 2021.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint 19X.vv1900.0// 2019.
Larry Schumaker. Spline functions: basic theory. Cambridge University Press, 2007.
Hinrich Schütze, Christopher D Manning, and Prabhakar Raghavan. Introduction to information retrieval, volume 39. Cambridge University Press Cambridge, 2008
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Ad- vances in Neural Information Processing Systems, 31, 2018.
Ananda Theertha Suresh, X Yu Felix, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In International conference on machine learning, pp. 3329 3329-3337. PMLR, 2017.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, al. Huggingface's transformers: State-of-the the-trttt-rtttt natural language processing. arXiv preprint 1r01v:1910.03771, 2019.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoe V Le.
XInet: Generalized autoregressive pretraining for language understanding. Advances neural information processing systems, 32, 2019.
Fang Yao, Hans- Georg Müller, and Jane-Ling Wang. Functional data analysis for sparse longitudinal data. Journal of the American statistical association, 100(470):577-590, 2005a.
Fang Yao, Hans-Georg Müller, and Jane-Ling Wang. Functional data analysis for sparse longitudinal data. Journal of the American statistical association, 577-500) 2005b.
A DECOMPOSITION
For estimation in FIXED-SPARSIFICTTION method, define the design matrix for B-spline regres- sion as
B = (B1/d), T(d/d))- (1/d
B1,+o-((/d))
(d/d) Bj.-p.(d//a)
11

---

Under review as a conference paper at ICLR 2023
Denote by V n. the empirical inner product matrix of B-spline basis (t)p((t) i.e.
V n. {BBe Be pe. det B
Denote x; (z,(1/d), ................................ ..........dd =dddd)) T m
..... m((//))...,.((( and Z; The form of model (I) ensures that spline estimator (.).) allows rep- resentation (4(1)) = BB. V m B BB= x; = rm(-) 2.(-), where
B m, m(+) BB)) V n.p
2,(-) = (-) V B T Z
B PROOF OF THEOREM
According to the definition of & and G, the MSE can be computed as
d
B|G G1 = Σ E
1
(hy hy) (bap - h2y)
(ats - m2) (arg my 112
J
==
1=1
==1
Now, as
J. his)
= zij and (fhi))) = Tig' it holds that
2
E
(haz hT) (hegr - -hy) (21) my) (De - -my.)
Jz
1
n
d
2 (hey - hT) (hey - hhy))) E ((I1)) m,) (3ez my ))²
2
E
n
J&
where hy stands for the j-th element of the d-dimensional vector h. Since hij = Iig with probability J./d and hij = 0 with probability 1 - J_/d, therefore
2 (hag - hT) (hay - -hy) = J/] -12) Jg
E
E ((hig - h,) (hey - h)
EE ((rig m,) (rag m. ))
Since elements in each vector are assumed to be generated independently for RANDOM- SPARSIFICATION, that Tag is independence of Tiy, 1 S i S n, j Hence,
(
d
2
d
E G - G|
E ((x:) m,) (xag - m ))²
n
J/
d 2 J/
E
Σ (xns m, Σ
(zig - m,.)² 3'=1
n
d 2
Ri
n
Ju
where Ri = E | - ml
Moreover, according to Assumption 6,
n-
-1
x d-
-0 0.
ddCC
The bounded R3 further tells that
(n and consequently || = Oppnn112)
12

---

Under review as a conference paper at ICLR 2023
C PROOF OF PROPOSITION 1
The trick is to introduce the random variable Eúg to aid in the computation of conditional expectations M,,2 (t). Let Eij be an indicator random variable which takes value in (0, 1}. depending on whether his = maj or not for I S n, S j S d, lead- ing to 21 (+) = = (-), EM, M, (+) = I9 =. (+), 1M ()) =. (*). Event {Ei E,y = 1} happens with prob-
ability (24) event {Ess = 0, Ety 1} happens with probability (4) (1 - ) and event
{Sig = 0, Ety' = 0} happens with probability (1 - 2
Case 1: With probability (1 ) event {Ei 0, Eip' = 0} holds, which implies haj 0 and
buy 0. Therefore,
B2 (his R.j) (higs - 11y)
)
E EM, Mylss 0.
T ((,,) T ((Mg))
3 (hij hgg) =EM, K0
B (hig - 11p) T (M,r)
) O.
18 My =0
T (M,)
Case 2: With probability (1) 2 event {Ets 0,6 1} holds, which implies ha
and hig = Tzy. Still we have
g2 (hij - h1) (has hg)) 0. T ((M)) T (M,)
Myy
Case 3: With probability (2))² Tays. Therefore,
event (Ei event 1, 1} holds, which implies his 2iy and hep
B (hij - Ríj) (higr - hT) (M,) T (Mz'
32 (hij - hT) (hay - hgg) T [M,) (M,
1
=3² (aij my) (xay my)) EM, M,M,,,,,,,,,.MM
T(M,)T(M))
crucial observation is that Eı only implies M, 2 1 and does not give any other information about My. Taking expectation with respect to Eıý we have,
3a (hij - hT) (hag -hz. T(M,) (M²)
Eg,, BM,, (J
d -(12)
B (zij m,) (Iag my MMM (T(M
(M,))
(xij my) (Deg² my))
This proves Proposition] 1
13

---

Under review as a conference paper at ICLR 2023
PROOF OF THEOREM 2 D
According to the definition, the (i. element of (SATT
EM,IMM21
-11 T(M,) EM,, 1M,
GSTAT
1
1/dd d
T(M
(hij - h2) (hey hy)
71 J&
T (M,) (My
1
32
(hus h2) (hey - Feyr)
T (M,) T (M²)
MSE can computed as
B|G
- GG12=
Σ
E
GGSNNT Gzfr) )²
5.'=1
2
Σ if'=1
E
Σ (hej 1ai--hh hs) (hey hy)
1 Σ
(an m2) (x1g mp))
n (M)
n 1=1
(5)
As the estimator is designed to be unbiased, i.e.,
B2
E
(hes - hT) (hey - hy.)
Σ (xyj - m - my))
T (M
it holds that
B2 n (M T (M²)
(Eis - m.j) (xeg' - -myy) )
2
E
Σ (hij - h1)) (his' hgg)
Σ
2
1
32
n
x
E
(his hj) (hig - -,r)
Σ
(zij m3) (34gs mm.')
n
T(M
n1
(6)
We now analyze the first term above.
32
E
Σ
(hej - h1) (hig - -hy))
T(M,) (My) 1=1
(hij - Tiy) (hes' - Fny))
T(M,)² (TM,))T((N))))) (M
1=1
(his - hs) (hus - hT) (hay - - (hay - hg) -Ry)) Rby))
2
T
T T (M²)²
1=1 k=1+1
Note that the expectation is taken over the randomness in hij as well as T TM2)). Further, ga TM,,)) is non-zero only when a node i samples coordinate j and j', i.e., his = xy and by Tag. This implies that Mj 2 1 and My 1. Therefore, by the law of total expectation,
14

---

Under review as a conference paper at ICLR 2023
have
(his - hn)² (higs hgg)) 2
B'
T (M,) T (M,
Jo (mis m2)² dT (M,)) 2
Jss [mly - mmr)p {
= -3'EMiMM22 M
Em EMyIMM,21
(d dT (Mg))
34 Σ
Ju
J.
n (x=1) n --1]
r' - 1)
Jg rtr'-2 (1
(1-d)
d
Jg
2n 2n-r-r²
(r)2 dr')2
d
r,r==1
x (Iaj m,)² (Iag m.) )
d Jg
+a (miy - m (xay' my))
(8)
where 01 is defined in Theorem
Following similar argument as above, note that (Au-hh (nas k2) (R: (R hzr))
is non-zero
(( (DM,
only when nodes i and & sample coordinate j and j'. i.e., his = Tij. Maj Tkjs by = Ray. hay = Iky. This implies that M, and My 2 2. Therefore, by the law of total expectation, have
(hig h2) (bes) hT) (hegs hy) (heg hy)
T (M,)² T (M₃y)²
Jo (2igg m2) (ækj mm)) df (M,)
Ja (srag -myy) (xak) mg.) dT (My)
=3 -51BM,1M,22
EM,,MMy22
3 n
J.
J2 n (n-2) 2)
(m
(n 2
J2
r+r'-4 -4
(
J
2n 2n-
1
(r- 2 x (maj m,) (Ikj m,) (Iag' my)) (Ikz)' my))
dT (r')² deT (ri)²
r' 2
d2
nr==2
= (1 c² (m:j m,) ) (يو m,) (xig my) (Iaky' myj'
where C2 is defined in Theorem Substituting S and 9 into
we get
B2
E
(his h1) (ley - hyy)
((M,)
T
(M,)
d
2
+
(Iig m, (IISz' - m2
J
+
(xi my) (Irk) m,) (xaz my) (INz my)
(10)
Now, substituting (10) into (
we get
(aag m,) (x1gg myy )² 2
E
1
Ba
(hij h2) (hey - hT)) 1
Σ i=1
n
TM,,) T (M,)
1
((#
d
Js
+ c1 -
(xig my)² (arig' mz
+ n
(1- (1))))² 1)
Σ
(Iez - my) (oxs m,) (Zeg my (2kg' - my.) (11)
k=i+1
15

---

Under review as a conference paper at ICLR 2023
Finally substituting 11 into
5 get,
(1, t (1,ta)
1 (1-c22²
E SPAT G1I² n²
-1 -
R1 + n²a
c2) -1) Ra
J
where R - Ei=1 | - ml
and R2 = 2 Σ Ek=iti (Los- - m)² (2x - m))²)
Moreover, according to Assumption 6 and the boundness of C1.
) -1 d
2
n-' +
(rCaa) + dd
(d'Caa -
The bounded R1 further tells that n-2 +0))
- RI =((=1)). The bounded 0g and R2
assure that - ((1 (1- (1-c2)²--1 R2 = O(n-)). Therefore, B||GSPAT - G112 O(n 12) and thus
||&SSaTT G|| = (1)111)))
E PROOF OF THEOREM 3
Note that 61 and are completely determined by the original data, while R2 and R2 are depen-
dent on function T(.). Observing the result in Theorem 2 the only term that depends on T(-) is
(4 + c1) R1 + (1 - c2)²
(1- R2 since these terms contain and c2, which are computed from T (-).
Thus to find the function (-) that minimizes the MSE, we just need to minimize this term.
From the definitions of 01 and c2 in Theorem
2
obtain the following expression for T (-)
(r) = arg min T
.04 Σ dT
n1
Jg
r r- (r)2
d
d
R2 3
J²
n 2)
Jg
r-2
(1
J. 21-
(12)
Ri
r d2T
2
d
r=2
1/2
We claim that T (r)
Ro 1+
an optimal solution for our objective defined in
12
To see this, consider the following cases,
Case 1: p or p 1. In this case ei and 0o are independent of T(-) and hence our objective does not depend on the choice of T(-).
Case 2: 0 p 1, we define
W T Aw
w arg min
(13)
bb w
where w is a n-dimensional vector whose r-th entry is w, 1/T(r)?, b is a vector whose r-th entry is
by = n
2 (( (1-p)- p)-
where p = L, and A is a diagonal matrix whose r-th diagonal entry is
Apr
(m-
n
1
p
(1 p)--rr
2
Ri
p n 2)
r p² p== -))-
2
Ri
1 Rg r--1 1) Ri 12
br
16

---

Under review as a conference paper at ICLR 2023
Note that Ayr 0 for all r (1.2....,,) which implies that A 1/2w is one-to-one mapping. Therefore setting A A the objective in (13) reduces to
|
z" = arg min
(14)
(bTA-1/22)
x
Observe that the objectives 13 and 14 are invariant to the scale of T(.), w and z respectively and thus the solutions will be unique up scaling factor. Therefore, in the case of [14] it sufficient to solve the reduced objective,
||2|22
z arg min
= arg min a.|/a||=1
2,||>||=1 (b" A -
(b A 11/22)
which is minimized by z²
1/ 1/2b
Therefore, the optimal solution (up to constant) is w"
A -1/22 (A -1/bb) Correspondingly, we conclude that 1/2
Arr br
1/2
R2
2
1/2
T (r) (r)
(w,)-1/2
1/2
1
Ri
n
minimizes
12 and consequently minimizes the MSE of the RK-SPAT estimator.
F PROOF OF THEOREM 4
PROOF OF (I) We first provide several technical lemmas.
Lemma 1, Let W; ~ (0,o7), o, > 0, i (1,2,...,n)) then n 2, a > 2,
F
WW/o;1| logn Isi5n
max
2
2-a²/2
Hence, (maxişiso [W))/ (maxisisa 0.) maxisisn [W//o Oa.o. (vlogn).
PROOF. Note that for > 2, 2,
W
W
P
max Isisn
av logn
P
an logn
i=1
paa log avlogn
2 - 1-02/2
22n - (lala(aalgn) < 2n
<
2nm(aa (logaaa/oonn))
where (xx) denotes standard probability density function at x and ((x) denotes the corresponding cumulative distribution function. Jemma[[ooloons by applying Borel-Cantelli lemma.
Lemma 2. As n + DO, we have
max ||, zillo -O.s. (J (nlogn)2/no) Oa.s. nn- (n-1/2) I8PSn
PROOF. The trajectory (1) can be written xz(1)) m(l) + Ex (1) Denote Φb (dv(1/d),.... ox(d/d)) and let dx(() = ( oh be B-spline smoothing of du (1). The linearity of spline smoothing implies that
ha (1) x.(()= = m((t) m() + Σ Eik (c(()) -x)0)))x(())) (x(
A=1
Lemma A.4 in Cao et al.
2012) assures there exists constant Cg > 0, such that
lll ml x < Co
(15)
(ex Φ1 < Cau I1 Jop', k 121
(16)
17

---

Under review as a conference paper at ICLR 2023
Thus, with norm inequality, have
|44 zilloo 1im mills + Σ Kial
Óx - oxl100
-oxx--xl.. S CQo
where W; |mlll... Σi=1 Kaak 1 are i.i.d. nonnegative random variables. W has finite absolute moment and we have
EW
P
max Isia
W, >
(n n) n/2
S
EW," (n 1)
1)g
which implies
max W; > (n (nlogn)22/ng Sish
S EW
Σ (nl n) < t00
According to Borel Cantelli lemma, we conclude that maxigisn We = On... (ng log 12/r0 which together with [15) and (16). prove the result
max ||, zilloc = Oa... {Jo" (nlogn)2/v) 2/ro I5i5n
Moreover, Assumption 6 assures that n J/ (n log n) 2/ro = 1/2 (1 Cd) (d log 2// ) = -22--00" fr0 (log d) + 0 (17)
Therefore, maxisiga ||/4 - - = Ca.s. (1-1/2). According to the definition of m(-) and m(-), m ml-) can be decomposed as m(.) m(--) n Dim (h₂(-) xz(-)) Lemma further tells that
sup n 1/2 1E(0..]
n222((((t) (n())= m(t) S n 1/2
max
h -2,lloo = Oas. (1).
IsiSn
Hence, ||m - mi/10 = Oa.s. 112 3) is proved where mn is a BS estimator.
Denote by (-)-) h₂(-) m(-) and Z.(-) xz(-) m)(-), we further obtain the following lemmas.
Lemma 3. Asn n
2: Zi
Oax. {J²" (nlog n) 1
max SSisn
20
PROOF. Denote dx(2) dt 'B()) TV-11 B ØR and 2,(t) Eie En for k N+,
2,(t) - Zz(t)) = Σ Eak (x((t) -ox(t)
From (66 and Assumption 5, - Σ --
Eaal 5. 22 s <W.,," where W,
Σ 00
1== Ezk ||ox "g i.i.d nonnegative random variables with finite absolute moment. Then
EW (n log n)²
P
max S
W₁ (n (n 2/r0
EW (logn))
thus,
PP
max W; > (n (nlogn)2//o) ISiS
EW Σ n=1
-1 (log (0ogn))200 +00,
R=1
so Lemma tells maxigisa O2s ((1logn)2/m) Lemma is then obtained.
18

---

Under review as a conference paper at ICLR 2023
Next compute the convergence rate of BS covariance estimators. For any t,t' [0,1], decompose G (t, G (t, into three parts
((41))G((,))) =n ((1)):(()) n 7(1)Z((1)
1=1
Σ (2((1) 2((0) (2 (t' (2)(1)
2x(1)) + +n
Σ 1=1
24 (t)) (2:(t) 2,(0))
=
n
+ n
Σ (t) (2s (t) (1)
(18)
According to decomposition of { [ and {-: that is (t( Zi(t) + m(() and x;(t)
Z,(t) + m(t), we get (t) (t) (t) (t) + mn() m(t). Noting that m(t)
n Er and m(t) =n EE== Zz (t), then 2,(t) (t) can be represented by
(xx(())-(()) -m(t)) - n Σ (z:(1) m(t)) }
2,(t) - Z,(0) = h₂(t) - m(t)
= h((t) - -n -1 Σ
hy (t) - {z((t) -n Σ x (t)
#=1
P=1
= h4((t) - 21(1) n- Σ
(t) - (t))
P=1
Therefore, we obtain that 21(1) (1) = 2,(1) Z((1) n -' (2x(t) Zo(()) Hence,
(2(11 - (2(0) (2((1)-24))
1=1
11
Σ (2((1) - 2 (Z. (t') ze (t))
(2((1) -2(()) n n E -)))))2(()) - -n- Σ i=1
=n
1=1
1=1
According to Lemma]
it is easy to obtain that
n
(z((t) s
Zi(t))
max S
2. Zi| zil10- -as. {J²² (n (nlogn)2/10) {n."(nlogn) } Ou.. (n-1/2)
where the last equation holds for 17 And
2i(1) - z.(()) (2. (1') - (t')-(((())
7
1=1
1/4 2, 12) 2
Ons. {Ir20 (n log 1)g
Oa.s. (1-1/2)
max ISiS
where the last equation follows from Assumption 6, d + cc.
n --
22 (n logon)//m x 12 Ca) 22" (d log ) 1/10 = 2/2-270' 2400 Ollog d) - 0
Hence,
2,(10 Z,(1) (2,(0) (())) =0a.. (1-1/2)
sup [0.1)
(19)
i=1
19

---

Under review as a conference paper at ICLR 2023
Moreover,
Zi (t) (2(()) -z((1)
i=1
Z4 (1') -n
Zo (1')
7,(1) -2(())
Z((1) n Σ (2+(1) ((4(()) -x(11)
Z (t) (2((1) -2((1))
2
Σ
Zi (t') Σ (2-(1) 2z (2))))=2+(0)))
(20)
1=1
1=1
8'=1
Noting that |11 1 -i=1 Zilloo O,1
since E
1 n
-i=1 Zi (1)
-=
| loc B|Ea| oo
where E. = 1 Li=1 Sik. Then we have
Σ (z:(() Zi 20) -xx)))xx(()))
n
Ze (1))
3
max isp'sh
2x Zi
11
Zi
=
=Op
1121
n
im
1=1
i=
Ze (t)) (2((1) - 2((1)
n
-
max IsiEn
2: Z:
Z
Op
1n-122
(21)
1=1
1=1
00
Substituting 21 into (20). we conclude that
a 2, (t') (2((0)=2((0) =0p (n-1112)
sup [0.1
n
(22)
Similarly, we have
Zi(t) 2. (t') (t)- =0p =0p(1" (1-1/2)
sup 1.
(23)
Substituting 19).
(22) and (23) into (18), we have supr,re((..1) (t, G (t, - op (n-1/2).
Then || Gl op (n 1/2) is proved where & BS estimator.
PROOF OF (II) Next we prove the conclusion of BS- SPATIAL mean and covariance estimators. The estimation error of spatial mean can be computed as
3
SPAT mllec
max I5JEd
hig
Tzj
T' (M,)
1=1
3
B
3
max n ISi$d
hij
Σ Dij +
Σ Fij
F'j
T (M,)
T (M,)
T (M,)
im
B
|lm ml
+
1
|| 1.0
T (M,)
((1,))
=0p n 1/2)
where the last equality holds by noticing that T(M,) +p 1 from the law of large numbers and from Theorem 4 (i) Iivv milcc Da.s. (n- (n21),,, in is BS mean estimator.
20

---

Under review as a conference paper at ICLR 2023
The estimation error of spatial covariance can be computed as
||GSPAT - -ol120
"3 G555
max 15is''d
1
B²
(Pig - h2)) (heyy - -hy,
(Eiz -my) (Fig - mar)
max ISJJ''S
(M,)) T (M₂))
i=1
1
B²
(les - h1)) (heys - -hy)) T (M,) T (Myi)
3
Σ
(Feg m3)) (ares m,))
max
1SSJ''Sd
((M)) T (M₃i)
1=1
+ max n 1SJ
1
B2
(xis m,) (2ie) - -m.))
Σ
(xij -m;) (2ig' my
T(
g2
|000
-G3y ///||
(TM))T -1) |
B
$ max
1skd' Sd T (M,) (M,,)
ISiJ'dd
max
so, (1)
G (1)
(1-1/2) |
+ +0p
=0p n 1/2
where the last equality holds by noticing that T(M;YT(M, ->p 1 from the law of large numbers and
ga
G G = oo (n -1/2), G is BS covariance estimator.
from Theorem 4 (i)
G PROOF OF THEOREM 5
PROOF OF (1) The proposed RK and RK-SPAT covariance estimators follows | G
(n/21 and the proposed BS and BS-SPAT covariance estimators follows G G
(n(2-1/2) Consequently, the result G G = Op(n 112) holds for all four estimators. More-
over, is easy obtain that ||ā G Op (n-11/1)))))) where G is the true covariance estimator which is usually unknown in application. In sum,
G G s | G + ||c - G0I=0 1/2))
It is worth noticing that although although the BS and BS-SPAT estimators enjoys smaller conver- gence rate, ||ā G| still converge at the rate of Op 112) since ||G G|l is the dominant term.
Denote An) = f(G G) (1, the (L') di' Based on the result that || G|l Op (n-1/2),
have | Op (n 1/2) for any to Z 1. Let
1/2 ||ه|| / (((,)))(((1)) dedt'
=Op (n- (1-1
then according to Hall et al. 2006), we have
V/ the
(Au - (Ax-),) (DuR, 15) (,)
It follows from Bessel's inequality that
4/x C (1/ 0 =0, (n-1/2)
| w/n On (n-1/2)
Hence, we obtain that
PROOF OF (II) By (2.9) in Hall et al. (006)) and || G Op (n-1/2), we obtain that
d A : // (o (G-CC G) (1, th (t) vh (t') dtdt' 0 (1)0)112) Opp (n 1/2
21

---

Under review as a conference paper at ICLR 2023
Hence, Axx- Ax = Op (n 1/2) is proved.
PROOF OF (III) According to ʃ {ar (1) m (1)) du (1) dr AuSiee we have
Lik = A/4 1/2 / { (t) - m (t)) the (t) dr.
Similarly, Eo = 2/11/ J (h, (t) - m (t)} th (t) dt.
For S Sis n, Eik fix can be divided into two parts Eix - Eix = RR + R2 where
R1 = 2x 1/1 / (he (1) - m (1) Sh (1) dt 2/=1/2 // / (x; (1) - m (1) the (1) di
R2 Sx 1-1 / (xx (t) m (t)} Sh (t) dr Xx 1/ / [x1 (t) m (t)) the (t) dt
We assume that for & E N, X > 0, Au > 0. Moreover, according to the fact that || - xz
Op (n 1/2).
|0 - 2/ = Op (n (12) and
|Im ml| s 1l mml + |lm- mll =Op (n (n-1/2).
obtain
R1 -x-1//2 { (hr (t) m (t)} { th (t) - ux (0) dt + 2/66 // / (he (t) m (t)) vh (t) dt
% 1/2 / {xz (t) m (t) vu (t)
-// / (1i(()) - (1)) ou (t) u/4 (1) dt
+ 1/2 / [hr (t) - mm - x; (t) + m (t)} thu (t) dt
<x=²1 1/2 ||0 - -mll | - //x + 2/2 (11 will + - mil) Welll
=Op nn (1-1/2)
Through first order Taylor expansion of Åe at Au. it is easy to obtain that \ = =x (1/2)
3/2
Ax
3/2
Ao) + o [ Aul) Hence, |he Au = On (1- ensures that
1/6
1/2
A/4
1/22
Op 2p (n-1/2), Consequently,
R₂ (x=1/2- >xx /)) / {xz (t) m (t)) th (t) dt
< \ 1/2 - X5 ||a;-mi) - ||xx |l = Opp (n-1/2)
where ||x;--))
102--m] ml| = (1). Therefore,
Eik
max (|) + [|22l) = Oo (1-112). Isisa
max 1Si5n
Eib
H MORE NUMERICAL STUDY
To visualize covariance function of functional data generated from model 44 in simulation study, Figure A shows the true covariance function, the sample averaged covariance estimator using orig- inal data without sparsification, and four proposed covariance estimator generated from sparsified vectors. The deviation of RK and RK-SPAT estimators is large the diagonal t l' and the smoothness of the surfaces are poor. The accuracy of BS estimator is significantly improved, with only slight deviation at the boundary points. On the basis of RK estimator, RK-SPAT estimator further considers the spatial factor, such that the estimation accuracy of boundary points is improved but the smoothness of the surface is sacrificed some extent.
22

---

Under review as a conference paper at ICLR 2023
0.2
0.4
02
02
(a) G (t, t')
(b) G (t, t')
0.6
0.8
(c) Random-knot G (t,)')
(d) handom-knots.o Spauttl G (t,
04
0.4
62
0.4
(c) B-spline G (t, t')
(f) Bspline-Spatial & (f. t')
Figure 4: Plots of covariance, averaged covariance and four different covariance estimators.
23


Reviews:
[{"review_id": "_RP22Cu88g", "reviewer": "Reviewer_orUQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors try to estimate the covariance function of sparsified functional data for dimension reduction. They propose four sparsification schemes and give the corresponding nonparametric estimation of the covariance function. The covariance estimators are asymptotically equivalent to the sample covariance computed directly from the original data. Moreover, the estimated functional principal components effectively approximate the infeasible principal components under regularity conditions. ", "summary_of_the_review": "In this paper, the authors try to estimate the covariance function of sparsified functional data for dimension reduction. They propose four sparsification schemes and give the corresponding nonparametric estimation of the covariance function. The covariance estimators are asymptotically equivalent to the sample covariance computed directly from the original data. I think it is not a good idea to transmit the original data or preprocessed data if the partner just needs the principal components. In summary, I do not think it is a good paper.", "strength_and_weaknesses": "Strength: The sparsified data costs less for transmission. The construction is simple such that the sparsified data has the similar covariance matrix get by the original data.\nWeakness: The computation of covariance matrix for the sparsified data has the same (even more) complexity as that of the original data, since the mean vector (h bar) may be dense with very high probability.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JK5LBAd4os", "reviewer": "Reviewer_Dxm2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes two classes of sparsification schemes for densely observed functional data with potential spatial correlations. The first class of schemes is random sparsification methods that extend the work of [1] from mean estimation to covariance estimation and the second class involves B-spline interpolation of the original data. Both classes achieve the desired convergence rates as by the originally observed functional data. \n\nReference:\n\n[1] Jhunjhunwala, Divyansh, Ankur Mallick, Advait Gadhikar, Swanand Kadhe, and Gauri Joshi. \"Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation.\" Advances in Neural Information Processing Systems 34 (2021): 14280-14292.", "summary_of_the_review": "I think the paper is well written, but in my opinion, the contributions are incremental at best.\n\n", "strength_and_weaknesses": "Strength: the paper is overall well written and the presentation is clear.\nWeakness: the overall novelty of the proposed method is limited and the applicability of the B-spline-based methods may be restrictive.\n\n1. The ideas of random sparsification and random-spatial sparsification follow rather closely to those in [1], except that [1] focuses on estimating the mean vector of the sparsified vectors. The extension to the covariance function estimation is straightforward and less innovative. If there are any nontrivial challenges in the theoretical investigations, please clarify.\n\n2. The ideas of B-spline interpolation rely heavily on the assumption that the observed random trajectories are smooth functions. But in practice, it is commonly the case that these trajectories are contaminated with measurement errors. I am not sure whether the proposed theory can be modified to address this issue, which will be of more practical interest. I don't think this will be an issue for the random sparsifications scheme, but not sure about the B-spline interpretations.\n\n3. I found some of the assumptions are not so standard. For example, (1) in Assumption 2, why would you need to assume $\\min_{t}G(t,t')>0$, which seems to be a strange condition? (2) In Assumption 3,  it is also strange to assume the decaying rate of the eigenvalues depends on the sample size $n$.  The decaying rate is usually only assumed to change with $k$. (3) In Assumption 5, I am confused by the wording \"the number of distinct distributions...is finite\". Please clarify the definition. \n\n4. I am also not so sure about some of the theoretical results regarding the convergence rate. (1) In Theorem 4, why the convergence rate for the first mean function is almost sure convergence while all other threes are convergence in probability? (2) The convergence rate in Theorem 5 appears to be faster than the existing convergence rate in the literature. For example, in Corollary 3.7 of [2], the convergence rates of these quantities are proved to be of the order $O_p(\\sqrt{\\log(n)/n})$, slower than those in Theorem 5. Please double-check.\n\nReference:\n\n[1] Jhunjhunwala, Divyansh, Ankur Mallick, Advait Gadhikar, Swanand Kadhe, and Gauri Joshi. \"Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation.\" Advances in Neural Information Processing Systems 34 (2021): 14280-14292.\n\n[2] Li, Yehua, and Tailen Hsing. \"Uniform convergence rates for nonparametric regression and principal component analysis in functional/longitudinal data.\" The Annals of Statistics 38.6 (2010): 3321-3351.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "83IqihuAhP", "reviewer": "Reviewer_BUn8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of estimating the covariance function for a random process. The random process functional data is sampled on a finite set of knots. Four algorithms are proposed, namely, RANDOM-KNOTS, RANDOM-KNOTS-SPATIAL, B-SPLINE, and B-SPLINE-SPATIAL. These four algorithms are proposed with the main motivation of reducing computational complexity. The first two algorithms achieve this target by reducing the sampling rate, and the last two algorithms achieve this target by using B-spline interpolation. Convergence analysis of the estimated covariance function to the true covariance function is provided. Convergence of the eigensystem is also derived.", "summary_of_the_review": "The results are new, to my best knowledge, and deserve a publication. However, some proofs are wrong, so I can not recommend a publication of this paper in its current form. I would consider to recommend a higher score after these problems have been resolved (without compromising the significance of the main results), and no more big mathematical mistake is found.", "strength_and_weaknesses": "Strength:\ncomprehensive numerical test; theoretical results on convergence.\n\nWeaknesses: Some typos do not belong to weaknesses, and are listed below simply because we do not find a better place to input. Below we also list some mathematical mistakes.\n1. Line 5 of page 3, the notations \"O\" and \"o\" should be defined.\n2. Assumption 2: for minimum value G(t,t') should be G(t,t).\n3. Is \"Figure 2.2\" the one at the top of page 6? I feel that this figure adds confusion. Here is the reason. According to the beginning of Section 2.1, the coordinates of vectors are set to zero randomly, and for Figure 2.2(a), with probability 1-(3/6)=0.5. With such a probability and a dense vector of dim=6, we may get a sparse vector with 3 zeros, 2 zeros, 4 zeros, etc. In Figure 2.2(a), all the three dim=6 vectors are sparsified to vectors with 3 zeros. I feel uncertain about whether each element of a vector is set to zero independently, or we are just randomly select 50% of the coordinates and then set them to zero in a batch.\n4. How is the norm ||G-hat - G-bar|| defined in Theorem 1?\n5. At the end of page 5, it seems to me that the least square regression with B-splines would lead to interpolation. Is that true?\n6. This paper proposes two families of covariance estimators, and according to Remark 2, the B-spline-based approach outperforms the random-knots family. Given such a claim, what is the reason for introducing RANDOM-KNOTS and RANDOM-KNOTS-SPATIAL?\n7. Line 2 of page 12, please define the inner product <.,.>_d.\n8. The first equation in Appendix B: the norm ||.|| is applied to a scalar, and should be changed to absolute value |.|.\n9. The second centered equation in Appendix B could be wrong if j=j'. Please provide treatment for this case.\n10. For the second centered equation in Appendix B, since we have the term \\bar{h}_j which contains h_{1j}, ..., h_{nj}, and they are transformed from x_{1j}, ..., x_{nj} independently as demonstrated in Figure 2.2(a), this centered equation is wrong even if j is not equal to j'.\n11. Line 4 of Appendix C, obviously xi_{ij}=1 and M_j>= 1 are not equivalent. More details are necessary to prove why the two conditional expectations are equal. The claim that event {xi_ij=1 and xi_ij'=1} happens with probability (Js/d)^2 is wrong when j=j'; this mistake may spoil the whole proof.\n12. The proof of Theorem 2 is wrong because the case j=j' is not considered.\n13. In the proof of Theorem 3, we note that the case p=1 is discussed. This causes 0^0 to show up in Theorem 2. Please define the value of 0^0 in such case.\n14. In the proof of Theorem 3, what is the relation between (12) and (13)? In particular, if one expands the target function in (12) as a quadratic function of 1/T(r)^2, then the off-diagonal entry is in general not zero. So we believe that the proof of Theorem 3 is wrong.\n15. Lines 5 & 7 on page 18: there is a factor \"n\" missing (but this is just a typo easy to fix). Besides this, how to derive the finiteness of the r_0 moment of W_i from Assumption 5?\n16. At the bottom of page 20, as the convergence speed is not given for the second term, deriving the rate n^{-1/2} is not proper. At the end of this section there is another place with the same problem.\n17. The proof of Theorem 5 fails when G has duplicated eigenvalues, in which case the estimator for an eigenvector does not converge to the eigenvector in general. Also, in line -4 on page 21, how to guarantee that C is finite?\n18. On page 22, a new assumption on positive eigenvalues is added to the proof. Please also include this assumption in the theorem.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-ys48Znkmy", "reviewer": "Reviewer_DGgK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors consider the problem of covariance estimation for a 1D time series based on $n$ identically distributed (but possibly correlated) draws of length $d$.  The standard estimator would look at all the data, but the authors consider four sparsified versions of the estimator based on a sample of the entries of the different series.  Two of the estimators use random selection of the data (one taking into account correlation between the different draws), and two use samples at fixed locations and fill in intermediate values using B-splines (again, with one taking into account covariance between the draws).  The authors also state convergence theorems for the estimated covariance and its principle eigenvalues and eigenvectors.", "summary_of_the_review": "The paper is largely interesting for the theoretical results that it proves about the four proposed estimators.  The claimed efficiency improvements are never really demonstrated, and I found it hard to figure out what was going on in the one real application.  As a piece of mathematics, the results seem plausible and somewhat interesting, particularly in the version that incorporates both temporal and spatial correlations.  At the same time, the paper is so packed with theorems (proved in quite a long additional supplement) that it is not altogether easy to follow.", "strength_and_weaknesses": "The combination of using correlation among draws and using interpolation via B-splines is an interesting theoretical idea, and the theorems look like the types I would hope for (I have not checked the details).\n\nAt the same time, despite the claimed advantages in terms of computational efficiency, this seems to mostly offer theoretical contributions.  None of the experiments addressed the claimed computational efficiency -- all were about accuracy of the estimators.\n\nI had a hard time understanding what was happening with the application section, both in terms of the actual data to which the estimators were being combined and how that data was used.  It seems like the data was a sequence of embedding vectors; but how is it reasonable to model these as identically-distributed time series with smooth correlation?  And what happens afterward in the clustering?  It would be useful to provide a few more details.\n\nAlso, while accounting for the correlation across draws (or components or spatial locations, as the authors have it) definitely decreases the mean squared error in estimating the standard estimator using all the data, it is less clear that it decreases the mean squared error in the estimator as a whole.  The highly-correlated case is exactly the one in which the standard covariance estimates should be most noisy, I think?  It would again be useful to have a comment on this.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject