Introduction
Differential privacy (DP) provides a rigorous framework for protecting individual-level information while balancing data usability. By carefully calibrating the noise added to the released summaries, DP obscures the contribution of any particular individual. Since Dwork et al. [11 ] formalized DP, it has become a central paradigm in privacy-preserving data
© Haotian Chen, Yu-Wei Chen, Qifan Song and Jordan Awan.
License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. analysis, stimulating extensive research in statistics, machine learning, and related fields. Despite this progress, much of the classical DP literature has focused on database queries, finite-dimensional statistical summaries, and conventional machine-learning tasks [27 , 7 , 10 ] . Extending DP to more complex data objects raises additional theoretical and methodological challenges, particularly when the data exhibit infinite-dimensional structure and complex dependence over continuous domains.
These challenges are particularly relevant in functional data analysis (FDA), where the basic unit of interest is a function or curve, potentially infinite-dimensional, but typically observed only at finitely many discrete points. Classical examples include growth curves, wearable sensor data, and other densely or continuously recorded signals [26 , 22 , 1 ] . Instead of treating observations at different time points independently, FDA models each subject’s data as a smooth function, allowing statistical procedures to exploit the within-curve correlation and geometric structure inherent in functional observations. Over the past several decades, FDA has become an important area of modern statistics with applications across biology, medicine, engineering, and environmental science [13 , 15 ] .
As functional data become increasingly prevalent, protecting the privacy of function-valued information has become an important challenge. In many applications, the object of interest is itself a function—for example, a mean trajectory, a regression function, or an estimated individual curve—which may reveal sensitive information about individuals. While classical DP mechanisms are primarily designed for finite-dimensional statistics, extending privacy guarantees to infinite-dimensional function spaces is substantially more challenging, requiring both suitable notions of sensitivity and carefully constructed noise processes. These challenges naturally raise the question of how DP should be formulated and implemented for function-valued outputs. Previous work has built ( ϵ , δ ) (\epsilon, \delta) ( ϵ , δ ) [14 , 19 ] , while recent work extends this to the Gaussian differential privacy (GDP) framework under reproducing kernel Hilbert spaces (RKHS) [21 ] .
Another fundamental question arises regarding when and where privacy should be enforced, given privacy mechanisms for functional outputs are available. For a functional estimation problem, privacy can be incorporated in at least two natural ways. One may first smooth the functional trajectories and then privatize the resulting estimates, or alternatively privatize the data first and subsequently perform the estimation using the protected observations. We refer to these two strategies as Fit-Then-Protect (FTP) and Protect-Then-Fit (PTF), respectively. Although both procedures can be calibrated to have the same privacy guarantee, they exploit the functional structure of the data in fundamentally different ways, and little is known about when one ordering is superior.
Contributions: In this paper, we study how the ordering of privacy protection and functional estimation affects the statistical accuracy in functional mean estimation. We first establish a sufficient condition under which Gaussian perturbations of function-valued summaries in general Banach spaces satisfy a prescribed GDP guarantee, extending existing results beyond the RKHS setting. We then compare the FTP and PTF pipelines under a common GDP budget. When functional observations are measured without error, we prove that FTP achieves strictly smaller estimation error than PTF asymptotically as the sample size increases, in both finite-dimensional Hilbert spaces equipped with the norm induced by L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] μ \mu μ
Related Work: Previous work on differential privacy for function-valued objects has primarily focused on extending classical privacy mechanisms from finite-dimensional vectors to infinite-dimensional function spaces. Hall et al. [14 ] proposed one of the earliest Gaussian process perturbation mechanisms for releasing functional summaries while satisfying ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) [19 ] established a general theory of Gaussian perturbation mechanisms in Banach spaces and characterized sufficient conditions under which function-valued summaries satisfy ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) [23 ] and extended the exponential mechanism to functional summaries, including functional principal component analysis [3 ] . More recently, Räisä et al. [21 ] established GDP guarantees for a Gaussian-process-based functional mechanism in RKHS. Beyond general privacy mechanisms, Xue et al. [28 ] studied private distributed FDA and established minimax results for functional mean and varying-coefficient estimation.
Another line of research investigates the role of dependence and structural information in privacy mechanisms. Cao et al. [5 ] analyzed privacy leakage under temporal correlations in continuous data release, while other work has developed correlated-noise mechanisms to preserve time-series structure and mitigate vulnerabilities of independent perturbations [25 , 18 ] . More broadly, geometry-aware and structured mechanisms have been shown to achieve near-optimal or improved utility over conventional independent perturbations in finite-dimensional settings, including mechanisms for vector- and matrix-valued queries, private learning [20 , 6 , 2 , 8 ] .
Organization: The remainder of this paper is organized as follows. Section 2 reviews the necessary background on functional data analysis and differential privacy. Section 3 formulates the problem of differentially private functional mean estimation and introduces the Fit-Then-Protect (FTP) and Protect-Then-Fit (PTF) strategies. Section 4 establishes a Gaussian differential privacy mechanism for function-valued summaries and develops theoretical comparisons between the two strategies. Section 5 presents simulation studies evaluating their empirical performance under different function spaces in various settings. Section 6 concludes the paper with a discussion of potential extensions. Proofs, technical details, as well as supplementary simulation results are in the appendix. The source code used to implement the simulation study and data analysis is available at https://github.com/Hao-tian-Chen/DP-FDA .
Background
In this section, we review the necessary background for FDA and DP. In Section 2.1, we give the notation and definition for some common function spaces in FDA, such as Banach spaces and reproducing kernel Hilbert spaces (RKHS), define the Gaussian random element in a separable Banach space, and introduce the corresponding Cameron–Martin space and discuss its relationship with RKHS. In Section 2.2, we first define μ \mu μ μ \mu μ
Functional Data Analysis
Let ( B , ∥ ⋅ ∥ B ) (\mathbb{B}, \|\cdot\|_{\mathbb{B}}) ( B , ∥ ⋅ ∥ B ) σ \sigma σ l : B → R l:\mathbb{B}\to\mathbb{R} l : B → R continuous linear functional if it is bounded, that is, sup ∥ h ∥ B ≤ 1 ∣ l ( h ) ∣ < ∞ \sup_{\|h\|_{\mathbb{B}}\leq1}|l(h)|<\infty sup ∥ h ∥ B ≤ 1 ∣ l ( h ) ∣ < ∞ B \mathbb{B} B B ∗ \mathbb{B}^{*} B ∗ ∥ l ∥ B ∗ = sup ∥ h ∥ B ≤ 1 ∣ l ( h ) ∣ \|l\|_{\mathbb{B}^{*}}=\sup_{\|h\|_{\mathbb{B}}\leq1}|l(h)| ∥ l ∥ B ∗ = sup ∥ h ∥ B ≤ 1 ∣ l ( h ) ∣ B ∗ \mathbb{B}^{*} B ∗ [12 Proposition 1.29] .
A B \mathbb{B} B Z Z Z l ( Z ) l(Z) l ( Z ) l ∈ B ∗ l\in\mathbb{B}^{*} l ∈ B ∗ [17 ] . We write Z ∼ N B ( m , C ) Z\sim\mathcal{N}_{\mathbb{B}}(m,C) Z ∼ N B ( m , C ) m ∈ B m\in\mathbb{B} m ∈ B E [ l ( Z ) ] = l ( m ) \mathbb{E}[l(Z)]=l(m) E [ l ( Z )] = l ( m ) l ∈ B ∗ l\in\mathbb{B}^{*} l ∈ B ∗ C : B ∗ → B C:\mathbb{B}^{*}\to\mathbb{B} C : B ∗ → B
C l = E [ l ( Z − m ) ( Z − m ) ] , l ∈ B ∗ . Cl=\mathbb{E}[l(Z-m)(Z-m)],\qquad l\in\mathbb{B}^{*}. C l = E [ l ( Z − m ) ( Z − m )] , l ∈ B ∗ . A Gaussian random element Z Z Z m = 0 m=0 m = 0 Z ∼ N B ( 0 , C ) Z\sim\mathcal{N}_{\mathbb{B}}(0,C) Z ∼ N B ( 0 , C ) C l = E [ l ( Z ) Z ] Cl=\mathbb{E}[l(Z)Z] C l = E [ l ( Z ) Z ] l ∈ B ∗ l\in\mathbb{B}^{*} l ∈ B ∗
Cameron–Martin Space. Let Z ∼ N B ( 0 , C ) Z\sim\mathcal{N}_{\mathbb{B}}(0,C) Z ∼ N B ( 0 , C ) C ( B ∗ ) ⊂ B C(\mathbb{B}^{*})\subset\mathbb{B} C ( B ∗ ) ⊂ B
⟨ C l , C g ⟩ : = l ( C g ) = E [ l ( Z ) g ( Z ) ] , l , g ∈ B ∗ . \langle Cl,Cg\rangle:=l(Cg)=\mathbb{E}[l(Z)g(Z)],\qquad l,g\in\mathbb{B}^{*}. ⟨ C l , C g ⟩ := l ( C g ) = E [ l ( Z ) g ( Z )] , l , g ∈ B ∗ . The Cameron–Martin (CM) space H C \mathcal{H}_{C} H C C ( B ∗ ) C(\mathbb{B}^{*}) C ( B ∗ ) ∥ ⋅ ∥ H C \|\cdot\|_{\mathcal{H}_{C}} ∥ ⋅ ∥ H C B \mathbb{B} B Z + h Z+h Z + h Z Z Z h ∈ H C h\in\mathcal{H}_{C} h ∈ H C h ∉ H C h\notin\mathcal{H}_{C} h ∈ / H C B \mathbb{B} B [24 ] .
Example 1 (Finite-Dimensional Hilbert Space). Let ϕ 1 , … , ϕ m \phi_{1},\ldots,\phi_{m} ϕ 1 , … , ϕ m [ 0 , 1 ] [0,1] [ 0 , 1 ]
⟨ ϕ j , ϕ k ⟩ L 2 [ 0 , 1 ] = ∫ 0 1 ϕ j ( t ) ϕ k ( t ) d t = δ j k , δ j k = { 1 , j = k , 0 , j ≠ k . \langle\phi_{j},\phi_{k}\rangle_{L^{2}[0,1]}=\int_{0}^{1}\phi_{j}(t)\phi_{k}(t)\,\mathrm{d}t=\delta_{jk},\qquad
\delta_{jk}=
\begin{cases}
1, & j=k,\\
0, & j\ne k.
\end{cases} ⟨ ϕ j , ϕ k ⟩ L 2 [ 0 , 1 ] = ∫ 0 1 ϕ j ( t ) ϕ k ( t ) d t = δ j k , δ j k = { 1 , 0 , j = k , j = k . Define H m = span { ϕ 1 , … , ϕ m } \mathcal{H}_m = \operatorname{span}\{\phi_1,\ldots,\phi_m\} H m = span { ϕ 1 , … , ϕ m } L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] ϕ ( t ) = ( ϕ 1 ( t ) , … , ϕ m ( t ) ) T \phi(t) = (\phi_1(t),\ldots,\phi_m(t))^{\mathsf{T}} ϕ ( t ) = ( ϕ 1 ( t ) , … , ϕ m ( t ) ) T f ∈ H m f \in\mathcal{H}_m f ∈ H m f ( t ) = θ T ϕ ( t ) f(t) = \theta^{\mathsf{T}}\phi(t) f ( t ) = θ T ϕ ( t ) g ( t ) = η T ϕ ( t ) g(t) = \eta^{\mathsf{T}}\phi(t) g ( t ) = η T ϕ ( t ) ⟨ f , g ⟩ H m = θ T η \langle f,g\rangle_{\mathcal{H}_m} = \theta^{\mathsf{T}}\eta ⟨ f , g ⟩ H m = θ T η ∥ f ∥ H m = ∥ θ ∥ 2 \|f\|_{\mathcal{H}_m} = \|\theta\|_2 ∥ f ∥ H m = ∥ θ ∥ 2 B = H m \mathbb{B} = \mathcal{H}_m B = H m
Z m ( t ) = ∑ k = 1 m ξ k ϕ k ( t ) , ξ 1 , … , ξ m ∼ i i d N ( 0 , 1 ) . Z_m(t) = \sum_{k=1}^{m}\xi_k\phi_k(t), \qquad\xi_1,\ldots,\xi_m \mathrel{\overset{\mathrm{iid}}{\sim}} N(0,1). Z m ( t ) = k = 1 ∑ m ξ k ϕ k ( t ) , ξ 1 , … , ξ m ∼ iid N ( 0 , 1 ) . Its CM space is H m \mathcal{H}_m H m σ Z m \sigma Z_m σ Z m H m \mathcal{H}_m H m N ( 0 , σ 2 I m ) N(0,\sigma^2 I_m) N ( 0 , σ 2 I m ) C m C_m C m Z m Z_m Z m
Definition 1 (Reproducing Kernel Hilbert Space). Let T \mathcal{T} T K : T × T → R K:\mathcal{T}\times\mathcal{T}\to\mathbb{R} K : T × T → R K K K H K \mathcal{H}_K H K span { K ( t , ⋅ ) : t ∈ T } \operatorname{span}\{K(t,\cdot):t\in\mathcal{T}\} span { K ( t , ⋅ ) : t ∈ T }
⟨ ∑ j a j K ( s j , ⋅ ) , ∑ k b k K ( t k , ⋅ ) ⟩ H K = ∑ j , k a j b k K ( s j , t k ) , \left\langle\sum_j a_j K(s_j,\cdot),\sum_k b_k K(t_k,\cdot)\right\rangle_{\mathcal{H}_K} = \sum_{j,k} a_jb_kK(s_j,t_k), ⟨ j ∑ a j K ( s j , ⋅ ) , k ∑ b k K ( t k , ⋅ ) ⟩ H K = j , k ∑ a j b k K ( s j , t k ) , where zero-norm elements are identified.
The completion is naturally identified with a Hilbert space of functions on T \mathcal{T} T f ( t ) = ⟨ f , K ( t , ⋅ ) ⟩ H K f(t) = \langle f,K(t,\cdot)\rangle_{\mathcal{H}_K} f ( t ) = ⟨ f , K ( t , ⋅ ) ⟩ H K t ∈ T t\in\mathcal{T} t ∈ T ∣ f ( t ) ∣ ≤ ∥ f ∥ H K K ( t , t ) |f(t)| \le\|f\|_{\mathcal{H}_K}\sqrt{K(t,t)} ∣ f ( t ) ∣ ≤ ∥ f ∥ H K K ( t , t ) ∥ f ∥ H K ≤ B \|f\|_{\mathcal{H}_K} \le B ∥ f ∥ H K ≤ B ∣ f ( t ) ∣ ≤ B K ( t , t ) |f(t)| \le B\sqrt{K(t,t)} ∣ f ( t ) ∣ ≤ B K ( t , t )
Example 2 (RKHS and Gaussian Process). Let K K K [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 K K K Z K ∼ GP ( 0 , K ) Z_K \sim\operatorname{GP}(0,K) Z K ∼ GP ( 0 , K ) { Z K ( t ) : t ∈ [ 0 , 1 ] } \{Z_K(t):t\in[0,1]\} { Z K ( t ) : t ∈ [ 0 , 1 ]} t 1 , … , t T t_1,\ldots,t_T t 1 , … , t T ( Z K ( t 1 ) , … , Z K ( t T ) ) T ∼ N ( 0 , K T ) (Z_K(t_1),\ldots,Z_K(t_T))^{\mathsf{T}} \sim N(0,K_T) ( Z K ( t 1 ) , … , Z K ( t T ) ) T ∼ N ( 0 , K T ) K T = [ K ( t j , t k ) ] j , k = 1 T K_T = [K(t_j,t_k)]_{j,k=1}^{T} K T = [ K ( t j , t k ) ] j , k = 1 T E [ Z K ( s ) Z K ( t ) ] = K ( s , t ) \mathbb{E}[Z_K(s)Z_K(t)] = K(s,t) E [ Z K ( s ) Z K ( t )] = K ( s , t ) Z K Z_K Z K Z K Z_K Z K B = C [ 0 , 1 ] \mathbb{B} = C[0,1] B = C [ 0 , 1 ] ∥ f ∥ ∞ = sup t ∈ [ 0 , 1 ] ∣ f ( t ) ∣ \|f\|_\infty= \sup_{t\in[0,1]}|f(t)| ∥ f ∥ ∞ = sup t ∈ [ 0 , 1 ] ∣ f ( t ) ∣ σ \sigma σ H C K \mathcal{H}_{C_K} H C K Z K Z_K Z K H K \mathcal{H}_K H K K K K
Since K K K [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 H K \mathcal{H}_K H K C [ 0 , 1 ] C[0,1] C [ 0 , 1 ] C [ 0 , 1 ] C[0,1] C [ 0 , 1 ] H K \mathcal{H}_K H K K ( s , t ) = min { s , t } K(s,t) = \min\{s,t\} K ( s , t ) = min { s , t }
K ( s , t ) = exp { − ( s − t ) 2 2 ρ 2 } , ρ > 0 , s , t ∈ [ 0 , 1 ] . (1) K(s,t) = \exp\left\{-\frac{(s-t)^2}{2\rho^2}\right\},\quad\rho>0,\ s,t\in[0,1]. \tag*{(1)} K ( s , t ) = exp { − 2 ρ 2 ( s − t ) 2 } , ρ > 0 , s , t ∈ [ 0 , 1 ] . (1) The covariance operator C K C_K C K
Differential Privacy
Let a dataset X = ( x 1 , … , x n ) X = (x_1, \ldots, x_n) X = ( x 1 , … , x n ) n n n x i x_i x i X \mathcal{X} X X n \mathcal{X}^n X n X , X ′ ∈ X n X, X' \in\mathcal{X}^n X , X ′ ∈ X n X ∼ X ′ X \sim X' X ∼ X ′ Hamming distance d H ( X , X ′ ) = ∑ i = 1 n 1 { x i ≠ x i ′ } ≤ 1 d_H(X, X') = \sum_{i=1}^n \mathbf{1}\{x_i \ne x_i'\} \le1 d H ( X , X ′ ) = ∑ i = 1 n 1 { x i = x i ′ } ≤ 1 X X X X ′ X' X ′ mechanism M : X n → Y \mathcal{M} : \mathcal{X}^n \to\mathcal{Y} M : X n → Y X X X Y \mathcal{Y} Y
At a high level, differential privacy quantifies the difference between outputs of the mechanism when taking two adjacent data sets as inputs. We use the GDP framework throughout the paper, where the difference between distributions is measured through hypothesis testing. Let P P P Q Q Q M ( X ) \mathcal{M}(X) M ( X ) M ( X ′ ) \mathcal{M}(X') M ( X ′ ) H 0 : Y ∼ P H_0 : Y \sim P H 0 : Y ∼ P H 1 : Y ∼ Q H_1 : Y \sim Q H 1 : Y ∼ Q Y Y Y ψ : Y → [ 0 , 1 ] \psi: \mathcal{Y} \to[0, 1] ψ : Y → [ 0 , 1 ] α ψ = E P [ ψ ] \alpha_\psi= \mathbb{E}_P[\psi] α ψ = E P [ ψ ] β ψ = 1 − E Q [ ψ ] \beta_\psi= 1 - \mathbb{E}_Q[\psi] β ψ = 1 − E Q [ ψ ] P P P Q Q Q trade-off function T ( P , Q ) : [ 0 , 1 ] → [ 0 , 1 ] T(P, Q) : [0, 1] \to[0, 1] T ( P , Q ) : [ 0 , 1 ] → [ 0 , 1 ]
T ( P , Q ) ( α ) = inf ψ { β ψ : α ψ ≤ α } , T(P, Q)(\alpha) = \inf_{\psi}\{\beta_\psi: \alpha_\psi\le\alpha\}, T ( P , Q ) ( α ) = ψ inf { β ψ : α ψ ≤ α } , where the infimum is taken over all measurable rejection rules ψ \psi ψ [9 ] .
The trade-off function characterizes the minimal type II error as a function of the prescribed Type I error. A large trade-off function indicates that the two distributions P P P Q Q Q μ ≥ 0 \mu\ge0 μ ≥ 0 G μ = T ( N ( 0 , 1 ) , N ( μ , 1 ) ) G_\mu= T(\mathcal{N}(0, 1), \mathcal{N}(\mu, 1)) G μ = T ( N ( 0 , 1 ) , N ( μ , 1 )) Gaussian trade-off function between unit-variance Gaussian with mean difference μ \mu μ G μ G_\mu G μ G μ ( α ) = Φ ( Φ − 1 ( 1 − α ) − μ ) G_\mu(\alpha) = \Phi(\Phi^{-1}(1-\alpha)-\mu) G μ ( α ) = Φ ( Φ − 1 ( 1 − α ) − μ ) Φ \Phi Φ
Definition 2 (Gaussian Differential Privacy (GDP)), Dong et al., 2022. A mechanism M \mathcal{M} M μ \mu μ X ∼ X ′ ∈ X n X \sim X' \in\mathcal{X}^n X ∼ X ′ ∈ X n
T ( M ( X ) , M ( X ′ ) ) ≥ G μ . T(\mathcal{M}(X), \mathcal{M}(X')) \ge G_\mu. T ( M ( X ) , M ( X ′ )) ≥ G μ . Intuitively, if a mechanism M \mathcal{M} M μ \mu μ H 0 : Y ∼ M ( X ) H_0 : Y \sim\mathcal{M}(X) H 0 : Y ∼ M ( X ) H 1 : Y ∼ M ( X ′ ) H_1 : Y \sim\mathcal{M}(X') H 1 : Y ∼ M ( X ′ ) H 0 : Y ∼ N ( 0 , 1 ) H_0 : Y \sim\mathcal{N}(0, 1) H 0 : Y ∼ N ( 0 , 1 ) Y ∼ N ( μ , 1 ) Y \sim\mathcal{N}(\mu, 1) Y ∼ N ( μ , 1 ) μ \mu μ μ \mu μ
Definition 3 (Global Sensitivity in a Normed Space). Let ( B , ∥ ⋅ ∥ B ) (\mathcal{B}, \lVert\cdot\rVert_{\mathcal{B}}) ( B , ∥ ⋅ ∥ B ) S : X n → B S : \mathcal{X}^n \to\mathcal{B} S : X n → B X ∈ X n X \in\mathcal{X}^n X ∈ X n S S S ∥ ⋅ ∥ B \lVert\cdot\rVert_{\mathcal{B}} ∥ ⋅ ∥ B
Δ B ( S ) = sup X ∼ X ′ ∥ S ( X ) − S ( X ′ ) ∥ B . \Delta_{\mathcal{B}}(S) = \sup_{X \sim X'} \lVert S(X) - S(X') \rVert_{\mathcal{B}}. Δ B ( S ) = X ∼ X ′ sup ∥ S ( X ) − S ( X ′ ) ∥ B . The sensitivity measures the maximum change in the statistic in the norm of the output space when one individual’s data is modified. In finite-dimensional settings when B = R d \mathcal{B} = \mathbb{R}^{d} B = R d ℓ 1 \ell_{1} ℓ 1 ℓ 2 \ell_{2} ℓ 2 Δ 1 \Delta_{1} Δ 1 Δ 2 \Delta_{2} Δ 2
Definition 3 extends naturally to function-valued statistics taking values in a function space, while it may require that the statistic resides in some specific space (e.g., CM space) to satisfy the desired GDP property. In particular, we say a measurable summary S S S compatible with a centered Gaussian random element Z ∼ N B ( 0 , C ) Z \sim\mathcal{N}_{\mathcal{B}}(0,C) Z ∼ N B ( 0 , C ) S ( X ) ∈ H C S(X) \in\mathcal{H}_{C} S ( X ) ∈ H C X ∈ X n X \in\mathcal{X}^{n} X ∈ X n Δ H C ( S ) = sup X ∼ X ′ ∥ S ( X ) − S ( X ′ ) ∥ H C \Delta_{\mathcal{H}_{C}}(S) = \sup_{X\sim X'} \lVert S(X) - S(X') \rVert_{\mathcal{H}_{C}} Δ H C ( S ) = sup X ∼ X ′ ∥ S ( X ) − S ( X ′ ) ∥ H C
In practice, sensitivity may be unbounded when the data are unbounded, making it difficult to calibrate noise for privacy mechanisms. Clipping is a standard technique in DP for limiting the influence of individual data values. The clipping of x ∈ R x \in\mathbb{R} x ∈ R [ a , b ] [a,b] [ a , b ]
clip [ a , b ] ( x ) = min { b , max { a , x } } . \operatorname{clip}_{[a,b]}(x) = \min\{b, \max\{a,x\}\}. clip [ a , b ] ( x ) = min { b , max { a , x }} . By restricting values to a bounded interval, clipping can help control the sensitivity of statistical queries and facilitate the calibration of noise required to achieve certain DP guarantees.
Proposition 4 (The Gaussian Mechanism [9 ] ) Let S : X n → R d S : \mathcal{X}^{n} \to\mathbb{R}^{d} S : X n → R d ℓ 2 \ell_{2} ℓ 2 Δ 2 ( S ) = sup X ∼ X ′ ∥ S ( X ) − S ( X ′ ) ∥ 2 \Delta_{2}(S) = \sup_{X\sim X'} \lVert S(X) - S(X') \rVert_{2} Δ 2 ( S ) = sup X ∼ X ′ ∥ S ( X ) − S ( X ′ ) ∥ 2 S S S
M ( X ) = S ( X ) + Z , \mathcal{M}(X) = S(X) + Z, M ( X ) = S ( X ) + Z , where Z ∼ N ( 0 , σ 2 I d ) Z \sim\mathcal{N}(0,\sigma^{2}I_{d}) Z ∼ N ( 0 , σ 2 I d ) M ( X ) \mathcal{M}(X) M ( X ) μ \mu μ σ = Δ 2 ( S ) / μ \sigma= \Delta_{2}(S)/\mu σ = Δ 2 ( S ) / μ
In finite-dimensions, the Gaussian mechanism provides a fundamental approach to achieving GDP by adding Gaussian noise calibrated to the ℓ 2 \ell_{2} ℓ 2
The GDP satisfies two important properties: composition and post-processing [9 ] . Suppose k k k M 1 , … , M k \mathcal{M}_{1},\ldots,\mathcal{M}_{k} M 1 , … , M k μ 1 \mu_{1} μ 1 … \ldots … μ k \mu_{k} μ k M = ( M 1 , … , M k ) \mathcal{M} = (\mathcal{M}_{1},\ldots,\mathcal{M}_{k}) M = ( M 1 , … , M k ) μ \mu μ μ = ∑ i = 1 k μ i 2 \mu= \sqrt{\sum_{i=1}^{k}\mu_{i}^{2}} μ = ∑ i = 1 k μ i 2 M : X n → Y \mathcal{M} : \mathcal{X}^{n} \to\mathcal{Y} M : X n → Y μ \mu μ g g g Y \mathcal{Y} Y R \mathcal{R} R M ′ ( X ) = g ( M ( X ) ) \mathcal{M}'(X) = g(\mathcal{M}(X)) M ′ ( X ) = g ( M ( X )) μ \mu μ
These properties are particularly useful for analyzing the PTF mechanisms, both when combining multiple private releases and when applying subsequent estimation procedures to privatized data.
Problem Setup
In this section, we first specify our functional data model with necessary assumptions, then we define the privacy and estimation operators and formalize the proposed two possible orderings of fitting and privatizing: Fit-Then-Protect (FTP) and Protect-Then-Fit (PTF) with algorithmic implementation in a general separable Hilbert space H \mathcal{H} H
Functional Data Model
Throughout the paper, the observed data consist of n n n x i = ( x i 1 , … , x i T ) T ∈ X = R T \mathbf{x}_i=(x_{i1},\ldots,x_{iT})^{\mathsf{T}}\in\mathcal{X}=\mathbb{R}^{T} x i = ( x i 1 , … , x i T ) T ∈ X = R T 0 ≤ t 1 < t 2 < … < t T ≤ 1 0\leq t_1<t_2<\ldots<t_T\leq1 0 ≤ t 1 < t 2 < … < t T ≤ 1 X = ( x 1 , … , x n ) T ∈ R n × T X=(\mathbf{x}_1,\ldots,\mathbf{x}_n)^{\mathsf{T}}\in\mathbb{R}^{n\times T} X = ( x 1 , … , x n ) T ∈ R n × T t = ( t 1 , … , t T ) T \mathbf{t}=(t_1,\ldots,t_T)^{\mathsf{T}} t = ( t 1 , … , t T ) T f 1 , … , f n ∈ H f_1,\ldots,f_n\in\mathcal{H} f 1 , … , f n ∈ H H \mathcal{H} H f i = ( f i ( t 1 ) , … , f i ( t T ) ) T \mathbf{f}_i=(f_i(t_1),\ldots,f_i(t_T))^{\mathsf{T}} f i = ( f i ( t 1 ) , … , f i ( t T ) ) T f i f_i f i t \mathbf{t} t ϵ 1 , … , ϵ n ∈ R T \boldsymbol{\epsilon}_1,\ldots,\boldsymbol{\epsilon}_n\in\mathbb{R}^{T} ϵ 1 , … , ϵ n ∈ R T
x i = f i + ϵ i , i = 1 , … , n , (2) \mathbf{x}_i=\mathbf{f}_i+\boldsymbol{\epsilon}_i,\quad i=1,\ldots,n, \tag*{(2)} x i = f i + ϵ i , i = 1 , … , n , (2) with the following assumptions:
A.1 (Bounded functional norm) ∥ f i ∥ H ≤ B \|f_i\|_{\mathcal{H}}\leq B ∥ f i ∥ H ≤ B i = 1 , … , n i=1,\ldots,n i = 1 , … , n B > 0 B>0 B > 0
A.2 (Gaussian observation noise) Conditional on f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n ϵ 1 , … , ϵ n ∼ i . i . d . N ( 0 , σ 0 2 I T ) \boldsymbol{\epsilon}_1,\ldots,\boldsymbol{\epsilon}_n\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}N(0,\sigma_0^2I_T) ϵ 1 , … , ϵ n ∼ i.i.d. N ( 0 , σ 0 2 I T ) σ 0 ≥ 0 \sigma_0\geq0 σ 0 ≥ 0
Under Assumption A.2 , when σ 0 \sigma_0 σ 0 σ 0 = 0 \sigma_0=0 σ 0 = 0 x i j = f i ( t j ) x_{ij}=f_i(t_j) x ij = f i ( t j )
Additional assumptions specific to finite-dimensional Hilbert spaces and RKHS will be stated in the corresponding subsections. Our objective is to estimate the sample mean function f ˉ = 1 n ∑ i = 1 n f i \bar{f}=\frac{1}{n}\sum_{i=1}^{n}f_i f ˉ = n 1 ∑ i = 1 n f i X X X μ \mu μ
Privacy–Estimation Operators and Orderings
To estimate an individual function from its observed trajectory, we define a generic function estimation operator F : X → H \mathcal{F}:\mathcal{X}\to\mathcal{H} F : X → H
F ( x ) = argmin f ∈ H L ( f ; x ) subject to ∥ f ∥ H ≤ B ′ , (3) \mathcal{F}(\mathbf{x})=\underset{f\in\mathcal{H}}{\operatorname{argmin}}\ \mathcal{L}(f;\mathbf{x})\quad\text{subject to}\quad\|f\|_{\mathcal{H}}\leq B', \tag*{(3)} F ( x ) = f ∈ H argmin L ( f ; x ) subject to ∥ f ∥ H ≤ B ′ , (3) where L \mathcal{L} L B ′ B' B ′ L \mathcal{L} L t \mathbf{t} t
L ( f ; x ) = ( f − x ) T W ( f − x ) , f = ( f ( t 1 ) , … , f ( t T ) ) T (4) \mathcal{L}(f;\mathbf{x})=(\mathbf{f}-\mathbf{x})^{\mathsf{T}}W(\mathbf{f}-\mathbf{x}),\quad\mathbf{f}=(f(t_1),\ldots,f(t_T))^{\mathsf{T}} \tag*{(4)} L ( f ; x ) = ( f − x ) T W ( f − x ) , f = ( f ( t 1 ) , … , f ( t T ) ) T (4) is often considered, which depends on the choice of the weight matrix W W W x \mathbf{x} x W ∝ Σ − 1 W \propto\Sigma^{-1} W ∝ Σ − 1 Σ : = Cov ( x ) \Sigma:= \operatorname{Cov}(\mathbf{x}) Σ := Cov ( x ) W = I W = I W = I
Next, we denote the privacy mechanism as an operator. Let P μ H : H → B \mathcal{P}_{\mu}^{\mathcal{H}} : \mathcal{H} \to\mathbb{B} P μ H : H → B H \mathcal{H} H B \mathbb{B} B μ \mu μ P μ X n : X n → X \mathcal{P}_{\mu}^{\mathcal{X}^n} : \mathcal{X}^n \to\mathcal{X} P μ X n : X n → X μ \mu μ § 4 .
Under the previous framework, the two privacy-estimation pipelines considered in this paper can be written compactly as follows.
Fit-Then-Protect (FTP). Each individual trajectory is first converted into a function through a functional estimator F F T P \mathcal{F}_{\mathrm{FTP}} F FTP
f ~ F T P = P μ H ( 1 n ∑ i = 1 n F F T P ( x i ) ) . (5) \widetilde{f}_{\mathrm{FTP}} = \mathcal{P}_{\mu}^{\mathcal{H}}\left(\frac{1}{n}\sum_{i=1}^{n}\mathcal{F}_{\mathrm{FTP}}(\mathbf{x}_i)\right). \tag*{(5)} f FTP = P μ H ( n 1 i = 1 ∑ n F FTP ( x i ) ) . (5) Protect-Then-Fit (PTF). Privacy is first enforced on the observed dataset, after which the function estimator F P T F \mathcal{F}_{\mathrm{PTF}} F PTF
f ~ P T F = F P T F ( P μ X n ( X ) ) . (6) \widetilde{f}_{\mathrm{PTF}} = \mathcal{F}_{\mathrm{PTF}}\left(\mathcal{P}_{\mu}^{\mathcal{X}^n}(X)\right). \tag*{(6)} f PTF = F PTF ( P μ X n ( X ) ) . (6) Importantly, although both pipelines will satisfy the same prescribed privacy guarantee after appropriate calibration, they differ fundamentally in the order in which smoothing and privatization are performed. The primary goal of this paper is to understand how this ordering affects statistical accuracy.
In general, the two fitting operators F F T P \mathcal{F}_{\mathrm{FTP}} F FTP F P T F \mathcal{F}_{\mathrm{PTF}} F PTF Algorithm 1 Fit-Then-Protect (FTP); FTP ( X , t ; B ′ , μ ) \operatorname{FTP}(X,\mathbf{t};B',\mu) FTP ( X , t ; B ′ , μ )
Fixed specification: Gaussian law of Z Z Z B \mathbb{B} B H C \mathcal{H}_{C} H C L F T P \mathcal{L}_{\mathrm{FTP}} L FTP
Input: Observed dataset X = ( x 1 , … , x n ) T X=(x_1,\ldots,x_n)^{\mathsf{T}} X = ( x 1 , … , x n ) T t = ( t 1 , … , t T ) T \mathbf{t}=(t_1,\ldots,t_T)^{\mathsf{T}} t = ( t 1 , … , t T ) T B ′ > 0 B'>0 B ′ > 0 μ > 0 \mu>0 μ > 0
for i = 1 , … , n i=1,\ldots,n i = 1 , … , n do
[Fitting ] f ^ i ( c ) ← argmin f ∈ H C , ∥ f ∥ H C ≤ B ′ L F T P ( f ; x i ) \hat{f}^{(c)}_i \leftarrow\underset{f\in\mathcal{H}_C,\lVert f\rVert_{\mathcal{H}_C}\leq B'}{\operatorname{argmin}}\mathcal{L}_{\mathrm{FTP}}(f;x_i) f ^ i ( c ) ← f ∈ H C , ∥ f ∥ H C ≤ B ′ argmin L FTP ( f ; x i )
end for
f ^ ( c ) ← n − 1 ∑ i = 1 n f ^ i ( c ) \hat{f}^{(c)}\leftarrow n^{-1}\sum_{i=1}^{n}\hat{f}^{(c)}_i f ^ ( c ) ← n − 1 ∑ i = 1 n f ^ i ( c )
Set sensitivity bound Δ ← 2 B ′ / n \Delta\leftarrow2B'/n Δ ← 2 B ′ / n σ ← Δ / μ \sigma\leftarrow\Delta/\mu σ ← Δ/ μ
Sample Z Z Z X X X
[Protecting ] f ~ F T P ← f ^ ( c ) + σ Z \widetilde{f}_{\mathrm{FTP}}\leftarrow\hat{f}^{(c)}+\sigma Z f FTP ← f ^ ( c ) + σ Z
Output: f ~ F T P \widetilde{f}_{\mathrm{FTP}} f FTP
Algorithm 2 Protect-Then-Fit (PTF); PTF ( X , t ; B ′ , μ , c ) \operatorname{PTF}(X,\mathbf{t};B',\mu,\mathbf{c}) PTF ( X , t ; B ′ , μ , c )
Fixed specification: Fitting space H \mathcal{H} H L P T F \mathcal{L}_{\mathrm{PTF}} L PTF
Input: Observed dataset X = ( x 1 , … , x n ) T X=(x_1,\ldots,x_n)^{\mathsf{T}} X = ( x 1 , … , x n ) T t \mathbf{t} t B ′ > 0 B'>0 B ′ > 0 μ > 0 \mu>0 μ > 0 c = ( c 1 , … , c T ) T \mathbf{c}=(c_1,\ldots,c_T)^{\mathsf{T}} c = ( c 1 , … , c T ) T c j > 0 c_j>0 c j > 0
for j = 1 , … , T j=1,\ldots,T j = 1 , … , T do
x ˉ j ( c l i p ) ← n − 1 ∑ i = 1 n clip [ − c j , c j ] ( x i j ) \bar{x}^{(\mathrm{clip})}_j\leftarrow n^{-1}\sum_{i=1}^{n}\operatorname{clip}_{[-c_j,c_j]}(x_{ij}) x ˉ j ( clip ) ← n − 1 ∑ i = 1 n clip [ − c j , c j ] ( x ij )
Δ j ← 2 c j / n \Delta_j\leftarrow2c_j/n Δ j ← 2 c j / n σ D P , j ← Δ j T / μ \sigma_{\mathrm{DP},j}\leftarrow\Delta_j\sqrt{T}/\mu σ DP , j ← Δ j T / μ
Independently sample Z j ∼ N ( 0 , σ D P , j 2 ) Z_j\sim\mathcal{N}(0,\sigma_{\mathrm{DP},j}^{2}) Z j ∼ N ( 0 , σ DP , j 2 ) X X X
[Protecting ] x ~ j ← x ˉ j ( c l i p ) + Z j \widetilde{x}_j\leftarrow\bar{x}^{(\mathrm{clip})}_j+Z_j x j ← x ˉ j ( clip ) + Z j
end for
x ~ ← ( x ~ 1 , … , x ~ T ) T \widetilde{\mathbf{x}}\leftarrow(\widetilde{x}_1,\ldots,\widetilde{x}_T)^{\mathsf{T}} x ← ( x 1 , … , x T ) T
[Fitting ] f ~ P T F ← argmin f ∈ H , ∥ f ∥ H ≤ B ′ L P T F ( f ; x ~ ) \widetilde{f}_{\mathrm{PTF}}\leftarrow\underset{f\in\mathcal{H},\lVert f\rVert_{\mathcal{H}}\leq B'}{\operatorname{argmin}}\mathcal{L}_{\mathrm{PTF}}(f;\widetilde{\mathbf{x}}) f PTF ← f ∈ H , ∥ f ∥ H ≤ B ′ argmin L PTF ( f ; x )
Output: f ~ P T F \widetilde{f}_{\mathrm{PTF}} f PTF
vary across sampling locations. Accordingly, F P T F \mathcal{F}_{\mathrm{PTF}} F PTF
While Equation (5) and (6) introduce FTP and PTF as operators, their implementation requires specifying the function space, fitting loss, fitting radius, clipping bounds, and privacy mechanism. Algorithms 1 and 2 provide concrete realizations of FTP and PTF, respectively. For FTP, we choose a B \mathbb{B} B Z Z Z H C \mathcal{H}_C H C B ⊃ H C \mathbb{B}\supset\mathcal{H}_C B ⊃ H C § 4 , we use the Gaussian noise constructions in Examples 1 and 2, respectively, so that H C = H \mathcal{H}_C=\mathcal{H} H C = H c = ( c 1 , … , c T ) T \mathbf{c}=(c_1,\ldots,c_T)^{\mathsf{T}} c = ( c 1 , … , c T ) T B ′ B' B ′ § 4.2 , we consider c \mathbf{c} c t \mathbf{t} t ∣ f ( t ) ∣ ≤ ∥ f ∥ H K K ( t , t ) |f(t)| \le\|f\|_{\mathcal{H}_K}\sqrt{K(t,t)} ∣ f ( t ) ∣ ≤ ∥ f ∥ H K K ( t , t ) K ( t , t ) = 1 K(t,t)=1 K ( t , t ) = 1 c j = B ′ c_j=B' c j = B ′
Utility Criteria
To compare the two procedures, we evaluate their estimation accuracy relative to the sample mean function f ˉ \bar{f} f ˉ L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] f 1 , … , f n f_1,\ldots,f_n f 1 , … , f n
IMSE ( f ~ ) = ∫ 0 1 E [ ( f ~ ( t ) − f ˉ ( t ) ) 2 ] d t . (7) \operatorname{IMSE}(\widetilde{f}) = \int_0^1 \mathbb{E}\left[\left(\widetilde{f}(t)-\bar{f}(t)\right)^2\right]\,dt. \tag*{(7)} IMSE ( f ) = ∫ 0 1 E [ ( f ( t ) − f ˉ ( t ) ) 2 ] d t . (7) In infinite-dimensional function spaces, however, multiple functions may interpolate the same observed data points, making the underlying function potentially unidentifiable from the observed data alone. In this case, we evaluate estimation accuracy at the observed data points, and consider the empirical mean squared error (MSE) instead,
MSE ( f ~ ) = 1 T ∑ j = 1 T E [ ( f ~ ( t j ) − f ˉ ( t j ) ) 2 ] . (8) \operatorname{MSE}(\widetilde{f}) = \frac{1}{T}\sum_{j=1}^{T}\mathbb{E}\left[\left(\widetilde{f}(t_j)-\bar{f}(t_j)\right)^2\right]. \tag*{(8)} MSE ( f ) = T 1 j = 1 ∑ T E [ ( f ( t j ) − f ˉ ( t j ) ) 2 ] . (8) The remainder of the paper develops concrete realizations of the privacy operators in different function spaces and compares the statistical performance of the FTP and PTF pipelines under a common privacy budget. We write IMSE F T P = IMSE ( f ~ F T P ) \operatorname{IMSE}_{\mathrm{FTP}}=\operatorname{IMSE}(\widetilde{f}_{\mathrm{FTP}}) IMSE FTP = IMSE ( f FTP )
Theoretical Results
In this section, we develop the GDP mechanisms for functionals and compare the FTP and PTF regimes under the IMSE/MSE metric (depending on the function space). In § 4.1 , we extend the GDP mechanisms for functionals to the general separable Banach space and apply it to finite-dimensional Hilbert spaces and RKHSs. In § 4.2 , we give results for IMSE/MSE Ratio between the two regimes under the case without observation noise.
Privacy Guarantees
Gaussian-process perturbations provide a natural way to privatize function-valued summaries while preserving their functional structure. Hall et al. [14 ] established ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) [19 ] developed a Banach-space formulation that provides privacy guarantees for full-function releases. More recently, Räisä et al. [21 ] established a GDP guarantee for Gaussian-process perturbations under RKHS. The following theorem extends this GDP guarantee to Gaussian random elements in a separable Banach space, with sensitivity measured in the corresponding Cameron–Martin space.
Theorem 6 (GDP for Function-Valued Summaries). Let B \mathbb{B} B Z ∼ N B ( 0 , C ) Z \sim\mathcal{N}_{\mathbb{B}}(0,C) Z ∼ N B ( 0 , C ) H C \mathcal{H}_{C} H C S : X n → B S:\mathcal{X}^{n}\to\mathbb{B} S : X n → B S S S Z Z Z Δ H C ( S ) < ∞ \Delta_{\mathcal{H}_{C}}(S)<\infty Δ H C ( S ) < ∞ μ > 0 \mu>0 μ > 0 σ > 0 \sigma>0 σ > 0 σ ≥ Δ H C ( S ) / μ \sigma\ge\Delta_{\mathcal{H}_{C}}(S)/\mu σ ≥ Δ H C ( S ) / μ
S ~ ( X ) = S ( X ) + σ Z , \widetilde{S}(X)=S(X)+\sigma Z, S ( X ) = S ( X ) + σ Z , Then, S ~ ( X ) \widetilde{S}(X) S ( X ) μ \mu μ
Proof sketch. Our proof works directly with the hypothesis-testing interpretation of GDP. Using the Cameron–Martin density formula, it reduces the comparison of adjacent output distributions to a real-valued Gaussian testing problem, yielding the privacy guarantee directly through its tradeoff function.
Theorem 6 provides the privacy guarantee for the FTP pipeline in Equation (5) . In this setting, the summary is S ( X ) = n − 1 ∑ i = 1 n F ( x i ) S(X)=n^{-1}\sum_{i=1}^{n}F(x_i) S ( X ) = n − 1 ∑ i = 1 n F ( x i ) B ′ B' B ′ 2 B ′ / n 2B'/n 2 B ′ / n ( 2 B ′ / ( n μ ) ) Z (2B'/(n\mu))Z ( 2 B ′ / ( n μ )) Z μ \mu μ
In general, the Cameron–Martin space H C \mathcal{H}_{C} H C B \mathbb{B} B Examples 1 and 2 . For the finite-dimensional space H m \mathcal{H}_{m} H m B = H m \mathbb{B}=\mathcal{H}_{m} B = H m Z = Z m = ∑ k = 1 m ξ k ϕ k Z=Z_m=\sum_{k=1}^{m}\xi_k\phi_k Z = Z m = ∑ k = 1 m ξ k ϕ k ξ 1 , … , ξ m ∼ i i d N ( 0 , 1 ) \xi_1,\ldots,\xi_m\mathrel{\overset{\mathrm{iid}}{\sim}}\mathcal{N}(0,1) ξ 1 , … , ξ m ∼ iid N ( 0 , 1 ) H K \mathcal{H}_{K} H K B = C [ 0 , 1 ] \mathbb{B}=C[0,1] B = C [ 0 , 1 ] Z = Z K ∼ GP ( 0 , K ) Z=Z_K\sim\operatorname{GP}(0,K) Z = Z K ∼ GP ( 0 , K ) Example 2 . These constructions give H C = H m \mathcal{H}_{C}=\mathcal{H}_{m} H C = H m H C = H K \mathcal{H}_{C}=\mathcal{H}_{K} H C = H K § 4.2 use these specified noise constructions, where the fitting space and corresponding CM space are equal.
Corollary 7 (Finite-Dimensional Hilbert Space Realization). Let H m \mathcal{H}_{m} H m ϕ \phi ϕ Z m Z_m Z m Example 1 , and let S ( X ) = θ ( X ) ⊤ ϕ S(X)=\theta(X)^{\top}\phi S ( X ) = θ ( X ) ⊤ ϕ Z m Z_m Z m θ : X n → R m \theta:\mathcal{X}^{n}\to\mathbb{R}^{m} θ : X n → R m Δ H m ( S ) < ∞ \Delta_{\mathcal{H}_{m}}(S)<\infty Δ H m ( S ) < ∞ μ > 0 \mu>0 μ > 0 σ > 0 \sigma>0 σ > 0 σ ≥ Δ H m ( S ) / μ \sigma\ge\Delta_{\mathcal{H}_{m}}(S)/\mu σ ≥ Δ H m ( S ) / μ
S ~ ( X ) = S ( X ) + σ Z m = ( θ ( X ) + σ ξ ) ⊤ ϕ , ξ ∼ N ( 0 , I m ) , \widetilde{S}(X)=S(X)+\sigma Z_m=(\theta(X)+\sigma\xi)^{\top}\phi,\qquad\xi\sim\mathcal{N}(0,I_m), S ( X ) = S ( X ) + σ Z m = ( θ ( X ) + σ ξ ) ⊤ ϕ , ξ ∼ N ( 0 , I m ) , is μ \mu μ H m \mathcal{H}_{m} H m σ = 2 B ′ / ( n μ ) \sigma=2B'/(n\mu) σ = 2 B ′ / ( n μ ) σ ξ \sigma\xi σ ξ
Corollary 8 (RKHS Realization). Let K K K [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 Z K ∼ GP ( 0 , K ) Z_K\sim\operatorname{GP}(0,K) Z K ∼ GP ( 0 , K ) Example 2 .
For a measurable S : X n → H K S:\mathcal{X}^{n}\to\mathcal{H}_{K} S : X n → H K Z K Z_{K} Z K Δ H K ( S ) < ∞ \Delta_{\mathcal{H}_{K}}(S)<\infty Δ H K ( S ) < ∞ μ > 0 \mu>0 μ > 0 σ > 0 \sigma>0 σ > 0 σ ≥ Δ H K ( S ) / μ \sigma\ge\Delta_{\mathcal{H}_{K}}(S)/\mu σ ≥ Δ H K ( S ) / μ
S ~ ( X ) = S ( X ) + σ Z K \widetilde{S}(X)=S(X)+\sigma Z_{K} S ( X ) = S ( X ) + σ Z K is μ \mu μ H K \mathcal{H}_{K} H K σ = 2 B ′ / ( n μ ) \sigma=2B'/(n\mu) σ = 2 B ′ / ( n μ ) f ~ F T P = f ^ ( c ) + ( 2 B ′ ) / ( n μ ) K T 1 / 2 ξ \widetilde{\mathbf{f}}_{\mathrm{FTP}}=\widehat{\mathbf{f}}^{(c)}+(2B')/(n\mu)K_{T}^{1/2}\xi f FTP = f ( c ) + ( 2 B ′ ) / ( n μ ) K T 1/2 ξ ξ ∼ N ( 0 , I T ) \xi\sim N(0,I_{T}) ξ ∼ N ( 0 , I T )
Corollary 7 shows that the proposed functional GDP mechanism naturally extends the classical Gaussian mechanism from finite-dimensional vectors to finite-basis functional release through its coefficient vector. Corollary 8 specifies a full GP perturbation and its exact grid marginal. These constructions give direct implementations of Algorithm 1: the finite-dimensional Hilbert space release is represented by its coefficient vector, whereas an RKHS release evaluated only on the grid can be generated from the exact Gaussian grid marginal.
Proposition 9 (Privacy Guarantee for PTF). For fixed grid t t t B ′ > 0 B'>0 B ′ > 0 μ > 0 \mu>0 μ > 0 c j > 0 c_j>0 c j > 0 j j j f ~ P T F \widetilde{f}_{\mathrm{PTF}} f PTF μ \mu μ
Proposition 9 establishes the privacy guarantee for the PTF pipeline. The argument combines GDP composition for the privatized coordinate means with the post-processing property: once the privatized vector x ~ \widetilde{x} x μ \mu μ F P T F \mathcal{F}_{\mathrm{PTF}} F PTF
Comparison of FTP and PTF
The privacy guarantees established in the previous subsection hold for a general Banach space. The accuracy of the FTP and PTF pipelines, however, depends strongly on the structure of the underlying estimation problem. In this subsection we compare the two procedures under two representative settings, finite-dimensional Hilbert space and RKHS. For each function space, we first analyze the error rates for FTP and PTF separately, then give the upper bound of the error ratio of FTP to PTF in the noiseless setting, which reveals the intrinsic effect of the ordering of estimation and privatization.
Finite-dimensional Hilbert spaces
We first study finite-dimensional Hilbert spaces, where we use the IMSE for the comparison. Consider the space H m \mathcal{H}_{m} H m L 2 [ 0 , 1 ] L^{2}[0,1] L 2 [ 0 , 1 ] f i ( t ) = θ i T ϕ ( t ) f_i(t)=\boldsymbol{\theta}_i^{\mathsf{T}}\boldsymbol{\phi}(t) f i ( t ) = θ i T ϕ ( t )
Φ = [ ϕ k ( t j ) ] j = 1 , … , T ; k = 1 , … , m , M = Φ T Φ . \Phi=[\phi_k(t_j)]_{j=1,\ldots,T;\,k=1,\ldots,m},\qquad M=\Phi^{\mathsf{T}}\Phi. Φ = [ ϕ k ( t j ) ] j = 1 , … , T ; k = 1 , … , m , M = Φ T Φ. with the following assumption
A.3 M = Φ T Φ M=\Phi^{\mathsf{T}}\Phi M = Φ T Φ ∥ ϕ ( t j ) ∥ 2 > 0 \|\phi(t_j)\|_2>0 ∥ ϕ ( t j ) ∥ 2 > 0 j = 1 , … , T j=1,\ldots,T j = 1 , … , T
The requirement that ∥ ϕ ( t j ) ∥ 2 > 0 \lVert\phi(t_j)\rVert_2 > 0 ∥ ϕ ( t j ) ∥ 2 > 0 j j j ϕ ( t ) \phi(t) ϕ ( t ) t 1 , … , t T t_1,\ldots,t_T t 1 , … , t T T ≥ m T \ge m T ≥ m ϕ ( t ) \phi(t) ϕ ( t ) m − 1 m-1 m − 1 t \mathbf{t} t m m m ϕ ( t ) \phi(t) ϕ ( t )
For a symmetric positive-definite matrix A A A spectral condition number is defined as κ ( A ) = λ max ( A ) / λ min ( A ) \kappa(A)=\lambda_{\max}(A)/\lambda_{\min}(A) κ ( A ) = λ m a x ( A ) / λ m i n ( A ) λ min ( A ) \lambda_{\min}(A) λ m i n ( A ) λ max ( A ) \lambda_{\max}(A) λ m a x ( A ) A A A
Theorem 10 (FTP IMSE Upper Bound in Finite-Dimensional Hilbert Spaces). Under the finite-dimensional Hilbert space H m \mathcal{H}_m H m Z m Z_m Z m H C = H m \mathcal{H}_{\mathrm{C}}=\mathcal{H}_m H C = H m f ~ F T P \widetilde{f}_{\mathrm{FTP}} f FTP FTP ( X , t ; B ′ , μ ) \operatorname{FTP}(X,\mathbf{t};B',\mu) FTP ( X , t ; B ′ , μ ) L \mathcal{L} L (4) and W = I W=I W = I σ 0 > 0 \sigma_0>0 σ 0 > 0 B ′ ≥ B + m σ 0 λ min ( M ) B'\ge B+\frac{\sqrt{m}\sigma_0}{\sqrt{\lambda_{\min}(M)}} B ′ ≥ B + λ m i n ( M ) m σ 0 f ~ F T P \widetilde{f}_{\mathrm{FTP}} f FTP
IMSE F T P ≤ m ⋅ 4 B ′ 2 n 2 μ 2 + κ ( M ) σ 0 2 n tr ( M − 1 ) + ( 1 − 1 n ) 3 κ ( M ) σ 0 2 tr ( M − 1 ) exp [ − 1 4 ( ( B ′ − B ) λ min ( M ) σ 0 − m ) 2 ] . (9) \operatorname{IMSE}_{\mathrm{FTP}}\le m\cdot\frac{4B'^2}{n^2\mu^2}+\frac{\kappa(M)\sigma_0^2}{n}\operatorname{tr}(M^{-1})
+\left(1-\frac{1}{n}\right)\sqrt{3\kappa(M)\sigma_0^2\operatorname{tr}(M^{-1})}\exp\left[-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{m}\right)^2\right]. \tag*{(9)} IMSE FTP ≤ m ⋅ n 2 μ 2 4 B ′2 + n κ ( M ) σ 0 2 tr ( M − 1 ) + ( 1 − n 1 ) 3 κ ( M ) σ 0 2 tr ( M − 1 ) exp − 4 1 ( σ 0 ( B ′ − B ) λ m i n ( M ) − m ) 2 . (9) When σ 0 = 0 \sigma_0=0 σ 0 = 0 B ′ ≥ B B'\ge B B ′ ≥ B IMSE F T P = 4 m B ′ 2 / ( n 2 μ 2 ) \operatorname{IMSE}_{\mathrm{FTP}}=4mB'^2/(n^2\mu^2) IMSE FTP = 4 m B ′2 / ( n 2 μ 2 )
Theorem 10 gives the upper bound for IMSE of FTP under finite-dimensional Hilbert spaces. The three terms correspond to privacy noise, observation error, and the effect of an active constraint. Fix the basis ϕ \phi ϕ t \mathbf{t} t B B B σ 0 > 0 \sigma_0>0 σ 0 > 0 B ′ B' B ′ m \sqrt{m} m m + a log n \sqrt{m}+a\sqrt{\log n} m + a log n a > 2 a>2 a > 2 O ( n − a 2 / 4 ) = o ( n − 1 ) O(n^{-a^2/4})=o(n^{-1}) O ( n − a 2 /4 ) = o ( n − 1 )
IMSE F T P = O ( 1 n + ( B ′ ) 2 n 2 μ 2 ) . \operatorname{IMSE}_{\mathrm{FTP}}=O\left(\frac{1}{n}+\frac{(B')^2}{n^2\mu^2}\right). IMSE FTP = O ( n 1 + n 2 μ 2 ( B ′ ) 2 ) . For a fixed μ > 0 \mu>0 μ > 0 B ′ = O ( n ) B'=O(\sqrt{n}) B ′ = O ( n ) O ( n − 1 ) O(n^{-1}) O ( n − 1 ) [ 0 , 1 ] [0,1] [ 0 , 1 ] T → ∞ T\to\infty T → ∞ M / T → I m M/T\to I_m M / T → I m κ ( M ) → 1 \kappa(M)\to1 κ ( M ) → 1 tr ( M − 1 ) ∼ m / T \operatorname{tr}(M^{-1})\sim m/T tr ( M − 1 ) ∼ m / T σ 0 2 m / ( n T ) \sigma_0^2m/(nT) σ 0 2 m / ( n T )
Theorem 11 (PTF IMSE Lower Bound in Finite-Dimensional Hilbert Spaces). Under the finite-dimensional Hilbert space H m \mathcal{H}_m H m
τ = 2 B ′ T n μ . \tau=\frac{2B'\sqrt{T}}{n\mu}. τ = n μ 2 B ′ T . For the estimator f ~ P T F \widetilde{f}_{\mathrm{PTF}} f PTF PTF ( X , t ; B ′ , μ , c ) \operatorname{PTF}(X,\mathbf{t};B',\mu,c) PTF ( X , t ; B ′ , μ , c )
defined in Equation (4) , W = diag { ∥ ϕ ( t j ) ∥ 2 − 2 : j = 1 , … , T } W = \operatorname{diag}\{\lVert\phi(t_j)\rVert_2^{-2}:j=1,\ldots,T\} W = diag {∥ ϕ ( t j ) ∥ 2 − 2 : j = 1 , … , T } c j = B ′ ∥ ϕ ( t j ) ∥ 2 c_j = B'\lVert\phi(t_j)\rVert_2 c j = B ′ ∥ ϕ ( t j ) ∥ 2 A = Φ T W Φ A = \Phi^{\mathsf{T}}W\Phi A = Φ T W Φ A A A σ 0 = 0 \sigma_0=0 σ 0 = 0 B ′ ≥ B + τ m λ min ( A ) B' \ge B + \frac{\tau\sqrt{m}}{\sqrt{\lambda_{\min}(A)}} B ′ ≥ B + λ m i n ( A ) τ m f ~ P T F \widetilde{f}_{\mathrm{PTF}} f PTF
IMSE P T F ≥ τ 2 tr ( A − 1 ) { 1 − 3 exp [ − 1 4 ( ( B ′ − B ) λ min ( A ) τ − m ) 2 ] } . (10) \operatorname{IMSE}_{\mathrm{PTF}} \ge\tau^2\operatorname{tr}(A^{-1})\left\{1-\sqrt{3}\exp\left[-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(A)}}{\tau}-\sqrt{m}\right)^2\right]\right\}. \tag*{(10)} IMSE PTF ≥ τ 2 tr ( A − 1 ) ⎩ ⎨ ⎧ 1 − 3 exp − 4 1 ( τ ( B ′ − B ) λ m i n ( A ) − m ) 2 ⎭ ⎬ ⎫ . (10) Theorem 11 gives the lower bound for IMSE of PTF under the finite-dimensional Hilbert space without observation noise, when B ′ > B B' > B B ′ > B n n n
Corollary 12 (IMSE Ratio Upper Bound for Finite-Dimensional Hilbert Spaces) Consider the FTP and PTF estimators defined in Theorem 10 and Theorem 11 with σ 0 = 0 \sigma_0=0 σ 0 = 0 T T T m m m μ \mu μ B n ′ B'_n B n ′ B n ′ > B B'_n > B B n ′ > B n n n
lim sup n → ∞ IMSE ( f ~ F T P ) IMSE ( f ~ P T F ) ≤ m T tr ( A − 1 ) ≤ 1 m , (11) \limsup_{n\to\infty}\frac{\operatorname{IMSE}(\widetilde{f}_{\mathrm{FTP}})}{\operatorname{IMSE}(\widetilde{f}_{\mathrm{PTF}})} \le\frac{m}{T\operatorname{tr}(A^{-1})} \le\frac{1}{m}, \tag*{(11)} n → ∞ lim sup IMSE ( f PTF ) IMSE ( f FTP ) ≤ T tr ( A − 1 ) m ≤ m 1 , (11) where A = Φ T W Φ A=\Phi^{\mathsf{T}}W\Phi A = Φ T W Φ Theorem 11 , and B n ′ B'_n B n ′ B ′ B' B ′ Theorems 10 and 11 .
Corollary 12 suggests that for m > 1 m>1 m > 1 n n n 1 / m 1/m 1/ m m m m m m m m = 2 m=2 m = 2 { 1 , 3 ( 2 t − 1 ) } \{1,\sqrt{3}(2t-1)\} { 1 , 3 ( 2 t − 1 )} span { 1 , t } \operatorname{span}\{1,t\} span { 1 , t } { 1 , 5 ( 3 t 2 − 1 ) / 2 } \{1,\sqrt{5}(3t^2-1)/2\} { 1 , 5 ( 3 t 2 − 1 ) /2 } span { 1 , t 2 } \operatorname{span}\{1,t^2\} span { 1 , t 2 } 1 / 2 1/2 1/2
RKHS
Let H K \mathcal{H}_K H K K ( ⋅ , ⋅ ) K(\cdot,\cdot) K ( ⋅ , ⋅ ) K T = [ K ( t k , t l ) ] k , l = 1 T K_T=[K(t_k,t_l)]_{k,l=1}^{T} K T = [ K ( t k , t l ) ] k , l = 1 T
A.4 K T K_T K T K ( t j , t j ) > 0 K(t_j,t_j)>0 K ( t j , t j ) > 0 j = 1 , … , T j=1,\ldots,T j = 1 , … , T
The comparison is performed under the empirical MSE criterion
Theorem 13 (MSE Upper Bound for FTP in RKHS) Under the RKHS H K \mathcal{H}_K H K Z K ∼ GP ( 0 , K ) Z_K\sim\operatorname{GP}(0,K) Z K ∼ GP ( 0 , K ) H C = H K \mathcal{H}_C=\mathcal{H}_K H C = H K f ~ F T P \widetilde{f}_{\mathrm{FTP}} f FTP FTP ( X , t ; B ′ , μ ) \operatorname{FTP}(X,t;B',\mu) FTP ( X , t ; B ′ , μ ) L \mathcal{L} L (4) and W = I W=I W = I σ 0 > 0 \sigma_0>0 σ 0 > 0 B ′ ≥ B + σ 0 T λ min ( K T ) B'\ge B+\frac{\sigma_0\sqrt{T}}{\sqrt{\lambda_{\min}(K_T)}} B ′ ≥ B + λ m i n ( K T ) σ 0 T
MSE F T P ≤ 4 B ′ 2 n 2 μ 2 T tr ( K T ) + σ 0 2 n + ( 1 − 1 n ) σ 0 2 T + 2 T exp { − 1 4 ( ( B ′ − B ) λ min ( K T ) σ 0 − T ) 2 } . \operatorname{MSE}_{\mathrm{FTP}} \le\frac{4B'^2}{n^2\mu^2T}\operatorname{tr}(K_T)+\frac{\sigma_0^2}{n}
+\left(1-\frac{1}{n}\right)\sigma_0^2\sqrt{\frac{T+2}{T}}\exp\left\{-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(K_T)}}{\sigma_0}-\sqrt{T}\right)^2\right\}. MSE FTP ≤ n 2 μ 2 T 4 B ′2 tr ( K T ) + n σ 0 2 + ( 1 − n 1 ) σ 0 2 T T + 2 exp ⎩ ⎨ ⎧ − 4 1 ( σ 0 ( B ′ − B ) λ m i n ( K T ) − T ) 2 ⎭ ⎬ ⎫ . When σ 0 = 0 \sigma_0 = 0 σ 0 = 0 B ′ ≥ B B' \ge B B ′ ≥ B M S E F T P = 4 B ′ 2 tr ( K T ) / ( n 2 μ 2 T ) \mathrm{MSE}_{\mathrm{FTP}} = 4B'^{2}\operatorname{tr}(K_T)/(n^{2}\mu^{2}T) MSE FTP = 4 B ′ 2 tr ( K T ) / ( n 2 μ 2 T )
Theorem 13 provides a general upper bound for the MSE of FTP in the RKHS setting. The result is analogous to Theorem 10, but the present formulation allows the true functions f i f_i f i K K K t t t B B B σ 0 > 0 \sigma_0 > 0 σ 0 > 0 B ′ B' B ′ T \sqrt{T} T T + a log n \sqrt{T} + a\sqrt{\log n} T + a log n a > 2 a > 2 a > 2
M S E F T P = O ( 1 n + ( B ′ ) 2 n 2 μ 2 ) . \mathrm{MSE}_{\mathrm{FTP}} = O\left(\frac{1}{n} + \frac{(B')^2}{n^2\mu^2}\right). MSE FTP = O ( n 1 + n 2 μ 2 ( B ′ ) 2 ) . For fixed μ > 0 \mu> 0 μ > 0 B ′ B' B ′ B ′ = O ( n ) B' = O(\sqrt{n}) B ′ = O ( n ) O ( 1 / n ) O(1/n) O ( 1/ n ) B ′ B' B ′ K ( t j , t j ) = 1 K(t_j,t_j) = 1 K ( t j , t j ) = 1 j j j tr ( K T ) = T \operatorname{tr}(K_T) = T tr ( K T ) = T 4 ( B ′ ) 2 / ( n 2 μ 2 ) 4(B')^2/(n^2\mu^2) 4 ( B ′ ) 2 / ( n 2 μ 2 )
Theorem 14 (MSE Lower Bound for PTF in RKHS). Under the RKHS H K \mathcal{H}_K H K τ = 2 B ′ T n μ \tau= \frac{2B'\sqrt{T}}{n\mu} τ = n μ 2 B ′ T f ~ P T F \tilde{f}_{\mathrm{PTF}} f ~ PTF ( X , t ; B ′ , μ , c ) (X,t;B',\mu,\mathbf{c}) ( X , t ; B ′ , μ , c ) L \mathcal{L} L (4) , W = diag { K ( t j , t j ) − 1 : j = 1 , … , T } W = \operatorname{diag}\{K(t_j,t_j)^{-1}: j = 1,\ldots,T\} W = diag { K ( t j , t j ) − 1 : j = 1 , … , T } c j = B ′ K ( t j , t j ) c_j = B'\sqrt{K(t_j,t_j)} c j = B ′ K ( t j , t j ) A = K T 1 / 2 W K T 1 / 2 A = K_T^{1/2}WK_T^{1/2} A = K T 1/2 W K T 1/2 A A A
When σ 0 = 0 \sigma_0 = 0 σ 0 = 0 B ′ ≥ B + τ T λ min ( A ) B' \ge B + \frac{\tau\sqrt{T}}{\sqrt{\lambda_{\min}(A)}} B ′ ≥ B + λ m i n ( A ) τ T
M S E P T F ≥ τ 2 T tr ( W − 1 ) [ 1 − 3 exp { − 1 4 ( ( B ′ − B ) λ min ( A ) τ − T ) 2 } ] . (12) \mathrm{MSE}_{\mathrm{PTF}} \ge\frac{\tau^2}{T}\operatorname{tr}(W^{-1})\left[1-\sqrt{3}\exp\left\{-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(A)}}{\tau}-\sqrt{T}\right)^2\right\}\right]. \tag*{(12)} MSE PTF ≥ T τ 2 tr ( W − 1 ) 1 − 3 exp ⎩ ⎨ ⎧ − 4 1 ( τ ( B ′ − B ) λ m i n ( A ) − T ) 2 ⎭ ⎬ ⎫ . (12) Theorem 14 provides a lower bound for MSE of PTF under RKHS without observation noise, which is similar to Theorem 11. In particular, under the Gaussian Kernel, we have K ( t j , t j ) = 1 K(t_j,t_j) = 1 K ( t j , t j ) = 1 j j j tr ( W − 1 ) = T \operatorname{tr}(W^{-1}) = T tr ( W − 1 ) = T
Corollary 15 (MSE Comparison under RKHS). Consider the FTP and PTF estimators defined in Theorem 13 and Theorem 14 with σ 0 = 0 \sigma_0 = 0 σ 0 = 0 T T T μ \mu μ B n ′ B'_n B n ′ B n ′ > B B'_n > B B n ′ > B n n n
lim sup n → ∞ M S E ( f ~ F T P ) M S E ( f ~ P T F ) ≤ 1 T . (13) \limsup_{n\to\infty}\frac{\mathrm{MSE}(\tilde{f}_{\mathrm{FTP}})}{\mathrm{MSE}(\tilde{f}_{\mathrm{PTF}})} \le\frac{1}{T}. \tag*{(13)} n → ∞ lim sup MSE ( f ~ PTF ) MSE ( f ~ FTP ) ≤ T 1 . (13) where B n ′ B'_n B n ′ B ′ B' B ′
Corollary 15 shows that in the noiseless setting with T > 1 T > 1 T > 1 n n n 1 / T 1/T 1/ T tr ( W − 1 ) = tr ( K T ) \operatorname{tr}(W^{-1}) = \operatorname{tr}(K_T) tr ( W − 1 ) = tr ( K T )
Simulation Studies
In this section, we compare the empirical performance of the proposed strategies, Protect-Then-Fit versus Fit-Then-Protect , implemented through Algorithms 1 and 2. We focus on the RKHS associated with the Gaussian kernel; the corresponding simulation setup and results for polynomial spaces are presented in Appendix § 10 . In § 5.1 , we first examine the noiseless error ratios in relation to the theoretical bounds in § 4.2 , and in § 5.2 , we investigate how different choices of the constraint radius B ′ B' B ′ § 5.3 , we further explore the effect of different magnitudes of observation noise. The RKHS simulation setup is specified below.
RKHS Simulation Setup. Consider the RKHS H K \mathcal{H}_K H K K K K (1) with bandwidth ρ = 0.2 \rho= 0.2 ρ = 0.2 f 1 , … , f n ∈ H K f_1,\ldots,f_n \in\mathcal{H}_K f 1 , … , f n ∈ H K M = 20 M = 20 M = 20 { c 1 , ⋯ , c M } \{c_1,\cdots,c_M\} { c 1 , ⋯ , c M } f i ( t ) = α i T K c ( t ) f_i(t) = \alpha_i^{\mathsf{T}}K_c(t) f i ( t ) = α i T K c ( t ) K c ( t ) = ( K ( c 1 , t ) , … , K ( c M , t ) ) T K_c(t) = (K(c_1,t),\ldots,K(c_M,t))^{\mathsf{T}} K c ( t ) = ( K ( c 1 , t ) , … , K ( c M , t ) ) T α i \alpha_i α i α i T K C α i ≤ B 2 \alpha_i^{\mathsf{T}}K_C\alpha_i \le B^2 α i T K C α i ≤ B 2 K C = [ K ( c j , c k ) ] j , k = 1 M K_C = [K(c_j,c_k)]_{j,k=1}^M K C = [ K ( c j , c k ) ] j , k = 1 M B = 1 B = 1 B = 1 ∥ f i ∥ H K ≤ B \lVert f_i\rVert_{\mathcal{H}_K} \le B ∥ f i ∥ H K ≤ B X X X x i j = f i ( t j ) + ϵ i j x_{ij} = f_i(t_j) + \epsilon_{ij} x ij = f i ( t j ) + ϵ ij ϵ i j ∼ i . i . d . N ( 0 , σ 0 2 ) \epsilon_{ij} \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} N(0,\sigma_0^2) ϵ ij ∼ i.i.d. N ( 0 , σ 0 2 ) t j = ( j − 1 ) / ( T − 1 ) t_j = (j-1)/(T-1) t j = ( j − 1 ) / ( T − 1 ) j = 1 , … , T j = 1,\ldots,T j = 1 , … , T
The constrained RKHS fitting in Algorithms 1 and 2 is implemented through finite kernel representations at the observation grid. An eigendecomposition of K T K_T K T 10 − 8 10^{-8} 1 0 − 8 N ( 0 , ( 2 B ′ / ( n μ ) ) 2 K T ) N(0,(2B'/(n\mu))^2K_T) N ( 0 , ( 2 B ′ / ( n μ ) ) 2 K T )
We vary the sample sizes, number of grid points, privacy budgets, constraint radius, and observation-noise standard deviations as follows: n ∈ { 2 2 , 2 3 , … , 2 12 } n \in\{2^2,2^3,\ldots,2^{12}\} n ∈ { 2 2 , 2 3 , … , 2 12 } T ∈ { 2 , 4 , 6 , 8 } T \in\{2,4,6,8\} T ∈ { 2 , 4 , 6 , 8 } μ ∈ { 0.1 , 1 } \mu\in\{0.1,1\} μ ∈ { 0.1 , 1 } B ′ ∈ { B , 1.1 B , log n , log n , n , n 2 / 3 } B' \in\{B,1.1B,\sqrt{\log n},\log n,\sqrt{n},n^{2/3}\} B ′ ∈ { B , 1.1 B , log n , log n , n , n 2/3 } σ 0 ∈ { 0 , 0.1 , 1 , 10 } \sigma_0 \in\{0,0.1,1,10\} σ 0 ∈ { 0 , 0.1 , 1 , 10 }
All the simulations are run with 1000 Monte Carlo repetitions. Simulation settings are evaluated in parallel in R using foreach and doParallel, with separate random-number streams assigned to the workers.
Effect of Fitting Dimension
We first investigate how the fitting dimension affects the relative accuracy of FTP and PTF. Here, the fitting dimension refers to the dimension of the space used to represent the fitted functions f ^ i ( c ) \hat{f}_i^{(c)} f ^ i ( c ) i = 1 , … , n i = 1,\ldots,n i = 1 , … , n f ^ P T F \hat{f}_{\mathrm{PTF}} f ^ PTF span { K ( t 1 , ⋅ ) , … , K ( t T , ⋅ ) } \operatorname{span}\{K(t_1,\cdot),\ldots,K(t_T,\cdot)\} span { K ( t 1 , ⋅ ) , … , K ( t T , ⋅ )} T T T K T K_T K T T T T T ∈ { 2 , 4 , 6 , 8 } T \in\{2,4,6,8\} T ∈ { 2 , 4 , 6 , 8 }
n ∈ { 2 2 , … , 2 12 } n \in\{2^2,\ldots,2^{12}\} n ∈ { 2 2 , … , 2 12 } σ 0 = 0 \sigma_0 = 0 σ 0 = 0 μ ∈ { 0.1 , 1 } \mu\in\{0.1,1\} μ ∈ { 0.1 , 1 } B ′ = 1.1 > B = 1 B' = 1.1 > B = 1 B ′ = 1.1 > B = 1 1 / T 1/T 1/ T
Figure 1 shows that the MSE ratios of FTP to PTF generally decrease as sample size n n n 1 / T 1/T 1/ T T ≥ 2 T \ge2 T ≥ 2 μ = 0.1 \mu= 0.1 μ = 0.1 T T T μ \mu μ 1 / T 1/T 1/ T n n n Table 1 in Appendix § 10 . The corresponding polynomial-space results are presented in Figure 4 in the same appendix.
Figure 1. Empirical MSE ratio of FTP to PTF versus sample size n n n B ′ = 1.1 B' = 1.1 B ′ = 1.1 μ ∈ { 0.1 , 1 } \mu\in\{0.1,1\} μ ∈ { 0.1 , 1 } T T T 1 / T 1/T 1/ T
Figure 4. Empirical IMSE ratio of FTP to PTF versus sample size n n n σ 0 = 0 \sigma_0 = 0 σ 0 = 0 B ′ = 1.1 B' = 1.1 B ′ = 1.1 μ = 0.1 \mu= 0.1 μ = 0.1 μ = 1 \mu= 1 μ = 1 m m m 1 / m 1/m 1/ m
Table 1. Noiseless RKHS simulation results for B = 1 B=1 B = 1 B ′ = 1.1 B'=1.1 B ′ = 1.1 ρ = 0.2 \rho=0.2 ρ = 0.2 p ^ P T F \hat{p}_{\mathrm{PTF}} p ^ PTF
Choices of Constraint Radius
We next examine the role of the fitting radius B ′ B' B ′ σ 0 = 1 \sigma_0 = 1 σ 0 = 1 μ = 1 \mu= 1 μ = 1 T = 4 T = 4 T = 4 B ′ ∈ { B , log n , log n , n , n 2 / 3 } B' \in\{B,\sqrt{\log n},\log n,\sqrt{n},n^{2/3}\} B ′ ∈ { B , log n , log n , n , n 2/3 } n ∈ { 2 2 , … , 2 12 } n \in\{2^2, \ldots, 2^{12}\} n ∈ { 2 2 , … , 2 12 } B ′ = B B' = B B ′ = B log n \sqrt{\log n} log n log n \log n log n n \sqrt{n} n § 4.2 , and B ′ = n 2 / 3 B' = n^{2/3} B ′ = n 2/3 O ( 1 / n ) O(1/n) O ( 1/ n ) n − 2 / 3 n^{-2/3} n − 2/3 n n n n − 1 n^{-1} n − 1
Figure 2 shows that no single radius choice performs best across all sample sizes. The oracle radius B ′ = B B' = B B ′ = B n n n B ′ = log n B' = \log n B ′ = log n n × M S E F T P n \times\mathrm{MSE}_{\mathrm{FTP}} n × MSE FTP B ′ = log n B' = \sqrt{\log n} B ′ = log n n n n log n \sqrt{\log n} log n n \sqrt{n} n n 2 / 3 n^{2/3} n 2/3 Figure 5 in Appendix § 10 .
Figure 2. Scaled empirical MSE (n × M S E n \times\mathrm{MSE} n × MSE B ′ B' B ′ σ 0 = 1 \sigma_0 = 1 σ 0 = 1 μ = 1 \mu= 1 μ = 1 T = 4 T = 4 T = 4
Figure 5. Scaled empirical IMSE (n × I M S E n \times\mathrm{IMSE} n × IMSE B ′ B' B ′ σ 0 = 1 \sigma_0 = 1 σ 0 = 1 μ = 1 \mu= 1 μ = 1 m = 4 m = 4 m = 4
Effect of Observation Noise
Finally, we investigate how observation noise affects the relative performance of FTP and PTF by comparing their MSE ratio under noisy observations. We vary n ∈ { 2 2 , … , 2 12 } n \in\{2^2,\ldots,2^{12}\} n ∈ { 2 2 , … , 2 12 } T ∈ { 2 , 4 , 6 , 8 } T \in\{2,4,6,8\} T ∈ { 2 , 4 , 6 , 8 } σ 0 ∈ { 0.1 , 1 , 10 } \sigma_0 \in\{0.1,1,10\} σ 0 ∈ { 0.1 , 1 , 10 } § 5.1 and 5.2, we fix μ = 1 \mu= 1 μ = 1 B ′ = log n B' = \log n B ′ = log n B = 1 B = 1 B = 1 ∣ f i ( t ) ∣ ≤ 1 |f_i(t)| \le1 ∣ f i ( t ) ∣ ≤ 1 1 / T 1/T 1/ T
Figure 3 shows that the relative performance of FTP and PTF depends strongly on the observation-noise level. When σ 0 = 0.1 \sigma_0 = 0.1 σ 0 = 0.1 σ 0 = 1 \sigma_0 = 1 σ 0 = 1 n n n σ 0 = 10 \sigma_0 = 10 σ 0 = 10 Figure 6 in Appendix § 10 .
Figure 3. Empirical MSE ratio of FTP to PTF versus sample size n n n σ 0 ∈ { 0.1 , 1 , 10 } \sigma_0 \in\{0.1,1,10\} σ 0 ∈ { 0.1 , 1 , 10 } μ = 1 \mu= 1 μ = 1 B ′ = log n B' = \log n B ′ = log n T T T 1 / T 1/T 1/ T
Figure 6. Empirical IMSE ratio of FTP to PTF versus sample size n n n σ 0 ∈ { 0.1 , 1 , 10 } \sigma_0 \in\{0.1, 1, 10\} σ 0 ∈ { 0.1 , 1 , 10 } μ = 1 \mu= 1 μ = 1 B ′ = log n B' = \sqrt{\log n} B ′ = log n m m m 1 / m 1/m 1/ m
Discussion and Directions for Future Work
In this paper, we study how the ordering of functional estimation and privacy perturbation affects the accuracy of private functional mean estimation. We introduce the Fit-Then-Protect (FTP) and Protect-Then-Fit (PTF) pipelines and establish a GDP guarantee for Gaussian perturbations of function-valued summaries in separable Banach spaces, and compare the accuracy of the two pipelines under a common privacy budget. Our results show that, under the stated conditions, FTP achieves strictly smaller estimation error than PTF for sufficiently large sample sizes, with the asymptotic error ratio governed by the basis dimension in finite-dimensional Hilbert spaces and by the number of sampling locations in RKHSs. These findings highlight the importance of exploiting functional structure before privatization.
The simulation results further demonstrate that the relative performance of FTP and PTF depends on the observation regime. In the noiseless and low-noise settings, the empirical results are consistent with the theoretical comparisons and show a substantial advantage for FTP. As observation noise increases, however, this advantage becomes smaller and can eventually disappear or reverse. Furthermore, the constraint radius B ′ B^{\prime} B ′ B ′ B^{\prime} B ′
Several limitations of the current analysis suggest directions for future work. First, our direct theoretical comparison between FTP and PTF focuses primarily on the noiseless setting. Although we derive noisy-data bounds for FTP and investigate observation noise empirically, a general theoretical characterization of the FTP–PTF comparison with nonzero observation noise remains open. Such a result would need to account simultaneously for observation-noise covariance, privacy-induced covariance, and the nonlinear effects of constrained functional estimation. A more complete noisy-data theory could clarify how the relative efficiency of the two orderings changes across observation regimes and identify conditions under which their performance become comparable or one procedure may become preferable.
Second, the comparison could be extended to more general sampling designs, function spaces, and privacy mechanisms. Our analysis assumes a common observation grid, and our simulations focus on polynomial spaces and Gaussian-kernel RKHSs. Studying irregular sampling and broader classes of function spaces, such as Sobolev spaces and RKHSs with different eigenvalue decay properties, would help clarify how sampling design and functional smoothness affect the relative accuracy of the two pipelines. In addition, while the current PTF construction provides a convenient GDP guarantee through perturbation at the observation level, coordinatewise perturbation need not be optimal for the geometry of functional data. Characterizing the optimal GDP design for PTF, including structured perturbations that exploit basis, kernel, or covariance information, is therefore an important open problem. Such mechanisms could potentially improve the utility of PTF and provide a more geometry-aware comparison with FTP.
Finally, the FTP/PTF distinction extends naturally beyond functional mean estimation. Functional regression, functional principal component analysis, covariance-function estimation, and other functional data analysis procedures involve transformations of functional observations that may be performed either before or after privacy perturbation. Investigating how privacy-estimation ordering interacts with these procedures, particularly when the estimation operator is nonlinear, could lead to a broader theory of when statistical structure should be extracted before privatization and when privacy should instead be imposed at an earlier stage of the analysis.
Overall, our results highlight that differential privacy for functional data is not only a problem of calibrating an appropriate noise process, but also a problem of deciding where privacy should be imposed within the statistical pipeline. The comparison between FTP and PTF illustrates that this design choice can have a substantial effect on estimation accuracy, while also showing that its impact depends on the observation-noise regime and the geometry of the underlying function space. These findings motivate further development of privacy mechanisms that jointly account for functional structure, observation noise, sampling design, and the geometry of the statistical representation.
Acknowledgments and Disclosure of Funding
This work was supported in part by NSF grants SES-2150615 and SES-260910.
Limitation of Pure Differential Privacy
In this section, we briefly review pure differential privacy (DP) and the Laplace mechanism, then use a constant-function example to illustrate how the privacy framework affects the relative performance of FTP and PTF.
Definition 16 (ϵ \epsilon ϵ A randomized mechanism M : X n → Y M : \mathcal{X}^{n} \to\mathcal{Y} M : X n → Y ϵ \epsilon ϵ X ∼ X ′ X \sim X' X ∼ X ′ A ⊆ Y A \subseteq\mathcal{Y} A ⊆ Y
Pr ( M ( X ) ∈ A ) ≤ e ϵ Pr ( M ( X ′ ) ∈ A ) \Pr(M(X) \in A) \leq e^{\epsilon} \Pr(M(X') \in A) Pr ( M ( X ) ∈ A ) ≤ e ϵ Pr ( M ( X ′ ) ∈ A ) The privacy parameter ϵ \epsilon ϵ
Proposition 17 (Laplace Mechanism, [11 ] .) Given a statistic S ( X ) ∈ R d S(X) \in\mathbb{R}^{d} S ( X ) ∈ R d
M ( X ) = S ( X ) + L , L i ∼ i i d Lap ( Δ 1 ( S ) ϵ ) , i = 1 , … , d . M(X) = S(X) + L, \qquad L_i \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Lap}\left(\frac{\Delta_1(S)}{\epsilon}\right), i = 1,\ldots,d. M ( X ) = S ( X ) + L , L i ∼ iid Lap ( ϵ Δ 1 ( S ) ) , i = 1 , … , d . Then M ( X ) M(X) M ( X ) ϵ \epsilon ϵ
In infinite-dimensional settings, extending Laplace-type mechanisms becomes difficult. In particular, some work shows that there does not exist a natural infinite-dimensional analogue of elliptical Laplace distributions that achieves pure ϵ \epsilon ϵ [23 ] ).
Example 3 (A Motivating Constant-Function Example). To illustrate why the ordering of estimation and privacy may matter, consider the simplified setting in which there is no observation noise (σ 0 = 0 \sigma_0 = 0 σ 0 = 0 f i ( t ) ≡ c i f_i(t) \equiv c_i f i ( t ) ≡ c i ∣ c i ∣ ≤ B |c_i| \leq B ∣ c i ∣ ≤ B c ˉ = n − 1 ∑ i = 1 n c i \bar{c} = n^{-1}\sum_{i=1}^{n} c_i c ˉ = n − 1 ∑ i = 1 n c i
Under the FTP strategy, each constant function is first estimated exactly, the estimates are averaged, and a single privacy mechanism is applied to the resulting scalar mean. Since the L 1 L_1 L 1 2 B / n 2B/n 2 B / n
c ~ F T P = c ˉ + η , η ∼ Lap ( 2 B n ϵ ) , \widetilde{c}_{\mathrm{FTP}} = \bar{c} + \eta, \qquad\eta\sim\operatorname{Lap}\left(\frac{2B}{n\epsilon}\right), c FTP = c ˉ + η , η ∼ Lap ( n ϵ 2 B ) , which satisfies pure ϵ \epsilon ϵ
Under PTF, a natural implementation first computes the sample mean at each observation time, x ˉ j = n − 1 ∑ i = 1 n x i j \bar{x}_j = n^{-1}\sum_{i=1}^{n} x_{ij} x ˉ j = n − 1 ∑ i = 1 n x ij T T T
x ~ j = x ˉ j + η j , η j ∼ i . i . d . Lap ( 2 B T n ϵ ) , \widetilde{x}_j = \bar{x}_j + \eta_j, \qquad\eta_j \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \operatorname{Lap}\left(\frac{2BT}{n\epsilon}\right), x j = x ˉ j + η j , η j ∼ i.i.d. Lap ( n ϵ 2 B T ) , where the factor T T T T T T
In contrast, under μ \mu μ μ / T \mu/\sqrt{T} μ / T T \sqrt{T} T
Proofs and Technical Details
In this section, we provide the proofs and additional technical details for our theoretical results in § 4 .
Lemma 18 (Cameron-Martin Lemma, [19 ] ) Let B \mathbb{B} B Z ∼ N B ( 0 , C ) Z \sim\mathcal{N}_{\mathbb{B}}(0,C) Z ∼ N B ( 0 , C ) H C \mathcal{H}_{C} H C S : X n → B S:\mathcal{X}^{n}\to\mathbb{B} S : X n → B Z Z Z h ∈ H C h\in\mathcal{H}_{C} h ∈ H C T h T_h T h σ > 0 \sigma>0 σ > 0 Q Q Q B \mathbb{B} B σ Z \sigma Z σ Z { P X : X ∈ X n } \{P_X:X\in\mathcal{X}^{n}\} { P X : X ∈ X n } B \mathbb{B} B S ( X ) + σ Z S(X)+\sigma Z S ( X ) + σ Z P X P_X P X B \mathbb{B} B Q Q Q
d P X d Q ( y ) = exp { − 1 2 σ 2 ( ∥ S ( X ) ∥ H C 2 − 2 T S ( X ) ( y ) ) } , Q -almost everywhere . \frac{\mathrm{d}P_X}{\mathrm{d}Q}(y)=\exp\left\{-\frac{1}{2\sigma^2}\left(\lVert S(X)\rVert_{\mathcal{H}_{C}}^2-2T_{S(X)}(y)\right)\right\}, \qquad Q\text{-almost everywhere}. d Q d P X ( y ) = exp { − 2 σ 2 1 ( ∥ S ( X ) ∥ H C 2 − 2 T S ( X ) ( y ) ) } , Q -almost everywhere . Here, T h T_h T h g ↦ ⟨ h , g ⟩ H C g\mapsto\langle h,g\rangle_{\mathcal{H}_{C}} g ↦ ⟨ h , g ⟩ H C H C \mathcal{H}_{C} H C h ↦ T h h\mapsto T_h h ↦ T h T h ( Z ) ∼ N ( 0 , ∥ h ∥ H C 2 ) T_h(Z)\sim\mathcal{N}(0,\lVert h\rVert_{\mathcal{H}_{C}}^2) T h ( Z ) ∼ N ( 0 , ∥ h ∥ H C 2 ) [19 Section 2.2, Lemma 3.1] .
Proof of Theorem 6. Fix any two neighboring datasets X ∼ X ′ X\sim X' X ∼ X ′ P X P_X P X P X ′ P_{X'} P X ′ S ( X ) + σ Z S(X)+\sigma Z S ( X ) + σ Z S ( X ′ ) + σ Z S(X')+\sigma Z S ( X ′ ) + σ Z d = S ( X ′ ) − S ( X ) ∈ H C d=S(X')-S(X)\in\mathcal{H}_{C} d = S ( X ′ ) − S ( X ) ∈ H C d = 0 d=0 d = 0 P X = P X ′ P_X=P_{X'} P X = P X ′ T ( P X , P X ′ ) ( α ) = 1 − α ≥ G μ ( α ) T(P_X,P_{X'})(\alpha)=1-\alpha\ge G_{\mu}(\alpha) T ( P X , P X ′ ) ( α ) = 1 − α ≥ G μ ( α ) ∥ d ∥ H C > 0 \lVert d\rVert_{\mathcal{H}_{C}}>0 ∥ d ∥ H C > 0
By Lemma 18, the log-likelihood ratio is
L ( y ) : = log d P X ′ d P X ( y ) = log ( d P X ′ d Q ( y ) / d P X d Q ( y ) ) = − 1 2 σ 2 ( ∥ S ( X ′ ) ∥ H C 2 − ∥ S ( X ) ∥ H C 2 − 2 T d ( y ) ) = 1 σ 2 T d ( y − S ( X ) ) − ∥ d ∥ H C 2 2 σ 2 , \begin{aligned}
L(y)&:=\log\frac{\mathrm{d}P_{X'}}{\mathrm{d}P_X}(y)\\
&=\log\left(\frac{\mathrm{d}P_{X'}}{\mathrm{d}Q}(y)\bigg/\frac{\mathrm{d}P_X}{\mathrm{d}Q}(y)\right)\\
&=-\frac{1}{2\sigma^2}\left(\lVert S(X')\rVert_{\mathcal{H}_{C}}^2-\lVert S(X)\rVert_{\mathcal{H}_{C}}^2-2T_d(y)\right)\\
&=\frac{1}{\sigma^2}T_d(y-S(X))-\frac{\lVert d\rVert_{\mathcal{H}_{C}}^2}{2\sigma^2},
\end{aligned} L ( y ) := log d P X d P X ′ ( y ) = log ( d Q d P X ′ ( y ) / d Q d P X ( y ) ) = − 2 σ 2 1 ( ∥ S ( X ′ ) ∥ H C 2 − ∥ S ( X ) ∥ H C 2 − 2 T d ( y ) ) = σ 2 1 T d ( y − S ( X )) − 2 σ 2 ∥ d ∥ H C 2 , almost surely under either distribution.
Define U ( y ) = T d ( y − S ( X ) ) U(y)=T_d(y-S(X)) U ( y ) = T d ( y − S ( X )) T d T_d T d
U ( Y ) ∼ { N ( 0 , σ 2 ∥ d ∥ H C 2 ) , Y ∼ P X , N ( ∥ d ∥ H C 2 , σ 2 ∥ d ∥ H C 2 ) , Y ∼ P X ′ . U(Y)\sim
\begin{cases}
\mathcal{N}(0,\sigma^2\lVert d\rVert_{\mathcal{H}_{C}}^2), & Y\sim P_X,\\
\mathcal{N}(\lVert d\rVert_{\mathcal{H}_{C}}^2,\sigma^2\lVert d\rVert_{\mathcal{H}_{C}}^2), & Y\sim P_{X'}.
\end{cases} U ( Y ) ∼ { N ( 0 , σ 2 ∥ d ∥ H C 2 ) , N (∥ d ∥ H C 2 , σ 2 ∥ d ∥ H C 2 ) , Y ∼ P X , Y ∼ P X ′ . By the Neyman–Pearson lemma, for α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) α \alpha α
ψ ( y ) = 1 ( L ( y ) > η α ) = 1 ( U ( y ) > c α ) . \psi(y) = 1(L(y) > \eta_\alpha) = 1(U(y) > c_\alpha). ψ ( y ) = 1 ( L ( y ) > η α ) = 1 ( U ( y ) > c α ) . Thus U ( y ) U(y) U ( y ) ψ \psi ψ
α ψ = E P X [ ψ ( y ) ] = P X ( U ( y ) > c α ) = 1 − Φ ( c α σ ∥ d ∥ H C ) . \alpha_\psi= \mathbb{E}_{P_X}[\psi(y)] = P_X(U(y) > c_\alpha) = 1 - \Phi\left(\frac{c_\alpha}{\sigma\lVert d \rVert_{\mathcal{H}_C}}\right). α ψ = E P X [ ψ ( y )] = P X ( U ( y ) > c α ) = 1 − Φ ( σ ∥ d ∥ H C c α ) . When α ψ ≤ α \alpha_\psi\le\alpha α ψ ≤ α c α ≥ σ ∥ d ∥ H C Φ − 1 ( 1 − α ) c_\alpha\ge\sigma\lVert d \rVert_{\mathcal{H}_C}\Phi^{-1}(1-\alpha) c α ≥ σ ∥ d ∥ H C Φ − 1 ( 1 − α ) ψ \psi ψ
β ψ = 1 − E P X ′ [ ψ ( y ) ] = 1 − P X ′ ( U ( y ) > c α ) = Φ ( c α − ∥ d ∥ H C 2 σ ∥ d ∥ H C ) . \beta_\psi= 1 - \mathbb{E}_{P_{X'}}[\psi(y)] = 1 - P_{X'}(U(y) > c_\alpha) = \Phi\left(\frac{c_\alpha-\lVert d\rVert_{\mathcal{H}_C}^{2}}{\sigma\lVert d \rVert_{\mathcal{H}_C}}\right). β ψ = 1 − E P X ′ [ ψ ( y )] = 1 − P X ′ ( U ( y ) > c α ) = Φ ( σ ∥ d ∥ H C c α − ∥ d ∥ H C 2 ) . Combine the above results and recall ∥ d ∥ H C / σ ≤ Δ H C ( S ) / σ ≤ μ \lVert d\rVert_{\mathcal{H}_C}/\sigma\le\Delta_{\mathcal{H}_C}(S)/\sigma\le\mu ∥ d ∥ H C / σ ≤ Δ H C ( S ) / σ ≤ μ
T ( P X , P X ′ ) ( α ) = inf ψ { β ψ ∣ α ψ ≤ α } = Φ ( σ ∥ d ∥ H C Φ − 1 ( 1 − α ) − ∥ d ∥ H C 2 σ ∥ d ∥ H C ) = Φ ( Φ − 1 ( 1 − α ) − ∥ d ∥ H C σ ) ≥ Φ ( Φ − 1 ( 1 − α ) − μ ) = G μ ( α ) , \begin{aligned}
T(P_X,P_{X'})(\alpha) &= \inf_{\psi}\{\beta_\psi\mid\alpha_\psi\le\alpha\}\\
&= \Phi\left(\frac{\sigma\lVert d\rVert_{\mathcal{H}_C}\Phi^{-1}(1-\alpha)-\lVert d\rVert_{\mathcal{H}_C}^{2}}{\sigma\lVert d\rVert_{\mathcal{H}_C}}\right)\\
&= \Phi\left(\Phi^{-1}(1-\alpha)-\frac{\lVert d\rVert_{\mathcal{H}_C}}{\sigma}\right)\\
&\ge\Phi\left(\Phi^{-1}(1-\alpha)-\mu\right)=G_\mu(\alpha),
\end{aligned} T ( P X , P X ′ ) ( α ) = ψ inf { β ψ ∣ α ψ ≤ α } = Φ ( σ ∥ d ∥ H C σ ∥ d ∥ H C Φ − 1 ( 1 − α ) − ∥ d ∥ H C 2 ) = Φ ( Φ − 1 ( 1 − α ) − σ ∥ d ∥ H C ) ≥ Φ ( Φ − 1 ( 1 − α ) − μ ) = G μ ( α ) , The cases where α = 0 , 1 \alpha=0,1 α = 0 , 1 S ~ ( X ) = S ( X ) + σ Z \widetilde{S}(X)=S(X)+\sigma Z S ( X ) = S ( X ) + σ Z μ \mu μ
Proof of Corollary 7. Take B = H m \mathbb{B}=\mathcal{H}_m B = H m Z m = ∑ k = 1 m ξ k ϕ k Z_m=\sum_{k=1}^{m}\xi_k\phi_k Z m = ∑ k = 1 m ξ k ϕ k
C m ℓ = E [ ℓ ( Z m ) Z m ] = ∑ j , k = 1 m E [ ξ j ξ k ] ℓ ( ϕ j ) ϕ k = ∑ k = 1 m ℓ ( ϕ k ) ϕ k . C_m\ell=\mathbb{E}[\ell(Z_m)Z_m]=\sum_{j,k=1}^{m}\mathbb{E}[\xi_j\xi_k]\ell(\phi_j)\phi_k=\sum_{k=1}^{m}\ell(\phi_k)\phi_k. C m ℓ = E [ ℓ ( Z m ) Z m ] = j , k = 1 ∑ m E [ ξ j ξ k ] ℓ ( ϕ j ) ϕ k = k = 1 ∑ m ℓ ( ϕ k ) ϕ k . For g ∈ H m g\in\mathcal{H}_m g ∈ H m ℓ g ( f ) = ⟨ f , g ⟩ H m \ell_g(f)=\langle f,g\rangle_{\mathcal{H}_m} ℓ g ( f ) = ⟨ f , g ⟩ H m C m ℓ g = g C_m\ell_g=g C m ℓ g = g C m ( H m ∗ ) = H m C_m(\mathcal{H}_m^*)=\mathcal{H}_m C m ( H m ∗ ) = H m
⟨ C m ℓ g , C m ℓ v ⟩ H C m = ℓ g ( C m ℓ v ) = ⟨ g , v ⟩ H m . \langle C_m\ell_g,C_m\ell_v\rangle_{\mathcal{H}_{C_m}}=\ell_g(C_m\ell_v)=\langle g,v\rangle_{\mathcal{H}_m}. ⟨ C m ℓ g , C m ℓ v ⟩ H C m = ℓ g ( C m ℓ v ) = ⟨ g , v ⟩ H m . Thus H C m = H m \mathcal{H}_{C_m}=\mathcal{H}_m H C m = H m
Orthonormality gives
∥ S ( X ) − S ( X ′ ) ∥ H C m 2 = ∫ 0 1 [ ( θ ( X ) − θ ( X ′ ) ) ⊤ ϕ ( t ) ] 2 d t = ∥ θ ( X ) − θ ( X ′ ) ∥ 2 2 . \lVert S(X)-S(X')\rVert_{\mathcal{H}_{C_m}}^{2}=\int_{0}^{1}\left[(\theta(X)-\theta(X'))^{\top}\phi(t)\right]^{2}\,dt=\lVert\theta(X)-\theta(X')\rVert_{2}^{2}. ∥ S ( X ) − S ( X ′ ) ∥ H C m 2 = ∫ 0 1 [ ( θ ( X ) − θ ( X ′ ) ) ⊤ ϕ ( t ) ] 2 d t = ∥ θ ( X ) − θ ( X ′ ) ∥ 2 2 . Apply Theorem 6 with sensitivity Δ H m \Delta_{\mathcal{H}_m} Δ H m S ( X ) + σ Z m = ( θ ( X ) + σ ξ ) ⊤ ϕ S(X)+\sigma Z_m=(\theta(X)+\sigma\xi)^{\top}\phi S ( X ) + σ Z m = ( θ ( X ) + σ ξ ) ⊤ ϕ ξ ∼ N ( 0 , I m ) \xi\sim N(0,I_m) ξ ∼ N ( 0 , I m ) B ′ B' B ′ Δ H m ≤ 2 B ′ / n \Delta_{\mathcal{H}_m}\le2B'/n Δ H m ≤ 2 B ′ / n
Proof of Corollary 8. Realize the continuous version of Z K Z_K Z K B = C [ 0 , 1 ] \mathbb{B} = C[0,1] B = C [ 0 , 1 ] ℓ ∈ B ∗ \ell\in\mathbb{B}^* ℓ ∈ B ∗ ν ℓ \nu_\ell ν ℓ ℓ ( f ) = ∫ 0 1 f ( s ) ν ℓ ( d s ) \ell(f) = \int_0^1 f(s)\,\nu_\ell(ds) ℓ ( f ) = ∫ 0 1 f ( s ) ν ℓ ( d s )
( C K ℓ ) ( t ) = E [ ℓ ( Z K ) Z K ( t ) ] = ∫ 0 1 K ( t , s ) ν ℓ ( d s ) . (C_K\ell)(t) = \mathbb{E}[\ell(Z_K)Z_K(t)] = \int_0^1 K(t,s)\,\nu_\ell(ds). ( C K ℓ ) ( t ) = E [ ℓ ( Z K ) Z K ( t )] = ∫ 0 1 K ( t , s ) ν ℓ ( d s ) . Fubini’s theorem applies because K K K ν ℓ \nu_\ell ν ℓ
The kernel sections depend continuously on their location in RKHS norm, since
∥ K ( s , ⋅ ) − K ( t , ⋅ ) ∥ H K 2 = K ( s , s ) + K ( t , t ) − 2 K ( s , t ) . \lVert K(s,\cdot)-K(t,\cdot)\rVert_{\mathcal{H}_K}^2 = K(s,s)+K(t,t)-2K(s,t). ∥ K ( s , ⋅ ) − K ( t , ⋅ ) ∥ H K 2 = K ( s , s ) + K ( t , t ) − 2 K ( s , t ) . Thus C K ℓ = ∫ K ( s , ⋅ ) ν ℓ ( d s ) C_K\ell= \int K(s,\cdot)\,\nu_\ell(ds) C K ℓ = ∫ K ( s , ⋅ ) ν ℓ ( d s ) H K \mathcal{H}_K H K ℓ , g ∈ B ∗ \ell,g \in\mathbb{B}^* ℓ , g ∈ B ∗
⟨ C K ℓ , C K g ⟩ H K = ∬ K ( s , t ) ν ℓ ( d s ) ν g ( d t ) = ℓ ( C K g ) = ⟨ C K ℓ , C K g ⟩ H C K . \langle C_K\ell,C_Kg\rangle_{\mathcal{H}_K} = \iint K(s,t)\,\nu_\ell(ds)\nu_g(dt) = \ell(C_Kg) = \langle C_K\ell,C_Kg\rangle_{\mathcal{H}_{C_K}}. ⟨ C K ℓ , C K g ⟩ H K = ∬ K ( s , t ) ν ℓ ( d s ) ν g ( d t ) = ℓ ( C K g ) = ⟨ C K ℓ , C K g ⟩ H C K . The evaluation functional δ t ( f ) = f ( t ) \delta_t(f)=f(t) δ t ( f ) = f ( t ) C K δ t = K ( t , ⋅ ) C_K\delta_t=K(t,\cdot) C K δ t = K ( t , ⋅ ) C K ( B ∗ ) ⊆ H K C_K(\mathbb{B}^*)\subseteq\mathcal{H}_K C K ( B ∗ ) ⊆ H K H C K = H K \mathcal{H}_{C_K}=\mathcal{H}_K H C K = H K C [ 0 , 1 ] C[0,1] C [ 0 , 1 ] ∥ f ∥ ∞ ≤ sup t ∈ [ 0 , 1 ] K ( t , t ) ∥ f ∥ H K \lVert f\rVert_\infty\le\sup_{t\in[0,1]}\sqrt{K(t,t)}\lVert f\rVert_{\mathcal{H}_K} ∥ f ∥ ∞ ≤ sup t ∈ [ 0 , 1 ] K ( t , t ) ∥ f ∥ H K Δ H K \Delta_{\mathcal{H}_K} Δ H K Δ H K ≤ 2 B ′ / n \Delta_{\mathcal{H}_K}\le2B'/n Δ H K ≤ 2 B ′ / n ( Z K ( t 1 ) , … , Z K ( t T ) ) ⊤ ∼ N ( 0 , K T ) (Z_K(t_1),\ldots,Z_K(t_T))^\top\sim N(0,K_T) ( Z K ( t 1 ) , … , Z K ( t T ) ) ⊤ ∼ N ( 0 , K T )
Proof of Proposition 9. Since x ~ \tilde{x} x ~ μ \mu μ F P T F : X → B \mathcal{F}_{\mathrm{PTF}}:\mathcal{X}\to\mathbb{B} F PTF : X → B
Proof of Theorem 10. Denote d = θ ^ ( c ) − θ ˉ ∈ R m d=\hat{\theta}^{(c)}-\bar{\theta}\in\mathbb{R}^m d = θ ^ ( c ) − θ ˉ ∈ R m Φ \Phi Φ M = Φ ⊤ Φ M=\Phi^\top\Phi M = Φ ⊤ Φ ∥ θ i ∥ 2 ≤ B \lVert\theta_i\rVert_2\le B ∥ θ i ∥ 2 ≤ B i = 1 , … , n i=1,\ldots,n i = 1 , … , n
C B ′ : = { θ ∈ R m : ∥ θ ∥ 2 ≤ B ′ } . \mathcal{C}_{B'}:=\{\theta\in\mathbb{R}^m:\lVert\theta\rVert_2\le B'\}. C B ′ := { θ ∈ R m : ∥ θ ∥ 2 ≤ B ′ } . For each individual i i i
θ ^ i ( u ) : = arg min θ ∈ R m ∥ x i − Φ θ ∥ 2 2 . \hat{\theta}^{(u)}_i:=\mathop{\arg\min}_{\theta\in\mathbb{R}^m}\lVert x_i-\Phi\theta\rVert_2^2. θ ^ i ( u ) := arg min θ ∈ R m ∥ x i − Φ θ ∥ 2 2 . We denote the following notations for convenience:
e i = θ ^ i ( c ) − θ i , ξ i = θ ^ i ( u ) − θ i , r i = θ ^ i ( c ) − θ ^ i ( u ) , b i = E e i . e_i=\hat{\theta}^{(c)}_i-\theta_i,\qquad\xi_i=\hat{\theta}^{(u)}_i-\theta_i,\qquad r_i=\hat{\theta}^{(c)}_i-\hat{\theta}^{(u)}_i,\qquad b_i=\mathbb{E}e_i. e i = θ ^ i ( c ) − θ i , ξ i = θ ^ i ( u ) − θ i , r i = θ ^ i ( c ) − θ ^ i ( u ) , b i = E e i . It follows that e i = ξ i + r i e_i=\xi_i+r_i e i = ξ i + r i M = Φ ⊤ Φ M=\Phi^\top\Phi M = Φ ⊤ Φ θ ^ i ( u ) = M − 1 Φ ⊤ x i \hat{\theta}^{(u)}_i=M^{-1}\Phi^\top x_i θ ^ i ( u ) = M − 1 Φ ⊤ x i x i = Φ θ i + ϵ i x_i=\Phi\theta_i+\epsilon_i x i = Φ θ i + ϵ i ξ i = θ ^ i ( u ) − θ i = M − 1 Φ ⊤ ϵ i \xi_i=\hat{\theta}^{(u)}_i-\theta_i=M^{-1}\Phi^\top\epsilon_i ξ i = θ ^ i ( u ) − θ i = M − 1 Φ ⊤ ϵ i ϵ i ∼ N ( 0 , σ 0 2 I T ) \epsilon_i\sim N(0,\sigma_0^2 I_T) ϵ i ∼ N ( 0 , σ 0 2 I T ) ξ i ∼ N ( 0 , σ 0 2 M − 1 ) \xi_i\sim N(0,\sigma_0^2M^{-1}) ξ i ∼ N ( 0 , σ 0 2 M − 1 )
E ∥ ξ i ∥ 2 2 = tr [ Cov ( ξ i ) ] = σ 0 2 tr ( M − 1 ) . (14) \mathbb{E}\lVert\xi_i\rVert_2^2=\operatorname{tr}[\operatorname{Cov}(\xi_i)]=\sigma_0^2\operatorname{tr}(M^{-1}). \tag*{(14)} E ∥ ξ i ∥ 2 2 = tr [ Cov ( ξ i )] = σ 0 2 tr ( M − 1 ) . (14) We next express the constrained estimator as a metric projection.
θ ^ i ( c ) = arg min θ ∈ C B ′ ∥ x i − Φ θ ∥ 2 2 . \hat{\theta}^{(c)}_i = \mathop{\arg\min}_{\theta\in C_{B'}} \lVert x_i - \Phi\theta\rVert_2^2. θ ^ i ( c ) = arg min θ ∈ C B ′ ∥ x i − Φ θ ∥ 2 2 . Using Φ ⊤ x i = M θ ^ i ( u ) \Phi^\top x_i = M\hat{\theta}^{(u)}_i Φ ⊤ x i = M θ ^ i ( u )
∥ x i − Φ θ ∥ 2 2 = x i ⊤ x i − 2 θ ⊤ Φ ⊤ x i + θ ⊤ M θ = x i ⊤ x i − 2 θ ⊤ M θ ^ i ( u ) + θ ⊤ M θ = C i + ( θ − θ ^ i ( u ) ) ⊤ M ( θ − θ ^ i ( u ) ) , \begin{aligned}
\lVert x_i - \Phi\theta\rVert_2^2
&= x_i^\top x_i - 2\theta^\top\Phi^\top x_i + \theta^\top M\theta\\
&= x_i^\top x_i - 2\theta^\top M\hat{\theta}^{(u)}_i + \theta^\top M\theta\\
&= C_i + (\theta-\hat{\theta}^{(u)}_i)^\top M(\theta-\hat{\theta}^{(u)}_i),
\end{aligned} ∥ x i − Φ θ ∥ 2 2 = x i ⊤ x i − 2 θ ⊤ Φ ⊤ x i + θ ⊤ M θ = x i ⊤ x i − 2 θ ⊤ M θ ^ i ( u ) + θ ⊤ M θ = C i + ( θ − θ ^ i ( u ) ) ⊤ M ( θ − θ ^ i ( u ) ) , where C i = x i ⊤ x i − θ ^ i ( u ) ⊤ M θ ^ i ( u ) C_i = x_i^\top x_i - \hat{\theta}^{(u)\top}_i M\hat{\theta}^{(u)}_i C i = x i ⊤ x i − θ ^ i ( u ) ⊤ M θ ^ i ( u ) θ \theta θ
θ ^ i ( c ) = arg min θ ∈ C B ′ ( θ − θ ^ i ( u ) ) ⊤ M ( θ − θ ^ i ( u ) ) . (15) \hat{\theta}^{(c)}_i = \mathop{\arg\min}_{\theta\in C_{B'}}(\theta-\hat{\theta}^{(u)}_i)^\top M(\theta-\hat{\theta}^{(u)}_i). \tag*{(15)} θ ^ i ( c ) = arg min θ ∈ C B ′ ( θ − θ ^ i ( u ) ) ⊤ M ( θ − θ ^ i ( u ) ) . (15) Define an inner product on R m \mathbb{R}^m R m ⟨ u , v ⟩ M : = u ⊤ M v \langle u,v\rangle_M := u^\top Mv ⟨ u , v ⟩ M := u ⊤ M v u , v ∈ R m u,v \in\mathbb{R}^m u , v ∈ R m ∥ u ∥ M : = ⟨ u , u ⟩ M = u ⊤ M u \lVert u\rVert_M := \sqrt{\langle u,u\rangle_M} = \sqrt{u^\top Mu} ∥ u ∥ M := ⟨ u , u ⟩ M = u ⊤ M u ( R m , ⟨ ⋅ , ⋅ ⟩ M ) (\mathbb{R}^m,\langle\cdot,\cdot\rangle_M) ( R m , ⟨ ⋅ , ⋅ ⟩ M ) M M M (15) can therefore be written as
θ ^ i ( c ) = arg min θ ∈ C B ′ ∥ θ − θ ^ i ( u ) ∥ M 2 = P C B ′ M ( θ ^ i ( u ) ) , (16) \hat{\theta}^{(c)}_i = \mathop{\arg\min}_{\theta\in C_{B'}}\lVert\theta-\hat{\theta}^{(u)}_i\rVert_M^2 = P^M_{C_{B'}}\left(\hat{\theta}^{(u)}_i\right), \tag*{(16)} θ ^ i ( c ) = arg min θ ∈ C B ′ ∥ θ − θ ^ i ( u ) ∥ M 2 = P C B ′ M ( θ ^ i ( u ) ) , (16) where P C B ′ M P^M_{C_{B'}} P C B ′ M C B ′ C_{B'} C B ′ M M M
The set C B ′ C_{B'} C B ′ [4 ] , the metric projection onto a nonempty closed convex subset of a Hilbert space is firmly nonexpansive, and hence nonexpansive. Thus, in the Hilbert space ( R m , ⟨ ⋅ , ⋅ ⟩ M ) (\mathbb{R}^m,\langle\cdot,\cdot\rangle_M) ( R m , ⟨ ⋅ , ⋅ ⟩ M ) u , v ∈ R m u,v \in\mathbb{R}^m u , v ∈ R m
∥ P C B ′ M ( u ) − P C B ′ M ( v ) ∥ M ≤ ∥ u − v ∥ M . (17) \left\lVert P^M_{C_{B'}}(u)-P^M_{C_{B'}}(v)\right\rVert_M \leq\lVert u-v\rVert_M. \tag*{(17)} P C B ′ M ( u ) − P C B ′ M ( v ) M ≤ ∥ u − v ∥ M . (17) Since ∥ θ i ∥ 2 ≤ B ≤ B ′ \lVert\theta_i\rVert_2 \leq B \leq B' ∥ θ i ∥ 2 ≤ B ≤ B ′ θ i ∈ C B ′ \theta_i \in C_{B'} θ i ∈ C B ′ P C B ′ M ( θ i ) = θ i P^M_{C_{B'}}(\theta_i)=\theta_i P C B ′ M ( θ i ) = θ i (17) with u = θ ^ i ( u ) u=\hat{\theta}^{(u)}_i u = θ ^ i ( u ) v = θ i v=\theta_i v = θ i (16) , we obtain
∥ e i ∥ M = ∥ θ ^ i ( c ) − θ i ∥ M = ∥ P C B ′ M ( θ ^ i ( u ) ) − P C B ′ M ( θ i ) ∥ M ≤ ∥ θ ^ i ( u ) − θ i ∥ M = ∥ ξ i ∥ M . (18) \lVert e_i\rVert_M = \left\lVert\hat{\theta}^{(c)}_i-\theta_i\right\rVert_M = \left\lVert P^M_{C_{B'}}\left(\hat{\theta}^{(u)}_i\right)-P^M_{C_{B'}}(\theta_i)\right\rVert_M \leq\left\lVert\hat{\theta}^{(u)}_i-\theta_i\right\rVert_M = \lVert\xi_i\rVert_M. \tag*{(18)} ∥ e i ∥ M = θ ^ i ( c ) − θ i M = P C B ′ M ( θ ^ i ( u ) ) − P C B ′ M ( θ i ) M ≤ θ ^ i ( u ) − θ i M = ∥ ξ i ∥ M . (18) Since M M M v ∈ R m v \in\mathbb{R}^m v ∈ R m
λ min ( M ) ∥ v ∥ 2 2 ≤ ∥ v ∥ M 2 ≤ λ max ( M ) ∥ v ∥ 2 2 . (19) \lambda_{\min}(M)\lVert v\rVert_2^2 \leq\lVert v\rVert_M^2 \leq\lambda_{\max}(M)\lVert v\rVert_2^2. \tag*{(19)} λ m i n ( M ) ∥ v ∥ 2 2 ≤ ∥ v ∥ M 2 ≤ λ m a x ( M ) ∥ v ∥ 2 2 . (19) Consequently, (18) implies
λ min ( M ) ∥ e i ∥ 2 2 ≤ ∥ e i ∥ M 2 ≤ ∥ ξ i ∥ M 2 ≤ λ max ( M ) ∥ ξ i ∥ 2 2 . \lambda_{\min}(M)\lVert e_i\rVert_2^2 \leq\lVert e_i\rVert_M^2 \leq\lVert\xi_i\rVert_M^2 \leq\lambda_{\max}(M)\lVert\xi_i\rVert_2^2. λ m i n ( M ) ∥ e i ∥ 2 2 ≤ ∥ e i ∥ M 2 ≤ ∥ ξ i ∥ M 2 ≤ λ m a x ( M ) ∥ ξ i ∥ 2 2 . Therefore,
∥ e i ∥ 2 2 ≤ κ ( M ) ∥ ξ i ∥ 2 2 , (20) \lVert e_i\rVert_2^2 \leq\kappa(M)\lVert\xi_i\rVert_2^2, \tag*{(20)} ∥ e i ∥ 2 2 ≤ κ ( M ) ∥ ξ i ∥ 2 2 , (20) where κ ( M ) = λ max ( M ) / λ min ( M ) \kappa(M) = \lambda_{\max}(M)/\lambda_{\min}(M) κ ( M ) = λ m a x ( M ) / λ m i n ( M ) M M M (20) and applying (14) , we obtain
E ∥ e i ∥ 2 2 ≤ κ ( M ) σ 0 2 tr ( M − 1 ) . (21) \mathbb{E}\left\|e_i\right\|_2^2 \leq\kappa(M)\sigma_0^2\operatorname{tr}(M^{-1}). \tag*{(21)} E ∥ e i ∥ 2 2 ≤ κ ( M ) σ 0 2 tr ( M − 1 ) . (21) Denote C = κ ( M ) σ 0 2 tr ( M − 1 ) C = \kappa(M)\sigma_0^2\operatorname{tr}(M^{-1}) C = κ ( M ) σ 0 2 tr ( M − 1 ) e i e_i e i
E ∥ d ∥ 2 2 = 1 n 2 E ∥ ∑ i = 1 n e i ∥ 2 2 = 1 n 2 E ( ∑ i = 1 n ∥ e i ∥ 2 2 + ∑ i ≠ j e i T e j ) = 1 n 2 ( ∑ i = 1 n E ∥ e i ∥ 2 2 + ∑ i ≠ j E e i T E e j ) . (22) \mathbb{E}\left\|d\right\|_2^2 = \frac{1}{n^2}\mathbb{E}\left\|\sum_{i=1}^n e_i\right\|_2^2 = \frac{1}{n^2}\mathbb{E}\left(\sum_{i=1}^n\left\|e_i\right\|_2^2+\sum_{i\ne j}e_i^\mathsf{T}e_j\right) = \frac{1}{n^2}\left(\sum_{i=1}^n\mathbb{E}\left\|e_i\right\|_2^2+\sum_{i\ne j}\mathbb{E}e_i^\mathsf{T}\mathbb{E}e_j\right). \tag*{(22)} E ∥ d ∥ 2 2 = n 2 1 E i = 1 ∑ n e i 2 2 = n 2 1 E i = 1 ∑ n ∥ e i ∥ 2 2 + i = j ∑ e i T e j = n 2 1 i = 1 ∑ n E ∥ e i ∥ 2 2 + i = j ∑ E e i T E e j . (22) Recall Equation (21) , it follows that
1 n 2 ∑ i = 1 n E ∥ e i ∥ 2 2 ≤ κ ( M ) σ 0 2 tr ( M − 1 ) n . (23) \frac{1}{n^2}\sum_{i=1}^n\mathbb{E}\left\|e_i\right\|_2^2 \leq\frac{\kappa(M)\sigma_0^2\operatorname{tr}(M^{-1})}{n}. \tag*{(23)} n 2 1 i = 1 ∑ n E ∥ e i ∥ 2 2 ≤ n κ ( M ) σ 0 2 tr ( M − 1 ) . (23) Then, we only need to bound the clipping bias term.
Recall the definition of θ ^ i ( c ) \hat{\theta}_i^{(c)} θ ^ i ( c ) (16) , we have
∥ r i ∥ M = ∥ θ ^ i ( c ) − θ ^ i ( u ) ∥ M ≤ ∥ θ i − θ ^ i ( u ) ∥ M = ∥ ξ i ∥ M . \left\|r_i\right\|_M = \left\|\hat{\theta}_i^{(c)}-\hat{\theta}_i^{(u)}\right\|_M \leq\left\|\theta_i-\hat{\theta}_i^{(u)}\right\|_M = \left\|\xi_i\right\|_M. ∥ r i ∥ M = θ ^ i ( c ) − θ ^ i ( u ) M ≤ θ i − θ ^ i ( u ) M = ∥ ξ i ∥ M . Combine with Equation (19) , we have ∥ θ ^ i ( c ) − θ ^ i ( u ) ∥ 2 2 ≤ κ ( M ) ∥ θ ^ i ( u ) − θ i ∥ 2 2 \left\|\hat{\theta}_i^{(c)}-\hat{\theta}_i^{(u)}\right\|_2^2 \leq\kappa(M)\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2^2 θ ^ i ( c ) − θ ^ i ( u ) 2 2 ≤ κ ( M ) θ ^ i ( u ) − θ i 2 2 θ ^ i ( u ) \hat{\theta}_i^{(u)} θ ^ i ( u ) r i = 0 r_i=0 r i = 0 ∥ θ ^ i ( u ) ∥ 2 ≤ B ′ \left\|\hat{\theta}_i^{(u)}\right\|_2\leq B' θ ^ i ( u ) 2 ≤ B ′ r i = ( θ ^ i ( c ) − θ ^ i ( u ) ) ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } r_i=\left(\hat{\theta}_i^{(c)}-\hat{\theta}_i^{(u)}\right)\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\} r i = ( θ ^ i ( c ) − θ ^ i ( u ) ) ⋅ 1 { θ ^ i ( u ) 2 > B ′ }
∥ r i ∥ 2 2 = ∥ θ ^ i ( c ) − θ ^ i ( u ) ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } ≤ κ ( M ) ∥ θ ^ i ( u ) − θ i ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } . \left\|r_i\right\|_2^2=\left\|\hat{\theta}_i^{(c)}-\hat{\theta}_i^{(u)}\right\|_2^2\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\}\leq\kappa(M)\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2^2\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\}. ∥ r i ∥ 2 2 = θ ^ i ( c ) − θ ^ i ( u ) 2 2 ⋅ 1 { θ ^ i ( u ) 2 > B ′ } ≤ κ ( M ) θ ^ i ( u ) − θ i 2 2 ⋅ 1 { θ ^ i ( u ) 2 > B ′ } . Thus, we can obtain
∥ b i ∥ 2 2 = ∥ E e i ∥ 2 2 = ∥ E r i ∥ 2 2 ≤ E ∥ r i ∥ 2 2 ≤ κ ( M ) E [ ∥ θ ^ i ( u ) − θ i ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } ] . (24) \left\|b_i\right\|_2^2=\left\|\mathbb{E}e_i\right\|_2^2=\left\|\mathbb{E}r_i\right\|_2^2\leq\mathbb{E}\left\|r_i\right\|_2^2\leq\kappa(M)\mathbb{E}\left[\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2^2\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\}\right]. \tag*{(24)} ∥ b i ∥ 2 2 = ∥ E e i ∥ 2 2 = ∥ E r i ∥ 2 2 ≤ E ∥ r i ∥ 2 2 ≤ κ ( M ) E [ θ ^ i ( u ) − θ i 2 2 ⋅ 1 { θ ^ i ( u ) 2 > B ′ } ] . (24) By the Cauchy–Schwarz inequality, we have
E [ ∥ θ ^ i ( u ) − θ i ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } ] = E [ ∥ ξ i ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } ] ≤ E ∥ ξ i ∥ 2 4 Pr ( ∥ θ ^ i ( u ) ∥ 2 > B ′ ) . (25) \mathbb{E}\left[\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2^2\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\}\right]=\mathbb{E}\left[\left\|\xi_i\right\|_2^2\cdot\mathbf{1}\left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\}\right]\leq\sqrt{\mathbb{E}\left\|\xi_i\right\|_2^4}\sqrt{\Pr\left(\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right)}. \tag*{(25)} E [ θ ^ i ( u ) − θ i 2 2 ⋅ 1 { θ ^ i ( u ) 2 > B ′ } ] = E [ ∥ ξ i ∥ 2 2 ⋅ 1 { θ ^ i ( u ) 2 > B ′ } ] ≤ E ∥ ξ i ∥ 2 4 Pr ( θ ^ i ( u ) 2 > B ′ ) . (25) Since ξ i ∼ i . i . d . N ( 0 , Σ ) \xi_i\mathrel{\mathop{\sim}^{\mathrm{i.i.d.}}}N(0,\Sigma) ξ i ∼ i.i.d. N ( 0 , Σ ) Σ = σ 0 2 M − 1 \Sigma=\sigma_0^2M^{-1} Σ = σ 0 2 M − 1
E ∥ ξ i ∥ 2 4 = ( tr Σ ) 2 + 2 tr ( Σ 2 ) ≤ 3 ( tr Σ ) 2 = 3 σ 0 2 tr ( M − 1 ) . (26) \sqrt{\mathbb{E}\left\|\xi_i\right\|_2^4}=\sqrt{(\operatorname{tr}\Sigma)^2+2\operatorname{tr}(\Sigma^2)}\leq\sqrt{3(\operatorname{tr}\Sigma)^2}=\sqrt{3}\sigma_0^2\operatorname{tr}(M^{-1}). \tag*{(26)} E ∥ ξ i ∥ 2 4 = ( tr Σ ) 2 + 2 tr ( Σ 2 ) ≤ 3 ( tr Σ ) 2 = 3 σ 0 2 tr ( M − 1 ) . (26) Recall ∥ θ i ∥ 2 ≤ B \left\|\theta_i\right\|_2\leq B ∥ θ i ∥ 2 ≤ B δ = B ′ − B \delta=B'-B δ = B ′ − B { ∥ θ ^ i ( u ) ∥ 2 > B ′ } \left\{\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right\} { θ ^ i ( u ) 2 > B ′ } { ∥ θ ^ i ( u ) − θ i ∥ 2 > δ } \left\{\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2>\delta\right\} { θ ^ i ( u ) − θ i 2 > δ }
Pr ( ∥ θ ^ i ( u ) ∥ 2 > B ′ ) ≤ Pr ( ∥ θ ^ i ( u ) − θ i ∥ 2 > δ ) = Pr ( ∥ ξ i ∥ 2 > δ ) . \Pr\left(\left\|\hat{\theta}_i^{(u)}\right\|_2>B'\right)\leq\Pr\left(\left\|\hat{\theta}_i^{(u)}-\theta_i\right\|_2>\delta\right)=\Pr\left(\left\|\xi_i\right\|_2>\delta\right). Pr ( θ ^ i ( u ) 2 > B ′ ) ≤ Pr ( θ ^ i ( u ) − θ i 2 > δ ) = Pr ( ∥ ξ i ∥ 2 > δ ) . Let ξ i = σ 0 M − 1 / 2 Z i \xi_i = \sigma_0 M^{-1/2}Z_i ξ i = σ 0 M − 1/2 Z i Z i ∼ N ( 0 , I m ) Z_i \sim N(0,I_m) Z i ∼ N ( 0 , I m ) ∥ Z i ∥ 2 2 ∼ χ m 2 \lVert Z_i\rVert_2^2 \sim\chi_m^2 ∥ Z i ∥ 2 2 ∼ χ m 2
∥ ξ i ∥ 2 2 = σ 0 2 Z i T M − 1 Z i ≤ σ 0 2 λ max ( M − 1 ) ∥ Z i ∥ 2 2 = σ 0 2 λ min ( M ) ∥ Z i ∥ 2 2 . \lVert\xi_i\rVert_2^2 = \sigma_0^2 Z_i^{\mathsf{T}}M^{-1}Z_i \le\sigma_0^2\lambda_{\max}(M^{-1})\lVert Z_i\rVert_2^2 = \frac{\sigma_0^2}{\lambda_{\min}(M)}\lVert Z_i\rVert_2^2. ∥ ξ i ∥ 2 2 = σ 0 2 Z i T M − 1 Z i ≤ σ 0 2 λ m a x ( M − 1 ) ∥ Z i ∥ 2 2 = λ m i n ( M ) σ 0 2 ∥ Z i ∥ 2 2 . Then, we can obtain
Pr ( ∥ ξ i ∥ 2 > δ ) = Pr ( ∥ ξ i ∥ 2 2 > δ 2 ) ≤ Pr ( σ 0 2 λ min ( M ) ∥ Z i ∥ 2 2 > δ 2 ) = Pr ( χ m 2 > δ 2 λ min ( M ) σ 0 2 ) . \Pr(\lVert\xi_i\rVert_2 > \delta) = \Pr(\lVert\xi_i\rVert_2^2 > \delta^2) \le\Pr\left(\frac{\sigma_0^2}{\lambda_{\min}(M)}\lVert Z_i\rVert_2^2 > \delta^2\right) = \Pr\left(\chi_m^2 > \frac{\delta^2\lambda_{\min}(M)}{\sigma_0^2}\right). Pr (∥ ξ i ∥ 2 > δ ) = Pr (∥ ξ i ∥ 2 2 > δ 2 ) ≤ Pr ( λ m i n ( M ) σ 0 2 ∥ Z i ∥ 2 2 > δ 2 ) = Pr ( χ m 2 > σ 0 2 δ 2 λ m i n ( M ) ) . By Lemma 1 from Laurent and Massart [16 ] ,
Pr ( χ m 2 > ( m + 2 x ) 2 ) ≤ Pr ( χ m 2 > m + 2 m x + 2 x ) ≤ exp ( − x ) . (27) \Pr\left(\chi_m^2 > (\sqrt{m}+\sqrt{2x})^2\right) \le\Pr\left(\chi_m^2 > m+2\sqrt{mx}+2x\right) \le\exp(-x). \tag*{(27)} Pr ( χ m 2 > ( m + 2 x ) 2 ) ≤ Pr ( χ m 2 > m + 2 m x + 2 x ) ≤ exp ( − x ) . (27) By choosing m + 2 x = δ λ min ( M ) σ 0 \sqrt{m}+\sqrt{2x} = \frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0} m + 2 x = σ 0 δ λ m i n ( M ) δ > m σ 0 λ min ( M ) \delta> \frac{\sqrt{m}\sigma_0}{\sqrt{\lambda_{\min}(M)}} δ > λ m i n ( M ) m σ 0
Pr ( ∥ θ ^ i ( u ) ∥ 2 > B ′ ) ≤ Pr ( ∥ ξ i ∥ 2 > δ ) ≤ Pr ( χ m 2 > δ 2 λ min ( M ) σ 0 2 ) ≤ exp [ − 1 2 ( δ λ min ( M ) σ 0 − m ) 2 ] . (28) \begin{aligned}
\Pr(\lVert\hat{\theta}_i^{(u)}\rVert_2 > B') &\le\Pr(\lVert\xi_i\rVert_2 > \delta) \\
&\le\Pr\left(\chi_m^2 > \frac{\delta^2\lambda_{\min}(M)}{\sigma_0^2}\right) \\
&\le\exp\left[-\frac{1}{2}\left(\frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{m}\right)^2\right]. \tag*{(28)}
\end{aligned} Pr (∥ θ ^ i ( u ) ∥ 2 > B ′ ) ≤ Pr (∥ ξ i ∥ 2 > δ ) ≤ Pr ( χ m 2 > σ 0 2 δ 2 λ m i n ( M ) ) ≤ exp − 2 1 ( σ 0 δ λ m i n ( M ) − m ) 2 . (28) Combine (24) , (25), (26) and (28), we obtain
∥ b i ∥ 2 2 ≤ κ ( M ) E [ ∥ θ ^ i ( u ) − θ i ∥ 2 2 ⋅ 1 { ∥ θ ^ i ( u ) ∥ 2 > B ′ } ] ≤ κ ( M ) E ∥ ξ i ∥ 2 4 Pr ( ∥ θ ^ i ( u ) ∥ 2 > B ′ ) ≤ κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp [ − 1 4 ( δ λ min ( M ) σ 0 − m ) 2 ] . (29) \begin{aligned}
\lVert b_i\rVert_2^2 &\le\kappa(M)\mathbb{E}\left[\lVert\hat{\theta}_i^{(u)}-\theta_i\rVert_2^2\cdot\mathbf{1}\{\lVert\hat{\theta}_i^{(u)}\rVert_2>B'\}\right] \\
&\le\kappa(M)\sqrt{\mathbb{E}\lVert\xi_i\rVert_2^4\Pr(\lVert\hat{\theta}_i^{(u)}\rVert_2>B')} \\
&\le\kappa(M)\sqrt{3}\sigma_0^2\operatorname{tr}(M^{-1})\exp\left[-\frac{1}{4}\left(\frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{m}\right)^2\right]. \tag*{(29)}
\end{aligned} ∥ b i ∥ 2 2 ≤ κ ( M ) E [ ∥ θ ^ i ( u ) − θ i ∥ 2 2 ⋅ 1 {∥ θ ^ i ( u ) ∥ 2 > B ′ } ] ≤ κ ( M ) E ∥ ξ i ∥ 2 4 Pr (∥ θ ^ i ( u ) ∥ 2 > B ′ ) ≤ κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp − 4 1 ( σ 0 δ λ m i n ( M ) − m ) 2 . (29) By the Cauchy–Schwarz inequality, we have
1 n 2 ∑ i ≠ j E e i T e j = 1 n 2 ∑ i ≠ j b i T b j ≤ ( 1 − 1 n ) max i ∥ b i ∥ 2 2 . (30) \frac{1}{n^2}\sum_{i\ne j}\mathbb{E}e_i^{\mathsf{T}}e_j = \frac{1}{n^2}\sum_{i\ne j}b_i^{\mathsf{T}}b_j \le\left(1-\frac{1}{n}\right)\max_i\lVert b_i\rVert_2^2. \tag*{(30)} n 2 1 i = j ∑ E e i T e j = n 2 1 i = j ∑ b i T b j ≤ ( 1 − n 1 ) i max ∥ b i ∥ 2 2 . (30) Combine (22) , (23), (29) and (30), we get
E ∥ d ∥ 2 2 ≤ κ ( M ) σ 0 2 tr ( M − 1 ) n + ( 1 − 1 n ) κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp [ − 1 4 ( δ λ min ( M ) σ 0 − m ) 2 ] . (31) \mathbb{E}\lVert d\rVert_2^2 \le\frac{\kappa(M)\sigma_0^2\operatorname{tr}(M^{-1})}{n}+\left(1-\frac{1}{n}\right)\kappa(M)\sqrt{3}\sigma_0^2\operatorname{tr}(M^{-1})\exp\left[-\frac{1}{4}\left(\frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{m}\right)^2\right]. \tag*{(31)} E ∥ d ∥ 2 2 ≤ n κ ( M ) σ 0 2 tr ( M − 1 ) + ( 1 − n 1 ) κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp − 4 1 ( σ 0 δ λ m i n ( M ) − m ) 2 . (31) Finally, since θ ~ F T P = θ ^ ( c ) + Z = θ ˉ + d + Z \tilde{\theta}_{\mathrm{FTP}}=\hat{\theta}^{(c)}+Z=\bar{\theta}+d+Z θ ~ FTP = θ ^ ( c ) + Z = θ ˉ + d + Z ∫ 0 1 ϕ ( t ) ϕ ( t ) T d t = I m \int_0^1\phi(t)\phi(t)^{\mathsf{T}}dt=I_m ∫ 0 1 ϕ ( t ) ϕ ( t ) T d t = I m
IMSE F T P = E ∫ 0 1 [ θ ~ F T P T ϕ ( t ) − θ ˉ T ϕ ( t ) ] 2 d t = E ∥ d + Z ∥ 2 2 . \operatorname{IMSE}_{\mathrm{FTP}}=\mathbb{E}\int_0^1\left[\tilde{\theta}_{\mathrm{FTP}}^{\mathsf{T}}\phi(t)-\bar{\theta}^{\mathsf{T}}\phi(t)\right]^2dt=\mathbb{E}\lVert d+Z\rVert_2^2. IMSE FTP = E ∫ 0 1 [ θ ~ FTP T ϕ ( t ) − θ ˉ T ϕ ( t ) ] 2 d t = E ∥ d + Z ∥ 2 2 . Because Z ∼ N ( 0 , σ 2 I m ) Z \sim N(0,\sigma^2 I_m) Z ∼ N ( 0 , σ 2 I m ) d d d E [ Z ] = 0 \mathbb{E}[Z]=0 E [ Z ] = 0
E ∥ d + Z ∥ 2 2 = E ∥ d ∥ 2 2 + E ∥ Z ∥ 2 2 = E ∥ d ∥ 2 2 + m σ 2 . \mathbb{E}\lVert d+Z\rVert_2^2=\mathbb{E}\lVert d\rVert_2^2+\mathbb{E}\lVert Z\rVert_2^2=\mathbb{E}\lVert d\rVert_2^2+m\sigma^2. E ∥ d + Z ∥ 2 2 = E ∥ d ∥ 2 2 + E ∥ Z ∥ 2 2 = E ∥ d ∥ 2 2 + m σ 2 . With σ = 2 B ′ / ( n μ ) \sigma=2B'/(n\mu) σ = 2 B ′ / ( n μ ) m σ 2 = 4 m B ′ 2 / ( n 2 μ 2 ) m\sigma^2=4mB'^2/(n^2\mu^2) m σ 2 = 4 m B ′2 / ( n 2 μ 2 )
IMSE F T P ≤ 4 m B ′ 2 n 2 μ 2 + κ ( M ) σ 0 2 tr ( M − 1 ) n + ( 1 − 1 n ) κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp [ − 1 4 ( ( B ′ − B ) λ min ( M ) σ 0 − m ) 2 ] . (32) \operatorname{IMSE}_{\mathrm{FTP}}\leq\frac{4mB'^2}{n^2\mu^2}+\frac{\kappa(M)\sigma_0^2\operatorname{tr}(M^{-1})}{n}
+\left(1-\frac{1}{n}\right)\kappa(M)\sqrt{3}\sigma_0^2\operatorname{tr}(M^{-1})\exp\left[-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{m}\right)^2\right]. \tag*{(32)} IMSE FTP ≤ n 2 μ 2 4 m B ′2 + n κ ( M ) σ 0 2 tr ( M − 1 ) + ( 1 − n 1 ) κ ( M ) 3 σ 0 2 tr ( M − 1 ) exp − 4 1 ( σ 0 ( B ′ − B ) λ m i n ( M ) − m ) 2 . (32) When σ 0 = 0 \sigma_0=0 σ 0 = 0 B ′ ≥ B B'\geq B B ′ ≥ B Φ \Phi Φ θ ^ i ( c ) = θ i \hat{\theta}_i^{(c)}=\theta_i θ ^ i ( c ) = θ i IMSE F T P = 4 m ( B ′ ) 2 / ( n 2 μ 2 ) \operatorname{IMSE}_{\mathrm{FTP}}=4m(B')^2/(n^2\mu^2) IMSE FTP = 4 m ( B ′ ) 2 / ( n 2 μ 2 )
Proof of Theorem 11. Denote a j = ∥ ϕ ( t j ) ∥ 2 a_j=\lVert\phi(t_j)\rVert_2 a j = ∥ ϕ ( t j ) ∥ 2 σ 0 = 0 \sigma_0=0 σ 0 = 0 x i = Φ θ i x_i=\Phi\theta_i x i = Φ θ i ∥ θ i ∥ 2 ≤ B < B ′ \lVert\theta_i\rVert_2\leq B<B' ∥ θ i ∥ 2 ≤ B < B ′ i = 1 , … , n i=1,\ldots,n i = 1 , … , n
∣ x i j ∣ = ∣ ϕ ( t j ) ⊤ θ i ∣ ≤ B a j < B ′ a j = : c j . |x_{ij}|=|\phi(t_j)^\top\theta_i|\leq Ba_j<B'a_j=:c_j. ∣ x ij ∣ = ∣ ϕ ( t j ) ⊤ θ i ∣ ≤ B a j < B ′ a j =: c j . Therefore the clipping clip ( x i j , c j ) \operatorname{clip}(x_{ij},c_j) clip ( x ij , c j )
x ˉ ( c l i p ) = x ˉ = 1 n ∑ i = 1 n x i = Φ θ ˉ . \bar{x}^{(\mathrm{clip})}=\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_i=\Phi\bar{\theta}. x ˉ ( clip ) = x ˉ = n 1 i = 1 ∑ n x i = Φ θ ˉ . It follows that the released private vector can be written as x ~ = Φ θ ˉ + Z \tilde{x}=\Phi\bar{\theta}+Z x ~ = Φ θ ˉ + Z
Z ∼ N ( 0 , τ 2 W − 1 ) , τ 2 = 4 B ′ 2 T n 2 μ 2 , W = diag { a 1 − 2 , … , a T − 2 } . Z\sim N(0,\tau^2W^{-1}),\qquad\tau^2=\frac{4B'^2T}{n^2\mu^2},\qquad W=\operatorname{diag}\{a_1^{-2},\ldots,a_T^{-2}\}. Z ∼ N ( 0 , τ 2 W − 1 ) , τ 2 = n 2 μ 2 4 B ′2 T , W = diag { a 1 − 2 , … , a T − 2 } . We first analyze the corresponding unconstrained WLS estimator. By definition,
θ ~ P T F ( u ) = A − 1 Φ ⊤ W x ~ . \tilde{\theta}_{\mathrm{PTF}}^{(u)}=A^{-1}\Phi^\top W\tilde{x}. θ ~ PTF ( u ) = A − 1 Φ ⊤ W x ~ . Substituting x ~ = Φ θ ˉ + Z \tilde{x}=\Phi\bar{\theta}+Z x ~ = Φ θ ˉ + Z
θ ~ P T F ( u ) = θ ˉ + A − 1 Φ ⊤ W Z . \tilde{\theta}_{\mathrm{PTF}}^{(u)}=\bar{\theta}+A^{-1}\Phi^\top WZ. θ ~ PTF ( u ) = θ ˉ + A − 1 Φ ⊤ W Z . Since Cov ( Z ) = τ 2 W − 1 \operatorname{Cov}(Z)=\tau^2W^{-1} Cov ( Z ) = τ 2 W − 1
Cov ( θ ~ P T F ( u ) ) = A − 1 Φ ⊤ W ( τ 2 W − 1 ) W Φ A − 1 = τ 2 A − 1 Φ ⊤ W Φ A − 1 = τ 2 A − 1 . \operatorname{Cov}\left(\tilde{\theta}_{\mathrm{PTF}}^{(u)}\right)=A^{-1}\Phi^\top W(\tau^2W^{-1})W\Phi A^{-1}
=\tau^2A^{-1}\Phi^\top W\Phi A^{-1}
=\tau^2A^{-1}. Cov ( θ ~ PTF ( u ) ) = A − 1 Φ ⊤ W ( τ 2 W − 1 ) W Φ A − 1 = τ 2 A − 1 Φ ⊤ W Φ A − 1 = τ 2 A − 1 . Hence θ ~ P T F ( u ) − θ ˉ ∼ N ( 0 , τ 2 A − 1 ) \widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\sim N(0,\tau^2 A^{-1}) θ PTF ( u ) − θ ˉ ∼ N ( 0 , τ 2 A − 1 )
E ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 = τ 2 tr ( A − 1 ) . (33) \mathbb{E}\left\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\right\|_2^2=\tau^2\operatorname{tr}(A^{-1}). \tag*{(33)} E θ PTF ( u ) − θ ˉ 2 2 = τ 2 tr ( A − 1 ) . (33) We next account for the constraint ∥ θ ∥ 2 ≤ B ′ \|\theta\|_2\le B' ∥ θ ∥ 2 ≤ B ′ A = { ∥ θ ~ P T F ( u ) ∥ 2 > B ′ } \mathcal{A}=\{\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}\|_2>B'\} A = { ∥ θ PTF ( u ) ∥ 2 > B ′ } A c \mathcal{A}^c A c θ ~ P T F ( c ) = θ ~ P T F ( u ) \widetilde{\theta}_{\mathrm{PTF}}^{(c)}=\widetilde{\theta}_{\mathrm{PTF}}^{(u)} θ PTF ( c ) = θ PTF ( u )
E ∥ θ ~ P T F ( c ) − θ ˉ ∥ 2 2 = E [ ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 1 A c ] + E [ ∥ θ ~ P T F ( c ) − θ ˉ ∥ 2 2 1 A ] ≥ E [ ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 1 A c ] = E ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 − E [ ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 1 A ] . \begin{aligned}
\mathbb{E}\|\widetilde{\theta}_{\mathrm{PTF}}^{(c)}-\bar{\theta}\|_2^2=\mathbb{E}[\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2^2 1_{\mathcal{A}^c}]+\mathbb{E}[\|\widetilde{\theta}_{\mathrm{PTF}}^{(c)}-\bar{\theta}\|_2^2 1_{\mathcal{A}}] \\
&\ge\mathbb{E}[\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2^2 1_{\mathcal{A}^c}] \\
&= \mathbb{E}\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2^2-\mathbb{E}[\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2^2 1_{\mathcal{A}}].
\end{aligned} E ∥ θ PTF ( c ) − θ ˉ ∥ 2 2 = E [ ∥ θ PTF ( u ) − θ ˉ ∥ 2 2 1 A c ] + E [ ∥ θ PTF ( c ) − θ ˉ ∥ 2 2 1 A ] ≥ E [ ∥ θ PTF ( u ) − θ ˉ ∥ 2 2 1 A c ] = E ∥ θ PTF ( u ) − θ ˉ ∥ 2 2 − E [ ∥ θ PTF ( u ) − θ ˉ ∥ 2 2 1 A ] . Thus, by Equation (33) , we get
I M S E P T F ≥ τ 2 tr ( A − 1 ) − R P T F , (34) \mathrm{IMSE}_{\mathrm{PTF}}\ge\tau^2\operatorname{tr}(A^{-1})-R_{\mathrm{PTF}}, \tag*{(34)} IMSE PTF ≥ τ 2 tr ( A − 1 ) − R PTF , (34) where R P T F = E [ ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 2 1 A ] R_{\mathrm{PTF}}=\mathbb{E}[\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2^2 1_{\mathcal{A}}] R PTF = E [ ∥ θ PTF ( u ) − θ ˉ ∥ 2 2 1 A ] ξ = θ ~ P T F ( u ) − θ ˉ \xi=\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta} ξ = θ PTF ( u ) − θ ˉ ξ ∼ N ( 0 , τ 2 A − 1 ) \xi\sim N(0,\tau^2 A^{-1}) ξ ∼ N ( 0 , τ 2 A − 1 ) ∥ θ ˉ ∥ 2 ≤ B \|\bar{\theta}\|_2\le B ∥ θ ˉ ∥ 2 ≤ B A \mathcal{A} A
∥ ξ ∥ 2 = ∥ θ ~ P T F ( u ) − θ ˉ ∥ 2 ≥ ∥ θ ~ P T F ( u ) ∥ 2 − ∥ θ ˉ ∥ 2 > B ′ − B . \|\xi\|_2=\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}-\bar{\theta}\|_2\ge\|\widetilde{\theta}_{\mathrm{PTF}}^{(u)}\|_2-\|\bar{\theta}\|_2>B'-B. ∥ ξ ∥ 2 = ∥ θ PTF ( u ) − θ ˉ ∥ 2 ≥ ∥ θ PTF ( u ) ∥ 2 − ∥ θ ˉ ∥ 2 > B ′ − B . Consequently,
A ⊆ { ∥ ξ ∥ 2 > B ′ − B } . \mathcal{A}\subseteq\{\|\xi\|_2>B'-B\}. A ⊆ { ∥ ξ ∥ 2 > B ′ − B } . Write ξ = τ A − 1 / 2 z \xi=\tau A^{-1/2}z ξ = τ A − 1/2 z z ∼ N ( 0 , I m ) z\sim N(0,I_m) z ∼ N ( 0 , I m )
∥ A − 1 / 2 z ∥ 2 2 ≤ λ max ( A − 1 ) ∥ z ∥ 2 2 = ∥ z ∥ 2 2 λ min ( A ) , \|A^{-1/2}z\|_2^2\le\lambda_{\max}(A^{-1})\|z\|_2^2=\frac{\|z\|_2^2}{\lambda_{\min}(A)}, ∥ A − 1/2 z ∥ 2 2 ≤ λ m a x ( A − 1 ) ∥ z ∥ 2 2 = λ m i n ( A ) ∥ z ∥ 2 2 , we obtain
Pr ( A ) ≤ Pr ( ∥ z ∥ 2 2 > ( B ′ − B ) 2 λ min ( A ) τ 2 ) . \Pr(\mathcal{A})\le\Pr\left(\|z\|_2^2>\frac{(B'-B)^2\lambda_{\min}(A)}{\tau^2}\right). Pr ( A ) ≤ Pr ( ∥ z ∥ 2 2 > τ 2 ( B ′ − B ) 2 λ m i n ( A ) ) . Because ∥ z ∥ 2 2 ∼ χ m 2 \|z\|_2^2\sim\chi_m^2 ∥ z ∥ 2 2 ∼ χ m 2 (27) , we get
Pr ( A ) ≤ exp [ − 1 2 { ( B ′ − B ) λ min ( A ) τ − m } 2 ] . (35) \Pr(\mathcal{A})\le\exp\left[-\frac{1}{2}\left\{\frac{(B'-B)\sqrt{\lambda_{\min}(A)}}{\tau}-\sqrt{m}\right\}^2\right]. \tag*{(35)} Pr ( A ) ≤ exp − 2 1 { τ ( B ′ − B ) λ m i n ( A ) − m } 2 . (35) Finally, by the Cauchy–Schwarz inequality,
R P T F ≤ ( E ∥ ξ ∥ 2 4 ) 1 / 2 Pr ( A ) 1 / 2 . R_{\mathrm{PTF}}\le\left(\mathbb{E}\|\xi\|_2^4\right)^{1/2}\Pr(\mathcal{A})^{1/2}. R PTF ≤ ( E ∥ ξ ∥ 2 4 ) 1/2 Pr ( A ) 1/2 . For a centered Gaussian vector with covariance τ 2 A − 1 \tau^2 A^{-1} τ 2 A − 1
E ∥ ξ ∥ 2 4 = τ 4 [ { tr ( A − 1 ) } 2 + 2 tr ( A − 2 ) ] ≤ τ 4 [ 3 { tr ( A − 1 ) } 2 ] . \mathbb{E}\|\xi\|_2^4=\tau^4\left[\{\operatorname{tr}(A^{-1})\}^2+2\operatorname{tr}(A^{-2})\right]\le\tau^4\left[3\{\operatorname{tr}(A^{-1})\}^2\right]. E ∥ ξ ∥ 2 4 = τ 4 [ { tr ( A − 1 ) } 2 + 2 tr ( A − 2 ) ] ≤ τ 4 [ 3 { tr ( A − 1 ) } 2 ] . Therefore,
( E ∥ ξ ∥ 2 4 ) 1 / 2 ≤ τ 2 3 tr ( A − 1 ) . \left(\mathbb{E}\|\xi\|_2^4\right)^{1/2}\le\tau^2\sqrt{3}\operatorname{tr}(A^{-1}). ( E ∥ ξ ∥ 2 4 ) 1/2 ≤ τ 2 3 tr ( A − 1 ) . Combining this inequality with Equation (35) and Equation (34) gives Equation (10) . ■
Proof of Corollary 12. Write τ n = τ = 2 B n ′ T / ( n μ ) \tau_n=\tau=2B'_n\sqrt{T}/(n\mu) τ n = τ = 2 B n ′ T / ( n μ ) B n ′ B'_n B n ′ B n ′ > B B'_n>B B n ′ > B n n n
B n ′ − B τ n = n μ 2 T ( 1 − B B n ′ ) ⟶ ∞ . \frac{B'_n-B}{\tau_n}=\frac{n\mu}{2\sqrt{T}}\left(1-\frac{B}{B'_n}\right)\longrightarrow\infty. τ n B n ′ − B = 2 T n μ ( 1 − B n ′ B ) ⟶ ∞. Thus, the radius condition in Theorem 11 holds for all sufficiently large n n n Theorem 10 gives
lim sup n → ∞ IMSE ( f ~ F T P ) IMSE ( f ~ P T F ) ≤ m T tr ( A − 1 ) . \limsup_{n\to\infty}\frac{\operatorname{IMSE}(\widetilde{f}_{\mathrm{FTP}})}{\operatorname{IMSE}(\widetilde{f}_{\mathrm{PTF}})}\leq\frac{m}{T\operatorname{tr}(A^{-1})}. n → ∞ lim sup IMSE ( f PTF ) IMSE ( f FTP ) ≤ T tr ( A − 1 ) m . Define u j = ϕ ( t j ) / ∥ ϕ ( t j ) ∥ 2 ∈ R m u_j=\phi(t_j)/\|\phi(t_j)\|_2\in\mathbb{R}^m u j = ϕ ( t j ) /∥ ϕ ( t j ) ∥ 2 ∈ R m A j = u j u j ⊤ A_j=u_ju_j^\top A j = u j u j ⊤ A j A_j A j tr ( A j ) = 1 \operatorname{tr}(A_j)=1 tr ( A j ) = 1 W W W A = Φ ⊤ W Φ = ∑ j = 1 T A j A=\Phi^\top W\Phi=\sum_{j=1}^{T}A_j A = Φ ⊤ W Φ = ∑ j = 1 T A j tr ( A ) = T \operatorname{tr}(A)=T tr ( A ) = T λ 1 , … , λ m > 0 \lambda_1,\ldots,\lambda_m>0 λ 1 , … , λ m > 0 A A A
m T tr ( A − 1 ) = m T ∑ k = 1 m λ k − 1 ≤ ∑ k = 1 m λ k T m = 1 m . \frac{m}{T\operatorname{tr}(A^{-1})}=\frac{m}{T\sum_{k=1}^{m}\lambda_k^{-1}}\leq\frac{\sum_{k=1}^{m}\lambda_k}{Tm}=\frac{1}{m}. T tr ( A − 1 ) m = T ∑ k = 1 m λ k − 1 m ≤ T m ∑ k = 1 m λ k = m 1 . The inequality follows from the harmonic mean–arithmetic mean inequality, with equality if and only if all λ k \lambda_k λ k
Proof of Theorem 13. Let f ˉ = n − 1 ∑ i = 1 n f i \bar{f}=n^{-1}\sum_{i=1}^{n}f_i f ˉ = n − 1 ∑ i = 1 n f i K T K_T K T K T − 1 K_T^{-1} K T − 1 K T 1 / 2 K_T^{1/2} K T 1/2
a. We first show that for any f i ∈ H K f_i\in\mathcal{H}_K f i ∈ H K ∥ f i ∥ H K ≤ B \|f_i\|_{\mathcal{H}_K}\leq B ∥ f i ∥ H K ≤ B g i g_i g i { K ( t 1 , t ) , … , K ( t T , t ) } \{K(t_1,t),\ldots,K(t_T,t)\} { K ( t 1 , t ) , … , K ( t T , t )}
f i ( t j ) = g i ( t j ) , ∥ g i ∥ H K ≤ B . f_i(t_j)=g_i(t_j),\quad\|g_i\|_{\mathcal{H}_K}\leq B. f i ( t j ) = g i ( t j ) , ∥ g i ∥ H K ≤ B . For each i i i
g i = argmin g ∈ H K { ∥ g ∥ H K : g ( t j ) = f i ( t j ) , j = 1 , … , T } . g_i=\underset{g\in\mathcal{H}_K}{\operatorname{argmin}}\left\{\|g\|_{\mathcal{H}_K}:g(t_j)=f_i(t_j),\ j=1,\ldots,T\right\}. g i = g ∈ H K argmin { ∥ g ∥ H K : g ( t j ) = f i ( t j ) , j = 1 , … , T } . By the representer theorem,
g i ( t ) = ∑ j = 1 T ( γ i ) j K ( t j , t ) , γ i = K T − 1 f i . g_i(t)=\sum_{j=1}^{T}(\gamma_i)_jK(t_j,t),\quad\gamma_i=K_T^{-1}f_i. g i ( t ) = j = 1 ∑ T ( γ i ) j K ( t j , t ) , γ i = K T − 1 f i . Hence
∥ g i ∥ H K 2 = γ i ⊤ K T γ i = f i ⊤ K T − 1 f i . \|g_i\|_{\mathcal{H}_K}^{2}=\gamma_i^\top K_T\gamma_i=f_i^\top K_T^{-1}f_i. ∥ g i ∥ H K 2 = γ i ⊤ K T γ i = f i ⊤ K T − 1 f i . Since f i f_i f i
∥ g i ∥ H K ≤ ∥ f i ∥ H K ≤ B . \|g_i\|_{\mathcal{H}_K}\leq\|f_i\|_{\mathcal{H}_K}\leq B. ∥ g i ∥ H K ≤ ∥ f i ∥ H K ≤ B . Therefore,
f i T K T − 1 f i ≤ B 2 . (36) f_i^{\mathsf{T}}K_T^{-1}f_i \le B^2. \tag*{(36)} f i T K T − 1 f i ≤ B 2 . (36) Define
β i : = K T − 1 / 2 f i . \beta_i := K_T^{-1/2}f_i. β i := K T − 1/2 f i . Then Equation (36) gives
∥ g i ∥ H K = ∥ β i ∥ 2 ≤ B . (37) \lVert g_i\rVert_{\mathcal{H}_K}=\lVert\beta_i\rVert_2\le B. \tag*{(37)} ∥ g i ∥ H K = ∥ β i ∥ 2 ≤ B . (37) b. We then derive the form of the constrained and unconstrained solution to
f ^ i ( c ) = argmin ∥ f ∥ H K ≤ B ′ 1 T ∑ j = 1 T [ x i j − f ( t j ) ] 2 . (38) \hat{f}_i^{(c)}=\underset{\lVert f\rVert_{\mathcal{H}_K}\le B'}{\operatorname{argmin}}\ \frac{1}{T}\sum_{j=1}^{T}[x_{ij}-f(t_j)]^2. \tag*{(38)} f ^ i ( c ) = ∥ f ∥ H K ≤ B ′ argmin T 1 j = 1 ∑ T [ x ij − f ( t j ) ] 2 . (38) and perform coefficient transformation for the convenience of following proof. By the Representer theorem, the constrained estimator has the form
f ^ i ( c ) ( t ) = ∑ j = 1 T ( α ^ i ( c ) ) j K ( t j , t ) , \hat{f}_i^{(c)}(t)=\sum_{j=1}^{T}(\hat{\alpha}_i^{(c)})_jK(t_j,t), f ^ i ( c ) ( t ) = j = 1 ∑ T ( α ^ i ( c ) ) j K ( t j , t ) , and its RKHS norm satisfies
∥ f ^ i ( c ) ∥ H K 2 = ( α ^ i ( c ) ) T K T α ^ i ( c ) . \lVert\hat{f}_i^{(c)}\rVert_{\mathcal{H}_K}^2=(\hat{\alpha}_i^{(c)})^{\mathsf{T}}K_T\hat{\alpha}_i^{(c)}. ∥ f ^ i ( c ) ∥ H K 2 = ( α ^ i ( c ) ) T K T α ^ i ( c ) . Consequently, Equation (38) is equivalent to
α ^ i ( c ) = argmin α T K T α ≤ B ′ 2 ∥ x i − K T α ∥ 2 2 . (39) \hat{\alpha}_i^{(c)}=\underset{\alpha^{\mathsf{T}}K_T\alpha\le B'^2}{\operatorname{argmin}}\ \lVert x_i-K_T\alpha\rVert_2^2. \tag*{(39)} α ^ i ( c ) = α T K T α ≤ B ′2 argmin ∥ x i − K T α ∥ 2 2 . (39) Consider the corresponding unconstrained estimator
f ^ i ( u ) = argmin f ∈ H K 1 T ∑ j = 1 T [ x i j − f ( t j ) ] 2 . \hat{f}_i^{(u)}=\underset{f\in\mathcal{H}_K}{\operatorname{argmin}}\ \frac{1}{T}\sum_{j=1}^{T}[x_{ij}-f(t_j)]^2. f ^ i ( u ) = f ∈ H K argmin T 1 j = 1 ∑ T [ x ij − f ( t j ) ] 2 . The minimum-norm unconstrained least-squares solution has the form
f ^ i ( u ) ( t ) = ∑ j = 1 T [ α ^ i ( u ) ] j K ( t j , t ) , α ^ i ( u ) = K T − 1 x i . (40) \begin{aligned}
\hat{f}_i^{(u)}(t)&=\sum_{j=1}^{T}[\hat{\alpha}_i^{(u)}]_jK(t_j,t),\\
\hat{\alpha}_i^{(u)}&=K_T^{-1}x_i. \tag*{(40)}
\end{aligned} f ^ i ( u ) ( t ) α ^ i ( u ) = j = 1 ∑ T [ α ^ i ( u ) ] j K ( t j , t ) , = K T − 1 x i . (40) Indeed, the fitted-value vector is
f ^ i ( u ) = K T α ^ i ( u ) = x i . \hat{f}_i^{(u)}=K_T\hat{\alpha}_i^{(u)}=x_i. f ^ i ( u ) = K T α ^ i ( u ) = x i . Define
β ^ i ( u ) : = K T 1 / 2 α ^ i ( u ) = K T − 1 / 2 x i and β ^ : = K T 1 / 2 α . \hat{\beta}_i^{(u)}:=K_T^{1/2}\hat{\alpha}_i^{(u)}=K_T^{-1/2}x_i\quad\text{and}\quad\hat{\beta}:=K_T^{1/2}\alpha. β ^ i ( u ) := K T 1/2 α ^ i ( u ) = K T − 1/2 x i and β ^ := K T 1/2 α . We have
α T K T α ≤ B ′ 2 ⟺ ∥ β ∥ 2 = ∥ K T 1 / 2 α ∥ 2 ≤ B ′ . \alpha^{\mathsf{T}}K_T\alpha\le B'^2\Longleftrightarrow\lVert\beta\rVert_2=\lVert K_T^{1/2}\alpha\rVert_2\le B'. α T K T α ≤ B ′2 ⟺ ∥ β ∥ 2 = ∥ K T 1/2 α ∥ 2 ≤ B ′ . Hence, we can rewrite the optimization problem in Equation (39) as
β ^ i ( c ) = arg min ∥ β ∥ 2 ≤ B ′ ∥ x i − K T 1 / 2 β ∥ 2 2 , β ^ i ( c ) = K T 1 / 2 α ^ i ( c ) . (41) \hat{\beta}_i^{(c)}=\underset{\|\beta\|_2\leq B'}{\arg\min}\left\|x_i-K_T^{1/2}\beta\right\|_2^2,\qquad\hat{\beta}_i^{(c)}=K_T^{1/2}\hat{\alpha}_i^{(c)}. \tag*{(41)} β ^ i ( c ) = ∥ β ∥ 2 ≤ B ′ arg min x i − K T 1/2 β 2 2 , β ^ i ( c ) = K T 1/2 α ^ i ( c ) . (41) It follows
f ^ i ( c ) ( t ) = ∑ j = 1 T ( α ^ i ( c ) ) j K ( t j , t ) = ∑ j = 1 T ( K T − 1 / 2 β ^ i ( c ) ) j K ( t j , t ) . \hat{f}_i^{(c)}(t)=\sum_{j=1}^{T}(\hat{\alpha}_i^{(c)})_jK(t_j,t)=\sum_{j=1}^{T}(K_T^{-1/2}\hat{\beta}_i^{(c)})_jK(t_j,t). f ^ i ( c ) ( t ) = j = 1 ∑ T ( α ^ i ( c ) ) j K ( t j , t ) = j = 1 ∑ T ( K T − 1/2 β ^ i ( c ) ) j K ( t j , t ) . c. Next, we introduce the metric projection and follow similar steps in the proof of Theorem 10.
Denote
C B ′ : = { β ∈ R T : ∥ β ∥ 2 ≤ B ′ } . C_{B'}:=\{\beta\in\mathbb{R}^{T}:\|\beta\|_2\leq B'\}. C B ′ := { β ∈ R T : ∥ β ∥ 2 ≤ B ′ } . By substituting Φ = K T 1 / 2 \Phi=K_T^{1/2} Φ = K T 1/2 M = Φ T Φ = Φ 2 = K T M=\Phi^{\mathsf{T}}\Phi=\Phi^2=K_T M = Φ T Φ = Φ 2 = K T
β ^ i ( c ) = arg min β ∈ C B ′ ( β − β ^ i ( u ) ) T M ( β − β ^ i ( u ) ) : = P C B ′ M ( β ^ i ( u ) ) . (42) \hat{\beta}_i^{(c)}=\underset{\beta\in C_{B'}}{\arg\min}(\beta-\hat{\beta}_i^{(u)})^{\mathsf{T}}M(\beta-\hat{\beta}_i^{(u)}):=P_{C_{B'}}^{M}\left(\hat{\beta}_i^{(u)}\right). \tag*{(42)} β ^ i ( c ) = β ∈ C B ′ arg min ( β − β ^ i ( u ) ) T M ( β − β ^ i ( u ) ) := P C B ′ M ( β ^ i ( u ) ) . (42) where P C B ′ M P_{C_{B'}}^{M} P C B ′ M C B ′ C_{B'} C B ′ M M M
Since the projection is nonexpansive, and ∥ β i ∥ 2 ≤ B ≤ B ′ \|\beta_i\|_2\leq B\leq B' ∥ β i ∥ 2 ≤ B ≤ B ′
∥ β ^ i ( c ) − β i ∥ M = ∥ P C B ′ M ( β ^ i ( u ) ) − P C B ′ M ( β i ) ∥ M ≤ ∥ β ^ i ( u ) − β i ∥ M . (43) \left\|\hat{\beta}_i^{(c)}-\beta_i\right\|_M=\left\|P_{C_{B'}}^{M}\left(\hat{\beta}_i^{(u)}\right)-P_{C_{B'}}^{M}(\beta_i)\right\|_M\leq\left\|\hat{\beta}_i^{(u)}-\beta_i\right\|_M. \tag*{(43)} β ^ i ( c ) − β i M = P C B ′ M ( β ^ i ( u ) ) − P C B ′ M ( β i ) M ≤ β ^ i ( u ) − β i M . (43) d. We denote convenient notations as follows
e i = β ^ i ( c ) − β i , ξ i = β ^ i ( u ) − β i , r i = β ^ i ( c ) − β ^ i ( u ) , b i = E e i . (44) e_i=\hat{\beta}_i^{(c)}-\beta_i,\qquad\xi_i=\hat{\beta}_i^{(u)}-\beta_i,\qquad r_i=\hat{\beta}_i^{(c)}-\hat{\beta}_i^{(u)},\qquad b_i=\mathbb{E}e_i. \tag*{(44)} e i = β ^ i ( c ) − β i , ξ i = β ^ i ( u ) − β i , r i = β ^ i ( c ) − β ^ i ( u ) , b i = E e i . (44) Then Equation (43) becomes
∥ e i ∥ M ≤ ∥ ξ i ∥ M . (45) \|e_i\|_M\leq\|\xi_i\|_M. \tag*{(45)} ∥ e i ∥ M ≤ ∥ ξ i ∥ M . (45) Since
x i = f i + ϵ i , ϵ i ∼ N ( 0 , σ 0 2 I T ) , x_i=f_i+\epsilon_i,\qquad\epsilon_i\sim N(0,\sigma_0^2I_T), x i = f i + ϵ i , ϵ i ∼ N ( 0 , σ 0 2 I T ) , we have
β i ( u ) = K T − 1 / 2 x i = Φ − 1 x i = β i + ξ i , \beta_i^{(u)}=K_T^{-1/2}x_i=\Phi^{-1}x_i=\beta_i+\xi_i, β i ( u ) = K T − 1/2 x i = Φ − 1 x i = β i + ξ i , where
ξ i = Φ − 1 ϵ i , ξ i ∼ N ( 0 , σ 0 2 M − 1 ) . \xi_i=\Phi^{-1}\epsilon_i,\qquad\xi_i\sim N(0,\sigma_0^2M^{-1}). ξ i = Φ − 1 ϵ i , ξ i ∼ N ( 0 , σ 0 2 M − 1 ) . Consequently,
E ∥ ξ i ∥ 2 2 = tr [ Cov ( ξ i ) ] = σ 0 2 tr ( M − 1 ) , E ∥ ϵ i ∥ 2 2 = σ 0 2 T . (46) \mathbb{E}\|\xi_i\|_2^2=\operatorname{tr}[\operatorname{Cov}(\xi_i)]=\sigma_0^2\operatorname{tr}(M^{-1}),\qquad\mathbb{E}\|\epsilon_i\|_2^2=\sigma_0^2T. \tag*{(46)} E ∥ ξ i ∥ 2 2 = tr [ Cov ( ξ i )] = σ 0 2 tr ( M − 1 ) , E ∥ ϵ i ∥ 2 2 = σ 0 2 T . (46) Then we can expand the MSE as
MSE F T P = 1 T ∑ j = 1 T E [ ( f ~ F T P ( t j ) − f ˉ ( t j ) ) 2 ] = 1 T E ∥ f ~ F T P − f ˉ ∥ 2 2 = 1 T E ∥ f ^ ( c ) − f ˉ + σ Z ∥ 2 2 . (47) \begin{aligned}
\operatorname{MSE}_{\mathrm{FTP}}&=\frac{1}{T}\sum_{j=1}^{T}\mathbb{E}[(\tilde{f}_{\mathrm{FTP}}(t_j)-\bar{f}(t_j))^2]\\
&=\frac{1}{T}\mathbb{E}\|\tilde{\mathbf{f}}_{\mathrm{FTP}}-\bar{\mathbf{f}}\|_2^2\\
&=\frac{1}{T}\mathbb{E}\|\hat{\mathbf{f}}^{(c)}-\bar{\mathbf{f}}+\sigma Z\|_2^2. \tag*{(47)}
\end{aligned} MSE FTP = T 1 j = 1 ∑ T E [( f ~ FTP ( t j ) − f ˉ ( t j ) ) 2 ] = T 1 E ∥ f ~ FTP − f ˉ ∥ 2 2 = T 1 E ∥ f ^ ( c ) − f ˉ + σ Z ∥ 2 2 . (47) Notice that Z Z Z K K K
Z = ( Z ( t 1 ) , … , Z ( t T ) ) T ∼ N ( 0 , M ) , \mathbf{Z} = (Z(t_1), \ldots, Z(t_T))^{\mathsf{T}} \sim\mathcal{N}(0,M), Z = ( Z ( t 1 ) , … , Z ( t T ) ) T ∼ N ( 0 , M ) , E ∥ Z ∥ 2 2 = tr ( M ) . \mathbb{E}\|\mathbf{Z}\|_2^2 = \operatorname{tr}(M). E ∥ Z ∥ 2 2 = tr ( M ) . Thus, we have
MSE F T P = 1 T E ∥ f ^ ( c ) − f ˉ + σ Z ∥ 2 2 = 1 T ( E ∥ f ^ ( c ) − f ˉ ∥ 2 2 + E ∥ σ Z ∥ 2 2 + 0 ) = 1 T E ∥ f ^ ( c ) − f ˉ ∥ 2 2 + 4 B ′ 2 n 2 μ 2 T tr ( M ) . (48) \begin{aligned}
\operatorname{MSE}_{\mathrm{FTP}} &= \frac{1}{T}\mathbb{E}\|\widehat{\mathbf{f}}^{(c)}-\bar{\mathbf{f}}+\sigma\mathbf{Z}\|_2^2\\
&= \frac{1}{T}\left(\mathbb{E}\|\widehat{\mathbf{f}}^{(c)}-\bar{\mathbf{f}}\|_2^2+\mathbb{E}\|\sigma\mathbf{Z}\|_2^2+0\right)\\
&= \frac{1}{T}\mathbb{E}\|\widehat{\mathbf{f}}^{(c)}-\bar{\mathbf{f}}\|_2^2+\frac{4B^{\prime2}}{n^2\mu^2T}\operatorname{tr}(M). \tag*{(48)}
\end{aligned} MSE FTP = T 1 E ∥ f ( c ) − f ˉ + σ Z ∥ 2 2 = T 1 ( E ∥ f ( c ) − f ˉ ∥ 2 2 + E ∥ σ Z ∥ 2 2 + 0 ) = T 1 E ∥ f ( c ) − f ˉ ∥ 2 2 + n 2 μ 2 T 4 B ′2 tr ( M ) . (48) Note that e i e_i e i
E ∥ f ^ ( c ) − f ˉ ∥ 2 2 = E ∥ f ^ ( c ) − g ˉ ∥ 2 2 = E ∥ Φ β ^ ( c ) − Φ β ˉ ∥ 2 2 = E ∥ β ^ ( c ) − β ˉ ∥ M 2 = 1 n 2 E ( ∑ i = 1 n ∥ e i ∥ M 2 + ∑ i ≠ j e i T M e j ) = 1 n 2 ( ∑ i = 1 n E ∥ e i ∥ M 2 + ∑ i ≠ j E e i T M e j ) . (49) \begin{aligned}
\mathbb{E}\|\widehat{\mathbf{f}}^{(c)}-\bar{\mathbf{f}}\|_2^2
&= \mathbb{E}\|\widehat{\mathbf{f}}^{(c)}-\bar{\mathbf{g}}\|_2^2\\
&= \mathbb{E}\|\Phi\widehat{\boldsymbol{\beta}}^{(c)}-\Phi\bar{\boldsymbol{\beta}}\|_2^2\\
&= \mathbb{E}\|\widehat{\boldsymbol{\beta}}^{(c)}-\bar{\boldsymbol{\beta}}\|_M^2\\
&= \frac{1}{n^2}\mathbb{E}\left(\sum_{i=1}^{n}\|e_i\|_M^2+\sum_{i\ne j}e_i^{\mathsf{T}}Me_j\right)\\
&= \frac{1}{n^2}\left(\sum_{i=1}^{n}\mathbb{E}\|e_i\|_M^2+\sum_{i\ne j}\mathbb{E}e_i^{\mathsf{T}}Me_j\right). \tag*{(49)}
\end{aligned} E ∥ f ( c ) − f ˉ ∥ 2 2 = E ∥ f ( c ) − g ˉ ∥ 2 2 = E ∥Φ β ( c ) − Φ β ˉ ∥ 2 2 = E ∥ β ( c ) − β ˉ ∥ M 2 = n 2 1 E i = 1 ∑ n ∥ e i ∥ M 2 + i = j ∑ e i T M e j = n 2 1 i = 1 ∑ n E ∥ e i ∥ M 2 + i = j ∑ E e i T M e j . (49) Recall Equation (45) and Equation (46) , we have
1 n 2 ∑ i = 1 n E ∥ e i ∥ M 2 ≤ 1 n 2 ∑ i = 1 n E ∥ ξ i ∥ M 2 = 1 n 2 ∑ i = 1 n E ∥ e i ∥ 2 2 = σ 0 2 T n . (50) \frac{1}{n^2}\sum_{i=1}^{n}\mathbb{E}\|e_i\|_M^2
\le\frac{1}{n^2}\sum_{i=1}^{n}\mathbb{E}\|\xi_i\|_M^2
= \frac{1}{n^2}\sum_{i=1}^{n}\mathbb{E}\|e_i\|_2^2
= \frac{\sigma_0^2T}{n}. \tag*{(50)} n 2 1 i = 1 ∑ n E ∥ e i ∥ M 2 ≤ n 2 1 i = 1 ∑ n E ∥ ξ i ∥ M 2 = n 2 1 i = 1 ∑ n E ∥ e i ∥ 2 2 = n σ 0 2 T . (50) e. Finally, we analyze the cross-term.
Recall the definition of β ^ i ( c ) \widehat{\beta}_i^{(c)} β i ( c ) (42) , we have
∥ r i ∥ M = ∥ β ^ i ( c ) − β ^ i ( u ) ∥ M ≤ ∥ β i − β ^ i ( u ) ∥ M = ∥ ξ i ∥ M . (51) \|r_i\|_M=\|\widehat{\beta}_i^{(c)}-\widehat{\beta}_i^{(u)}\|_M\le\|\beta_i-\widehat{\beta}_i^{(u)}\|_M=\|\xi_i\|_M. \tag*{(51)} ∥ r i ∥ M = ∥ β i ( c ) − β i ( u ) ∥ M ≤ ∥ β i − β i ( u ) ∥ M = ∥ ξ i ∥ M . (51) Since β ^ i ( u ) \widehat{\beta}_i^{(u)} β i ( u ) r i = 0 r_i=0 r i = 0 ∥ β ^ i ( u ) ∥ 2 ≤ B ′ \|\widehat{\beta}_i^{(u)}\|_2\le B^{\prime} ∥ β i ( u ) ∥ 2 ≤ B ′
r i = ( β ^ i ( c ) − β ^ i ( u ) ) ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } . r_i=\left(\widehat{\beta}_i^{(c)}-\widehat{\beta}_i^{(u)}\right)\cdot\mathbf{1}\left\{\|\widehat{\beta}_i^{(u)}\|_2>B^{\prime}\right\}. r i = ( β i ( c ) − β i ( u ) ) ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } . It follows that
∥ r i ∥ M 2 = ∥ β ^ i ( c ) − β ^ i ( u ) ∥ M 2 ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } ≤ ∥ ξ i ∥ M 2 ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } = ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } . \begin{aligned}
\|r_i\|_M^2
&=\|\widehat{\beta}_i^{(c)}-\widehat{\beta}_i^{(u)}\|_M^2\cdot\mathbf{1}\left\{\|\widehat{\beta}_i^{(u)}\|_2>B^{\prime}\right\}\\
&\le\|\xi_i\|_M^2\cdot\mathbf{1}\left\{\|\widehat{\beta}_i^{(u)}\|_2>B^{\prime}\right\}\\
&=\|\epsilon_i\|_2^2\cdot\mathbf{1}\left\{\|\widehat{\beta}_i^{(u)}\|_2>B^{\prime}\right\}.
\end{aligned} ∥ r i ∥ M 2 = ∥ β i ( c ) − β i ( u ) ∥ M 2 ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } ≤ ∥ ξ i ∥ M 2 ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } = ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } . Thus, we can obtain that
∥ b i ∥ M 2 = ∥ E e i ∥ M 2 = ∥ E r i ∥ M 2 ≤ E ∥ r i ∥ M 2 ≤ E [ ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } ] . (52) \lVert b_i\rVert_M^2 = \lVert E e_i\rVert_M^2 = \lVert E r_i\rVert_M^2 \le\mathbb{E}\lVert r_i\rVert_M^2 \le\mathbb{E}\left[\lVert\epsilon_i\rVert_2^2 \cdot1\left\{\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B'\right\}\right]. \tag*{(52)} ∥ b i ∥ M 2 = ∥ E e i ∥ M 2 = ∥ E r i ∥ M 2 ≤ E ∥ r i ∥ M 2 ≤ E [ ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } ] . (52) By the Cauchy–Schwarz inequality, we have
E [ ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β ^ i ( u ) ∥ 2 > B ′ } ] ≤ E ∥ ϵ i ∥ 2 4 Pr ( ∥ β ^ i ( u ) ∥ 2 > B ′ ) . (53) \mathbb{E}\left[\lVert\epsilon_i\rVert_2^2 \cdot1\left\{\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B'\right\}\right] \le\sqrt{\mathbb{E}\lVert\epsilon_i\rVert_2^4}\sqrt{\Pr(\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B')}. \tag*{(53)} E [ ∥ ϵ i ∥ 2 2 ⋅ 1 { ∥ β i ( u ) ∥ 2 > B ′ } ] ≤ E ∥ ϵ i ∥ 2 4 Pr (∥ β i ( u ) ∥ 2 > B ′ ) . (53) Since ϵ i ∼ i . i . d . N ( 0 , Σ ) \epsilon_i \overset{i.i.d.}{\sim} N(0,\Sigma) ϵ i ∼ i . i . d . N ( 0 , Σ ) Σ = σ 0 2 I T \Sigma= \sigma_0^2 I_T Σ = σ 0 2 I T
E ∥ ϵ i ∥ 2 4 = ( tr Σ ) 2 + 2 tr ( Σ 2 ) = σ 0 2 T 2 + 2 T . (54) \sqrt{\mathbb{E}\lVert\epsilon_i\rVert_2^4} = \sqrt{(\operatorname{tr}\Sigma)^2 + 2\operatorname{tr}(\Sigma^2)} = \sigma_0^2\sqrt{T^2 + 2T}. \tag*{(54)} E ∥ ϵ i ∥ 2 4 = ( tr Σ ) 2 + 2 tr ( Σ 2 ) = σ 0 2 T 2 + 2 T . (54) Recall ∥ β i ∥ 2 ≤ B \lVert\beta_i\rVert_2 \le B ∥ β i ∥ 2 ≤ B δ = B ′ − B \delta= B' - B δ = B ′ − B { ∥ β ^ i ( u ) ∥ 2 > B ′ } \left\{\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B'\right\} { ∥ β i ( u ) ∥ 2 > B ′ } { ∥ β ^ i ( u ) − β i ∥ 2 > δ } \left\{\lVert\widehat{\beta}_i^{(u)}-\beta_i\rVert_2 > \delta\right\} { ∥ β i ( u ) − β i ∥ 2 > δ }
Pr ( ∥ β ^ i ( u ) ∥ 2 > B ′ ) ≤ Pr ( ∥ β ^ i ( u ) − β i ∥ 2 > δ ) = Pr ( ∥ ξ i ∥ 2 > δ ) . \Pr(\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B') \le\Pr(\lVert\widehat{\beta}_i^{(u)}-\beta_i\rVert_2 > \delta)
= \Pr(\lVert\xi_i\rVert_2 > \delta). Pr (∥ β i ( u ) ∥ 2 > B ′ ) ≤ Pr (∥ β i ( u ) − β i ∥ 2 > δ ) = Pr (∥ ξ i ∥ 2 > δ ) . Let ξ i = σ 0 M − 1 / 2 Z i \xi_i = \sigma_0 M^{-1/2}Z_i ξ i = σ 0 M − 1/2 Z i Z i ∼ N ( 0 , I T ) Z_i \sim N(0,I_T) Z i ∼ N ( 0 , I T ) ∥ Z i ∥ 2 2 ∼ χ T 2 \lVert Z_i\rVert_2^2 \sim\chi_T^2 ∥ Z i ∥ 2 2 ∼ χ T 2
∥ ξ i ∥ 2 2 = σ 0 2 Z i T M − 1 Z i ≤ σ 0 2 λ max ( M − 1 ) ∥ Z i ∥ 2 2 = σ 0 2 λ min ( M ) ∥ Z i ∥ 2 2 . \lVert\xi_i\rVert_2^2 = \sigma_0^2 Z_i^{\mathsf{T}}M^{-1}Z_i \le\sigma_0^2\lambda_{\max}(M^{-1})\lVert Z_i\rVert_2^2 = \frac{\sigma_0^2}{\lambda_{\min}(M)}\lVert Z_i\rVert_2^2. ∥ ξ i ∥ 2 2 = σ 0 2 Z i T M − 1 Z i ≤ σ 0 2 λ m a x ( M − 1 ) ∥ Z i ∥ 2 2 = λ m i n ( M ) σ 0 2 ∥ Z i ∥ 2 2 . Apply the χ 2 \chi^2 χ 2 [16 ] , we have
Pr ( ∥ β ^ i ( u ) ∥ 2 > B ′ ) ≤ Pr ( ∥ ξ i ∥ 2 > δ ) ≤ Pr ( χ T 2 > δ 2 λ min ( M ) σ 0 2 ) ≤ exp [ − 1 2 ( δ λ min ( M ) σ 0 − T ) 2 ] . (55) \begin{aligned}
\Pr(\lVert\widehat{\beta}_i^{(u)}\rVert_2 > B') &\le\Pr(\lVert\xi_i\rVert_2 > \delta) \\
&\le\Pr\left(\chi_T^2 > \frac{\delta^2\lambda_{\min}(M)}{\sigma_0^2}\right) \\
&\le\exp\left[-\frac{1}{2}\left(\frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{T}\right)^2\right]. \tag*{(55)}
\end{aligned} Pr (∥ β i ( u ) ∥ 2 > B ′ ) ≤ Pr (∥ ξ i ∥ 2 > δ ) ≤ Pr ( χ T 2 > σ 0 2 δ 2 λ m i n ( M ) ) ≤ exp − 2 1 ( σ 0 δ λ m i n ( M ) − T ) 2 . (55) Combine Equation (52), (53), (54) and (55), we obtain
∥ b i ∥ M 2 ≤ σ 0 2 T 2 + 2 T ⋅ exp [ − 1 4 ( δ λ min ( M ) σ 0 − T ) 2 ] . (56) \lVert b_i\rVert_M^2 \le\sigma_0^2\sqrt{T^2+2T}\cdot\exp\left[-\frac{1}{4}\left(\frac{\delta\sqrt{\lambda_{\min}(M)}}{\sigma_0}-\sqrt{T}\right)^2\right]. \tag*{(56)} ∥ b i ∥ M 2 ≤ σ 0 2 T 2 + 2 T ⋅ exp − 4 1 ( σ 0 δ λ m i n ( M ) − T ) 2 . (56) By the Cauchy–Schwarz inequality, we have
1 n 2 ∑ i ≠ j E e i T M E e j = 1 n 2 ∑ i ≠ j b i T M b j ≤ ( 1 − 1 n ) max i ∥ b i ∥ M 2 . (57) \frac{1}{n^2}\sum_{i\ne j} E e_i^{\mathsf{T}} M E e_j = \frac{1}{n^2}\sum_{i\ne j} b_i^{\mathsf{T}} M b_j \le\left(1-\frac{1}{n}\right)\max_i\lVert b_i\rVert_M^2. \tag*{(57)} n 2 1 i = j ∑ E e i T M E e j = n 2 1 i = j ∑ b i T M b j ≤ ( 1 − n 1 ) i max ∥ b i ∥ M 2 . (57) Finally combine Equation (48), (49), (50), (56), (57), and recall K T = M K_T=M K T = M
M S E F T P ≤ 4 B ′ 2 tr ( K T ) n 2 μ 2 T + σ 0 2 n + ( 1 − 1 n ) σ 0 2 T + 2 T exp [ − 1 4 ( ( B ′ − B ) λ min ( K T ) σ 0 − T ) 2 ] . (58) \begin{aligned}
\mathrm{MSE}_{\mathrm{FTP}} \le{}& \frac{4B'^2\operatorname{tr}(K_T)}{n^2\mu^2T}+\frac{\sigma_0^2}{n}\\
&+\left(1-\frac{1}{n}\right)\sigma_0^2\sqrt{\frac{T+2}{T}}\exp\left[-\frac{1}{4}\left(\frac{(B'-B)\sqrt{\lambda_{\min}(K_T)}}{\sigma_0}-\sqrt{T}\right)^2\right]. \tag*{(58)}
\end{aligned} MSE FTP ≤ n 2 μ 2 T 4 B ′2 tr ( K T ) + n σ 0 2 + ( 1 − n 1 ) σ 0 2 T T + 2 exp − 4 1 ( σ 0 ( B ′ − B ) λ m i n ( K T ) − T ) 2 . (58) When σ 0 = 0 \sigma_0 = 0 σ 0 = 0 B ′ ≥ B B' \ge B B ′ ≥ B f ^ i ( c ) ( t j ) = f i ( t j ) \hat{f}^{(c)}_i(t_j) = f_i(t_j) f ^ i ( c ) ( t j ) = f i ( t j )
MSE F T P = 4 ( B ′ ) 2 tr ( K T ) n 2 μ 2 T . \operatorname{MSE}_{\mathrm{FTP}} = \frac{4(B')^2\operatorname{tr}(K_T)}{n^2\mu^2T}. MSE FTP = n 2 μ 2 T 4 ( B ′ ) 2 tr ( K T ) . Proof of Theorem 14. For each i i i
g i = argmin g ∈ H K { ∥ g ∥ H K : g ( t j ) = f i ( t j ) , j = 1 , … , T } , g_i=\underset{g\in\mathcal{H}_K}{\operatorname{argmin}}\left\{\lVert g\rVert_{\mathcal{H}_K}:g(t_j)=f_i(t_j),\ j=1,\ldots,T\right\}, g i = g ∈ H K argmin { ∥ g ∥ H K : g ( t j ) = f i ( t j ) , j = 1 , … , T } , and its transformed coefficients as in the proof for Theorem 13:
β i : = K T − 1 / 2 f i , ∥ g i ∥ H K = ∥ β i ∥ 2 ≤ B . \beta_i:=K_T^{-1/2}f_i,\qquad\lVert g_i\rVert_{\mathcal{H}_K}=\lVert\beta_i\rVert_2\le B. β i := K T − 1/2 f i , ∥ g i ∥ H K = ∥ β i ∥ 2 ≤ B . Denote a j = K ( t j , t j ) a_j=\sqrt{K(t_j,t_j)} a j = K ( t j , t j )
∣ f i ( t j ) ∣ ≤ ∥ f i ∥ H K K ( t j , t j ) ≤ B a j ≤ B ′ a j . \lvert f_i(t_j)\rvert\le\lVert f_i\rVert_{\mathcal{H}_K}\sqrt{K(t_j,t_j)}\le Ba_j\le B'a_j. ∣ f i ( t j )∣ ≤ ∥ f i ∥ H K K ( t j , t j ) ≤ B a j ≤ B ′ a j . Since we are considering the noiseless case σ 0 = 0 \sigma_0 = 0 σ 0 = 0 x i = f i x_i = f_i x i = f i
c j = B ′ a j . c_j = B' a_j. c j = B ′ a j . the clipping operation clip ( x i j , c j ) \operatorname{clip}(x_{ij},c_j) clip ( x ij , c j )
x ˉ ( clip ) = x ˉ − 1 n ∑ i = 1 n x i = f ˉ . \bar{x}^{(\operatorname{clip})} = \bar{x} - \frac{1}{n}\sum_{i=1}^{n} x_i = \bar{f}. x ˉ ( clip ) = x ˉ − n 1 i = 1 ∑ n x i = f ˉ . It follows that the released private vector can be written as
x ~ = f ˉ + Z = K T 1 / 2 β ˉ + Z , \widetilde{x} = \bar{f} + Z = K_T^{1/2}\bar{\beta} + Z, x = f ˉ + Z = K T 1/2 β ˉ + Z , where
Z ∼ N ( 0 , τ 2 W − 1 ) , τ 2 = 4 B ′ 2 T n 2 μ 2 , W = diag { a 1 − 2 , … , a T − 2 } . Z \sim N(0,\tau^2 W^{-1}), \qquad\tau^2 = \frac{4B'^2T}{n^2\mu^2}, \qquad W = \operatorname{diag}\{a_1^{-2},\ldots,a_T^{-2}\}. Z ∼ N ( 0 , τ 2 W − 1 ) , τ 2 = n 2 μ 2 4 B ′2 T , W = diag { a 1 − 2 , … , a T − 2 } . By the representer theorem, the constrained estimator has the form
f ^ P T F ( c ) ( t ) = ∑ j = 1 T ( α ^ P T F ( c ) ) j K ( t j , t ) , \widehat{f}_{\mathrm{PTF}}^{(c)}(t) = \sum_{j=1}^{T}(\widehat{\alpha}_{\mathrm{PTF}}^{(c)})_j K(t_j,t), f PTF ( c ) ( t ) = j = 1 ∑ T ( α PTF ( c ) ) j K ( t j , t ) , α ^ P T F ( c ) = argmin α ⊤ K T α ≤ B ′ 2 1 T ( x ~ − K T α ) ⊤ W ( x ~ − K T α ) . \widehat{\alpha}_{\mathrm{PTF}}^{(c)} = \underset{\alpha^\top K_T\alpha\le B'^2}{\operatorname{argmin}}\ \frac{1}{T}(\widetilde{x}-K_T\alpha)^\top W(\widetilde{x}-K_T\alpha). α PTF ( c ) = α ⊤ K T α ≤ B ′2 argmin T 1 ( x − K T α ) ⊤ W ( x − K T α ) . Denote β = K T 1 / 2 α \beta= K_T^{1/2}\alpha β = K T 1/2 α
β ^ P T F = argmin ∥ β ∥ 2 ≤ B ′ ( x ~ − K T 1 / 2 β ) ⊤ W ( x ~ − K T 1 / 2 β ) , β ^ P T F ( c ) = K T 1 / 2 α ^ P T F ( c ) . \widehat{\beta}_{\mathrm{PTF}} = \underset{\lVert\beta\rVert_2\le B'}{\operatorname{argmin}}(\widetilde{x}-K_T^{1/2}\beta)^\top W(\widetilde{x}-K_T^{1/2}\beta), \qquad\widehat{\beta}_{\mathrm{PTF}}^{(c)} = K_T^{1/2}\widehat{\alpha}_{\mathrm{PTF}}^{(c)}. β PTF = ∥ β ∥ 2 ≤ B ′ argmin ( x − K T 1/2 β ) ⊤ W ( x − K T 1/2 β ) , β PTF ( c ) = K T 1/2 α PTF ( c ) . We then analyze the corresponding unconstrained WLS estimator. Define
Φ : = K T 1 / 2 , M : = Φ ⊤ Φ = K T , A : = Φ ⊤ W Φ = K T 1 / 2 W K T 1 / 2 . \Phi:= K_T^{1/2}, \qquad M := \Phi^\top\Phi= K_T, \qquad A := \Phi^\top W\Phi= K_T^{1/2}WK_T^{1/2}. Φ := K T 1/2 , M := Φ ⊤ Φ = K T , A := Φ ⊤ W Φ = K T 1/2 W K T 1/2 . By definition, the unconstrained problem is:
β ~ P T F ( u ) = argmin β ∈ R T ( x ~ − K T 1 / 2 β ) ⊤ W ( x ~ − K T 1 / 2 β ) . \widetilde{\beta}_{\mathrm{PTF}}^{(u)} = \underset{\beta\in\mathbb{R}^T}{\operatorname{argmin}}(\widetilde{x}-K_T^{1/2}\beta)^\top W(\widetilde{x}-K_T^{1/2}\beta). β PTF ( u ) = β ∈ R T argmin ( x − K T 1/2 β ) ⊤ W ( x − K T 1/2 β ) . with the solution
β ~ P T F ( u ) = A − 1 Φ ⊤ W x ~ = Φ − 1 x ~ . \widetilde{\beta}_{\mathrm{PTF}}^{(u)} = A^{-1}\Phi^\top W\widetilde{x} = \Phi^{-1}\widetilde{x}. β PTF ( u ) = A − 1 Φ ⊤ W x = Φ − 1 x . Substituting x ~ = K T 1 / 2 β ˉ + Z = Φ β ˉ + Z \widetilde{x} = K_T^{1/2}\bar{\beta}+Z = \Phi\bar{\beta}+Z x = K T 1/2 β ˉ + Z = Φ β ˉ + Z β ~ P T F ( u ) = β ˉ + ξ \widetilde{\beta}_{\mathrm{PTF}}^{(u)} = \bar{\beta}+\xi β PTF ( u ) = β ˉ + ξ ξ : = Φ − 1 Z \xi:= \Phi^{-1}Z ξ := Φ − 1 Z Z ∼ N ( 0 , τ 2 W − 1 ) Z\sim N(0,\tau^2W^{-1}) Z ∼ N ( 0 , τ 2 W − 1 )
ξ ∼ N ( 0 , τ 2 Φ − 1 W − 1 Φ − 1 ) = d N ( 0 , τ 2 A − 1 ) . \xi\sim N(0,\tau^2\Phi^{-1}W^{-1}\Phi^{-1}) \mathrel{\stackrel{d}{=}} N(0,\tau^2A^{-1}). ξ ∼ N ( 0 , τ 2 Φ − 1 W − 1 Φ − 1 ) = d N ( 0 , τ 2 A − 1 ) . Hence
E ∥ ξ ∥ 2 2 = τ 2 tr ( A − 1 ) , E ∥ Z ∥ 2 2 = τ 2 tr ( W − 1 ) . (60) \mathbb{E}\lVert\xi\rVert_2^2 = \tau^2\operatorname{tr}(A^{-1}), \qquad\mathbb{E}\lVert Z\rVert_2^2 = \tau^2\operatorname{tr}(W^{-1}). \tag*{(60)} E ∥ ξ ∥ 2 2 = τ 2 tr ( A − 1 ) , E ∥ Z ∥ 2 2 = τ 2 tr ( W − 1 ) . (60) We next account for the constraint ∥ β ∥ 2 ≤ B ′ \|\beta\|_2 \le B' ∥ β ∥ 2 ≤ B ′ A = { ∥ β ~ P T F ( u ) ∥ 2 > B ′ } \mathcal{A} = \{\|\widetilde{\beta}_{\mathrm{PTF}}^{(u)}\|_2 > B'\} A = { ∥ β PTF ( u ) ∥ 2 > B ′ } A c \mathcal{A}^c A c β ~ P T F ( c ) = β ~ P T F ( u ) \widetilde{\beta}_{\mathrm{PTF}}^{(c)} = \widetilde{\beta}_{\mathrm{PTF}}^{(u)} β PTF ( c ) = β PTF ( u )
E ∥ Φ ( β ~ P T F ( c ) − β ˉ ) ∥ 2 2 = E [ ∥ Φ ( β ~ P T F ( u ) − β ˉ ) ∥ 2 2 1 A c ] + E [ ∥ Φ ( β ~ P T F ( c ) − β ˉ ) ∥ 2 2 1 A ] ≥ E [ ∥ Φ ξ ∥ 2 2 1 A c ] = E ∥ Z ∥ 2 2 − E [ ∥ Z ∥ 2 2 1 A ] . \begin{aligned}
\mathbb{E}\|\Phi(\widetilde{\beta}_{\mathrm{PTF}}^{(c)}-\bar{\beta})\|_2^2
= \mathbb{E}[\|\Phi(\widetilde{\beta}_{\mathrm{PTF}}^{(u)}-\bar{\beta})\|_2^2\mathbf{1}_{\mathcal{A}^c}]
+ \mathbb{E}[\|\Phi(\widetilde{\beta}_{\mathrm{PTF}}^{(c)}-\bar{\beta})\|_2^2\mathbf{1}_{\mathcal{A}}] \\
&\ge\mathbb{E}[\|\Phi\xi\|_2^2\mathbf{1}_{\mathcal{A}^c}] \\
&= \mathbb{E}\|Z\|_2^2-\mathbb{E}[\|Z\|_2^2\mathbf{1}_{\mathcal{A}}].
\end{aligned} E ∥Φ ( β PTF ( c ) − β ˉ ) ∥ 2 2 = E [ ∥Φ ( β PTF ( u ) − β ˉ ) ∥ 2 2 1 A c ] + E [ ∥Φ ( β PTF ( c ) − β ˉ ) ∥ 2 2 1 A ] ≥ E [ ∥Φ ξ ∥ 2 2 1 A c ] = E ∥ Z ∥ 2 2 − E [ ∥ Z ∥ 2 2 1 A ] . Thus, by (60) ,
MSE P T F = 1 T E ∥ f ~ P T F − f ˉ ∥ 2 2 = 1 T E ∥ Φ ( β ~ P T F ( c ) − β ˉ ) ∥ 2 2 ≥ 1 T [ τ 2 tr ( W − 1 ) − R P T F ] , (61) \operatorname{MSE}_{\mathrm{PTF}}
= \frac{1}{T}\mathbb{E}\|\widetilde{f}_{\mathrm{PTF}}-\bar{f}\|_2^2
= \frac{1}{T}\mathbb{E}\|\Phi(\widetilde{\beta}_{\mathrm{PTF}}^{(c)}-\bar{\beta})\|_2^2
\ge\frac{1}{T}\left[\tau^2\operatorname{tr}(W^{-1})-R_{\mathrm{PTF}}\right], \tag*{(61)} MSE PTF = T 1 E ∥ f PTF − f ˉ ∥ 2 2 = T 1 E ∥Φ ( β PTF ( c ) − β ˉ ) ∥ 2 2 ≥ T 1 [ τ 2 tr ( W − 1 ) − R PTF ] , (61) where
R P T F = E [ ∥ Z ∥ 2 2 1 A ] . R_{\mathrm{PTF}}=\mathbb{E}[\|Z\|_2^2\mathbf{1}_{\mathcal{A}}]. R PTF = E [ ∥ Z ∥ 2 2 1 A ] . It remains to bound the remainder term. Since
∥ β ˉ ∥ 2 ≤ 1 n ∑ i = 1 n ∥ β i ∥ 2 ≤ B , \|\bar{\beta}\|_2 \le\frac{1}{n}\sum_{i=1}^{n}\|\beta_i\|_2 \le B, ∥ β ˉ ∥ 2 ≤ n 1 i = 1 ∑ n ∥ β i ∥ 2 ≤ B , the event A \mathcal{A} A
∥ ξ ∥ 2 = ∥ β ~ P T F ( u ) − β ˉ ∥ 2 ≥ ∥ β ~ P T F ( u ) ∥ 2 − ∥ β ˉ ∥ 2 > B ′ − B . \|\xi\|_2=\|\widetilde{\beta}_{\mathrm{PTF}}^{(u)}-\bar{\beta}\|_2
\ge\|\widetilde{\beta}_{\mathrm{PTF}}^{(u)}\|_2-\|\bar{\beta}\|_2
> B'-B. ∥ ξ ∥ 2 = ∥ β PTF ( u ) − β ˉ ∥ 2 ≥ ∥ β PTF ( u ) ∥ 2 − ∥ β ˉ ∥ 2 > B ′ − B . Consequently,
A ⊆ { ∥ ξ ∥ 2 > B ′ − B } . \mathcal{A}\subseteq\{\|\xi\|_2>B'-B\}. A ⊆ { ∥ ξ ∥ 2 > B ′ − B } . Write ξ = τ A − 1 / 2 z \xi=\tau A^{-1/2}z ξ = τ A − 1/2 z z ∼ N ( 0 , I T ) z\sim N(0,I_T) z ∼ N ( 0 , I T )
∥ A − 1 / 2 z ∥ 2 2 ≤ λ max ( A − 1 ) ∥ z ∥ 2 2 = ∥ z ∥ 2 2 λ min ( A ) , \|A^{-1/2}z\|_2^2\le\lambda_{\max}(A^{-1})\|z\|_2^2=\frac{\|z\|_2^2}{\lambda_{\min}(A)}, ∥ A − 1/2 z ∥ 2 2 ≤ λ m a x ( A − 1 ) ∥ z ∥ 2 2 = λ m i n ( A ) ∥ z ∥ 2 2 , we obtain
Pr ( A ) ≤ Pr ( ∥ z ∥ 2 2 > ( B ′ − B ) 2 λ min ( A ) τ 2 ) . \Pr(\mathcal{A})\le\Pr\left(\|z\|_2^2>\frac{(B'-B)^2\lambda_{\min}(A)}{\tau^2}\right). Pr ( A ) ≤ Pr ( ∥ z ∥ 2 2 > τ 2 ( B ′ − B ) 2 λ m i n ( A ) ) . Because ∥ z ∥ 2 2 ∼ χ T 2 \|z\|_2^2\sim\chi_T^2 ∥ z ∥ 2 2 ∼ χ T 2 (27) , we get
Pr ( A ) ≤ exp [ − 1 2 { ( B ′ − B ) λ min ( A ) τ − T } 2 ] . (62) \Pr(\mathcal{A})\le\exp\left[-\frac{1}{2}\left\{\frac{(B'-B)\sqrt{\lambda_{\min}(A)}}{\tau}-\sqrt{T}\right\}^2\right]. \tag*{(62)} Pr ( A ) ≤ exp − 2 1 { τ ( B ′ − B ) λ m i n ( A ) − T } 2 . (62) Finally, by the Cauchy–Schwarz inequality,
R P T F ≤ ( E ∥ Z ∥ 2 4 ) 1 / 2 Pr ( A ) 1 / 2 . R_{\mathrm{PTF}}\le\left(\mathbb{E}\|Z\|_2^4\right)^{1/2}\Pr(\mathcal{A})^{1/2}. R PTF ≤ ( E ∥ Z ∥ 2 4 ) 1/2 Pr ( A ) 1/2 . For a centered Gaussian vector with covariance τ 2 W − 1 \tau^2W^{-1} τ 2 W − 1
E ∥ Z ∥ 2 4 = τ 4 { [ tr ( W − 1 ) ] 2 + 2 tr ( W − 2 ) } ≤ τ 4 { 3 [ tr ( W − 1 ) ] 2 } . \mathbb{E}\|Z\|_2^4=\tau^4\left\{[\operatorname{tr}(W^{-1})]^2+2\operatorname{tr}(W^{-2})\right\}
\le\tau^4\left\{3[\operatorname{tr}(W^{-1})]^2\right\}. E ∥ Z ∥ 2 4 = τ 4 { [ tr ( W − 1 ) ] 2 + 2 tr ( W − 2 ) } ≤ τ 4 { 3 [ tr ( W − 1 ) ] 2 } . Therefore
( E ∥ Z ∥ 2 4 ) 1 / 2 ≤ τ 2 3 tr ( W − 1 ) . \left(\mathbb{E}\lVert Z\rVert_{2}^{4}\right)^{1/2} \le\tau^{2}\sqrt{3}\operatorname{tr}(W^{-1}). ( E ∥ Z ∥ 2 4 ) 1/2 ≤ τ 2 3 tr ( W − 1 ) . Combining this inequality with Equation (62) and Equation (61) , we prove Equation (12) . ■
Proof of Corollary 15. Write τ n = τ = 2 B n ′ T / ( n μ ) \tau_n=\tau=2B'_n\sqrt{T}/(n\mu) τ n = τ = 2 B n ′ T / ( n μ ) B n ′ B'_n B n ′ B n ′ > B B'_n>B B n ′ > B n n n
B n ′ − B τ n = n μ 2 T ( 1 − B B n ′ ) → ∞ . \frac{B'_n-B}{\tau_n}=\frac{n\mu}{2\sqrt{T}}\left(1-\frac{B}{B'_n}\right)\to\infty. τ n B n ′ − B = 2 T n μ ( 1 − B n ′ B ) → ∞. Thus, the radius condition in Theorem 14 holds for all sufficiently large n n n Theorem 13 gives
lim sup n → ∞ MSE ( f ~ F T P ) MSE ( f ~ P T F ) ≤ tr ( K T ) T tr ( W − 1 ) . \limsup_{n\to\infty}\frac{\operatorname{MSE}(\widetilde{f}_{\mathrm{FTP}})}{\operatorname{MSE}(\widetilde{f}_{\mathrm{PTF}})}\leq\frac{\operatorname{tr}(K_T)}{T\operatorname{tr}(W^{-1})}. n → ∞ lim sup MSE ( f PTF ) MSE ( f FTP ) ≤ T tr ( W − 1 ) tr ( K T ) . By the definition W = diag { K ( t j , t j ) − 1 : j = 1 , … , T } W=\operatorname{diag}\{K(t_j,t_j)^{-1}:j=1,\ldots,T\} W = diag { K ( t j , t j ) − 1 : j = 1 , … , T }
tr ( W − 1 ) = ∑ j = 1 T K ( t j , t j ) = tr ( K T ) . \operatorname{tr}(W^{-1})=\sum_{j=1}^{T}K(t_j,t_j)=\operatorname{tr}(K_T). tr ( W − 1 ) = j = 1 ∑ T K ( t j , t j ) = tr ( K T ) . Hence, we get the claimed bound of 1 / T 1/T 1/ T
Additional Simulation Results
In this section, we provide the simulation setup and results for polynomial spaces and supplementary numerical results for the RKHS setting.
Polynomial Setup. Consider the functional model: f 1 , … , f n ∈ H m f_1,\ldots,f_n\in\mathcal{H}_m f 1 , … , f n ∈ H m L 2 [ 0 , 1 ] L^2[0,1] L 2 [ 0 , 1 ] H m = { θ T ϕ ( t ) : θ ∈ R m , t ∈ [ 0 , 1 ] } \mathcal{H}_m=\{\theta^{\mathsf{T}}\phi(t):\theta\in\mathbb{R}^m,t\in[0,1]\} H m = { θ T ϕ ( t ) : θ ∈ R m , t ∈ [ 0 , 1 ]} ϕ ( t ) = ( ϕ 1 ( t ) , … , ϕ m ( t ) ) T \phi(t)=(\phi_1(t),\ldots,\phi_m(t))^{\mathsf{T}} ϕ ( t ) = ( ϕ 1 ( t ) , … , ϕ m ( t ) ) T ϕ k ( t ) \phi_k(t) ϕ k ( t ) k − 1 k-1 k − 1 k = 1 , … , m k=1,\ldots,m k = 1 , … , m m = 2 m=2 m = 2 ( ϕ 1 ( t ) , ϕ 2 ( t ) ) T = ( 1 , 12 ( t − 0.5 ) ) T (\phi_1(t),\phi_2(t))^{\mathsf{T}}=(1,\sqrt{12}(t-0.5))^{\mathsf{T}} ( ϕ 1 ( t ) , ϕ 2 ( t ) ) T = ( 1 , 12 ( t − 0.5 ) ) T i i i f i ( t ) = θ i T ϕ ( t ) f_i(t)=\theta_i^{\mathsf{T}}\phi(t) f i ( t ) = θ i T ϕ ( t ) θ i \theta_i θ i m m m B = 1 B=1 B = 1 ∥ f i ∥ L 2 = ∥ θ i ∥ 2 ≤ B \lVert f_i\rVert_{L^2}=\lVert\theta_i\rVert_2\leq B ∥ f i ∥ L 2 = ∥ θ i ∥ 2 ≤ B X X X x i j = θ i T ϕ ( t j ) + ϵ i j x_{ij}=\theta_i^{\mathsf{T}}\phi(t_j)+\epsilon_{ij} x ij = θ i T ϕ ( t j ) + ϵ ij ϵ i j ∼ i . i . d . N ( 0 , σ 0 2 ) \epsilon_{ij}\overset{\mathrm{i.i.d.}}{\sim}N(0,\sigma_0^2) ϵ ij ∼ i.i.d. N ( 0 , σ 0 2 ) t j = ( j − 1 ) / ( T − 1 ) , j = 1 , … , T t_j=(j-1)/(T-1),j=1,\ldots,T t j = ( j − 1 ) / ( T − 1 ) , j = 1 , … , T T = 20 T=20 T = 20 f ~ F T P \widetilde{f}_{\mathrm{FTP}} f FTP f ~ P T F \widetilde{f}_{\mathrm{PTF}} f PTF f ˉ = n − 1 ∑ i = 1 n f i \bar{f}=n^{-1}\sum_{i=1}^{n}f_i f ˉ = n − 1 ∑ i = 1 n f i n ∈ { 2 2 , … , 2 12 } n\in\{2^2,\ldots,2^{12}\} n ∈ { 2 2 , … , 2 12 } m ∈ { 2 , 4 , 6 , 8 } m\in\{2,4,6,8\} m ∈ { 2 , 4 , 6 , 8 } μ ∈ { 0.1 , 1 } \mu\in\{0.1,1\} μ ∈ { 0.1 , 1 } B ′ ∈ { B , 1.1 B , log n , log n , n , n 2 / 3 } B'\in\{B,1.1B,\sqrt{\log n},\log n,\sqrt{n},n^{2/3}\} B ′ ∈ { B , 1.1 B , log n , log n , n , n 2/3 } σ 0 ∈ { 0 , 0.1 , 1 , 10 } \sigma_0\in\{0,0.1,1,10\} σ 0 ∈ { 0 , 0.1 , 1 , 10 }
Figure 4 examines the noiseless IMSE comparison between FTP and PTF in the polynomial space with B ′ = 1.1 B' = 1.1 B ′ = 1.1 1 / m 1/m 1/ m Corollary 12 . Larger basis dimensions yield smaller ratios at large sample sizes, while stronger privacy protection (μ = 0.1 \mu= 0.1 μ = 0.1
Figure 5 compares the scaled IMSE under different fitting radii with σ 0 = 1 \sigma_0 = 1 σ 0 = 1 μ = 1 \mu= 1 μ = 1 m = 4 m = 4 m = 4 B ′ = B B' = B B ′ = B n n n B ′ = log n B' = \sqrt{\log n} B ′ = log n B ′ = n B' = \sqrt{n} B ′ = n B ′ = n 2 / 3 B' = n^{2/3} B ′ = n 2/3
Figure 6 compares the IMSE ratios under different observation-noise levels with μ = 1 \mu= 1 μ = 1 B ′ = log n B' = \sqrt{\log n} B ′ = log n σ 0 = 0.1 \sigma_0 = 0.1 σ 0 = 0.1 σ 0 = 1 \sigma_0 = 1 σ 0 = 1 σ 0 = 10 \sigma_0 = 10 σ 0 = 10 m m m m = 8 m = 8 m = 8
Table 1 supplements Figure 1 with the individual MSEs and the empirical probability that the PTF fitting constraint is active. This probability generally decreases with sample size, but remains higher for larger T T T μ \mu μ T = 8 T=8 T = 8 n = 2 10 n=2^{10} n = 2 10 μ = 0.1 \mu=0.1 μ = 0.1 μ = 1 \mu=1 μ = 1 1 / T 1/T 1/ T
