Exploiting Hidden Symmetry to Improve Objective Perturbation for DP Linear Learners with a Nonsmooth L1-Norm
Authors: Du Chen
Geoffrey A. Chua
Venue: ICLR 2025 Poster (2025)
Keywords: Objective Perturbation
Convolution
Nonsmooth
DP-SCO
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: apply convolution to L1-norm to improve OP

Abstract: Objective Perturbation (OP) is a classic approach to differentially private (DP) convex optimization with smooth loss functions but is less understood for nonsmooth cases. In this work, we study how to apply OP to DP linear learners under loss functions with an implicit $\ell_1$-norm structure, such as $\max(0,x)$ as a motivating example. We propose to first smooth out the implicit $\ell_1$-norm by convolution, and then invoke standard OP. Convolution has many advantages that distinguish itself from Moreau Envelope, such as approximating from above and a higher degree of hyperparameters. These advantages, in conjunction with the symmetry of $\ell_1$-norm, result in tighter pointwise approximation, which further facilitates tighter analysis of generalization risks by using pointwise bounds. Under mild assumptions on groundtruth distributions, the proposed OP-based algorithm is found to be rate-optimal, and can achieve the excess generalization risk $\mathcal{O}(\frac{1}{\sqrt{n}}+\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon})$. Experiments demonstrate the competitive performance of the proposed method to Noisy-SGD.

Published as a conference paper at ICLR 2025
EXPLOITING HIDDEN SYMMETRY TO IMPROVE OB- JECTIVE PERTURBATION FOR DP LINEAR LEARNERS WITH A NONSMOOTH L1-NORM
Du Chen
Geoffrey A. Chua
Nanyang Business School Nanyang Technological University Singapore, 639798 chen14438e. ntu. wtw..nu.uuuu..... ed
Nanyang Business School
Nanyang Technological University Singapore, 639798
ABSTRACT
Objective Perturbation (OP) is classic approach to differentially private (DP) convex optimization with smooth loss functions but is less understood for nons- mooth cases. In this work, we study how to apply OP to DP linear learners under loss functions with hidden implicit -norr structure, such as max æ} as motivating example. We propose to first smooth out the implicit e -nor by convolution, and then invoke standard OP. Convolution has many advantages that distinguish itself from Moreau Envelope, such as approximating from above and higher degree of hyperparameters. These advantages, in conjunction with the symmetry of fn-norm, result in tighter pointwise approximation, which fur- ther facilitates tighter analysis of generalization risks by using pointwise bounds. Under mild assumptions on groundtruth distributions, the proposed OP-based al- gorithm is found be rate-optimal, and can achieve the excess generalization risk
/d
Experiments demonstrate the competitive performance
of the proposed method to Noisy-SGD.
INTRODUCTION
Differentially private convex optimization is one of the most crucial tools in private data analysis, which seeks well- pell-performin output from an optimization problem so that the output is also insen- sitive to the presence or absence of an individual in a dataset. In the past decade more, numerous works have together formed a good understanding of DP convex optimization, such as Chaudhuri et al. (201 Kifer et al. (2012) : Bassily al. (2014) 2019 2020). name few. While Noisy- (Abadi et al. 2016) has outstripped almost all other approaches, findings of privacy leakage through Noisy-SGD's hyperparameter tuning (Papernot & Steinke 2022 Mohapatra et al. 2022) have moti-
vated recent revisits (Redberg et al. 2023 Agarwal et al. 2023) to another classical and competitive
method, Objective Perturbation (Kifer al. 2012 OP).
OP follows a completely different design philosophy: it injects noise into the loss function of an em- pirical risk minimization (ERM) problem and then solves the noisy ERM, unlike Noisy-SGD that injects noise into gradients. Often, OP only requires light to no hyperparameter tuning. Moreover, because the noisy ERM can be solved by any optimizer whose choice is independent of the problem at hand, OP often returns high-quality (empirical) minimizers. regardless of the sample size. To further improve
practicability, the recent work (Redberg et al., 2023) has tightened privacy ac- counting of OP by employing privacy profiles, making it competitive or even better in performance than honest Noisy-SGD ("honest" means privacy in hyperparameter tunings correctly tracked). Some other works also found OP appealing for certain tasks, such as private logistic regression (Tyengar et al. 2019), binary classification (Neel et al. 2020), quantile regression (Chen Chua 2023). and online convex optimization (Agarwal et al.
2023 As subroutine, OP also found its
"Corresponding Author

---

Published as a conference paper at ICLR 2025
place in personalized pricing (Chen et al. 2022) that fosters analysis of statistical properties of some estimators.
However, compared to Noisy-SGD that can be applied to both nonsmooth and smooth problems, OP often criticized for being too restrictive as its performance is known to be optimal only when being applied to problems with smooth loss functions. Intuitively, this is because minimizers to nonsmooth functions are very unstable. To hide privacy contained in such unstable minimizers, we should either inject a high-variance noise or stabilize the minimizer first, both of which might en- gender nontrivial accuracy loss. This technical issue prevents a rich class of problems from enjoying the advantages of OP, ranging from simple problems with II-11- regullarzzr to neural networks with ReLU activation functions. As a motivating example demonstrated by Bassily et al. (2014), min-
imizing a simple though basic nonsmooth function [(0) == >> im1 max y/- 0 x; by OP is found to be challenging.
While the nonsmoothness issue of OP has been observed for decade, it has not been well addressed yet. One promising remedy is to smooth out the original nonsmooth function to get a smooth approx- imation, and then apply standard OP to the smoothed approximation function. However. downside of this idea is the additional approximation error introduced by the smoothing step. Early on, |Bassily et al. 2014) has noticed severe consequences of the additional error: the convergence rates of OP is no longer optimal. They attempted to resolve the issue with convolution smoothing, but ended with concluding that "straightfrrward smoothing does not yield optimal algorithms". More recently,
some works (Kulkarni et al., 202 Chen & Chua 2023) designed more intricate OP-based algo- rithms and developed involved analysis. But they either failed obtain optimal convergence rates or achieved it only under strong regularity conditions. Approaches that do not include a smoothing step has also been explored by Neel et al. (2020), but they left the convergence rate-optimality as an unanswered question.
Observing the strengths of OP and the open problem for nonsmooth cases, we are interested in applying OP to nonsmooth convex problems. Specifically, we focus our discussion mainly on common class of nonsmooth problems, where the loss function f(0; z) can be written as a sum of an & f--nrrm function [[A()))) 0 and well-behaved convex smooth function h(0 z), where @ is the variable to optimize and x is the data point, and A(-). h(-) are some known functions. In other words, we assume that the nonsmoothness issue in the loss function f(0; x) == ||A())01| + hh x) is rooted in the & norm.
This structure naturally covers problems with (possibly grouped) 4 fe-reuulrr II- with linear transformation of A(-). Moreover, many loss functions with widely accepted formulations not fol- lowing the structure can actually be reformulated into this form; for instance, positive part operator x+ = |x| / + /2, pinball loss rxt + (1 r-)+ | /2 + (r - 1/2)r, t-soft-thresooiding (|æ) [| =
(a- (2+r)/2 | - etc. This is precisely why we call it an implicit or hidden & structure
throughout this paper, starting from its title. Surprisingly, some special functions that do not follow the considered structure are also found to enjoy the advantages developed in this work, see Section for extensions.
The key step of our approach is to apply convolution smoothing (Hirschman & Widder 2012) to the -oomr function only. While it seems a straightforward idea and minor refinement, the benefit turns out to be significant. The reason is that the symmetry of the l function can be utilized to iden- tify a smaller set over which an integral is calculated to characterize pointwise approximation errors. With proper kernels, the errors could be exponentially small, in contrast to linearly small errors used in the literature. The exponentially small approximation error is negligible and thus does not harm convergence rates. Moreover, the smoothing method chosen is convolution smoothing, rather than the most common method, Moreau Envelope (Parikh et al. 2014). Though convolution is a classical method, its advantages such as analytic convenience and a higher degree of hyperparameter not often noticed and exploited in DP literature. It turns out that these overlooked advantages are crucial to the improved performance. We compare both methods in Section 4.4
Our contributions. Our first contribution includes the adoption of convolution for nonsmooth DP convex optimization problems and demonstrating its advantages in performance improvements. While we are not the first to employ convolution to address nonsmoothness issues, our analysis pro- vides new insights into its role. Along with this development, we also make a thorough comparison to Moreau Envelope. The second contribution is the improved performance analysis of convergence
2

---

Published as a conference paper at ICLR 2025
rates of the proposed OP-based algorithm for nonsmooth DP stochastic convex optimization (DP- SCO) with an implicit & structure. Under mild assumptions, the proposed algorithm can achieve optimal rates of DP-SCO in Euclidean space. Last, run simulations to demonstrate the benefits of convolution and OP. Specifically, we observe a comparable performance to Noisy-SGD, and OP even performs better in high-privacy regimes.
Related works. Objective Perturbation (Kifer et al. 2012 OP) is a classical tool for DP-ERM (Bassily et al., (2014) and DP-SCO (Bassily et al. 2019). OP outputs minimizer of a perturbed loss function, which substantially differs from iterative a algorithms, such as Noisy-SGD (Abadi et al. 2016). For smooth Generalized Linear Models, OP known to be rate optimal, i.e. its excess
(din
Bassily et al. 2021). To improve OP's practicability, under smoothness assumption, Iyengar et al. (2019) extended OP to allow it to return approximate minimizers, and Redberg et al. (2023) tightened privacy accounting. However, much less is known about nonsmooth cases. Without smoothness, NNel et al. 2020) proposed an OP algorithm paired with an additional output perturbation step, but whether their algorithm is optimal is unclear. Chen & Chua (2023) considered special case of quantile regression; however, their result lacks general- ity. Our work is also closely related to another stream of work that applies convolution to address nonsmoothness issues in DP convex optimization (Feldman al. 2018 Kulkarni al.) [022]] Wang et al.) [202]] Carmon et al. (023). A common feature of these works is that they all apply convolution before feeding loss functions into a standard OP. We follow this idea develop our algorithm.
generalization risk is O VT
+
2 PRELIMINARIES
Definition 2.1 (Differential Privacy), A randomized algorithm A 2 + θ is (c, -)dffferrent private if, for any pair of neighboring datasets D D' that differ in one data point, and for any subset S C θ, Pr (A(D) E S S e Pr [A((') E S] S]+ 6
Definition 2.2 (B-smoothness). Let B 2 0. A function f θ - IR is B-smooth (w.r.t 11-11p) over set θ if for every 01, 02 O, (0:) f((2)) I 3 ||0: 0211n- where p,q are conjugate indices such that 1/p 1/q 1. If the only admissible value of |9 is co, we say f is nonsmooth.
Notation. We use B(R) = {o Rd ||0||, S R} to denote the Euclidean ball with radius R > 0 around the origin, and ||-112 to denote Euclidean norm. Data space is 2, and datapoints in a dataset D == { are i.i.d. drawn from an unknown distribution supported on 2. The empirical risk of any O θ C Rdd under loss function f and dataset D is denoted by F(0; D) == n Er= f(0: 2,). and the generalization risk of 0 under distribution IP denoted by F(0:P))
Egwr [f(; Shorthand F()) and F(0) are used when the dependence is clear from the context. The excess generalization risk of algorithm A under distribution thus denoted as R(A; IP)
ED-P=.A A [(0-)] F(O") where 0 :- arg mingeR* F())).
In this work, our ultimate goal is to design an OP-based algorithm A to find 0 that can achieve rate- optimal performance in terms of excess generalization risk R(A: P) == ED [(OA)] - F(0)
for nonsmooth functions satisfying a specific structure in Assumption 2.3 Assumption 2.3 (Nonsmooth models with an l structure).
1. (Implicit ε structure) Loss function f(0; 2) Rd x Bdd + IR has an implicit -n-mr structure and can be written as f(0; z) : A( + h(z 0) for some known function
((()) RR + IR and function A(-) _d + mxd where I d is independent of d.
2. (Well-behaved h(-)) Function h(-) is convex and B mmoshh in 0 (w.r.t. (1-112). As scalar function, its derivative is uniformly upper bounded by Ln-
3. (Boundedness) Let 0~ := arg mingeg F(O). We asume 0" E B(R). Data space := B(D) C Rdd a Euclidean ball. Further assume the 2-norm of matrix A(-) uniformly upper bounded, i.c. supxez [[A(z)]]2 - A.
The first assumption makes our discussion focus on a specific class of nonsmooth functions where the nonsmoothness comes from the implicit nnrmm Despite the structural assumption, the con-
3

---

Published as a conference paper at ICLR 2025
sidered model still covers rich set of interesting problems. For instance, the motivating example max(0, 2) = (|x) + / admits a reformulation with A(z) == x /2 and h(z) := x/2, where
is the residual derived from x 0. Similar reformulation applies pinball loss: Vr (0, 1), have rx+ + (1 - (-==) )+ = |>|| 2 + (r 1 1/2)x. Another illustrative example is when A(-) is independent of datapoint 2; then the original model becomes 6 l1-regularized GLM. If we further have h = O, then the problem becomes model for finding high-dimensional quantiles. Given all these examples, should be clear that our assumption of the model structure not very restrictive. The second assumption ensures h(-) is well behaved, and the third assumption on boundedness is common and appears frequently in DP literature.
3 THE ALGORITHM
We propose the algorithm saavolution-then-Objeeee Perturbation (C-OP), which is formally given below in Algorithm ! The algorithm is built upon classical OP by wrapping it with an additional convolution smoothing step (T). The smoothed function is then fed into classical OP, i.e. Step 4, which returns minimizer 0². Both privacy and performance guarantees highly depend on the convolution step. We thus give brief introduction to convolution smoothing first.
Algorithm Convolution then Objective Perturbation (C-OP), Ac-oP
Input: Private dataset D {z, == privacy parameters (s, 6); noise variance a²; nonsmooth 2
loss function =() = [ 0 1 + h(=TO) () that satisfies Assumption 2.3 Constant C
V m D3 any random variable k whose pdf (i.e. kernel) given in the first column in Table T and bandwidth parameter μı > O.
1: For a given X, find such that = (mm+1) where 3, is given in Table
2: Get smooth approximation by convolution,
f=(0:2)= Ex [|IA(z)) uk]1 h(=T0)
(1)
3: Draw a Gaussian noise vector b (N0, (
4: 0 arg mingerd 1 - fx 24) 110112 (b.0)
5: Return: 0.4
3.1 CONVOLUTIOO SMOOTHING
Convolution smoothing Hirschman Widder (0012) is an operation on function g RT + R. and kernel k R. + 1 that produces smooth approximation 9n of g. The kernel function should meet some regularity Conditions A. the Appendix. In the main text, we focus on three common kernels listed in Table Each kernel in deefies probability density function (pdf). Intuitively, the approximated function value (x) := En [g(x + ukk] weighted average over
Table 1: Kernels and properties of smooth approximation (Lemma 3.1
properties of gx) := Eu [g(2 + pk)]
Lipschitz Ly
smoothness
uniform gap
pointwise gap (g (xx)
Kernels
k(v)
By
sup (op (x)))
e- |N13 ((22m)
Gaussian
T.
L/P VOL/H VoL/u,
T.pupp
L.p. Jy, || A(x)) du same as above
Exponentiale -1lulla/
L
Lump
Laplacian e -|ull m
L
=p==1
Lump
same as above
V6mL/14 o.w.
Notes. Properties of Ue under Gaussian kernel is known literature kernels. The set (x)) the last column is defined around Lemma 4.1 (fm//2)/(22=///11/1 with Camma function I'(-).
Duchi 2012]: derive properties for other
The normalizer n for exponential kernel is n =
4

---

Published as a conference paper at ICLR 2025
its neighbors, and the weights are controlled by kernel & and bandwidth parameter μr >> O. Properties of the approximation function 9μ for general Lipschitz continuous function g are given below.
Lemma 3.1 (Properties of gy). Let 9 IR R be closed, proper, convex, and L-Lipschitz continuous (w.r.1 I1-I1p E (1, loss function. Let k. IR - R be any kernel function in Table
denote Kip = 1. [|k||p Then, the convolution smoothing 9p possesses following properties:
1. 9u is convex, Ly -ipschitt and -y-smooth w.r.f. 1I-11p (see Table 7 for values of Ly and By);
2. 9u is differentiable with gradient (g = Ex Vg(x + μk)) vz;
3. Approximation error satisfies the inequality g(æ) - gx(x)) S g(x) + Lutk, Vx;
4. gx(x)) = -JUER [ll=tp)) pmm k<(v) des
These properties hold for general convex and Lipschitz function Oy- Throughout this paper, we will use n. = |l-1l frequently.
3.2 PRELIMINARY RESULTS
can be shown that, with a well-calibrated variance o², the algorithm C-OP is (s, DD- Theorem 3.2 (Privacy Guarantee). Suppose Assumption 2.3 holds. The algorithm AC is (c,
DP, of C²-(8la (1/6)+88) where C == V m.72 L. DD.
Because the matrix A(z) in Assumption 2.3 our model does not have the same model structure for which the privacy accounting bug was fixed by |Redberg al. (2023) and Agarwall et al. (2023). Thus, we provide a detailed proof in the Appendix. The proof follows similar idea in Agarwal al. 2023) but uses bounded A(-) to control the privacy loss random variable's 's tail behavior.
Now, we move on to analyze the performance of C-OP. A crucial observation is the third part of Lemma 3.1 which implies oft (a) == [xx[|= ,kk]1 approximates original function ge (x)
||œ||| from above. Therefore, if we apply convolution to the é part of loss function f. then Sy given by (T) is pointwise upper bound for f. This facilitates new decomposition of the excess
generalization risk R(A: IP) = ED-P= A
[(0-)] F(O"), as shown below:
RP ED.A
F(OA) 1.03-Fio F(0-))
+ ED.A
((O-)) F(0))
< EDDA
F(OAA) ((01)
+ ED.A
(u((4))) F(0*)
ED.A
(((MA) -
+ ED.A
F,,00 P.,(0T) -F F(O))) (2)
In the first line, we insert terms ((O-)); in the second line, we use the pointwise upper bound fn 2 f; in the third line, insert Fr. (0*) Essentially, the new risk upper bound ( consists of three parts. The first part a sampling error that can be controlled through uniform stability analysis; the second part is an empirical risk that be controlled through risk analysis. With these observations, can get a preliminary result of C-OP's performance.
Lemma 3.3 (C-OP Performance; Preliminary). Suppose Assumption 2.3 holds. If set the regu- larizer coefficient X
/ /4C² /n do² /n22 //2/E and use o² suggested by Theorem 3.2
then
Vdln(115) nE
R(A:P) < R(A:P) 4V2CR-
+ (F, - F(
Vn
The preliminary performance bound is remarkable, as it suggests that the additional approximation error depends only on the approximation quality at optimal 0-. Intuitively, this comes from us- ing pointwise approximation upper bound to tightly characterize the approximation error, which is unique to convolution smoothing. Instead, many other smoothing methods, such as Moreau Enve- lope, do not allow this tighter characterization, roughly because Moreau approximates from below
5

---

Published as a conference paper at ICLR 2025
(see details in Section 4.4). With lemma 3.3 remains to control the population-level approxima- tion enror at 0" We do so in the next section by exploiting the l structure of assumed models.
Before proceeding, we want to highlight an immediate result the choice of μ from Lemma Algorithm | the value of l should satisfy (8,+8.) (m+)) Because 3p x. A x VI/n+ /n², and o² = In (1/6)/e², we know
3.3 and Theorem 3.2 According to Step
/ne2+2d(in (1/8)+c)-Bx Therefore, roughly speaking, when sample size - oo, the value of y decreases. The fact that ş is decreasing a desired feature, leading to F2 (0*) F())) ) - (see
next section for details).
4 IMPROVED APPROXIMATION AND OPTIMAL RATES
4.1 EXPLOIT SYMMETRY OF -NORM OBTAIN TIGHTER APPROXIMATION ERRORS
We know from part four of Lemma 3.1 that g (æ) is in fact convex combination of g(x + wv) and g(x μv);; thus the approximation error at æ admits a closed form
g(x wv) + g(x wv) 2((2) k(v) do, Var.
gx(x)) g(xr)
DER"
However, most existing works use the uniform upper bound Luup in part three of Lemma [.Tmmaa..ffaa. for convergence analysis, which is ob- viously too conservative and significantly overestimates actual ap- proximation error.. The example of g(x)) |a: in Figure 1 demon- strates the huge overestimate: outside the interval [-1, roughly, there is no approximation error by convolution (green curve in Fig- ure D but uniform bound (in black) says the error is nontrivial.
0.8
uniform error
0.5
pointwise error
0.4
0.1
To understand this phenomenon analytically, we first notice that the pointwise error (3) is calculated from an integral on the entire space.
0.0
-2
x
However, actually suffices integrate over a smaller set Vp (x:).
Figure 1: approximation error.
where the integrand g( + -v) g(x)
( is strictly positive:
J == 0.5, Gaussian kernel
(x( = (v R" g(x + nv) + g(x - wv) 2g(x)}.
(4)
Although the integrand is always nonnegative by convexity, under -norr function, the set (x())) in fact a much smaller set than the entire space, thanks to the symmetry of & nn-norm function.
For clarity, we denote this set under L -ormr function by 2 (z) == {v E pm | + pwll, +
|| wlll > 2 ||>||] }. It has closed-form expression as shown below.
Lemma 4.1 (Smaller Domain of Integration). gf x + ||>||, is the l fi-orrm function, then the ||>||| strictly positive has closed-form expression Dia (ax) = {v E Rm |aa /ul//.,, where applies elementwise.
set 1/ (x: on which the integrand ||=+,oll -|| -vl
Geometrically, the set Vi (a) is a hollow set with a rectangle around the origin being removed. Moreover, it can be shown that the set Vμ, defined in (4p shrinks with gradually decreasing \ 0. This result holds for any convex function. But, specifically for gf, this shrinkage is strict.
Lemma 4.2 (Monotonicity of Vμ, in μ). If g is convex but not linear, then for any given the set V (x) is monotonically increasing in and satisfies, for any < 14d < P1 < oc.
① Vo(x) S Vno (x) S Vmn (x) C Voo IR TM (O))
Vz.
Moreover, the inequality becomes strict under function ge == |1-11,, iee.
0 = v (x: V&a
Vfa (z) V (x) =RT) Vo 0g",
Vfa
where Jg'r
{xc E R Fij + 0, Vj 1,...,m) m) } the set of differentiable points.

---

Published as a conference paper at ICLR 2025
This lemma allows us to further tighten the approximation errors. To ses this, notice first that
|| + 1wlll + || pm
||>||| k(o) du S 11 / (2)
of (x) g (x))
||l|| k(v) do.
JOENS (2)
(5)
The upper bound in Eq. is a product between the multiplicative factor μ and integral over V Essentially, Lemma 4.2 states that when μ > O, the set V tends be an empty set. Therefore, both the factor μ and the integral term tend to 0 when jr Y 0, indicating much faster rate of their product than any of them. Moreover, the integral term decreases at a rate that heavily depends on the kernel function chosen. If choose kernels from Table [ then the integral term decreases exponentially fast due to the kernel functions' light tail. We formally characterize the finding below.
Lemma 4.3 (Kernel-dependent Approx. Error). Suppose g : +> ||=:1 If kernel function ke()) is Gaussian kernel, then git (a) - ge (x) S 22/TH ΣØ=1 exp
1x 24
The left panel of Figure justifies the finding: when f > O, the approximation error at either = or = 0.5 decreases exponentially fast, whereas the uniform bound is only linear in μ. This observation also supports our argument that using a uniform bound is too conservative for convergence analysis. Moreover, all observations naturally extend to high-dimensional cases, the right panel of Figure 2 One remark about Lemmas 4.2 and 4.3 is that both results provide nontrivial improvements when & 0g Because the set 0g actually has Lebesgue measure zero, we can expect its impact to be negligible.
uniform
unforr enor
арргок. error
0.5
0.2
0.4-
x-0.5
0.1
0.2
0.0
2
0.0
0.5
2 -2
Figure 2: Left: approx. error v.s. l under g(x) = |ao|: convolution by Gaussian kernel. Right: approx. error under g(x) = ||ح||| in 2-dim space.
4.2 OPTIMAL RATES OF C-OP
With developed tighter approximation characterization, we are ready show optimal rates of C-OP under some distributions. By lemma 3.3 it suffices to show F₃ (6*) - F(0*) is dominated by
(1/55) Because approximatio errors are roughly exponentially small (given Gaus-
sian kernel is used), i.c. exp (- [=A Vj E [m], the optimal rate is then achievable as long as A(2)0* is not concentrated around O, and μ - 0 is properly chosen.
Assumption 4.4 (Widespread A(z)0*). Let æ ~ IP and let || x -ox == min l [mm|] denote the minimal absolute value among elements of æ. We assume there exists threshold 7 0 such that IP= [|]((2)"]] 2 1 2 - exp (-1/12), Vt S..
Assumption a.4ssmmsss that A(z)0" is at least t-distance away from nondifferentiable points with certain probability; otherwise, if all A(z)0* are nondifferentiable points, this distribution of z might be ill-posed and impractical. This assumption is motivated by observations in neural networks with ReLU activation functions where A are often far from nondifferentiable points (Ma & Fattahi 2022).
Theorem 4.5 (C-OP Performance). Suppose Assumptions 2.3 and hold. When we have either (i) 6 S min
exp (- max m m² //d///dd mm? /d) or (ii) 8 S exp (- (3, m² //////////) and
7

---

Published as a conference paper at ICLR 2025
2 V m² Inn//n, then running C-OP with Gaussian kernel and parameters in Lemma 3.3 yields
(1 Vn
Vdln (1/6)
R(A.P) SV2CR
ne
The theorem claims that under some assumptions, running C-OP can achieve the same optimal convergence rate as that by Noisy-SGD (Bassily et al. [019 2020). However, readers should be reminded that the optimal rate of C-OP comes at prices of (i) some restrictions on (e, 6) and (ii) smaller set of admissible distributions. Practically, both requirements are mild. Our numerical experiments keep showing satisfactory performance of C-OP, even when these requirements are not necessarily met.
4.3 SOME SPECIAL CASES
We found that some special loss functions not strictly following the assumed structure also benefit from convolution. Applying C-OP to those functions can achieve optimal rates if the distribution not ill-posed (see Appendix B.4 for details).
Piecewise Linear Loss (Figure middle). Suppose the nonsmooth loss function is piece- wise linear with P < pieces in the form f(0;z) == maxpe(rj ((pp:r///aappp))))p + bp} where {ap, bp are known parameters of pieces. In this case, the smooth approximation is (=; Ek [maxpe(r) {app A()) 0+ + pk) + bpp]
Bowl-shaped Loss (Figure 4 rightmost) Suppose bowl-shaped thresholding loss function f(0: 2) = [||A0]|, , =) with known Rmxd In this case, applying convolution gives
(0; 2) E& [[ + pkll1 2)+1.
4.4 COMPARE TO (GENERALIZED) MOREAU ENVELOPE
Because our work is motivated by DP convex optimization we interested in comparing convolu- tion with (generalized) Moreau Envelope (Parikh et al. 2014), which the most common smoothing approach in DP literature,
its applications Asi et al. 2 Bassily et al. (202)). (Standard) Moreau Envelope approximates the original non-
Bassily ly et al. (2014) 2019), Feldman et al. (2020);
smooth function g 12m IR with smooth approximation obtained from minimization problem
involving a smooth function (-) = με(-/u) with c--) 1 11-112 and μ
9MM (x)) = inf {g(u) + 6n(x u)}, Va..
(6)
welm
The Generalized Moreau takes other (6-) function and possesses similar properties to convolution.
Lemma 4.6 (Properties of 9ME. partially from Beck & Tebouile (2012)). Let g IRm R be closed, proper. convex, and L-Lipschitz continuous function (w.r.f. [1))), and let ó : Rm + I be 5'-smooth function satisfying regularity conditions (Condition B.l in Appendix). Then the
Generalized Moreau Envelope 9ME possesses following properties:
1. IME is convex, T--lipschitz, and (3' (B'//)) /m)-smooth, w.r.f. 11-112;
2. (gME(x)= ( (x--"""" (x)). where u² u²(a (x) is the minimizer to the r.h.s problem of Eq.
3. Let o² : + R be the Fenchel conjugate of ②. and let |1 ll suPyEB(L) 0" (y). Then, the approximation error is ||0" 11 (ME(#)) g(x)) (á)())
is self-evident that Lemma{4.6fis analogue of Lemma 3.1 As a minor contribution, the Lipschitz constant 9ME is tightened from 2L (Bassily et al.) 2019) to L. Comparing Lemmas 3. and 4.6
observe some distinctions between convolution and Moreau.
First, Moreau approximates the original function from below, contrasting with convolution that ap- proximates from above (Figure 3 first and third plots). Approximating from below invalidates the newly developed risk decomposition in Eq. (2); thus analysis developed in this work does not directly apply Moreau.
8

---

Published as a conference paper at ICLR 2025
(1) SMI
3.0
6.
2.5
6.5
660)
2.0-
84
0.1
Sancicn
1.3
1.0
o
0
Figure 3: Comparison between Moreau AME and convolution Jeanv. Left two figures: g |///
right two figures: g(x)) = ||a]| in 2-dim space.
2.0
2.0
2.0
1.5
1.5
0.5
0.0
0.0
0.0
-2
(3)
Goom 22 (AL 0.5)
(30 (1a 0.5)
Figure 4: From left to right are quantile, piecewise linear, and bowl-shaped functions (in black), and their smooth approximation functions via (i) convolution with Gaussian kernel (in green) and (ii) Moreau with o(x) = /1 + x² (in blue). Both 9ME and Jconv are 2-smooth.
Second, Moreau approximates poorly at most points, whereas convolution approximates tightly at most points, see Figure 33] second and fourth plots. This suggests that the overall approximation error by Moreau is roughly at the same magnitude as the uniform bound; thus, Moreau cannot enjoy benefits from replacing uniform bound with pointwise bounds.
If Moreau takes other functions, such as <(-) LV 1 I1-112- then GME approximate y from above. Nevertheless, the approximation quality is much lower, as shown Figure Therefore, we prefer convolution over Moreau Envelope. We also highlight that the insights drawn and distinctive features of convolution may have broader impact on other applications.
EXPERIMENTS
We run experiments on two problems (i) high-dimensional medians f(0;; y. A) = yyy - A0I1, whose convolution is given in Eq. Th: (ii) piecewise linear f(0: y, A) maxxpp[P (app y A0) b,)
whose convolution is given in Section 4.3 We use relative risks F( F(O") 100% as the per-
F(0
formance metric and compare three algorithms; namely, our algorithm C-OP; Moreau Envelope (Bassily et al. 2019 Algorithm 1); and Noisy-SGD (Bassily al. 2020 Algorithm 2). Noisy-SGD does not have smoothing step, while the other two have. Figure shows results for problem (i). It is evident that our algorithm C-OP outperforms existing methods in high-privacy regimes (sub- plots on the left). In other regimes, it still performs comparably well to Noisy-SGD. Intuitively, the improved performance of C-OP is because of our better utilization of the l structure, whereas Noisy-SGD an indiscriminate approach.
CONCLUSION
Limitation of our work. Our work is not without limitations. First, Assumption 4.4 might be hard verify in practice as it requires the knowledge of 0". Second, the assumed model still restrictive to some extent. For example, terms A(z)0 and zT 0 are assumed to be low-dimensional: otherwise, the convergence rate will blow up by an additional factor of vd. While this limitation not unique to ours but is inherent to OP, we would like to bring this issue to the community's s attention for further research.

---

Published as conference paper at ICLR 2025
relative risk (%) 0.2
0.5
Moreau NoBy-SGD
10
C-OP (Ours)
100
100
500
200
Figure 5: Relative risk v.s. sample size under various settings. Datapoint (A0, Taxa), where for the base case 5, we let 0 (.5, -5,, 1, 1, 1), and let each element of matrix A follow
(HAg 12) with μлд 0 -00001
01 For higher dimensional cases, concat multiply As and Os. Results are averaged from 50 runs. Error bar std. More results in Appendix B.7
In this paper, we studied how to apply OP to nonsmooth DP-SCO problems whose loss function has an implicit & structure. We proposed to wrap OP with additional convolution smoothing step. Convolution found many distinctive features that make more suitable than common methods such Moreau Envelope. These features facilitate tighter analysis of generalization risks, and thus under mild assumptions, convolution-then- showcase competitive performance. There many interesting directions to explore in the future, such as extending the idea in this work to more general nonsmooth functions, and how to get rid of the mild assumptions on groundtruth distributions.
can achieve optimal rates. Numerical experiments further
ACKNOWLEDGMENTS
We sincerely thank the anonymous Area Chair and reviewers for their valuable feedback that sig- nificantly improved this work. This research is supported by the Ministry of Education, Singapore, under its MOE AcRF Tier (RG117/23) grant.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Thakurta. Differentially private and lazy online convex optimization. In The Thirty Sixth Annual Conference Learning Theory, pp- 4599-4632. PMLR, 2023.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates 1I geometry. In International Conference on Machine Learning, pp. 393 393-403. PMLR, 2021.
10

---

Published as a conference paper at ICLR 2025
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. 2014 IEEE 55th annual symposium on foundations of computer science, pp. 464-473. IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33: 4381 1391-4391, 2020.
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic optimization: New results in convex and non-convex settings. Advances in Neural Information Processing Systems, 34:9317-9322 2021.
Raef Bassily, Mehryar Mohri, and Ananda Theertha Suresh. Differentially private learning with margin guarantees. Advances in Neural Information Processing Systems, 35:32127-32141, 2022.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Amir Beck and Mare Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557-580, 2012.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-5222 526, 2002.
Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, and Kevin Tian. Resqueing parallel and private stochastic convex optimization. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 2031-2058. IEEE, 2023.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Du Chen and Geoffrey A Chua. Differentially private stochastic convex optimization under quan- tile loss function. In International Conference on Machine Learning, pp. 4435-4461. PMLR, 2023.
Xi Chen, David Simchi-Levi, and Yining Wang. Privacy-preserving dynamic personalized pricing with demand learning. Management Science, 68(7))4878 4898, 2022.
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization, 22(2):674-701, 2012.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by itcration. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439 449, 2020.
Pablo Gómez, Håvard Hem Toftevaag, and Gabriele Meoni. torchquad: Numerical integration in arbitrary dimensions with pytorch. Journal of Open Source Software, 6(64):3439, 2021.
Isidore Isaac Hirschman and David V Widder. The convolution transform. Courier Corporation, 2012.
Roger Iyengar, Joseph P Near, Dawn Song. Om Thakkar, Abhradeep Thakurta, and Lun Wang. To- wards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 299-316. IEEE, 2019.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings, 2012.
11

---

Published as a conference paper at ICLR 2025
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth and sco in subquadratic steps. Advances Neural Information Processing Systems, 34:4053 4064, 2021.
Jianhao Ma and Salar Fattahi. Blessing of depth in linear regression: Deeper models have flatter landscape around the true solution. Advances Neural Information Processing Systems, 35: 34334-34346, 2022.
Shubhankar Mohapatra, Sajin Sasy, Xi He, Gautam Kamath, and Om Thakkar. The role of adaptive optimizers for honest private hyperparameter selection. In Proceedings of the aaai conference on artificial intelligence, volume 36, pp. 7806-7813, 2022.
Seth Neel, Aaron Roth, Giuseppe Vietri, and Steven Wu. Oracle efficient private non-convex opti- mization. In International conference on machine learning, pp. 7243-7252. PMLR, 2020.
Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differrnnial privacy. In International Conference on Learning Representations, 2022. URL /ttptttt///ppeeeeiieet
net fee//forue Eorum?id 70L81pp9DF
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimization, 1(3):127-239, 2014.
Rachel Redberg, Antti Koskela, and Yu-Xiang Wang. Improving the privacy and practicality of objective perturbation for differentially private linear learners. Advances in Neural Information Processing Systems, 36:13819-11 11/3388913333 1853, 2023.
Ralph Tyrell Rockafellar. Convex analysis:(pms-28) 2015.
Wenxiao Wang, Tianhao Wang, Lun Wang, Nanqing Luo, Pan Zhou, Dawn Song, and Ruoxi Jia. Dplis: Boosting utility of differentially private deep learning via randomized smoothing. Pro- ceedings on Privacy Enhancing Technologies, 4:163-183, 2021.
12

---

Published as a conference paper at ICLR 2025
A OMITTED MATERIALS AND PROOFS FOR SECTION 3
A.1 CONDITIONS ON KERNEL FUNCTIONS
Condition A. (Kernel Functions). Let k I R be nonnegative function defined on d-
dimensional real space. We assume the function & has following properties:
Integrate to 1: Sa k(b) de 1;
Central Symmetry: k(v) = k(-v), Vo E R";;
Monotonicity: k(v) is decreasing in |||| Ip for some 2 1;
Finite Moments: Kig fRm ||||| k(t) de co, Te == SuPeer k(t) k<()) < co.
A.2
PROOF OF LEMMA 3.1 PROPERTIES OF CONVOLUTION
Proof.
1. Convexity and Lipschitzness can be easily shown by definition:
(convexity) 9p(Ax + -))))= v (Ng(a + (o) + (1 A)g( + [w)) k(w) du
>gu(ar) + (1 (y)
(Lipschitzness)
gp(x)) - gu(v) = [g(x + ww) glv + vmm k(v) S L || ullp
To show smoothness, we temporarily assume the second property that Vg, (a) Ex [V f(x + μk)] true. Let TV(P, Q) and KL(P,, Q) denote the total variation and KL-divergence between distributions P and Q, Let > 0 be conjugate index such that 1/p + 1/q = 1. By definition smoothness, it suffices to show [V Vgg S 3r | yll.- Direct computation gives
/ [Vg( + (v) - Vg(y + wv) k(b) du
V - (y)ll) =
/ Vg(Hu) (u x/p) k (u auyyy/1 4/p/) du
(change variables)
$ / ( (k(u - x/p)) (u y/1il du
(triangle ineq.)
< L / 1s 1k(uu [u - - (u y /1) du
(g is L-lips cts w.r.t. 11-11p)
= 2L 2/ / [k((w) - - -k(u- - (x - 2)/4) du
2L TV(K, k 8/11).
< 2L V KL(K, + 5/1)
(8)
The integral in the third-to-last line the total variation (TV) between random variables k and k + 8/μ for any given å : x and μe; the last line is by Pinsker's inequality. Therefore, it suffices to control the KL-divergence between k and k + 8/p.
(a) When k ~ N(0, Iaxd), the KL-divergence between two Gaussians are well known:
|
KL(N(O, (), 1))
2n
see Feldman et al. 2018 yl
Theorem 33). Consequently, [[V (g) <
1 x yll
1 #
Vp [1.
(b) When the kernel function is Exponential k(v) --1lilla with 4/²T((d T(d/2)
where
r(=) f0 -e-le- dt is the gamma function, consider cases:
13

---

Published as a conference paper at ICLR 2025
i. when ||ö1|, 2 μ.: show
KL(k, +
-1llll2 In
du
n
e
l1lllll -1111 2 / do
|00|2 /2 S 1001p/14
(9)
Therefore [z) - (y)l,) - 21. |101|p D0lp:/ /u S V2L second inequality is from || /p 2 1.
|01| /ts, where the
ii. when |001, $ μr: for notational brevity, we temporarily use P. Q denote the probability measure of k, k + 8/14 respectively. By the inequality between KL- divergence and X=-divergence (L(IP, Q) Dx=(P, Q) and the fact that ex V3r when x E [0, 1].
show that
/
10-1/ul12 11) Q(v) do
e-111112
(L Q) Dx> 10-
/(( (c11011// - -1) -Q(()) de
(10)
$ 1//181//12 2 $31001,,,??
(11)
Consequently, (. (g)(l)),, s /
11000//10 VGL 1|81
Combining both cases, conclude that when exponential kernel function is used, the smoothed approximation Iμ is /6L/ smothh w.r.t. I1-Ilp
(c) When we use Laplacian kernel k: = - [Ivll, /24, the analysis idea for Exponential kernel can still apply. Specifically, we can consider two cases || | 2 μ and | || s
μ.. In the first case, can shown that KL(K, k + 8/μ1 I || [6]1, /μ which follows from equation 9 in the second case, we can also show Dx= (P, Q) S /1/51//2
as that in equation Therefore, ( Vg,(t))l, s 21 } || /22
VoL. |6]1 /p S V6 ||01, p /M, Vy [1,2].
2. Since assume loss function g is Lipschitz and convex, it implies is differentiable almost everywhere; thus, Vg(æ pk) exists with probability 1, As result that,
(z)(x)= v / g(x + (o) / Vo(x + wo)k(() du = E VV9 + 4k)].
3. Lower bound: for any x E X,
(x) = Es [g(x + p pkkk]]]]] 2 g( + E(k) g(x),
where the inequality is by Jensen's inequality, and the last equality is from the fact that [k = 0 since is centrally symmetric.
Upper bound: for any E X.
uw) (x))) g(x)) = / 10(0 ww))++w)=0- g(x)]
k(o) du s Lp [llll,((0) k(w) du Lurnp
where Hip : [|0||, k(()) (v) do Fxx [
Specially, do some calculations for K2 will N2 later. Denote the surface area a given set by S(.). well-known result from the geometry literature is that the surface area of m-dimensional Euclidean ball with radius is S(B(t) 2n 4m-1
[(m/2)
14

---

Published as a conference paper at ICLR 2025
(a) When using Gaussian kernel k ~ (0, I), we have K2 = E [[lk]l22] -
|
/m, which is by Jensen's 's inequality and by noticing that ||k|| is chi-square random variable with degree m.
(b) When using exponential kernel k(v) 1 e 11lll with n= 2=/m/3((m) that
r(m/2)
show
1 - |101|2
|elll mw n /
le -e ((((()) di
A/2
Rm
n
n
2m/
I(m + 1)
te -t
T(m/2)
mn dt = r(m)
= m.
(c) When using Laplacian kernel k(v) = c -1oll 122h
e-11el11
e 1111|
12
|,0|22
mo
||
dv
2m
2
Rm
|0y1
duy
(integrate layer by layer)
2
j=1
4. We then notice that, the central symmetry of kernel function k(() allows another represen- tation of the approximation gap, for any æ E X:
(x(x))
g(x + wv) do
(12)
JoERm
/ -''ER g(x 1 -o'))(( (kk--'))e d(-v'),
(change variables v' := -v)
g(x po (k('')((o'))
(k:()) is central symmetric)
(13)
v'eRn
Combining equation
12 and equation 1 gives
1 2
(/r VERM
g(x pv)k(v) du /
gu(x))
g(x wo)k(v)) du
vERm
g(x: + (ov + g(x vu)
k(v) do
A.3 PROOF OF LEMMA 4.1 SMALLER DOMAIN INTEGRATION
Proof. To prove the statement for the m-dimensional case, it suffices to prove the case of 1-
dimension, i.e., prove (z) {u R [etpo|te-puo |x| 0} fo R |o| >
2
|o| /u} 1 (x). For ease of notation, we omit the dependence on æ. We start with the L.b.s:
V/2 = { E IR: l + pml
+ fc pml > 2 |
I + pwl
+ x pvl
> 2 |
x + pal + |r
> 2 |z|
U E
uw
1 PER
1
<
|x||
E:E;
Es
+ pol
+ |x
> 2|
+
+ |x
> 2 |z|
U e R
e R
0 p
|z|--
0.
Es
E.
Since V,, is divided into four sets, check out each set individually.
15

---

Published as a conference paper at ICLR 2025
E1: For any u such that w |a:|, we have Jar + اnl| = x frv and |x wmi = p I; thus,
x + pol + 2z - pad = 2p > |z]. In other words, fev > |2c] is sufficient to characterize the set Ej, and the another constraint is redundant. So E {u R: p |=]).
na and | pwl pnu thus, | + poo + | poll = 2, > 2 |z]. Similarly, fev < - |o|| is sufficient. So
Eg: For any v such that pw - |ac|, we have [ - -
Ej = (u R: pe < [x]).
Eg: For any e such that 5 me S |x|, (i) if 2 0. then Jx + ped + |x Fam 2x
2 jæl: (ii) if < O, then |r + wol + x www = 22 2 |zl. The preceding two cases
indicate that no matter what a we have, læ + wvl + x foo) is always strictly equal to 2 |
Therefore, Eg @ is empty set.
Eg: Following the same idea for E3, it is easy show Eg is also an empty
Combining four cases, we conclude V = E1 U U2 f [1/1]} V
A.4 PROOF OF THEOREM 3.2 PRIVACY GUARANTEE
Proof. Let A(D) == arg ming 1 (n(;; + A 1110 + b be the output of Ac.o.. We explicitly indicate its dependence on dataset D. We are going to show, for any v and pair of neighboring datasets D D',
PRa (A(D) v)
PRA [A(D') = v) S Se, w.p. at least 1 - 8.
By firs--ordr-condditon b(AA(D); D) = = - fu(A(D): 2,) - 2nAA(D). Changing variables according function inverse theorem, the output A(D) be represented as function of b in probabilistic way; that Pr (A(D) v) (b D))- Vb(b; D)) for for any possible output Here, the right-hand-siee pdf (b(: D)) is the pdf of noise b, and Vb is function of u; det(-) is the determinant of given matrix. Therefore, we must have
Pra (A(D) vl pdf(b(A(D):D)) PR [A(D') = v) (df(b(((DD: D)))
Idet (ee(V)((( det (e((()(( D'))
Vo.
(14)
Without loss of generality, we assume D' has one more entry z' than D, which immediately implies b(A(D); ((A(((()))))))))))) + (A,()) zn).
Recall the smoothed function is Its gradient at any given 0 is, by part 2 of Lemma 3.1
f0; 2) E, [= pk]] h(z² TO).
f0; 2) E& [o (IIA(2) + / + h(2 [0)]
Ex [A(2) (gg((A))000)))))))))) nk) + zh'(2 (=T0) 0)
= A(2) T Tx [sgn( A(2) + μk)] + 2= O),
where sgn(-) is the sign vector.
Remember that, the noise b(A(D):))
No o2).
Thus, b(A(D);D'
N(Vis(A(()): zn), I). Their likelihood ratio thus becomes
exp (- [)
(df(b(A(D): D))
pdf(b(((D)) D1) exp - [I((A(D) V[A(A(D):=
((-(bL(()):)) D), ((((())))) + =.))? 102
= exp
(15)
16

---

Published as a conference paper at ICLR 2025
It should be noticed that ((A(D);; D) and (Ap() zn) are not independent, whereas Kifer al. (012)) claims they are independent, which is incorrect. This has been fixed by Redberg et al. (2023)
for linear models but not for models we considered here. There is necessity to do the proof ourselves.
We first look at the inner product in Eq. 15
(2, (b(A(D);)) D), V[)(A((); (b(A(D); D), A(z.) EE (sgn( (0((((Z))(())))) + fk)] + 2,,'(2,, A(D)))
Because b(A(D;D) o(0,o²1), we know A(2,)b(A(()) D)) Ni A(2,) A(z))o²)
Moreover, since we assume the 2-norm A(z) is uniformly upper bounded by for all z, by the fact that [sgn(-)] S 1, we have
Var D(, Eu (s)n(A(Z))) + [k)]>}] - Var [(N A(z) T (gn))"),,gn(()))
S mz
Immediately, we know if we use this upper bound, the resulting random variable will have heavier tail, and the variance can be upper bounded:
Var A(Z.) "sgn(-) 2,,'(()) S mZ² -R | I <mA' o2 + "2,0² D2
(16)
Moreover, the bounded 2-norm of matrix Azz) also indicates a bounded lg norm of (f)((
| (A(D)
Ex
[A(z) sgn + μk) + æh' (z 0) 11
s Ex
||((z)
pk) + zh' (zT0)
- Ex
[2|[(2)]
(aMA(z)Tsgn(AAiii nk) 2 1| [)][
$ 2m7² + 2D
(17)
Take log-transformation for both sides of Eq. 15) and then plug (16) and 17 back into 15 we know that the privacy loss random variable In random variable given below
pdf (br (((A)D) has lighter tail than the Gaussian
(d((b((())
[N(0, (mA² + (2) (mA² D2 /02.
It remains to find a ²² so that [N(00, 02 (mZ² + ))) - (mA² L3DD?)] /02 S with prob- ability least 1 5. By Gaussian random variable's tail bound Pr |N 12) 2 (2 s 6, it suffices to set
C² 18 (1/5) 8E)
d² 2
E2
where C == ==V/ii mm + D3, Therefore, with this o², we ensure
pdf (b(o; D)) pdf (b(u;
S e with prob. least 1 - 5.
(18)
We then come to control the ratio between two determinants Eq. 14) Denote matrix E(v) = Vb(v: (; D) Vb(v; D') 22 fz 2n). The rank of matrix E(v) over all v A(D) is at most m 1. This is because V = A VelLz [Ag + jak] zz h²(-). Because A is an m-by-d matrix and m < d, the product matrix A A is at most rank-m. Further because zz (h)(()) a rank-1 matrix, we conclude that E is at most rank- (m + 1). An immediate result is that the number of different eigenvalues between { of matrix n
A
& (A(D); + E' and { of matrix 2 F, (A(D); D) is most m 11 Therefore, the ratio between the two determinants below
17

---

Published as a conference paper at ICLR 2025
depends only on the different eigenvalues:
det( det(-nV"F,(A((D):)> -nnII E)
|det (Vb(A(D):))) (d((())((
11 101 + 2nd
del(-n (A)(- - 2nd1)
P + 2md
1 + lpg - Pil
I1: m+
2nd
B 3h
m+1
1
2nd
(19)
The last inequality is due (Sp. + -mmootttsssssss of fus which gives 1Ø pil S 3p B/. A
sufficient condition for 19) S e is X 2 (5μ + 3m)(m + 1)/(n)). Hence, if X 2 (0p (0++0((m++)) then
|det Vb((A(())))) det (b(A()) D))[
Se..
(20)
Plugging Eqs.
and 20 into equation]
14 we finally obtain,
PRA (A(D) v)
S c,, with prob. least 1 5,
Pra (A(D') = v)
if X > [B, (1.+ttm) and 0² 2 C². (8 (1/6) 8E)/ with C' := v mA² 13 D2. The lowered dependence of À on rank of matrix F2 which is m + 1 instead of d, has also been noticed by Iyengar et al. (019 and been utilized improve OP's practicability.
Lemma A.1 (Uniform Stability Lemma, Bousquet & Elisseeff 2002). Let A 2" + be a T- uniformly stable algorithum w.r.t. loss function f O x R. Let P be distribution over Z, and D ~ pp be samples i..d. drawn from P. Then, we have ED, [(((DD) F(A(D)) ST.
A.5 PROOF OF THEOREM 3.3 PRELIMINARY PERFORMANCE GUARANTEE
(b.0) and let 04 = arg ming H (:) We first decompose the excess generalization risk of A, i... R(A:P) ED.A [F()))] - F( into three parts:
Proof. Denote (0) = 0)) + 2
R(A:P) = ED.A
F(OA) ((04)
+ ED.A
(((A))
F(B') -
< EDAA
F(O^)- ((0-)
+ ED.A
(2(0-1) -
(since Sn 2 f
= =EPAA
F(ØA) )(0A)
+ Ep.A
( (0))
+ Ep [2,(0') - F(O*)
= ED.A
F(OA)- P()0)
+ ED.A
(0) (0))
+ (0) F(O"))
(21)
As a result of the decomposition. it suffices to control three parts separately. The first part can be controlled through uniform stability analysis; the second part can be upper bounded by classic analysis on empirical loss; the last part amounts to approximation error.
1. The first part can be bounded by uniform stability analysis. Specifically, we first notice fp is L = (vmA + DL,,) - continuous w.r.t. 11-112- This is because
0of. = A(z) sgg(-) (-)+ + zh'(-) = |10ofall S || || [|sgn(-)ll + ||=||, It.
S VmA DL
18

---

Published as a conference paper at ICLR 2025
Then, for any given μs, by the facts that FLA is 2X- convexity and that fr is Ls (mA D continuous, we have:
> A|0A(D)  DA(D') ||- (A'OA (A(AA(D),
-D''0AD'': (D)( f=(OA(D'): (D):
n 2T, (A((D) - (D)
n
$
which implies (A((D) - ã 0A(D")
<
Since function f is also LL-iscchii,,, we can An
conclude that Algorithm is 2
w.r.t. f.i...
An
2
- ((OA))))((((()))
VD ~ D', Vb, V/u.
An"
Then, by uniform stability lemma A. we can conclude that
AD F(O)(D)) - P(O S
2L3 An
402
(22)
An"
where C
mA² + D2 a same value as defined in Theorem 3.2
2. The second part can upper bounded by empirical loss analysis (Kifer et al. 2012 Iyengar et al. 2019). Let F (0) == (o) + A ||0l| and let @t be its minimizer; Firstly, we notice that, by the strong convexity of P.A.
(0.0*)
b, 0-
A 10 @4(1 S 1 (A*) (0))
p (0#)
f# (0^) +
n
n
|bll @ @
2
n
which implies
@@"- -
-
||b| An
Consequently, we can show
(0 ( -
+ (0A) - 2 010041 - F (F# - - 1110111)
(Ø#)
(0.04)
RA(0 (b, (0.0*) )
TA((0)))
+ A 1110011
|bll
0
0-
+ A 1011
|bll 2
110011
Xn²
which holds for any dataset D, noise b, and bandwidth μ. Therefore, taking expectation on both sides gives
E
|bbb 2
do² 11100133
EDA F.((0')
<
Anz + AR2.
(23)
An
The last inequality is by assumption that 0* is in B(R).
19

---

Published as a conference paper at ICLR 2025
Last, plugging E2 and (23 back into Eq 21 and setting À V4C²/n do /n2 n// RR, where x² 02 (8 (1/6) + 8e)/e² and C
mm² + I. D2, we can get
2C R(A:P) & 2R\
do²
+
+ [F F(O')
n
n²
d (1/5)
S 4V2CR
+ [F, - F(e)).
n²=²
B OMITTED MATERIALS AND PROOFS FOR SECTION 4
B. PROOF OF LEMMA 4.2
MONOTONICITY OF V/
Proof. For notational convenience, fix and omit the dependency on in expressions, and denote set V/, := (=) {o E I g( + (v) + g(x .v) > 2g(x)) First of all, when = 0, Vo- D. When l oo, because assume g is linear function, then V. "I {0} due to convexity of Second, because of convexity of and Jensen's ' inequality, the set V4 * 0 as long as
{
# O.
Now, we come to prove monotonicity, For any μo > 0, suppose we have the set Vno at hand. Then, for any Vag by definition of Vja. we must have
2g(x)) < g(x + pov) g(x pov); Yo Vau.
(24)
Again, because of convexity of g, we have:
g(x Mov) g(x) + (Vg(a + (ow)) An:
g(x - )) S g(x) - (Vg(æ - ~) Hot)), Ao.
Plugging the preceding two inequalities into inequality (24) gives
0< (Vg(x + (Qv) Vg(l - pn v) Ve E Viu.
(25)
We would like to highlight that the above incquality is strict.
Let #n No. We first show the weak version Vuo S Vny It suffices to show every E Vio is also in yp i.e g(x: + m1v) + g(x - m1 > 2g(x), Ve E Van- We start with the l.h.s.:
g(x + +iv) + g(x - (l = g(x + μ0 + (M) mo) + g(x no - (#1 mo)v)
1g(x + mo0) + (Vg(x + fov), (M) -o)o)]
+ [g(x wov - (Vg(x (ov), -(11 - mo)uil
(by convexity of g)
[ø(x + /b + g( [6ai
+ (#1 no) (Vg(x + wov) - Vg(a - pov). v)
Because v E Vao. we must have g(x + (g + g(x w) > 2f(x); morcover, inequality 25
implies (M1 140 (Vg(x + mov) Vg uQv), v) 0. With these two facts, immediately
conclude g(x + p)v) + g( ) > 2x) Vo E Vuo: thus Vu C Vp
Now, we move to prove the strict subset claim when g : + ||>||| is the f norm function. Let us pick the point Au for some u E VaD and À E (Mu/ 1). remains to show this point is Vμ, but not in V Woo
Au in Vy,;: It suffices to show
g(x - un xx) + g(x - p1 Ao) 2 g(x + (ov) + g(x - (oo)
>2)(e), by V.D
+ Vg(x + pov)
Vg(x - (oo), MId (oo)
>0, by incquality and À > Ho/P1
2g(x))
where the second line is by convexity of g.
20

---

Published as a conference paper at ICLR 2025
Au not in po: We prove this by contradiction. Assume X V then must have g( + )o g Mayo) 2g(x). However, this inequality is not true with gft æ | and a E 0g because || + Notvoll + || - Nouvell I = ||>||| = 2g (2:), vo 0g The preceding equality can be verified through the same idea as that in the proof of Lemma 4.
Combining both cases, we know the strict subset claim holds for g+ x + ||a||1
B.2
PROOF OF LEMMA 4.3
KERNEL-DEPENDENT APPROXIMATION ERROR
1v13 x /(v2x)
Proof.
1. When kernel function k(-) is Gaussian kernel k(v) e-
we have
[ V (x) (2)
[ + pall + ||00 well ||0||1, k(v)
9 (x)
(()(())
1ell13 /(V2T) du
|1011 e
(by Lip cts.)
0:///>//0///
S 14
1 / T du
(layer-by-layer)
J=1 00/1,/112,///4
|arz
22/T
Σ exp
2p1²
e-lloll with 2rm"//r(mm))
2. Suppose kernel is exponential kernel k(t) |==|_> == min, [|5 be the minimal element of |ac]. and let 5() be the surface mea- sure for any given set. Then, have,
[(m/2) Let
e -1lll12 |1011
0 (x) (x)) S..
do
0:/0/>/20//1
n ||01|2 -1lll
$ svmm
dv
10/0|///0///
"Vm
Le
S(B2(1))
dt
(volumn of ball)
æll
w/P
2m /2 (T(m/22)
PVm
et dt, [00|| |00l-
(T'(-) is Gamma function)
T(m)
(26)
where the function I(m + 1.r) l e- dt in 26 is the upper incomplete gamma function. The upper incomplete gamma function has closed-form when m is positive integer, i.c., I'(m + r) m! e - function has a light tail; that is, when r increases, the function value tends to zero very fast. The can be characterized if find tight upper bound for the series Σ ,
th y k= 전 Moreover, the upper incomplete gamma
21

---

Published as a conference paper at ICLR 2025
We notice that, when 3:
k
In
In
I In
(by Stirling's approximation)
Ar!
kc!
0
k=
S In
(re)
h=0
[ (re) -
In
re
(m 1) (Inr +ur+10 +1) - In (ne
(Irr+ ln
re
- 2m ln
(by r 2 3)
Consequently, an upper bound for the upper incomplete gamma function follows:
T(m + 1,r) I m!! . e 2m lur = m! e rr. pm Vr 2 3.
Immediately,
||0||| |
| |
(x) (z) - gx(x S m312 μ exp
2m In
#
3. When kernel is Laplacian kernel k:v)) = 2 e e- |lolls, we have
(x) (00)-9((()) (x)()) S 00/00/>//0///
Σ usl
[wll du
E
2
10yl. - cl / /2 dw
15:1,,1111,511
j=1
|x
1
exp
p
j=1
B.3 PROOF OF THEOREM 4.5 OP'S OPTIMAL RATES
Proof. Because we use Gaussian kernel, by Lemmas 3.3 and risk can be upper bounded
4.3
we know the excess generalization
AA(z) 13 }
(1 Vi
1 + dd (1/8) (1/8)
R(A:P) < 4V2CR-
2/ TH Eg
Σ exp
(27)
ne
2422
It remains to check the upper bound when the value μ is chosen according to the algorithm (9.tth)m+11) Moreover, Table indicates 8,, : T,,/H, where b mA + DTA.- Furthermore, by Lemma 3.3 we set = V4C2 do2/n2 R with C ;= m2² + D2 and 0² C (1/6) + 8e)/c². Therefore, combining these re- lationships together, we can explicitly find a i used by C-OP; specifically, the used is = (m+1)4, (cdm/ne"22d(mm11/ (1/8)+=)-
C-OP in Step 1, i.e.,
ne
22

---

Published as a conference paper at ICLR 2025
Now, to control pointwise approximation enror upper bound. If Gaussian kernel is used, then Lemma 4.3 implies, by law of total probability,
IA(=)0
IA(=)01
Ex
exp
E
exp
||A(2))011
21 p(()
2/12
2412
(- [A(2)001)
+ Ez
exp
)
|11A(2)0'1 <t
.1 -1- (1-p(t))
2p²
1=1
S exxp
(-P/(22))) +m (1-))())
(exp
(-1² +1 +1-p(t))
(28)
Since assumption becomes
4.4 says p(t) 1 - exp (-1/t)) Vt S if we take t v/. then Eq. 28
28 m (exp( (-1/ + exp (-1/p)) S exp (-1/u).
(29)
The preceding inequality holds only when /u smaller than the threshold Nevertheless, we will see later that the chosen tends to 0 as sample size n goes to infinity. Substituting (29) into we get the final utility guarantee:
(1 + Vdin(
R(A:P) S 4V2CR-
+ 2v 222pmxppppp (-1/H)
ns
Intuitively, if μ = 2CR 2d( (1/8)+
as cc, then the approximation error which decreases exponentially in μ. will be dominated by the polynomial term It is straightforward to find out sufficient conditions for
(m+ 1)1
2/2mmp exp(
(-1/p), cxp(-1/p)
(1/6(
4/2CR
VT
11 72
dd (1/6)
e (-1/u) < 4V2CR
+
Vn
- / S min 1,72,1/1
m
dd (1/6)
2CR(
1 + Vn
2CR no2 2d (1/8) + 2 Bn.
2CR neW + 2n(In (1/0) + +) 2 Br + (m + 1) max 1,1/72.11
m yain (1/
201 ys
n + 2d(nn (1/5) + +c)
C²R2
no² + 2d(In (1/8) + +)
(m+1)² 13
m 2CR
In
mnc 2
(30)
2C
2CR
ns² + 2d(In (1/8) + (m+ 1)² min(l.+*)
CR
The first inequality in Eq.30) ensures that the denominator in the expression of is always positive. Below are some sufficient conditions ensuring the above inequalities be true.
max f 1113 440
(m+1)"/(2dRR)
1. 8 min
2CR myn
First of all, <
maxx(87 (m++1) mon (1.
max (m 1) mnin(1,-"1)
Je2ga
is equivalent to dln (1/8) Z
C2
which implies the first and last inequalities of (30
(m+1)²/(2an")
(m+1)?/(2dd))) myn
Next, when 8
2CR /R/R
we have 8 <
2CR
2CR my/
(m+1)21.3) R?)
exp
(m+1))2 2
In
myn 2CR
which implies dnn (1/8) 2
(m+1))13
In
m 2CK
R"
23

---

Published as a conference paper at ICLR 2025
Combining both cases, we know the ó chosen is sufficient for Eq.
moxt (m + /
/3 "in(1,
2(m+1)2 In
2. 8 <
24c 122
and
We only need to
n
check the condition on E. Direct calculation gives nE²
2
2(m-11" R
my 2CR
2(m+1)2-12 RC
In
m.
(m+1) C
In
myy 2C
2CK
B.4 OMITTED DISCUSSIONS ON SOME SPECIAL CASES
Piecewise Linear Loss f(0: == max (ap, A(=)0)==)))))))))))))() + by). The piecewise linear loss is essentially linear model. The privacy guarantee follows the same proof idea in the proof of Theorem 3.2 with slight modifications. First, the piecewise linear loss does not have an f(-) function; so f(() related terms, such as 1 L2, can be removed. Second, the additional term a, makes the variance in Eq larger by at most suppe[p) [ l|ap Therefore, the multiplicative constant C' in the noise variance now should be C :- mm²
suppe[r] 1l
To obtain the optimal convergence rate, we need a analogue of Assumption 4.4 to en- sure A(=)0* stays away from the set of critical points 2 := {2 2 Ji Pl,.s. (a,,A(z))")
(az, (e..A(z)0'))) The set Z contains all z's where there are at least two pieces intersects with each other. Let r(z, Z) == min EZ {||z =00l be the distance between point and Z, where || min ..... | } is the minimal absolute value of vector z.
Another key ingredient is to ensure the set defined follow is strictly monotone in μt,
Va(x) = v POCR" Rm
max (ap, + pe) + bpp PE[P]
max ( (ap. A(2)0 0 -wo + bp}
pE[P]
max A(z)0) + by)
pel P
on which the corresponding integrand is strictly positive. However, the set (z) hard to characterize. But we can find a superset of it:
(z(2) = (v E R"
|| > r(z, Z)R²).
Because for any v s.t. || < r(z, 2)H,, the value A(z)0 + μv does not move away from the piece where A(z)0 originally lives in, we can immediately conclude that such
v & (z) ).. By a contrapositive argument, when v E V/((),, then || 1 2) ie.
" E (z).). Therefore, (₁((2) C (=(
Assumption B.1. Let ~ P. We assume there exists a threshold т 0 such that P. [r(z. 3) 2 2 exp (- vt ST
With this assumption and assumption 2.3 proof in Appendix B.3 then can go through for (z(z).
Bowl-shaped Loss f(0:2) == (I]AA) - +
with known A mxd Because the positive operator has Lipschitz constant this operator will affect noise magnitude; thus if we let the constant C m2 in o², then (c, 8)-DP is guaranteed. Regarding convergence rates, we first let == A0 Similarly, we denote
Va(2) = (u CRd (11=- + +wwl, - = + (1|=0 - -wwl1 - =)+ - -([[a=*) ||, - =)+ > 0}.
It can be shown that (x) C Sy(2), where S,(2)'ss complementary
S (x)
p 1oy
< |xf]. Vi 1...,, m,; The set $ (z) is highlighted in blue in Fig-
a | < =||00 -
ure 6. For any (x), must be true that sgn(#") sgn(#** (onn(==+/u> +ww) sgn(="- -,v),
24

---

Published as a conference paper at ICLR 2025
||x 111 x|
Figure 6: Set S (2) is in blue (when μ 1)
which follows from the first constraint in (1). An immediate consequence of the un- changed signs is
x plll + ||== - -loll 2 [ Il
(31)
The second constraint in Sp (z) implies
m
m s1n(2;) paa
(sgn(>;)) sgus=))uull= = a |101|1 S |||x0 - 21
m
| 11 +
sgn(x:) (1es + ||00||| 2 +
sgn(x;) (-pre) = 2 =2|||=>*| 1|1
m
m
(sgn(x?) (xf + pm:)) -
sgg()))) (x - -wx)) - 2 = =2||| ||1 =|
m
{sgn(a; + pwi) (x + [vv) 2
(sgn(z; - pos)) (x, - -mee - = 2 |||
plll =| + ||"=" ياal
2| 2 ||| II 2/.
(32)
With these two Eqs. (1) and (32). we are ready to show 5 (z) C Ve (z): for any v So (2), we have:
(|x= + well 2)+ + (1x= -well 2)+
|||0 + uoel1,
2/ + (|xx + 1ull - 2)
-2([[20
2)+
2
|||0 woll
2| + (1|x²* www/ |//l|
2
2 (11[x= ||
2| +
(1|20 2))
||=0 uwlll
+ 1|,0
well
2 2|122111
|| + poll
- 2| |||0
well
2||10
|| -2
2
0 = O,
where the last line is by (1 and Eq 32
The above derivation implies v E (x).
Therefore (x(2) C ((()), and consequently, (=()) c Sz)z). We next assume the distribution of = is not ill-posed.
P. We assume there exists a threshold - 0 such that P. []> |00 In 2 f 2 exp (-1/E), Vt 5T.
Assumption B.2. Let
Then, with this assumption and assumption 2.3 similarly, proof in Appendix B.3 then can go through for (z).
25

---

Published as a conference paper at ICLR 2025
B.5 PROOF OF LEMMA 4.6 PROPERTIES OF MOREAU ENVELOPE
Proof. We first introduce two Lemmas on Fenchel's conjugate that are helpful in later analysis. For function denote its Fenchel Conjugate (gy = suP (ar, y) f(x).
Lemma B.3 (Fenchel's Duality, Theorem 31.1 in Rockafellar 2015). Let f. h be two proper convex functions. the intersection between the relative interior of domains of functions f and g are nonempty, ie., ri(dom f) O ri(dom h) * 9, then one has
inf ( h(u)) sup f 1
Lemma B.4 (Conjugate Correspondence Theorem, Theorem 5.26 in Beck 2017). Let f: IR + I be a proper lower semicontinuous convex function. The following statements are equivalent:
function f is / p-smoothh with respect to ||-I|;
its Fenchel conjugate f* is p-strongly convex with respect to dual norm ||-I1-
Throughout this proof, replace the subscript ME with j to indicate the dependency param- eter μ.. By applying Lemma B.3 we first rewrite the Generalized Moreau Envelope into a dual formulation:
(z) = inf (9(u) + 0x( u)} inf {g(u) - (2))
(let oo (u) == - (x: u))
sup (h)n(()) (²())
(by Lemma B.3
y
(33)
Since
1e (1) sup (g. y) + + g)
g
(x. y) inf (x -g, y)
6x(x g)}
(safe here since domo, = R
(x. y) 0 (g),
we can plug h = (x. y) $7 (y) back into equation 33
and obtain
Iu (x) sup (w. y) (1) -g" (v)}
(34)
y
sup (xx y) (g" + (1) = =0" (z))
(35)
With the Fenchel dual expression, we are ready to show desired properties.
1. The convexity of 9μ is straightforward. as g, is obtained from minimizing convex function over convex set; thus convexity is preserved.
The smoothness comes from applying Lemma B.4 to or- Specifically, with properly chosen function & that is continuously differentiable and 3" smooth (w.r.t 1|-112), we have
[V) (o)(l)), [[V((</)) - vo(y/u)ll, S 3' 1|0/11 y/uulp
1/x 1100020 yllp
which implies Φ is 9' /p-smooth (w.rt ||.11.). Applying Lemma B.4 we know that 6% n/8'-strongly convex (w.r.t II- As result, g* + of is also // -strongyyy convex. Then applying again Lemma B.4 to g* + + we have (g* + "1 is B¹ p-smooth (w.r.t [1-11p)) By the equivalence between [g* + and 9n. i.c., Eq (35). we know 9, is 3 = 3' =33::=//usmmooot
Lastly, come show 9a is L-Lipschitz. For a given æ. pick arbitrary subgradient v E (z), We know that Fenchel- Fenchel-Young inequality can characterize subgradients when taking equality, i.c.,
(v, x:) = (x) + (T)),, Vo E (z).
(36)
26

---

Published as a conference paper at ICLR 2025
In addition, because á is strictly convex, u" := arg min g(u) + óu(( u) is unique for any æ; and therefore fu (æ) can be expressed as gu (x) = g(u") + 0u(a u²). Moreover,
we have 9 9" + pp by Eq. (3.( Hence, Eq. 33) can be equivalently rewritten
2 uu) + (v, = LHS of (36)
RHS of 36 [g(u") + @ u²)) +²]]+ (00(w) + o (v)
(37)
Since 0₂ is continuously differentiable, its subgradient set is singleton and is 06
u') = (x u² u²)}, Vx. By the second property in Lemma 4.6 i.e. Vg,
Von ( u ). the set of subgradients of gu(x) also singleton since (x) u²) (Von(> =u)) The coincidence between (2) and 0 u² implies that
the picked subgradient u E (z) should be also in d0 u²). ). By Fenchel- Young equality again, we have
(0, u²) 0u( u²) (7,)).
(38)
Subtracting Eq. from Eq. 37
results in
(v, u²) = g( + g
which implies E 0g(u"). The above analysis shows that the picked subgradient e (z)(x) belongs to two other sets 00 - u²) and 0g(u") at the same time, implying that v E do u²) (dg) S Og(u"). Therefore, the norm of is upper bounded by the largest norm of subgradients in 0g u (=), i.e.::
||a|| < gE0g(u-)
Igll
Va, v.
kindly note that u" depends on æ. By the assumption that is L-Lipschitz continuous w.r.t. |1-Ilp- subgradients in Ög(u*) are uniformly bounded w.r.t. dual norm Il-Ily- i.e., supgeag(u*) |glla S L. When we are Euclidean space ||-I1pp = |l-I11, = Il-Il2- we finally have sUPgeeg(u*) |lgll2 & L, which directly leads to
sup v (x),
|ell S
sup
lggl12 S I,
gEdg(u")
indicating that 9μ L-Lipschitz continuous.
2. The second property is a well-known result in Moreau Envelope literature, see Theorem
4. 1 in Beck & Teboulle (012). This property also indicates that gn differentiable.
3. It is easy to see
gu (x) - g(x)) = inf (g(u) + 6p - -]) g(x=)= S g(x)) (0) g(x) = ==((0), Va,
which gives the upper bound. To show the desired lower bounds, we notice that, for any x E Rd.
(x(2) g(x)) inf (g(u) 6r(x u}} g(x) inf {gg x) 00 - u)}
Vg 0g(Ø))
sup {(g, u) 2 u)}
0 (g) -
Vg E 0g(x), Va.
(39)
where the inequality is by the definition of subgradients. Further because we assume dom o² 2 Uzex0g(2), the supermum of o* is thus finite, i.e. || == sup の (g) <
Do. Therefore, Eq. 39 - is valid lower bound, which completes the proof.
27

---

Published as a conference paper at ICLR 2025
B.6 SUPPLEMENTARY MATERIALS TO SECTION 4
Condition B.I. The smooth function ø _ + R in Eq.66) should satisfy following conditions:
1. function @ is continuously differentiable, strictly convex, and -mmoohh;
2. its Fenchel conjugate function (1) == du (Vv u) o(u)) exists, and the do- main of o* is superset of subgradients set of g, i.e. dom o* Ug(x)
The first condition is common in literature. The second condition facilitates analysis through Fenchel Conjugate, which leads various results in Lemma 4.6 4.6 While the superset requirement in the second condition is not straightforward at first glance, if is L-Lipschitz continuous (w.r.t & norm), we can safely replace with sufficient alternative that dom o* requirement is much easier to check in practice.
2 B(L). The alternative
There are various eligible function, and we list out some in Table Evidently, functions in Table all meet Condition B.I However, not all ø functions in Table 2 result in approximation function GME that approximates g from above. The inequality in part Lemma 4.6 implies approximation
Table 2: Eligible Functions ((-) for (Generalized) Moreau Envelope
Functions
((x)
dom ø Smoothness
('(1)
dom ø Convexity'
Energy²
|x/|
lv/
R
Eg-norm
4' ||
Bd
8
12
Rd
3
Huber
8' x
/2
|
11,
Rd
8'
1/
l
B(3")
8'.
B//2,
otherwise.
207
Hellinger
8
||
R
8
g2
1
B(3")
with respect to 12-norm I1-11z: p.g > S.t 1/p
1/9 =:
from above only when || < 0. The only eligible á function is Hellinger. Specially, for the Hellinger function, we should set 33 to be least in order meet the superset requirement. The approximation function by Hellinger is drawn in Figure
B.7 ADDITIONAL EXPERIMENT RESULTS
B.7.1 EXCESS GENERALIZATION RISKS
Linear & loss with fixed A. In the main text, we reported numerical results for loss function f(0; y, A) = 1/ - A0 I where datapoints are (y, A) and As' elements are random variables. Now,
1
011
In this case, the optimal e* satisfies AO (-1.25, -1, 0.5); therefore, assumption 4.4 holds. Results are reported below in Figure 7 Similarly, in high-privacy and small-sample regimes (left bottom), C-OP outperforms other methods. One may notice the improvement is not significant as that shown in Figure [S] We conjecture this is because the deterministic nature of A weakens the advantage of C-OP that it can return minimizer to an ERM. With deterministic matrix A, SGD can also output a high-quality minimizer, even with high privacy.
let us fix the matrix to be deterministic matrix A :
55
01
0
501
Piecewise linear loss. We further conduct experiments under piecewise linear function
f0; y, A) = maxpeir (ap, y - AA) + bp) whose convolution given in Section 4.3 Experi- ment settings are the same that in Figure and results are shown in Figure 8 From Figure g we have similar observations: C-OP outperforms Noisy-SGD and Moreau in high-privacy regimes (for example,
0.2, 20). But when privacy requirements become less stringent, the advan- tages diminish; and finally, Noisy-SGD performs the best again (for example, æ = 5, d = 30). This suggests that when privacy is high, C-OP might be competitive alternative to Noisy-SGD.
28

---

Published as a conference paper at ICLR 2025
relative rikk (%) s= 0.2
== 0.5
8
NoBy-SGD C-OP (Ours)
00
10
d=
74
d= 20
24
100
d=330
80
200
1033
1200
20.00
320
1000
1520
20.00
500
1000
12.00
2000
550
1000
1500
2000
Figure 7: Relative risk sample size under f--norm loss. Settings the same in Figure
11.5
01 0 01
0
expect that we fix the matrix A to be deterministic A ==
-5
-650
(%6 0.2
= 0.5
8
Moreau
Noky-SGD
C-OP (Ours)
13
407
200
8
300
2000
550
2000
1500
2000
Figure 8: Relative risk v.s. sample size, under piecewise linear loss function. Settings the same as in Figure 5
29

---

Published as a conference paper at ICLR 2025
B.7.2 COMPUTATIONAL EFFICIENCY
For the ease of notation, let denote A(2)0. The computational bottleneck of C-OP the high-dimensional integration Ek [=)) + μ := JoERm. ||(==) + plll k(v) do in Eq.
When the kernel function chosen Gaussian kernel (<v) 1 Уशन admits closed form expression:
exp
(-2)
the integral
[
up
| pelll k(v) do
| + wolll -=
exp
(-2
du dum
VERm
V2T
x} 2/2,|0
[xy) ))
= |||0||1 +
2V22/TeX)) exp
242²
where (()) is the CDF of standard Gaussian random variable. However, for general kernels that only satisfy Condition A.I the convolution may not admit closed-form expressions because the integral cannot be analytically done layer by layer.
We implement the integration with torchquad Gómez et al. (0211. numerical integration module utilizing GPUs. The module conducts high-dimensional convolution by discretizing convolution integral into small bins first, and then it calculates the function value in each bin, and lastly sums them up. Because this kind of parallclization significantly benefits from GPUs, the calculation is computationally efficient. Specifically, each integration completes within 50ms graphics card, and the overall optimization completes within seconds. The source code attached supplementary materials for readers who interested in implementation details.
RTX 2060S
Table 3: C-OP Runtime (in seconds)
[
0.2
0.5
100
5
0.49
0.53
0.54
0.51
10
0.70
0.83
0.88
0.83
2.73
3.11
3.48
3.16
4.02
5.19
6.16
5.85
500
5
0.76
0.91
0.67
0.71
0.90
0.98
1.00
1.01
4.41
4.02
3.94
3.71
30
9.24
8.96
6.63
6.03
1000
0.98
1.08
0.89
0.90
1.16
1.28
1.35
1.36
5.03
5.16
5.42
5.28
30
12.04
10.23
8.98
8.64
2000
1.58
1.52
1.35
1.36
1.84
2.09
2.01
2.04
7.05
7.72
8.11
7.51
30
14.75
13.88
12.17
13.41
30


Reviews:
[{"review_id": "naUdqAL6I9", "reviewer": "Reviewer_4oV9", "summary": "The authors extend the Objective Perturbation (OP) framework for differentially private (DP) convex optimization, traditionally applied to smooth loss functions, to accommodate a specific class of nonsmooth convex losses. Specifically, they address nonsmooth functions characterized by an implicit $\\ell_1$-norm structure. Their method involves smoothing only the nonsmooth component of the objective function via convolution, followed by the application of an OP-based algorithm to uphold DP guarantees.", "questions": "Can the authors comment on the applicability and verifiability of Assumption 4.4? It would strengthen the paper to provide some concrete examples related to real-world applications where the proposed assumption holds.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The problem is well-motivated, and the core ideas of the paper are clearly articulated. Although the use of convolution to obtain a smooth approximation of a nonsmooth function is not novel in itself, it enables the derivation of interesting and novel theoretical results. The primary innovation lies in leveraging an approximation function that provides an upper bound on the original nonsmooth objective. This approach results in a new decomposition of the excess generalization risk, which is subsequently used to derive optimal generalization rates.", "weaknesses": "In my opinion, the main limitation of the paper lies in the applicability of Assumption 4.4. For example: the $\\ell_1$-norm structured nonsmooth functions which is the focus of this paper is often utilized in sparse linear regression where $\\theta^*$ is sparse. The  Assumption 4.4 does not seem to hold for such cases. Besides, without the knowledge of $\\theta^*$, one cannot verify this assumption easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nScqyyS3zf", "reviewer": "Reviewer_SBAs", "summary": "This work proposes C-OP, an algorithm for differential privacy. C-OP is designed for a specific class of problems, namely one with a smooth component and a non-smooth component containing the $\\ell_1$ norm. The key design is the random perturbation within the $\\ell_1$ norm. The algorithm achieves $\\epsilon-\\delta$ privacy with optimal excess risk.", "questions": "1. As the reviewer is not quite familiar with the literature, it would be interesting to see why previous methods that try to use convolutional smoothing fail to achieve the optimal risk but the algorithm in this paper can. Is it due to the new analysis techniques in this paper? If not, what consequence does the convolution on the smooth component bring about?\n2. As the scale of $A(z)$ decays, the problem becomes close to a smooth problem, and it seems that more noise needs to be injected into the convolution to preserve privacy. How can the authors explain this using Theorem 3?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis is technically impactful. Lemma 4.3 as a technical lemma is very useful.\n2. The presentation follows good logic.\n3. The proposed algorithm is effective in experiments.", "weaknesses": "1. It would be better if the authors could discuss the explicit result of the convolution. The reviewer did not check it, but they believe that the $\\mathbb{E}_k[A(z)\\theta+\\mu k]$ can be explicitly written in all choices of $k$ of interest. If not, the authors are expected to discuss how the convolution is implemented.\n2. It would be interesting to see the intuition of applying convolution to the part of $\\ell_1$ loss only instead of the entire objective function. See Question 1.\n3. In several subfigures of Figure 5, the plot goes out of the boundary.\n4. The discussion about the choice of $\\mu$ and $\\sigma$ is not detailed enough. It would be better if the authors could discuss whether $\\mu$ and $\\sigma$ should increase or decrease with the change of other hyperparameters.\n5. According to my understanding, the algorithm cannot be applied to the smooth setting. See also Question 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PCMxgKhnGq", "reviewer": "Reviewer_cGwQ", "summary": "The paper studies differentially-private optimization of nonsmooth convex functions. A subclass of such functions with \"hidden $\\ell_1$ structure\" is defined, for which a smoothing+objective perturbation is shown to achieve the optimal rate (which is not the case in general).\nSome experiments show the algorithm preforms well compared to baselines.", "questions": "I would appreciate the author's comments on the two issues I raised in the previous \"weakness\" box.\n\nSome additional minor comments:\n\n- Line 076: It is unclear at this point of the paper what $\\theta$ vs. $z$ are.\n- Line 082: \"and etc.\" should be simply \"etc.\".\n- Several places, including Lines 092 and 107, use \\cite (or \\citet) where \\citep is more appropriate.\n- Line 130: $B(R)$ is the ball around the origin, I suppose? This is unclear.\n- If possible, rather slightly move Algorithm 1 so that it appears at the beginning or end of the paragraph it currently cuts-off in the middle.\n- Assumption 4.4 and related discussion: the notation $\\|\\cdot\\|_{-\\infty}$ is used, perhaps should be $\\infty$ instead of $-\\infty$? Otherwise I don't understand this notation.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies an important problem, and does a good job motivating it with an excellent introduction, posing it compared to prior work.\n\nThere are several technical contributions throughout the paper, in order to apply the OP approach and prove its utility. These are explained fairly well in my opinion, and are generally of general interest.\n\nThe experiments make a convincing point that the approach considered in this work might have practical importance.", "weaknesses": "The assumptions made throughout the paper, the formulation of which are arguably the main contribution, seem pretty limiting.\n\nTwo things particularly seem limiting:\n\n1. Although the word \"hidden\" structure appears in the title and in the name of the main assumption, it actually **needs to be known explicitly** by the algorithm, if I am not mistaken. The algorithm seems to need to know the decomposition into the \"$\\ell_1$-component\" and the rest in the first place, which only holds for very structured problems such as GLMs or computing quantiles (which is indeed the one considered in the experiment).\n\n2. The results neglect the dependence on the matrix dimension $m$, which is considered a small constant. This is what really allows the smoothing approach to work here, which would otherwise have a strong dimension dependence (preventing the optimal rate, as far as I can tell). While this is true for some structured problems considered in the paper, this seems pretty specific.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)