Beyond ordinary Lipschitz constraints: Differentially Private optimization with TNC
Authors: Difei Xu
Meng Ding
Zihang Xiang
Jinhui Xu
Di Wang
Venue: Accepted by TMLR ()

Abstract: We study Stochastic Convex Optimization in Differential Privacy model (DP-SCO). Unlike previous studies, here we assume the population risk function satisfies
the Tsybakov Noise Condition (TNC) with some parameter $\theta>1$, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the $\ell_2$-norm gradient of the loss has bounded $k$-th moment with $k\geq 2$. 
For the Lipschitz case with $\theta\geq 2$, we first propose an $(\epsilon, \delta)$-DP algorithms whose utility bound is $\tilde{O}\left(\left(\tilde{r}_{2k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\epsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ in high probability, where $n$ is the sample size, $d$ is the model dimension, and $\tilde{r}_{2k}$ is a term that only depends on the $2k$-th moment of the gradient.  It is notable that such an upper bound is independent of the Lipschitz constant. We then extend to the case where 
 $\theta\geq \bar{\theta}> 1$ for some known constant $\bar{\theta}$. Moreover, when the privacy budget $\epsilon$ is small enough, we show an upper bound of $\tilde{O}\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\epsilon}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$ even if the loss function is not Lipschitz. For the lower bound, we show that for any $\theta\geq 2$, the private minimax rate for $\rho$-zero Concentrated Differential Privacy is lower bounded by $\Omega\left(\left(\tilde{r}_{k}(\frac{1}{\sqrt{n}}+(\frac{\sqrt{d}}{n\sqrt{\rho}}))^\frac{k-1}{k}\right)^\frac{\theta}{\theta-1}\right)$.

Published in Transactions on Machine Learning Research (09/2025)
Beyond Ordinary Lipschitz Constraints: Differentially Private Stochastic Optimization with Tsybakov Noise Condition
Difei Xu
difei.ru@koost.cco edu.
Deportment of Statistics
King Abdullah University of Science ond Technology
Meng Ding
mengding@@buffaloccm edu
Department of Computer Sciecne
State University of New York at Buffalo
Zihang Xiang
zihong.aiang ziang edu.
Deportment of Computer Sciecne
King Abdullah University of Science and Technology
Jinhui Xu
edcu@usltc.duu.cr
School of Information Science and Technology
University of Science and Technology of China
Di Wang"
di d...angkkaustt.ed edw..
Deportment of Computer Science
King Abdullah University of Science end Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= S2=ygOyggg
Abstract
We study Stochastic Convex Optimization in the Differential Privacy model (DP-SCO). Unlike previous studies, here assume the population risk function satisfies the Tsybakov Noise Condition (TNC) with some parameter / > 1, where the Lipschitz constant of the loss could be extremely large or even unbounded, but the f--norm gradient of the loss has bounded k-th moment with k 2 2. For the Lipschitz case with 0 2 2, we first propose an
(e, 6)D algorithm whose utility bound Ô ((rul + (2 (=)) in high probability, where is the sample size, d is the model dimension, and Fiz is a term that only depends on the 2k-th moment of the gradient. It notable that such upper bound is independent of the Lipschitz constant. We then extend to the case where 0 > 0 > constant 0. Moreover, when the privacy budget is small enough, we show an upper bound of x"
for some known
even if the loss function is not Lipschitz. For the lower bound, we show that for any A 2 the private minimax rate for p-zero Concentrated Differential Privacy is lower bounded by Ω (FFa(
ò (Fa(
+ (
v
V
1
1 Introduction
Machine learning is increasingly being integrated into daily life, driven by an ever-growing volume of data. This data often includes sensitive information, which raises significant privacy concerns. In response, rogulations such as the GDPR mandate that machine learning algorithms not only effectively extract insights from training data but also uphold stringent privacy standards. Differential privacy (DP) (Dwork et al., 2006), a robust framework for ensuring statistical data privacy, has garnered substantial attention recently and has data analysis.
emerged as the leading methodology for conducting
*Corresponding author

---

Published in Transactions on Machine Learning Research (09/2025)
Differential Privacy Stochastic Convex Optimization (DP-SCO) and its empirical form, DP Empirical Risk Minimization (DP-FRM), stand as core challenges within the machine learning and differential privacy communities. These methodologies have been the focus of significant research over the past decade, beginning with seminal works like those by Chaudhuri et al. (Chaudhuri et al., 2011) and followed by mumerous influential studies (Bassily et al., 2014; Wang et al., 2017; 2019a; Wu el al., 2017; Kasiviswanathan & Jin, 2016; Kifer et al., 2012; Smith et al., 2017; Wang et al., 2018; 2019b; Huai et al., 2020; Xue et al., 2021; Asi et al., 2021a). For instance, Bassily et al. (Bassily et al., 2019) have provided near-optimal rates for DP-SCO across both convex and strongly convex loss functions. Feldman et al. (Feldman et al., 2020) have developed algorithms that boast linear time complexity, and Su et al. (Su et al., 2023) have expanded the discussion to non-Euclidean spaces.
However, the majority of existing theoretical frameworks primarily focus on scenarios where the loss function is O11)-iischhiz across all data, necessitating assumptions that the underlying data distribution is either bounded or sub-Gaussian based on output perturbation (Chaudhuri et al., 2011) and objective or gradient perturbation (Bassily et al., 2014). Yet, these assumptions may not be valid for real-world datasets, particularly those from fields like biomedicine and finance, which are known to exhibit hcavy-tailed distributions (Woolson & Clarke, 2011; Biswas et al., 2007: Ibragimov et al., 2015; Chen et al., 2023). This discrepancy can compromise the effectiveness of the algorithms in maintaining differential privacy. To bridge this gap; recent research has begun exploring DP-SCO in the context of heavy-tailed data, where the Lipschitz constant for the loss may be significantly higher or even unbounded (Wang et al., 2020; Kamath et al., 2022; Hu et al., 2022; Lowy & Razaviyayn, 2023; Tao et al., 2022a; Tian et. al., 2025; Ding et al., 2025; 2024). These studies typically assume that the gradient of the loss is bounded only in terms of its k-th moment for some h > 0, a much less stringent requirement than O(1)-Lipschizz continuity.
Such assumptions are crucial for the effectiveness of differential privacy methods
Although DP-SCO with heavy-tailed data has been extensively studied, most research has concentrated on general convex or strongly convex functions. Yet, numerous other problems exist that exceed the complexity of strongly convex functions or do not neatly fit within the oonve-tto-strongly convex spectrum. In non-private settings, several studies have managed to achieve faster convergence rates by introducing additional constraints the loss functions. It has been demonstratod that it is possible to exceed the convergence rates of general convex functions (Yang et al., 2018; Koren & Levy, 2015; van Erven et al., 2015), and some approaches have even matched the rates typical of strongly convex functions without the function actually being strongly convex (Karimi et al., 2016; Liu et al., 2018; Xu et al., 2017). Similar advancements have been observed in the context of compelling question:
algorithms (Asi et al., 2021b; Su et al., 2022; 2024). This leads to a
For the problem of DP-SCO with heavy-tailed data and special classes of population risk functions, is it possible to achieve faster rates of excess population risk than the optimal ones of general convex and (or) strongly convex cases?
In this paper, we affirmatively respond by examining certain classes of population risk functions. Specifically, we focus on the case where the population risk function possesses a large or polentially infinite Lipschitz constant and meets the Tsybakov Noise Condition (TNC) 1 encompassing strongly convex functions, SVM, l frrrguuaarizd stochastic optimization, and lincar regression with heavy-tailed data as notable examples.
Our contributions are detailed as follows (refer to Table for details).
1. We study DP-SCO where the population risk satisfies (0, A)-TCC with 0> 1. Here, the loss function is Ly-iischhtz, and the k-th moment of the loss gradient is small, where Ly < oc could be extremely large and k > 2. Based on our newly developed localization method, we propose an (e, 8)DP algorithm whose utility bound, with high probability, is Ö v me (44) ه when 0 > 2. Here, n is the sample size, d is the model dimension and ioz is a term that only depends on the 2k-th moment of the gradient. It is notable that such an upper bound independent of the Lipschitz constant.
This is also referred to as the Error Bound Condition or the Growth Condition in related literature (Láu al., 2018; Xu et. al., 2017).
2

---

Published in Transactions on Machine Learning Research (09/2025)
Table 1: Comparion with previous results on DP-SCO with different assumptions in (c, dD- (we always assume the loss is smooth). All results omit the term of log 1
8: smoothness and strong convexity. f means the result is for p-aCDP. * indicated the result holds when & = (
Upper Bound
Lowe Boun
Ascumption
(Basiily et al. 2019)
0 (++10
4
0(1)-Lipachitz
[Baeily et al., 2019)
0 + Aa)
[A4 + ,
((1)
(Kamath et al., 2021)
0 (A+ + ((gp))
0ly + vit ( (
((1) Lipschitz and bounded k-th mooment (+.2
(Kamath al., 2021)
( + di 2 _ 2لp
( + -4
0(1) sirungly convex hounded Aoth
mocuent (R 2 2)
(Asl es nl., 2022a, Su et al., 2022)
0 ( va
(++
when 02
O(1)-ippehitz under TNC wish
(Lowy& & Rasaviyann, 2023;
o Rer.
Jn + (3a)
(lagge Lipechitz, bounded
k-th moment (42 2)
[Lowy& & Razaviyayn, 2023;
o
Fu v max ((t)
bounded 8-th monnent [e2
(Lony& & Razaviyann 2023)
o Ricn
+
[(a) 11
1
(>M)
strougly convex, bounded k-th moment (A: (4227 2)
This paper
0
Ren
(22)
(ult (1)
when 2
(large) Lipechitz fanetion under TNC with 9 > 1
This paper
o
(2))
(fit) -
when 6 2 TNC with 0-1
2. We further relax the assumption that 0 2 2 to 0 > that could achieve asymptotically the same bound as the previous one. Moreover, when the privacy budget e is small enough, we show that even if the loss function is not Lipschitz, we can still get an upper bound of Ö((FA( + Ldd )ー=)
for some known 0 and propose an algorithm
3. On the lower bound side, for any 0 2 2, we show that there exists population risk function satisfying TNC with parameter 0, whose minimax population risk under p-zero Concentrated Differential Privacy is always lower bounded by 2((FF( va + ( (2 )ー
2 Related Work
DP-SCO with Heavy-tailed Data. As we mentioned previously, there is a long list of work for DP-SCO from various perspectives. Here we only focus on the work related to DP-SCO with heavy-tailed data. Generally speaking, there are two ways of modeling heavy-tailedness: The first one considers each coordinate of the loss gradient has bounded moments, while the second one assumes the norm of the loss gradient. has bounded moments, which is stronger than the first one. For the first direction, (Wang et al., 2020) provides the first study under the assumption of bounded k-th moment (k 2 2) and proposes three different ways for both convex and strongly convex loss. The bounds were later improved by (Kamath et al., 2021). Specifically, (Kamath et al., 2021) provides improved upper bounds for convex loss and optimal rates for strongly convex loss. Later, there are some works that consider different extensions. For example, (Hu et al., 2022) extends to the nigh-dimensional and polyhedral cases, (Tao et al., 2022a) extends to the case where the gradient only has (1 + v)-th moment with (0, 1], and (Wang & Xu, 2022; 2025) considers the fi-regression. For the sccond direction, (Lowy & Razaviyayn, 2023) provides a comprchensive study for both convex and strongly convex loss. In detail, for Lipschitz loss whose gradient. has k-th moment, they provide upper bounds that are independent of the Lipschitz constant. In contrast to the work of (Lowy & Razaviyayn, 2023), our approach builds upon Theorem 6 from (Lowy & Razaviyayn, 2023). We then derive the probaiiiyyyylity upper bound and extend these results to population risks satisfying the Tsybakov Noise Condition (TNC) in subsequent sections. Notably, when 0 2, our findings align with their results for
3

---

Published in Transactions on Machine Learning Research (09/2025)
strongly convex losses, while simultaneussly generalizing their underlying assumptions. Moreover, the results in (Towy & Razaviyayn, 2023) are in expectation form while we provide new algorithms, and our results are in the high probability form. What is notable is that (Asi et al., 2024) proposes a reduction-based method to deal with data with heavy-tailed gradients, deriving results analogous to ours. Novertheless, we apply different techniques under distinct assumptions. Specifically, their framework relies on a uniform Lipschitz assumption, which imposes more restrictive conditions compared to our method. Furthermore, our analysis extends to TNC, and subsequent theoretical investigation demonstrates that the Lipschitz requirement can be entirely eliminated under certain conditions.
DP for Hcavy-tailed Data. In addition to DP-SCO, there is also some work on DP for heavy-tailed data. (Barber & Duchi, 2014) provided the first study on private mean estimation for distributions with a bounded moment, which has been extended by (Kamath et al., 2020; Liu et al., 2021; Brunel & Meella-Medina, 2020) recently. However, these methods cannot be applicd to our problem as these results are all in the expectation form. Motivated by (Wang et al., 2020), we later consider statistical guarantoes of DP Expectation Maximization and apply them to the Gaussian Mixture Model. (Wu el. al., 2023; Tao et al., 2022b; Wu el al., 2024) considers private reinforcement learning and bandit learning where the reward follows a heavy-tailed distribution. However, since the reward is scalar, these methods are not applicable to our problem.
Loss functions with TNC. While most of this paper focuses on loss functions that are either convex or strongly convex, many loss functions fall between these two categories. That is, they are not strongly convex, but their statistical rate is better than purely convex losses. For TNC and Lipschitz loss functions, the best-known current rate is ((((z)))1)) (Liu et al., 2018), which corresponds to the first term in our upper bounds. In Theorem 5, we demonstrate that this upper bound is tight for 0 2 2. A comparison to the non-private setting will be included in the final version of the paper.
Our methods introduce novel technical challenges compared to non-private approaches. The key innovation lies in our analysis, which is based on algorithmic stability and a newly developed localized and clipped algorithm (Algorithm 3), which has not been previously studied. Specifically, Algorithm 4 is inspired by Algorithm 2 in (Liu et al., 2018). However, while the base algorithm in (Liu et al., 2018) is simple averaged version of projected SGD, our Algorithm 3 is signifieantly more complex. One major technical challenge is that Algorithm 2 in (Liu et al., 2018) assumes Lipschitz loss function with fixed Lipschitz constant. Consequently, their bounds rely on this constant. In contrast, we address scenarios where the Lipschitz parameter can be extremely large. Therefore, we developed a new base algorithm that removes dependence on this parameter and instead utilizes moments.
3 Preliminaries
Definition 1 (Differential Privacy (Dwork et al., 2006)). Given data universe X, we say that two datasets S, C X are neighbors if they differ by only one entry, which is denoted as S ~ S'. A randomized algorithm A is (e, Jdifffrrrrrt private (DP) if for all neighboring datascts S, and for all events E in the output space of A, the following holds
P(A(S) E E) & <FP(((()) E EE)+ 6
6f 0, we call algorithm E-DP.
Definition 2 (zCDP (Bun & Steinke, 2016)). A randomized algorithm A is prero-coneentatee-fffeeniilll private (zCDP) if for all neighboring datasets S, S" and a E (1,00), we have (a(A)))AA(())) & pa, where D., is the a-Rényi divergence between A(S) and A(S").
Remark 1. In this paper, we focus on (s, OP for upper bounds and p=zCDP for lower bounds, and we mainly use the Gaussian mechanism to guarantee the DP property. For Algorithms 1-5, which are based on stability analysis and the Gaussian mechanism, they operate as one-pass algorithms without sub-sampling. As a result, they can easily meet the requirements for CDP. However, a challenge arises with Algorithm 6. In this case, we employ privacy amplification via shuffling to reduce the noise. Currently, privacy amplification via shuffling is only applicable to and (e, (D,D), and no version exists for zCDP. To maintain consistency throughout the paper, we use O)DP) for all our upper bounds.
4

---

Published in Transactions on Machine Learning Research (09/2025)
Definition 3 (Gaussian Mechanism). Given any function q: Xm + R the Gaussian mechanism is defined as ((5) + where & No, 1032(0))o0(11)) la); where A2(1) is the lg-sensitivity of the function g. d.e., A2(1) = sups-s' (1) (22) Gaussian mechanism preserves (e. for 0 < <,, < 1.
Definition 4 (DP-SCO (Bassily et al., 2014)). Given a dataset S ( ..) from data universe X where are i.i.d. samples from some unknown distribution D, convex loss function f(-,)) ((:-), and convex constraint set W S R", Differentially Private Stochastic Convex Optimization (DP-SCO) is to find wpriv so as to minimize the population risk, i.e., F(w) Ex-Dlf(w,at x)] with the guarantee of being differentially private. The utility of the algorithm is mcasured by the (erpected) excess population risk, that is
[A(F(WPri)) min F(w), wEW
where the expectation of A taken over all the randomness of the algorithm. Besides the population risk, we may also measure the empirical risk of dataset S: F(w,S) = Ei=1 J(,,
Definition 5 (Lipschitz). A function f W + R is L-Lipschitz over the domain W if for all w, w' e W, [f(w) - f(w") < L|[w w') 12-
Definition 6 (Smoothness). A function f: W + R is 8-smooth over the domain W if for all w. w E W, (w) < [(w') + (VI(w"), w - w²) + _ ||w - w/ 112-
Definition 7 (Strongly Convex). A function F; W + R is X-strongly convex over the domain W if, for all w, w/ E W, F(w) + (VF(w), w/ - w) + 21lu/ w < F(w').
Previous work on DP-SCO only focused on cases where the loss function is either convex or strongly convex (Bassily et al., 2019; Feldman et al., 2020). In this paper, we mainly examine the case where the population risk satisfies the Tsybakov Noise Condition (TNC) (Ramdas & Singh, 2012; Liu et al., 2018; Ramdas & Singh, 2013), which has been extensively studied and has been shown that it could achieve faster rates than the optimal one of general convex loss functions in the non-private case, Below, we introduce the definition of TNC.
Definition 8 (Tsybakov Noise Condition). For a convex function F(.), let W. = arg wen F F(w) denote the optimal set and for any w E W, let w² arg min.ew. ||u - w|l2 denote the projection of w onto the optimal set W. The function F' satisfies (0,A)-TNG for some 0 > and x 0 if, for any w W, the following inequality holds:
F(w) - -F("") 2 M||l w w=112-
(1)
From the definition of TNC and Definition 7, we can see that a A-strong convex function is (2, J-TNC. In Examples after Theorem 2, we deomenstrate how TNC can be verified in practical situations. Moreover, if a function is (0, A)-TNC, then it is also (0', AN-NNC for any < 8'. Throughout the paper, we assume that 0 is a constant and thus we omit the term of d in the Big-O notation is a constant.
Lemma 1 (Lemma 2 in (Ramdas & Singh, 2012)). Tf the function F(.) is (0,A)-TNC and L.p-ápscchlzz then we have || - w²112 < (Lz2-1))=- and F(w) F(w") & (1クー-1 for all w E W, where w" is defined as in Definition 8.
As mentioned earlier, our primary focus here is on cases where the loss function's Lipschitz constant is sufficiently large or even infinite. In such cases, we may seek alternative terms to replace the Lipschitz constant. Motivated by previous work on DP-SCO with heavy-tailed gradients, we consider the moments of the gradient. Specifically, we assume that the stochastic gradient distributions have bounded k-th moment. for some k *>2 2:
Assumption 1. There exists k 3 2 and p(k) > 0 such that E [suPwew [V x)1]]] < F(0), where Fi = 1/ 1/k Moreover, we assume the constrained set W is bounded with diameter D.
If the loss function is Lipschici, we can always observe that Fx & Ly sup [[ 122 Moreover, 7 could be far less than the Lipschitz constant.
5

---

Published in Transactions on Machine Learning Research (09/2025)
To state subsequent theoretical results more clearly, we introduce some additional notations. For batch of data X E X we define the k-th empirical moment of f(w,,), by
Fm (x) = sup wEW
For X ~ Dm,, we denote the k-th expected empirical moment by
e (X) (k),
and let
Fk.m == (C 12/k)
Note that Fk,1 = Fjg- We define Rg.. V Ei=1 17 kin where n4 2 and / = logg n. Actually, Re a weighted average of the expected empirical moments for distinct batch sizes, a constant used in the excess risk upper bounds, where we give more weight to I'm for large m. The following lemma indicates that is smaller than Fk-
Lemma ((Lowy & Razaviyayn, 2023)). Under Assumption 1, we have: f(t) = =t Thus, we have Ra. & Fk.
> (1))
4 Large Lipschitz Constant Case
Algorithm ClippedMean((z)PP)) C)
Input: Z= (2 C' 0,
12
1: Compute == 1 " Σ [z+) where (z) = argmin yeBe 11y - 21I2 denotes the projection onto the &
ball C.C. Return 0
In this section, we will focus on the population risk function satisfying (0, A)-TNC, and the Lipschitz constant of the loss is extremely large (but finite). Before that, we first propose a novel localized noisy stochastic gradient method whose excess population risk is independent of the Lipschitz constant for general convex loss. See Algorithm 3 for details.
In Algorithm 3, first partition the dataset into O(log2 n) subsets where the i-th set has 0(2-'n) samples. In the i-th iteration, we use the i-th set and construct lz-regularized empirical risk function F; with hyperparameter X; in step 5. Moreover, based on the current model w;-1, construct the W; with diameter exponential decay D,. To handle a large Lipschitz constant and to solve the lz-regularized empirical risk, we adopt a clipped gradient descent method (Algorithm 2) with a clip threshold C₁, where we use clipped gradients (Algorithn 1) to update our model instead of the original gradient. After T; ilerations, add Gaussian noise based on the stability of our clipped gradient descent ensure (P. In the following, show Algorithm 3 could achieve rate Ó(max dlog 1 ( with specific parameters \; T and C.
set
Theorem 1. Under Assumplion 1, suppose that f(,, is a-smooth and Lipiscchil with Lg < 0o for every T. Then, for any O < E & & < 8 < and n & 1 for all i, Algorithm 3 is (), Let p 2 1 such
that Lg & np/2 Ran (4a + (og() = ). For any 0 < B with probabilily at least 1 - 3, il holds thot
En
F(wi) - F(w") <ō
+ Ren Ri 1 7/
+ /1/og11/0)
Dolog(1/B) 20+1 /n
where the Big-ō notation omits all logarithmic terms (il is the same for other upper bounds).

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm Clipped Regularized Gradient Method
Input: Datasct S E X", iteration number T, stepsize 7, clipping threshold C, regularization À > 0, constraint set W and initialization wo W.
1: for all E [ 1] do
(w.) ::el:pppeeeeea(((//(( mi))==ii)) C) for gradients V ([,,,
W/+1 Iww[w, (w;) X(u; wo))l
end for Return WT
Algorithm Localized Noisy Clipped Gradient Method for DP-SCO)LNC-GMM((un, 7) n, W)
Input: Dataset X stepsize 7) clipping threshold 1o5," privacy parameter E, 6, hyperparameter p.
initialization wo E W.
Let == logg nt
for all E [1] do
Set 2 2-,,, TJE 11, x; when i > 2, and X1
91nd FF T,
2 ( and D; = 2L1. 3.
Draw a new batch B; of IB: samples from S without replacement. Denote F(w)) == 1 n, Ejes, fw,
w| w;-1l12
Use Algorithm with initialization w;-1 1 to minimize F over W: == {w E W| ||u w:-1l Il D2} for 11/k and stepsize 7/i Let w; be the
T; iterations with clipping threshold C F2 (11/)) log(n)
output of Algorithm 2.
7: Set & ~ (0, La where o; 8C, log
Set w/; = 0; + &r-
end for
10: Return the final iterate wn
Remark 2. Previous work DP-SCO such (Wang et al., 2017; Bassily et al., 2014), Lipschitz is still required for the loss function; though, it disappears in the final excess risk upper bound. And due to the property of worst-case stability and our assumption that L, can be controlled by np/2 RZk ( +
( /8ogo///8logn
gn *r²) for sufficiently large p, we reach the upper bound with high probability without Ly in the final result. Compared to (Lowy & Razaviyayn, 2023), the main difference is that result is in the high probability form while (Lowy & Razaviyayn, 2023) is only in the expectation form. Specifically, to achieve a high probability result, instead of adding Gaussian noise to the gradient, use the stability of the gradient descent. However, we cannot directly use the stability result in (Hardt et al., 2015) here, which depends on the Lipschitz constant, making a large noise. We show that by using clipping, the stability now only depends on the clipping threshold.
Based on our novel locality algorithm, we then apply it to TNC functions. See Algorithm 4 for details. Specifically, we partition the dataset into several subsets of equal size. As the iteration number increases, we consider constrained set centered at the current parameter with smaller diameter and learning rate in Algorithm 3.
Theorem 2. Under Assumption 1 and suppose that the population risk function F(-) is (9, A)-TNC with 2 2, and f(,,z) is a-smooth and Ly-Lipschitz for each. x. Additionally, take p 2 1 such that L,f & then algorithm 4 is (D, Moreover, for sufficiently large such that < , with probability at least 1 - B, we have
1p/2 Rzn /n + 1
2n
F F(0m) F (w") 5 RoR
1 Tii
+
d (og()
k-1
log n log (1/3) log(log//// 20 1/1
en
7

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 4 Private Stochastic Approsimation(u, Ro)
Input: Datasel S E X, initial point W1 W, privacy parameter and 6, hyperparameter p, initial diameter
Ro-
2n 1: Set wh = W 1 loge loga ni
1, no
Then partition the dateset S into m disjoint subsets,
namely, (Si,... ........................ .5m) with each |Si| = no-
for all E [m] do
and R₁ = R 4: Denote in = LNC-GM (11-1, 71, n1, W), and constrained set W n (((0) RI-1).
3: Set R min
Eng
Vdllog n
2
Rak.n
13V fog no (og(1/9)
5: end for
Return 2m
We note that there is no dependence on p in the final bound in Theorem 1 and 2. p is used to control the Lipschitz constant thus we can remove the Lipschitz constant from the final bound. We can see that in the proof of Theorem 1, there exists a term with n² both in the numerators and denominators. By assuming that Ly is controlled by the O /2) and choosing specific y, we can eliminate the p in the final bound. A similar result holds for Theorem 2.
Remark 3. In the case of O(L)-Lipschitz loss under TNC, compared with the optimal rate ((((}, +
)))+))) in (Asi et al., 2021b), our improved result gets rid of the dependence of Lipschitz constant, which could be extremely large. Moreover, when 0 2, i.e., the population risk is strongly convex, our result covers the result in (Lowy & Razaviyayn, 2023). Thus, our result is generalized upper bound. It is also notable that our upper bound is independent of the diameter of the constrained set and the Lipschitz-smootthess parameter. In Algorithm 4, one need the projection onto the ball W R(-1) in each iteration of the Phased-SGD in each phase. This could be solved using Dykstra's algorithm (Dykstra, 1983; Boyle & Dykstra, 1986).
Example. We consider the & constrained 4--orrm linear regression, which has been studied in (Xu et al., 2017) and satisfies TNC with 0 = (Liu et al., 2018). Specifically, it can be written as the following.
min F(w) - E[((( - 4) |eli1
(2)
When y is bounded by O()) and x follows a truncated normal Gaussian distribution at [-n, n]]. Then we can see that the loss function is Poly(n))Lipschitzz but its 2k-th moment is O(1). In this case, our bound in equation 2 is much smaller than the previous results in (Asi et al., 2021b; Su et al., 2024).
Example. We also investigate the 4--norm regularized logistic regression problem with regularization parameter À subject to the unit fz-norm ball constraint. This formulation exhibits X-strong convexity and consequently satisfies the TNC with = 2. Specifically, let hw) = ite-to.w) denote the logistic function and y E {0. 1} represent the binary response variable. The optimization problem can be formulated as
hew (x) min F(w)= Elgylog (1-v) log(1 1 hw (ww wll221
2 11012.
(3)
Suppose that ||x||| S R or x is sub-Gaussian and is bounded by some constant. Under these conditions, we can derive the 2k-th moment for equation 3, which is O(1) for fixed k and R. Under these circumstances, our approach yields improvements over the previous results established in (Liu et al., 2018).
So far, we have proposed an algorithm for TNC. Nevertheless, we also find that Theorem needs a strong assumption on 0, i.e 0 >> 2. Thus, a direct question that occurs us is whether we can further improve the upper bound. To conquer the vistavantage of the above algorithm, we propose the following. We assume 0 is unknown but bigger than some definite 0 >>> 1. Then we divide the whole dataset into subsets with distinct elements, detailly I = [loog 2)- log log n2] with n, 2 (log los3 samples for each subset. Then we

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm Iterated Localized Noisy Clipped Gradient Method
Input: Datasct S E X", initial point wo E W, privacy parameter and 6, paramcter p, initial diameter Ro- 1: Partite the data S into 1 disjoint subsets (S ,t),, where I = [[logn 2) log log and for each
E [] |S = n4 = 2 () [)ogg))oos" lo033
for all 1,... do
3: Let W = LMC w4-1, W), where n
R__1 min ( by R0, 20,
en
h-1
2
Vdlog n
ng
1
and R R
1-1
R, 2 13g log(1/9)
4: end for
Return w7
run the Algorithm for / times while each phase implements on the i-th subset and is initialized at the output of the previous one.
Theorem 3. Under Assumption 1 and assume that the loss function F(-) satisfies (0, A)-TNO with parameter
0 0 for some definile constant O, and [(,,z) is conver, a smooth and LipLiccchita for each x. Algorithm 5 is DD for ony 2 (1g()/)), and take p 2 such that L & np/2 R2 &nP/2RaR.N /n (Válog(1/8) log k-1 Moreover, if the sample size n sufficiently large such that $ at least B
en
bog log Tog I and n) < 1, we have with probability
F (wn) F (w)) 2 (
1 Vn
(110) *=") )
/ /log(1/// 2 Vn
+
8-
en
Remark 4. We pause to have another glimpse of Algorithm 4 and Algorithm 5. Note that they have a similar procedure to take the dataset apart, while the number of each subset is the same in Algorithm 5 and increases in Algorithm as the itcration grows. And the set we project on also varies between Algorithm 4 and 5.
5 Lower Bounds
In this section, will show that the above upper bound is nearly optimal (if F2x and Fs are asymptotically the same) by providing lower bounds of the private minimax rate for p-zCDP. Specifically, for sample space X' C Rd and collection of distributions P over X, we define the function class FP F()) the set of population risk functions from Rd + IR that satisfy (0, 1)-TNC and their loss satisfies Assumption 1. We define the coistrained minimax risk
M(W,P, )()) inf max
(FDDE)((((A()) - min F(w)], wEW
AEQ(A) PXPEF((PAA)
where (p))) is the set of all p-zCDP algorithms. We will show the following two results for different sample spaces and constraint sets.
Theorem 4. For any 0, 2 (((())))) > 0, denote X = [+p fu jd U {0} with is (f(()) and W B, 2/a
with (8 ( and p nyp then, if is large enough such that 2 22 vd), we have the following
lower bound"
M(W.P. ((K)) 2 Ω (Fall
vd -
)
Vpm
Theorem 5. For any k 2 2, Fx > 0, denote X = ( Ps ld and W = B, with r = ( then, if
20d
n 2 21 (d),), we have the following lower bound
(2((())
M(W.P. FM)) 2 2
'nn
9

---

Published in Transactions on Machine Learning Research (09/2025)
Remark 5. First, it is notable that although the upper bounds in Section are for (e,8)-DP, can easily extend to the pzCDDP case we used the Gaussian mechanism and parallel theorem to guarantee DP, which also holds for zCDP (Bun & Steinke, 2016). The only difference is replacing the term O /og by O vo Thus, from this side, combining with Theorem and 5, we can see the upper bound is nearly optimal for p>CDP the general case if F2k (since R2n. < F2x) and F. are asymptotically the same. Secondly, in the Lipschitz case for (e, (),P), (Asi et al., 2021a) proved the lower bound result via a reduction to the ERM problem for general convex loss. However, their reduction cannot be applied to our problem as their proof heavily relies the O(I)-Lipschitz condition, which is not satisfied for our loss. For e-DP, (Asi et al., 2021a) considered the empirical risk and used the packing argument for the lower bound, which cannot be applied to our problem as our loss is not constant Lipschitz. In our proof, we directly considered the population risk Fr(w)= = - (w, Ep(z]) + || for some data distribution P and used private Fano's 's lemma to prove the lower bound.
Algorithm 6 Permuted Noisy Clipped Accelerated SGD for Heavy-Tailed DP SCO (PNCA-SGD)
Input: Data S' Xm" iteration number T, stepsize parameters (ne) (at)em with on 1, private paratemter e, 6, initialization Wp-
1: Randomly permute the data and denote the permuted data as {z1,- (nn)
2: Initialize ng = wo.
3: for all E [T] do
4: wit : (1 - at) w + W1:W4-1.
Draw new batch B, (without replacement) of n/T samples from S.
CT Fe. (m=mid) Clap ((VS (witdd 2x) nEB, 7: (:C)+((C +Gi, where & ~N(00, 0² 0 00
n²e"
1/k
and C= Fm
Vdlog(1/6)
at (VFi (witid)
w) + mt |1,-1 w/|3]
7: We arg weW
w a (1 ai)) -
end for Return w/
6 Relax the Lipschitz Assumption
In the previous section, we have considered the Lipschitx case and show that under the TNC, compared to that for the general convex loss, it is possible to get improved excess population risk that is independent of the Lipschitz constant. There are still two questions left: (1) Compared to the previous studics on DP-SCO with heavy-tailed gradient such as (Wang et al., 2020; Kamath et al., 2021), our above upper bounds still need the finite Lipschitz condition; (2) We can see our upper bounds depend on R2i.n < f2x while the lower bounds only depend on Fg. Thus, there is a gap for the moment term. In this section, we aim to address these two issues. Specifically, we will show that even if the loss function not Lipschitz, it is still possible get the same upper bound as in the above section when is small enough. Moreover, we improve the dependency from R2E, to Fx.
Specifically, our main method, Algorithm 7, shares a similar idea as in Algorithm 5 with different parameters and base algorithm. Specifically, rather than using Algorithm 3, here we propose Algorithm 6 as our base algorithm, which a shuffled, clipped, and private version of the accelerated SGD. Specifically, step we randomly shuffle the data for privacy amplification (Feldman el al., 2022). Then, in each iteration, we clip the gradients and add Gaussian noise to ensure DP. We can show that with some parameters, the output could achieve upper bound similar to Theorem 1 even if the loss is not Lipschitz.
Theorem 6. For any O(y log n//6 and O < 8 < 1, Algorithm 6 is (c. D)DP. Moreover, under Assumption and assuming function F is B-smooth with the diameter D over w E W, then the output of Algoritiem 6, by
10

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm Iterated PNCA-SGD (Wo: n. W.
Input: Dataset E X", initial point wo W, privacy parameter and 6. 1: Partite the data S into k disjoint subsets ( ( where k = [[log, 2) log log n|, and for cach
EE [k], [ = n, "//1n/(oo,,
2: for all I,... , do
Let W/ PNCA-SGD (1 th ne, W), where the AC-SA runs on the t-th subset F.rr (e,8)-DP, x(+1))> at = 242
and R₁ R
2
4: end for Return u'
selecting the following T,
T T=minf
3D
en
25
BD
n//4
Tk
V d
log (1/6)
Pkk
we have
1 Vn
dllog (1/8) b-
F E O EF (w 0g
F&D( +
en
Note that (Lowy & Razaviyayn 2023) also proposes a private accelerated SGD. However, their bound is sub-optimal (see the second row in Table 1). Here, we leverage privacy amplification via shuffling to reduce the noise added to each iteration. Thus, we can get the optimal rate here. We note that this also the first. result that can achieve the optimal rate for the general convex function without the Lipschitz assumption. Based on this result, we have the following theorem for Algorithm 7.
Theorem 7. For any DlV/oan and assuming function is B-smooth, then we have
O(V /Loo 1og )r and O < < 1, Algorithm is (e, ().6)-DP. Moreover, under Assumption a
(1
/dloo((1//)) + )) )-2))
(F(#)) - F(w") < δ A ( +
(4)
Sn
Compared with the results in the above section, we can see the result in Theorem which is due to the noisy clipped gradient in Algorithm 6. Moreover, the constraint of E = O( log n/ō comes from the results of privacy amplification via shuffling (Feldman et al., 2022). We leave these two assumptions be relaxed for future research. Moreover, the improvement from Rex.n to F& is due the different results between Theorem and 1.
the expectation form,
7
Numerical Experiments
In this section, we conduct series of numerical experiments with three different datasets to show the performance of our algorithms.
7.1
Experimental Settings
For instances satisfying TNC, we investigate two representative examples that have been thoroughly analyzed in existing literature. We first. consider the 4-norm linear regression. This setting satisfies TNC with parameter 0 = 4. More preciscly, we have
min F(w) A B[((w,)) - -
WED
We also investigate the fy-norm regularized logistic regression problem with regularization parameter X. This formulation exhibits A-strong convexity and consequently satisfies the (2, Aj-TNC condition. Specifically, let.
11

---

Published in Transactions on Machine Learning Research (09/2025)
(x) 1+ denote the logistic function and y E {0, 1} represent the binary response variable. The optimization problem can be formulated as follows:
2 2 1
min F(w) A E (-y log hm (2)) (1 () log(1 how (x))) WED
Baselines Although our investigation covers both (e, 6)DDP and s-DP, practice, we prefer (e, 8)-DP. Therefore, this section dedicated to the performance of O)-D.. For the problem mentioned before, we adopt DP-SGD as baseline.
DP-SGD (Abadi et al., 2016). The foundational DP-SGD algorithm was originally proposed by (Bassily al., 2014). However, its practical efficacy in the initial formulation proved inadequate, as evidenced by (Wang al., 2017). To overcome the deficiencies, we adopt the batched and clipped variant proposed by (Abadi et al., 2016), which demonstrates substantial improvement. Although the algorithm of (Abadi et al., 2016) with arbitrary clipping thresholds does not provide theoretical convergence guarantees for excess population risk, it achieves superior empirical performance. Our experimental framework incorporates systematic hyperparameter tuning to optimize results, with findings reported using some selected parameters.
LNC-GM (Algorithm 3). LNC-GM could be considered as the state-of-the-art method for DP-SCO problem with smooth convex loss functions, especilally with large Lipschitz constant.
PNCA-SGD (Algorithm 6). PNCA-SGD could be regarded the state-of-the-arl algorithm for DP-SCO problem withour requirement of Lipschitzness for the smooth loss functions.
Dataset and Parameter Settings We will implement the LNC-GM algorithm on three real-world datasets from the libsvm website, namely a8a (n 22, 696, d 123 for training, and n 9, 865 for testing), a9a (n 32, 561, d = 123 for training, and 16, 281 for testing),and w7a (n 24, 692, d 300 for training, and n 25, 057 for testing).
We study the above-mentioned TNC problem and their corresponding testing errors with various sample sizes and privacy budgets 8. When performing the results for different sample sizes, we will fix = 8 and consider different sample sizes n that are at most 3.5 10a. When performing the results for different privacy budgets E, we will use n = 10 samples and choose ε = {0.5, 1.0, 1.5, 2.0, 3.0, 4.0, 5.0} respectively. We will fix 8 ..r for all experiments.
7.2 Experiment Results
Figures are attached in the Appendix. Figures 1, 2, and 3 present the results of 44-norm linear regression for our proposed methods (LNC-GM and PNCA-SGD) compared the baseline DP-SGD algorithm. Our base algorithm demonstrates performance comparable to or superior to DP-SGD in most cases, with closely matched results on the w7a. dataset. Without dataset normalization, the uniform Lipschitz assumption no longer holds. Our LNC-GM algorithm can accommodate large Lipschitz constants, which explains why its performance is not inferior to DP-SGD and even outperforms it on the a8a and a9a datasets. The relaxation of the Lipschitz requirement represents a key characteristic of PNCA-SGD, albeit requiring a small privacy budget 6. As illustrated in Figures la and 2a, a small value of e ensures that PNCA-SGD achieves superior performance compared DP-SGD.
Figure 4 5 6 shows the results of & norm regularized logistic regression. DP-SGD is better on the two datasets a8a and a9a, where the gap for logistic regression between DP-SGD and LNC-GM is acceptable. However, we can see through Figure 6, the performance w7a of our two methods is better than DP-SGD, both for varying privacy budget e and different sample sizes, where PNCA-SGD converges faster than the others given large sample size as expected. Although LNC-GM does not achieve the same convergence rate as DP-SGD, the tradc-off is acceptable given that our approach operates under considerably more relaxed conditions. In contrast, PNCA-SGD not only eliminates the Lipschitz requirement but also demonstrates superior convergence performance compared to DGDSGD. When compared to DP-SGD, PNCA-SGD achieves
12

---

Published in Transactions on Machine Learning Research (09/2025)
comparable test MSE performance and demonstrates superior performance given sufficiently large sample sizes.
8 Conclusion
In this paper, we address the challenge of DP-SCO with heavy-tailed data. We establish bounds for Lipschitz loss functions using the k-th moments, without relying on the Lipschitz constant. A key contribution of our work is the elimination of the Lipschitz requirement for loss functions. Furthermore, we introduce the Tsybakov Noise Condition as unifying framework for our analysis. We reveal the fundamental trade-off between privacy preservation and utility, offering comprehensive insights into the interplay between privacy guarantees and data quality.
Acknowledgments
Di Wang and Difci Xu are supported in part by the funding BAS/1/1669-01-011 URF/1/4663-01-01 REI/1 REI/1/5232-014 /5232-01-01, RE1/1/5332-01-01, and URF/1/5508-01-01 from KAUST, and funding from KAUST Center of Excellence for Generative AI, under award number 5940.
References
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications securily, pp. 308 318, 2016.
Jayadev Acharya, Zileng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Leorning Theory, pp. 48-78 PMLR, 2021.
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pp. 383-392. PMLR, 2021a.
Hilal Asi, Daniel Lévy, and John C Duchi. Adapting function difficulty and growth conditions in private optimization. Advances in Neural Information Processing Systems, 34:19069 190811, 2021b.
Hilal Asi, Daogao Liu, and Kevin Tian. Private stochastic convex optimization with heavy tails: Near- optimality from simple reductions. Advances in Newral Information Processing Systems, 37:59174-59215, 2024.
Rina Foygel Barber and John C. Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint xrxiv: 14 42.44411, 2014.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473. IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. arXio preprint ar Xix:110900 0908009970, 2019.
Atanu Biswas, Sujay Datta, Jason P Fine, and Mark R Segal. Statistical advonces in the biomedical science. Wiley Online Library, 2007.
James P Boyle and Richard L Dykstra. A method for finding projections onto the intersection of convex sets in hilbert spaces. In Advances in order restricted statistical inference, pp. 28-47, Springer, 1986.
Eireoo-Emmmauel Brunel and Marco Avella-Medina. Propose, test, release: Differentially private estimation with high probability. arXio preprint ar 087774 2020.
13

---

Published in Transactions on Machine Learning Research (09/2025)
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pp. 658. Springer, 2016.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Junren Chen, Michael K Ng, and Di Wang- Quantizing heavy-tailed data in statistical estimation:(near) minimax rates, covariate quantization, and uniform recovery. IEEE Trunsactions on Information Theory, 70(3):2003-2033 20388, 2023.
Meng Ding, Mingxi Lei, Liyang Zhu, Shaowei Wang, Di Wang, and Jinhui Xu. Revisiting differentially private relu regression. Advunces in Newral Information Processing Systems, 37:55470- --555700-55566, 2024.
Meng Ding, Mingxi Lei, Shaowei Wang, Tianhang Zheng, Di Wang, and Jinhui Xu. Nearly optimal differentially private relu regression. In The 41t Conference on Uncerlainly in Artificial Intelligence, 2025.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptogrophy conference, pp. 265 284. Springer, 2006.
Richard L Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78(384):837-844 842, 1983.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279. PMLR, 2019.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Compuling, pp. 439-449 2020.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 TEFE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954 964. IEEE, 2022.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv e-prints, pp. arXiv-1509, 2015.
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM ZIGMOD-SIGACT-SICAA Symposium on Principles of Database Systems, pp. 227-236 2022.
Mengdi Huai, Di Wang, Chenglin Miao, Jinhui Xu, and Aidong Zhang. Pairwise learning with differential privacy guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 694-701, 2020.
Marat Ibragimov, Rustam Tbragimov, and Johan Walden. Heavy-tailed distributions and robustness in economics and finance, volume 214. Springer, 2015.
Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distribu-
tions. In Proceedings of 33rd Conference on Learning Theory (COLT), pp. 2204-2235, 2020.
Gautam Kamath, Xinglu Liu, and Huanyu Zhang, Improved rates for differentially private stochastic convex optimization with heavy-tailed data. arXie preprint arXiv:2106.01: 01336, 2021.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference Machine Learning, pp. 10633-10660. PMLR, 2022.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-lojasiewie condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for high- dimensional learning. In International Conference on Machine Learning, pp. 488-4984 2016.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference Learning Theory, pp. 25-1, 2012.
Tomer Koren and Kfir Y Levy. Fast rates for exp-concave empirical risk minimization. In NIPS, pp. 1477-1485, 2015.
Mingrui Liu, Xiaoxuan Zhang, Lijun Zhang, Rong Jin, and Tianbao Yang. Fast rates of erm and stochastic approximation: Adaptive to error bound conditions. arXiv preprint 3Xxx:8805044777 2018.
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. arXiv preprint arXiv:2102, 09159, 2021.
Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses. In International Conference on Algorithmic Learning Theory, pp. 186-1054. PMLR, 2023.
Frank D McSherry. Privacy integrated queries: an extensible platform for Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp. 19 19-30, 2009.
data analysis. In
Aaditya Ramdas and Aarti Singh. Optimal rates for first-order stochastic convex optimization under tsybakov noise condition. ar preprint 1rXi::1207.300 2012.
Aaditya Ramdas and Aarti Singh. Algorithmic connections between active learning and stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pp. 339-33330 353.. Springer, 2013.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private lcarning? In 2017 IEEE Symposium on Security and Privacy (SP), pp. 58-77. IEEE, 2017.
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of private stochastic convex optimization. In International Conference on Algorithmic Learning Theory, pp. 995-1002. PMLR, 2022.
Jinyan Su, Changhong Zhao, and Di Wang, Differentially private stochastic convex optimization in (non)- euclidean space revisited. In Uncertainty in Artificial Intelligence, pp. 2026-2035. PMLR, 2023.
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25(114):1-41, 2024.
Youming Tao, Yulian Wu, Xiuzhen Cheng, and Di Wang 0015. Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In IJCAI, pp. 3947-3953. 2022a.
Youning Tao, Yulian Wu, Peng Zhao, and Di Wang. Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits. In International Conference Artificial Intelligence and Statistics, pp- 1546 1574, PMLR, 2022b.
Xizhi Tian, Meng Ding, Touming Tao, Zihang Xiang, and Di Wang. Differentially private sparse lincar regression with heavy-tailed responses. arXiv preprint or arXi::2506.0643 2025.
Tim van Erven, Peter D Grünwald, Nishant A Mchta, Mark D Reid, and Robert C Williamson. Fast rates in statistical and ouline learning. Journal of Machine Learning Research, 16:1793 1861, 2015.
Di Wang and Jinhui Xu. Differentially private 4--nrrm lincar regression with heavy-tailed data. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 1856 1861. IEEE, 2022.
Di Wang and Jinhui Xu. Private least absolute deviations with heavy-tailed data. Theoretical Computer Science, 1030:115071, 2025.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pp. 2722-22222 22731, 2017.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Di Wang, Marco Gaboardi, and Jinhui Xu. Empirical risk minimization in non-interactive local differential privacy revisited. In Aduances in Neural Information Processing Systems, pp. 965-974, 2018.
Di Wang, Changyou Chen, and Jinhui Xu. Differentially private empirical risk minimization with non-convex loss functions. In International Conference on Machine Learning, pp. 6526-6535, 2019a.
Di Wang, Adam Smith, and Jinhui Xu. Noninteractive locally private learning of linear models via polynomial approximations. In Algorithmic Learning Theery, pp. 897 902, 2019b.
Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex oplimization with heavy-tailed data. In International Conference on Machine Learning, pp. 10081-10911. PMLR, 2020.
Robert F Woolson and William R Clarke. Statistical methods for the analysis of biomedical data, volume 371.
John Wiley & Sons, 2011.
Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent- based analytics. In Proceedings of the 2017 ACM International Conference Managemend of Data, pp. 1307-1322. ACM, 2017.
Yulian Wu, Xingyu Zhou, Sayak Ray Chowdhury, and Di Wang. Differentially private episodic reinforcement learning with heavy-tailed rewards. In International Conference on Machine Learning, pp. 37880 37918. PMLR, 2023.
Yulian Wu, Xingyu Zhou, Youming Tao, and Di Wang. On private and robust bandits. Advances in Neural Information Processing Systems, 36, 2024.
Yi Xu, Qihang Lin, and Tianbao Yang. Stochastic convex optimization: Faster local growth implies faster global convergence. In International Conference on Machine Learning, pp. 3821-3830 PMLR, 2017.
Zhiyu Xue, Shaoyang Yang, Mengdi Huai, and Di Wang. Differentially private pairwise learning revisited. In International
30th International Joint Conference Artificial Intelligence, IJCAI 2021, pp. Joint Conferences Artificial Intelligence Organization, 2021.
Tianbao Yang, Zhe Li, and Lijun Zhang. A simple analysis for exp-concave empirical minimization with arbitrary convex regularizer. In International Conference on Artificial Intelligence and Statistics, pp. 445-453. PMLR, 2018.
A Experimental Results
Privary Sudget bifect on ABA [14 Losal
Sample Size Effect ASA (14 Losal
1.2
04403
Miapy audget10
(a) Results of 4-rorm linear regression with different privacy budget on aSa
(b) Results of form linear regression with different training sample size a8a
Figure 1: Two experiments on 4-norm linear regression with a8a
16

---

Published in Transactions on Machine Learning Research (09/2025)
Nilacy Sudget Effedt un ADA ILA Lossl
Sample Siee Effect ASA (14 Losst
14
14
1.2
12
27
Miacy Sudget Id
(a) Results of 4-morm linear regression with different privacy budget on a9a
(b) Results of 4o-norm linear regression with different. training sample size a9a
Figure 2: Two experiments on 4--orm linear regression with a9a
Fivvcy Budget Effect WIA E14 Losst
Sampre WIA
UR--n Reco 503
JAGAN POOK-LD
34
08
03
0.6
1.00
19:05
20/05
(a) Results of 4-rmorm linear regression with different privacy budget E on w7a
(b) Results of & norm linear regression with different training sample size on w7a
Figure 3: Two experiments on 4--oorm lincar regression with w7a
Privccy Budget Effect ABA deghiic tegressio))
Sumele Size Effect A&A Logghicc Reg
09.003
0.2
3.50
3.8
114
Pronyy Rudgetnn
SangleS00 S0m
(a) Results of logistic regression with different privacy
(b) Results of logistic regressioon with different training sample size on a8a
budget on
Figure 4: Two experiments on logistic regression with a8a.
17

---

Published in Transactions on Machine Learning Research (09/2025)
Bopit segresson)
Loggetic
312
1.2
035
032
3100
10000
13550
11250
11500
(a) Results of logistic regression with different privacy
(b) Results of logistic regression with different training sample size on a9a
budget& on a9a
Figure 5: Two experiments on logistic regression with a9a
USC OR
030
LKG.MM
037
1.2
0.18
030
172
1200
3000
10000
1000
110.0
10.00
(a) Results of logistic regression with different privacy
(b) Results of logistic regression with different training sample size on w7a
budget on w7a
Figure 6: Two experiments on logistic regression with w7a
18

---

Published in Transactions on Machine Learning Research (09/2025)
B
Omitted Proof
Proof of Lemma 2. Let E N, and n = 2' and consider
1
n/2
n
Fx( n
Σ
[V[(w,
sup
i=/22-1
nf2
sup
(f((wx)))l
sup
[Vf(w,
n
i=n/241
Taking expectations over the random draw of X D and have (k)
n/2 Thus, RE & Tk-
(k)
Proof of Theorem Privacy, Since in each epoch of Algorithm we use a disjoint dataset, it is sufficient for us show each wa (e,6)-DP.
Since the batches [= disjoint, it suffices (by parallel composition in (McSherry, 2009) to show that wy (produced by T. iterations Algorithm in line 6 Algorithm 3) is 2CDP for all i [4] hence by Proposition 1.3 in (Bun & Steinke, 2016), then it is (2s /log(1/))) 8)-DP
With clip threshold C₁ and batch size the & sensitivity of the clipped subgradient update is bounded by
20: [[ (Vf(w.))) (V S
A = sup W.
Ic. (Vf(w,x;)) - ITc, (Vf(w,
= sup ns w.z.a''
j=1
(5)
Note that the terms arising from regularization cancel out. Thus, conditional on the previous updates Wiat the + s) update in line 3 of Algorithm 2 satisfies e² =CD,, Hence, Lemma 2.3 in (Bun & Steinke, 2016)
implies that wy (in line of Algorithm 3) is _ SZDPP, hence /lgglog()/)), 8)- By the assumption that & (log(1/5), the mechanism is 0)-DP, by laking e' = we can claim that the algorithm is 8)DD)
Excess risk: We finish our proof through several parts. We first recall the following lemma.
Lemma 3. [(Feldman & Vondrak, 2019)] Assume diam, (X) & D. Let S = (Si.... Sn) where ST add P and f(w,x) is L-Lipschitz and X-strongly convex for all x E X. Let & argmin F(w) be the empirical minimizer. For 0 < 3 & 1/n, with probability at least 1 -
cL2 llg(gg log(1/3)
cLD LiD(log////
F F <
An
Vn
Theorem 8. We have the following bound for I|wT 0112 for T ilerttion::
||w 01|2 & expl- Anpl'
+ SnAD= + 1lwo 2 Saf(((r)
20
X2
Proof. Detailly,
1VF (wz))? < (war <2 (Iv
+ +1(bel1)
< 2 2f (X) + 2X2 + B2)
And also, by Young's inequality,
B +
1b,, w/ - 18)l <
4 ww wl|
A
19

---

Published in Transactions on Machine Learning Research (09/2025)
Set VF (wx) VÂ (w)) tb 1 Ei= Ie (Vf 24)) + X (w= - wo) as the biased, noisy subgradients of the regularized empirical loss in Algorithm 3, with No- ~ N (0. TT)) and by = n Ei= Ne (V (w),
n
1 - Vʃ (w), Denote 11+11 wt- F (wr); so that W241 Il (v++1). For now, by strong convexity, n
we have
x
Ba (wr) - Px(tt) E V Ps (Roe), we - v0)
2 1w - 6012
FF (wee): w/4 - 20)
X
1l1e - w01 + ( (VFx (wr) - FFx (wx)) we - 10)
2
(Iuu: - :01 + |1 - -0-++++1l 11- - -1l1++1 11:41-111 60(l²)
2 2
| - -012
2n
+ (VFA (wx) - -VFx (ure). : we - ,b)
1
(Ius) w1l (1 - -nn) - 111/+11 -mil²) + "?
VFz (uz) 2
|
2m
2
(VFx (wx) - VFx (uze) , We - v0)
+
1
(I02 - w (1 - An) - ||00+11 - -0ll²) =00l()++
+ " F (wn2) - -bbe, 1o - -w),
2ny
2
where we used non-expansivennss of projection and the definition of V (wx) in the last line. Now, re-arranging this inequality,
|| - 16|2 < |1:0 - w||2 (1 - An) + n/ FF (w)) m
-21 ue -w) - 22n(F2(1r)) - (D)
< | - =1|² (1 - Xn) + n/² F (wx) 1|
-21 We- - w)
X1|
2 + 17 2(2) +00+++2220 +2x2D2 + B32) + 20,
||uree - 11l3 (1
A
|00 0||3 (1
An
+ 4nj (P% (x) + + B²)
2
x
where B is defined as below,
(x)
î sup
|ball <
(k - 1)C
tT
Thus, iterating the above equation, we get
(47()())))) + B²) + 2n T-1
An An TT 1wo - -01l + =012+
|UT - |wl- < <11-
Σ (1
2
2
X
t=1
Xn or 1//00 - -011 + (477
2nB² 2
< (1
+ B9)
2
An
Xm
TT |/w0 -0ll + 81 (f D2 + B²)
4
=(1-
2
X2
AnT
0||2 + 8nf
+ 8nADD2 + B
48
< expp
} -1wlg
+
2
A
X²
AnT
(1))(()
+ S1IAD2 + 20
<
<expl
} -|w0
क| + A
2
x2
The last inequality holds due to the assumption that 17 < 3.
Theorem 9. We have the following bound for f(wi) - f((ir):
F(wi)- - F())) < Ō Fzk
DL1
R
vn
20

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Firstly, the choise of D, ensures that dhe E W,.
Then by the above lemma, and choosing specific Ti,
||1; - -0;ll < expl - A.neTi ||u0-1 will++ +
Sn n; (B.)
20 (B,)
+ B, +
27 n.
2
A
1)0
11 1 ||l; - 0i:l? ~
X;
+
XCC
I'm
24
1 x 16'4
(11
+
C2k-244
(6)
Then by setting supwew [VF(w)) r. Therefore,
F(w)) - F(i)) v ww 0d/l
((2k)
r (I, +
C
2 4'
SL 71
(Lا +
12k
n2
ck-1
SL ? n2
(L1 +
22
Chi
L ! n²
Lj +
T2k
vd
)
We know that & ~NO, of and & is sub- sub-Gaussian, thus, we can derive that
2
Pflll > (Vd] & 2expl
160
Here there shall be some confusion about the lower index, where equivalent to as above, not the original & here. Therefore, with probability 1- 3, lls:ll & 4ydo, log(4/3). Thus, due to the choice of n, we have
8C1 (lg(1//)
F(wr) - F(i,) E4L /d, log = 41, 4T, dlog (4/3)
ni2ie
Cmnn
-32L, /log(1/1 lo8)) log(4/3)
8m1
np 1
=32L // dlog(1/8)log (4/
(dlog(n)
4 (2
F2k.m
LogLlog(1//)
Bzz.
Vogog m
Finally, we reach the upper bound for F(Wr) F(w"):
Theorem 10. Finally, we reach the upper bound for F(wx) - F(w*):
F(w))- - F(w") S D( 1
+ /dlog(1//) 1/5) log n
1-1 +
D2 Dolog(/ Log((1//))) (1/3)
Vn
2 2
21

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. Rewrite this term into summation of their differences,
F(w)) F(w") E1((1o) [10x-1)) (f(w)) [(,)))
By lemma 3,
cI2log ny log (2/3)
+ cLD (2g(2/3) vn;
x
F(w:;) - F(ū;-1)) <
+ || w;:111?
Ap1
2
For ||u;- - 12 < th 13 - with probability at least 1 B, for some constant Co
F124)
< 0
n' (I) +
c )
Tak)
then summing over from to we have
X X²C24-24
16
f(w)) f(10)
1
d -1 cLi log n, log(1/8)
CLy Da PP/log(11 (1/3)
<oo
Amn
VTh
L log n, log(1/3)
Diy log(1/3)
<A1 -100
woll + Σ
A 1100;-1-;,-1 - 1/
A
Vnh
2=2
1=1
D
n 20m(2k)
L (logn log 2 log(1/3)
Xo
ni L3
nene + Σ L3 p- Vlo((188)
1M
C₂2
14
1=
D2
Σ
1/2 1 + nn Ci:
(=(2k)
Lim (logn - log 20g (mamp-'(logn
log (0g(113)= Σ L
VVlo(11BB
1p
CP
1=2
D2
L + Rea p dloog n mmd
(log n - i)
+
+ Li L-7mp--oog(1/99 log(1/3)
4 . (2p-1)i + Lz \log(11/3)
2p
22n2
2
D2
dlog A-1
+
p L + n
7m22
22
1
log nl 20+1
+ log(1/B)
Limeee a /llo(1113))
2p+1 log"
20+ -
D2
+ (LL + Rn d dlog n 2
+ Logn-~1oo((///)) log n (-++1) + 12mmp- 1o//o1111)) (x++)))
2
22n²
n2/2 n Rizk ( + (1)())
Assume that 3p s.l.
and take
Df min( I,j' Rak.n
}. then the above can be reduced
n2
Vdlog(1/ log
1.3% lox (og(1/8)
$ (Rann D D Vn
+ (v /dlo((118)) log n
D/log(1 (1/B) 2 V/n
f(wi) - f(w²) (ww)))(w*))
En
which holds with probability least
Proof of Thorem 2.
22

---

Published in Transactions on Machine Learning Research (09/2025)
Theorem 11. Assume that loss function F()) is (0,A)-TNC and f(;,2) is convex, a-smooth and L Lipiscchtte for each x. Then algorithm. 4 is (e, 0DDP based on däfferent stepsizes {7R ) and noises if n & 1 Then for sufficiently large n and (E, with probability at least 1 - B, we have
VVdlog(1/b) (16) log"
log n Vn
log n log((1/)))) (1/B)
F (wm)- - F (w") 50
+
A
en
20 20+ 1/
Proof. The guarantee of (e, 6)P is just followed by Theorem 1.
For simplicity, we denote a(n) O R2k.n (/ (V Vallg
+
[og(1/5) 2 20tiv
We set po = 2R 2RR-0a. (no) : Mh
where k 1, 1,... m. 2(8-1)8 Ho and RS Bo 2
Then we have μa - R Ro.. We can also assume that X < R otherwise we can set X R which
makes TNC still hold. Recall that m
2n log2 log,
1, when n 2 256, it follows that
2
2n
2n
1
0 <
2 log2
2 E m E 2
loga
1
loga n.
loga
log2
2
Thus, we have 2m 2
2n
(il we pick specific m such that 2 2
2n loga
log v /lg(1188) ) Thus
V
loga
V
Pm 200-1)m p4 2 2m 40
2n
1
2 VV loga log no v log (1/3)
2. 2.10 RR-00 (mo)
5 RD-
2n
1 +
/
dlog no
-
v (1/(1/3)
+
log no /
V
log2 n
Vno
Eno
20 1/oo
2n
2 5 Ro Rd R1-8
log2 n
2n log,
loga 2n
loga
logz 2n
logg log2
=5. Rex Rg R4-0
log no / /log(1/3)
loga
logg 2n
log, log, n
2 Ro -
Since 5
2 when n 2 256
log, n
2 X By assumption ).
where the third inequality is given by throwing away the /dllog P-1 and 2"+\/ng term and substituting m in term with 2
(1/8)
logz log, 2. Below, we consider the following two cases.
2n
Case If X No. then Ao < X E pm. We have the following lemma.
Lemma 4. Let K- satisfies pa X 20 pke, then for any Algoritlum salisfy
k", the points {ūx 1m generated by
|10x-1 w' w0112 < R8-1 = 2-(k-1) Ro,
F (wx)= F (w") & ua Re 2- nD Rg.
(8)
Morcover, for lo 2 k², have
F (mxx) F (wx-) ) & p4- Re.
23

---

Published in Transactions on Machine Learning Research (09/2025)
Proof. We prove (7), (8) by induction. Note that (7) holds for h = 1. Assume (7) is true for some h 1, then we have
F F( - F (w*) < Rk-1- : Reximo 1
( / no
/log(1/3)
+
71o
Eno
2 2
Rx-1a (no)
1 2 1-1) 1 Ri
R2
Which is (8). By the definition of TNC, we have
1
100g w012 <
X (F (10x) (w*))
F (wx) (ww)
pk-
14 R
& R
p4.
Thus (7) is true for & + 1. Now we prove (9). Referring to Theorem 1, we know that
F (wx)) F (wx-1) 1) < RE-1 aa (no)
2k" RR Rk--100 10 (no)
2h' -k "Mx- R²-
-xx R2
Thus, for K.
(w)) - F (fok-)
Σ
(F - F (10)-1))
+=
2k- ) Wu R
j=
(1 2t -x- 1* R
M4: R$-
Here completes the proof of the lemma. Now proceed to prove Theorem 1 in this case.
24

---

Published in Transactions on Machine Learning Research (09/2025)
F (10m) - F (w² = (F (10m) - F (dxz-) )) + (F (dxx=) - F (w*))
< 2p1 R
4 Nk
Nk+ Ri-
Since
8-1
2
1
x
2)
1)0k") 140
1k R4.
4
2 uk Ri Ho
T-T
=4 4
No Ro
T
1 8-I
=4
4
1
att
(2.a a (mo)) 6
4
(2) 1 ,
(d /dlog no
V log (1 (1)3)
= 4.
.2
Ratino Vnu (Tr
+
+
Eno
2 /oo
where m = O (log2 n) ( Recall that m & 1 logg 12).
Case 2 If À < Mo. then
F F(01) F (w*) < Roa (no)
0-1
2
a (no) p (mo)==T
No
2
a (no) I
A
Also, we have
F (w0m) - F (00z) = Σ
(10) F (10
j=2
Rg-1.a 1 (mo)
j=2
m
>> 2 2-(j11) Ro (no)
j-2
= (1 - (1/2)m-1) 1) Ro - a (no) < Ro a (mo)
By a similar argument process as in Case 1, we have
F ((Dm)) - F (w²) = (F (17m) - F (v01)) + (F (101) - F (w²))
2 /5
< 2Roa (no) <
a (nx
=2. (2) o-
Rox Tro
+ v
dlog no
[
Vlog (1/3)
+
eno
2 1/1o
25

---

Published in Transactions on Machine Learning Research (09/2025)
Combining the two cases, conclude that with probability at least 1 B,
A
VVllog(166) log²
R2 Vlog n vn
log n 1og(1//)
F (w0) F (w") 0 A
En
2 20+ 1
Proof of Theorem 3. Proof. The guarantee of (e, 0)DD just followed by Theorem and the parallel theorem of Differential Privacy. In the following focus the utility.
Since [loggloga 2) loglogrh n], then k (log, 2) log logn, namely 2 (logn) log? and 2
<
1.
(log n) Lonu?
Observe that the total sample number used in the algorithm is E n $ Σ 2i-in
(2 1)m
(lon (loR
(log n) long
For the output of phase i, denote A; = F (w;) - F' (w=), and let D. = l|w; - "= w=1l2. The assumption of TNC implies that F (we: F (w") ||w; w² 11 which is F (wa) F (w*) 2 A ||w0s w=112 when take expectations at both sides, namely
A; AD
(10)
Thus, have
dlog mi
k-1 + cD; 1V log (1/3)
A < c.
+
VT,
Eng
20+ 20+1/, Vii
(11)
(10)
Ai-1
dlog n4
& Vlo (1/3)
cR2z
+
Vn
en,
20 1
where the first inequality comes from Theorem 1 and the second inequality uses (10). 0
Denote E,
5 Resen (ur + (v Valogni ni
Then (11) can be simplified as - + 27 Vnu
/lg((1/3)
enc
A < (A, (,)
(12)
Notice that ni/ni-1 = 2, then
Ex-1 E.
<
nl
20 namely:
E, 2 2-8 Ei-1.
(13)
Then we can rearrange the above incquality as
A
(A))E
2
(14)
EST
E
E
where the first inequality uses (12) and the second inequality applies (13).
It can be verified that (14) is equivalent to
1-1
A
11² E
T-
201-12
F
13-
26

---

Published in Transactions on Machine Learning Research (09/2025)
According to Lemma 1, A & (1
Also observe that
e E1
(neaml
1
dog n
(lg(115) (1/5)
Do 22,2
c
R2
+
+
A
m
eme
2D+ /
A
(v
n
Let C c 10-11
then
A
I
which implics that for I [llgg 2) log log n|],
2
Fy
A
n1
1j2
E
Let C1 = -2 2 lolle In the following we prove that
n
C₁.
Since 1 ++1 1 12 (logg 2) log logn (loga 2) log log n, it follows that
(1 1) log loglog C1 2 log ( 0
0011" + |logea] + logolog logn,
which indicates
0 - 1 + log c1l logn & g0 log C1.
0 Thus we have Ø-Ι log n logei & log C1. which is equivalent to our object
n n-T
$
Cj. Now we
Ci
know
11
<
C₁,
2 00
E T-T
C1
which indicates that
+ < 270-
C₁ = 20²
[1oRe2)) 1
= C. As a result, we hold a solution with error:
F (wi) - F (w") < CE
C
c0
+
1
(
Vdlog nn xx² + (1/()13)
-4
V
Eng
2D VTi
Proof of Theorem 4. We first define the set of distributions {Quhvey. Specifically, by the standard Gilbert-
Varshamov bound, there exists set V [=)d such that: (1) | 2 2 (2) for all v. e V, dham (v, v') > d (Acharya et al., 2021). For each v E V, we define Qu as
0, with probability - p
X. x
(15)
p v with probability p
We that for each X, Qu, we always have ||m, E[xx)ll22 = =p 1-ع
μ1.
27

---

Published in Transactions on Machine Learning Research (09/2025)
1lw112. i.c., Fp(w) -ww,Ep(z) b|[l|l for We then consider the loss function f(w, z) = -ww, 2) distribution P. By (Ramdas & Singh, 2012) we know it satisfies (0, 1)-TNC when 0 2 2. Moreover, for each Qu we have
E sup wEW
[V
E sup wEW
|1| x=10 & El| 2
- =(()
(16)
where the first inequality due to the radius of W (2 1 ) Thus we can see Fr(w) satisfies Assumption 1. For convenience we denote (w)(w) Fo(w).
By the form the F. (w: we also see that
VE =0 00= 1 pv.
(17)
Thus the optimal solution w.
E W by our assumption on and thus p & 1. In total we have
MWN,P,F1(PFOO)) 2 inf
Σ
EAD (F(A(D)
min F. (w)),
(18)
AEQ(A)
V
wEW
DEV
inf AEl(pt [V]
EEADERE IA(D) w0ll2
inf AEe(p)
Σ vEV
BAD [A())
Me
11..
(19)
NEV
Next, we recall the following private Fano's lemma:
Lemma 5. [Theorem 1.4 in (Kamath el al., 2021)] Let P be class of distributions over a dala universe X. For each distribution p E T, there is deterministic function 0(p) E T, where T the parometer space. Let p T x T 3ー R+ be semi-metric function on the space T and + R+ - R+ be a non-decreasing function with ((0) 0. We further assumne that X x [X=]__ are n i.i.d observalions drawn according to some distribution
P, and Q 2² + θ be some algorithm whose output Q(X) is an estimator. Consider set of distributions V {PI, P2. .PM} S P such that for all + j,
((p(0(p:))0pp)) 2 a,
DxL(ps.P)) Pi) & B, where DKL is the KL-divergence,
Drv(pt.P) Pj) &,,
then we have for any p-cCDP mechanism Q.
1
a
max n,3 + logg 2
p(n2 + +n 7)) + log 2
Ex (00((()))))))) MEMM]
M
log M
log M
Now we will leverage the above lemma to lower bound equation 19. We can see in our set of probabilities (Quhevv for any v, E V we have Drv(Qus Q & p. And
B(R P
Hv
A-1 F*
(v 0')11
>
C
-- 2(F
k-1
0-1
(20)
11011
6-2
11
P
2vd
/
910
Taking p = m/p
vd
and by Lemma we have
inf AE
Σ EADeE A(D)
-
Hv
212 29
(Fx
(21)
M
NEV
28

---

Published in Transactions on Machine Learning Research (09/2025)
Proof of Theorem 5. The lower bound for non-private case follows the proof in (Asi et al., 2021a). Here extend to the heavy-tailed case. For the index set V we consider the same one as in the proof of Theorem 4. For each E V we define X ~ Pe as
Fg 1/ 20a
with probability 1+8
for [
2
(22)
2Vd
Fo..
with probability
1-6
_
We can see that for each X, ~ Qu we always have 1| = |X|xlll22 = 8 μ.
We then consider the loss function 2( - (wc, x) 1l i.c., FF(w) -ww,Ep(a) 1 for
distribution P. By (Ramdas & Singh, 2012) know it satisfies (0, 1)-TNC when 0 2 2. Moreover, for each Qu we have
E sup wEW
[V 2)
sus
||| x < 2
- p(k)
(23)
wEW
where the first inequality is due to the radius W is (2) Ft. Thus we can see Fy((w)) satisfies Assumption 1. For convenience we denote (w)) = (www).
By the form the (wr we can also see that
VF.(w")=00 =0 10 Mv.
(24)
Thus the optimal solution w
E W by our assumption on n and thus p & 1. In total we have
6-z 1
MWW.P.F((P...).)))
2 inf AEe(p)
Σ
EA.DEQU (F((A())
min F. [w]],
(25)
VI
wEW
NEV
2 inf (E
EAADEO (A(D) will2 inf
Σ vEV
AADE [A(D)
Pv
112.
(26)
IV
AEQ(A)
M
1-
VEV
We can see in our set of probabilities (Quleev, for any U. E V we have DKz(Qu: Qu) $ 62. And
Hv
8Fk
(v
0')112 2
8
7 = (((5-1880())
(27)
n=-1
0-1
PG 6-1
2vd
01-2 8-1
Thus by Fano's 's lemma or Lemma 5, taking 8 = Va we have the result.
Proof of Theorem 6. Proof of Privacy. We first recall the following lemma:
Lemma 6. (Feldman et al, 2022) For a domain D, let R( f f Sti) for i E [n] be a sequence of algorithmms such that R() (600 (21:-1..) is (Eg, DD local vandomizer for all values of auailiary inpuls 21:1-1 S(1) .... x S(i-1), Let As D - S(1) x... S(n) be the algorithmm that given dataset TineD"" sample a uniformly random permutation N, then sequentially computes 2, (1) In(ii) for [n], and where
the outputs 21: Then for any E [0, 1] such that Eo & log (1610(12/0) As is (E, +
= -o----t0) eto (og(1/5) Vn
e00
We know that for each a E Br, we have R(Tc(V/(w,x)) [c((/((x,)) + Cas with Sn ~ N' and of 802 log zn is an (5o, LDP randomizer. As we randomly shuffled the data in the beginning, thus, the og
algorithm will be (8, 8 (on))-D where = o (1 (1---6o))
(eeo log(1/6)
50
vn
29

---

Published in Transactions on Machine Learning Research (09/2025)
Now, assume that < 2, then 3c, O, s.t.,
(Vetl (Ve8log(118) log(1 ec
E (1-66)
vn
72
(ea023 -0002)) log(1/0)
e
<..
+
n
n
-1++)))(11-)))
log(1/8)
(1 +1+30 250)
<
- -11-
n
n
log(1/8)
61 600
2
+
11
n1
2V2C
/ log kg
Set 8 8,
60 = 02 p..
for some constant C2 > and replace ED
2,
2/2C
log 80
3
log(1/8)
2 n
8 E
2
σ1
n
C. /lo((1/0) log(
0
σivn
For any & 1, if we set σ = 0 C.yloR(1/b 1/8) log(e"n/8)
=0
then we have & &
Furthermore, we need This implies that for log(n/8) if releasing (R(II((V(())" .+))) is
eva
202C / log I
& I which would be ensured if set e o
((V [og(n/5) (Vior(n//)
en
91
n
o C.y ( algorithm 6 satisfies (e, d)D as long E = 0
σ1
6VR
R(IIc([[(w,x:)) for all x. Thus in step we can see VF, (wmid) = EeSB, (e, for each I. And since (B.} are disjoint, Algorithm 6 is (c, O)DP.
Lemma 7. (Barber & Duchi, 2014) Let {zi)i=ı De be Rd-valued rundom vectors with Ez; = and
E || < (k) for some > Denote the noiseless average of clipped samples by = ! Σ II and
1=1
((k b: D+N. Then, |Eū-u vll |E w/l < -EIi- wll & (k-1)C*-1, and Elji-Eij Elii P < do 2 2(0)
claim: can improve the noise to y² sup [[I & do + 2T
2C 24
TT
+
Excess risk: Consider round t [T] of Algorithm 6, where Algorithm is run input data (Vf (w,, WTT Denote the bias Algorithm by b, : ÆVF, (w.) - V (w:), where VF, (w;) = 8 in the notation of Algorithm 1. Also let V.F (wy) = f (in the notation of Lemma 7) and denote the noise by N₂ FF. (w)) VF (w,)) b, = VF, (w)) - EV F; (wz). Then we have B = suPte[T] ||bel| < ক-ांलह and
R/T
((t))
+ = by Lemma 5. Plugging these estimates for B and Σ² = suptemm E [INa]l]] < do + ST < u
dC T
30

---

Published in Transactions on Machine Learning Research (09/2025)
1/k
E into Proposition 40 of (Lowy Razaviyayn, 2023) and setting C r
on
we get
3D
D
EF (WT) 09
- F
+ +BD
T
VT
3D
CD (lloo(1/6)
rD
((() D vn + Ck-1
T2
en
(k- (k-1) Vdlog(1/0)
3D
<
+
+rD
+
72
vn
en
Now, our choice of? T
R-1
3D
3D
min
n 1/44
r
(1100(1/5)
(k-1)/A
implics that aDa
rD
+
(1/0)
and we get the result upon plugging in T.
vn
272
Proof of Theorem 7. Similar to the proof of Theorem 3.
31


Reviews:
[{"review_id": "A2ygO91FpQ", "reviewer": "Reviewer_sWaU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not intimately familiar with prior work, but it seems like the analysis overcomes several technical challenges. The work will surely be of interest to the TMLR audience. \n\nI found some of the technical presentation and discussion confusing. Here are some questions I had about Theorem 1.\n- Why is ``$p$'' in the theorem? What purpose does it serve? It doesn't show up in the conclusion.\n- Where is the privacy parameter $\\delta$ in the conclusion?\n- Why do we restrict the failure probability $\\beta$ to be at most $1/n$? This doesn't make sense to me.\n- Where is $\\beta$ in the conclusion? It seems to be hidden as a logarithmic factor, but since the discussion of high-probability versus in-expectation is important here the dependence on $\\beta$ should be explicit.\n\nI also have some questions about the relationship with prior work. We seem to be missing a reference to [1]. I'm also confused about the formal relationships with the work of Lowy and Razavivyan; part of their contribution is to obtain results without the smoothness assumptions used here, so it's not clear to me which results are directly comparable.\n\nThe current application of citations throughout the text is hard to read and inconsistent.\n\n[1] Asi, H., Liu, D., & Tian, K. Private stochastic convex optimization with heavy tails: Near-optimality from simple reductions. NeurIPS 2024.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission considers DP stochastic convex optimization. Most work in DP-SCO relies on strong assumptions about the loss being uniformly Lipschitz; this work lies in a \"heavy tailed\" setting where we assume a bound on the low-order moments of the gradients. One of the specific assumptions used is that of a \"Tsybakov Noise Condition,\" an assumption from the optimization and machine learning literature that might allow improved results for important special cases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Can you restate Theorem 1 in a way that makes the role of $p,\\delta,$ and $\\beta$ precise?\n\nCan you provide an overview of which of your theorems improve over those of Lowy and Razavivyan, with pointers to their theorem numbers?\n\nCan you briefly compare to the 2024 work of Asi, Liu, and Tian?", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HwZvl2X02O", "reviewer": "Reviewer_ZoeR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I think that this paper indeed provides a great analysis of DP optimization problem with heavy-tailed response. Based on my reading, this paper makes a solid contribution. Moreover, I have briefly read through the proof. It seems that the result is technically correct. Therefore, I strongly recommend acceptance at TMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the bound of differentially private optimization. While this problem has already been widely studied in many previous literatures, This paper introduces a Tsybakov noise condition. In particular, this paper assumes that\n\n$$F(w)-F(w^)\\geq \\lambda ||\\theta-\\theta^||_2^\\theta$$\n\nWhen $\\theta = 0$, the condition reduces to general convex case. The bound derived in this paper also matches with existing works.\n\nWhen $\\theta=2$, the condition becomes the strong convex case. The bound derived in this paper matches existing works about strong convex case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have any requested changes.", "broader_impact_concerns": "I do not have any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "P59e1M3Xx3", "reviewer": "Reviewer_K3oy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- By leveraging the TNC and assuming heavy-tailed gradients, the paper relaxes commonly used assumptions (e.g., bounded Lipschitzness, sub-Gaussian input distributions), thereby broadening the applicability of DP-SCO to more realistic settings.\n\n- The proposed algorithms yield utility bounds that are independent of the Lipschitz constant—an important advancement, especially in scenarios involving heavy-tailed data. The combination of high-probability upper bounds and tight lower bounds further strengthens the theoretical contribution.\n\n- The paper is well-written and organized. Despite the technical depth, the exposition is clear, definitions and assumptions are well-motivated, and comparisons to prior work are comprehensive and informative.\n\n\n\nWeaknesses:\n\n- While the adoption of the TNC leads to significant theoretical improvements, its practical relevance could be more clearly articulated. The paper cites past papers and gives examples such as $\\ell_1$-constrained $\\ell_4$-norm linear regression, but these may not be sufficiently accessible or persuasive for readers unfamiliar with TNC. I encourage the authors to include additional concrete examples or offer stronger justification for the prevalence and importance of TNC in real-world applications. Moreover, it would be helpful to explain under what circumstances the TNC condition can be verified and how the parameter $\\theta$ (or $\\overline{\\theta}$) might be estimated in practice.\n\n- The algorithms depend on several hyperparameters (e.g., $C_i$, $\\lambda_i$) that are tied to abstract quantities like the $k$-th moment of gradients or the TNC parameter. These parameters may be difficult to estimate or tune in practice, especially when the required quantities are unknown.\n\n- The paper does not provide any numerical results. While this is not a strict requirement for a theoretical contribution, some simulation studies — particularly comparing standard optimization methods to the proposed ones under TNC—would significantly enhance the paper. Such experiments would not only illustrate the practical impact of the TNC assumption but also make the theory more accessible to a broader audience.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses differentially private stochastic convex optimization (DP-SCO) under the Tsybakov Noise Condition (TNC), targeting settings where the loss function may not be Lipschitz or where the Lipschitz constant is very large. The authors propose novel algorithms that achieve high-probability excess population risk bounds based only on the boundedness of higher-order gradient moments and the TNC, rather than Lipschitz continuity. They further present tight lower bounds under $\\rho$-zCDP, demonstrating that their results are near-optimal.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- See weaknesses.\n- Ensure consistent and appropriate usage of LaTeX citation commands such as \\cite, \\citep, and \\citet. For example, citation formatting needs to be reviewed and possibly corrected in the following parts:\n  - Caption of Definition 2 and 4\n  - The paragraph following Definition 7\n  - Remark 2\n  - The paragraph below Theorem 6", "broader_impact_concerns": "No concerns. This is a theoretical work that may have societal impacts in the future.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)