Online robust locally differentially private learning for nonparametric regression
Authors: Chenfei Gu
Qiangqiang Zhang
Ting Li
Jinhan Xie
Niansheng Tang
Venue: NeurIPS 2025 poster ()
Keywords: Online learning
nonparametric regression
local differential privacy
Huber loss
Primary area: general_machine_learning

Abstract: The growing prevalence of streaming data and increasing concerns over data privacy pose significant challenges for traditional nonparametric regression methods, which are often ill-suited for real-time, privacy-aware learning. In this paper, we tackle these issues
by first proposing a novel one-pass online functional stochastic gradient descent algorithm that leverages the Huber loss (H-FSGD), to improve robustness against outliers and heavy-tailed errors in dynamic environments. To further accommodate privacy constraints, we introduce a locally differentially private extension, Private H-FSGD (PH-FSGD), designed to real-time, privacy-preserving estimation. Theoretically, we conduct a comprehensive non-asymptotic convergence analysis of the proposed estimators, establishing finite-sample guarantees and identifying optimal step size schedules that achieve optimal convergence rates. In particular, we provide practical insights into the impact of key hyperparameters, such as step size and privacy budget, on convergence behavior. Extensive experiments validate our theoretical findings, demonstrating that our methods achieve strong robustness and privacy protection without sacrificing efficiency.

Online robust locally differentially private learning for nonparametric regression
Chenfei Gul Qiangqiang Zhang** Ting Lift Jinhan Xie
Niansheng Tang' 'Scooo of Statisties and Data Science, Shanghai University of Finance and Economics ZZhongtai Securities Institute for Financial Studies, Shandong University Yunnan Key Laboratory of Statistical Modeling and Data Analysis, Yunnan University sdu. edu. en,
gu. chenfei@ @liee..eeee....eeee sufe. edu. en, tingli@mail shufe. enu (jinhanxie, nstang) @ynu. edu. cn
Abstract
The growing prevalence of streaming data and increasing concerns over data pri- vacy pose sigmificant challenges for traditional nonparametric regression methods, which are often ill-suited for real-time, privacy-aware learning. In this paper, we tackle these issues by first proposing novel one-pass online functional stochastic gradient descent algorithm that leverages the Huber loss (H-FSGD), to improve robustness against outliers and heavy-tailed errors dynamic environments. To fur- ther accommodate privacy constraints, we introduce a locally differentially private extension, Private H-FSGD (PH-FSGD), designed to real-time, privacyprreeervng estimation. Theoretically, we conduct comprehensive non-asymptotic conver- gence analysis of the proposed estimators, establishing finite-sample guarantees and identifying optimal step size schedules that achieve optimal convergence rates. In particular, we provide practical insights into the impact of key hyperparameters, such as step size and privacy budget, on convergence behavior. Extensive experi- ments validate our theoretical findings, demonstrating that our methods achieve strong robustness and privacy protection without sacrificing efficiency.
1 Introduction
Nonparametric regression, which models the relationship between response variable and its predic- tors without imposing a specific functional form, is fundamental tool in statistical data analysis. It has been extensively studied over the past several decades (c.g.. Siegel [1957] Härdle (199)), Wasserman and Lafferty| [2005). Takezawa (2005) and is particularly well-suited for capturing complex and nonlinear structures in data. More recently, nonparametric modeling has provided powerful insights into complex and dynamic systems across a range of applications, including deep learning (Schmidt-Hiebel Hieber 2020 Zhang and Wang 2024], climatology (Huth and Pokorná 2004
Deb and Jana 2024]. and economics [Donnelly et al. 2011 Salibian--Baa BBrrera 2023
Traditional nonparametric regression methods typically assume full access to the entire dataset beforehand and require it to be stored entirely memory. Within this batch learning framework, model estimation is conducted only once based on the full dataset. However, this paradigm faces substantial limitations in streaming data environments, where observations arrive sequentially and continuously over time. In such settings, storing and processing the entire data stream simultancously often infeasible. For example, data generated in real time by autonomous vehicles or large-scale sensor networks in smart cities accumulate rapidly and far exceed the capacity of available memory
"qqual contribution.
CCorresponding authors: Ting Li and Jinhan Xie.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

resources. In contrast to classical batch learning, online learning methods are designed to dynamically update model estimates using only the currently available data, thereby enabling real-time time decision- making in nonparametric regression. Too date, such methods have been extensively studied in the literature; see, for example, Gu www.annaaaaafeeaaee Lafferty [2012] Huang et al. [013). Kuzborskij and Cesa- Bianchi]
[2017], (uue and Yao [2022.. . Yang et al. [2024) Quan and Lin 2024]. Beyond these approaches, a line of work has focused on functional stochastic gradient descent (FSGD) approximation algorithms developed within the framework of reproducing kernel Hilbert spaces (RKHS) more general Hilbert
spaces; see Kivinen et al. [2004]. Dieuleveut and Bach (2016), Zhang and Simon
[0222] Liu et al.
2023 Zhang and Simon 2023]. Chen and Klusowski 22224,, Fonseca et al. [0024] Nevertheless,
common limitation across the above literature is the implicit assumption of unrestricted access to raw
individual, level data throughout the learning process.
As data complexity and volume continue to grow, so do the challenges associated with safeguarding individual privacy and maintaining public trust, particularly in applications involving potentially sensitive user data, such as patient records in healthcare or behavioral logs in e-commerce platforms. Differential privacy (DP), one of the most widely adopted frameworks [Dwork et al. 2006a bj. pro- vides rigorous guarantees that the output of a statistical analysis does not reveal sensitive information about any individual in the dataset. Owing to its rigorous mathematical definitions and practical applicability, DP has been successfully applied in numerous fields, including medical imaging, health- care analytics, and intelligent transportation systems [Dankar and El Emam 2013 Ziller et al., [022]] Bhadani 2024]. In the literature, two primary variants of DP have been extensively studied: the central differential privacy (CDP) model assumes the existence of a trusted server that can securely collect, store, and process raw data from users, and the local differential privacy (LDP) model eliminates the need for such a trusted entity by requiring each user's ' data be privatized at the source, before being transmitted to any data aggregator or processor (see e.g. Dwork et al. (2014). Duchi et al.]
20188, Berrett and Yu (02T). Li al. [2023] Duchi and Ruan (2024)) ). However, privacy protection inevitably introduces tension with two other key objectives: model robustness against adversarial per- turbations and statistical utility. This fundamental trade-off, known as the privacy-robustness--
trilemma, has been extensively studied across different learning paradigms, including distributed learning (Allouah et al. 2023], adversarial learning with certified guarantees (Phan et al., [022)]. and decentralized ryzzantine-robur systems (Ye et al.] 2024]. Although substantial progress has been made under both paradigms, most existing methods are dedicated to miite-dimensional learning problems such as fitting parametric regression model.
Recently, increasing attention has been directed toward privacy-preserving estimation in infinite- dimensional settings, where either the inputs, outputs, or both are functions in nature. Most existing work in this area has been developed under the CDP framework. For example. (Hall al. 2013 proposed to add an appropriately calibrated Gaussian process to release functional data while preserv- ing privacy. Building this idea. Mirshani al. [2019] developed the Gaussian mechanism general framework capable of releasing a broad class of functional estimators. |Reimherr and Awan [2019] further generalized this line of work by introducing privacy mechanisms based on centered elliptical processes. In parallel, Awan et al. [2019) studied the exponential mechanism in separable Hilbert spaces, with applications statistics. More recently, [in and Reimberr (2024) introduced the independent component Laplace process mechanism to achieve pure DP for functional summaries in separable dimneioad
more
functional data analysis, shape analysis, and nonparametric
Hilbert spaces. Cai et al. [2024] examined the statistical optimality of federated nonparametric regression under DP constraints. In cases where the infiniteddimensional functional space can be effectively approximated by finite number of basis functions, several methods have utilized the post- processing property of DP to design privacy- preseeciipne procedures. For example, Cai et al. (2023) introduced CDP-based techniques for nonparametric regression under basis-functis representations. Extending this line of work, Xue et al. (2024) established statistically optimal estimation procedures for distributed functional mean estimation and varying coefficient models under varicty of DP frameworks. Despite these advances, existing approaches are primarily designed for batch learning and often rely on trusted data curator. To the best of our knowledge, no scalable and statistically sound method has yet been developed to perform online private nonparametric regression under the LDP framework. This gap leads to the following fundamental question:
Can one design online, private, nonparametric regression algorithm that is robust to heavy-tailed noise and simultaneously satisfies LDP, without compromis- ing statistical efficiency?
2

---

Privacy?
Receive Data
One by One
No
% Noise
Update
Functione LDP Estinatoo
H-FSGD
PH-FSGD
Figure I: Flowchart of the proposed online robust privacy-rreservin estimation framework. Data is received one by one, optionally perturbed with noise for privacy, and then used to update a functional LDP estimator via either H-FSGD or PH-FSGD.
The main goal of this paper is address the question outlined above. To this end, develop fully online robust LDP framework for real-time estimation nonparametric regression. Specifically, introduce novel algorithms, i.e., H-FSGD and PHH-FSGD, that enable efficient and privacy- preserving learning in streaming data environments. In contrast to minimizer-optimal loss alignment approaches [Allouah al. 2023 for addressing the privacy- porracy-robuttnss-uuiiii trilemma, our method achieves inherent outlier robustness via Huber loss framework. A flowchart illustrating the structure of the proposed framework is provided in Figure [ comparative summary our method against representative recent works in nonparametric regression is provided in Table For brevity, we include one example from each category of related methods. Our main contribution can be summarized as follows:
Online robust LDP estimation framework: Our framework provides rigorous per-iteration LDP guarantees for nonparametric regression in an online setting, addressing key limitation of existing methods that typically require access to the entire dataset. By incorporating Huber loss into our framework, the proposed algorithms attain robustness to outliers and heavy-tailed errors, thereby enabling robust
real-time saal-imme estimation in dynamic environments.
One-pass algorithms: The proposed algorithms are both designed to operate in an online, one- pass manner, yielding LDP estimators with O(1) time and space complexity per iteration for nonparametric regression. By eliminating the need store re-access historical data, our approach avoids the (n) computational and memory overhead typically associated with maintaining past kernel evaluations. This design enables high computational efficiency and inherent scalability, making the algorithms particularly well-suited for large-scale streaming data environments.
Non-asymptotic analysis: We systematically establish non-asymptotic convergence rates for our estimators, with without LDP, under both constant and decaying step-size regimes. Our analysis operates in a general framework that recovers the best approximation the true function within the RKHS. The convergence rate depends on the sample size, step size, and the smoothness of both the RKHS and the original space containing the best approximation. Specifically, under a constant step-size scheme, the proposed estimators attain the minimax optimal rate not only when the original function space matches or is smoother than the estimation space, but also in certain cases when is less smooth.
Table I: A comparison recent results on nonparametric regression.
Method
Online
One-pass
Robust
Optimal rate
Privacy
Hall al. 2013
Dieuleveut and Bach
2016
*x*
Liu et al. 2023
Quan and Lin 2004
Proposed
V
3

---

2 Problem formulation
We observe an independently and identically distributed stream of data {(X,, vn))== generated from the regression model
Y, (X,, + Cn:
where X, E X' is the n-th copy of the covariate X with marginal distribution Px, Yn E I is the response, en is the noise with E[e)
Var(e) o² and Cov(e, X) and the regression function f belongs to (2x) with || < oc. For our theoretical analysis, we assume finite- variance noise to derive tractable bounds on the gradient variance. This assumption encompusses many common heavy-tailed distributions, such as the Student-f distribution with degrees of freedom 2, the Laplace distribution, and the symmetric Pareto distribution with shape parameter a 2. Empirically, however, our procedure remains robust even under infinite-varianee conditions, such as Cauchy noise (see Subsection H.4.
Our objective is to estimate f* in a streaming setting that operates in a single pass, where samples arrive sequentially and storing the entire dataset is infeasible. Online methods that incrementally process data are increasingly adopted for large-scale problems due to their computational and memory efficiency (Zhang and Lei 2025]. At the same time, many application domains that generate streaming data, such as healthcare Mohammed et al., 2013), medical records (Liu et al., 2024), and customer analytics (Hard al.) 2019]. require formal privacy protection, which motivates the design of algorithms that provide provable privacy guarantees while remaining computationally efficient. These desiderata raise several intertwined challenges: the target is an
function, yet the algorithm is restricted to single update per sample, which rules out classical offline kernel methods requiring multiple passes and global optimization [Cai and Yuan 2011]) most differential privacy techniques are developed for miiee-dimensional parameters [[work et al.) (2044) and do not transfer straightforwardy to infinite-dimensionall single-pass function estimation; and heavy-tailed noise can make gquared-loss-based online methods [Dieuleveut and Bach 2016) unstable, necessitating
robustness in the loss function.
To address robustness in the presence of heavy tails and to facilitate private updates, we consider Huber regression an RKHS. Concretely, we study the population optimization
min SEN
E L, (y-YY-Y-F - ((X),
where L, is the Huber loss with parameter T > 0:
(u) f Iflul < + (7/u) 2/²²) 2/7") > r}.
(2)
The Huber loss combines the efficiency of squared loss for small residuals with the robustness of absolute loss for large residuals; importantly for our setting, for fixed r yields uniformly bounded gradients, which both stabilizes online updates and simplifies the design of per-iteration noise under LDP without relying on ad-hoe gradient clipping (see (6) for gradient details).
We take H. to be a RKHS on X' with kernel ((:-)) and inner product (. To allow for model misspecification we do not require f* E H: instead we target the best RKHS approximation
fn == arg min E [(Y - f(x))²]
JEH
where H denotes the closure of H in (Px))) The RKHS restriction is a standard device in nonparametric regression that converts the infiniteddimensiona estimation problem into a tractable functional estimation framework while permitting a misspecified truth [Wahba] 1990 Dieuleveut and Bach, 2016 Zhang et al. (2023).
We place the following standard regularity conditions the covariate distribution and the kernel. Assumption 1. Suppose that the distribution of Px has full support in X.
Assumption 2. The kernel is continuous and uniformly bounded on the diagonal: supsex K(xxx) S B² < 30 for some B* > 0.
Assumptions 2 are common in nonparametric RKHS regression and ensure basic well-posedness of the estimation task (Cai and Yuan 2011 Zhou et al. 2020 Liu and Li 2023]

---

Since privacy is core concern in our work, we adopt the LDP framework, which removes the need for trusted curator by randomizing data at the user side prior collection. Formally, for E > 0 and 5 2 0, randomized mechanism M X + y is ().D) if for any x, E X and measurable E c y holds that
((M(a) E E) S ( +
where the probability is taken over the randomness of M Xiong et al. 2020J. Within the online RKHS framework, the LDP mechanism leverages the boundedness of Huber gradients to calibrate noise precisely to the sensitivity of each update, ensuring rigorous privacy guarantees while preserving statistical efficiency.
Our aim is to construct a computationally efficient, single-pas pasleeppsssss sequence of estimators {fn Jnnn11 C H. that can be updated incrementally upon receipt of , and that satisfies I| ful Il (x())) + 0 as n -> oo in both the non-private and the LDP settings. The algorithms leverage the Huber loss achieve robustness heavy-tailed noise and yield bounded per-iteration sensitivity suitable for LDP.
More background information regarding RKHS and DP is presented in Appendix B
We introduce the notation used throughout the paper. Let {an Jn21 and {bn)n21 n2 are two sequences of non neganiee numbers. On - bn, or an = O(b,,) indicates that a, S Cb,, for some constant C' > 0 independent of On Z, bn indicates that on 2 Cb2, for some constant C 0 independent of a, x bn represents On < bn and 0g Z 6n Denote Px as the distribution of X over the space X. and I2 (f X R fx d(x))dx(x)) as I1.f11i,,, = Sx d(x) -(((())
) is defined oo). The norm -118,x for f E (Px)
3 Methodology
In this section, we propose the online robust nonparametric estimation within the RKHS framework to the minimization problem ( which is universal for pprvacc-preservvnn and privacy-preservnng settings.
3.1 Robust functional SGD
We first propose a Huber functional stochastic gradient descent (H-FSGD) algorithm to solve ① in the streaming data setting without DP. Inspired by functional SGD methods for squared loss [Lu
et al. 2023 H-FSGD extends this approach to the Huber loss. Given initial estimate fo (e.g..
fo(.) fo)-) 0), the estimate is recursively updated upon the arrival of each new sample (X,,, Y.)
as follows:
- 11--177 (L
Jn
n2
-nn
1 T1.
(3)
n
where "nn is the step size, and VL, is an estimator of the Fréchet gradient of the Huber loss evaluated at (X,, Y,). This update generalizes classical SGD to the functional setting with a robust loss, and the Polyak average f,, further improves stability and accuracy by averaging over the update trajectory Ruppert 1988 Polyak and Juditsky 1992).
By the reproducing property of the kernel K, any f E H satisfies f(X) = (f, Kx)x. where Kx(-) = K(X,)). The Fréchet derivative of (f, Kx)x with respect to f is Kx. Therefore, the gradient estimator of the Huber loss at sample (I, y) is given by
(L,()(=EV)) - {(x))K= -- (v f(x))(v -
f())) f())
(4)
where (u( = ut (lu S r) sign(u)T {lui 7). and w,- // By utilizing the reproducing property fx-1(X) (fn-1, 1, Kx)n, the recursion in (3) can be written as
fn = f--1 + wn
Yn - (fa- (x)) (Xn (f 1 Kx.1H) KX..
(5)
Fm n1
1
fm.
fn-1
+ n
n
5

---

The proposed H-FSGD algorithm updates iteratively without storing historical raw data. In practice, we retain the current estimate fn-1 evaluated on fixed grid (t, (t,) Upon receiving the n-th sample (Xn, Yn), the prediction fn-1(X, (X,) can be computed as (fn-1, Kx,) H. requiring only the current estimate fn-1 and Kx, calculated at the new Xn, which offers greater flexibility and lower memory usage.
The parameter r in the Huber loss establishes a trade-off between robustness and bias in the estimatiion, data-driven
which is consistent with classical literature [Fan et al.) 2017]. In practice, procedure to choose the parameter т, motivated by classical Huber loss methods [Holland and Welsch 1977]. Firstly, obtain an initial estimator fr' of fu via the existing ceast-squares functional SGD Dieuleveut and Bach 2016) and small samples. Secondly, calculate the prediction errors {resi, ) based on the estimator ftS, and get the robust estimation of a via the median absolute deviation estimator, i.c.,
δ Median|[resii, (ttessi/)/0.65/ /0.6745.
Lastly, construct 1.345ö, where 1.345 is the default value R package ('rlm' function) to achieve 90% efficiency for normally distributed noise.
We summarize the selection of in Algorithm and the proposed H-FSGD in Algorithm Please see Appendix C
3.2 Robust locally differentially private functional SGD
Protecting sensitive information in real-time data streams is paramount to prevent unintended disclo- sures as each new observation is processed. Unlike Hall et al. 2013]. which applies DP to the entire algorithm in centralized manner, our approach integrates privacy protection into each iteration step. This design eliminates the need for a trusted data collector and achieves LDP by ensuring that data privatized at the source before any aggregation occurs.
To ensure rigorous LDP guarantees, we augment Algorithm by adding per-iteration Gaussian process noise. Under Assumption aannd the definition of the Huber loss, for any N, and pair of input individual values (s, v); =" yz), we have
sup VL(Jn- VI( 1/ S 27 sup 2,2²
|Kg| S 2T
(6)
=E
The quantity BrB corresponds to the sensitivity in the standard LDP framework [Xiong al.
2020]. Let En be the sample path Gaussian process having mean zero and covariance function 87 1 log(2/6.) K, where (s,, dn) is the privacy budget the n-th iteration. Applying Proposition fi
we propose the private H-FSGD (PH-FSGD) as following, initialized fu fo O,
Jn fn- + W- (Yn V (x,,1, (Yn. - (fa-1, Nid,1,Kx,1e Kx,,x) Kx, Inhns
Fn = n - Fn fm.
worth noting that PH-FSGD supports varying privacy constraints across iterations, with per- iteration noise ensuring that each data point protected at the source.
We summarize our approach as Algorithm D
make the following remarks.
Remark 1. Algorithm supports mixed privacy regimes through -teration-specific privacy budgets. Large En values effectively imply non-private updates. While our current experiments focus on fully private or non- con-private settings, the algorithm naturally accommodates hybrid cases by adjusting per-iteration noise.
Remark 2. While our method is developed in the infiiit-ddimensionl RKHS, the computational implementation employs grid discretization finite approximation, which is standard approach in functional data analysis to balance computational feasibility with theoretical fidelity. Following established practice (e.g.. Dieuleveut and Bach [016). Liu et al. (023) )
dense grids ensure accurate function recovery, with approximation error diminishing as grid density increases.
Remark When outliers are not a concern (T - oo), the Huber loss reduces to squared loss. the context of DP, the privacy guarantee is governed by the sensitivity of the gradient. Without additional

---

Algorithm PH-FSGD
1: Input: The streaming data {(X,, Yn) nER. the initial estimates f(-) = f(-) = the step size sequences ('nn IEN, the tuning parameter 0, the reproducing kernel K, the bounded parameter B >> O, the privacy parameters { {ôn JUEN, and the function grids (4:))=r
2: for = 1,,, 1, ... do
3:
Generate the noise {En(t)))== from NO,
8=" log(2/6m) K(0),, where K a
matrix with its components (K );j = K(t;; tz).
4: Calculate the residual: res,, Yn (fn-1. 1fn-1.Xx.77 Kx.)
5:
Perform the noisy gradient descent at each function grid t, for j = I....,JJ as follows.
6: if rres
7: then (1;) = fn-1 (11) + In res, K ((X: (1Xnn4)) (4) + mmn((1))
8: elseif res,, >
9:
then ft())) = (1 + 7n K( n, (n
else [(,) = In-1(( (11) 7nn T K mx (4) ma
11: Update Jn each function grid:
(n,4) n2 n In (1z) + 1 P.),)) = I....,J.
12: end for
13: Output: The estimators (Fa(ta)}z= at each function grid ty and each iteration n.
assumptions, it is standard practice to apply gradient clipping to ensure bounded sensitivity under the squared loss (Song et al. 2021). If the response variable Y is further assumed to be bounded, then the gradient sensitivity is naturally finite, and the privacy guarantee directly depends its magnitude. Thus, squared loss remains privacy-compatbbe with proper sensitivity control.
Theorem 1.
The estimators fn and fn at each iteration (maxisien { (ixx)sisnn6,))-LD for E N.
N in Algorithm satisfy
Theorem ensures that each update in the proposed PH-FSGD algorithm satisfies (E. max ( by adding Gaussian process noise calibrated to the gradi- ent's s sensitivity. This protects individual sample privacy at each iteration without storing data. Cumulative privacy over time can be analyzed via the composition result in Proposition??
Theoretical properties
In this section, establish non-asymptotic convergence rates for the averaged estimator F.. We first introduce the necessary assumptions.
Assumption Suppose that the reproducing kernel K satisfies & E, where = =(K(x & Kx), and the symbol & denotes the order between self-adjoint operators.
Assumption 4. There exists a constant M > such that [| S M for all f E H.
Assumption Suppose that Cov(e, X) = 0. addition, denote Pe is the probability density function of e. There exist constants > O and k. > O such that inf Pe(t) 2 K.
Assumption 6. Denote (Vi)ieN as the sequence of non-zero eigenvalues of the operator E in the decreasing order. Suppose that V S s2i-a f"for some a > 1 and some positive constant s. <ET(LY with
Assumption 7. Assume that fH b2 Ein beb; such that Eie a consequence, ((w)lle < co.
0. where M (LPx)))
< 20
with the eigenvalues {b:}i and the eigenvectors (diti As
Assumptions 3 and are automatically satisfied by any continuous bounded Mercer kernel on compact domain. Common examples include the Gaussian, Laplace, Periodic, and Polynomial kernels. Assumption 5 is mild, as it covers any continuous distribution with positive density zero,
7

---

such as the normal distribution, t-distribution, or tero-mean uniform distribution. Assumptions 6 and [ 7 are standard in the RKHS literature (Dieuleveut and Bach 2016, Fischer and Steinwart 2020
Zhang et al.) 2023 Assumption 6 imposes smoothness via the spectral decay of the covariance operator Σ; larger decay exponent a leads to faster eigenvalue decay, effectively reducing the RKHS's s effective dimension and imposing stronger smoothness constraints. Assumption 7 relates to
the regularity of fH. A larger source condition exponent r indicates greater smoothness. In particular, when r = 1/2, the source space ( coincides with the H. For r N 1/2, the minimizer fu lies in H. whereas for r < 1/2. may reside only in the closure of H..
We establish the consistency of our proposed H-FSGD and PH-FSGD estimators. By comparing ( and (7), we observe that the non-private estimator is special case of the private one with &n for all n. Accordingly, we focus on the consistency of the private estimators here and defer the analysis of their non-private counterparts to Appendix D The privacy budget is allowed to vary across iterations. A notable special case arises when the estimator reduces to (e, 0)-LDP with a uniform privacy budget across all individuals, i.e., = E1 handling heterogeneous privacy budgets requires no additional theoretical complexity beyond the uniform case, we assume a common budget (s, 8) for simplicity.
En
and similarly for 6. Since
The following lemma plays a central role in establishing the consistency of the proposed estimators.
Lemma 1. Suppose that Assumptions 2 4 and 5 are fulfilled. Denole Ts E Ju=((,, - ((xx)) @ Kx,,) for any f E EH. There exists a constant e > 0 such that Ty b cC. for any n and any f. where > denotes the order between self-adjoint operators.
Theorem establishes the convergence rate of the privatized estimator Jn with constant step size.
Theorem 2 (Constant step size), Suppose Assumptions 77 hold. Take any constant choice V/2 = 7 = [(n). for 1 i S n. If c 'B < 1 with defined in Lemma then
fn - fHll22 Fx
((02+
8 B2
15-33/o8(2000 108(2/10) (22/an- -141/a + +n - + (1 ()) - 2 2miinf;;1) n2miimiu(r.) || || fHe fxel 1.2xx
2²
(8)
where ((),)) f S 1/2, and - (2ta)(er-))/ante0--)) for > 1/2.
On the right-hand side of (8), the first term represents the variance component, while the second corresponds to the bias. The variance term is associated with both the intrinsic noise level o² and an additional factor 87 B2 log(2/8)/E², which arises from the privacy constraint. A larger step size amplifies the variance, whereas the bias term decreases as the step size increases. This reveals fundamental variina trade-off in the choice of step size to control estimation error. Compared to regularized kernel ridge regression (KRR) with penalty parameter À in offline (Yang et al. 2017). the variance of KRR scales as X n1, and the bias as X²r By choosing À = (ym) the convergence rate of KRR matches that of our PH-FSGD estimators. Our current theoretical bounds assume sufficiently fine discretization to guarantee the grid-based solution closely approximates the RKHS optimum. While small may introduce non-negligible error, our empirical results confirm that larger J effectively mitigates this discrepancy. Extending the theory to explicitly account for finite grid effects remains an important direction for future work.
To optimize the variinarancee trade-off, we choose the step size y as prescribed in Corollary Corollary 1 (Constant step size). Under Assumptions 77 lake the constant step size 7/t = 7 [(n) x 5 foo = 1,2,....
(i) When 0 < r $ (a - 1)/(2)), take Ç = 0, then E - fulli,, $0(n-22)
(ii) When (a - 12/( < < 1, take Ç (2ra + 12r)+11 + 1). then Ellfa fral22
0 (n 2rra
(ii)) When < S (a + 2)/2, take Ç = (a + 1)/(2ra + 1), then Ellfa fu 1ull2zy
0 (n -Brra (Bra-2rt2)((2r--1))
(iv) When > (a + 2)/2, take Ç 1/(1 + a) then ElIfa - fullip S 00(n (n-ai((ta)))
8

---

The results above focus on the effect of the sample size n. all privacy parameters (E, 8) are treated as constants and are thus absorbed into the O(-) notation. For results with explicit dependence on the privacy parameters in the convergence rates, we refer to Corollary 2 When 0 < r S (a 1)/(2n), where the original space of J is less smooth than the estimation RKHS, our estimator remains consistent, with the estimation error vanishing as n - 0o, depending on r. For (e--1)(2a)) < r S 1, the estimator achieves the minimax optimal rate [Zhang et al. 2023]. This region includes the classical case Σ" (Lpxx) H with r 1/2, smoother scenarios with 1/2, and even less smooth cases where (ax (2)(a) <r < 1/2. The convergence rate improves as either or increases, reflecting the intuition that greater smoothness in the estimation or original space leads to faster rates. When 1, although Assumption 7 is stronger than 1, we do not improve the bound, which is the saturation phenomenon Engl et al. 1996].
In Appendix D we also examine consistency under non-constant step sizes. Theoretical results for non-private estimators are also included, showing similar patterns to the private case when the privacy term is set to zero. All technical proofs are provided in Appendix
5
Experiments
This section evaluates the finite-sample performance of the proposed H-FSGD and PH-FSGD estimators under two cases: (Case 1) the true function f (xx is a sine function; (Case 2) f (z) is a linear combination of two Beta density functions. Two types of errors are considered, the Gaussian distribution N (0, 0.25) and L distribution with degree of freedom 3. Simulation details are provided in Appendix F We assess both non-private and privacy-preserving settings, repeating each setup 200 times independently and using the mean squared error (MSE) as the evaluation metric.
Example 5.1 (Non-private synthetic data). In this example, evaluate the H-FSGD estimator and compare with two basclines: one-pass FSGD using least-squares loss (denoted L2-FSGD) and least-squares FSGD with access to historical data (denoted offline) from Dieuleveut and Bach (016). All three methods are tested under both constant and con-constant step-size schemes. We report the MSEs of the averaged estimators sample sizes 2000, 5000, and 10000, and include function fitting plots at n = 10000 to illustrate model performance. Box plots and corresponding function fitting results for Cases and 2 under constant step sizes are shown in Figure 2 under non-constant step sizes are presented in Figure 5 in Appendix for space considerations.
while the results
MAP
Prendiin Bnttrntiion
Panciiin Exlmation
0.825
2,0
5.004
0.800
h,003
0.813
LIVEER SI per
3.0
0.008
0.810
-3.
0.015
-1.
-10
0.004
0.635
Notee:
VAB
Puendier Bultradien
6,0055
Note:: Gaua consare
Hose: constaa
Parsdo Eolenaton
0.030
0.858
b.018
0.500
2.01
Sarephe Slae
Figure 2: Box-plots and function fitting plots for Case I (top panels) and Case (bottom panels) with the constant step size scheme in Example 5.
Figures 2 and 5 demonstrate that when the error follows a heavy-tailed distribution such as the t(3) distribution, our proposed H-FSGD method significantly outperforms the least-squares-biis based FSGD in both the median and interquartile range of the MSES, especially when the sample size is small. Under Gaussian errors, H-FSGD matches or exceeds the performance of the baseline methods. Moreover, as the sample size grows, the MSES of all three methods declines, and by n = 10000 they all achieve near- perfect function fits.
9

---

Example 5.2 (Private synthetic data). In this example, we evaluate our PH-FSGD method under two LDP settings: (3, 0.1)-LDP and (2, 0.2).LDP. Box-plots of MSEs and corresponding function fitting results under both data -ata-generating cases and constant step size schemes are shown in Figures and (in Appendix respectively.
6:35
0e: 155, SHApT COnVtRNT
0e1 181
6:12
Nottrr Gasssinn Step: cont
Gaueale. Stap: COMNIRT
0:30
6:10
Markut
6.00
0.2
6.18
660
664
602
600
10000
20090
43300
6.00
6.36
3.5
3.5
1/6
6.0
10000
20038
43300
6.00
6.26
5.5
376
1.00
Dept
0.20
6:15
0.4
6.55
8.0
6.0
10000
20098
40000
6.00
6.25
3.50
3.55
1.00
10000
2003
49300
6.00
6.25
0.50
0.75
1.00
Figure 3: Box-plots and function fitting plots for Case I (top panels) and Case 2 (bottom panels) with the constant step size scheme in Example 5.2
As shown in Figures 3] and 6 the non-private estimator consistently achieves the lowest median MSE and tightest variability, while the two LDP variants incur progressively larger error as privacy strength increases ((3, 0.1 0.1)-LDP represents moderate privacy, and (2, 0.2)-LDP represents strong privacy). These results reflect the inherent trade-off between privacy and statistical efficiency: stronger privacy (i.e., more noise) enhances protection but also leads to greater estimation error and slower convergence. Despite strong privacy constraints, all methods still recover the true function shape well. The differences in box plots and curve fits diminish the sample size increases, demonstrating that larger datasets can effectively offset the accuracy loss from LDP.
Computational time. We compare the computational efficiency of different methods on a laptop equipped with 3.20 GHz AMD Ryzen 5800H CPU and 16GB RAM. Computational times are recorded for sample sizes ranging from n = 4000 to 40000, as shown in Figure
Computation
Sample
50
LDF93D
Time (9)
5000
10000
15000
20310
25000
20030
25000
40030
Sample
Size
Figure 4: Change of computation times of our proposed H-FSGD and PH-FSGD, and baselines L2-FSGD and Offline as the sample sizes increasing from 4000 to 40000.
Figure # that both our proposed H-FSGD and PH-FSGD methods are one-pass algorithms with linear computational complexity (n)), whereas the offline method computationally intensive, exhibiting cubic complexity Onz²) as the sample size increases. Further experimental results, en- compassing analyses of step-size sensitivity, performance beyond theoretical assumptions, robustness under contamination models, and a real-data application, are detailed in Appendix F and Appendix G
10

---

Acknowledgements
We sincerely thank the reviewers, ACs, SACs, and PCs for their time, constructive feedback, and thoughtful discussions. Niansheng Tang's research was supported by the National Key R&D Program of China (No. 102022 1003701.. Chenfei Gu's research was supported by the Fundamental Research Funds for the Central Universities (No. CXJJ-2024-448). Qiangqiang Zhang's s research was supported by the National Key R&D Program of China (No. YFA 1008701) and the National Natural Science Foundation of China (Nos. 12371148, 12326603, and 12431017). Ting Li's research was partially supported by the National Natural Science Foundation of China (No. 12571304) 1304), the Shanghai Pujiang Programme (No. 24PJC030), CCF-DiDi GAIA Collaborative Research Funds and the Program for Innovative Research Team of Shanghai University of Finance and Economics. Jinhan Xie's 's' research was supported by the National Natural Science Foundation of China (No. 12501388).
References
Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. On the privacy- robustness-utility trilemma in distributed learning. In International Conference on Machine Learning, pages 569-626. PMLR, 2023.
Amit Attia and Tomer Koren, Benefits of learning rate annealing for tuning-robustness in stochastic optimization, 2025.
Marco Avella-Medina. Privacy- prrecc-preserving parametric inference: case for robust statistics. Journal of the American Statistical Association, 116(534):969 983, 2021.
Jordan Awan, Ana Kenney, Matthew Reimherr, and Aleksandra Slavković. Benefits and pitfalls of the exponential mechanism with applications to hilbert spaces and functional pea. In International Conference on Machine Learning, pages 374-384. PMLR, 2019.
Tom Berrett and Yi Yu. Locally private online change point detection. Advances in Neural Information Processing Systems, volume 34, pages 3425-3437, 2021.
Rahul Bhadani. A survey on differential privacy for spatiotemporal data in transportation research, 2024.
T Tony Cai and Ming Yuan. Optimal estimation of the mean function based discretely sampled functional data: Phase transition. The Annals of Statistics, 39(227):233-2336 2011.
T. Tony Cai, Yichen Wang, and Linjun Zhang. Score attack: A lower bound technique for optimal differentially private learning, 2023.
T. Tony Cai, Abhinav Chakraborty, and Lasse Vuursteen. Optimal federated learning for nonparamet- ric regression with heterogeneous distributed differential privacy constraints, 2024.
Xin Chen and Jason M. Klusowski. Stochastic gradient descent for nonparametric regression, 2024.
Yujing Chen, Yue Ning, Martin Slawski, and Huzefa Rangwala. Asynchronous online federated learning for edge devices with non-iid data. In 2020 IEEE International Conference on Big Data (Big Data), pages 15 24. IEEE, 2020.
Fida Kamal Dankar and Khaled El Emam. Practicing differential privacy in health care: review. Transactions on Data Privacy, 6(1):35-67, 2013.
Soudeep Deb and Kaushik Jana. Nonparametric quantile regression for time series with replicated observations and its application to climate data. Statistical Science, 39(3):428-444 448,, 2024.
Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 1399, 2016.
Aoife Donnelly, Bruce Misstear, and Brian Broderick. Application of nonparametric regression methods to study the relationship between no2 concentrations and local wind direction and speed at background sites. Science of the Total Environment, 134 2011.

---

John C Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information. The Annals of Statisties, 52(1):1-51, 2024.
John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182- 201 8.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, llya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptoloyy-ERRoCHE 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503, Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages
Springer, 2006b.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 933-4) 2014
Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
Jianqing Fan, Quefeng Li, and Yuyan Wang. Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions. Journal of the Royal Statistical Society Series B: Statistical Methodology. 79(1):247-2655 2017.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algorithms. Journal of Machine Learning Research, 21 2020.
Yuri Fonseca, Caio Peixoto, and Yuri Saporito. Nonparametric instrumental variable regression through stochastic approximate gradients. In Advances Neural Information Processing Systems, volume 37, pages 131756-131785 2024.
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. In Advances in Neural Information Processing Systems, volume 32, pages 14977-14988, 2019.
Chong Gu and Chong Gu. Smoothing spline ANOVA models, volume 297. Springer, 2013.
Haijee Gu and John Lafferty. Sequential nonparametric regression. In Proceedings of the 29th International Coference on Machine Learning, pages 387-394. PMLR, 2012.
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.
Frank R. Hampel, Elvezio M. Ronchetti, Peter J. Rousseeuw, and Werner A. Stahel. Robust Statistics: The Approach Based on Influence Functions. Wiley, New York, 1986.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction, 2019.
Wolfgang Härdle. Applied nonparametric regression. Number 19. Cambridge university press, 1990.
Paul W Holland and Roy E Welsch. Robust regression using iteratively reweighted least-squares. Communications Statistics-theory and Methods, 6(9):113882) 827, 1977.
Yinxiao Huang. Xiaohong Chen, and Wei Biao Wu. Recursive nonparametric estimation for time series. IEEE Transactions on Information Theory, 60(2):1301-1312, 2013.
Radan Huth and Lucie Pokoráá Parametric versus nonamarmmtrric estimates of climatic trends. Theoretical and Applied Climatology, 77:107-112, 2004.
Jyrki Kivinen, Alexander J Smola, and Robert C Williamson. Online learning with kernels. IFEE transactions on signal processing, 52(8):2165-2176 2004.
12

---

Iija Kuzborskij and Nicolò Cesa-Bianchi Nonparametric online regression while learning the metric. In Advances Neural Information Processing Systems, volume 30, 2017.
Mengchu Li, Thomas B Berrett, and Yi Yu. On robustness and local differential privacy. The Annals of Statistics, 51(2):117-737 2023.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-llD data. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Haotian Lin and Matthew Reimherr. Pure differential privacy for functional summaries with a laplace-like process. Journal of Machine Learning Research, 25(305):1-500 2024.
Meimei Liu, Zuofeng Shang, and Yun Yang. Scalable statistical inference in non- non-parametric least squares, 2023.
WeiKang Liu, Yanchun Zhang, Hong Yang, and Qinxue Meng. A survey differential privacy for medical data analysis. Annals of Data Science, 11(2):73-7447,22 2024
Zejian Liu and Meng Li. On the estimation of derivatives using plug-in in kernel ridge regression estimators. Journal of Machine Learning Research, 24(266):1-37. 2023.
Zichen Ma, Yu Lu, Wenye Li, and Shuguang Cui. Efl: elastic federated learning on non-iid data. In Conference Lifelong Learning Agents, pages 2151 PMLR, 2022.
Ardalan Mirshani, Matthew Reimherr, and Aleksandra Slavković. Formal privacy for functional data with gaussian perturbations. In International Conference on Machine Learning, pages 4595-4604.
PMLR, 2019.
Noman Mohammed, Xiaoqian Jiang, Rui Chen, Benjamin CM Fung, and Lucila Ohno-Machadee Privacy-preserving heterogeneous health data sharing. Journal of the American Medical Informatics Association, 20(3):462 469, 2013.
Hai Phan, My T Thai, Han Hu, Ruoming Jin, Tong Sun, and Dejing Dou. Scalable differential privacy with certified robustness in adversarial learning. In International Conference on Machine Learning, pages 7683-7694. PMLR, 2020.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-855 1992.
Mingxue Quan and Zhenhua Lin. Optimal one-pass nonparametric estimation under memory constraint. Journal of the American Statistical Association, 1195555):855-96, 2024.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax-optimat rates for sparse additive models over kernel classes via convex programming. The Journal of Machine Learning Research, 13(1):389-427, 2012.
Matthew Reimherr and Jordan Awan. Elliptical perturbations for differential privacy. In Advances in Neural Information Processing Systems, volume 32, 2019.
David Ruppert. Efficient estimations from slowly convergent robbins-monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
Matias Salibian-Barrera, Robust nonparametric regression: review and practical considerations.
Econometrics and Statistics, 2023.
Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with relu activation 2020.
function. The Annals of Statistics,
Sidney Siegel. Nonparametric statistics. The American Statistician, 110 11(3):13-19, 1957.
Shuang Song. Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages (638-266.. PMLR, 2021.
13

---

Kunio Takezawa. Introduction to nouparametric regression. John Wiley & Sons, 2005.
Grace Wahba. Spline models for observational data. SIAM, 1990.
Larry Wasserman and John Lafferty. Rodeo: Sparse nonparametrie regression in high dimensions. In Advances in Neural Information Processing Systems, volume 18, 2005.
Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, and Xiaoguang Niu. A comprehensive survey on local differential privacy. Security and Communication Networks,
2020.
Dingchuan Xue and Fang Yao. Dynamic penalized splines for streaming data. Statistica Sinica, 32 13880,3-1380, 2022.
Gengyu Xue, Zhenhua Lin, and Yi Yu. Optimal estimation in private distributed functional data analysis, 2024.
Ying Yang. Fang Yao, and Peng Zhao. Online smooth backfitting for generalized additive models. Journal of the American Statistical Association, 119(546):1115-122) 2024.
Yun Yang, Mert Pilanci, and Martin Wainwright. Randomized sketches for kernels: Fast and optimal nonparametric regression. The Annals of Statistics, 45(3):991-1023, 2017.
Haoxiang Ye, Heng Zhu, and Qing Ling. On the tradeoff between privacy preservation and byzantine- robustness decentralized learning. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages (336-9340) IEEE, 2024.
Haobo Zhang, Yicheng Li, Weihao Lu, and Qian Lin. On the optimality of misspecified kernel ridge regression. In International Conference on Machine Learning, pages 41331-41353, PMLR, 2023.
Kaiqi Zhang and Yu-Xiang Wang. Deep learning meets nonparametric regression: Are weight- decayed dnns locally adaptive?, 2024.
Tianyu Zhang and Jing Lei. Online estimation with rolling validation: Adaptive nonparametric estimation with streaming data. The Annals of Statistics, 53(6):2702-2777, 2025.
Tianyu Zhang and Noah Simon. A sieve stochastic gradient descent estimator for online nonparametric regression in sobolev ellipsoids. The Annals of Statistics, 50(5):2848. 2022.
Tianyu Zhang and Noah Simon. An online projection estimator for nonparametric regression in reproducing kernel hilbert spaces. Statistica Sinica, 33(1):127, 2023.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, 2018.
Yuhao Zhou, Jiaxin Shi, and Jun Zhu. Nonparametric score estimators. In International Conference Machine Learning, pages 1 11513-11522. PMLR, 2020.
Alexander Ziller, Tamara T Mueller, Simon Stieger, Leonhard Feiner, Johannes Brandt, Rickmer Braren, Daniel Rueckert, and Georgios Kaissis. Reconciling privacy and accuracy in ai for medical imaging. Nature Machine Intelligence, 6(7):764-774, 2024.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly articulate the paper's contributions and the problems it addresses, and these align perfectly with the methods, theoretical analysis, and experimental results presented in the main text.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of this work have been discussed in Appendix
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: We provided the full set of assumptions Assumption T7 and a complete and correct proof has been presented in Appendix[] J
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Algorithms
Section and Appendix have provided detailed information ensure the reproduction of core results.
T
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access the code with sufficient instructions, described in supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
Poolicc/guides/Codeebbbmsss
caaessionoolyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccpbblcggiii..eeee Seaeee/CCoSSuubissS..S.. www.ssssiicgcyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental settings and details have been presented in Section 5 and Ap- pendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The errors have been defined suitably and correctly, and have been reported with Box-plots of MSES and function fitting plots, as shown in Section and Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided the type of compute workers, memory and time of execution for experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics / http:///wrrrp.ccoooooo..aaaaaaaa
Answer: [Yes]
Justification: Our research strictly adheres the NeurlPS Code of Ethical requirements in all aspects.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss both potential positive and negative societal impacts in Section T
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This study does not release any new datasets or models that may pose potential risks for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have mentioned and cited all assets used in this paper properly.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.papersstt
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper proposes new algorithm for online robust locally differentially private learning nonparametric regression, no new assets such as datasets, models, or code repositories are released.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
The core methods and experimental framework in this paper do not involve the of Large Language Models.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurd) hutt::///eerrpp.cc/ooofffeereeee /c/////feeeeeees//222////.. for what should or should not be described.
21

---

Appendix
A
Notation
Table 2: List of notation
Notation
Meaning
Xn
the n-th copy of the random covariate X the n-th copy of the response Y
Ya
en
the n-th copy of the error the variance of the error e
S*
the target nonparametric function lying in the space (P2()x)
K
the reproducing kernel RKHS
H
the inner product in H
H
the closure of H
fu
the best approximation of f* in the RKHS H.
L.
the Huber loss with the parameter
V
the estimator the Frechet gradient the Huber loss the uniform upper bound of K (z, x) for all æ
B²
nn
the step size at the n-th iteration the current private estimator of fn. at the n-th iteration
fn
fn
the averaged private estimator of fu at the n-th iteration
Jo
the averaged non-private estimator of J' at the n-th iteration the privacy budget at the n-th iteration the function grids
En. 8n
(4) 1=)
Σ
the covariance operator associated with the kernel K, i.e., Σ E & Kx)
a
the parameter characterizing the decay rate of the eigenvalues of the covariance operator Σ
r
the parameter quantifying the regularity of the target function fx with respect to eigenbasis of Σ
B Background on RKHS and LDP
B.1 RKHS and linear operators
Definition 1. |Gu and Gu 2013 A Hilbert space H. of functions f X + R. is said be an RKHS if the elements of H are functions defined on a compact topological space X, and there is a bivariate function K(-,) )) X x X + R. having the following properties:
(1) For all a E X, the function K2 = K(x,)) is in H.
(2) The reproducing property holds, ie.. for all E X and f E H. f(x) = (J, KayH-
where (H.) is the associated inner product of H. In this case, K is the reproducing kernel of H.
22

---

Define an operator : (Pxx) - (Px)) such that for any f (Pxx).
Σʃ = -/=K|Kx((X);
Then for any EE E,
(X =)g(X)) If H. the reproducing property gives that = = & Kx]. where Kx @ Kx is an operator defined as (Kx @ Kx)f (f. Xx f( for f H. It follows that for any f.g E H.
If(z)= 2E
Eg = ())())((X))-
This operator links the RKHS inner product to the expected product of functions, facilitating theoreti-
cal analysis. Assumptions 2
make be an valid linear operator for the whole space (p²
The closure of H in (Px). denoted by H. is defined as the set of all limits of sequences in H.
Formally,
H = {f (Px) B{fa} C H. such that f fll - 0}.
Intuitively, H. consists of all functions in L²(Px) that can be approximated arbitrarily well (in (Px) norm) by a sequence functions H.. This construction is standard in the kernel methods literature [Dieuleveut and Bach 2016). and it allows us to avoid assuming that f belongs to H. or that is dense in ('xxx).
B.2 Differential privacy
A random algorithm, denoted as M, can be intuitively considered as protecting privacy if it prevents an attacker from distinguishing whether a specific datum ir belongs to the dataset when the algorithm is applied to X. To formalize this notion, the concept of CDP is introduced.
Definition 2 (CDP, [Dwork et al. 2006a b)). Let > and 6 2 0. A dataset X (x), Ø2..... ,....,,,,, Inn) E X consists of n. data from some space X. Two datasets X and X' by only one entry, denoted as X ~ X', . random algorithm M X +Y is said to be (e, 6)-DP if for any neighboring datasets X and X', and any measurable set F. C.Y.
called neighbors if they differ
(XM E E) < P E E)
where the probabilities are computed over the randomness of the mechanism M.
This definition ensures that the probabilities of obtaining certain outcomes under the algorithm M applied to datasets X and X' are similar. However, CDP relies trusted curator, which may lead to internal exposure risks and undermine the goal of privacy protection. To address this issue, LDP eliminates such risks by randomizing data prior collection.
Definition 3 (LDP, [Xiong et al. 2-20)). Let 0 and 6 > 0. A randomized algorithm M : y P if for any pair of input individual values x, x' E X, and any measurable set said to be (e, LDDP
E BCY,
((M(2) E) S &P(((x))) E) +
where the probabilities are computed over the randomness of the mechanism M.
LDP can be regarded as a stricter variant of DP, where individuals add noise to their data before sharing, ensuring that each user's information remains confidential without relying on a trusted data collector. We next introduce the following Gaussian mechanism to construct a function estimator with DP.
Proposition 1. (Hall et al. 2013 Let D E D be input dutaset. Suppose that the family of functions {Sn: D E D) lies in the reproducing kernel Hilbert space (RKHS) H with the reproducing kernel K, the inner product (: and the corresponding norm || || Two datasets D and D' are called neighbors if they differ by only one entry, denoted as D D'. Let supp-p' llfp - fo ll S Do- c( 2 (2 1og(2/8)) for 8 > 0. Take G as the sample path of a Gaussian process having mean zero and covariance function K. Then the release of
Fo = --fD Anc(d)
(E, d)ddifferettial private.
Some useful properties for the construction of LDP algorithms are stated below.
23

---

Proposition 2. [Xiong et al. 2020
(1) Parallel composition for LDP: Let M, i L, ..... k be (E,, - mechanisms and ....... Xx be disjoint. Then M ( Xk) (M1(X))...
Mg(X&)) is (max; Ei, max; 6t)-L.P. (2) Postprocessing property for LDP: Let M1 be an (e, 6-LDDP mechanism, and M2 mechanism without any privacy constraints. Then the composition of M1 and M2, Lee, (2 )) is (c, D)-LP.
C Algorithms for H-FSGD
Algorithm 2 Choice of
1: Input: Small sample data {(Xn, Ya)) the initial estimates f(-) = f()) = O, the step size
sequences {7m the reproducing kernel K, and the function grids {t,)
2: Use existing least-squares functional SGD [Liu et al. 2023 to obtain estimator fiS.
3: Calculate the prediction errors {resi:}; J: based on the estimator fiS.
4: Estimate the standard deviation of noise via & = Median (resi,] /0..6745.
5: Choose as 1.3450.
6: Output: T.
Algorithm 3 H-FSGD
The streaming data {(X,, Yn)nnen the initial estimates f()) f(.) = 0, the step size sequences {7/m JeN, the tuning parameter via Algorithm the reproducing kernel K, and the function grids (1,))=ı-
Input:
2: for 1, ... do
3: Calculate the residual: res,, = Y,, -(nn Kx xx.
4: Perform the gradient descent at each function grid for j = 1.....J J as follows.
5: if |res/|
6: then (tt)t) (t,) In.es, (enn tj).
7: elseif res,, >T
8: then fn())) = fn- ((1) + In K ((X, Xxx ())
9: else fn(t))= fn-1(t,) - (Xn: tz).
Update Jn each function grid:
(n, n
In [t,)(t)) + (.()).) = 1,...,,
11:
end for 12: Output: The estimators (Fa(t))} at each function grid ty and each iteration n.
D Additional theoretical results
We state the following refinement of Corollary I to make the dependence the privacy parameters (c, 5) explicit the convergence rates.
Corollary 2 (Constant step size, explicit dependence on privacy parameters). Under Assumptions
take the constant step size 7% = I'nn) x n for i = 1,2.....
(i) When 0 < r < (a (2x), take ( 0, then E E - fxlli 50 (n-2r);
(ii) When (ax - 12) <r 1, take Ç (2ra + (a)/arrr + 1), then ElJJn SH 1x
O ((02 8-2 (2/6))
(222a((22ra+1))
(iti) When
s (a + 2)/2. take (a + 1)/(2ra + 1), then Ellf.. f fuelliz 0 ((02 8-2 n² lon(2/d) n - (2ra-2r+2) (2to-)2+))/errtt))
24

---

(iv) When r > (a + 2)/2, take 0 ((02 8 1= n -a/(1t)))..
1/(1 + a) then Ellfa fullipx
We consider the consistency of privatized estimators in the setting of non-constant step sizes. Theorem 3 (Non-constant step size). Suppose Assumptions / hold. Take the step sizes % i-C
with Ç E (0, 1) satisfying 2r 1/(1 () < 0, for = 1,2,.... If c BB < 1 with e. defined in Lemma ! then:
(i) & 1/2
8r B² log (2/() 5o <0((02
BlJ -fllli
9 /2/an 1-t1aa + + -2r 10 -0 fu 1.7x8
8²
(ii) </2
BlJ - fullit 50((022 8r B² Br2gBllo((2)))) log(2/0)) (n%%))-2+1/a + Va (1%m) -2r | - fH 1
2²
Consistent with Theorem 2 the first term in (i) and (ii) reflects the variance order, while the second term captures the bias order. Theorem 3 indicates that for Ç E [0, 1/2], both the bias and variance terms respond to changes of the step size similarly to those in Theorem 2
In contrast, for smaller step size with Ç E (1/2, 1), the bias term retains this behavior, but the variance term increases as the step size decreases.
We can also choose an optimal step size and achieve the optimal convergence rate.
Corollary 3 (Non-constant step size). Under Assumptions take the step sizes Ys i for
i i= 11,,,.....
(i) When 0 <r (a - 12/(2 take (= O, then TEI, - fuili 0 50(n (n-
(ii) When (a 12/(2)) < < (1 + a)/(2a). take Ç = (2ra + /2ra + 1 + a). then
F - fulli, S 0 (n -2rattt ( 11/(2r++(1))))
(iii) When (1 a) (2))) take < 1/(1 o), then BIJ Sullie (0
comparison between Corollary 3 and Corollary 1 reveals that when 0 < r S (a - 12/ or 2 (a + 2)/2, the convergence rates of the non-constant and constant step size schemes identical. In contrast, for (a (2) < r < (a + 2),2, the convergence rate achieved under the non-constant step size scheme is slower than that under the constant step size setting.
The consistency of the privatized estimators can be easily reduced to the estimators without DP, as shown in Corollary 4 [
Corollary 4 (Constant step size, without privacy). Suppose Assumptions 777 hold. Consider the estimator 1 without privacy protection defined via the recursion (5) Take any constant choice
7/s 7 [(n). for S n. If yB2 < 1 with defined in Lemma then
E fl fulli so
50 02 (22/an 1+1// +1 + (1 (1+ (1,,())))) 2r - min(r.11 || |H- 13p
Further, take [(n) x 55
(i) When 0 < r I (a - 1)/(2n), take Ç = 0, then E Sull2 L3x S
(ii) When (a - 12)( < < 1, take (2ra + (2)r + 1), then Ellfo ffull
O (n (rra
(ii) When < S (a + 2)/2, take 5 = (a + 1)/(2ra + 1), then Eljao fu 11
O (n (rra-2+2))(220-111
(iv) When (a 2)/2, take 1/(1 a) then El - fulli;, 0 (n (n-a/(l+a)).
25

---

Corollary 5 (Non-constant step size, without privacy), Suppose Assumptions hold. Consider the
estimator fll without privacy protection defined via the recursion (5). Take the step sizes %i x i-
holdd
with Ç E 10, for = 1,2..... cf -0 Bd < 1 with defined in Lemmal / and 2r 1/ () < 0,
then:
( S 1/2,
so 50(022 02yl//on n 1111aa + + (177) -2r 1 'f fulli;z))
fH 12, E f
(i) <<
E E -filli 0 (0"(1))) -241/a + 22 |E 1r.flli 13
Further,
(i) When 0 < r S (a - 12/( take Ç= 0, then El fulli33 <n(n~2))
(ii) When (a (2)(2)) < < (1+ + (2)( take = (2ra a2/ + 1 + a), then
E fuellz, 1 0 (n (2rata- (acrtta))/(raattaa))
(iii) When 2 (1 + (a)+aa/2220 (2a), take Ç 1/(1 + a), then E fulli;, 3 0n (n--a((t)a))
We summarize the theoretical results to facilitate comparison of the guarantees under private and non-private settings across different decay-rate regimes r, encompassing both constant and non-constant step-size schemes.
Constant step size. In the private setting, the error bound is
8T B² 1og(2/0)
0² +
(21/an-1+1/e + +m-1) + (1 (() 2"n -2 min 1120))111--- 112==fmliz (x
E2
whereas in the non non-private setting, the error bound is
o 0 (7 1/ 141/a + n " + (1 + a(1,n))) 2" 2mmn(f;;1) ||= ( Tuullzz
The optimal choices of ( and the corresponding convergence rates across different ranges of are summarized in Table
Table 3: Constant step size: optimal ( and convergence rates.
r range
Optimal ( in (in7 7/ x n Private non-private convergence rate
(a,
0 (2ra + 11 11)
O(n 2)) (n--2ra (n-22a/(2rat1))) (n (2ra para-20 222 22+441(2)0++1) Onn (n-aa((+a)
(a=-1)((2a),
(2)
(a + ++)/((ra++)) 1/(1 +a)
((a + 2)/2,ox
Non-constant step size. In the private setting, the error bound is
02 87 Ba 101(2/01)
7n 1// 11t1/a + (1ci.) -2 2r 12- SHe 1ell 1/xx
OSC51/2.
87 B² log (2/66)
(n%a) -2+1/a + 35m (n - 2r | fx 13
1/2<<<1,
while the non-private setting, the error bound is
{ /
o Mo 141/ + mo + (nT)) -2r))-22p
1- 1| 11e fullle
05551/2
(m))))))) 2211/a - vn 7 (m%)) -2r || - 13
1/2<
The optimal and convergence rates summarized in Table 4
26

---

Table 4: Non-constant step size: optimal Ç and convergence rates.
range
Optimal in % n
Private non prii-rtttee convergence rate
(0, (2a)]
0
O -r)
((a - 1)/(2))())))))))) (1 + (2)() (2ra + 1 1aa)/(2raaaaa ++
O(n (2ra+a- (rrata-1)//rrattaaa
(1+a)/(2a))
1/(1 +
O O(n-a/1+a))
Overall, the privacy term introduces an additional additive factor of (8+ B² increases the variance constant but does not affect the asymptotic rates under optimal step sizes.
which
E Robusstess-privccy-utttty trilemma
The interplay among the Huber parameter, the privacy budget, and the step size forms a fundamental robustness- Sooustness-privcc--uue privacy-utility trilemma. In the non non-private setting, using a smaller Huber parameter improves robustness to outliers but increases bias, which is classical couustoouss trade-off Fan et al. 2017]. In the private setting, however, larger T amplifies gradient sensitivity, requiring stronger noise for given (=,D)-LDP, which raises gradient variance and necessitates smaller % for stability. Similarly, a tighter privacy budget (e.g., smaller e) demands stronger noise, again making smaller to critical for stable convergence. The step size itself is typically chosen according to decaying schedule, either 7/4 = Ton for constant step size with sample size n or 7 = = for non-constant step size. As shown in Corollaries [ the optimal choice of the decay exponent depends on the smoothness parameters r and a. Under strong privacy noise, smaller 7o improves stability, but overly small steps slow convergence.
In practice, the three hyperparameters must be co-tuned carefully. The Huber parameter can be set following the procedure described in Algorithm 2 which builds on established methods in the Huber loss literature [Holland and Welsch 1977]. The privacy budget is usually determined by application-speeifie requirements, but, whenever possible, relaxing the budget (choosing larger e) reduces the amount noise added and thereby improves utility. In the absence of theory- -uoidd tuning, recommend grid search over (Yu, () for the step size a validation set, consistent with practical and widely used approaches in optimization [Ge et al. 2019 Attia and Koren 2025).
Additional experimental results
F.1
Experiment details
We generate i.idd samples from the model = fx() + e. We consider two examples of true functions f* as follows:
Case 1: ff(x) sin(3rx//2,,
Case 2: fz 310,((x) + 1 f5,10(z),
3
where Bp.q 2 (1-))-- with g(p.q) ((p)
T(++ę) denoting the beta function and I is the gamma function with (p)) p! for E N4, and vh.. denotes the density function of N (a, 6²). The first case is simple, and the second case is designed to mimic complex
B(p.a)
function. The noise two cases: t(3) representing heavy-tailed noise, and N 0.25) representing the regular situation.
In simulation, we use the RKHS with the Gaussian kernel K(x, v) exp {-(x ( y)² (2h/)) and f(w))(w)) du, where f(w) = Jg. f(x)e iuz dx, and k(w)
the inner product: for any f.g E Hk. (f.g) 5
(w) v exp( /22}
We conduct all three methods under both constant and non-constant step-size schemes. For constant step size setting, we use fixed step size of the form m with total sample sizes where the total sample size; for the non-constant setting, the step size is set as 7 = voi - for the i-th iteration.
27

---

50.00: 121 SMOT DOPNCESSEER
Nolr:: 231 Shop: toRvesretrr
Nott:: Gauselas Seap: sencerratttettt
0.890
0.938
0.833
9.5
6011
6.68
Rad
-10
-1.
6.42
-1.
0.890
2000
5666
19300
-20
640
0.23
0.54
6.75
1.30
6.00
2390
5900
10400
0.90
135
0.50
035
1,30
2.0
6.007
0.033
0.830
Ratied
0.038
0.090
2009
5ece
19000
6.00
0.25
9.50
6:75
5.30
6.000
2090
5900
10080
0.30
4.25
0.50
8:35
1.50
Figure 5: Box-plots and function fitting plots for Case I (top panels) and Case 2 (bottom panels) with the non-constant step size scheme in Example 5.1
F.2 Additional main results
As shown in Figure 5, when the error distribution exhibits heavy tails such as the ((3) distribution, our H-FSGD algorithm also delivers markedly improved robustness compared the standard least- squares-based FSGD under the non-constant step size scheme. The advantage is most pronounced small sample sizes. In the case of Gaussian noise, H-FSGD maintains superior or competitive accuracy relative to benchmark methods. Furthermore, all methods exhibit decreasing MSEs with growing sample size, and they convergence to nearly ideal function approximations by 10000.
Nelber 183, Orig: nor conntent
Netsed 1055 Step: nore commteet
Molos: Gasssien Step: noe- coe-coratort
Molee: Gassnien Step: F-P--------0 con-cerettrrt
Catiraatin
0.175
0.180
1.4
6.15
0.100
6.10
0.00
+1.0
665
-1.
6.00
3.59
3.5
6000
10000
49900
6.0
Naber 150, Sag mendent
Noher (S,, Sey: 19s
Mekur Banodan Mays oen cummier
Meki:: Barmies Stop zoe cermiot
Dxtimatiss
6.40
30
3.0
6.69
0.2
620
9.5
654
0.5
604
6.00
10000
20098
45900
6.00
6.28
0.50
0.54
1.00
10000
20090
49300
6.00
6.26
3.59
Figure 6: Box-plots and function fitting plots for Case 1 (top panels) and Case 2 (bottom panels) with the non-constant step size scheme in Example
similar patterns to Figure 3 Two LDP estimators exhibit increasing estimation error as the level of privacy protection intensifies, which illustrates the classic tension between privacy and utility. Nonetheless, all estimators, including those under stringent LDP, are still capable of capturing the underlying functional form. As sample size grows, the performance gap between private and non-private methods narrows significantly. This trend underscores how larger datasets mechanisms estimation accuracy.
Rigure/ddemonseee
can mitigate the negative impact of
F.3 Sensitivity of step sizes
We have conducted additional simulation studies to examine the sensitivity of estimation performance with respect to different values of step size. We examine the H-FSGD performance under Case 1 for both constant and non-constant step size settings, with 7o E [4, 24) and Ç E [0.3, 0.8). Figure illustrates the heatmaps of average MSEs over 50 repetitions when the sample size is 10000.
28

---

Heatmap of MSE using H-FS GD with constart step sire
Heatmap of MSE using HDFSGD with non-constant step site
Figure 7: Sensitivity analysis of the step-size parameters 7o and Results under the constant step-size scheme are presented in the left panel, whereas those under the non-constant step-size scheme are shown in the right panel.
Figure indicates that the proposed estimators exhibit robustness to the choice of "/o and under both constant and non-constant step size settings, with wide parameter regions yielding stable and comparable MSEs.
F,4 Performance beyond theoretical assumptions
While our theoretical analysis requires finite-variance noise condition, we also conduct experiments with heavier-tailed noise, including Student-t(2.5) and Cauchy(O, 1) noises. Tables 5 and 6 show MSE (x 10-3) means and standard deviations over 200 repetitions for n 10000, 20000, and 40000, under both constant and non-constant step sizes.
Table 5: MSE (x10-3 with standard deviations in parentheses (x (x10-3), computed over 200 repeti- tions under f(2.5) noise.
Step size
Constant
Non-constant
"
10000
20000
40000
10000
20000
40000
H-FSGD
2.15
1.25
0.669
2.26 (1.06)
1.41
0.907
(0.758)
(0.415)
(0.214)
(0.682)
(0.467)
L2-FSGD
3.97 (2.25)
2.04 (1.20)
1.11
6.13 (4.40)
3.38 (2.89)
2.02 (1.71)
(0.551)
Offline
4.21 (2.17)
2.17 (1.26)
1.16
6.75 (5.49)
3.65 (3.25)
2.12 (1.85)
(0.569)
Our experimental results demonstrate that H-PSGD maintains superior robustness compared to both L2-FSGD and offline methods, even when handling ddinite-varianee distributions that fall outside current theoretical framework. While formal guarantees for these extreme remain to be established, the observed empirical performance strongly motivates future theoretical investigation of such challenging scenarios.
F.5
Robustness in contamination models
While our method is designed for heavy-tailed noise via the Huber loss, we also assess its robustness under Huber's e* -contamination model, where an e*-fraction of data adversarially corrupted. Using Case (true model) and Case 2 (contaminated model), we simulate performance across varying e*. Table reports the mean and standard deviation of the MSE (x10) (x10-2) over 50 repetitions for both constant and non-constant step sizes at 10000.
29

---

Table MSE (x10- 3) with standard deviations in parentheses (x10-3), computed over 200 repeti- tions under Cauchy(0, 1) noise.
Step size
Constant
Non-constant
10000
20000
40000
10000
20000
40000
H-FSGD
3.64 (1.57)
1.97
1 (0.435)
5.22 (3.25)
2.98 (1.81)
1.65 (1.03)
(0.816)
L2-FSGD
5.83e+07
1.89e+07
5.7e+06
2.24e+08
1.01e+08
4.36e+07
(8.2c+08)
(2.65e+08)
(7.89c+07)
(3.17e+09)
(1.42e+09)
(6.15e+08)
Offline
1.73e+08
4.86c+07
1.33e+07
3.67c+08
1.38c+08
5.32c+07
(2.45e+09)
(6.85c+08)
(1.86e+08)
(5.19c+09)
(1.95++09)
(7.51c+08)
Table 7: Performance comparison under different contamination levels.
Step size
0.1
0.2
0.3
0.4
H-FSG
0.0722
0.657
2.85
8.08
20.4
Constant
(0.0158)
(0.0985)
(0.251)
(0.497)
(1.27)
L2-FSGD
0,0619
2.46
9.49
21.2
37.4
(0.0150)
(0.263)
(0.611)
(0.928)
(1.16)
H-FSGD
0.0939
0.683
2.89
8.11
20.2
Non-constant
(0.0326)
(0.105)
(0.260)
(0.517)
(1.23)
L2-FSGD
0.152
2.55
9.63
21.3
37.5
(0.136)
(0.310)
(0.683)
(1.01)
(1.23)
Step size
0.5
0.6
0.7
0.8
0.9
H-FSGD
56.7
114 (3.47)
155 (2.49)
186 (2.21)
211 (2.10)
Constant
(3.91)
L2-FSGD
58.4
84 (1.70)
114 (1.74) 149 (2.15) 189 (2.14)
(1.60)
H-FSGD
56.4
114 (3.78)
155 (2.61) 186 (2.32) 211 (2.16)
Non-constant
(4.23)
L2-FSGD
58.5
84.2
114 (1.94) 149 (2.25) 189 (2.18)
(1.64)
(1.83)
30

---

As shown in Table 7 H-FSGD remains stable up to E* = 0.3, with degradation beginning around 0.4, suggesting breakdown point near 40%. contrast, L2-FSGD deteriorates earlier at = 0.3. Across all settings, H-FSGD consistently outperforms L.2FSGG.
G
Applications
Many real-world applications simultaneously require privacy protection, robustness heavy-tailed noise, and nonparametric modeling. Examples include:
Healthcare analytics. Wearable fitness data (e.g.. heart rate, sleep patterns) demands LDP since raw physiological signals can re-identify users; exhibits heavy-tailed noise due irregular activities (e.g., sudden spikes in heart rate during exercise sensor artifacts); and necessitates nonparametric regression because the relationship between metrics (e.g., sleep duration vs. recovery rate) is often nonlinear and complex.
Financial fraud detection. Transaction histories require LDP when shared due to their identifiable nature, legitimate spending patterss contaminated by fraudulent outliers create heavy-tailed distri- butions, and the adversarial nature of fraud evolution necessitates nonparametric methods to detect novel attack patterns beyond rigid rule-based systems.
Consumer behavior analysis. Browsing logs need LDP protection against profiling, purchase amounts exhibit heavy-tailed distributions dominated by rare large orders, and market segmentation reveals irregular price elasticity patterns that nonparametric models can adequately capture.
To better validate our method's practical utility, we conducted experiments the real data "Health and fitness dataset" from Kaggle website Our goal is to investigate how endurance levels affect overall fitness. We select 40000 samples the training set and 1000 samples as the test set. We compared our H-FSGD and PH-FSGD methods with baseline methods on -tamplll-mppe R² performance, as displayed in Table g
Table 8: Out-of-sample R2 of proposed and baseline methods.
Step size
H-FSGD
L2-FSGD
Offline
(2.0.2)-LDP
(3,0.1)-LDP
Im
Constant
0.622
0.617
0.609
0.589
0.609
0.581
Non-constant 0.623
0.618
0.609
0.526
0.596
0.581
The results show that H-FSGD consistently outperforms L2-FSGD and Offline methods, showing strong robustness. All non-private nonparametric methods outperform linear regression (lm) in capturing complex relationships. Under LDP, PH-FSGD remains competitive, matching or exceeding Im, confirming its effectiveness under privacy constraints. These findings validate our method's ability to model nonlinear patterns while preserving privacy.
H Discussions
H.1 Computational complexity
Our theoretical analysis is conducted directly in the RKHS, where finite-sample bounds depend on the kernel eigenvalue decay rate rather than the grid size J. The grid size J primarily influences computational costs, reflecting the inherent tradeoff between accuracy and efficiency.
In the univariate setting, the computational complexity remains tractable: constructing the covariance matrix and performing Cholesky decomposition require ((Ja) setup time, while n functional SGD iterations incur an additional O(n.²) cost with O(J²) storage. However, we fully acknowledge that the situation changes drastically in the multivariate case. A d-dimensional problem would demand (J3dd) setup time, (nn,22d) 2d) operations, and (]2d) storage, rendering naive grid-based approaches impractical for 2
To mitigate this curse of dimensionality, additive kemel methods [Raskutti et al. 2012 provide
scalable alternative. By decomposing the problem dimension-wiss the computational costs
witness-datasese
31

---

reduced to Od + nd.J)) with storage O(dJ²), thereby preserving theoretical guarantees while ensuring practical feasibility.
H.2 Minibatching integration
Our framework can be easily extended to support minibatching. Specifically, at iteration n, if mini-batch {(Xnt, Yut) ) with size B, is available, the update rule becomes:
Bn
fn fn-1 nh B t=1
Σ
(Ynt
1i-,,KKnlll (fn-1, Kxnizt) (Knt 1,,,,fnn,, KxmihH) Kxar + YnSn.
Jn
fn.
where En is the sample path of a Gaussian process having mean zero and covariance function 87 13 log/2/6..) K with (En, 6n) being the privacy budget at the n-th iteration. The noise term &n 2g
still suffices to ensure DP, as the modified Fréchet gradient has same sensitivity and the privacy mechanism remains applicable in this case. Moreover, the theoretical analysis can be readily modified by replacing the ainle-sample gradient with its minibatch-averagee counterpart. Minibatching may in fact help improve the privacy-utilit, trade-off by reducing gradient variance, allowing for smaller noise magnitudes under the same privacy budget; however, it also requires a trusted data collector to aggregate and access the mini-batch data.
H.3 Extension to non-i..d. data
Addressing concept drift and non-i.i.d. data both important and challenging. Our current framework, like standard functional SGD theory, assumes i.i.d. data, and does not directly extend to non-i.i.d. settings, which is a limitation shared by many SGD-based methods. challenges include parameter drift, slower convergence (Zhao et al. 2018 Li et al. 2020), and bias from dependent observations. While one could define the population risk as
Σ (Y, (X,.)
with distribution weight this is infeasible in online settings due to unknown distribution shifts and the ill-defined infinite-sum objective. A more practical alternative models the data coming from M sub-populations with different distributions, minimizing the global risk
M
Pm ( ( f(x(m))).
m==1
This leads parallel SGD scheme: each round the global estimate ft is sent to local devices, which compute updates
1Z (f)) y(ml) 7eE:
followed by weighted aggregation
Σ m=1
f(m)) PmJt+1
This setup accommodates distributional heterogeneity and aligns with recent federated learning approaches for non-i.i.d data [Chen et al., 2020 Ma et al. 2022
I Limitations
The first limitation of this work lies in its exclusive focus on the Gaussian mechanism for implementing LDP, without exploring alternative mechanisms such as the exponential mechanism [Awan al.)
2019 or the Laplace mechanism Lin and Reimher 2024 While the Gaussian mechanism provides
32

---

desirable analytical properties and facilitates rigorous theoretical analysis, this choice may reduce the flexibility of our framework in settings where other mechanisms are better suited. We acknowledge this constraint; however, to the best of our knowledge, our work is the first to adapt the Gaussian mechanism into online nonparametric regression under IDP, providing novel and theoretically estimation in streaming environments. The second limitation
grounded approach to concerns the scope of our loss function, which is restricted to the Huber loss rather than a broader class of M-estimators, This modeling decision is primarily driven by two technical challenges: (i) quantifying sensitivity for general M-estimators under LDP nontrivial, and (ii) most M-estimators lack closed-fome update rules, posing significant challenges for theoretical convergence analysis in online learning frameworks. Future research may address these limitations by extending the proposed framework incorporate alternative privacy mechanisms and more general robust loss functions.
J Technical proofs
J.1 Proof of Equation
By the definition of the Huber loss
the estimator of the Fréchet gradient is
VL, - (y - ((x)) Kas
Iy - (--((x)) ST - >
T .ignsyg sign(y- f(x))K,
= =- [1 - ((y) f(x) ST + sign(y f(x))/ fly- f(x) > +T] K₂
(u {xx))
where K2(-) = K(r, -) and e, (u) == ut {|u| + sign(u) {/u| > r). Note that (,(w) =
uw-(u) (w) with w. (u) = min ( 1//// then
(I, - w f(=)(( f(x)K
J.2 Proof of outlier robustness
Outlier robustness in statistics and machine learning is typically characterized by the influence function (Hampel et al. 1986 Avella-Medinal 2021]. which we formally define below.
Definition 4 (Robust statisties). Let F be a space of probability distributions on X' R, and let T & + G be functional mapping each F E I to function T(F) fp E G. For any
contamination point = (x',y') .y')))) E 2, define the contaminated distribution F = (1 - c) + eAz, where Ag is the point mass at and E (0, 1). Then the influence function Tf at under F is the given pointwise by
function [F(2; T, F)
IF(2; := lim (FF))z)-T(F)G)
lim
c--
-++
the influence function is uniformly bounded, then the statistics T(F) are considered robust, as no single outlier can have disproportionate effect on the estimator.
We now rigorously show that the Huber loss yields estimator with uniformly bounded influence
function in the nonparametric setting. Consider the nonparametric regression model Y f(X) + and the estimator f arg min, Ex [L. - ((X)), where the Huber loss is
2
|u| S T
(u)
r/u| 2
|u| > T,
u, { sigu(u),
|u| E T, and vi
[1, |u| < T,
with di (u) L.
du bh (u)
[u] > T Define the functional Tu, on the joint distribution F of (X, by T (F) J (xo), where fF(+) satisfics the population estimating equation
10, [u] TT,
T za (t: F) = f VT(U t) Fo (dy) = 0.
33

---

Let contaminated distribution be F. = (1 c) + (orr)))) where (at,o) is a point mass at (a', y²). The influence function at (a'; y²) is defined by
Tzo (Fe) TTo
(F((1', Tap F)
lim c-0
Since Varo (Tag (Fe); F.) = 0, by differentiating with respect to at 0 (implicit function theorem), we obtain
0
Tzu (FT) + Mas (fr(xo); = o(e). (Tzo(Fe)
Ōt
Noting 09 88
- S Vy fy( (dy), and Uao Fe))
Evi
(=(=o) we solve get
wr ff(10)) (P10 TF((a', : F) ( fr((z)) Fy (y (dy)
Note that 1/4 (r()))) S r, (m)==))) S and ((xo) == ( (dy F(]Y [x(0))] < X mn). Under the usual assumption that the conditional density of r = Y - f(X) is continuous and strictly positive at zero, there exists universal constant > 0 such that (zzo) 2 for all zo. Hence, for all contamination points (a', 3 and all 20.
IF((''s .ore..))) Tz, P)
which does not depend on (a',y), y"), proving that the influence function uniformly bounded, This establishes that our estimator based the Huber loss is provably robust outliers.
J.3 Proof of Theorem
1
Fixing fa-1, the Fréchet gradient iterating fn is
(N Yn) = (Yn - -nn-i(X)))))))
View as an operator such that g(x, y) = - l - (y- (n)) Kg. By Assumption 2 and the definition of (-(,,, we have
11 v) - g(x', //)ll S BT (=_.)),''=(''>>)
sup
Applying Proposition D with single sample = {(X,, Y,)), }, E, is taken as the sample path of
Gaussian process having mean zero and covariance function 8, Bd log(2/6m)) K, then the next iterate
=
Ja (En, DDD. Utilizing the parallel composition property of LDP stated in Proposition 2 (1), we observe that releasing each update based on disjoint subsets of the data does not amplify the overall privacy loss. Consequently, for any E N, both the estimator fr and its averaged counterpart f.. inherit (maxigisn ( maxigis (5, LDDP from each individual update.
J.4 Proof Theorem
Lemma I and the following Lemmas are usefull to prove Theorem
Proof of Lemmal 7 then
Recall that (s) min(1, [ )- Assumptions
2 and 4 imply that || & BM,
11o + BM + leul, it follows that w- (Yn - f(X,)) 2 min |e. }. Utilizing Assumption we have
Yn f(Xw)l < ll + 1l + le < Ilf
Ty > E
min
T
E(Kx, , & Kx.))
BM + || [enl
> 2m
1,
= cZ.
m + BM + ||
34

---

Let an = -n-11 an-1 + 7 T--1 satisfies Tn-1 E with 7 z I, where < denotes the order between self-adjoint operators. En E H. Fn measurable for a sequence of increasing o-fields (Fn).. | FFn-1) is finite, and E( @ = o o Then
Lemma 2.
Bi Eān) 1xx - Bias(n, 7, 2, 7, (T))i, 0o) + Var(n, 2, (7:) k3)
where Onn = Eij=1 On an
Bias(n,7, 7, (T) E
1//
TT-
i=1
and
Var(n, 2,, (5)
1 B
1/2
II (-
n²
Proof of Lemma 2
By the recursion of Cn, we have
n
TT-1) + ΣΣ II
(1-
On
n
Then
Bl
E|
11x
2 2 E
1//
ΣI [1 (1- (T-1))
2
E
Σ1/2
Il (1-
n
n
j=
=1klli=k1
=: BBaas(n, 7, (Ti);, on) + Var(n, 7, (Ti),, (3))
Lemma 3. Under Assumptions 5 for any r 2 0 and any n 2 E(E,, @ EE)
< <
and E miisse In poise.r)
& c (r+1))r+ B
where 7² o² 87 B² 1og(2/8)
and defined
as in Lemma
Proof of Lemma We make an induction on For r 0, using Cauchy- Schwarz inequality and Assumption
we have
E
E [Yn fx((x))) 2
Kx X Kx,
+ E(En @ En) 87 B² 1og(2/8)
E( LKXx (xx))
K
8 B² log(2) (2/()
2
E
where /2 = 0²
8² log(2/6)
The recursion formula of noniss, implies that
6²
0 0
Σ II -
Rm 1=nk1
Then
n Σ II (I - (T) o E II (I- (T-)
E
1n
0
& The
noise,
T II (I-
Σ k=li=
II (I (T- i=b+1
35

---

Utilizing Lemma 1 we have Tx - cE for any then
II (1- II 1m
(1--)--1)-
II (1- ēmk+1
(1 = II (1-
imk
R+1
It follows that
T II (I (T-1) $2 Σ II (I (T-1)=
n
Σ II (T-
i=b+1
k= 1=1k+
II (1 - TT-
II (1 - 7T-1)
X &C
k=
L+=++1
==k
Then
E Un
noise.0 0
0)
Assume that for any 2 0, B c-(++1)r+1
=M of -p B OZE, and E (177 (yieeise.r @ Mm moiise,))
Ba We now consider E(E, & 1 and E (1noeeserr+ @ mp 1)) Recall that E =
- - - fn-1 (Xx)) Kx, @ Kx,) n
poise." By induction and Assumption
B(E,+1 @ ) x c ( +2 J²E
[n-1- -n-Yn--nn(X.))366 2 @Xx.) )
Fn-1
x c (r+1) +2 82 (Kx, 8 &Xx,)²)
$ c ( +1 b2(++1)022
follows that
E(m E(nnoiee noise,
@ T/ 1)
x (1+1)
II (1- II (1 (1- (T-1) i=k+1
x B2r+1101
Lemma 4. Assume that (Xa, fn.3%) E XX F, measurable for sequence of increas-
Fn1)) ing o-fields {Fu)a. Further, ((2g)Fn-1)) = 0, E( (_ < 0c, and [[][xx, x,, 12 Kxx Ø Kx. Kx,(Fn-1) & B with E(Kx, @ (x.(F = for all n 1, some constant B > 0 and
invertible operator E. Let On = (1 (1- - fn-1 (X @ Kx_ an-1 + 75 with
ag = 0 and -e- << 1. Then
B6 E, 10n-1)133 I c(1 7c- B2)
B
1=1
Proof of Lemma
The recursion formula implies that
|anlli; px
$ 1||an- l2,z, + + [Yn - fn-1(Xx)) @ an-
+ +2>2||E
+ +2 -+ (Yn fr- & Kx Kx,
Taking expectations on both sides and utilizing Lemma]
we have
B(I|an 12 x
(Fn-1)
< |an 11:33
+ 2 2 (Kx, @ Kx (kx))an1llf I12 + + - -2n-an-IITT--aam--- 1n
< ||n--1
[12
+ 2 (an [[|| K x. 1| K x, @ K )onn 13, + 2 li: - 227/0an E, 1) 13
|| 112
+ 2- 2 E E R230 20 - yc- B² "B2 (an-1, Ean-1)
36

---

Taking another expectation on both sides, we obtain that
B(an-1, Ean-1) 2c7(1 - y0 B²) E (1an-1113,,
Ianlli;
+ +27"11%%
By convexity and op 0, we have
1 (0n--,,)nnn)aa 5 c(1 - 70 132
2
B k 1P
Rmm
Lemma 5. Consider On = (1- (Yn (n- (xx) an-1 with ao -- If
F > 1/2, then
E( Land so (1 (2r (mm) (on)--211 |
Proof of Lemma 5
The proof is similar that of Lemma 13 in Dieuleveut and Bach 20166] The
recursion implies that
On M (n, i + 1)at
[Ts= (1 -V-- @xx,)
for any i 0, ,...,,,n. where M (
Note that
n Ban, Σān) = E
Σ
(as Ea;) + 2E
Σ
Eaz).
1=0
1=0 f=++1
For the second term, by Lemma
E
(a, Eay) I E
Σ
E(, c723))1aa))
1=0
j=i+1
j=it1
I
E
(ais [c 1 ((1 (1--y)) m)-) (1 -yyE)m--t)t A nE(( - -cyE)] as)
1=0
$ E
(a;; An E Σ (a,,
Ea;),
1=0
1=0
where A & (c 1
I A nZ
=: A. Define the operator T from symmetric matrices to symmetric
matrices
TA eEA + CAE - [xx, @ AKx, & Kx.]
Then for any symmetric matrix A,
E M (M(i,1)) AM &
> (I TT)
1=
i=0
Similar to the proof of Lemma in Dieuleveut and Bach
2016), for r > 1/2, we have
TT 1 0 (nal+n\laglaa) 2r-1
Σ
TT
n 3-22r1121
1=0
and then
(a,, Aai) 50 (11+tttt)/))))))) 20-1 q 2 2 3-1p50001? ro013
RF
Thus,
B(ān, Ean) 20(11+0400))2-11 (2) (1--)) (mm) -2 -- -|5-- -|x--(x((??)
37

---

Lemma 6. Suppose Assumptions 2
4
hold. Define
(i 7, T,, (T))..
E
1//2 -T- SH
-
n²
j=1 i=1
1 S r 1, then
7, fn) (xm)
-2r | fx
I > 1, then
"i (Ti)i, fH) S 2c 2" n2 2r - 1 fx11
Proof of Lemma 6
The proof is similar to that of Lemma 4 in Dieuleveut and Bach [016]. Utilizing
Lemma
Bias(n, 7, E, (Ti)e, JH) S
///
(T-c) SH
(7 -
n²
j=1 t1
E
2
2
n-1
Σ (T Ey E Σ
$
n²
2
2r
277-22 2r
Σ (1 2 (cy21)"
113
2 2r
(1 (1- x) x²
| fH 1
112
c
sup
0Sa51
I Sr 1, then suPogasi Eny (1 x))² x²) S n -r it follows that
Bias n, 7, E, (Ti) SHt 2c 2 (ym) || SH 11
If > then supoçasi EEj (1 -1 x)' x" } 1, it follows that
2r 1 (T),, fx) < 2c 22n 222-22
Lemma 7. Under Assumptions 2 4
have for 2 0,
Var(n, 7, (T)h, (E)).) E 1/2
2
ΣΣ
n
j
II (1-
n
Tor2c 272
[co(a)(o))
111/a -11t//
where co(a) [a+1)[a-1]
4
38

---

Proof of Lemma 7
Utilizing Lemmas 1 and 3
we have
Var(n, 7, E,
S
2
B
E1/2
(1 (1- 75%
n
J R=1
2
B tr Σ 11 CyE)i=k
Σ
Σ
11 - インン
3 2 E
n k=1
j=h
2
2
a
6 B2
7-
Σ (1 - c7
Σ
n2
k=1
j=k
2c 2
=c =c
B
I (I - cy o
2
Note that
S <1+ 1,- 1111-yu-ay du
[I (I- (1-)))
( (112))//
[1- (1 -1-1-99 -1-1oyu--93 du 1ro
=1+ /
Jeons3in [1-
cyu (1-(1-cyu-pp1 du
+ 2a 1 ) (075)1/a
$ 1 +
then
V,r(n,,,,21 ( (E] S
1//2
(1 c2 73%
n²
j=1k=1
-2
" S " B2n
+
1+
(cy(n - + 111)
nt
2a
40²
S c 2
12 1111a - n-
(a 1)(2a
Following Lemmas
17 we give the proof of Theorem
Proof of Theorem 2 The recursion
is equivalent to
fn. = 11---1110 -I- - fn-1(X,)) Kx. & Kx.) fn-1 + VYnu+ - -x))(XX)) +
Denote Kx, @ Kx,, as the a.s. extension of Kx 60 Kx H + H to T-2x + H. such that Kx. @ Kx (f) = f(Xn)Kx,. and it will be denoted as Kx, @ Kx, for simplicity without confusion. Let T/ = fn Sn. and E, = (Y, - (x((X))),,Y, ( KX,, + + We obtain that 17u = - SH, and
Th (1 -1- - fx @ (x.) mn-1 7E..
(9)
We decompose the recursion formula (9) into two simpler recursions yinit and noiee such that 7), noise Specifically, the initial component {1) init In is defined as 176m =-H and
q/ + nh.
iiit (1 1--ywxC
(Yn, - (I-
Ix.) @ Kx.) n
init
and the noise component {npoise }n satisfies 1/ nivie 0, and
noise
(1 yw, -1-,w,,Y, - (xn-1(X,)) 8 Kx.) m + 7
39

---

By Minkowski's inequality,
E 17 13
)
1/2
E
1/2
+
[
1 1.x
(10)
where 7/1 = Σラ=1 T//n, m tively present the upper bounds of Bl "1l
Σラ=
75
/n, and th
n/ /n. Next, we will respec-
1 1 and 1/
1.7xx
Noise component.
Denote Tn- E
WT (Yn - IX-)(X 3x.
Define the
main recursion of poise
Ma noise,0 = (1 - -TT--1) noise,00 + 3Bx,, with 170
noise.U 0.
Then the residual term is
poise Vn
noise.. 1/2
700 (Yn (X-1(Xn))KKs @ Kx.) ) (naobe
7n-1
noise,0)
+, with noise -1o
noise,0
0,
where E = (Tn-1 - (Yn - ( @ Kx,)
Mn-1"
For any 2 0, we further define
a sequence (1/hoise,r In as follows:
misser (1 (1-1)))1) 1n-1 + 7 with roo
noise,r
noise,
Un
where
=0
En, and B/ = (Tn-1 w+ (Yn - fn-1(Xxn) @ Kx.)
Mn-1
noise.r-1
for r 2 1. Then
7
maise
= 170
noise, O. and
7n
poise
paise, In
I - ywo - (Xnn @ Kx.)
7n-1
Σ
nn-1
nolse,
+ +
1=
Minkowski's 's inequality implies that
1/2
1/2
1/2
E|
E|
1122
1.
+
E
Im
nn
boise,
1.
where vinoise,
=j= f2
noise, /n_ To obtain the upper bound of [2l117p0iss,
L.
we first verify the
px
conditions in Lemma
The definition of w-(()) implies that Tn Σ for any n. For i = 0,
[X. (x,)))) - -n--
E. 11 Fn-1
E
s E
1(Y - fx(XX,)) 11? Fn-1 E([lEn 12) < co.
For i 2 1,
= [1 wr - -
(x.)) 8 Kx.)
mn-1
noise,
|1?
F
= E [| (Yn fx-1(Xn))Xx, @ Kx_ 12 [n-1)) - -n
noise.
$ [Kxx @ Kx 1x)
noise.r-1 1n-1
2
< oc.
By Lemma 3 for any r 2 0 and any n 2 O. BE & Bn) x tt B2rgg 2 Utilizing Lemma 2 with
0g 0 and a2 m b we have
E B
paise, i
1
< Var(n, 7, E, (Tib, (3)h)
(11)
For the residual term noice yc B² 1, then
En m/ naise, it is easy to verify the conditions in Lemma 4 If
E
T/e
noise
Σ
Tn
Σ
poise
Σ
In
c(1 70
B
B
k
1127
1=0
1=0
Lixx
40

---

Utilizing Lemma
3
Σ
EE
L
tr
(
-
s ne ( B2 (2))))))
A= 1
k=
Then,
E Amiise
1 7c 1 B2 petprrttgrttttteo 32
(12)
Combining
[2). and Lemma]
we have
1/2
E (ioiis
12 L2x
1/2
Var(n, 7: (Tibi, (Eib)) 1/2 +
(r+2) 222 t2
yc- 1yc-1B B2
1=0
$ 2c 222
(ola)(c))\/nn11t1)
+-
1/2
Σ by
c-c ly 22r
1/2
26
(1o(a)(o))//)
1/2
-1/2+11/(20)
+ n -1/2
(r+2) +2 22
1/2
1
(c- B22
+
c B
where
co(ar)
4o²
Let the recursion step - 0o, if 1y22 < then we have
[a+1](20-])
[Bl 1/2
1/2
Vā '0 1 (c- B2211/2 (Co(a)(e)))1))) 1/2 11/2+11((2) + +n -1/2 (13)
(1 (1- (1- (Yn - fn-1(X @ [xx)) n with
Initial component.
Recall that r
vi -fn- Define the main recursion as
init, - (T-) 17-1
init,0
with init.0 = -fx Then the residual term is
jnit
0nit,0
(I (1- (1-,,,(n - - xKx))
(11111 w/--1) + +,
In
Tn
with vigit
7o
init. O, where =imit
(Tn-1-w- w- - fn-1(Xn)) @0 Kx.)
init. 1n-1-
Utilizing
Lemmas
andd 4 we have
E
Em initt
L2px
I Bias(n, E, (T)...
and
E(pi init, Σ iiit
Th
1)
I c(1
1
7
B
Sini 2
70-1
132)
n
k=1
where
Bias(n, 7, (T
E
1// -T--TT(-1) 1H
n1
j=
57
Note that
inic lige P
(T-1) (Th-1 - -wr(Yr - Kx @ Kx. 2 II TT-1)fm
E
fn. II
[I -
i=1
12xx
Ilu-nTTi))
< B²E
ESh
[=
Lixx
41

---

By Lemma
for any r, if x <
with C (0, then cy < 1, it follows that
B
2
init
E
SH:
7T-11
Elh
Px
k=
k=1
i=l
Lix
B
n
fH
(1- - o32)) 2iHH
11
k=1
L3xx
1/2
7B2
Σ
(1 - 23
-- IH
11
Lk=1
L
B
-B 22
(I (I--)))) (oy2))2 (0)))))
| fxe 1ellii
n
B
n Σ
c
2r
2r
sup
(1 - )2) 2r 2r
| fm fulli1
n
05551
k=1
Ifr < 1/2, then suPogag1 and Bach 2016). Then
E Ek=1(1
2222 S n 1222r, whose proof can be found in Dieuleveut
30((m)-3) | fx (1(imx) )
- 11
Thus, for 1/2
1/2
E Ellstain xxxx
Bias(n, 7. E, (T). 1/2 +0 (00T(1--Hlles
By Lemma 6 0 S S 1/2, then
)²² 0 (0m)~T|E=~1 || Fulle
1/2
init 2 Bl x
(14)
When 1/2, utilizing Lemmas 5 and 6
we have
1/2
(1+ (1+2 1/a (2r (2r--11/)) 7 -- minfmiiff11 1aanfr/2)||111 || fn (xllle1
1/2
E| E
1 1
1xx111x))
(15)
To put
14 and g(L+a)(2 /an (2r 12r-11/ 11 for r > 1/2. Then
15
together, denote n( = for r S 1/2, and 4(7, n))
1/2 0 (1+ ((r, n minfr.11 || (rffill1zz (16)
2 1/
Combining 10).
and
16)
we obtain that
1/2
V2c- 10
(cala))oo)//a) 1/2 n -1/2+11/(20) n -1/2
E
12
<
(c 1yB2)1/2
+ +0
122 (r.) 3 Ff (2)
Thus,
Fn fulli,, so 182 (12/an-111)) +n + (1 + {(7, -2n -2m -2nn-2min(r.)) 2miin(r:1) 1 1 Lix
42

---

J.5 Proof of Theorem
The proof idea of Theorem B similar that of Theorem We begin by presenting several useful lemmas that will be useful in proving the main theorem. For brevity, we omit proofs that are analogous to previously shown results. The proof of Theorem is given thereafter.
Let on (I - Ina Tn-1n an-1 + m Tn-1 satisfies Tn-1 & E with Vn x I. where & denotes the order between self-adjoint operators. En E H is Fn measurable for a sequence of increasing o-fields {Fn)m. B[[] (FF1)) finite, and E(Ea = $ og Then
Lemma 8.
Biān: Lān)
s Bias(n (wh. E, (Ti)i, + Var(n, (T))
where Ünn
E)== On
2 E
Bias(n, (ns)is E, (Ti)s,
1/2
EII 7T
n²
and
Var(n, (wiss En (Th,, (=))) (E),, = n²
1//
(1 -7-76 71-1)) mx
Lemma 9. Under Assumptions 2 for any 2 0 and any 2 0, BE =nh & c
and E. (ypolse. & spoise,r) < (r+1))g r+1 B2r 821, where 02 = 0² 8 R² (2g(2/8)
and e is defined
g²
as in L
Lemma 10. Assume that (X,, fn. =a) E H x H x is F, measurable for sequence of increas- ing o-fields {n- Further, B(Eū Fn-1) = 0, [|| < 0o, and E[||x,, 2 I',,, & K Kx Fn-1) & B with B(Kx, Kx Fn-1) = Σ for all n 1, some constant B > 0 and
invertible operator Σ. Les an = (I 1-,, (Yn - (Xx)))x @ (x_) an + 7, with
on = 0 and non-increasing (in)n satisfying c 10 B² < 1. Then
E(ān-1, Emn-
Ellaa 11
2cn(1 c 1o B2)
L3x
7h+1
k=
Proof of Lemma 10 Similar to the proof of Lemma
we obtain
20%a (1 c- (" Ean-1)
E
ax
1x
El
+2
If {7m) non-increasing, then
E(an-1: Ean- S By convexity and aq = 0, we have E(ān- 1, Eā
(Ellan-11 1,,
El 11 1.3xx E
+2
20 - (oB
1
1
S 2cn(1 - c- B2)
Bl Bllax 12
+
7x
||
11
7/
Yk++1
Lemma 11. Suppose Assumptions 2
4
7
hold. Take x i- with Ç E (0,1). Define
2
2 n
Bias(n, (xdi, E,, (Te),, fx)
E
1/2
II (T- - SH
Σ
43

---

1fr- - () S 0. then
(na ti E, (Ti)e, 20 =0 (n-2(()-)) || fHL l1:))
ifr ffr11(11- 5) > O, then
Bias(n, fwhh E, fu) S <0 fullit)
Proof of Lemma 17
The proof is similar to that of Lemma 6 Dieuleveut and Bach 20066] Utilizing
Lemma if 7
5 then
n i 1/2
2
Bias(n, tndis 2, (Tites fH) v
(1
c7,2) FH
n²
j=
Σ
J
2
Σ -
- Σ
|
112
1
I n²²
2
sup
-
(1- cxa) xt'
||Σ "
05051/(ew))
2
C sup
nar" A Ax 1=--1/0-00) fnn"
n2
05051
Ifr 1/(1 () S 0, then supogasi { {nx"" A Ax--1/10 1((-1() S 5n!-r(1-Q) so that
(ias(n, (7,) E, (Ti) (H) Con -2r(1-() () [
- () > O, then supusas1 { mxx A Ax" 1---1//// 1/(1 [1]{]]]]]]- 1, so that ifr 1fr-1
(nas(n, (7 E, (T:) (H) - Con 2 || fxll
Lemma 12. Under Assumptions 7 positive constants Css and C4 such that
take 74 x i with Ç (0, 1). we have r 2 there exist
Var(n, (ah E, (T)). (E.).)
2 n²
E
1/2
II (1 TT-))
C3e
B
(I
7a B2r (26+33
/
Proof of Lemma 12
The proof is similar to that of Lemma 7 in Dieuleveut and Bach 2016
Utilizing
Lemmas and 9 have
Var(n, (m), E, (T))
2
1/2
II (1-oxi)
n2
j=1 kiliii
2 n
j
ME
tr
Σ II
(1 (1-))
E
Σ II (1- joki
E 8 E
n
k=1
j=ki=k+1
<c 10
2
2
II
I (1 (w-)
E
1=1
j=ki=k+1
20
Σ II (1- a
<
a
1=1
j=k 1=
44

---

Take xx x. Utilizing 1 - I exp( (x), we have
n II (1- cgt c1- Σ expt-6 -d Σ 1t
Σ
j=kiskt1
5=
i=k+1
(j+ + 1)+ - (A: 1)
Σ exp j=
1- 5
n+1
ctt x (k ++)1)-
exp
de
1-5
k+1
I é" max
(1= 1)5..
Then
2
a
J (1-c)) 7
Var(n, 17))., E, (T)i (3 S
1/2
n1
20
n
x
(min(n- c. max f (k + 1)833)
kk
11
C
n
Se
7
min ((n - 2;)2, (2/(1-5)3
n
k=1
min {(n - k)2, 20 (k: + 1)2g
k=1
1=1
Utilizing the same arguments as Lemma 7 in Dieuleveut and Bach 2016], we have,
C" 7
Cin
if S 1/2
22 min((n - kn) (000011)) -
Cin(2act1-
if if 1/2
Also,
C"
20
min k)), fa +k+ 1) S (-
n1
Thus.
if0 <
Var(n, E, (3)) <
Cie B 3 (20511 2020//a <
Following Lemmas
1 12 give the proof of Theorem
Proof of Theorem
Denote Tme fn fM.. The recursion implies that
Th (1 Wn (Yn fX,) @ Kx.) 1--1 7n
(17)
where E, = (Yn SH )w-))w fn- (X.)) + We also decompose the recursion
formula [7p into the initial and noise components. Specifically, the initial component (1 mit
is
defined as 77mm
fH, and
jnit M/
= (T (V.
8 Kx.)
1
and the noise component {n Jn satisfies 1/ 0, and
anise
(1 wr (Yn - - 8 Kx.) m + Fn
The
45

---

By Minkowski's 's inequality,
1/2 )a²=
11px ) 1/2
(El 1| 3.
1/2
1
S
[2 1
+
(18)
where Th = Σj= ///n, Via
Σラ= 1/5tt /,, and Th
ΣEz nngiss/ /n. Next, we will respec-
tively present the upper bounds of BB(l1/1111 11 12 and IE| 17
12 1/7x"
Noise component.
Denote Tn- E (Yn
& Kx.1Fn-11 For any r 2
define a sequence (1 (1)moise.r), In as follows:
paise," (I - Tn-1) 11--1" + mm with r70
poise.r = 0,
In
where =p = E, and E = (Tn-1
(x) @ Kx.) 1n-1 muise,r- for r 2 1. Then
poise
noöse, 0, and
== 1/1
nn
poise
noise, In
[
Wr WYn -n- 2 @Kx.)
1h-1
noise
nn-1
noise,
+
1=
Minkowski's inequality implies that
1/2
1/2
1/2
E 1h
moise 2
n
$12
+
E
paise,
1=0
f=0
where 77 _hh B2r
En 12
/n_
By Lemma for any r 2 0 and any n 2 0, E(E, @ Ei) z
Utilizing Lemma 8 with ag
O and an 1/2 paise, we have
EE
moise. In
||2
Var(n, (ny)s, 2, (T))., (E)
(19)
For the residual term 7n and B
-E 0 Ih si we can utilize Lemma with at = paise
-i 1/% noise,
2 If {ran is non- non-increasing and satisfies e- %o B 1, then
E
noise
n I
Σ
noise In
mhois,, Th
1=0
1=0
Lix
n
1
< (cn c 10
El Bl P.
+
7
B 112
7kk
7k+1
k=1
Utilizing Lemma
9
12
set
(E( & ) nc
-nn--rrin (=22))g++22((++1
k=1
Take 74 x S, Note that ||a!'|| S ||ا
al + +
< Σ km 1
|| Then
1
1 カー
Blaklii
+
<
2d'
E Blaa 2
n
7
7h+11
71
iqi
n-
i
}
< 2c
Σ
7kk
B |1
iri
t=1
d(
<
nc - (x+1))))++ 222 1) 12(++)))p((()))) (rr())).
1
46

---

It follows that
E
Un
poise
==0
2x
cc
+ 2c 20 2
20(1 - c x0
nc
x Enc
(r+t)) 7+2 2
(20)
Combining 19
20
and Lemma
12
we have
B noise 12
Bllmm
(Vrr(n, fr.1,. (T)s, (E)b)) 1/2 + (+t
1/2
1/2 r
150 < 1/23 -an <1
Σ
BB
(c
1/2
+ Cnn200t1---22//0011111 < <1)
1- (3
1/2
+ (cnc-((+1)n 22(
Let the recursion step r + 0c, if
bB² < 1, then we have
C1/2g
(1 (000))2()2))
i
1/2
(c BB2)1/2
Bl 11 L
E| noise
<
(21)
C1/2g
if1/2<
Initial component.
The main recursion is
init,0
Ine Tn-1)
1n-1
0ni,0
with 1/o
init,0
SHH and the residual term is
init,0
(I In WY, - (X,)(X,)) (xx) (xx.)( (/2m1))) + Y, Eiit
Un
with witi
Tlo
0, where =init (Tn-1-wa - w (Yn - (x-1(Xn)) @ Kx.) min.0
Utilizing
Lemmas
8 and 10
we have
Eniii.. Enphi,. 13x
Bias(n, treti 2, (T) fH),
and
E(T
0 Σ init
1.
mi
1
init.0
1117x
+
1
+ 2
Σg
iini 12g BE
2cn(1 - c B2)
7k
7k+1
1=1
where
2
Bias(n, (xdri E,, E, (Te)e, fx)
2
E
1/2
II
(T
Tx SH
n
47

---

Note that
2
- ((Ti))
E E iii li
1x
S
B
fni,
Ifn
Lixx
By Lemma
for any r, we have
Ba
k -1-11877 (1
12
B.B
fH.
E1e
71
k=1
1=1
1ix
B
k on2))
Σ
-u-
|| 10-Mmlliz
A=l
lix
The proof of Theorem in Dieuleveut and Bach [2016] implics that, 2r
- < 0. then
(1- cx22)
22222
S <dnn(nm))-
17x
It follows that
BE x
(B(r) -2 - fH
n
k=
Denote On rini
7n
Lemma
10
implies that
B|las||2 < El a; 21 + B:
<
2n Σ
yyx B|
1=1
Taking ' S, we have
1
1
1
B Ba
Lix
+
s 26
B1|aa|11
7
7k++1
i
k=1
n-1
< c - 1c13
i(i7t) (0r4)-2r-11
-2 ||
frell27
11
n B2 ( -2r
(n7/a)
2r
Σ fH. 122 1,px
It follows that
E
init
0
112
0 (1%)) -2r
1 | 12xx
+ +
In (0 (m7))) (00m))2211200 1 Frx l1(eex
1o (1777)) 2r 1|2 1 0
L3
Thus.
[111711112 12 )u² < Bias(n, (whi, E, (Ti) fx) +0 (11 (17m) ">==feell 11x
1/2
Take 71 x 8- with < E (0, 1). By Lemma
11 if (1+ (/2)/(1 -() 0, then
1/2
Bl Bllniii inin Li
50
1/2((1))))))))))))))))))))))))
1|
1|0 2005SHll 112
(22)
if -1+ - > O, then
1/2
1 12
<
n 1--1|-1
20-"fxll Full 12
48

---

Note that 1/(2(1 ()) < (1+(/2//(1 for any E 1). Combining (8) (2
and 22 D).
take
Ç satisfying 2r --, (0, 1/2], then
(Bllvallig,
1/2 00 (0)111)-)))110) + +
(0 Tn
(107))))
Sanlllll )
ç E (1/2, 1), then
[Blmm 1ig
1/2 5o (000maattt----20/10a) + + 1/ (1 112-1=/l
Thus, taking { satisfying 2r - 1/(1 -() 5) < 0, we have
)- σ - -1+1/a + nom (10m)) 22 ||> f-rfxll 13xx )
if0 < <51//
BlI5n fullitx
(mm))) -2+1/a + 7/ (m)ma) -2r ---1 fH 2 1x
/f//2<<<1
49


Reviews:
[{"review_id": "MQx4TkyQc7", "reviewer": "Reviewer_euKv", "summary": "The title says it all: this paper proposes an online learning method for solving nonparametric regression problems under the constraint of local differential privacy (LDP). The algorithm is stochastic gradient descent (SGD) on the reproducing kernel Hilbert space (RKHS) $\\mathcal{H}$. The main contributions are:\n\n  * finite sample analysis (theoretical)\n  * optimizing convergence rates over the hyperparameters (theoretical)\n  * experiments (empirical)\n\nThere are two key aspects of the problem which motivates their solution concept:\n\n1. They do not assume the true regressor $f^* \\in \\mathcal{H}$ (i.e. the problem is misspecified).\n2. They want the method to have good empirical performance when the noise is heavy-tailed.\n\nThe main idea is to use the Huber loss to get some robustness against the heavier noise. This is a standard approach (as they point out themselves). The benefit of this loss is that the gradient becomes bounded, avoiding the clipping needed for DP-SGD for quadratic losses like in ridge regression.", "questions": "**Main Question 1: Does the convergence analysis really take into account heavy-tailed noise?**\n\n* In Section 2, the error is zero-mean but has finite bounded variance $\\sigma^2$. While $\\sigma^2$ could be large, assuming it is finite means that whole classes of two-tailed distributions are out, such as $\\alpha$-stable distributions for $\\alpha \\ne 2$ or $t$-distributions with $\\nu \\le 2$.\n\n* In the experiments in the submitted manuscript (the supplement has code only as far as I could see) the authors use Gaussian noise with only one value of the variance ($0.25$) and the Student-$t$ distribution with $\\nu = 3$ so the variance is  $\\frac{3}{3-1} = 1.5$. If I am misunderstanding, I am happy to be corrected! However, these are hardly the \"extensive experiments\" promised in the abstract. Obviously, space is limited, but I would have expected a better exploration of how robust the method is to actual heavy tailed noise.\n\n* Considering this I think the claims that this method is itself robust is misleading: the loss function is chosen for its robustness properties, but neither the analysis nor the experiments properly take into account real heavy tails.\n\n**Main Question 2: How is this algorithm supposed to be run?** This is a bit of a disconnect between the idea of the algorithm and its implementation. Since empirically everything is computed on the grid of $m$ points, everything turns into an $m$-dimensional vector gradient problem. Of course, the underlying structure comes from the RKHS assumption.\n\n* Figure 1 suggests that for each individual, they either need privacy or do not need privacy so each gradient can be computed with or without noise. However, the experiments seem to only do private or nonprivate. Is the setting under consideration really reflected in Figure 1?\n\n* The privacy piece is \"turnkey\": just add Gaussian noise at each iteration according to the gradient sensitivity. This is the same SGD algorithm which has been studied for 10+ years now. So, the novelty is in the analysis of the functional gradient. The grid determines the covariance of the noise, but how should we choose the grid?\n\n* Because the analysis/theory is done in the RKHS, the grid size doesn't appear in the finite sample bounds. Commenting on the computational complexity in terms of the sample size alone also erases the impact of the grid: is there a way to incorporate it?\n\n**Main Question 3: Is this really about privacy at all?** In the end, this is just a noisy gradient algorithm for nonparametric regression. The privacy \"story\" is an OK motivation, but the experiments are on synthetic data and have no bearing on problems involving actual privacy considerations.\n\n* Under LDP there is no need to do privacy accounting so much of the \"privacy apparatus\" that has been developed over the years does not apply here.\n\n* If minibatching were allowed then perhaps we would see some more relevance for privacy. Is there a way to incorporate minibatching into this framework?\n\n* Several applications are mentioned in the introduction, but is there a vignette that the authors could provide in which someone has a privacy constraint, is worried about heavy-tailed noise, and has to use a nonparametric regression model (i.e. that's the right model for this kind of data)?\n\n**Other comments:**\n\n* There is some notation clash in using $z$ for the pair $(x,y)$ and a grid point (which is only in the $\\mathcal{X}$ space, right?)\n\n* Shouldn't the kernel function be an input to the algorithm as well?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** I am not able to evaluate the novelty of the theory w.r.t. the literature on nonparametric regression and online learning. \n\n* The problem is straightforward to state, mathematically.\n* The analysis, although quite complex, is interesting.\n\n**Weaknesses:**\n\n* It's not clear why this combination of constraints/properties would be needed in any particular application. In particular, the privacy piece seems almost incidental.\n* The experimental evaluation is quite cursory and doesn't explore the parameter space adequately.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Heavy-tailed noise in convergence analysis.**\n\n  - Our theoretical analysis requires finite-variance noise for tractable proof techniques, excluding some extreme heavy-tailed cases. However, it still covers common heavy-tailed distributions like student-$t$ distributions with degrees of freedom $\\nu > 2$, Laplace distribution, and symmetric Pareto distributions with shape parameter $\\alpha>2$.\n\n  - While our main manuscript focuses on Gaussian and $t(3)$ noise, we have conducted additional experiments with heavier-tailed noise, including Student-$t(2.5)$ and $\\text{Cauchy}(0,1)$ noises. The tables below show MSE (×$10^{-3}$) means and standard deviations over 200 repetitions for $n=10000, 20000$, and $40000$, under both constant and non-constant step sizes.\n\n    - $t(2.5)$ noise:\n\n      |                  |   Constant   |              |               | Non-constant |              |               |\n      | :--------------: | :----------: | :----------: | :-----------: | :----------: | :----------: | :-----------: |\n      | **Method \\ $n$** |  **10000**   |  **20000**   |   **40000**   |  **10000**   |  **20000**   |   **40000**   |\n      |    **H-FSGD**    | 2.15 (0.758) | 1.25 (0.415) | 0.669 (0.214) | 2.26 (1.06)  | 1.41 (0.682) | 0.907 (0.467) |\n      |   **L2-FSGD**    | 3.97 (2.25)  |  2.04 (1.20)  | 1.11 (0.551)  |  6.13 (4.40)  | 3.38 (2.89)  |  2.02 (1.71)  |\n      |   **Offline**    | 4.21 (2.17)  | 2.17 (1.26)  | 1.16 (0.569)  | 6.75 (5.49)  | 3.65 (3.25)  |  2.12 (1.85)  |\n\n    - $\\text{Cauchy}(0,1)$ noise: \n\n      |                  |      Constant       |                     |                     |    Non-constant     |                     |                     |\n      | :--------------: | :-----------------: | :-----------------: | :-----------------: | :-----------------: | :-----------------: | :-----------------: |\n      | **Method \\ $n$** |      **10000**      |      **20000**      |      **40000**      |      **10000**      |      **20000**      |      **40000**      |\n      |    **H-FSGD**    |     3.64 (1.57)     |    1.97 (0.816)     |      1.00 (0.435)      |     5.22 (3.25)     |     2.98 (1.81)     |     1.65 (1.03)     |\n      |   **L2-FSGD**    | 5.83e+07 (8.2e+08)  | 1.89e+07 (2.65e+08) | 5.7e+06 (7.89e+07)  | 2.24e+08 (3.17e+09) | 1.01e+08 (1.42e+09) | 4.36e+07 (6.15e+08) |\n      |   **Offline**    | 1.73e+08 (2.45e+09) | 4.86e+07 (6.85e+08) | 1.33e+07 (1.86e+08) | 3.67e+08 (5.19e+09) | 1.38e+08 (1.95e+09) | 5.32e+07 (7.51e+08) |\n\n  - The results show H-PSGD's superior empirical performance over L2-FSGD and offline methods even under extreme heavy-tailed noise. While lacking theoretical guarantees for infinite-variance settings, this robustness motivates future theoretical investigation. \n\n- **Implementation of the algorithm.**\n\n    - **Mixed privacy.** Algorithm 1 (PH-FSGD) supports mixed privacy regimes through iteration-specific privacy budgets. Large $\\varepsilon_n$ values effectively imply non-private updates. While our current experiments focus on fully private or non-private settings, the algorithm naturally accommodates hybrid cases by adjusting per-iteration noise. We will clarify this in the revision. \n\n  - Our method employs functional SGD, which differs fundamentally from finite-dimensional SGD by optimizing over infinite-dimensional function spaces  (\"Online learning with kernels\", *IEEE transactions on signal processing*, 2004). This involves Fréchet derivatives, RKHS-based analysis, and more complex convergence proofs (see, e.g., \"Nonparametric stochastic approximation with large step-sizes\", *The Annals of Statistics*, 2016). Our key contribution is a theoretically grounded private functional estimator with convergence guarantees for both step size schemes.\n\n  - **Choice of grids.** We clarify that our method and theory are developed in the infinite-dimensional RKHS, while the grid-based implementation is a discretized approximation for computational feasibility. The current bounds do not reflect the effect of grid size $m$, as the analysis assumes sufficiently fine discretization to approximate the continuous function. We acknowledge that small $m$ may introduce non-negligible error. In practice, a dense grid is needed to recover the function accurately, as also done in prior work (e.g., \"Scalable statistical inference in non-parametric least squares\", *arxiv*, 2023), which similarly builds theory in function space but uses discrete grids for implementation. Extending the theory to account for finite grid is left for future work.\n\n  - **Computational complexity.** Our theoretical analysis operates directly in RKHS, with finite-sample bounds depending on kernel eigenvalue decay rate $\\alpha$ rather than grid size $m$. The grid size $m$ affects the computational costs, with $O(m^3+nm^2)$ total runtime and $O(m^2)$ storage. This reflects an accuracy-efficiency tradeoff that we will clarify in revision.\n\n- **Practical applicability.**\n  - Our method is grounded in LDP, which avoids the need for trusted data collectors or centralized privacy accounting, unlike CDP-based methods. With disjoint data access at each iteration, our algorithm leverages parallel composition to provide rigorous per-user privacy protection, particularly valuable in streaming or decentralized environments.\n\n  - **Minibatching integration.** Our framework can be easily extended to support minibatching. Specifically, at iteration $n$, if a mini-batch $\\\\{(X_{nt}, Y_{nt})\\\\}_{t=1}^{B_n}$ with size $B_n$ is available, the update rule becomes: $$\\hat{f}_n=\\hat{f}\\_{n-1}+\\gamma_n \\frac{1}{B_n}\\sum\\_{t=1}^{B_n}w\\_{\\tau}\\left(Y\\_{nt}-\\langle \\hat{f}\\_{n-1},K\\_{X\\_{nt}}\\rangle\\_{\\mathcal{H}}\\right)\\left(Y\\_{nt}-\\langle \\hat{f}\\_{n-1},K\\_{X\\_{nt}}\\rangle\\_{\\mathcal{H}}\\right)K\\_{X\\_{nt}}+\\gamma_n \\xi_n,$$ $$\\bar{f}_n=\\frac{n-1}{n}\\bar{f}\\_{n-1}+\\frac{1}{n}\\hat{f}\\_n,$$\n    where $\\xi_n$ is the sample path of a Gaussian process having mean zero and covariance function $\\frac{8 \\tau^2 B^2\\log(2/\\delta_n)}{\\varepsilon_n^2}K$ with $(\\varepsilon_n, \\delta_n)$ being the privacy budget at the $n$-th iteration. The noise term $\\xi_n$ still suffices to ensure differential privacy, as the modified Fréchet gradient has the same sensitivity and the privacy mechanism remains applicable in this case. Moreover, the theoretical analysis can be readily modified by replacing the single-sample gradient with its minibatch-averaged counterpart. Minibatching may in fact help improve the privacy–utility trade-off by reducing gradient variance, allowing for smaller noise magnitudes under the same privacy budget; however, it also requires a trusted data collector to aggregate and access the mini-batch data. We will discuss the incorporation of minibatching in the revised version. \n\n  - **Applications.** Many real-world applications simultaneously require privacy protection, robustness to heavy-tailed noise, and nonparametric modeling. Examples include:\n\n    - Healthcare analytics. Wearable fitness data (e.g., heart rate, sleep patterns) demands LDP since raw physiological signals can re-identify users; exhibits heavy-tailed noise due to irregular activities (e.g., sudden spikes in heart rate during exercise or sensor artifacts); and necessitates nonparametric regression because the relationship between metrics (e.g., sleep duration vs. recovery rate) is often nonlinear and complex.\n    - Financial fraud detection. Transaction histories require LDP when shared due to their identifiable nature, legitimate spending patterns contaminated by fraudulent outliers create heavy-tailed distributions, and the adversarial nature of fraud evolution necessitates nonparametric methods to detect novel attack patterns beyond rigid rule-based systems.\n    - Consumer behavior analysis. Browsing logs need LDP protection against profiling, purchase amounts exhibit heavy-tailed distributions dominated by rare large orders, and market segmentation reveals irregular price elasticity patterns that nonparametric models can adequately capture. \n\n  - To better validate our method's practical utility, we conducted experiments on the real data \"Health and fitness dataset\" from Kaggle website. Our goal is to investigate how endurance levels affect overall fitness. We select 40000 samples as the training set and 1000 samples as the test set. We compared our H-FSGD and PH-FSGD methods with baseline methods on out-of-sample $R^2$ performance, as displayed in the table below. \n\n     | Step size \\ Method | H-FSGD | L2-FSGD | Offline | (2,0.2)-LDP | (3,0.1)-LDP |  lm   |\n    | :----------------: | :----: | :-----: | :-----: | :---------: | :---------: | :---: |\n    |    **Constant**    | 0.622  |  0.617  |  0.609  |    0.589    |    0.609    | 0.581 |\n    |  **Non-constant**  | 0.623  |  0.618  |  0.609  |    0.526    |    0.596    | 0.581 |\n\n    The results show that H-FSGD consistently outperforms L2-FSGD and Offline methods, showing strong robustness. All non-private nonparametric methods outperform linear regression (lm) in capturing complex relationships. Under LDP, PH-FSGD remains competitive, matching or exceeding lm, confirming its effectiveness under privacy constraints. These findings validate our method’s ability to model nonlinear patterns while preserving privacy. We will include additional practical application details and real-world data analysis in the revision.\n\n- **Notation and presentation.**\n\n  - We will revise the notation to eliminate conflicts, include the kernel function as an explicit algorithm input, and review the presentation for clarity and consistency in the revision.\n\nThank you again for your comments. We hope our responses resolve your concerns. If anything remains unclear, we’d be happy to provide further clarification."}, {"review_id": "PvaloYq2XI", "reviewer": "Reviewer_nvq6", "summary": "The authors address the problem of online nonparametric regression and propose an algorithm that is both outlier-robust and locally differentially private. The key novelty lies in the use of the Huber loss to enhance robustness against outliers, combined with the addition of Gaussian process noise to ensure local differential privacy. The paper provides non-asymptotic theoretical guarantees for the proposed method and validates the results with synthetic numerical experiments.", "questions": "Please see strengths and weaknesses.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper addresses a compelling problem that is likely to interest the machine learning community, particularly those focused on streaming data, robustness, and privacy. Building on functional SGD methods for the squared loss [Liu et al., 2023], the authors introduce the Huber loss to enhance robustness and incorporate Gaussian process noise to achieve local differential privacy.\n\nIn my opinion, the paper is difficult to read due to heavy notation and a lack of a clear formal problem setup. A more structured presentation would help place the contributions in a better context and improve overall readability.\n\n1. Could the authors provide formal definitions of outlier robustness and local differential privacy (LDP) in the context of this work? While the theorems address properties related to LDP, the main text does not clearly define it. Including formal definitions would help clarify the contributions and make the theoretical results more accessible. \n2. The paper does not appear to provide any formal guarantees regarding outlier robustness. Interestingly, the choice of $\\tau$ also influences the privacy guarantees through the term $8 \\tau^2 B^2 \\log (2/\\delta)/\\varepsilon^2$. Suppose one does not have any concern about outliers, can we keep $\\tau$ to $\\infty$ and essentially work with the squared loss? How does this affect the privacy guarantees?\n3. Similarly, if privacy is not a concern, then one does not see any direct dependency on $\\tau$ in Corollary 3. How does the choice of $\\tau$ affect the guarantees in Corollary 3?  \n4. In my opinion, Lemma 1 should be included in the main text, as it appears to play a central role in supporting the main results.\n5. Related to point 1, could the authors clarify how Proposition 1, which (as far as I understand) concerns central differential privacy, is used in the proof of Theorem 1, which provides guarantees for local differential privacy?\n6. The step size depends on hyperparameters $(B, M, \\kappa)$, which may not be readily available in practice. Could the authors clarify how the step size should be selected to ensure convergence when these parameters are unknown?", "was_revised": true, "final_justification": "After reading the rebuttal and subsequent discussion, I have decided to maintain my current score. In my opinion, the paper needs a major restructuring and remains difficult to parse in its current state. The authors have promised to improve the clarity of the paper, but I believe that would require major changes in the current presentation, and should ideally go through another round of fresh reviews for a better assessment. \n\nThe authors have also included some additional guarantees for the robustness part. I have not verified these results. In any case, I believe these would be a good addition in a fresh version of the paper.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Clarification of notation and problem setup.** We agree that the current notation may hinder readability. Due to space constraints, we refer the reviewer to the notation table in our response to Reviewer x3FU, and a concise version will be included in the revision. While the formal setup appears in Section 2, we will reorganize and clarify its structure to better contextualize our contributions and improve clarity.\n\n- **Formal definitions.** \n  - **Outlier robustness.**  In our work, outlier robustness refers to the estimator’s stability and accuracy under contaminated or heavy-tailed data. Classical examples include Huber's M-estimators, which cap large residuals to balance efficiency and robustness (\"Robust estimation of a location parameter\", *The Annals of Mathematical Statistics*, 1964). Recent results (e.g., \"Concentration study of M‑estimators using the influence function\", *Electronic Journal of Statistics*, 2022) further establish their non-asymptotic stability under adversarial contamination, though sensitivity to high-leverage points remains due to unbounded structural influence. We will clarify this in the revised version.\n\n  - **Local differential privacy (LDP).** We agree that including key definitions such as LDP in the main text is important for clarity. Due to space constraints, the formal definition currently appears in Appendix A.2 (Definition 3). If accepted, we will move it to the main text to improve readability. For completeness, we restate the definition below.\n\n    **Definition3** (LDP, \"A comprehensive survey on local differential privacy\", *Security and Communication Networks*, 2020). Let $\\varepsilon>0$ and $\\delta\\geq 0$. A randomized algorithm $M: \\mathcal{X} \\rightarrow \\mathcal{Y}$ is said to be $(\\varepsilon,\\delta)$-LDP if for any pair of input individual values $x, x^\\prime\\in\\mathcal{X}$, and any measurable set $E\\subset \\mathcal{Y}$, \n    $$\\mathbb{P}(M(x)\\in E)\\leq e^{\\varepsilon}\\mathbb{P}(M(x^\\prime)\\in E)+\\delta,$$\n    where the probabilities are computed over the randomness of the mechanism $M$. \n  \n- **Robustness and privacy guarantee without outlier concern.** \n  - Our use of the Huber loss is motivated by its well-established robustness, balancing squared loss sensitivity for small residuals with absolute loss stability for large outliers. While we omit formal robustness guarantees here, its strong theoretical backing, from Huber’s original minimax analysis (\"Robust estimation of a location parameter\", *The Annals of Mathematical Statistics*, 1964) to modern concentration bounds (e.g., \"Concentration study of M‑estimators using the influence function\", *Electronic Journal of Statistics*, 2022), supports its effectiveness. We will elaborate on this rationale in the revised version.\n\n  - When outliers are not a concern ($\\tau \\to \\infty$), the Huber loss reduces to the squared loss. In the DP setting, the privacy guarantee depend on gradient sensitivity. Without additional assumptions, it is standard practice to apply gradient clipping to ensure bounded sensitivity under the squared loss (see, e.g., \"Evading the curse of dimensionality in unconstrained private glms\", *AISTATS*, 2021). If the response variable $Y$ is further assumed to be bounded, then the gradient sensitivity is naturally finite, and the privacy guarantee directly depends on its magnitude. Thus, squared loss remains privacy-compatible with proper sensitivity control. We will clarify this connection in revision.\n\n- **Role of $\\tau$ on the upper bound in Corollary 3.**\n\n  - When privacy is not a concern, the parameter $\\tau$ does not appear explicitly in Corollary 3, as it is absorbed into the constant $c$ defined in Lemma 1 and further into the  $O(\\cdot)$ notation. However, $\\tau$ implicitly influences the bound via its role in defining constant $c$.\n\n  - To make this dependence more transparent, we provide a modified version of Corollary 3 in which $\\tau$ is not absorbed into the $O(\\cdot)$ notation.\n\n    **Corollary 3'** (Constant step size, without privacy).\n\n    Suppose Assumptions 1-7 hold. Consider the estimator $\\bar{f}_n^0$ without privacy protection defined via the recursion (5). Take any constant choice $\\gamma_i=\\gamma=\\Gamma(n)$, for $1\\leq i\\leq n$. If $c^{-1}\\gamma B^2<1$ with $c$ defined in Lemma 1, i.e., $c:=c(\\tau)=2m\\kappa\\min\\left\\\\{1, \\frac{\\tau}{m+BM+\\\\|f^{\\star}\\\\|\\_{\\infty}}\\right\\\\}$, then $$\\mathbb{E}\\\\|\\bar{f}_n^0-f_{\\mathcal{H}}\\\\|_{L_{P_X}^2}^2\\leq O\\left(\\frac{c^{-2}\\sigma^2}{(1-(c^{-1}\\gamma B^2)^{1/2})^2}\\left(c^{1/\\alpha}\\gamma^{1/\\alpha}n^{-1+1/\\alpha}+n^{-1}\\right)+(1+q(c,\\gamma, n))c^{-2r}\\gamma^{-2r}n^{-2\\min\\\\{r,1\\\\}}\\\\|\\Sigma^{-r}f_{\\mathcal{H}}\\\\|_{L_{P_X}^2}^2\\right),$$ where $q(c,\\gamma, n)=0$ for $r\\leq 1/2$, and $q(c,\\gamma, n)=\\left(\\frac{B^2}{2c-\\gamma B^2}\\right)^{2r-1}c^{(2r-1)/\\alpha}\\gamma^{(1+\\alpha)(2r-1)/\\alpha}n^{(2r-1)/\\alpha}$ for $r>1/2$.\n\n  - The parameter $\\tau$, which is embedded in $c$, establishes a trade-off between robustness and bias in the estimation, which is consistent with classical literature (see, e.g., \"Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions\", *Journal of the Royal Statistical Society, Series B*, 2017). In practice, we first compute an L2-FSGD estimate and residuals, then estimate the noise scale via median absolute deviation (MAD). The robustness parameter $\\tau$ is set to $1.345\\times \\mbox{MAD}$, ensuring $90\\\\%$ efficiency under normal errors while resisting outliers, following standard robust regression practice (Lines 191-193, Algorithm 2). This builds on classical Huber loss methods (see, e.g., \"Robust regression using iteratively reweighted least-squares\", *Communications in Statistics-theory and Methods*, 1977). We will incorporate these clarifications in the revised revision.\n\n- **Placement of Lemma 1.** We agree that Lemma 1 plays a central role in supporting our main results. If the paper is accepted, we will include it in the main text to improve clarity and accessibility.\n\n- **Clarification on the use of Proposition 1 in the proof of Theorem 1.** You are right that Proposition 1 concerns central differential privacy (CDP). However, CDP reduces to local differential privacy (LDP) in the single-sample setting. In our proof of Theorem 1, we apply Proposition 1 with single sample $D = \\\\{(X_n, Y_n)\\\\}$, effectively leveraging CDP results to establish LDP guarantees.\n\n- **Selection of step size.**\n\n  - Theoretically, the choice of step size is indeed crucial for the convergence rate of the proposed estimators, both under constant and non-constant step size settings. Corollaries 1-4 demonstrate that, depending on the range of $r$, different choices of $\\zeta$ are required to attain the optimal convergence rate. \n  \n  - In practice, when the hyperparameters involved in the theoretical step size are unavailable, we recommend selecting the step size using a decaying schedule of the form $\\gamma_i = \\gamma_0 n^{-\\zeta}$ (for constant step size and the total sample size $n$) or $\\gamma_i = \\gamma_0 i^{-\\zeta}$ (for non-constant step size). The parameters $\\gamma_0$ and $\\zeta$ can be tuned via grid search on a validation set. This approach is widely adopted in practice and shown to be effective across various optimization settings (see, e.g., \"The step decay schedule: a near optimal, geometrically decaying learning rate procedure for least squares\", *NeurIPS*, 2019; \"Benefits of learning rate annealing for tuning‑robustness in stochastic optimization\", *arxiv*, 2025). \n  \n  - To address practical concerns, we have conducted additional simulation studies to examine the sensitivity of estimation performance with respect to different values of step size. We examine the H-FSGD performance under Case 1 for both constant and non-constant step size settings, with $\\gamma_0 \\in [4, 24]$ and $\\zeta \\in [0.3, 0.8]$. The tables below report the average MSE ($\\times 10^{-3}$) over 50 repetitions when $n = 10000$.\n  \n    - Constant step size setting:\n  \n      | $\\zeta$ \\ $\\gamma_0$ |   4   |   8   |  12  |  16  |  20  |  24  |\n      | :------------------: | :---: | :---: | :--: | :--: | :--: | :--: |\n      |       **0.3**        | 1.52  | 1.76  | 2.05 | 2.38 | 2.79 | 3.32 |\n      |       **0.4**        | 1.59  | 1.49  | 1.56 | 1.65 | 1.76 | 1.87 |\n      |       **0.5**        | 2.06  | 1.67  | 1.54 | 1.50 | 1.49 | 1.51 |\n      |       **0.6**        | 4.03  | 2.30  | 1.93 | 1.76 | 1.67 | 1.60 |\n      |       **0.7**        | 12.28 | 5.18  | 3.37 | 2.66 | 2.31 | 2.11 |\n      |       **0.8**        | 59.14 | 17.12 | 9.69 | 6.77 | 5.21 | 4.25 |\n  \n    - Non-constant step size setting:\n  \n      | $\\zeta$ \\ $\\gamma_0$ |  4   |  8   |  12  |  16  |  20  |  24  |\n      | :------------------: | :--: | :--: | :--: | :--: | :--: | :--: |\n      |       **0.3**        | 1.63 | 1.99 | 2.44 | 3.04 | 4.13 | 5.12 |\n      |       **0.4**        | 1.51 | 1.62 | 1.77 | 1.96 | 2.13 | 2.33 |\n      |       **0.5**        | 1.69 | 1.59 | 1.63 | 1.66 | 1.80 | 1.85 |\n      |       **0.6**        | 2.27 | 1.94 | 1.92 | 1.84 | 1.87 | 1.93 |\n      |       **0.7**        | 3.59 | 3.14 | 2.95 | 2.85 | 2.68 | 2.63 |\n      |       **0.8**        | 7.74 | 6.27 | 6.50 | 6.46 | 6.58 | 6.39 |\n  \n  - Our results indicate that the proposed estimators exhibit robustness to the choice of $\\gamma_0$ and $\\zeta$ under both constant and non-constant step size settings, with wide parameter regions yielding stable and comparable MSEs. If the paper is accepted, we will clarify the step size selection procedure and provide a sensitivity analysis.\n\nThank you again for your comments. We hope our responses resolve your concerns. If anything remains unclear, we’d be happy to provide further clarification."}, {"review_id": "UdRyvbtmSD", "reviewer": "Reviewer_x3FU", "summary": "This paper addresses nonparametric regression on streaming data by introducing two algorithms:\n\nH-FSGD: A functional stochastic gradient descent method that employs the Huber loss to mitigate heavy-tailed noise and outliers by truncating large residuals.\n\nPH-FSGD: A locally differentially private variant of H-FSGD that injects carefully calibrated Gaussian process noise at each iteration, ensuring each data point is protected at the source without requiring a trusted curator.", "questions": "1. In Corollary 1 (Line 264), under a constant step size, the bound appears independent of the privacy parameters. Could the authors clarify this?\n\n2. In Line 144, how is the closure of H measured or defined?", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The manuscript is well written and clearly structured.\n\n2. Incorporating the Huber loss is a sensible choice: it projects estimates into a finite-dimensional RKHS subspace, handles heavy-tailed noise and outliers effectively, and yields a uniformly bounded gradient—ideal for private algorithm design.\n\n3. Both algorithms operate in a single pass, making them well suited for streaming data scenarios.\n\nWeaknesses:\n\n1. The notation is dense and could overwhelm readers; a summary table contrasting the theoretical guarantees for the non-private and private settings would improve clarity.", "was_revised": true, "final_justification": "I think my concerns have been addressed, so I increase my score.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Clarification of notation and theoretical results.**\n\n  - Thank you for the valuable suggestion. We agree that a notation list and a summary table contrasting the theoretical guarantees for the non-private and private settings would enhance clarity and highlight our contributions. If accepted, we will include these in the revised manuscript to improve reader comprehension.\n\n  - The list of notation: \n    - $X_n$: the $n$-th copy of the random covariate $X$;\n    - $Y_n$: the $n$-th copy of the response $Y$;\n    - $e_n$: the $n$-th copy of the error $e$;\n    - $\\sigma^2$: the variance of the error $e$;\n    - $f^\\star$: the target nonparametric function lying in the space $L^2(P_X)$;\n    - $K$: the reproducing kernel;\n    - $\\mathcal{H}$: a reproducing kernel Hilbert space (RKHS);\n    - $\\langle \\cdot, \\cdot\\rangle_{\\mathcal{H}}$: the inner product in $\\mathcal{H}$;\n    - $\\bar{\\mathcal{H}}$: the closure of $\\mathcal{H}$;\n    - $f_{\\mathcal{H}}$: the best approximation of $f^\\star$ in the RKHS $\\bar{\\mathcal{H}}$;\n    - $L_{\\tau}$: the Huber loss with the parameter $\\tau$;\n    - $\\widehat{\\nabla L_{\\tau}}$: the estimator of the Fréchet gradient of the Huber loss;\n    - $B^2$: the uniform upper bound of $K(x,x)$ for all $x$;\n    - $\\gamma_n$: the step size at the $n$-th iteration;\n    - $\\hat{f}\\_n$: the current private estimator of $f_{\\mathcal{H}}$ at the $n$-th iteration;\n    - $\\bar{f}\\_n$: the averaged private estimator of $f_{\\mathcal{H}}$ at the $n$-th iteration;\n    - $\\bar{f}\\_n^0$: the averaged non-private estimator of $f_{\\mathcal{H}}$ at the $n$-th iteration;\n    - $\\varepsilon_n$, $\\delta_n$: the privacy budget at the $n$-th iteration;\n    - $\\\\{z_j\\\\}_{j=1}^m$: the function grids;\n    - $\\Sigma$:  the covariance operator associated with the kernel $K$, i.e., $\\Sigma=\\mathbb{E}(K_X\\otimes K_X)$;\n    - $\\alpha$: the parameter characterizing the decay rate of the eigenvalues of the covariance operator $\\Sigma$;\n    - $r$: the parameter quantifying the regularity of the target function $f_{\\mathcal{H}}$ with respect to the eigenbasis of $\\Sigma$.\n\n  - Summary of theoretical results: we will add a table below contrasting the theoretical guarantees under private and non-private settings across different regimes of the decay rates $r$, covering both constant and non-constant step-size schemes. \n\n    - Constant step size:\n\n      Private setting: $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)\\left(\\gamma^{1/\\alpha}n^{-1+1/\\alpha}+n^{-1}\\right)+(1+q(\\gamma, n))\\gamma^{-2r}n^{-2\\min\\\\{r,1\\\\}}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P\\_X}^2}^2\\right)$;\n\n      Non-private setting: $O\\left(\\sigma^2\\left(\\gamma^{1/\\alpha}n^{-1+1/\\alpha}+n^{-1}\\right)+(1+q(\\gamma, n))\\gamma^{-2r}n^{-2\\min\\\\{r,1\\\\}}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P_X}^2}^2\\right)$.\n\n      |           $r$ range           | Optimal $\\zeta$ in $\\gamma_i\\asymp n^{-\\zeta}$ |    Private / non-private convergence rate    |\n      | :---------------------------: | :--------------------------------------------: | :------------------------------------------: |\n      | $(0, (\\alpha - 1)/(2\\alpha)]$ |                      $0$                       |                 $O(n^{-2r})$                 |\n      |  $((\\alpha-1)/(2\\alpha) ,1]$  |       $(2r\\alpha+1-\\alpha)/(2r\\alpha+1)$       |     $O(n^{-2r\\alpha / (2r\\alpha + 1)})$      |\n      |      $(1, (\\alpha+2)/2]$      |           $(\\alpha+1)/(2r\\alpha+1)$            | $O(n^{-(2r\\alpha - 2r + 2)/(2r\\alpha + 1)})$ |\n      |   $((\\alpha+2)/2, \\infty)$    |                 $1/(1+\\alpha)$                 |        $O(n^{-\\alpha / (1+\\alpha)})$         |\n\n    - Non-constant step size:\n\n      Private setting: for $0\\leq\\zeta\\leq 1/2$, $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)\\gamma_n^{1/\\alpha}n^{-1+1/\\alpha}+\\gamma_n^{-1}(n\\gamma_n)^{-2r}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P_X}^2}^2\\right);$ \n\n      ​                           for $1/2<\\zeta<1$, $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)(n\\gamma_n)^{-2+1/\\alpha}+\\gamma_n^{-1}(n\\gamma_n)^{-2r}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P_X}^2}^2\\right);$\n\n      Non-private setting: for $0\\leq\\zeta\\leq 1/2$, $O\\left(\\sigma^2\\gamma_n^{1/\\alpha}n^{-1+1/\\alpha}+\\gamma_n^{-1}(n\\gamma_n)^{-2r}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P_X}^2}^2\\right);$ \n\n      ​                                    for $1/2<\\zeta<1$, $O\\left(\\sigma^2(n\\gamma_n)^{-2+1/\\alpha}+\\gamma_n^{-1}(n\\gamma_n)^{-2r}\\left\\\\|\\Sigma^{-r}f\\_{\\mathcal{H}}\\right\\\\|\\_{L\\_{P_X}^2}^2\\right).$\n\n      |                   $r$ range                    | Optimal $\\zeta$ in $\\gamma_i\\asymp n^{-\\zeta}$ |          Private / non-private convergence rate           |\n      | :--------------------------------------------: | :--------------------------------------------: | :-------------------------------------------------------: |\n      |         $(0, (\\alpha - 1)/(2\\alpha)]$          |                      $0$                       |                       $O(n^{-2r})$                        |\n      | $((\\alpha-1)/(2\\alpha) ,(1+\\alpha)/(2\\alpha))$ |   $(2r\\alpha+1-\\alpha)/(2r\\alpha+1+\\alpha)$    | $O(n^{-(2r\\alpha + \\alpha - 1)/(2r\\alpha + 1 + \\alpha)})$ |\n      |        $[(1+\\alpha)/(2\\alpha), \\infty)$        |                 $1/(1+\\alpha)$                 |                $O(n^{-\\alpha/(1+\\alpha)})$                |\n\n    - In all, the privacy term introduces an additional constant factor of $(8\\tau^2 B^2 \\log(2/\\delta))/(\\varepsilon^2)$, which increases the variance constant but does not change the asymptotic rates under optimal step sizes.\n\n- **Role of the privacy parameters in Corollary 1.**\n\n  - We appreciate the reviewer’s careful reading. Corollary 1 is a direct consequence of Theorem 2, where the dependence on the privacy parameters is made explicit. In Corollary 1, we focus on the asymptotic order in terms of the sample size $n$, all privacy parameters ($\\varepsilon$, $\\delta$) are treated as constants; their contribution is absorbed into the $O(\\cdot)$ notation. To clarify this point, we have now restored the explicit dependence on the privacy parameters in the convergence rates. Specifically, for different regimes of $r$, the convergence rate becomes:\n\n    - When $0<r\\leq (\\alpha-1)/(2\\alpha)$, the optimal order is $O\\left(n^{-2r}\\right);$\n    - When $(\\alpha-1)/(2\\alpha)<r\\leq 1$, the optimal order is $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)n^{-2r\\alpha/(2r\\alpha+1)}\\right);$\n    - When $1<r\\leq (\\alpha+2)/2$, the optimal order is $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)n^{-(2r\\alpha-2r+2)/(2r\\alpha+1)}\\right);$\n    - When $r>(\\alpha+2)/2$, the optimal order is $O\\left(\\left(\\sigma^2+\\frac{8 \\tau^2 B^2\\log(2/\\delta)}{\\varepsilon^2}\\right)n^{-\\alpha/(1+\\alpha)}\\right)$.\n\n  We will incorporate this clarification into the revised manuscript to enhance transparency regarding the role of the privacy parameters.\n\n- **Definition of the closure of $\\mathcal{H}$.**\n\n  - We thank the reviewer for pointing this out. As defined in the paper, $\\mathcal{X}$ is the domain of the random covariate $X$ with marginal distribution $P_X$, $\\mathcal{H}$ is a reproducing kernel Hilbert space on $\\mathcal{X}$ with inner product $\\langle \\cdot, \\cdot \\rangle_{\\mathcal{H}}$ and reproducing kernel $K(\\cdot,\\cdot): \\mathcal{X} \\times \\mathcal{X} \\to \\mathbb{R}$, and $L^2(P_X)$ is the space of square-integrable functions with respect to $P_X$, i.e., $L^2(P_X) = \\\\{f: \\mathcal{X} \\rightarrow \\mathbb{R} | \\int\\_{\\mathcal{X}}f(x)^2dP_X(x) < \\infty  \\\\}$. Then the closure of $\\mathcal{H}$ in $L^2(P_X)$, denoted by $\\bar{\\mathcal{H}}$, is defined as the set of all limits of sequences in $\\mathcal{H}$. Formally,\n\n    $$\\bar{\\mathcal{H}} = \\\\{ f \\in L^2(P_X): \\exists \\\\{f_k\\\\} \\subset \\mathcal{H} \\text{ such that } \\\\|f_k - f\\\\|_{L^2(P_X)} \\to 0 \\\\}.$$ \n\n    Intuitively,  $\\bar{\\mathcal{H}}$ consists of all functions in $L^2(P_X)$ that can be approximated arbitrarily well (in $L^2(P_X)$ norm) by a sequence of functions in $\\mathcal{H}$. This construction is standard in the kernel methods literature (see, e.g., \"Nonparametric stochastic approximation with large step-sizes\", *The Annals of Statistics*, 2016), and it allows us to avoid assuming that $f^\\star$ belongs to $\\mathcal{H}$ or that $\\mathcal{H}$ is dense in $L^2(P_X)$. We will clarify this point in the revised version if the paper is accepted.\n\nThank you again for your comments. We hope our responses resolve your concerns. If anything remains unclear, we’d be happy to provide further clarification."}, {"review_id": "qdk46Ie5Zy", "reviewer": "Reviewer_HRn7", "summary": "This paper addresses the problem of nonparametric regression in a streaming data setting, where data arrives sequentially and privacy is a major concern. The authors propose a novel framework and two new algorithms to tackle this challenge. The first algorithm, H-FSGD (Huber Functional Stochastic Gradient Descent), is a one-pass online method that uses the Huber loss to achieve robustness against heavy-tailed errors and outliers. The second algorithm, PH-FSGD, extends H-FSGD to provide Local Differential Privacy (LDP) by injecting calibrated Gaussian process noise at each iteration, thus protecting individual data points at the source without a trusted curator. The paper provides a comprehensive non-asymptotic convergence analysis for both estimators, establishing optimal convergence rates and exploring the trade-offs involving step size and privacy budget. The theoretical findings are supported by experiments on synthetic data, demonstrating the robustness and privacy-preserving capabilities of the proposed methods.", "questions": "I have a few questions for the authors that I believe could help clarify some points and strengthen the paper:\n\n1. **Real-world Performance:** I understand that setting up real-world streaming experiments can be challenging. However, could you perhaps comment on how you expect your method to perform on a benchmark streaming dataset? Even a discussion of the potential challenges (e.g., concept drift, non-i.i.d. data) and how your framework might adapt would be very insightful.\n\n2. **Robustness in Contamination Models:** Your use of Huber loss is well-motivated for heavy-tailed noise. I'm curious if you have any intuition on how the method would perform under a stronger threat model, like Huber's contamination model, where an adversary could corrupt a small fraction of the data points. Does your analysis provide any clues about the breakdown point of the estimator?\n\n3. **The Robustness-Privacy-Utility Trilemma:** There's a known tension in the local model between robustness, privacy, and statistical utility (see e.g. \"On the Privacy-Robustness-Utility Trilemma in Distributed Learning\", ICML '23). It seems your framework has all the knobs to explore this: the Huber parameter τ, the privacy budget (ϵ,δ), and the step size γ. Could you elaborate on the interplay between these? For example, how should one co-tune τ and ϵ to achieve a good trade-off, especially when outliers are present?\n\n4. A quick note on notation: In line 185, you define $w_\\tau$ in terms of a variable $u$. It's clear from the line above that $u=y−f(x)$, but for maximum clarity, you might consider making that explicit in the definition itself.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n1. **Significance and Originality:** The paper tackles an important problem at the intersection of streaming data analysis, robust statistics, and privacy. To the best of the authors' knowledge and my own, developing a scalable, statistically sound method for online, robust, and locally private nonparametric regression is an open problem. The proposed framework, which combines functional SGD, Huber loss for robustness, and LDP for privacy, is a novel contribution to this area.\n\n2. **Theoretical Quality:** The paper provides a rigorous and comprehensive non-asymptotic convergence analysis. The authors establish finite-sample guarantees for their estimators in a general setting that does not assume the true function lies within the chosen RKHS. The analysis of convergence rates under various smoothness assumptions and step-size schemes is thorough and provides valuable theoretical insights into the behavior of the algorithms. The proofs provided in the appendix appear to be detailed and correct.\n\n3. **Clarity:** The paper is well-written. The authors clearly motivate the problem, lay out their contributions, and present their algorithms in a way that is easy to follow. The inclusion of a comparison table and flowchart is also helpful for understanding the overall structure of their contribution.\n\n### Weaknesses\n\n1. **Experimental Scope:** My main reservation about this paper is the limited scope of the experiments. While the synthetic data simulations do a good job of supporting the theoretical claims about efficiency and privacy, they stop short of showing how the method would perform on a real-world streaming dataset. Given that the work is motivated by practical applications like sensor networks and autonomous vehicles, the absence of a real-data experiment feels like a missed opportunity to demonstrate the framework's utility.\n\n2. **Characterization of Robustness:** The paper's notion of robustness is tied to handling heavy-tailed errors via the Huber loss. This is a perfectly reasonable approach, but it would be interesting to see a discussion of how this translates to robustness in an adversarial sense, for instance, in a Huber contamination model where a fraction of the data might be arbitrarily corrupted. The trade-off between the degree of robustness and the privacy guarantee is a subtle but important aspect that isn't fully explored. An example of this in the local privacy model is \"On the Privacy-Robustness-Utility Trilemma in Distributed Learning\", ICML '23.\n\n3. **Incremental Technical Novelty:** While the synthesis of ideas here is original and valuable, the core components (Functional SGD, Huber loss, and the Gaussian mechanism for privacy) are all well-established tools in their respective fields. The contribution is therefore less about creating a new technical tool and more about demonstrating how existing tools can be thoughtfully combined and analyzed to solve a new, complex problem. This is a valid and useful contribution, but it's worth noting.", "was_revised": true, "final_justification": "I agree with other reviewers that the paper clarity could be improved, e.g., definitions of differential privacy and outlier robustness. For the interplay between privacy and robustness, I recommend that the authors cite the trilemma work I referenced in my original review and any other relevant ones. The rebuttal and new experiments have addressed my initial concerns, and will introduce important changes to the paper. I maintain my positive assessment of the paper.", "rebuttal": "Thank you for your thoughtful and critical assessment. Many of your comments will help us produce a more readable and self-contained version of the paper. Below, we address each of your specific concerns in turn.\n\n- **Real-world performance.**\n  - **Real data analysis.** To demonstrate the practical utility of our method, we evaluated it on the “Health and Fitness” dataset from Kaggle website, aiming to assess the impact of endurance on overall fitness. We used 40000 samples for training and 1000 for testing. The table below reports out-of-sample $R^2$ comparisons across methods.\n\n       | Step size \\ Method | H-FSGD | L2-FSGD | Offline | (2,0.2)-LDP | (3,0.1)-LDP |  lm   |\n    | :----------------: | :----: | :-----: | :-----: | :---------: | :---------: | :---: |\n    |    **Constant**    | 0.622  |  0.617  |  0.609  |    0.589    |    0.609    | 0.581 |\n    |  **Non-constant**  | 0.623  |  0.618  |  0.609  |    0.526    |    0.596    | 0.581 |\n  \n    H-FSGD consistently outperforms L2-FSGD and Offline methods in streaming settings. Under LDP constraints, PH-FSGD remains competitive with or exceeds linear regression, underscoring its robustness and practical relevance. If accepted, we will include this analysis in the final version.\n  - **Extension to non-iid data.** We agree that addressing concept drift and non-i.i.d. data is both important and challenging. Our current framework, like standard functional SGD theory, assumes i.i.d. data,  and does not directly extend to non-i.i.d. settings—a limitation shared by many SGD-based methods. Challenges include parameter drift, slower convergence  (see, e.g., \"Federated learning with non-iid data\", *arXiv*, 2018; \"On the convergence of FedAvg on non-IID data\", *ICLR*, 2020), and bias from dependent observations. While one could define the population risk as $\\sum\\_{n=1}^{\\infty}p_nL\\_{\\tau}(Y_n-f_n(X_n))$ with distribution weight $p_n$, this is infeasible in online settings due to unknown distribution shifts and the ill-defined infinite-sum objective. A more practical alternative models the data as coming from $M$ sub-populations with different distributions, minimizing the global risk $\\sum_{m=1}^M p_m L\\_{\\tau}(Y^{(m)}-f(X^{(m)}))$. This leads to a parallel SGD scheme: at each round $t$, the global estimate $\\hat{f}\\_t$ is sent to local devices, which compute updates $$\\hat{f}^{(m)}\\_{t+1}=\\hat{f}\\_t-\\gamma_t \\widehat{\\nabla L}\\_\\tau (\\hat{f}\\_t)(X_n^{(m)}, Y_n^{(m)})+\\gamma_t \\xi_t,$$ followed by weighted aggregation $$\\hat{f}\\_{t+1}=\\sum_{m=1}^M p_m \\hat{f}\\_{t+1}^{(m)}.$$ This setup accommodates distributional heterogeneity and aligns with recent federated learning approaches for non-i.i.d. data  (see, e.g., \"EFL: elastic federated learning on non-IID data\", *Conference on lifelong learning agents*, 2022; \"Asynchronous online federated learning for edge devices with non-iid data\", *2020 IEEE International Conference on Big Data*, 2020). We will add this discussion to the revised version.\n- **Robustness in contamination models.**\n  - While our method is designed for heavy-tailed noise via the Huber loss, we also assess its robustness under Huber’s $\\varepsilon^\\star$-contamination model, where an $\\varepsilon^\\star$-fraction of data is adversarially corrupted. Using Case 1 (true model) and Case 2 (contaminated model), we simulate performance across varying $\\varepsilon^\\star$ at $n=10000$, reporting mean and standard deviation of MSE ($\\times 10^{-2}$) over $50$ runs:\n\n    |    Step size     | $\\varepsilon^\\star$ |        0        |      0.1       |     0.2      |     0.3      |     0.4     |     0.5     |     0.6     |    0.7     |    0.8     |    0.9     |\n    | :--------------: | :-----------------: | :-------------: | :------------: | :----------: | :----------: | :---------: | :---------: | :---------: | :--------: | :--------: | :--------: |\n    |   **Constant**   |     **H-FSGD**      | 0.0722 (0.0158) | 0.657 (0.0985) | 2.85 (0.251) | 8.08 (0.497) | 20.4 (1.27) | 56.7 (3.91) | 114 (3.47)  | 155 (2.49) | 186 (2.21) | 211 (2.10) |\n    |                  |     **L2-FSGD**     | 0.0619 (0.015)  |  2.46 (0.263)  | 9.49 (0.611) | 21.2 (0.928) | 37.4 (1.16) | 58.4 (1.60)  |  84.0 (1.70)   | 114 (1.74) | 149 (2.15) | 189 (2.14) |\n    | **Non-constant** |     **H-FSGD**      | 0.0939 (0.0326) | 0.683 (0.105)  | 2.89 (0.26)  | 8.11 (0.517) | 20.2 (1.23) | 56.4 (4.23) | 114 (3.78)  | 155 (2.61) | 186 (2.32) | 211 (2.16) |\n    |                  |     **L2-FSGD**     |  0.152 (0.136)  |  2.55 (0.31)   | 9.63 (0.683) | 21.3 (1.01)  | 37.5 (1.23) | 58.5 (1.64) | 84.2 (1.83) | 114 (1.94) | 149 (2.25) | 189 (2.18) |\n\n    H-FSGD remains stable up to $\\varepsilon^\\star = 0.3$, with degradation beginning around $\\varepsilon^\\star = 0.4$, suggesting a breakdown point near 40%. In contrast, L2-FSGD deteriorates earlier at $\\varepsilon^\\star = 0.3$. Across all settings, H-FSGD consistently outperforms L2-FSGD. We will include these results in the revised version.\n- **Robustness-privacy-utility trilemma.**\n  - Interplay among Huber parameter, privacy budget, and step size. \n    - In the non-private setting, smaller $\\tau$ improves robustness to outliers but increases bias—a classical bias–robustness trade-off (see, e.g., \"Estimation of high dimensional mean regression in the absence of symmetry and light tail assumptions\", *JRSSB*, 2017). In the private setting, a larger $\\tau$ amplifies gradient sensitivity, requiring stronger noise for given $(\\varepsilon, \\delta)$-LDP, which raises gradient variance and necessitates smaller $\\gamma_0$ for stability.\n    - A tighter privacy budget (e.g., smaller $\\varepsilon$) also demands more noise, further constraining $\\gamma_0$.\n    - The step size follows a schedule: $\\gamma_i = \\gamma_0 n^{-\\zeta}$ (constant step size) or $\\gamma_i = \\gamma_0 i^{-\\zeta}$ (non-constant). Corollaries 1–4 show the optimal $\\zeta$ depends on smoothness parameters $r$ and $\\alpha$. Under strong privacy noise, smaller $\\gamma_0$ improves stability, but overly small steps slow convergence.\n\n  - Co-tune strategy in practice. \n\n    - Huber parameter: we first compute an L2-FSGD estimate and residuals, then estimate noise scale via MAD. The Huber parameter is set to $\\tau = 1.345 \\times \\text{MAD}$, achieving $90\\\\%$ efficiency under normality while preserving robustness (Lines 191–193, Algorithm 2), following standard practice (see, e.g., \"Robust regression using iteratively reweighted least-squares\", *Communications in Statistics-theory and Methods*, 1977).\n\n    - Privacy budget: chosen based on application needs. Where possible, a looser budget (larger $\\varepsilon$) reduces noise and improves utility.\n\n    - Step size: in the absence of theory-guided tuning, we recommend grid search for $\\gamma_0$ and $\\zeta$ on a validation set—a practical and widely used approach (see, e.g., \"The step decay schedule: a near optimal, geometrically decaying learning rate procedure for least squares\", *NeurIPS*, 2019; \"Benefits of learning rate annealing for tuning‑robustness in stochastic optimization\", *arxiv*, 2025). To assess sensitivity, we simulate H-FSGD under Case 1 using both step-size schedules, with $\\gamma_0 \\in [4, 24]$ and $\\zeta \\in [0.3, 0.8]$, and report average MSE ($\\times 10^{-3}$) over 50 repetitions at $n = 10000$ (tables below). These results will be included in the revision.\n\n      - Constant step size setting:\n\n        | $\\zeta$ \\ $\\gamma_0$ |   4   |   8   |  12  |  16  |  20  |  24  |\n        | :------------------: | :---: | :---: | :--: | :--: | :--: | :--: |\n        |       **0.3**        | 1.52  | 1.76  | 2.05 | 2.38 | 2.79 | 3.32 |\n        |       **0.4**        | 1.59  | 1.49  | 1.56 | 1.65 | 1.76 | 1.87 |\n        |       **0.5**        | 2.06  | 1.67  | 1.54 | 1.50 | 1.49 | 1.51 |\n        |       **0.6**        | 4.03  | 2.30  | 1.93 | 1.76 | 1.67 | 1.60 |\n        |       **0.7**        | 12.28 | 5.18  | 3.37 | 2.66 | 2.31 | 2.11 |\n        |       **0.8**        | 59.14 | 17.12 | 9.69 | 6.77 | 5.21 | 4.25 |\n\n      - Non-constant step size setting:\n\n        | $\\zeta$ \\ $\\gamma_0$ |  4   |  8   |  12  |  16  |  20  |  24  |\n        | :------------------: | :--: | :--: | :--: | :--: | :--: | :--: |\n        |       **0.3**        | 1.63 | 1.99 | 2.44 | 3.04 | 4.13 | 5.12 |\n        |       **0.4**        | 1.51 | 1.62 | 1.77 | 1.96 | 2.13 | 2.33 |\n        |       **0.5**        | 1.69 | 1.59 | 1.63 | 1.66 | 1.80 | 1.85 |\n        |       **0.6**        | 2.27 | 1.94 | 1.92 | 1.84 | 1.87 | 1.93 |\n        |       **0.7**        | 3.59 | 3.14 | 2.95 | 2.85 | 2.68 | 2.63 |\n        |       **0.8**        | 7.74 | 6.27 | 6.50 | 6.46 | 6.58 | 6.39 |\n\n      Our results indicate that the proposed estimators exhibit robustness to the choice of $\\gamma_0$ and $\\zeta$ under both constant and non-constant step size settings, with wide parameter regions yielding stable and comparable MSEs.\n\n- **Incremental technical novelty.** While our work builds on established tools, its key novelty lies in being the first to adapt them to online, robust, and privacy-preserving nonparametric learning in streaming environments, a setting not addressed in prior work. We simultaneously tackle three challenging constraints: robustness to heavy-tailed noise, rigorous differential privacy, and efficient streaming updates. Our theoretical analysis establishes non-asymptotic guarantees under both constant and decaying step sizes, with or without LDP, and shows that proper step size tuning yields optimal convergence rates, extending prior results from finite- to infinite-dimensional settings. Finally, our experiments demonstrate superior empirical performance.\n\n- **Notation.** We agree that making the relationship $u=y-f(x)$ explicit in the definition of $w_{\\tau}(u)$ will enhance readability and prevent any potential ambiguity.\n\nThank you again for your comments. We hope our responses resolve your concerns. If anything remains unclear, we’d be happy to provide further clarification."}]

Author rebuttal:

Meta-review: This paper proposes methods for online nonparametric regression that are robust to outliers, including one that satisfies local differential privacy. The reviewers generally found the results compelling, believed the problem to be important and fundamental, and thought the analysis was high-quality and interesting. These qualities all argue in favor of acceptance at NeurIPS.

While the authors are encouraged to address all reviewer comments for the final version (and of course to make the revisions promised in their responses), they should especially focus on the clarity of the notation, which was a concern for several reviewers (as acknowledged by the authors in their final remarks).
Decision: Accept (poster)