Function Privatization in the Local Model

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Function Privatization in the Local Model

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Function Privatization in the Local Model Yuting Liang∗

Tian Shu†

Ke Yi‡

arXiv:2607.27164v1 [cs.CR] 29 Jul 2026

Abstract We study the problem of privately releasing functions, with a particular focus on curves, which are images of continuous functions on some finite interval. Many types of data exist naturally as curves, such as trajectory data or 1D density curves. We shall primarily be interested in the local model setting, where the function to be privatized captures data belonging to one individual, which is the more challenging setting with limited prior work. Under the standard notion of local differential privacy (DP), any two arbitrarily different functions are required to be made indistinguishable by privatization, which is too strong to allow meaningful utility; we thus work with a generalized notion of DP known as Geo-Privacy (GP), which allows functions far apart to be distinguished more easily while providing strong protection for near functions. To demonstrate the effectiveness of our framework, we provide experimental evaluation on several datasets.

Introduction

A fundamental problem in data privatization is the following: Suppose a user possesses data in the form of a sequence, where each record can be either 1D (e.g., prices over a period or ECG data) or multi-dimensional (e.g., a trajectory). How can they privatize the data before sending it to an untrusted analyst? More abstractly, the data can be modeled as a function q : [0, T ] → Rn , and we thus term the problem function privatization. Naively, one could privatize some subset of the function values q(t1 ), . . . , q(tk ) separately, each using some existing privatization method. However, this solution consumes privacy linear in k. It is also not a theoretically elegant solution as it only obtains the function values at discrete points (often chosen heuristically) while f can be defined over the reals. Importantly, this naive solution ignores the correlations among the function values, which often exist in real-world data. In the extreme case, suppose we know a priori that the function is a constant. Then privatizing the function at any one point suffices. On the other hand, if q can really be an arbitrary function, then there might be little to no correlation and the naive solution is already the best one can hope for. Thus, the central technical problem to be addressed in this paper is: how to design a privatization method that automatically exploits the correlation if it exists in the data, thereby achieving good utility on typical real-world data. In our setup where each user privatizes their own data, the most popular privacy definition is the local model of differential privacy (DP), which requires the output to be ε-indistinguishable between any two different instances. However, this is inappropriate for functional data as it insists a ∗

Department of Computer Science, University of Toronto. [email protected] Computer Science and Engineering, Hong Kong University of Science and Technology. [email protected] ‡ Computer Science and Engineering, Hong Kong University of Science and Technology. [email protected] †

uniform privacy guarantee, e.g., the level of indistuinguishability is the same between q1 (t) := 2t+3 and q2 (t) := 2.01t + 2.99 vs between q1 (t) := 2t + 3 and q3 (t) := 2000t − 3000. This in turn leads to a privatized output of low utility and there is no effective function privatization method in the local DP model. Therefore, we adopt the notion of generalized differential privacy (GP) [CABP13, LY23], which is often adopted in a local model setting for data in a metric space as a more attractive alternative to local DP (e.g. [ABCP13, LWX21, YTL22, LY24]). GP stipulates that the level of indistuinguishability be proportional to the distance (using an appropriate metric) between the two instances (see Section 2 for precise definitions). For functions, we will adopt the natural L2 metric. Then in the example above, GP will make q1 and q2 much more indistinguishable than q1 and q3 . Such a more refined privacy definition not only results in good utility (as will be achieved by our methods), but also captures the natural privacy requirement in a metric space.

1.1

Our Contributions

In this paper, we present a series of function privatization methods, requiring different correlation assumptions on the function: We start by considering linear functions (Section 3.1), and then generalize the method to functions that can be represented as a linear combination of a fixed number m of basis functions (Section 3.2). We show that our method incurs an L2 noise to the √ privatized function that is proportional to m ( m for CGP, a variant of GP). Since the privacy noise grows with m, it is sometimes beneficial to use less basis functions to reduce the noise, at the expense of some approximation error. In Section 3.4, we develop a method that automatically and privately chooses a suitable number of basis functions from a possibly infinite collection, while trying to balance the two sources of error. In Section 4, we focus on curves, which are images of continuous functions on some finite interval. Curves are best approximated using piecewise basis functions. We develop algorithms to determine how the curve should be divided into pieces, approximate each piece, and then privatize. Compared with the naive solution, our methods enjoy the following advantages: (1) It captures the correlation in the data, in the sense that stronger assumptions (e.g., linear functions or functions that can be represented by a few basis functions) result in better utility. (2) If the assumption does not strictly hold, our method can approximate it while automatically balancing the approximation error and privacy noise, which allows us to extract the hidden correlations present in the data. (3) Our methods output functions defined over the reals, not only at discrete points. (4) It supports vector-valued variables as well as vector-valued functions. Finally, we conducted an extensive set of experiments to demonstrate the practical advantage of our methods using real-world functional data.

1.2

Related Work

The closest work to ours is that of Hall et al. [HRW13], who studied the function privatization problem in the central model of DP. In the central model, the trusted analyst has N functions qi (·), i = 1, . . . , N , where each qi depends on the private data xi and wishes to privatize their mean 1 P i qi (·). They also reduce the privacy noise by exploiting the correlations in each qi (·). In N 2 2 particular, they study the case where qi (t) := e−(xi −t) /2b for fixed b > 0, which corresponds to the Gaussian kernel density estimation (KDE) function at point t, where the xi ’s are assumed to have been drawn from some distribution.

The work of [WNM23] also privatizes the P Gaussian kernel function, where a factorized form 2 1 g(x) · p(t) is used to approximate κt (x) = N i e−∥xi −t∥ . There, the central curator releases a privatized g̃(x), which can then be used by an analyst to perform further queries without further interaction with the curator. The work in [AR17] uses Bernstein polynomials to approximate a real-valued function qx parameterized by private data x = (x1 , · · · , xN ); their method builds a lattice of the function domain and privatizes the evaluations of qx (·) on all lattice points by adding Laplace noise, which requires the function qx to have small sensitivity w.r.t. changing x. The works that privatize a set of queries by approximating the query functions are also related [TUV12, WJF+ 16]. In [TUV12], they showed that for private data x ∈ ({0, 1}d )N , it is possible to approximate a set of k-way marginal queries by low-degree polynomials, which leads to efficient running time and requires lower sample complexity than previous works on k-way P marginals. The work of [WJF+ 16] considers privatizing a set of queries of the form x 7→ N1 i f (xi ), for private data x with xi ∈ [−1, 1]d and smooth functions f that can be approximated by trigonometric polynomials, assuming bounded derivatives of some order; there, the private data vector x ∈ 1 P d N ([−1, 1] ) is embedded into a basis and privatized, so that the query answer N i f (xi ) can be approximated by a dot product of the coefficients of f and the privatized basis. The problem of privately releasing trajectory data has been considered in central DP [CAC12, HCM+ 15, GLT+ 18], where the goal is to generate a synthetic collection of trajectories that is distributionally similar to the original input collection of trajectories. In these works, a privatized empirical distribution on sequences of locations is constructed, from which the synthetic database can then be generated. For a comprehensive list of works on trajectory data privatization under central DP, we refer the reader to the SoK paper of [MPGBPA+ 23], which provides a detailed discussion of the works in terms of utility and limitations. This problem has also been attempted under the local model of DP, where the goal is to publish a privatized trajectory from a single input trajectory [CCFS21]; however, due to the strong requirement of local-DP, it is not possible for a local-DP mechanism on this problem to have any meaningful utility, unless the data universe is restricted to a very small space. There are a couple of works using GP for privatization of various types of queries [LY23, LY24]. In particular, [LY24] also considered privatizing the Gaussian kernel function; however, their mechanism is for privatizing a single query and loses utility quickly when many queries are asked. [LY23] considered releasing a collection of points in a trajectory under GP using basic composition; however, such an approach is not suitable when the goal is to preserve a general likeness of the curve, as we will also demonstrate in our experiments.

Preliminaries

2.1

Geo-Privacy

We briefly recall the definitions and basic properties of GP, which is defined on metric spaces. Let (U, dist) be a metric space. For Λ > 0, and x, x′ ∈ U , we write x ∼Λ x′ if dist(x, x′ ) ≤ Λ. Definition 1 (Geo-privacy, Definition 6 in [LY23]). Fix ε, δ ≥ 0, Λ ∈ R>0 ∪ {∞}. A randomized mechanism M : U → V satisfies (ε, δ, Λ) geo-privacy, or simply (ε, δ, Λ)-GP, if for all measurable S ⊆ V and all x ∼Λ x′ ′ Pr[M (x) ∈ S] ≤ eε dist(x,x ) Pr M (x′ ) ∈ S + δ. 3

The parameter ε measures privacy loss per unit distance (e.g. ε = 0.001 per meter using the Euclidean metric). We denote by M(x) the distribution of the random variable M (x), and by m(x)(y) its pdf at y ∈ M(x). Concentrated geo-privacy (CGP) is defined in terms of the Rényi divergence of order α [Rén61, VEH14], defined for distributions P, Q with pdf’s p(·), q(·), respectively: Z 1 α 1−α Dα (P∥Q) := log p(y) q(y) dz . α−1 V Definition 2 (Concentrated Geo-privacy , Definition 3 in [LY23]). Fix ρ ≥ 0. Λ ∈ R>0 ∪ {∞}. A mechanism M : U → V satisfies (ρ, Λ) concentrated geo-privacy, or simply (ρ, Λ)-CGP, if for all x ∼Λ x′ , and all α > 1 Dα (M(x)∥M(x′ )) ≤ αρ dist(x, x′ )2 . The parameter ρ is privacy loss per unit distance squared. Note that by setting Λ = 1 in the definitions above and using the Hamming metric as dist(·, ·), one recovers the usual (ε, δ)-DP [DMNS06] and ρ-CDP [BS16] definitions of the central model; while setting dist(·, ·) to be the discrete metric dist01 (x, x′ ) := 1{x ̸= x′ } yields the same definitions in the local model. The main appeal of the GP model is in its flexibility to choose a metric suitable for the application and data being studied. We write ε-GP for (ε, 0, ∞)-GP and ρ-CGP for (ρ, ∞)-CGP. Note that one way to show that a mechanism M satisfies ε-GP, is to show that M induces distributions on all pair of inputs x, x′ ∈ U such that M(x) and M(x′ ) have the same support, and the ratio of their pdf’s satisfies for all m(x)(y) ε dist(x,x′ ) . y ∈ M(x): m(x ′ )(y) ≤ e An example of such mechanisms is the exponential mechanism. Lemma 2.1 (Exponential mechanism for ε-GP [CABP13, MT07]). Let (V, distV ) be a metric space. Let g : U → V be K-Lipschizt where K > 0. The mechanism that, on input x, draws a y from a ε distribution with pdf m(x)(y) = c(ε, K)e− K distV (g(x),y) , where c(ε, K) is a constant independent of the input x, is ε-GP. We also have the following basic mechanisms for vector-valued queries. Lemma 2.2 (Canonical mechanisms for vector-valued queries [LY23]). Let g : U → V ⊆ Rm be K-Lipschitz. Let M : U → Rm be the mechanism defined by M (x) = g(x) + Kb Z, where Z is an m-dimensional random vector. Then 1. M is ε-GP if b = ε, where Z is drawn from the standard m-dimensional spherical Laplace distribution, denoted Z ∼ SLap(m), with pdf h(z) ∝ e−∥z∥ ; √ 2. M is ρ-CGP if b = 2ρ, where Z is drawn from the standard m-dimensional Gaussian 1 2 distribution, denoted Z ∼ N (0, Im×m ), with pdf h(z) ∝ e− 2 ∥z∥ . Similar to DP, GP also enjoys the following composition properties, which will be helpful for developing algorithms composed of multiple steps. Lemma 2.3 (Basic compositions [ABCP13, LY23]). Fix k ≥ 2, let Mj : U → Vj for j ∈ [k]. Let M = (M1 , · · · , Mk ) be the k-fold composition, where the choice of Mj may depend on the outputs of previous Ml ’s for l < j. Then P 1. M is ε-GP, if each Mj is εj -GP, where ε := j∈[k] εj ; 4

2. M is ρ-CGP, if each Mj is ρj -CGP, where ρ :=

j∈[k] ρj .

A special case of the composition property where all but the first mechanism have ε = 0 is known as the postprocessing property, i.e., gpp (M (·)) satisfies the same GP guarantee of M for any measurable function gpp (·). The Sparse Vector Technique (SVT) [DR+ 14], shown in Algorithm 1, takes in a possibly infinite sequence of queries, and returns the index corresponding (approximately) to the query that first crosses some prespecified threshold T . The SVT is ε-GP [LY23] for any metric dist(·, ·), as long as all queries are K-Lipschitz w.r.t. the same metric. Algorithm 1 Sparse Vector Technique Input: x ∈ U ; (ε1 , ε2 ) with ε = ε1 + ε2 ; T ; K; g1 , g2 , · · · each K-Lipschitz Output: variable-length sequence y1 , y2 , · · · 1: draw W ∼ Lap(K/ε1 ) 2: for j = 1, · · · do

draw Vj ∼ Lap(2K/ε2 ) if gj (x) + Vj ≥ T + W then 5: output yj = ⊤ and HALT 6: else 7: output yj = ⊥ 8: end if 9: end for

The SVT has the following utility guarantee, which can be verified by standard analysis (e.g. see [DY23]): Lemma 2.4. Let k̄ be the index j when SVT(x, ( 3ε , 2ε 3 ), T , K, g1 , g2 , · · · ) halts. Suppose there is t such that gt (x) ≥ 6K ln(2/β)/ε. Then with probability at least 1 − β, k̄ satisfies k̄ ≤ t and T+ 3K 2t 2 gk̄ (x) ≥ T − ε ln β + ln β .

2.2

The Problem of Function Privatization

We consider functions of the form q : I → Rn , where I = I1 × · · · × Id with Ii ⊆ R for i ∈ [d] := {1, · · · , d}. A natural metric between two functions is the L2 distance dist2 (q, q ′ ) := 1/2 R ′ 2 , where ∥ · ∥ denotes the usual Euclidean metric. Our goal is to compute, I ∥q(t) − q (t)∥ dt for a given function q, a privatized function q̃ that satisfies GP (or CGP) w.r.t. the dist2 met2 L2 (I) denotes the set of square-integrable functions on I, i.e., Rric. We 2assume q ∈ L (I), where ′ ′ I ∥q(t)∥ dt < ∞; so dist2 (q, q ) < ∞ for every pair q, q . We focus primarily on the setting where d = 1 and I = [0, T ] for T > 0. We distinguish between the restricted case I = [0, T ] and the general case I by explicitly writing [0, T ] in the former case. In particular, we are interested in continuous functions on [0, T ], which correspond to curves in Rn . We use C(I) to denote the set of continuous functions on I.

2.3

On the L2 Metric

The L2 metric is arguably the most natural/important metric for physical sciences and engineering; it is preferred by physicists and engineers because of its desirable properties such as completeness, rotation-invariance [SS11, AW05], relations to physical quantities such as the energy of the signal [OWN97], etc. Conceptually, the L2 metric is to functions as the ℓ2 (Euclidean) metric is to points, and the latter is commonly used for point privatization [ABCP13, LY23, LY24]. Concretely, consider a function q : [0, 1] → R: The function q can be identified with its image f ([0, 1]), which is a collection of infinitely many points. Recall we can approximate the L2 distance between two curves using point evaluations at t1 , . . . , tn for increasingly many points; in particular, we have Z 1 n 1X (q(t) − q ′ (t))2 dt = lim (q(tj ) − q ′ (tj ))2 . n→∞ n 0 j=1

Thus, the L2 distance between two functions is essentially an average of ℓ2 distances between the collections of points (q(t1 ), . . . , q(tn )) and (q ′ (t1 ), . . . , q ′ (tn )) for infinitely many points. Start (0,0) A

(1,0.8)

(2,1.6)

(3,2.4)

(4,3.2)

D’

(4.7, 2.8)

(5,4)

E’

(4.8.4.6)

(6,4.8)

(7,5.6)

End

(8,6.4)

Members-only club

G F

E’ E D D’

Service station

B A

Figure 1: Reference locations for example trajectories.

Privacy protection via L2 metric. The L2 metric measures variations across the entire domain, it is robust against variations in small areas. An analyst observing a privatized function would not be able to infer with high confidence, whether and where the original function had a brief but otherwise distinguishing shift. For example, when applied to trajectory data, it protects against sudden and short changes in the curve. Consider the following scenario: We have three trajectories, q1 , q2 , q3 traveling on a straight road from time 0 to time 1, see Fig. 1 for an illustration of the road and values of the locations. The trajectories are listed as (time, location) tuples, where the traveling speed between two tuples is assumed to be uniform; they are similar except q2 , q3 will briefly stop at different locations before continuing down the road: q1 : {(0.13, A), (0.26, B), (0.4, C), (0.53, D), (0.66, E), (0.8, F ), (0.9, G)} 6

q2 : {(0.12, A), (0.24, B), (0.35, C), (0.45, D), (0.52, D′ ), (0.54, D′ ), (0.6, D), (0.7, E), (0.8, F ), (0.9, G)} (briefly stops at D′ ) q3 : {(0.12, A), (0.24, B), (0.35, C), (0.45, D), (0.55, E), (0.61, E ′ ), (0.63, E ′ ), (0.7, E), (0.8, F ), (0.9, G)} (briefly stops at E ′ ) The three trajectories have small pairwise L2 distances; thus, an analyst observing a privatized trajectory would not be able to tell whether the original trajectory had been q1 , q2 or q3 with high confidence. Also, the pairwise L2 distance is smaller than the pairwise maximum ℓ2 distance at any point, for each pair: dist2 (q1 , q2 ) = 0.40 < maxt∈[0,1] ∥q1 (t) − q2 (t)∥ = 0.85 dist2 (q1 , q3 ) = 0.48 < maxt∈[0,1] ∥q1 (t) − q3 (t)∥ = 1.08 dist2 (q2 , q3 ) = 0.50 < maxt∈[0,1] ∥q2 (t) − q3 (t)∥ = 1.54. Thus, the distinguishability level is smaller under the L2 (i.e. the privacy protection is stronger for the same privacy parameter), compared to the maximum point-wise distance. Finally, the L2 metric provides protection for single points in a way that is consistent with (and at least as strong as) that provided by the Euclidean metric for single points. For trajectory data, the longer a curve stays at a single point, the more similar the privacy guarantee becomes to that offered by point privatization under the Euclidean metric used in previous works [ABCP13, LY23, LY24]. Concretely, consider two constant trajectories q, q ′ : [0, 1] → Rd (e.g. if a person stays at a location for the entire duration of the trajectory) such that q(t) = p and q ′ (t) = p′ for some p, p′ ∈ Rd for all t. The L2 distance between them is Z 1

1/2 1/2 ∥q(t) − q ′ (t)∥2 dt = ∥p − p′ ∥2 = ∥p − p′ ∥,

which is the same level of distinguishability required for point privatization in the aforementioned works.

Privatization of functions

3.1

Linear functions

We start by considering the simple case of linear functions, which serves as an illustrative example to demonstrate some key ideas of our framework. Let fa : [0, T ] → R, defined by fa (t) = a1 t + a2 with a = (a1 , a2 ) ∈ R2 . Let Uf be the space consisting of all such linear functions. Restating the GP definition for this special case, a mechanism Mf on (Uf , dist2 ) satisfies ε-GP, if for all pairs fa and fa′ , and all measurable subsets Sf ⊆ V = Uf , Pr[Mf (fa ) ∈ Sf ] ≤ eε dist2 (fa ,fa′ ) Pr[Mf (fa′ ) ∈ Sf ]. Note that we can identify fa with the point a ∈ R2 , so to privatize fa it would suffice to privatize a, i.e., we want to find a mechanism M : R2 → R2 such that for all Sf ⊆ Uf , and all pairs a, a′ Pr[M (a) ∈ S] ≤ eε dist2 (fa ,fa′ ) Pr M (a′ )) ∈ S 7

(1)

where S := {c ∈ R2 : fc ∈ Sf }. Observing also the one-to-one correspondence between S and Sf , we may simply write that (1) is required to hold for all measurable S ⊆ R2 . We first show that a natural attempt fails to solve the problem. As stated above, for linear functions the problem reduces to privatizing a point a ∈ R2 . Thus, it is tempting to simply apply Lemma 2.2 on a while taking the identity function as g (thus K = 1). For concreteness, consider the GP version of Lemma 2.2 with ε = 1, which adds Z to a, where Z follows the 2-dimensional spherical Laplace distribution. This outputs a y = (y1 , y2 ) with pdf ∝ e−∥y−a∥ . Now consider the following two functions on [0, 1]: fa : t 7→ 2t + 0.5 and fa′ : t 7→ 0.5t + 2; i.e., a = (2, 0.5) and a′ = (0.5, 2). Then the ratio of the respective pdf’s at y = (3, 1.5) is √ 2 2 √ √ e− (y1 −a1 ) +(y2 −a2 ) − 2+ 2.52 +0.52 √ = e = e1.135 − (y1 −a′1 )2 +(y2 −a′2 )2 e q √

> e1.5/ 3 = e

′ ′ 2 0 ((a1 −a1 )t+(a2 −a2 )) dt

= edist2 (fa ,fa′ ) ,

which violates the GP requirement. Critically, this naive method fails because the L2 distance between fa and fa′ is not equal to the ℓ2 distance between a and a′ : two points far apart in the Euclidean space, which this method does not protect, may correspond to two functions that are very close in the function space, which are required to be indistinguishable under GP. To fix the issue, we should apply Lemma 2.1 with the correct metric, i.e., draw y from a distribution with pdf m(a)(y) ∝ e−ε dist2 (fy ,fa ) . This is no longer an isotropic spherical Laplace distribution. To draw from such a distribution efficiently, we rewrite Z T 2 2 dist2 (fy , fa ) = f(y1 ,y2 ) (t) − f(a1 ,a2 ) (t) dt 0 Z T = ((y1 − a1 )t + (y2 − a2 ))2 dt 0 Z T = (y1 − a1 )2 t2 + 2(y1 − a1 )(y2 − a2 )t + (y2 − a2 )2 dt 0

T 1 2 3 2 2 = (y1 − a1 ) t + (y1 − a1 )(y2 − a2 )t + (y2 − a2 ) t 3 t=0 1 = (y1 − a1 )2 T 3 + (y1 − a1 )(y2 − a2 )T 2 + (y2 − a2 )2 T 3 1 T 3 1 T 2 (y1 − a1 ) 3 2 = (y1 − a) (y2 − a2 ) 1 2 T T (y2 − a2 ) | 2 {z }

Σ−1

= Σ−1/2

2 (y1 − a1 ) . (y2 − a2 )

(2)

The matrix Σ−1 can be shown to be positive definite, hence the distribution with pdf m(a)(y) ∝ e−ε dist2 (fy ,fa ) = e−ε∥Σ

−1/2 [(y −a ), (y −a )]T ∥ 1 1 2 2

(3)

precisely corresponds to outputting 1ε Σ1/2 Z + a where Z follows the standard 2D spherical Laplace distribution. Equivalently speaking, we must add noise to a in the eigen-directions of Σ. 8

It is important to note that the scaling matrix Σ depends on T ; in particular, it requires T < ∞. This is not a restriction, though, since linear functions over [0, ∞) is not square-integrable. In Sections 3.4 and 4.3, we will see how square-integrable functions over an unbounded domain can still be privatized. Remark 3.1. The mechanism given by the pdf in (3) above can be extended to piecewise linear functions. Following the derivations above, one finds that the matrix Σ−1 becomes a block matrix of size 2k × 2k, if the function is continuous within each of the k ≥ 1 segments. We will discuss piecewise functions in more detail in Section 4 when we discuss the privatization of curves.

3.2

Multi-basis Functions

Linear functions can be considered as linear combinations of two basis functions ϕ1 (t) = t, ϕ2 (t) = 1, and our method in the previous subsection can be easily extended to functions with m basis functions. Such functions are thus parameterized by points in Rm , i.e., an m-dimensional Pm function m space. Specifically, let Uf = {fa : a ∈ R } where each fa : I → R is defined by fa (t) = j=1 aj ϕj (t), for basis functions ϕ1 (·), · · · , ϕm (·) ∈ L2 (I), with each ϕj : I → R for j ∈ [m]. We assume the ϕj (·)’s are linearly independent to avoid redundancy. A common set of basis functions are {ϕj (t) := tm−j }j∈[m] , which induce the space of all polynomials of degree up to m − 1. Note that linear independence among the ϕj (·)’s implies that fa (·) = fa′ (·) ⇐⇒ a = a′ , thus preserving the one-to-one correspondence between the sets Sf ⊆ Uf and S := {c ∈ Rm : fc ∈ Sf }. Next, we extend our ε-GP mechanism for linear functions to this more general function space. For y = (y1 , · · · , ym ) ∈ Rm , we have Z 2 dist2 (fy , fa ) = (fy (t) − fa (t))2 dt ZI = ((y1 − a1 )ϕ1 (t) + · · · + (ym − am )ϕm (t))2 dt I   Z X m X m (yj − aj )ϕj (t) · (yk − ak )ϕl (t) dt =  I

j=1 k=1

m X m X

Z (yj − aj )(yk − ak ) ·

ϕj (t)ϕl (t)dt I

j=1 k=1

R

= (y1 − a1 ) · · ·

  R ··· ϕ1 (t)ϕm (t)dt y1 − a 1 I    .. .. .. .. (ym − am )    . . . . R R ϕm (t)ϕ1 (t)dt · · · ϕm (t)ϕm (t)dt ym − am | I {z I } I ϕ1 (t)ϕ1 (t)dt

Σ−1

 = Σ

 2

y1 − a 1  ..   .

−1/2 

(4)

ym − a m Thus, we can privatize fa ∈ Uf by privatizing a as M (a) := Ra + 1ε Σ1/2 Z where Z is drawn from a m-dimensional spherical Laplace distribution, and [Σ−1 ]j,l = I ϕj (t)ϕl (t)dt. Note that Σ is positive definite, since Σ−1 has full rank and is positive semi-definite as it is an outer product of a vector of 9

linearly independent functions. In particular, if {ϕj (·)}j∈[m] is a set of orthogonal basis such that R I ϕj (t)ϕl (t)dt = 0 for j ̸= l, then all of the off-diagonal entries in Σ vanish. We summarize this result below. Theorem 3.2. Fix a setPof linearly independent functions {ϕj }j∈[m] ⊂ L2 (I), where each ϕj : I → R. Let Uf := {fa (·) := j aj ϕj (·) | a ∈ Rm }, equipped with the L2 metric dist2 (·, ·). Let Σ−1 be R the matrix whose (j, l)th entry is given by [Σ−1 ]j,l = I ϕj (t)ϕl (t)dt for j, l ∈ [m]. Then for any fa ∈ Uf , the mechanism that releases fã (·) where ã = M (a) := a + 1ε Σ1/2 Z, and Z ∼ SLap(m), is ε-GP. The identity in (4) allows us to also privatize any fa ∈ Uf under CGP. In fact, the proof to the theorem below gives an alternative way to derive the GP guarantee of the mechanism mentioned above using Lemma 2.2. Theorem 3.3. Let (Uf , dist2 ) and Σ be as defined in Theorem 3.2. Then for any fa ∈ Uf , the mechanism that releases fã (·) where ã = M (a) := a + √12ρ Σ1/2 Z, and Z ∼ N (0, Im×m ), satisfies ρ-CGP. Proof. Let g : Uf → Rm be given by g(fa ) := Σ−1/2 a. Then    ′   a1 a1 a1 − a′1       .. ∥g(fa ) − g(fa′ )∥ = Σ−1/2  ...  − Σ−1/2  ...  = Σ−1/2   = dist2 (fa , fa′ ), . ′ ′ am am am − a m where the last equality is due to identity (4). Thus, g is 1-Lipschitz w.r.t. dist2 and by Lemma 2.2, the mechanism g(fa ) 7→ g(fa ) + √12ρ Z for Z ∼ N (0, Im×m ) satisfies ρ-CGP. Moreover, by postprocessing, we get that the mechanism M given by 1 1 1 M (a) := Σ1/2 g(fa ) + √ Z = Σ1/2 Σ−1/2 a + √ Z = a + √ Σ1/2 Z 2ρ 2ρ 2ρ satisfies ρ-CGP. Below, we analyze the utility of our mechanism, i.e., the L2 error induced by the privacy noise, both in expectation and with high probability. Lemma 3.4. Let ã = M (a) := a + 1ε Σ1/2 Z, where Z ∼ SLap(m). Then M is ε-GP, and 1. E[dist2 (fã , fa )] = m ε; 2. dist2 (fã , fa ) ≤ η(β;m,1) with probability at least 1 − β, ε e where η(β; m, 1) := e−1 (m + ln β1 ).

Proof. We have 1 dist2 (fã , fa ) = Σ−1/2 ã − a = Σ−1/2 a + 1ε Σ1/2 Z − a = ∥Z∥ . ε The magnitude ∥Z∥ follows a generalized gamma distribution (see Lemma B.6), where ∥Z∥ ∼ G(1, m, 1) for Z drawn from a spherical Laplace distribution. The rest follows from Corollary B.1 and Lemma B.7. 10

Similar arguments apply for the ρ-CGP variant. Notice √ that the magnitude of an m-dimensional standard Gaussian random vector has distribution G( 2, m, 2), then applying Corollary B.1 and Lemma B.8, we get: Lemma 3.5. Let ã = M (a) := a + √12ρ Σ1/2 Z, where Z ∼ N (0, Im×m ). Then M is ρ-CGP, and 1. E[dist2 (fã , fa )] =

√ √ Γ(m/2+1/2) m 2 Γ(m/2)√2ρ ≤ √2ρ ;

√ 2. dist2 (fã , fa ) ≤ η(β;m,2) with probability at least 1 − β, 2ρ

where η(β; m, 2) :=

m+2

p m ln(1/β) + 2 ln(1/β).

Multivariate functions. It is easy to see that the mechanisms in Theorems 3.2 and 3.3 hold nearly verbatim for multivariate functions, or equivalently, when the variable t is a vector (t1 , · · · , td ), where ti ∈ Ii ⊆ R, with the integrals appropriately defined over I := I1 × · · · × Id . The prototypical example is the space of multivariate polynomials over the reals. Note that in this case the computation of the matrix Σ is the same, and Σ remains m × m, where m is the number of linearly independent functions ϕj (·)’s we choose in the basis. Remark 3.6. All the mechanisms described in Section p 3 (above and henceforth) generalize to any metric induced by an inner product dist(u, v) := ⟨u − v, u − v⟩. In the most general case, the entries of Σ−1 become [Σ−1 ]j,l = ⟨ϕj , ϕl ⟩, and the matrix Σ−1 is also called the Gram matrix of {ϕj }j∈[m] .

3.3

Vector-valued Functions

P In the above, we discussed privatizing functions of the form fa : t 7→ m j=1 aj ϕj (t) for real-valued basis functions ϕj (·), and coefficients aj ∈ R for j ∈ [m], so fa (·) is also real-valued. Next, we discuss the scenario where fa (·) is vector-valued, which arises when either the basis functions ϕj (·)’s or the coefficients aj ’s are vector-valued. Vector-valued basis, real-valued coefficients. Suppose the basis functions ϕj (·)’s are vectorvalued, with ϕj (·) = (ϕj,1 (·), · · · , ϕj,n (·)) for j ∈ [m]. Let Uf = spanR ({ϕj }j∈[m] ). Then the L2 distance dist2 (·, ·) in this case can be computed from Z 2 dist2 (fy , fa ) = ∥fy (t) − fa (t)∥2 dt I

iT 2 P (y − a )ϕ (t) · · · (y − a )ϕ (t) dt j j j,1 j j j,n j j∈[m] I   Z X n X  = (yj − aj )(yl − al )ϕj,r (t)ϕl,r (t) dt Z

I r=1

n X

j,l∈[m]

Z (yj − aj )(yl − al ) I

r=1 j,l∈[m]

ϕj,r (t)ϕl,r (t) dt

n X



(y1 − a1 ) · · ·

r=1

= (y1 − a1 ) · · ·

 (y1 − a1 ) (r)   .. (ym − a′m ) Σ−1   .

(ym − am )   ! (y1 − a1 ) n X −1 (r)   .. (ym − a′m ) Σ   . r=1 (ym − am ) (1)

(n)

(r)

−1 −1 + · · · Σ−1 , where [Σ−1 ]j,l = RThus, Σ is still m × m, and can be computed from Σ = Σ I ϕj,r (t)ϕl,r (t)dt for r ∈ [n]. The dimension of Σ is not affected because although the basis functions are vector-valued, one coefficient is used for each basis function vector, no matter how large it is.

true privatized

6 8

true privatized

3 8

1 (a) I = [0, 2π], Σ = 2π I3×3

1 (b) I = [0, 4π], Σ = 4π I2×2

Figure 2: Example curves with vector-valued basis, fix ε = 1. (2a): [x1 (t), x2 (t)]T = 4.8 · [cos(t), sin(t)]T − 2 · [1, 0]T − 1 · [0, 1]T . (2b): [x1 (t), x2 (t)]T = 2 · [cos(t), sin(t)]T + 1 · [cos(t/2), sin(t/2)]T . Example 1. Consider the basis {ϕ1 } where the function ϕ1 : t 7→ [cos(t), sin(t)]T with I = [0, 2π], then a[cos(t), sin(t)]T describes a circle of radius |a| centered at the origin. Using our mechanism above, we only need to privatize the coefficient a, which is intuitive since all information about the curve is captured by the radius. If we want to account for shift, we can add the constant vectors ϕ2 (·) ≡ [1, 0]T , ϕ3 (·) ≡ [0, 1]T as basis functions. See Fig. 2a for an illustration of this example, and Fig. 2b for another example. Real-valued basis, vector-valued coefficients. In some cases, a function might be described more naturally by vector coefficients, while the basis functions are real-valued. Example 2. An ellipse can be described by a two-variable polynomial, or a parametric curve with vector coefficients as [x1 (t), x2 (t)]T = a1 cos(t) + a2 sin(t) + a3 where aj = [aj,1 , aj,2 ]T for j ∈ [3], and I = [0, 2π]. See Fig 3a for a zero-centered ellipse. Example 3. Another example is the basis {ϕ1 , ϕ2 } where ϕ1 : t 7→ t, ϕ2 : t 7→ 1, and I = [0, T ]. Then x1 (t) a1,1 a2,1 = · ϕ1 (t) + · ϕ2 (t) x2 (t) a1,2 a2,2 12

true privatized

22.5

20.0

17.5 15.0

12.5

10.0

7.5

5.0

0.0

(a) I = [0, 2π], Σ = π1 I4×4

2.5

5.0

(b) I = [0, 4], Σ =

7.5

10.0

−6 16

16 −6 16

Figure 3: Examples with vector-valued coefficients, fix ε = 1. (3a): [x1 (t), x2 (t)]T = [3, −1]T · cos(t) + [5, 3.5]T · sin(t). (3b): [x1 (t), x2 (t)]T = [3, −1]T · t + [5, 3.5]T · 1. describes a 2D linear curve (see Fig. 3b), which is useful for approximating 2D trajectories. In general, suppose each aj = [aj,1 , · · · , aj,n ]T for j ∈ [m]. We have Uf = spanRn ({ϕj }j∈[m] ) where each ϕj : I → R. Then Z 2 dist2 (fy , fa ) = ∥fy (t) − fa (t)∥2 dt ZI T (y1,1 − a1,1 ) · · · (y1,n − a1,n ) ϕ1 (t) + · · · = I

+ (ym,1 − am,1 ) · · · = =

Z X n

(yj,r − aj,r )(yl,r − al,r )

ϕj (t)ϕl (t)dt I



(y1,r − a1,r ) · · ·

r=1



ϕm (t) dt

r=1 j,l∈[m]

((y1,r − a1,r )ϕ1 (t) + (ym,r − am,r )ϕm (t))2 dt

I r=1 n X X

n X

(ym,n − am,n )

 (y1,r − a1,r )   .. (ym,r − am,r ) Σ−1  . 0  (ym,r − am,r )

T





y1,1 − a1,1 y1,1 − a1,1     .. ..     . .     ym,1 − am,1  ym,1 − am,1        −1   . . . . =   Σ  . .      y1,r − a1,r   y1,r − a1,r          .. ..     . . ym,r − am,r ym,r − am,r 13

R −1 −1 is an mn × mn block where Σ−1 0 is an m × m matrix with entries [Σ0 ]j.l = I ϕj (t)ϕl (t)dt, and Σ matrix, with Σ−1 0 repeated in the diagonal. For a finite-dimensional function space Uf , let dim(Uf ) denote its dimension; i.e. dim(Uf ) is the number of columns of its associated Gram matrix. From the discussions above and Lemma 3.4, we have: P Corollary 3.1. For fa = j aj ϕj ∈ Uf := spanRna ({ϕj }j∈[m] ), let ã = M (a) := a + 1ε Σ1/2 Z where Z is a standard spherical Laplace random vector and dim(Uf ) = na · m. Then M is ε-GP, and 1. E[dist2 (fã , fa )] = 2. dist2 (fã , fa ) ≤

dim(Uf ) ; ε

η(β;dim(Uf ),1) with probability at least 1 − β. ε

Similarly, from Lemma 3.5, we have: Corollary 3.2. For fa , Uf and dim(Uf ) as in Corollary 3.1, let ã = M (a) := a + √12ρ Σ1/2 Z where Z is a standard Gaussian random vector. Then M is ρ-CGP, and √ √ Γ(dim(Uf )/2+1/2) dim(Uf ) √ √ ; 1. E[dist2 (fã , fa )] = 2 Γ(dim(U )/2) 2ρ ≤ 2ρ f

2. dist2 (fã , fa ) ≤

3.4

η(β;dim(Uf ),2) √ with probability at least 1 − β. 2ρ

Arbitrary Functions

So far, we have focused on functions that are linear combinations of a given set of basis functions. In this subsection, we consider the most general case where the function q to be privatized is not assumed to take any specified form, i.e., it is taken from L2 (I), the entire space of square-integrable functions. Note that this is an infinite-dimensional space. We shall focus on GP algorithms; translating such algorithms to their CGP variants is straightforward, with details deferred to Appendix C. Project-and-privatize. A natural approach to reduce this problem to the previous one would be to first project q into Uf defined with respect to some basis {ϕj }j , then privatize its projection. Specifically, let PUf : U → Uf be a function that computes the least squares projection onto Uf . We also write PUf (q) = fa(q) where a(q) denotes the coefficients of the approximation. We summarize this simple approach in Algorithm 2. Algorithm 2 Project-and-Privatize Input: q : I → Rn ; finite-dimensional function space Uf ; ε > 0 Output: privatized q̃ 1: compute Σ from Uf 2: a ← coefficients of PUf (q) 3: ã ← a + 1ε Σ1/2 Z, Z ∼ SLap(dim(Uf )) 4: return

fã

To prove the privacy of Algorithm 2, we need the following standard result (e.g. see [DD01]): 14

Lemma 3.7. Let Uf be a finite-dimensional function space. Then for any pair of q, q ′ ∈ U , dist2 (fa(q) , fa(q′ ) ) ≤ dist2 (q, q ′ ), where fa(q) , fa(q′ ) denote the least squares projections of q and q ′ onto Uf , respectively. Lemma 3.8. Algorithm 2 is ε-GP. Proof. Let Mf : Uf → Uf be the mechanism that privatizes PUf (q), which is ε-GP on (Uf , dist2 ) by previous discussions. Let M : U → Uf denote the mechanism in Algorithm 2. We have for any measurable Sf ⊆ Uf and any pair q, q ′ ∈ U Pr[M (q) ∈ Sf ] = Pr Mf (PUf (q)) ∈ Sf ≤ eε dist2 (fa(q) ,fa(q′ ) ) Pr Mf (PUf (q ′ )) ∈ Sf = eε dist2 (fa(q) ,fa(q′ ) ) Pr M (q ′ ) ∈ Sf . Thus, if we can show that dist2 fa(q) , fa(q′ ) ≤ dist2 (q, q ′ ), then M satisfies the GP requirement on U w.r.t. dist2 . The required inequality then follows from Lemma 3.7. The detailed formulas for computing the least squares projections for both real-valued and vector-valued functions are provided in Appendix E. Next, we discuss the L2 error of Algorithm 2. By simple triangle inequality, we have E[dist2 (q, fã )] ≤ dist2 (q, fa ) + 1b E[∥Z∥]. Below, we provide a tighter analysis. Lemma 3.9. Let Uf be the subspace given by the span of {ϕj (·)}j∈[m] . For q ∈ U , let fa ∈ Uf be a projection of q in Uf . For ã := a + 1b Σ1/2 Z where Z is a random vector with mean zero, we have E[dist2 (q, fã )2 ] = dist2 (q, fa )2 +

1 E[∥Z∥2 ]. b2

As one would expect, the simple mechanism incurs large error if q cannot be approximated well by any fa ∈ Uf . On the other hand, if Uf has large dimension, then we might still end up with a large error from the noise vector ∥Z∥ even if q is well approximated by Uf . Thus, the challenge is to select a basis {ϕj }j that strikes a balance between the two sources of error. Critically, the selection must also be done in a private manner. A private, balanced selection. Let {ϕj (·)}j∈J be a pre-selected collection of basis functions indexed by J. We assume that q can be approximated by these basis functions to some accuracy γ = O(1/ε) that the analyst is content with, absent privacy. Otherwise, a general-purpose dense basis allowing arbitrary γ > 0 can be used, where J is infinite, such as Hermite functions for L2 (R), the Fourier basis {1, sin(jt), cos(jt)}j∈N for L2 ([−π, π]), or monomials {1, tj }j∈N for L2 ([0, T ]). Our algorithm (Algorithm 3) follows roughly these steps: 1. Identify a large enough basis that approximates q well; 2. Project and privatize q, obtain the first approximation q̃0 ; 3. Based on the coefficients of q̃0 , identify and eliminate the ones with (relatively) small magnitude, as they contribute less to the approximation quality but increase the noise; 4. Project q onto the space spanned by the remaining basis functions, and privatize. 15

Algorithm 3 PrivFuncSelect Input: q : I → Rn ; {ϕj }j∈J ; β > 0; ε > 0 Output: privatized q̃ ε ε 1: k0 ← SVT(q, ( 12 , 6 ), − 4ε , 1, g1 , g2 , . . . ), gj (·) := − dist2 (P

(j)

(k0 )

2: q̃0 ← Project-and-Privatize(q, Uf

(·), ·)

, ε/4)

(k0 ) 3: c̃ ← coefficients of q̃0 in Uf 4: s(r) ← rth largest magnitude among c̃, r ∈ [k0 ] ε ε , 6 ), 0, 1, g1′ , g2′ , · · · ), Nr := {j 5: k1 ← SVT(q, ( 12 (r) bj := c̃j · 1{j ∈ Nr }

r| : ∥c̃j ∥ ≥ s(r) }, gr′ (·) := n|N ε/4 − dist2 (fb(r) , ·),

6: Uf ← span({ϕj : j ∈ Nk1 }) 7: fã ← Project-and-Privatize(q, Uf , ε/4) 8: return

fã (j)

For j ≥ 1, let Uf denote the subspace spanned by the first j basis functions, Let PU (j) (q) denote f

(j)

the least-squares projection of q in Uf . In step (1) above, we want to find j such that PU (j) (q) is f

sufficiently small (e.g. O(1/ε)). We use SVT on g1 , g2 , . . . where each gj (q) := − dist2 (PU (j) (q), q) f

is 1-Lipschitz, as in line 1 of Algorithm 3. Then we apply project-and-privatize in line 2-3, where c̃ are the privatized coefficients of q̃0 . To decide which basis functions to keep, we order the noisy coefficients in c̃ based on their magnitude, and create candidate sets Nr := {j : ∥c̃j ∥ ≥ s(r) }, where (r) s(r) is the rth largest magnitude. We use bj = c̃j · 1{j ∈ Nr } to approximate the projection that corresponds to muting the coefficients not in Nr . We run SVT to find which candidate set has approximately balanced noise and approximation error, by using the sequence g1′ , g2′ , · · · where r| gr′ (·) := n|N ε/4 − dist2 (fb(r) , ·), which are 1-Lipschitz, and finding where they first cross zero, as in line 5. Finally, we perform a final project-and-privatize, using the basis set Nk1 identified by the second SVT call, as in lines 6-7. Privacy. Algorithm 3 is ε-GP by basic composition in Lemma 2.3, where ε/4 is used in each of lines 1, 2, 5, 7. Utility. The goal of the first SVT is to identify a large enough subset of basis functions from a given basis that is assumed to approximate q well, while that of the second SVT is to further refine the selection by approximately balancing the privatization noise and approximation error. By the generic guarantee of SVT in Lemma 2.4, both goals are approximately achieved: In each SVT call, we might overshoot the target in value by O(log(1/β)/ε) resulting in an extra subset of basis functions of size O(log(1/β)), or undershoot in value from the threshold by at most O ((log(1/β) + log(k ∗ /β)) /ε), where k ∗ denotes the index of the balance point. Thus, Algorithm 3 meets our goal of providing a roughly balanced selection. While Algorithm 3 has addressed the problem of how to select a set of good basis functions from a given collection, we have not touched the issue of how to decide which collection to use. Certainly, the choice of the basis also has a large impact on the utility of the algorithm, but this is

largely application-dependent. For example, if the functions tend to be periodic, then the Fourier basis is preferred; for data arising from signal processing (e.g. ECG data), sinc functions can be used; if the function is a curve, then piecewise basis functions are better (see Section 4). Thus, this decision is best made at the application level.

3.5

Projecting [0, T ]-functions onto R-functions

In previous discussions, we had assumed that both the function q and the basis {ϕj }j are functions on the same domain I. In fact, it is possible to separate the domains, in particular for the case where one is R and the other is a finite interval. In some cases, it might even be beneficial to do so, for example when it gives a matrix Σ that is easier to work with. Let sinc(t) := sin(πt) be the πt normalized sinc function. The set of functions {sinc(t−k)}k∈Z is square-integrable on R (hence also R∞ 2 on [0, T ]); moreover, the set {sinc(t − k)}k∈Z is an orthonormal basis with −∞ sinc(t − k) = 1 and R∞ −∞ sinc(t − k) · sinc(t − l)dt = 0 for k ̸= l. We would like to use this readily available orthonormal basis, which is also commonly used for approximating functions that arise in signal processing. We will show that using such a basis in L2 (R) for a curve in C([0, T ]) only requires little additional work1 , and the privacy guarantee follows similarly to the discussion above. Here, I always refers to the domain of the function q, and dist2 is defined in terms of I. Using L2 (R) for (C([0, T ]), dist2 ). We consider the case where q ∈ U = C([0, T ]) is a continuous function on the interval [0, T ], but its privatization uses functions from L2 (R). Define a function L : U → L2 (R) by ( q(t) t ∈ [0, T ] L(q)(t) := 0 otherwise. I.e., of q which takes inputs from R. Let L(U ) := {L(q) : q ∈ U }. Notice R R ∞ L(q) is 2the extension 2 dt < ∞, so L(U ) ⊂ L2 (R). Given an m-dimensional subspace L ⊆ L(q)(t) dt = q(t) f −∞ [0,T ] L2 (R), let P : U → Lf be the function that computes the least squares projection of L(q) in Lf , R∞ ′ 2 ′ 2 ′ i.e. P : q 7→ fa(L(q)) . Let us write dist2,R (u, u ) = −∞ (u(t) − u (t)) dt for u, u ∈ L (R). Now, from Section 3.2 we have a GP mechanism Mf for privatizing P(q) ∈ Lf w.r.t. dist2,R . Define a mechanism M1 : U → Lf , where M1 (q) = Mf (P(q)). Then M1 satisfies for all q, q ′ , and all measurable Sf ⊆ Lf Pr[M1 (q) ∈ Sf ] = Pr[Mf (P(q)) ∈ Sf ] ′ ≤ eε dist2,R (P(q),P(q )) Pr Mf (P(q ′ )) ∈ S ′ = eε dist2,R (P(q),P(q )) Pr M1 (q ′ ) ∈ Sf . Also, since L(U ) ⊂ L2 (R), Lemma 3.7 holds when we replace the metric space (U, dist2 ) with (L(U ), dist2,R ) in the statement. Thus, dist2,R (P(q), P(q ′ )) = dist2,R (fa(L(q)) , fa(L(q′ )) )

Lemma 3.7

≤

dist2,R (L(q), L(q ′ )) = dist2 (q, q ′ );

i.e. M1 is ε-GP w.r.t. dist2 . 1

Note the approximation quality could be different, see discussion in Appendix E.4

Privatization of Curves

A curve is a continuous function [0, T ] → Rn . Unlike the case of arbitrary function privatization which assumes a suitable Uf is given, for privatizing curves there are well known sets of basis functions that approximate continuous functions well. Based on this fact, in this section we provide another algorithm more suitable for curves.

4.1

Privatization of piecewise functions

Before we present our algorithm for arbitrary curve privatization, we discuss how piecewise functions can be privatized using the framework developed in Section 3.2. For ease of discussion we assume the coefficients are real-valued in Sections 4.1.1 and 4.1.2 below; the discussions adapt to the vector-valued case by repeating the operations in each coordinate, as explained in Section 3.3. 4.1.1

Defining piecewise basis functions

Let 1A : I → {0, 1} be the indicator function that checks whether a point is in the set A, i.e., 1A (t) = 1 if t ∈ A and 0 otherwise. Clearly, two indicator functions 1A (·) and 1A′ (·) are linearly independent if A ̸= A′ . Let As = [Ts−1 , Ts ) for s ∈ [k], and 0 = T0 < T1 < · · · < Tk = T . If a set of functions {ϕj (·)}j∈[m] is linearly independent on each As , then the set {ϕs,j }s∈[k],j∈[m] , where ϕs,j (t) := 1As (t)ϕj (t), is also linearly independent on [0, T ] as long as each ϕs,j (·) is not identically zero. Since the latter set has size mk, the matrix Σ becomes P mk P × mk. In particular, ordering the coefficients as a = [a1,1 , . . . , a1,m , a2,1 , . . . , ak,m ]T , so fa (t) := s j as,j · 1As (t)ϕj (t), we get   −1 Σ(1) 0 ··· 0   −1  0 Σ(2) ··· 0  −1   Σ :=  . .. ..  , .. . . . . .   0 where each Σ(s)

−1

is m×m, with [Σ(s)

−1

···

Σ(k)

−1

For example, applying to t∈As ϕj (t)ϕl (t)dt for s ∈ [k]. 1 3 1 3 2 2 (T −1 s − Ts−1 ) 2 (Ts − Ts−1 ) (s) 3 piecewise linear functions with {ϕ1 : t 7→ t, ϕ2 : t 7→ 1}, we get Σ = 1 2 , 2 Ts − Ts−1 2 (Ts − Ts−1 ) ]j,l =

which gives





−6(Ts +Ts−1 ) (Ts −Ts−1 )3 2 2 ) . 4(Ts +Ts Ts−1 +Ts−1 3 (Ts −Ts−1 )

12 (Ts −Ts−1 )3 Σ(s) =  −6(T s +Ts−1 ) (Ts −Ts−1 )3

Thus, although the matrix Σ for piecewise linear functions is 2k × 2k, matrix multiplication can be done at each sub-matrix Σ(s) after obtaining the 2k-dimensional random vector Z, i.e., the number of multiplications is 4k instead of 4k 2 . Remark 4.1. N.B. Although the multiplications can happen at the sub-vector level, the noise vector Z from the spherical Laplace distribution must be drawn together as a single vector. Drawing the noise vector together enables an effect that is reminiscent of parallel composition in DP; using separately drawn sub-vectors would require splitting the privacy budget among the component privatizations that use these sub-vectors, which would not be ideal. On the other hand, Gaussian noises can be separately drawn, as uncorrelated Gaussian random variables are also independent, a desirable property enjoyed solely by the Gaussian distribution! 18

4.1.2

Ensuring continuity

The privatization mechanism where noise is added to each segment described above might result in a privatized curve that is only continuous within each segment, and discontinuous at the segment end points Ts ’s. If continuity is desired, a post-processing step may be added where the privatized curve is replaced with a continuous one that is nearest to it. That is, given privatized function fã , we find fâ with limt↑Ts fâ (t) = fâ (Ts ) for 1 ≤ s ≤ k − 1, such that dist2 (fã , fâ ) is minimized. Such a process may increase the initial error by at most two times. Indeed, let fa ∈ Uf denote the original continuous function, then dist2 (fâ , fa ) ≤ dist2 (fâ , fã ) + dist2 (fã , fa ) ≤ 2 dist2 (fã , fa ), where the last inequality is due to fâ being the nearest continuous curve to fã in Uf . 2 Equivalently, we want to minimize − ã)T Σ−1 (y − ã) = y T Σ−1 y P − 2ãT Σ−1 y + P dist2 (fy , fã ) = (y P T ã ã, and fy is continuous at Ts iff j∈[m] ys,j · ϕj (Ts ) = j∈[m] ys+1,j · ϕj (Ts ) ⇐⇒ j∈[m] (ys,j − ys+1,j )ϕj (Ts ) = 0, for 1 ≤ s ≤ k − 1. I.e., the projection process can be formulated as the following quadratic program with linear equality constraints: 1 T −1 y Σ y − ãT Σ−1 y 2 subject to Cy = 0, minimize y

where y = [y1,1 , · · · , y1,m , · · · , yk,1 , · · · , yk,m ]T ∈ Rkm , and the matrix C ∈ R(k−1)×(km) is   ϕ1:m (T1 ) −ϕ1:m (T1 ) 0 ··· 0   0 ϕ1:m (T2 ) −ϕ1:m (T2 ) · · · 0   C :=   .. .. .. .. ..   . . . . . 0

···

−ϕ1:m (Tk−1 )

where ϕ1:m (Ts ) = [ϕ1 (Ts ), · · · , ϕm (Ts )] ∈ Rm .

4.2

Privately approximating curves via piecewise functions

In this subsection, we present an algorithm for arbitrary curve privatization using piecewise basis functions. Our algorithm tries to find a suitable finite-dimensional Uf , and performs a Project-andPrivatize of q onto Uf . The space Uf is generated from a set of sub-intervals and an input real-valued basis {ϕj }j , and has the property that the error from the approximation PUf (q) is roughly equal to dim(Uf ). The process to find Uf is composed of two parts, provided in sub-algorithms PrivFuncSeg (Algorithm 4) and ReduceSeg (Algorithm 5), which we discuss in detail below. PrivFuncSeg. We are given a (small) set of basis functions {ϕj }j , which should provide good approximations to continuous functions when restricted to a small sub-interval. The goal of PrivFuncSeg is find the number of sub-intervals, such that when we fit {ϕj }j to each sub-interval, we get an overall curve which roughly balance the two sources of error mentioned above. We do so via SVT where we double the number of sub-intervals in each check. Let q : [0, T ] → Rn be the input curve. For j = 0, 1, 2, · · · , let PU (j) (·) compute the best approximation using 2j sub-intervals f

with end points at {r 2Tj : r = 0, 1, 2, · · · , 2j }; i.e. PU (j) (q) is the least squares projection of q onto f

Algorithm 4 PrivFuncSeg Input: q : [0, T ] → Rn ; {ϕj }j∈[m] ; β > 0; ε > 0 Output: privatized q̃ j

mn 1: k̄ ← SVT(q, (ε/12, ε/6), 0, 1, g0 , g1 , g2 , · · · ), where τj = 2ε/4 , gj (q) := τj − dist2 (P

(j)

(q), q),

PU (j) computes best approximation using 2j sub-intervals f

2: B ← 3ε/4, privacy budget for remaining steps 3: S ← {jT /2k̄ : j = 0, 1, 2, · · · , 2k̄ } 4: k1 ← min(k̄ − 2, 4) 5: if k1 ≥ 1 then

for i = 1, . . . , 4 do Ŝi ← ReduceSeg(q, (i − 1)T /4, iT /4, k1 , 1, Si , β, B, ε/16), Si := S ∩ [(i − 1)T /4, iT /4] 8: end for 9: end if 10: Ŝ ← ∪i Ŝi = {0 = T0 , T1 , . . . , TN = T }; N ← |Ŝ| − 1 11: Uf ← span({ϕj · 1[Ts−1 ,Ts ) }s∈[N ],j∈[m] ) 12: fã ← Project-and-Privatize(q, Uf , B) 13: return fã 6: 7:

(j)

the space Uf

(j) := spanRn {ϕl · 1A(j) }l∈[m],r∈[2j ] , where Ar := [(r − 1) 2Tj , r 2Tj ). We run SVT on r

(j)

the queries gj (q) := τj − dist2 (PU (j) (q), q) with privacy budget 4ε , where τj := f

dim(Uf ) ε/4

mn = 2ε/4

is the expected error due to privatization of PU (j) (q). Note that dist2 (PU (j) (·), ·) is 1-Lipschitz, f

and so is gj (·). Moreover, the sequence gj (q) strictly increases, since τj strictly increases while dist2 (PU (j) (q), q) is non-increasing with j. f

𝑙=1 𝑙=2 𝑙=3

Figure 4: Example illustration for sub-interval removal process in ReduceSeg. 32 sub-intervals at the start of level 1; 20 sub-intervals at level 2; 18 sub-intervals at level 3, and the process terminates here. ReduceSeg. After we find that 2k̄ (evenly spaced) sub-intervals suffice to roughly balance the two sources of error, the goal of ReduceSeg is to remove sub-intervals that are not needed, since the curve might be flatter in some segment of [0, T ]. To this end, we partition the sub-intervals into 4 parts, where we then try to reduce the number of sub-intervals in each part. For each part, we perform at most 24 checks over at most k1 ≤ 4 levels. Let ε′ be the allocated budget for the l current interval [ts , te ]. Starting at level l = 1, we use 2ε′ to check whether reducing the number of segments by half results in a decrease in error. If so, we remove half of the segments and proceed to check the children intervals [ts , (te + ts )/2] and [(te + ts )/2, te ] at level l = 2, and so on, until 20

Algorithm 5 ReduceSeg Input: q : [0, T ] → Rn ; [ts , te ) ⊂ [0, T ]; k1 ; l ≤ k1 ; set S containing breakpoints to be checked; β > 0; B ≥ ε′ > 0 Output: Ŝ after reducing the number of sub-intervals 1: if l > k1 then

return S 3: end if 4: k ← log2 (|S| − 1); s 5: S ′ ← {2r te2−t + ts : r = 0, · · · , 2k−1 } {try to reduce number of sub-intervals by half} k 6: f[ts ,te ] ← best approx. of q on [ts , te ] using break points in S ′ 2:

7: err ← dist2 (f[ts ,te ] , q · 1[ts ,te ] ) + 2ε′ Z, Z ∼ Lap(1) ′

8: B ← B − 2εl l

k−1

emn 9: if err + 2ε′ (k1 ln(2) + ln(1/β)) ≤ 22(e−1)B then

′ ← S ′ ∩ [(t + t )/2, t ] SL′ ← S ′ ∩ [ts , (ts + te )/2], SR s e e ′ 11: ŜL ← ReduceSeg(q, ts , (ts + te )/2, k1 , l + 1, SL , β, B,ε′ /2) ′ , β, B,ε′ /2) 12: ŜR ← ReduceSeg(q, (ts + te )/2, te , k1 , l + 1, SR 13: Ŝ ← ŜL ∪ ŜR 14: else 15: Ŝ ← S 16: end if 17: return Ŝ

10:

we finish level l = k1 . See Fig. 4 for an example illustration of the sub-interval removal process corresponding to running ReduceSeg on all four parts together (lines 5-9 of Algorithm 4). It is straightforward to check that ReduceSeg consumes at most ε′ of the P privacy budget, since at each ε′ 1 ε′ 1 level l there are at most 2l−1 calls, each uses 21l of 2l−1 2l−1 2l−1 , for a total of kl=1 = (1 − 2k11 )ε′ . 2l Privacy. The entire algorithm satisfies ε-GP, since ε/4 is used in the SVT call, at most ε/4 is used for ReduceSeg, and the remaining is used for Project-and-Privatize; the remaining budget depends on the actual number of times ReduceSeg is invoked, but the overall privacy guarantee is the same by a privacy filter argument (e.g. see [FZ21, LY26]). Utility. In the SVT call, the potential overshoot in the target position is O(log log(1/β)), since the queries gj increase at a rate of 2× after the balance point. This also means the number of sub-intervals 2k̄ is potentially O(log(1/β)) times larger than the size at the balance point, hence the need to reduce. ReduceSeg is capable of reducing the number by a factor of 2k1 , comparable to O(log(1/β)) for any constant β, if every call results in a reduction. In any case, we show below that in the worst case, ReduceSeg does not increase the overall error. η(β;dim(Uf ),1) Let ErrBound(fã , ε, β; q, 1)) := dist2 (fa , q)+ for Uf ∋ fa := PUf (q), and fã obtained ε from privatizing fa as in Theorem 3.2. Note that ErrBound(fã ; q, ε, β, 1)) provides a high probability bound on dist2 (fã , q), the L2 error of fã as an approximation for q, since dist2 (fã , q) ≤ dist2 (fa , q) + dist2 (fa , fã ) 21

1 = dist2 (fa , q) + ∥Z∥ ≤ ErrBound(fã , ε, β; q, 1) ε where the latter holds with probability 1 − β for Z ∼ SLap(dim(Uf )). Lemma 4.2. Let Ŝ be the set of breakpoints resulting from running ReduceSeg(q, ts , te , k1 , k, 1, S, β2 , B, ε′ ). Let q̃Ŝ be obtained from the ε/2-GP privatization of the best approximation of q on the interval [ts , te ] using breakpoints in Ŝ, let q̃S be defined similarly for the set S. Then with probability 1 − 32 β, dist2 (q̃Ŝ , q) ≤ ErrBound(q̃S ; q, ε/2, β, 1)). Additional discussion on ReduceSeg. ReduceSeg is an optional step; its goal is remove redundant sub-intervals, which may happen when the curve is relatively flat on a sub-segment of the domain, as stated earlier. As such, it will not be useful for curves that do not stay flat for sufficiently long. Example curves where ReduceSeg is useful and not useful are provided in Fig. 5. By Lemma 4.2 above, however, there is no harm in choosing to run ReduceSeg (minus the privacy budget it consumes), since it will not remove sub-intervals that help with the approximation. In particular, line 9 in Algorithm 5 ensures that sub-intervals are only removed when it results in an overall decrease in the error. 2500

true privatized

2500

true privatized

2500

2000

1500

1000

500

250

500

750 1000 1250 1500

(a) q1 without ReduceSeg, N = 64

250

500

750 1000 1250 1500

(b) q1 with ReduceSeg,

500

true privatized 0

250

500

750 1000 1250 1500

N = 42

N = 32

true privatized 0

250

500

750 1000 1250 1500

(d) q2 with ReduceSeg, N = 32

Figure 5: Stylized trajectories q1 , q2 privatized without and with ReduceSeg, each using total budget ε = 1. Here, q1 benefits from ReduceSeg while q2 does not. Sub-intervals were reduced on flatter segments of q1 , as shown in (b), resulting in noise reduction. The acute reader may notice that some parameters in Algorithm 5 may be left as hyperparameters that can be further tuned. Indeed, there might be better choices for the number of partitions on which to call ReduceSeg, as well as the maximum depth k1 of the recursion tree in ReduceSeg. These two parameters might be further tuned, for example, using public data; together they determine the total number of times ReduceSeg is called. The privacy budget allocated for each such call decreases as the number of calls increases, which makes ReduceSeg less useful since it will return early at line 9 without successful reduction (due to noisier estimation of the potential utility gain). On the other hand, a small number of calls to ReduceSeg directly limits how many sub-intervals can be removed. For simplicity, we set the parameters conservatively to be 4, knowing that by Lemma 4.2 even sub-optimal parameters do not harm the utility.

4.3

Extending to unbounded intervals

In this subsection, we briefly describe how we can extend the previous algorithm for curve privatization on [0, T ] to an unbounded interval. This is useful for when the function is defined on R, and we wish to estimate it using functions integrable on finite intervals (e.g. polynomials). Using L2 ([0, T ]) for (C(R), dist2 ). Suppose U ⊆ C(R) ∩ L2 (R), so q ∈ U is both continuous and square-integrable on the entire real line. In order to use Algorithm 4 above for such a function, we first find an approximate T̄ such that clipping the function to the interval [−T̄ , T̄ ] (i.e. setting the function value to zero outside the interval) introduces a small amount of error, say O(1/ε). To qonly qR RT ∞ 2 dt − 2 find such a T̄ , define a function gT : q 7→ q(t) −T −∞ q(t) dt. Note that gT is 2-Lipschitz w.r.t. to the dist2 metric. Then we can use SVT on the sequence of queries gT1 , gT2 , . . . , where Tj = 2j for j ≥ 1, with threshold set to −1/ε. After obtaining T̄ , we run Algorithm 4 on the function q · 1[−T̄ ,T̄ ] , and return the R-extension of the privatized curve as output.

Experiments

In this section, we provide experimental evaluation of our algorithms on several datasets. Here, we present the results for mechanisms in the GP model, deferring results of their CGP variants to Appendix C.3. Baseline methods. There are no prior work for function privatization in the local model, to the best of our knowledge. However, a method for releasing (a subset of) a collection of points under GP/CGP was provided in [LY23]; since the privatized points can be connected together to form a piecewise curve, we will use this as our main baseline. The method in [LY23] samples k points for some fixed k > 1, and privatizes each sampled point under GP/CGP using Lemma 2.2; by applying basic composition to k points, the release of these points together satisfies GP w.r.t. the dist∞ metric, where dist∞ (q, q ′ ) := sup[0,T ] ∥q(t) − q ′ (t)∥. The privacy definitions using the two metrics dist2 and dist∞ are incomparable in terms of strength and purpose, where dist2 considers the functional data as a whole, while dist∞ aims to provide protection for each released point. Nevertheless, the aforementioned method from [LY23] serves as a good reference for understanding the problem at hand, and for lacking a better alternative. In the privatized points, substantial fluctuations might occur between consecutive points due to the large noise injected, especially when the privacy budget is small. To mitigate such effects, we also apply smoothing in the baseline method with sliding windows (labeled as “Baseline (smoothed)”). We evaluated various combinations of the number of samples k, where the points are evenly spaced, and the sliding window size s; in each plot, the best combination with the minimum error is shown for each parameter setting. Datasets.

We conduct experiments on three datasets:

1. ECG records. The PTB-XL Electrocardiography (ECG) dataset [WSB+ 22, WSB+ 20, GAG+ 00] contains 21799 clinical 12-lead ECGs of 10 seconds length and 100 Hz sample frequency. We select the Lead II data of the first 100 records, scale the samples to the unit of microvolt, and perform linear interpolation on them. 23

2. Taxi trajectory. The CRAWDAD dataset [PSDG22] contains the mobility traces of approximately 500 cabs in San Francisco Bay Area. The GPS coordinates are converted to points in R2 , with meters as the unit. We perform linear interpolation between consecutive points to convert the time series data into continuous trajectory functions from [0, T ] to R2 , for a total of 304 curves recorded over a 12-hour window. 3. Synthetic Gaussian mixtures. We randomly generate 50 synthetic curves, where each instance is a linear combination of 1 to 5 random Gaussian functions. We report both the average L2 error and the L2 -squared error (the mean of which is the functional analogue of MSE). The averages are computed over all simulations of all functions in the respective dataset, where the errors are normalized by the L2 norm of the original input curve.

5.1

Evaluation on Project-and-Privatize

Some types of data are known to be approximable by certain finite-dimensional spaces, either due to public available data or expert knowledge. ECG data are one such example, and they can be well approximated by a sufficient number of sinc functions. Here, we show that the simple Project-and-Privatize method (Algorithm 2) suffices for privatization. We use the normalized sinc function basis {ϕj (t) = sinc(t − j)}j∈[m] defined in Section 3.5, and incorporate the technique discussed there where the basis functions are treated as being defined on R. Since a normal QRS length2 is between 0.08-0.10 seconds (public information), we scale the time domain by 80 times (so T = 800) to allow the central zero-crossings of a sinc function to approximately capture that length (alternatively, sinc functions with appropriately scaled non-integer zero-crossings can be used). We use m = 800 sinc functions for our algorithm. The baseline methods use the number of samples k ∈ {100, 200, 800}, and smoothing parameter s ∈ {k/20, k/10}. Each method is applied on each record for 30 simulations. 101

102

Project-and-Privatize Baseline Baseline (smoothed)

101

100

100 10 1

10 1

10 2 0.1

0.2

0.5

Privacy Budget

1.0

2.0

0.1

(a) L2 error

0.2

0.5

Privacy Budget

1.0

2.0

(b) L2 -squared error (MSE)

Figure 6: GP results on ECG dataset In Fig. 6, we evaluate the performances of the methods at various privacy levels. We see significant utility improvement in our mechanisms over the baseline methods, reaching up to an order of magnitude for the average L2 error, and up to 2 orders orders of magnitude in the MSE, for some parameter settings. Also, the utility gap gets larger as the privacy budget increases. We also present an example curve privatized by GP in Fig. 7 to see how the methods perform in terms of capturing the signals in the data. The baseline method presented uses k = 100 samples, 2

The period of ventricular depolarization, covering the Q, R and S waves.

amplitude ( V)

400

True

Project-and-Privatize

True

Baseline

Baseline (smoothed)

300 200 100 0 100

amplitude ( V)

400 200 0 200

time (s)

Figure 7: Example of privatizing a ECG record. ε = 1.0 with smoothing s = 5. We see that our mechanism is able to capture all the large and medium-sized peaks, thus retaining the important signals in the data. In contrast, the baseline methods struggle to capture the positions of most of the peaks, as ECG records are rich in information which are difficult to be captured with sampling. Also, even though smoothing helps with the L2 error, it also removes the important signals from the data in this case.

5.2

Evaluation on privately selecting a basis.

In this subsection, we evaluate the performance of our adaptive basis selection method (Algorithm 3) against the baseline methods, on synthetic Gaussian mixtures over the interval I = [0, 100]. Our mechanism selects a basis from the set of monomials of degree at most 32, and the baseline methods use the number of samples k ∈ {10, 20, 50, 100} with smoothing parameter s = k/10. Each method is applied on each curve for 30 simulations. 102

PrivFuncSelect Baseline Baseline (smoothed)

104 103

101

102 101

100

100 0.001 0.002

0.005 0.01

0.02

Privacy Budget

0.05

10 1

0.1

(a) L2 error

0.001 0.002

0.005 0.01

0.02

Privacy Budget

0.05

0.1

(b) L2 -squared error (MSE)

Figure 8: GP results on synthetic Gaussian curves We evaluate the methods at various privacy levels in Fig. 8. We see obvious improvement in our mechanisms over the baseline methods, in both the L2 and MSE error, over all parameter settings. Note that Gaussian mixtures are very smooth, so it seems reasonable to use the baseline methods for privatization on these; however, they are still outperformed by our mechanisms. Fig. 9 shows an example of privatizing a synthetic curve, which is a linear combination of two Gaussian functions. Our mechanism selects 8 monomial basis. The baseline methods uses 10 samples and smoothing parameter s = 3. 25

200

250

True PrivFuncSelect

True Baseline Baseline (smoothed)

200

150

150 100

100

50 0

100 150 0

100

Figure 9: Example of privatizing a synthetic curve. ε = 0.1.

5.3

Evaluation on curve privatization

Finally, we evaluate the performance of our curve privatization mechanism (Algorithm 4) against the baseline methods, on the taxi trajectory dataset and on synthetic Gaussian curves. Each method is applied on each curve for 30 simulations. For a trajectory curve with N points, the number of samples k ∈ {N/10, N/5} and smoothing parameter s ∈ {k/20, k/10} are used in the baseline methods. We also apply the post-processing program in Section 4.1.2 to obtain continuous versions of our privatized curves, and they are labeled as “PrivFuncSeg (continuous)”.

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

102

101

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

107 105 103

100

101

10 1

10 1 10 3

10 2 0.001 0.002

0.005 0.01

0.02

Privacy Budget

0.05

0.1

0.001 0.002

(a) L2 error

0.005 0.01

0.02

Privacy Budget

0.05

0.1

(b) L2 -squared error (MSE)

Figure 10: GP results on the taxi trajectory dataset Results on trajectory dataset. We apply our PrivFuncSeg algorithm with the simple linear basis given in Example 3. The results for various privacy levels are reported in Fig. 10. We see a significant advantage in our mechanisms over the baseline methods, where our mechanisms offer a 1 to 2 orders of magnitude improvement in the L2 error, over all parameter settings. The improvement reaches up to 3 orders of magnitude in the MSE. To better understand the advantage of our mechanisms, we also plotted the errors in the (partially private) least-squares projection (labeled as “LS Approximation”) obtained from our procedure to find the best set of break points for piecewise privatization (i.e. PrivFuncSeg and ReduceSeg (Algorithms 4 and 5) without the final privatization step). An error in PrivFuncSeg that is close to that in LS Approximation indicates that the mechanism is successful in balancing the error due to approximation and that due to privatization (noise). 26

Next, we present an example trajectory curve privatized by the methods in Fig. 11, to examine how well the mechanisms are able to provide outputs with a general likeness to the original curve. The baseline method here uses k = 10 samples, with smoothing parameter s = 3. We see that 1e6

True LS Approximation PrivFuncSeg PrivFuncSeg (continuous)

4.546 4.544

True Baseline Baseline (smoothed)

4.542 4.540 4.538 1.3622 1.3620 1.3618 1.3616 1.3614 1.3612 1.3622 1.3620 1.3618 1.3616 1.3614 1.3612 1e7 1e7

Figure 11: Example of privatizing a taxi trajectory. ε = 0.01. our mechanism offers a privatized trajectory that retains the overall shape and major directional turns, in both the continuous or piecewise continuous curve. In contrast, the curves provided by the baseline method (smoothed or not), are only able to retain some likeness in terms of shape. The locations of the sampled points and the noise added to the them can cause the baseline methods to miss meaningful segments of the trajectory, as demonstrated here.

Error

102

PrivFuncSeg Degree-1 Basis

PrivFuncSeg (continuous) Baseline Degree-4 Basis Degree-8 Basis

Baseline (smoothed) Degree-16 Basis

101

Error MSE

100

104 103 102 101 100

Privacy Budget

0.05 0.1

0.005 0.01 0.02

0.05 0.1 0.001 0.002

Privacy Budget

0.005 0.01 0.02

0.05 0.1 0.001 0.002

Privacy Budget

0.005 0.01 0.02

0.05 0.1 0.001 0.002

0.005 0.01 0.02

0.001 0.002

10 1

Privacy Budget

Figure 12: GP results on synthetic Gaussian curves

Results on synthetic Gaussian curves. We apply PrivFunSeg to synthetic Gaussian curves with the monomial basis {tm−j }j∈[m] for m ∈ {2, 5, 9, 17}, corresponding to polynomials of degrees upto 1, 4, 8, 16, respectively. The errors at various privacy levels are shown in Fig. 12. Our mechanisms outperformed the baseline methods at all parameter settings, for all selected bases, in both 27

the L2 error and MSE. Note that for small privacy parameters, it is preferable to use a smaller basis, since the privatization error (due to noise) dominates. For a sufficiently large privacy budget, it becomes preferable to use a larger basis to improve the approximation error.

Concluding Remarks

We have provided a framework for function privatization in the local model of geo-privacy, offering algorithms tailored to different types of functions. Our experimental evaluation based on multiple datasets and various parameter settings demonstrates the advantage of our methods, especially for preserving the features and signals in the functions. The privacy guarantee adopted in this work is based on similarity of functions measured by the L2 metric. Depending on the application, in some cases another metric may be preferred, where the ideas developed in this framework might be useful. In particular, our framework readily generalizes to any metric induced by an inner product, as remarked in Section 3. For trajectories, other popular choices for measuring distance include the Hausdrorff distance or Fréchet distance, which are interesting directions for future work.

Acknowledgements This work is supported in part by HKRGC under grants 16205422, 16204223, and 16203924. We thank the anonymous reviewers of CCS ’26 for their helpful feedback and valuable comments.

References [ABCP13]

Miguel E Andrés, Nicolás E Bordenabe, Konstantinos Chatzikokolakis, and Catuscia Palamidessi. Geo-indistinguishability: Differential privacy for location-based systems. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 901–914, 2013.

[AR17]

Francesco Alda and Benjamin Rubinstein. The bernstein mechanism: Function release under differential privacy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.

[AW05]

George B Arfken and Hans J Weber. Mathematical methods for physicists. Elsevier Academic Press, 6 edition, 2005.

[BS16]

Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pages 635– 658. Springer, 2016.

[CABP13]

Konstantinos Chatzikokolakis, Miguel E Andrés, Nicolás Emilio Bordenabe, and Catuscia Palamidessi. Broadening the scope of differential privacy using metrics. In Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13, pages 82–102. Springer, 2013.

[CAC12]

Rui Chen, Gergely Acs, and Claude Castelluccia. Differentially private sequential data publication via variable-length n-grams. In Proceedings of the 2012 ACM conference on Computer and communications security, pages 638–649, 2012.

[CCFS21]

Teddy Cunningham, Graham Cormode, Hakan Ferhatosmanoglu, and Divesh Srivastava. Real-world trajectory sharing with local differential privacy. Proc. VLDB Endow., 14(11):2283–2295, jul 2021.

[DD01]

Frank Deutsch and F Deutsch. Best approximation in inner product spaces, volume 7. Springer, 2001.

[DMNS06]

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265–284. Springer, 2006.

[DR+ 14]

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211– 407, 2014.

[DY23]

Wei Dong and Ke Yi. Universal private estimators. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 195–206, 2023.

[FZ21]

Vitaly Feldman and Tijana Zrnic. Individual privacy accounting via a renyi filter. Advances in Neural Information Processing Systems, 34:28080–28091, 2021.

[GAG+ 00]

Ary L. Goldberger, Luis A. N. Amaral, Leon Glass, Jeffrey M. Hausdorff, Plamen Ch. Ivanov, Roger G. Mark, Joseph E. Mietus, George B. Moody, ChungKang Peng, and H. Eugene Stanley. Physiobank, physiotoolkit, and physionet: Components of a new research resource for complex physiologic signals. Circulation, 101(23):e215–e220, 2000.

[GLT+ 18]

Mehmet Emre Gursoy, Ling Liu, Stacey Truex, Lei Yu, and Wenqi Wei. Utilityaware synthesis of differentially private and attack-resilient location traces. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 196–211, 2018.

[HCM+ 15]

Xi He, Graham Cormode, Ashwin Machanavajjhala, Cecilia M Procopiuc, and Divesh Srivastava. Dpt: differentially private trajectory synthesis using hierarchical reference systems. Proceedings of the VLDB Endowment, 8(11):1154–1165, 2015.

[HRW13]

Rob Hall, Alessandro Rinaldo, and Larry Wasserman. Differential privacy for functions and functional data. The Journal of Machine Learning Research, 14(1):703– 727, 2013.

[LM00]

Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 1302–1338, 2000.

[LWX21]

Fang Liu, Dong Wang, and Zhengquan Xu. Privacy-preserving travel time prediction with uncertainty using gps trace data. IEEE Transactions on Mobile Computing, 22(1):417–428, 2021. 29

[LY23]

Yuting Liang and Ke Yi. Concentrated geo-privacy. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 1934–1948, 2023.

[LY24]

Yuting Liang and Ke Yi. Smooth sensitivity for geo-privacy. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 333–347, 2024.

[LY26]

Yuting Liang and Ke Yi. arXiv:2601.10866, 2026.

Adaptive privacy budgeting.

arXiv preprint

[MPGBPA+ 23] Àlex Miranda-Pascual, Patricia Guerra-Balboa, Javier Parra-Arnau, Jordi Forné, and Thorsten Strufe. Sok: Differentially private publication of trajectory data. Proceedings on Privacy Enhancing Technologies, 2023. [MT07]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007.

[NP00]

Pierpaolo Natalini and Biagio Palumbo. Inequalities for the incomplete gamma function. Math. Inequal. Appl, 3(1):69–77, 2000.

[OWN97]

Alan V Oppenheim, Alan S Willsky, and Syed Hamid Nawab. Signals & systems. Pearson Educación, 1997.

[PSDG22]

Michal Piorkowski, Natasa Sarafijanovic-Djukic, and Matthias Grossglauser. Crawdad epfl/mobility, 2022.

[Rén61]

Alfréd Rényi. On measures of entropy and information. In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, volume 4, pages 547–562. University of California Press, 1961.

[Sán06]

József Sándor. On certain inequalities for the gamma function. RGMIA Res. Rep. Coll, 9(1), 2006.

[SM65]

E Webb Stacy and G Arthur Mihram. Parameter estimation for a generalized gamma distribution. Technometrics, 7(3):349–358, 1965.

[SS11]

Elias M Stein and Rami Shakarchi. Fourier analysis: an introduction, volume 1. Princeton University Press, 2011.

[Sta62]

Edney W Stacy. A generalization of the gamma distribution. The Annals of mathematical statistics, pages 1187–1192, 1962.

[TUV12]

Justin Thaler, Jonathan Ullman, and Salil Vadhan. Faster algorithms for privately releasing marginals. In International Colloquium on Automata, Languages, and Programming, pages 810–821. Springer, 2012.

[VEH14]

Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):3797–3820, 2014. 30

[WJF+ 16]

Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, 17(51):1–42, 2016.

[WNM23]

Tal Wagner, Yonatan Naamad, and Nina Mishra. Fast private kernel density estimation via locality sensitive quantization. In International Conference on Machine Learning, pages 35339–35367. PMLR, 2023.

[WSB+ 20]

Patrick Wagner, Nils Strodthoff, Ralf-Dieter Bousseljot, Dieter Kreiseler, Fatima I. Lunze, Wojciech Samek, and Tobias Schaeffter. Ptb-xl, a large publicly available electrocardiography dataset. Scientific Data, 7(1):154, May 2020.

[WSB+ 22]

Patrick Wagner, Nils Strodthoff, Ralf-Dieter Bousseljot, Wojciech Samek, and Tobias Schaeffter. PTB-XL, a large publicly available electrocardiography dataset, Nov 2022.

[YTL22]

Mengmeng Yang, Ivan Tjuawinata, and Kwok-Yan Lam. K-means clustering with local dχ -privacy for privacy-preserving data analysis. IEEE Transactions on Information Forensics and Security, 17:2524–2537, 2022.

Ethical Considerations and Open Science

In this paper, we considered privatizing functions under the local model. Compared to the central model, the local model allows stronger privacy protection; i.e. it benefits individual data owners. We have performed experimental evaluation of our methods using synthetic data, and public available datasets: taxi trajectories [PSDG22] and ECG records [WSB+ 22, WSB+ 20, GAG+ 00]. The public datasets had been previously sanitized. Our approach considers an input function to be privatized as a whole, and over the entire domain of the input function. This has the benefit that it allows a general likeness of the input function to be retained, thus allowing further meaningful analytics on the features/signals contained in the function. I.e. researchers can benefit from such improved utility. The code to all experiments can be found at: https://github.com/hkustDB/FuncPrivGP, where we also provide detailed information on the datasets, implementations and running the experiments.

Useful facts and inequalities

Fact B.1. Privatizing point set via Lemma 2.2 is not GP w.r.t dist2 . Proof. We give an example to show that privatizing and releasing a fixed set of points does not suffice to guarantee GP w.r.t. dist2 . Consider again the example in Section 3.1, where we have two linear functions fa and fa′ on [0, 1], with a = (2, 0.5) and a′ = (0.5, 2). Suppose we privatize the points at t1 √ = 0, t2 = 0.5, t3 = 1, with ε = 1, which for fa corresponds to a pdf at z = (z1 , z2 , z3 ) that is − (z1 −fa (t1 ))2 +(z2 −fa (t2 ))2 +(z3 −fa (3))2 ∝e . Then the ratio of the respective pdf’s at z = (0.5, 1.0, 2.0) is √ 2 2 2 √ √ √ e− (z1 −fa (t1 )) +(z2 −fa (t2 )) +(z3 −fa (3)) − 0.5+ 1.52 +1.252 +0.52 1.5/ 3 √ = e > e = edist2 (fa ,fa′ ) , − (z1 −fa (t1 ))2 +(z2 −fa (t2 ))2 +(z3 −fa (3))2 e 31

thus violating the GP requirement. Theorem B.2 (Hilbert projection theorem). Let C ⊆ H be any non-empty closed convex subset of a Hilbert space H whose inner product induces norm ∥ · ∥H . Then for every y ∈ H, there exists a unique c(y) ∈ C such that ∥y − c(y)∥H = inf z∈C ∥y − z∥H . Moreover, if C is also a subspace of H, then c(y) ∈ C is such that y − c(y) is orthogonal to C. t Fact B.3. Fix any x, t > 0. Then xt ≤ ex/e . Proof. The function z 7→ ez−1 − z is convex and has minimum value 0, i.e. ez−1 − z ≥ 0 ⇐⇒ ez ≥ x ez =⇒ z ≥ 1 + ln z for z > 0. Choose z = et > 0, then x x x ln = 1 + ln ≤ t et et x x t ln ≤ t e x t ≤ ex/e . t

Lemma B.4 ([Sán06]). For any x > 0, √

Γ(x + 1) x≤ ≤ Γ(x + 12 )

1 x+ . 2

c Lemma B.5 ([NP00]). For any c, t > 1 and x where x > c−1 (x − 1),

Γ(t, x) < cxt−1 e−x . Lemma B.6 (Generalized Gamma Distribution [Sta62, SM65]). Let G(λ, d, p) denote the generalp p ized gamma distribution with parameters λ, d, p > 0, whose pdf is given by g(r) = λd Γ(d/p) rd−1 e−(r/λ) . Then for G ∼ G(λ, d, p), Pr[G ≤ r] =

Γ(d/p + k/p) γ(d/p, (r/λ)p ) and E[Gk ] = λk , k ≥ 1. Γ(d/p) Γ(d/p)

Let Z = [z1 , · · · , zm ] be a random vector. If Z is drawn from √ a spherical Laplace distribution, then ∥Z∥ ∼ G(1, m, 1); if Z ∼ N (0, Im×m ), then ∥Z∥ ∼ G( 2, m, 2) (see [LY23], Appendix A). Thus, using Lemmas B.4 and B.6 above, we have: Corollary B.1. Let Z = [z1 , · · · , zm ] be a random vector. Then Γ(m+2) 2 1. E[∥Z∥] = Γ(m+1) Γ(m) = m and E[∥Z∥ ] = Γ(m) = m(m + 1), if Z ∼ SLap(m);

2. E[∥Z∥] =

√ Γ(m/2+1/2) √ √ 2 Γ(m/2) ∈ m − 1, m and E[∥Z∥2 ] = 2 Γ(m/2+1) Γ(m/2) = m, if Z ∼ N (0, Im×m ).

We can derive high probability bounds for the magnitude ∥Z∥: e Lemma B.7. Fix 1 < m ∈ N, let R ∼ G(1, m, 1). Then for any 1 > β > 0, R ≤ e−1 (m + ln(1/β)) with probability at least 1 − β.

e (m + ln(1/β)). We will show Pr[R ≤ r] ≥ 1 − β. We have Γ(m) = γ(m, r) + Proof. Let r := e−1 R∞ Γ(m, r), where Γ(m, r) = r tm−1 e−t dt is the upper incomplete gamma function. By Lemma B.6, Γ(m)−Γ(m,r) Γ(m,r) Pr[R ≤ r] = γ(m,r) = 1 − Γ(m,r) Γ(m) = Γ(m) Γ(m) , so it suffices to show Γ(m) ≤ β. To this end, we c use the inequality from Lemma B.5: Γ(m, r) < crm−1 e−r for c > 1, and r > c−1 (m − 1). Choose c e c = e, then r = e−1 (m + ln(1/β)) > c−1 (m − 1), so

Γ(m, r) erm−1 e−r erm−1 e−r < = Γ(m) Γ(m) (m − 1)! erm−1 e−r ≤p 1 2π(m − 1)(m − 1)m−1 e−(m−1) e 12(m−1)+1 m−1 r 1 · ≤p e−(r−1)+(m−1) m − 1 2π(m − 1) | {z }

(Stirling’s)

≤er/e , Fact B.3.

e e−r(1− e )+m = ≤p 2π(m − 1)

e − e−1 (m+ln β1 ) e−1 +m e

p 2π(m − 1)

−(m+ln 1 )−m

β e β = p =p ≤ β. 2π(m − 1) 2π(m − 1)

Lemma B.8 ([LM00]). Given Z ∼ N (0, Im×m ), then with probability at least 1 − β, q p ∥Z∥ ≤ m + 2 m ln(1/β) + 2 ln(1/β). Fact B.9. Fix k > 0. Let sinck : t 7→ sin(kπt) kπt . Then R∞ 1. −∞ sinck (t − a) · sinck (t − b)dt = sinck (a − b)/k R∞ 2. −∞ sinck (t − a)2 dt = 1/k 

 S1,1 (t) · · · S1,m (t)   .. Fact B.10. For u = [u1 , · · · , um ]T , v = [v1 , · · · , vm ]T ∈ Rm , and S(t) =  ...  . Sm,1 (t) · · · Sm,m (t) where Sj,l (t) = Sl,j (t) ∈ L2 (I) for all j, l ∈ [m], we have R   R   S1,1 (t)dt · · · S1,m (t)dt v1 v1 Z t∈I t∈I   ..    ..  . . . . u1 · · · um S(t)  .  dt = u1 · · · um   . . . . R R I vm vm t∈I Sm,1 (t)dt · · · t∈I Sm,m (t)dt

Privatization under CGP

In this section, we provide the CGP variants of the algorithms provided above. For the steps that involve SVT, which is a GP mechanism, we use the following relationship to convert the privacy parameters from GP to CGP. 2

Lemma C.1 (GP conversion to CGP [LY23]). Any ε-GP mechanism is also ε2 -CGP. 33

C.1

Function Privatization

The CGP variant of Project-and-Privatize is provided in Algorithm 6; its expected squared error p is given by Lemma 3.9, where the noise vector for CGP has magnitude proportional to dim(Uf ). The latter is reflected in CGP variant of PrivFuncSelect (Algorithm 7), in the step where we try to balance the errors due to approximation and noise addition (line 5). We use Lemma C.1 to convert the GP privacy parameter used in the SVT call (line 1) to a CGP privacy parameter, then similar to the GP case, the privacy of Algorithm 7 follows from basic composition. Algorithm 6 Project-and-Privatize-CGP Input: q : I → Rn ; finite-dimensional function space Uf ; ρ > 0 Output: privatized q̃ 1: compute Σ from Uf 2: a ← coefficients of PUf (q) 3: ã ← a + √12ρ Σ1/2 Z, Z ∼ N (0, Idim(Uf ) ) 4: return

fã

Algorithm 7 PrivFuncSelectCGP Input: q : I → Rn ; {ϕj }j∈J ; β > 0; ρ > 0 Output: privatized q̃ √

ρ 2

1: k0 ← SVT(q, (ε0 /3, 2ε0 /3), − ε1 , 1, g1 , g2 , · · · ), where ε0 = √ , gj (·) := − dist2 (P 0

(k0 )

2: q̃0 ← Project-and-Privatize-CGP(q, Uf

(·), ·)

, ρ/4)

(k0 ) 3: c̃ ← coefficients of q̃0 in Uf 4: s(r) ← rth largest magnitude in c̃, for r ∈ [k0 ] ε

(j)

2ε

5: k1 ← SVT(q, ( 30 , 30 ), 0, 1, g1′ , g2′ , · · · ), Nr := {j : ∥c̃j ∥ ≥ s(r) }, gr′ (·) :=

√

n|Nr | − dist2 (fb(r) , ·), ε0

(r)

bj := c̃j 1{j ∈ Nr } 6: Uf ← span({ϕj : j ∈ Nk1 }) 7: fã ← Project-and-Privatize-CGP(q, Uf , ρ/4) 8: return fã

C.2

Curve Privatization

The CGP variant of PrivFuncSeg for curve privatization is provided in Algorithm 8. The privacy guarantee follows similarly to the case of GP. The steps that use the magnitude related to noise p addition reflect the (·) relationship with that of GP: in line 1 of Algorithm 8, and line 9 of Algorithm 9.

Algorithm 8 PrivFuncSegCGP Input: q : [0, T ] → Rn ; I = [0, T ]; {ϕj }j∈[m] ; β > 0; ρ > 0 Output: privatized q̃ √

1: k̄

√

j ρ ← SVT(q, (ε0 /3, 2ε0 /3), 0, 1, g0 , g1 , g2 , · · · ), where ε0 = √2 , τj = √2 mn , gj (q) := τj −

ρ/2

dist2 (PU (j) (q), q), PU (j) computes best approximation using 2j sub-intervals f

2: B ← 3ρ/4 3: S ← {jT /2k̄ : j = 0, 1, 2, · · · , 2k̄ } 4: k ← min(k̄ − 2, 4) 5: if k1 ≥ 1 then

for i = 1, ..., 4 do ρ Ŝi ← ReduceSegCGP(q, (i − 1)T /4, iT /4, k1 , 1, Si , β, B, 16 ), Si := S ∩ [(i − 1)T /4, iT /4] 8: end for 9: end if 10: Ŝ ← ∪i Ŝi = {0 = T0 , T1 , · · · , TN = T }; N ← |Ŝ| − 1 11: Uf ← span({ϕj · 1[Ts−1 ,Ts ) }s∈[N ],j∈[m] ) 12: fã ← Project-and-Privatize-CGP(q, Uf , B) 13: return fã 6: 7:

Algorithm 9 ReduceSegCGP Input: q : [0, T ] → Rn ; ts < te ; k1 ; l; set S containing breakpoints to be checked; β > 0; B ≥ ρ′ > 0 Output: Ŝ after reducing the number of sub-intervals 1: if l > k1 then 2:

return S

3: end if 4: k ← log2 (|S| − 1);

s 5: S ′ ← {2r te2−t + ts : r = 0, · · · , 2k−1 )} k

{try to reduce number of sub-intervals by half} 6: f[ts ,te ] ← best approx. of q on [ts , te ] using break points in S ′ √

7: err ← dist2 (f[ts ,te ] , q · 1[ts ,te ] ) + √ 2 ′ Z, Z ∼ N (0, 1) 2ρ

ρ′ √ p √ √ l k−1 mn 2−1 2√ 9: if err + √ 2 ′ 2k1 ln(2) + 2 ln(1/β) ≤ √ · then 2ρ 2 2B ′ ′ ′ ′ 10: SL ← S ∩ [ts , (ts + te )/2], SR ← S ∩ [(ts + te )/2, te ] ′ 11: ŜL ← ReduceSegCGP(q, ts , (ts + te )/2, k1 , l + 1, SL′ , β, B, ρ2 ) ′ , β, B, ρ′ ) 12: ŜR ← ReduceSegCGP(q, (ts + te )/2, te , k1 , l + 1, SR 2

8: B ← B − 2l

Ŝ ← ŜL ∪ ŜR 14: else 15: Ŝ ← S 16: end if 17: return Ŝ

13:

η(β;dim(U ),2)

√ f Let ErrBound(fã , ρ, β; q, 2)) := dist2 (fa , q) + for fã ∈ Uf obtained from privatizing 2ρ fa as in Theorem 3.3. Similar to the GP case, ErrBound(fã , ρ, β; q, 2)) bounds dist2 (fã , q) with probability 1 − β. We also have a utility guarantee similar to the GP case for Algorithm 9.

Lemma C.2. Let Ŝ be the set of breakpoints resulting from running ReduceSegCGP(q, ts , te , k1 , k, 1, S, β2 , B, ρ′ ). Let q̃Ŝ be obtained from the ρ/2-CGP privatization of the best approximation of q on the interval [ts , te ] using breakpoints in Ŝ, let q̃S be defined similarly for the set S. Then with probability 1 − 32 β, p √ dist2 (q̃Ŝ , q) ≤ ErrBound(q̃S ; q, ρ/2, β, 1)) + ( 2 − 1) ln(1/β)/ρ.

C.3

Experiments under CGP

In this section, we provide evaluations for the methods in the CGP model, on the same set of experiments as those in Section 5. We observe similar improvements in our CGP mechanisms over the baseline methods in all the experiments, for all parameter settings, as those shown for the GP mechanisms in Section 5. Project-and-Privatize Baseline Baseline (smoothed)

Project-and-Privatize Baseline Baseline (smoothed)

101

100

100 10 1

10 1

10 2 8e-05

0.00032

0.002

Privacy Budget

0.008

0.032

8e-05

(a) L2 error

0.00032

0.002

Privacy Budget

0.008

0.032

(b) L2 -squared error (MSE)

Figure 13: CGP results on ECG dataset 104

PrivFuncSelect Baseline Baseline (smoothed)

103

101 102 101 100

100 10 1 1e-07 4e-07

2.5e-06 1e-05 4e-05

Privacy Budget

0.00025 0.001

1e-07 4e-07

(a) L2 error

2.5e-06 1e-05 4e-05

Privacy Budget

0.00025 0.001

(b) L2 -squared error (MSE)

Figure 14: GP results on synthetic Gaussian curves

102

107

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

101

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

105 103

100 101 10 1

10 1

10 2

10 3 1.25e-08

5e-08

3.125e-07 1.25e-06

5e-06

Privacy Budget

3.125e-05 0.000125

1.25e-08

(a) L2 error

5e-08

3.125e-07 1.25e-06

5e-06

Privacy Budget

3.125e-05 0.000125

(b) L2 -squared error (MSE)

Figure 15: CGP results on the taxi trajectory dataset

102

PrivFuncSeg Degree-1 Basis

PrivFuncSeg (continuous) Baseline Degree-4 Basis Degree-8 Basis

Baseline (smoothed) Degree-16 Basis

Error

101 100

10 1 104

Error MSE

103 102 101 100

Privacy Budget

Figure 16: GP results on synthetic Gaussian curves

0.00025 0.001

Privacy Budget

2.5e-06 1e-05 4e-05

0.00025 0.001 1e-07 4e-07

Privacy Budget

2.5e-06 1e-05 4e-05

0.00025 0.001 1e-07 4e-07

Privacy Budget

2.5e-06 1e-05 4e-05

0.00025 0.001 1e-07 4e-07

2.5e-06 1e-05 4e-05

1e-07 4e-07

10 1

Deferred Proofs

D.1

Utility of SVT

The analysis on SVT below is mostly the same as that in [DY23], and re-produced here for completeness. Proof of Lemma 2.4. We will use the one-sided and two-sided Laplace tail bounds: For Z ∼ Lap(b), Pr[Z ≤ b ln(1/β)] ≥ 1 − β/2 and Pr[|Z| ≤ b ln(1/β)] ≥ 1 − β. Let W , Zj ∼ Lap(3K/ε) denote the Laplace random variables in the SVT call. The analysis requires bounding |W | and Zj for 1 ≤ j ≤ t. Notice that SVT halts at t if Zt + gt (x) ≥ T + W , i.e. Zt − W ≥ T − gt (x). We have gt (x) − T ≥ 6K ln(2/β)/ε by assumption, and 3K Pr |W | ≤ ln(2/β) ≥ 1 − β/2 (5) ε 3K 3K ln(2/β) = Pr −Zt ≤ ln(2/β) ≥ 1 − β/4 (6) Pr Zt ≥ − ε ε 6K ln(2/β) ≥ 1 − 3β/4. Pr [Zt − W ≥ −(gt (x) − T )] ≥ Pr Zt − |W | ≥ − ε Thus, SVT halts at or before t with probability1 − 3β/4 (by a union bound over (5), (6)). We 3K assume this holds in the remaining analysis. Pr Zj > ε ln(2t/β) ≤ β/(4t) for each 1 ≤ j ≤ t. Then 3K Zk̄ ≤ max Zj ≤ ln(2t/β) (7) 1≤j≤t ε where the last inequality holds with probability at least 1 − β/4. Thus, with probability at least 1 − β (by union bound over (5), (6), (7)), gk̄ (x) ≥ T + W − Zk̄ ≥ T − |W | − Zk̄ ≥ T −

D.2

3K 3K ln(2/β) − ln(2t/β). ε ε

Lipschitzness of finite-dimensional function space projection

Proof of Lemma 3.7. First, the space L2 (I) of square-integrable functions is a Hilbert space whose qR 2 2 inner product induces the L2 metric dist2 (f, g) := I (f (t) − g(t)) dt. Let U ⊆ L (I) be any subset. Next, the span of m linearly independent functions in L2 (I) forms a subspace; let Uf be any such subspace. Then for any pair q, q ′ ∈ U , by the Hilbert projection theorem3 there are fa(q) , fa(q′ ) ∈ Uf such that fa(q) = arg minz∈Uf dist2 (q, z) and fa(q′ ) = arg minz∈Uf dist2 (q ′ , z); moreover, q − fa(q) , q ′ − fa(q′ ) are orthogonal to Uf . Denote cq,q′ := fa(q) − fa(q′ ) , c⊥ q,q ′ := (q − fa(q) ) − ′ ⊥ ′ ′ (q − fa(q ) ), then cq,q ∈ Uf and cq,q′ is orthogonal to Uf . dist2 (q, q ′ )2 = dist2 fa(q) + q − fa(q) , fa(q′ ) + q ′ − fa(q′ ) 3

Technically speaking, appealing to the Hilbert projection theorem is not necessary, since the constructions in Appendix E provide the projections we need.

fa(q) (t) + q(t) − fa(q) (t) − (fa(q′ ) (t) + q ′ (t) − fa(q′ ) (t))

2 ⊥ (cq,q′ (t)2 + c⊥ q,q ′ (t) + 2cq,q ′ (t)cq,q ′ (t))dt ZI Z Z 2 ⊥ 2 ′ = cq,q (t) dt + cq,q′ (t) dt +2 cq,q′ (t)c⊥ q,q ′ (t))dt I | I {z } |I {z }

≥0

Z ≥

cq,q′ (t)2 dt = dist2 (fa(q) , fa(q′ ) )2 .

D.3

Utility of Project-and-Privatize

Lemma D.1 (Lemma 3.9). Let Uf be the subspace given by the span of {ϕj (·)}j∈[m] . For q ∈ U , let fa ∈ Uf be a projection of q in Uf . For ã := a + 1b Σ1/2 Z where Z is a random vector with mean zero, we have 1 E[dist2 (q, fã )2 ] = dist2 (q, fa )2 + 2 E[∥Z∥2 ]. b Proof of Lemma 3.9. We need to discuss all three cases, though the derivations are similar. 1. Real-valued coefficients and basis functions.   2  2 T ϕ1 (t) Z Z X 1 1  ..   dist2 (q, fã )2 = q(t) − ãj ϕj (t) dt = q(t) − a + Σ 2 Z  .  dt b I I j∈[m] ϕm (t)  2    ϕ1 (t) ϕ1 (t) Z 1     1 z1 · · · zm Σ 2  ...  dt = q(t) − a1 · · · am  ...  − b I ϕm (t) ϕm (t)     z1 Z Z X X 1 .  2 2 aj ϕj (t)) dt − = (q(t) − q(t) − aj ϕj (t) ϕ1 (t) · · · ϕm (t) Σ 2  ..  dt b I I j∈[m] j∈[m] {z } zm | h i =: v1 (t) · · · vm (t)     ϕ1 (t) z1 Z 1  .  1 .  1 z1 · · · zm Σ 2  ..  ϕ1 (t) · · · ϕm (t) Σ 2  ..  dt + 2 {z } I b | ϕm (t) zm ∈Rm | {z } ∈Rm



2 R v1 (t)dt · · · = dist2 (q, fa ) − b I 2



z1  .  . I vm (t)dt  .  zm

 +

1 1 z 1 · · · zm Σ 2  2 b R

2 I ϕ1 (t) dt

···

I ϕ1 ϕm (t)dt

 z1  12  ..  Σ  .  

.. .. . . R ϕ (t)ϕ (t)dt · · · ϕ (t)ϕ m 1 m m (t)dt | I {z I }



Σ−1 , by Fact B.10



= dist2 (q, fa )2 −

2 R v1 (t)dt · · · b I

E[dist2 (q, fã )2 ] = dist2 (q, fa )2 −

2 R v1 (t)dt · · · b I

   z1 z1  .   .  R 1 . . I vm (t)dt  .  + b2 z1 · · · zm  .  , zm zm   z1  .  1 R 2 . v (t)dt + E E ∥Z∥     m . I b2 zm | {z } 0

1 = dist2 (q, fa )2 + 2 E[∥Z∥2 ]. b 2. Real-valued coefficients, vector-valued basis. Here ϕj = [ϕj,1 , · · · , ϕj,n ]T for j ∈ [m]. Let   ϕ1,1 (t) · · · ϕm,1 (t)  .. .. . Note that f (t) = P T Φ(t) :=  . a .  j∈[m] aj [ϕj,1 (t), · · · , ϕj,n (t)] = Φ(t)a. ϕ1,n (t) · · ·

ϕm,n (t)    2 q1 (t) ϕ1 (t)  ..  X   ãj  ...  dt  . − 

dist2 (q, fã )2 =

Z I

j∈[m] qn (t) ϕm (t)     2 q1 (t) ϕ1,1 (t) · · · ϕm,1 (t) Z 1 1  ..   .. ..  (a + Σ 2 Z) dt =  . − . .  b I qn (t) ϕ1,n (t) · · · ϕm,n (t)   2 q1 (t) Z Z Z 2 1 1 1 1  ..  2 Z dt − 2 (q(t) − Φ(t)a)T Φ(t)Σ 2 Zdt Φ(t)Σ = − Φ(t)a dt +  .  2 {z } b I b I| I qn (t) =:[v1 (t),...,vm (t)] Z R 1 1 1 2 R 2 v1 (t)dt · · · vm (t)dt [z1 , . . . , zm ]T = dist2 (q, fa ) + 2 Z T Σ 2 Φ(t)T Φ(t)Σ 2 Zdt − I I b I b P  P  2 ··· Z r∈[n] ϕ1,r (t) r∈[n] ϕ1,r (t)ϕm,r (t) 1  12 .. .. T 12  = dist2 (q, fa )2 + 2 Z Σ   |Σ{zZ} dt . · · · . b I | {zm } P P 2 ∈R ∈Rm r∈[n] ϕm,r (t)ϕ1,r (t) · · · r∈[n] ϕm,r (t) R T   z1 I v1 (t)dt 2   . .  .. −    ..  b R zm I vm (t)dt

= dist2 (q, fa )2 +

1 T 1 Z Σ2  b2 R P I

| R

2 r∈[n] ϕ1,r (t) dt

R P



···

R P

.. .

··· ϕ (t)ϕ (t)dt · ·· 1,r r∈[n] m,r {z

r∈[n] ϕ1,r (t)ϕm,r (t)dt

.. . R P 2 r∈[n] ϕm,r (t) dt I

T 

 z1  .  R . I vm (t)dt  .  , 

= dist2 (q, fa )2 +

2 R 1 v1 (t)dt · · · ∥Z∥ − 2 b b I

1 2 R v1 (t)dt · · · E[dist2 (q, fã )2 ] = dist2 (q, fa )2 + 2 E[∥Z∥] − b b I

zm h I vm (t)dt E z1 · · · {z |

T i

}

3. Vector-valued coefficients, real-valued basis. Here aj = [aj,1 , · · · , aj,n ] for j ∈ [n]. Write a:r = [a1,r , · · · , am,r ]T and z:,r = [z1,r , · · · , zm,r ]T for r ∈ [n]. We have the coefficient vector a = [a:1 , · · · , a:n ]T , noise vector Z = [z:1 , · · · , z:n ]T , and privatized coefficient vector ã = a + 1/2 1 1/2 Z, where Σ1/2 is a diagonal block matrix with Σ0 repeated in the diagonal. Let Φ(t) := bΣ [ϕ1 (t), · · · , ϕm (t)]T .  P  2 q1 (t) j∈[m] ãj,1 ϕj (t)  ..    ..  . −  dt . P qn (t) j∈[m] ãj,n ϕj (t)  2    1/2 [ϕ1 (t), · · · , ϕm (t)] · (a:1 + 1b Σ0 z:1 ) q1 (t)   ..   ..  . −  dt .  Z dist2 (q, fã ) = I

Z = I

1/2 qn (t) [ϕ1 (t), · · · , ϕm (t)] · (a:n + 1b Σ0 z:n )      2  2 1/2 Φ(t)T Σ0 z:1 q1 (t) Φ(t)T a:1 Z Z 1   ..     .. .. =  . −   dt  dt + 2 . . b I I T 1/2 qn (t) Φ(t) a:n Φ(t)T Σ0 z:n   1/2 Φ(t)T · Σ0 z:1 Z 2   .. [q1 (t), · · · , qm (t)]  −  . b I 1/2 T Φ(t) · Σ0 z:n   1/2 Φ(t)T Σ0 z:1 Z h i 1   1/2 .. T 1/2 z T Σ Φ(t), · · · , z:n Σ0 Φ(t)  = dist2 (q, fa )2 + 2  dt . b I :1 0 1/2 Φ(t)T Σ0 z:n

 12 Σ Z }

Σ−1 , by Fact B.10

 z1 2   ..  .. −    .  . b R zm I vm (t)dt I v1 (t)dt



−

2 b

Z I

 Φ(t)T  [q1 (t), · · · , qm (t)] 

 ..

. Φ(t)T

=:[v1,1 (t),··· ,vm,1 (t),··· ,vm,n (t)]

= dist2 (q, fa )2 +

1 X b2

r∈[n] I

  Σ Zdt }

1/2 T 1/2 z:r Σ0 Φ(t)Φ(t)T Σ0 z:r dt

R 2 R v1,1 (t)dt · · · vm,n (t) [z1,1 , · · · , zm,n ]T I I b i h R 1 2 R T v (t)dt · · · v (t) E[dist2 (q, fã ) = dist2 (q, fa )2 + 2 E[∥Z∥2 ] − . E [z , · · · , z ] 1,1 m,n 1,1 m,n I b b I {z } | −

D.4

Utility of ReduceSeg (Algorithm 5)

Proof of Lemma 4.2. Let t̂s , t̂e denote the end points of the running interval in ReduceSeg. There k1 are at most 2k1 calls to ReduceSeg, where at most 2 Lap(1) random variables are drawn, which k are simultaneously lower bounded by − ln 2 1 /β with probability at least 1 − β/2. Assume this holds in the remaining analysis. In each call, we have dist2 (f[t̂s ,t̂e ] , q · 1[t̂s ,t̂e ] ) = err −

2l 2l k1 Z ≤ err + ln 2 /β , ε′ ε′

(8)

where f[t̂s ,t̂e ] is computed using S ′ (i.e. half of the sub-intervals). Thus, if line 9 is true, then the k−1

emn emn approximation error dist2 (f[t̂s ,t̂e ] , q · 1[t̂s ,te ] ) is dominated by 22(e−1)B = |[t̂s , t̂e ) ∩ S ′ | 2(e−1)B after removing half of the sub-intervals. Assume the number of breakpoints is reduced at least once (i.e. at level l = 1); otherwise Ŝ = S and there would be nothing to prove. Starting from C = ∅, add the pair (t̂s , t̂e ) to C whenever line 9 is false. Let par(t̂s , t̂e ) denote the sub-interval at its parent call, so [t̂s , t̂e ] ⊂ par(t̂s , t̂e ); there were twice as many sub-intervals in the call on par(t̂s , t̂e ), during which line 9 was true. We have

dist2 (f[t̂s ,t̂e ] , q · 1[t̂s ,t̂e ] ) ≤ dist2 (fpar(t̂s ,t̂e ) , q · 1par(t̂s ,t̂e ) ) emn emn = |[t̂s , t̂e ) ∩ Ŝ| , ≤ 2|[t̂s , t̂e ) ∩ Ŝ| 2(e − 1)B (e − 1)B since the non-private approximation on par(t̂s , t̂e ) has error bounded by the number of its subemn intervals times 2(e−1)B , and B ≥ ε/2 is non-increasing. When the recursive calls terminate, we have that the original interval is equal to the union of sub-intervals defined by the pairs in C. Let PŜ (q) denote the non-private best approximation of q using intervals in Ŝ. We have dist2 (PŜ (q), q) ≤

dist2 (PŜ (q · 1[t̂s ,t̂e ] ), q · 1[t̂s ,t̂e ] )

(t̂s ,t̂e )∈C

≤

X (t̂s ,t̂e )∈C

|[t̂s , t̂e ) ∩ Ŝ|emn (|Ŝ| − 1)emn = , (e − 1)ε/2 (e − 1)ε/2 42

dist2 (q̃Ŝ , q) ≤ dist2 (PŜ (q), q) + dist2 (q̃Ŝ , PŜ (q)) (|Ŝ| − 1)emn η(β; (|Ŝ| − 1)m, 1) + (w.p. 1 − β) (e − 1)ε/2 ε/2 (|Ŝ| − 1)emn e ≤ + |Ŝ| − 1)mn + ln(1/β) (e − 1)ε/2 (e − 1)ε/2 e e = (2|Ŝ| − 2)mn + ln(1/β) (e − 1)ε/2 (e − 1)ε/2 η(β; (|S| − 1)mn, 1) ≤ (since 2|Ŝ| ≤ |S|) ε/2 ≤ ErrBound(q̃S ; q, ε/2, β, 1)).

≤

(9)

Combining (8) and (9) above, we have with probability 1− 32 β, dist2 (q̃Ŝ , q) ≤ ErrBound(q̃S ; q, ε/2, β, 1)).

D.5

Utility of ReduceSegCGP (Algorithm 9)

Proof of Lemma C.2. The proof proceeds similarly to that for Lemma 4.2. p The N (0, 1) random variables in the (at most) 2k1 calls are simultaneously lower bounded by − 2 ln(2k1 /β) with probability at least 1 − β/2. Assume this holds. In each call, we have √ √ q 2l 2l dist2 (f[t̂s ,t̂e ] , q · 1[t̂s ,t̂e ] ) = err − √ ′ Z ≤ err + √ ′ 2 ln(2k1 /β), 2ρ 2ρ where f[t̂s ,t̂e ] is computed using S ′ . If line 9 is true, then the approximation error dist2 (f[t̂s ,t̂e ] , q · q √ √ √ ( 2−1) 2k−1 mn √ √ √ √ = |[t̂s , t̂e ) ∩ S ′ |mn after removing half of the sub1[t̂s ,te ] ) is dominated by ( 2−1) 2 2B 2 2B intervals . Assume the number of sub-intervals is reduced at least once. Starting from C = ∅, add the pair (t̂s , t̂e ) to C whenever line 9 is false. Let par(t̂s , t̂e ) denote the sub-interval at its parent call. Note that we have √ q ( 2 − 1) dist2 (f[t̂s ,t̂e ] , q · 1[t̂s ,t̂e ] ) ≤ dist2 (fpar(t̂s ,t̂e ) , q · 1par(t̂s ,t̂e ) ) ≤ √ √ 2|[t̂s , t̂e ) ∩ Ŝ|mn, 2 2B since the non-private approximation on √par(t̂s , t̂e )) has error bounded by the square root of the √

2−1) mn √ number of its sub-intervals times ( √ , and B ≥ ρ/2 is non-increasing. When the recursive 2 2B calls terminate, we have that the original interval is equal to the union of sub-intervals defined by the pairs in C. Let PŜ (q) denote the non-private best approximation of q using intervals in Ŝ. Then

dist2 (PŜ (q), q)2 =

X (t̂s ,t̂e )∈C

≤

X (t̂s ,t̂e )∈C

dist2 (PŜ (q · 1[t̂s ,t̂e ] ), q · 1[t̂s ,t̂e ] )2 √ √ ( 2 − 1)2 ( 2 − 1)2 (2|[t̂s , t̂e ) ∩ Ŝ|mn) = (|Ŝ| − 1)mn, 2ρ ρ

dist2 (q̃Ŝ , q) ≤ dist2 (PŜ (q), q) + dist2 (q̃Ŝ , PŜ (q))

√ q ( 2 − 1) η(β; (|Ŝ| − 1)mn, 2) ≤ (|Ŝ| − 1)mn + (with prob. 1 − β) √ √ ρ ρ r √ q q ( 2 − 1) 1 = (|Ŝ| − 1)mn + √ (|Ŝ| − 1)mn + 2 (|Ŝ| − 1)mn ln(1/β) + 2 ln(1/β) √ ρ ρ| {z } r 2 √ √ ≤

(|Ŝ|−1)mn+

2 ln(1/β)

q q p √ 1 ( 2 − 1) (|Ŝ| − 1)mn + (|Ŝ| − 1)mn + 2 ln(1/β) ≤√ ρ q p p √ 1 √ =√ 2 (|Ŝ| − 1)mn + ln(1/β) + ( 2 − 1) ln(1/β) ρ r ! q p √ 1 =√ 2(|Ŝ| − 1)mn + 2 2(|Ŝ| − 1)mn ln(1/β) + ln(1/β) + ( 2 − 1) ln(1/β) ρ q p p √ 1 (|S| − 1)mn + 2 (|S| − 1)mn ln(1/β) + ln(1/β) + ( 2 − 1) ln(1/β) ≤√ ρ (since 2|Ŝ| ≤ |S|)

p √ η(β; (|S| − 1)mn, 2) ( 2 − 1) ln(1/β) ≤ + √ √ ρ ρ p √ ( 2 − 1) ln(1/β) ≤ ErrBound(q̃S ; q, ρ/2, β, 2)) + . √ ρ

Least squares projection

E.1

Real-valued basis functions and real-valued coefficients

We discuss how the least squares projection can be computed for a 2-dimensional Uf spanned by {ϕ1 (·), ϕ2 (·)}. The extension to m-dimensional spaces for m ≥ 2 follows analogously. In the least squares projection problem, given a function q ∈ U we want to find fa ∈ Uf such that R dist2 (q, fa )2 = I (q(t) − (a1 t + a2 ))2 dt is minimized; i.e., we want to solve the unconstrained program Z (q(t) − (a1 ϕ1 (t) + a2 ϕ2 (t)))2 dt, a = (a1 , a2 ) ∈ R2 .

minimize I

First, we show that the program is (strictly) convex. Denote the objective function as F (a1 , a2 ) := R (q(t) − (a1 t + a2 ))2 dt. We have I Z Z ∂F ∂ 2 = [q(t) − (a1 ϕ1 (t) + a2 ϕ2 (t))) ]dt = −2ϕ1 (t) (q(t) − (a1 ϕ1 (t) + a2 ϕ2 (t))) dt ∂a1 IZ ∂a1 I =2 a1 ϕ1 (t)2 + a2 ϕ1 (t)ϕ2 (t) − q(t)ϕ1 (t) dt, I Z Z ∂F ∂ 2 = [q(t) − (a1 ϕ1 (t) + a2 ϕ2 (t))) ]dt = −2ϕ2 (t) (q(t) − (a1 ϕ1 (t) + a2 ϕ2 (t))) dt ∂a2 I ∂a2 I 44

a2 ϕ2 (t)2 + a1 ϕ1 (t)ϕ2 (t) − q(t)ϕ2 (t) dt, I Z Z ∂2F ∂2F 2 = 2 ϕ1 (t) dt, = 2 ϕ2 (t)2 dt ∂a21 ∂a22 I I Z 2 2 ∂ F ∂ F = 2 ϕ1 (t)ϕ2 (t)dt = . ∂a1 ∂a2 ∂a 2 ∂a1 I =2

" ∂2F Therefore, the Hessian matrix is HF =

∂2F ∂a1 ∂a2 ∂2F ∂a22

∂a21 ∂2F ∂a2 ∂a1

# = 2Σ−1 , which is positive definite, and

the program is strictly convex. Then, the unique minimizer of F (a1 , a2 ) is the point that makes ∂F ∂F ∂a1 = 0 = ∂a2 . That is, R 2 RI a1 ϕ1 (t)2 + a2 ϕ1 (t)ϕ2 (t) − q(t)ϕ1 (t) dt 0 = 2 2 a2 ϕ2 (t) + a1 ϕ1 (t)ϕ2 (t) − q(t)ϕ2 (t) dt 0 R RI R 2 a1 RI ϕ1 (t) dt + a2 I ϕ1R(t)ϕ2 (t)dt q(t)ϕ1 (t)dt I R ⇐⇒ = a1 I ϕ1 (t)ϕ2 (t)dt + a2 I ϕ2 (t)2 dt q(t)ϕ2 (t)dt R R R IR 2 a1 q(t)ϕ1 (t)dt q(t)ϕ1 (t)dt ϕ1 (t) dt ϕ1 (t)ϕ2 (t)dt a1 I I I I R R R R =Σ = ⇐⇒ . ⇐⇒ a2 a2 ϕ1 (t)ϕ2 (t)dt ϕ2 (t)2 dt I q(t)ϕ2 (t)dt I q(t)ϕ2 (t)dt {z I } | I Σ−1

(10) Let a∗ =

R ∗ a1 q(t)ϕ (t)dt 1 I := Σ R . Then we can verify that a∗2 I q(t)ϕ2 (t)dt Z Z (q(t) − (a∗1 ϕ1 (t) + a∗2 ϕ2 (t))ϕ1 (t)dt = 0 = (q(t) − (a∗1 ϕ1 (t) + a∗2 ϕ2 (t))ϕ2 (t)dt, I

i.e., q − (a∗1 ϕ1 + a∗2 ϕ2 ) is orthogonal to Uf .

E.2

Vector-valued basis functions and real-valued coefficients

For vector-valued functions u, v : I → Rn , consider with inner product Z Z T ⟨u, v⟩ = u(t) v(t)dt = (u1 (t)v1 (t) + · · · + un (t)vn (t))dt I

where u = (u1 , · · · , un ), v = (v1 , · · · , vn ). Note that the space containing vector-valued functions u such that ⟨u, u⟩ < ∞ is complete (i.e. a Hilbert space). We have vector-valued function q = (q1 , · · · , qn ) ∈ U , space Uf spanned by the set of vectors {ϕj (·)}j∈[m] where each ϕj = (ϕj,1 , · · · , ϕj,n ) ∈ L2 (I), and wish to minimize   2    ϕ1,1 ϕm,1 q1 (t)  ..   .   .   .  − a1  ..  + · · · am  ..  dt  Z F (a) := I

qn (t)

ϕ1,n

ϕm,n

over a = (a1 , · · · , am ) ∈ Rm . F (a) =

Z X n

(qr (t) − (a1 ϕ1,r (t) + · · · + am ϕm,r (t)))2 dt

I r=1

∂F = ∂aj

Z X n

∂2F = ∂a2j

Z X n

∂a1 ∂a2

 2  ∂ F  HF =  ∂a2.∂a1  .  .

···

∂2F ∂a1 ∂am

∂2F ∂a2m

···

R Pn

2 r=1 2ϕ1,r (t) dt

Z X n

2ϕj,r (t)ϕk,r (t)dt for j ̸= k.

I r=1

      

. .. .

∂2F ∂am ∂a1



∂2F = ∂aj ∂ak

2ϕj,r (t)2 dt,

I r=1

The Hessian matrix  ∂2F ∂2F ∂a21

−2ϕj,r (t) (qr (t) − (a1 ϕ1,r (t) + · · · + am ϕm,r (t))) dt

I r=1

R Pn I

···

r=1 2ϕ1,r (t)ϕ2,r (t)dt

 R Pn ..  . 2ϕ2,r (t)ϕ1,r (t)dt r=1 I  = ..  . R Pn 2ϕ ··· m,r (t)ϕ1,r (t)dt I r=1 R R 2 I ϕ1,r (t) dt I ϕ1,r (t)ϕ2,r (t)dt · · ·  R .. n X  ϕ2,r (t)ϕ1,r (t)dt .  I =2  .. . r=1  R ϕm,r (t)ϕ1,r (t)dt ··· {z | I

R Pn



r=1 2ϕ1,r (t)ϕm,r (t)dt

.. .

R Pn

2 r=1 2ϕm,r (t) dt

I ϕ1,r (t)ϕm,r (t)dt

.. .

2 I ϕm,r (t) dt

    

   .   }

Σ−1 (r)

Thus, HF = 2Σ−1 and is positive definite. For all j ∈ [m] n

r=1

X ∂F = 0 ⇐⇒ ∂aj ⇐⇒ a1

ϕj,r (t) (a1 ϕ1,r (t) + · · · + am ϕm,r (t)dt) =

r=1

n Z X r=1

n Z X

ϕj,r (t)ϕ1,r (t)dt + · · · + am

n Z X r=1

ϕj,r (t)qr (t)dt

ϕj,r (t)ϕn,r (t)dt =

n Z X r=1

ϕj,r (t)qr (t)dt



⇐⇒

r=1 I ϕj,r (t)ϕ1,r (t)dt

···

 a1 n Z  .  X Pn R . ϕj,r (t)qr (t)dt. r=1 I ϕj,r (t)ϕm,r (t)dt  .  = I r=1 am

The minimizer is therefore given by  R     Pn R  R ϕ1,r (t)2 dt ··· ϕ1,r (t)ϕm,r (t)dt a1 ϕ1,r (t)qr (t)dt n r=1 I I I X   ..    .. ..   .  =   . . R R R P n 2 dt r=1 ϕ (t)ϕ (t)dt · · · ϕ (t) a ϕ (t)q (t)dt 1,r m r r=1 I m,r I m,r I m,r 46

  Pn R  a1 r=1 I ϕ1,r (t)qr (t)dt     .. ⇐⇒  ...  = Σ  . . Pn R am r=1 I ϕm,r (t)qr (t)dt  

(11)

 ∗  Pn R a1 r=1 I ϕ1,r (t)qr (t)dt  ..    .. ∗ Let a =  .  := Σ  . Then a∗ is the unique minimizer of F (a) and . R P n a∗m r=1 I ϕm,r (t)qr (t)dt   ϕl,1 (t) Z X   (q(t) − a∗j ϕj (t))T  ...  dt = 0 I j∈[m] ϕl,n (t) for l ∈ [m].

E.3

Real-valued basis functions and vector-valued coefficients

We have vector-valued function q = (q1 , · · · , qn ) ∈ U , m-dimensional space Uf ⊂ L2 (I) spanned by {ϕj (·)}j∈[m] , and wish to minimize       2 q1 (t) a1,1 am,1  ..   ..   .    .  −  .  ϕ1 (t) + · · ·  ..  ϕm (t) dt  Z F (a) := I

qn (t)

a1,n

am,n

over a = (a1,1 , · · · , am,1 , · · · , am,n ) ∈ Rm×n . As in Section E.1 above, we show that the minimization program with objective function F (a) is convex. F (a) =

Z X n

(qr (t) − (a1,r ϕ1 (t) + · · · am,r ϕm (t)))2 dt,

Z r=1 ∂F = −2ϕj (t)(qr (t) − (a1,r ϕ1 (t) + · · · am,r ϕm (t)))dt ∂aj,r I Z Z ∂2F ∂2F 2 = 2 ϕj (t) dt, = 2 ϕj (t)ϕk (t)dt, ∂aj,r ∂ak,r ∂a2j,r I I The Hessian matrix  ∂2F ∂a21,1 ∂2F

   ∂a2,1 ∂a1,1 HF =  ..  . 

∂2F ∂am,n ∂a1,1

where

···

∂2F ∂a1,1 ∂am,1

∂2F ∂a22,1

··· .. . ···

···

∂2F ∂a1,1 ∂a1,2

···

∂2F = 0 for r ̸= s. ∂aj,r ∂ak,s

∂2F ∂a1,1 ∂am,n  ∂2F  ∂a2,1 ∂am,n 



.. .

∂2F ∂a2m,n

 (0) HF 0  .. . .. = .   0 ···

 R R 2 I ϕ1 (t)2 dt · · · 2 I ϕ1 (t)ϕm (t)dt   (0) .. .. .. HF =  . . . R R . 2 2 I ϕm (t)ϕ1 (t)dt · · · 2 I ϕm (t) dt 

··· .. . (0)

  

Thus, HF = 2Σ−1 and is positive definite. We find the minimizer of F (a) by setting the gradient , . . . , ∂a∂F ]T = 0. We have for all j ∈ [m], r ∈ [n] vector [ ∂a∂F1,1 , . . . , ∂a∂F m,n m,1 Z ϕj (t)(a1,r ϕ1 (t) + · · · am,r ϕm (t)))dt = ϕj (t)qr (t)dt I I  a1,r Z R  .  R . ϕj (t)qr (t)dt, ⇐⇒ I ϕj (t)ϕ1 (t)dt · · · I ϕj (t)ϕm (t)dt  .  = I am,r

∂F = 0 ⇐⇒ ∂aj,r

so the minimizer of F (a) is given by  R   R  R 2 · · · I ϕ1 (t)ϕm (t)dt a1,r I ϕ1 (t) dt I ϕ1 (t)qr (t)dt    ..    .. .. .. ..   .  =   . . . . R R R 2 ϕm (t)ϕ1 (t)dt · · · am,r I ϕm (t) dt I ϕm (t)qr (t)dt | I {z } Σ−1 0

for r ∈ [n]. In terms of the matrix Σ,   a1,1  ..    .  Σ0    am,1      a1,2  =     ..   .  | am,n

E.4

R

 ϕ (t)q (t)dt 1 1 I  ..    . R     RI ϕm (t)q1 (t)dt  .. .  .   I ϕ1 (t)q2 (t)dt  Σ0   ..  {z } . R Σ I ϕm (t)qn (t)dt

(12)

Approximations of functions in C([0, T ]) using basis in L2 (R)

In Section 3.5, we discussed how a continuous function q ∈ U can be approximated using basis functions in L2 (R) by treating q as a function in L2 (R). In particular, we let L(q) denote the extended function that satisfies L(q)(t) = q(t) for t ∈ [0, T ], and L(q)(t) = 0 otherwise. Let the basis functions be {ϕj }j∈[m] ⊂ L2 (R). By Appendix E.1 above, the least squares projection of L(q) onto the span of {ϕj (·)}j∈[m] is given by 

R∞

2 −∞ ϕ1 (t) dt

···

.. . ϕ (t)ϕ m 1 (t)dt · · · −∞

  R∞

R∞

 R ∞  R T  a1 −∞ L(q)(t)ϕ1 (t)dt 0 q(t)ϕ1 (t)dt   ..      .. ..  .  =  = . . . R∞ R∞ RT 2 am −∞ ϕm (t) dt −∞ L(q)(t)ϕm (t)dt 0 q(t)ϕm (t)dt

−∞ ϕ1 (t)ϕm (t)dt



On the other hand, the least squares projection of q onto the span of {ϕj (·)1[0,T ] (·)}j∈[m] is given by  RT   R T  RT 2 ··· a1 0 ϕ1 (t) dt 0 ϕ1 (t)ϕm (t)dt 0 q(t)ϕ1 (t)dt    ..    .. ..   .  =  . . . RT RT R T 2 am 0 ϕm (t)ϕ1 (t)dt · · · 0 ϕm (t) dt 0 q(t)ϕm (t)dt Thus, while using basis functions in L2 (R) might be more convenient in some cases, the quality of the approximation could be different. 48

Additional Statistics on Experimental Evaluation

In this section, we provide additional statistics on our experimental evaluation presented in Section 5 and Appendix C.3, for the results on the ECG and taxi trajectory datasets. Observe that for the taxi trajectory dataset, the median errors for the baseline methods are noticeably smaller than the mean errors (Fig. 18a vs. 10a, and Fig. 18b vs. 15a), indicating that there were extreme curves in the taxi trajectory dataset that severely damaged the performance of the baseline methods; on the other hand, the median and mean errors are similar in our methods, so our methods are less impacted by such curves. Overall, the advantage of our methods is clear. Project-and-Privatize Baseline Baseline (smoothed)

101

Project-and-Privatize Baseline Baseline (smoothed)

101

100 100 10 1 10 1 0.1

0.2

0.5

Privacy Budget

1.0

2.0

8e-05

(a) GP L2 error

0.00032

0.002

Privacy Budget

0.008

0.032

(b) CGP L2 error

Figure 17: L2 error on the ECG dataset: median, 25th and 75th percentiles.

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

102 101

LS Approximation PrivFuncSeg PrivFuncSeg (continuous) Baseline Baseline (smoothed)

101 100

100 10 1 10 1 10 2 10 2 0.001 0.002

0.005 0.01

0.02

Privacy Budget

0.05

10 3

0.1

(a) GP L2 error

1.25e-08

5e-08

3.125e-07 1.25e-06

5e-06

Privacy Budget

3.125e-05 0.000125

(b) CGP L2 error

Figure 18: L2 error on the taxi trajectory dataset: median, 25th and 75th percentiles.

Record · ID 410926 · SHA-256 eeee71052a0ccccb
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.