Multi-Class Support Vector Machine with Differential Privacy
Authors: Jinseong Park
Yujin Choi
Jaewook Lee
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
support vector machine
multi-class classification
all-in-one SVM
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose a differentially private support vector machine tailored for multi-class classification.

Abstract: With the increasing need to safeguard data privacy in machine learning models, differential privacy (DP) is one of the major frameworks to build privacy-preserving models. Support Vector Machines (SVMs) are widely used traditional machine learning models due to their robust margin guarantees and strong empirical performance in binary classification. However, applying DP to multi-class SVMs is inadequate, as the standard one-versus-rest (OvR) and one-versus-one (OvO) approaches repeatedly query each data sample when building multiple binary classifiers, thus consuming the privacy budget proportionally to the number of classes. To overcome this limitation, we explore all-in-one SVM approaches for DP, which access each data sample only once to construct multi-class SVM boundaries with margin maximization properties. We propose a novel differentially Private Multi-class SVM (PMSVM) with weight and gradient perturbation methods, providing rigorous sensitivity and convergence analyses to ensure DP in all-in-one SVMs. Empirical results demonstrate that our approach surpasses existing DP-SVM methods in multi-class scenarios.

Multi-Class Support Vector Machine with Differential Privacy
Jinseong Park', Yujin Choiè, Jaewook Lee²
Korea Institute for Advanced Study
Seoul National University
j jinseongkkaas.. reciiiissreekere.. kr, fuznhigh, jaewook)@snu. ac. kr
Abstract
With the increasing need to safeguard data privacy in machine learning models, differential privacy (DP) is one of the major frameworks to build privacy-preservig models. Support Vector Machines (SVMs) are widely used traditional machine learning models due to their robust margin guarantees and strong empirical per- formance in binary classification. However, applying DP to multi-class SVMs is inadequate, the standard one-versus-rest (OvR) and one-versus approaches repeatedly query each data sample when building multiple binary classifiers, thus consuming the privacy budget proportionally to the number of classes. To overcome this limitation, we explore all-in-one SVM approaches for DP, which access each data sample only once to construct multi-class SVM boundaries with margin maximization properties. We propose a novel differen- tially Private Multi-class SVM (PMSVM) with weight and gradient perturbation methods, providing rigorous sensitivity and convergence analyses to ensure DP in all-in-one SVMs. Empirical results demonstrate that approach surpasses existing DP-SVM methods in multi-class scenarios.
(OvO)
Introduction
As machine learning models may contain sensitive information about training data samples, privacy- preserving machine learning methods are actively investigated. Differential privacy (DP) [ is one of the prominent privacy concepts by offering rigorous mathematical framework to quantify and bound the risk of disclosing single individual's data in training datasets. To hide personal information, DP methods add random perturbations to model parameters or their outputs [3. At the same time, the randomness inevitably degrades the utility of the models, it is important reduce the noise level or the number of data accesses 4
Support vector machine (SVM) 5 is one of the widely used traditional machine learning models with a strong theoretical guarantee of margin and following empirical performance in binary classification tasks. Within various privacy-preservin SVMs [6 77. Chaudhuri et al. [3] proposed DP convex optimization approach and applied it to SVM with convex margin maximization to ensure DP within the SVM framework. Later research has focused improving the convex optimization analysis to reduce noise levels [0]. Alternatively, previous papers tailored to DP-SVM frameworks [1] have proposed enhancing SVM privacy using Wolfe dual formulation. However, the multi-class classification using DP-SVMs has not been actively investigated. In multi-class classification, Park al. [33 argued that traditional one-vs-rest (OvR) one-vs-one (OvO) strategies present challenges for DP due to the need for multiple binary SVMs, leading to repeated data accesses for training samples and, consequently, a repeated consumption of the privacy budget for each classifier.
"Corresponding author "Code implementation:
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(a) One-vs-Rest SVM: accesses
(b) One-vs-One SVM:
accesses
(c) All-in-one: access
Figure 1: Illustration of multi-class classification strategies for e classes. The individual sample (+) is queried repeatedly in (a) and (b). but only once in (c). Each color represents class.
To address the problem of multiple data accesses in support vector classification, we introduce DP- friendly and straightforward solution to minimize the privacy cost of multi-class SVMs by leveraging all-in-one SVMs [7 All-in-one SVMs solve the joint convex optimization problem, which allows for single access to each data point while maximizing margins for multi-class classifiers. Fig. D demonstrates the advantages of the all-in-one method in this paper in terms of data access, compared to other strategies in multi-class scenarios.
In this paper, we propose novel differentially Private Multi-class SVM (PMSVM), which signifi- cantly reduces privacy expenditures by accessing each data point only once, based on the all-in-one multi-class SVM framework. Our approach includes two methods to obtain private model: (i) Weight Perturbation (WP), which adds Gaussian noise to the primal weight vector of all-in-one SVMs, and (ii) Gradient Perturbation (GP), which applies a smoothed hinge-loss approximation and introduces noise during gradient descent. In summary, the proposed PMSVM framework (i) reduces the number of data accesses per sample, (ii) thus achieves better utility, while (iii) preserving the key properties of SVMs. Empirical evaluations outperforms existing DP-SVM approaches in both accuracy and privacy-utility trade-offs, making practical solution for privacy-preserve multi-class machine learning models.
benchmark multi-class datasets show that our method
2 Backgrounds
2.1 Differential Privacy
Differential privacy (DP) 212 establishes mathematical framework to ensure the privacy of training data caused by changes in an individual sample, such as deletion and modification. To prevent the leakage of individual information through query responses, its formal definition is as follows:
Definition 1. (Differential privacy) A randomized mechanism M satisfies (c, d)dfiffrrenti privacy ((c, DDP if. for two neighboring datasets D. D' X, which differ in exactly one data sample, and for any set of possible ouiputs O C Range(M).
Pr(M(D) Ol e Pr(M(D') +
(1)
The privacy loss is quantified by the parameter e, where smaller values of indicate stronger privacy guarantee. The parameter ó represents the probability of failure for the mechanism M.
Definition (Te Sensitivity). For a function f D - RR. the sensitivity A defined as
AS = max [(D) ((D))ll D.D
(2)

---

where D and D' differ by at most one element.
We introduce widely used properties as remarks for DP, i.e., composition boost the sequential application, and post-processing to preserve the privacy guarantee of outputs that are already private.
Remark (Composition (2]) Let Mi & R1 be an (c1, SD) algorithm, and let M2 : X - R2 be an (62, DDP algorithm. Then, their combination M1, X - RR x R2 by the mapping: M. (Mi(), M2()) is (el + t2, ô1 + +2))-DP. For 2, the composition of k algorithms, where each algorithm meets (e, satisfies
Pr(M(D) E OJ S c Pr[M(D") E +
(3)
Remark 2. (Post-processing (21) If a mechanism M: X + R1 is (e. for any randomized mapping h: R1 - R2, h M : X - R2 is at least (c. 6)DP.
Balle and Wang 18 proposed an analytic Gaussian mechanism to reduce the noise level of DP:
Remark 3. (Analytic Gaussian Mechanism (78)) Let f be a function with Le sensitivity A. A
Gaussian output perturbation mechanism M(x) fxx with z ~ o²) satisfies (c, 6DDP for all c 2 O, the if and only if
A
60
A
60
+
8,
(4)
20
A
2x
A
where T is the cumulative distribution function of the standard normal distribution.
2.2 Multi-class Support Vector Machine
Binary Support Vector Machine Support Vector Machines (SVMs) [5] are a broadly used
machine learning method with margin maximization for building binary classification boundaries. Consider training dataset with samples, = (x,, ys } where each x; E RRd is feature vector and y {-1, +1} its corresponding label. Then, the objective of SVM is as follows:
C
n2
min- w.b
2/1
&
s.t. (:(wT +) 2 - E & 2 0, Vi,
(5)
where Rd is the weight vector, b is the bias term, & represents the slack variables accounting for misclassifications, and C is the regularization parameter controlling the trade-off between margin and errors. The Wolfe dual of Equation 5 is formulated follows:
22
n
C
T2
max
O
A. X 0 az
Σ
a.y 0, Vi,
(6)
where a {ai..... an E R" are the dual variables. Utilizing the Karush-Kutie Kuhn-Tucker (KKT), we can obtain the optimal parameter with w = Ei= d,yx,, where ä are the optimal dual parameters of the convex optimization 6 Then, the binary support function is formulated as f(x) = w x + b.
Multi-Class Support Vector Machine
The most common way to expand binary SVM to multi-class
is to use one- one-versus-one (OvR) or one-versus- (OvO) approaches by training each classifier for
each class pair or each class versus the rest, respectively. After training multiple binary classification models, we can make a decision ÿ = arg maXke w, x + by) for classes and class-wise weights Wi and bias by. Stacking the class wise weights gives weight matrix W [Wi...., wel. d
and biases E IR for multi-class classification.
Instead of calculating support vectors for each binary classification, line of work investigated training multi-class SVM 15 at once, which called all-in-one SVM methods [14). Each all-in-one method has its own design for defining the margin. Among them, Weston and Watkins 15] (WW-SVM) formulated a multi-class classification as a single joint optimization problem:
min W.b
w +
Ski
2
k=
i=1
s.t. WT, x, + by. 2 wg x, by +
Ekis Cri 2 O, h: E [c], + yo E [n].
3

---

Table 1: Comparison of multi-class SVM strategies (c: # of classes, ni # of training samples).
Method
Loss function
# variables per classifier
# classifiers
accesses per sample
OvO
pair-wise QP (convex)
2n/c
c(c- 1)/2
OvR
class-wise QP (convex)
n
C
All-in-one
joint QP (convex)
ne
1
1: we note that may depend on the implementation algorithm.
Crammer and Singer (CS-SVM proposed penalize only the largest violating class, not all pairs, per sample [16]. Then the optimization can written as follows:
min
1
ww
C
ΣE &
"
2
(8)
S.L. y. X; We X; + U 1- E,, 2 k [
where Uy equals if = =t and otherwise.
More recently, Nie et al. 17 developed concept of maximizing minimum margin SVM (M SVM),, not just maximizing the margin between class pairs. With the support function fia(x) =
(Wa w1) x + b b, between class k and for < its objective function with Ly-norm is
C n
Σ | will2
Σ Eut
min W.b 2
(9)
s.t. (Na()))) (x,( -1 Ends
2 1 Eikl,
for y = k, for y) =
ENI 2 2,
In summary, WW-SVM enforces pair-wise constraints per sample, each with its slack Exr CS-SVM imposes a single constraint by penalizing only the most-violating class and therefore uses single slack m whereas M9-SVM simultaneously applies all pair-wise constraints per sample, introducing a distinct slack Eut for every class pair.
Differentially Private Multi-Class SVM
3.1 Motivation: Advantages of All-in-One SVM for Privacy
begin by comparing the trade-offs of multi-class SVM strategies in Table Each method has its own strengths. For instance, the OvO approach requires only 2N/c dual variables per problem, which allows it to scale efficiently and be easily parallelized. The OvR method grows linearly with the number of classes, avoiding the quadratic explosion inference time. The primary advantage of the all-in-one SVM method is its ability to build a robust classifier in one step by calculating the pair-wise maximum margin at once, compared to ensemble of binary classifiers that may become overfitted to each individual class 17.. Note that efficiency improvements may vary depending on the specific implementation of each algorithm.
When focusing on privacy, we observe that all-in-one SVMs have a clear advantage. They reduce the number of data accesses needed to build classifiers. In contrast, binary classification methods such as OvO or OvR require multiple accesses data samples, which increase linearly with the number of classes consuming the privacy budget repeatedly with each access. Specifically, the composition theorem (Remark D states that the number of accesses to individual data samples directly affects the noise level if each mechanism has dependency training data. When applying this principle to the OvR case, the composition of classifiers requires ce privacy budget when each binary classifier requires Therefore, maintain the same total privacy budget, can only allocate E to each binary classifier, amplifying the amount of noise on each classifier.
In the following subsections, we propose differentially Private Multi-class SVM (PMSVM) with weight and gradient perturbations tailored for all-in-one SVMs that can significantly lower the privacy cost of building DP classifiers. In contrast existing OvO or OvR methods, the proposed PMSVM requires only one data access build a multi-class classifier, allowing us to utilize the full privacy budget

---

3.2 Weight Perturbation for All-in-one PMSVM
Motivated by the DP empirical risk minimization (ERM) methods 10 we first propose weight perturbation method for PMSVM (PMSVM-WP), In DP ERM problems, we estimate the optimal weight and protect by adding random noise proportional to the sensitivity. The sensitivity in inniiitiionnniiiaan how significantly the weight can vary with the worst-case changes to individual data points. The Wolf dual problem of the all-in-one SVMs can unified as follows 14]
min ΣE a
Σ
M My y..p.us. x3 Xj aspp ass
Σ Chip
(10)
C'
C ViE n
s.t. Pipp S PEP
Σ
aip
Σ
Cipp Vun.k k= = O, 4k A E [c].
n
i=
where Ps. -Y\ {y:} is the of non-true class indices for sample i; V...p = Con.k Cp,k with ca.k denoting the k-th component of the basis vector c, E IR;; and M My.p..... _k=1 V...p. v..k..
The convexity of convex quadratic optimization problems remains the dual formulation of all- in-one SVMs. Therefore, we take a closer look at the leave-one-out method [19] of support vector classifiers, which bounds the difference of the support function after changing To calculate the sensitivity of optimal weights and support functions, we need to track the sensitivity in the dual function since the dual variables of SVM are defined per data sample.
individual sample.
Definition 3 (Weight Perturbation). w
where z NO, o for optimal weight w.
To calculate the sensitivity of w for DP, we derive new Lemma, a multi-class extension of the leave-one-out bound of SVM [9], as follows:
Lemma 1. For convex function T, dataset D, and input scaler g()), let WD Ei= (x;). where (ō1,.... ōn) is the solution to:
min |1 322
pipp (u. g(x,)
E aTpp)s.))
3.
Let D be D with the n-th point removed, and let D be defined similarly. Then the difference of the weights between original and leave-one-out SVMs is bounded as:
lI Inl
- Amax (1),
Using this Lemma, we can calculate the sensitivity of the weights w of all-in-one SVMs. Theorem (DP guarantee of weight perturbation). W w + (Definition 3) satisfies an (e, 8)-DP when (O, II. For aw Remark 4 the sensitivity of the all-in-one SVM weight Aw is:
Aw 20
Vimase(G) (G),
Gpg -Wypr Vygg
(11)
n
where Amax is the largest eigenvalue of the Gram matrix G. The support function f(x) arg maxkeld w[x) x] is also (e, DDD..
Detailed proofs of Lemma [ and Theorem are provided in Appendix B However, this a generalized version of the weight perturbation binary setting [3 We can obtain the same sensitivity of binary support vectors in [13] with Equation 11, where yy cp. thus Aw = 2C n in L2 norm with normalization
max(]lg())ll)) = 1. This tightened version of A 4C/n in binary SVM 11]. Within all-in-one SVMs, we primarily focus on CS-SVM due to the ease of calculating Amax (G), /mmax(G)) = 2 due to My.p ey ep. Therefore, we can expand the sensitivity of binary weight to multi-class weight at cost of v2 ratio while reducing the access to training data regardless the class numbers, which gives a significant advantage for the multi-class scenario, when >> 2.
5

---

3.3 Gradient Perturbation for All-in-One PMSVM
In addition to solving the SVM dual solution through weight perturbation, we now focus on the primal solution and utilize a smoothed approximation of the hinge loss to compute gradients. Since gradient methods outperform output perturbation methods [8] we refer our approach as gradient perturbation for PMSVM (PMSVM-GP). Specifically, Nie et al. 17 proposed smoothed version of Equation for gradient updates in all-in-one SVMs, introducing a small perturbation ç 2
min W.b
Vikk
TK
+ 5²
C n
Wk will2
(12)
where Yik = 1 [w]]
2. no by: w x; bε) is replaced by the smooth approximation de (Tac) (7ik + V / for O. μ is small regularization parameter to ensure a unique solution.
Definition (Gradient Perturbation). Wi+1 = W. T) = We ne ne[M[(W. D) + z) where Z ~ (0, ow, I) for update step t E [0, [O....,-- - with gradient update mechanism Mr and learning rate T/. The final weight of the gradient update is w WT.
Due to the strong convexity of (12), following the proof of [17] and the positive definiteness of its Hessian matrix, the convergence of the loss function with gradient methods is guaranteed.
Lemma 2. (Moments accountant (20)). There exist constant e₁ and C2 so that given total steps T and sampling probability for any < T, gradient updates guarantee (e, 8y-D.. for any 5 > 0 if we choose
9V Tog(11))
2 02
(13)
To ensure the gradient updates are private, we use differentially private gradient descent (DP-GD) or its mini- batch stochastic version, differentially private stochastic gradient descent (DP-SGD). For updates, we should choose the noise level a with the privacy budget (c, 8) as follows:
Theorem 2 (DP guarantee of gradient perturbation). W++1 = w, n. [M[Me(W,, D) + zu] (Definition
and its final weight Wy satisfy (c, 6)-DP when updating as follows:
( (x,)
WHI W. nigi = we - M7 12
+ 2t
(14)
max (1, (x:)
where individual gradients of x,, v(1) (x,) = [V (x)).... !!! (x;)]. [x;)] are calculated as:
Nit + 2 +s²
x; + 21
Σ
(Wx wi) + 2pWW 1o yi.
2
+
LAK
1sf
(15)
Yik
+ Tik +5²
X4
+ 2A
Σ
(Wk wi) + 2/
k + yi:
2 2 1/x +52
Iff
and 2, N(0,, Reo21) with the in Lemma
and individual gradient clipped to size R.
Refer to the appendix of (20 for the proof of the moments accountant of DP gradient methods, while caleulate the gradients following Equation [5] To show the advantage of the proposed method by reducing the noise level, we now investigate the utility gain of our method compared to previous DP-SVMs the same privacy budget. As the objective function is strictly convex, we can guarantee a tight error bound ( 21 with gradient updates as follows:
Lemma 3. (121)) Suppose F(w) is X-strongly convex and let w = arg minw F(w). Consider the stochastic gradient update
W+11 = W. - -m..MMWW.. D)]
where El M, (w.), ) D) VF(W.). [ < G2. and the learning rate schedule qe Xe Then, for any T > 1,
B(F(wT) - F(w) = of G2 log(T) xT

---

Then, by (0, is the ratio of a in the Gaussian noise of ours to that of the OvR and OvO settings, Le., Jours/Oovt or -oors//ovo. we can make tighter bound of convergences of the noised gradient update w r compared to non-private gradient update wr as follows:
(7)
Theorem 3 (Utility Advantage). Let each mingleexxmppl loss f(w, 24) be L-Lipschitz and the population objective F(w)= = [ z)] be X-strongly convex. Consider the noisy gradient update
W++1 W T: Wt TI (nVf(WW, tzz):
Z, ~(0,
where (0, 1] is the ratio of a in the Gaussian noise. Let w/ be the T-th iteration with noise Z and Wi is without noise addition. Then, with decayed learning rate n(t) for any T>> 1,
((w)) - F(w o do do' (1-+2) log
XT
Instead, with constant learning rate r7(t) 1l 11 with <cs for any T> 1,
F[F(WT) F( F( [ = of co (1-
Thus, we theoretically prove that the reduced noise level in the all all-in-one classifier results in smaller error compared to non-private updated points.
The main reason to use clipping-based gradient updates in DP-SGD is that these approaches are ex- tensively studied, allowing us to leverage recent analytical techniques for gradient-based optimization. By the moments accountant, we can lower the privacy cost of the composition to (O(gevT), 6)-DP (0). Also, can utilize the Poisson sub-sampling [22] for mini-batch update, since private opti- mization has limited access to the data samples due to the privacy-utility trade-offs. Furthermore, adopting advanced techniques is feasible within our framework. For example, for stable convergence, we can adapt adaptive moment methods, such as Adam [23] and its DP variants [24], update the weight of Equation 14 into adaptive gradient perturbation (AGP) as follows:
m
31 m (1
B1 Bi, Vr B2V,-1 (1 B2) 3 ()),
m
V. 35 W. Wi-1 1) VV, +
m
(16)
m
Vi
with the gradient momentum m. and the second-moment accumulator v. of Equation 15 as in 24. which helps reduce the iteration complexity. Because of the post-processing in Remark Equation 16 still guarantees (c, 5)-DP guarantee of Lemma 2
Related Works
Existing DP-SVM methods primarily foeus binary classification tasks. Chaudhuri et al. investigated the use DP convex optimization SVMs, and Rubinstein et al. [1 expanded the methods with kernels with weight perturbation in binary setups. As the support vectors of dual formulation are coupled with the subset of training data, Jain and Thakurta [12) published the private weight based on the interactive scenario of model users. Ding al. [ used the gradient method for SVM with smoothed loss. None of the following works on DP-SVMs 225 26 investigated the privacy amplification of multi-class SVMs.
Park et al. 133 argued a similar research question to our paper that multi-class SVMs need multiple accesses for training. Rather than mitigating within the boundary of SVMs, they detoured from the method with a kernel clustering and labeling method. On the other hand, we directly utilized the all-in-one SVMs reduce the number of data accesses, which is compatible with the non-DP methods, such as CS-SVM or M3-SVM.
Experiments
5.1 Experimental Design
Datasets We used multi-class classification datasets from the University of California Irvine (UCI) repository [27] for various data types: Cornell (CS web pages), Dermatology (clinical skin
7

---

Table 2: Performance comparison across datasets for weight- and bold the best accuracy within each perturbation strategy.
methods. We
Weight Perturbation
Grudient
Perturbation
Data
PrivateSVM [
OPERA [
PMSVM-WP
GRPUA 9
Linear [20
PMSVM-GP
PMSVM-AGP
1
0.197 1 0.089
0.244 1 0.095
0.599
0.199
0.493 1 0.029
0.624 1 0.035
0.623 1 0.018
0.693 0.033
2
0.278 1 0.086
0.333 0.127
0.730
0.242
0.572 a 0.011
0.695 1 0.033
0.695 1: 0.032
0.707 0.023
Comeell
0.448 1.
0.50
0.761
0.244
0.692
0.747
0.010
0.723 0.026
0.782 0.023
0.597 0.20
0.282
0.770
0.250
0,746=0.00
0.012
0.789
0.024
0,765 0.024
0.240 1 0.120
0.296 1 0.131
0.711
0.098
0.787 1. 0.041
0.911 1 0.028
0.865 1 0,050
0,905 0.017
2
0.422 +-0 142
0.465 + 0. 141
0.821
0.077
0.903 0.002
0.930 + 0.018
0.954 + 0.021
0,981 + 0.042
Dermatology
0.595 0. 146
0.698 134
0.894 0 0.064
0,968
0.970 0.022
0,965 + 0.015
0.978 0.012
8
0,858 0.078
0.058
0.976=0.015 0.923=0.052
0.887 4 0.014
0.910
0.976 0.018
0.575 0.137
0.674
0.889 0.013
0.851 0.0220
0.908
0.929 0.007
0.789 0,
0.044
0.09==0.007
0,861 0..133
0.944 0.002
0,946 0.004
HIAR
4
0.889 = 0.023
0.898 0.016
0.006
0.873 00003
0.936
0.008
0.958 = 0.004
0,956 = 0.006
8
0.912 + 0.009
0.913 + 0.005
0.898 0.006
0,869 +: 0.006
0.949 + 0.002
0.962 + 0.003
0,989 0.003
0.053++0.00
0.046+0.0020
0.060=
0.466
0.442 0.011
0.501 0.025
0.054=0.017
+ 0.023
0.672 0.003 0.502=0.075
0.078
0.670 0.022
0.687 0.017
ISOLET
0.032
0.123 0.044
0.699 0.056
0.117 0.012
0.820 : 0.014
0.812 4: 0.023
0.804 0.010
0.137 + 0.048
0. 0.205+0.055
0
0.197 + 0.008
0.858 + 0.024
0.874 + 0,009
0,840 0.013
0.077
0.236
0.884=0.018
0,747 0.0118
0.875
0.009
0.879 = 0,005
0.897 0.006
2
0.257 1. 0.093
0.367 1 105
0.008 0.919
0,845 1. 0.007
0.904 1 0.009
0.911 1 0,006
0.907 0.006
USPS
0.503 + 0.121
0.642-40.088
0.925 0.007
0,876 0.005
0,922 + 0.005
0.920 + 0.003
0.917 + 0.002
0.769 0..699
0.026
0.928 0.880=00004 0.029=0.006
0.000
0.004
0.312 1.0588
0.331 1 0.055
0.070
0,568 0.052
0.661
0.696 0,060
0.356 0.073
0.345 0.053
0.307
0.0664
0.659 0.058
0.722 + 0.034
0.676 + 0,056
0.753 0.007
Vehicle
4
0.377 = 0.064
0,384 0::4:00000 0.068
0.378 0.097
0,728 0.012
0.711 + 0.035
0, 0,707 - 0.018
0.733 + 0.023
8
0.386 = 0.057
0.047
0.478 0. 0.106
0.722 = 0.020
0.729 # 0.024
0.721 = 0.063
0.766 = 0.009
records), HHAR (wearable activity sensors), ISOLET (spoken alphabet), USPS (hand-written digits), and Vchicle (vehicle silhouettes).
Baselines For comparison methods, compared with both existing weight and gradient perturba- tion methods in DP-SVMs based on OVR strategies. For weight perturbation, we compared with PrivateSVM [11 and OPERA (9]. For gradient methods, we compare with GRPUA [.] Additionally, for gradient descent 20 for a neural network classification, we used a linear layer (Linear), with the cross-entropy loss, which shares the same architecture but with the loss used in neural network classification. We exclude the DP-SVM models having interaction with users 12] and local DP 255
Experimental details For privacy budget, we fixed 10-5 on various c. We reported the mean and standard deviation on each setting, where we used 20 runs for weight perturbation and 5 runs for gradient perturbations. We performed a grid search on each method to find the well-performing one on 4, and used the obtained parameters for each model on other epsilons. We searched on C/n for weight perturbation, and learning rate ?)t gradient steps T, and fixed the clipping R = 1 for gradient methods. We further utilize the min-max scaler for weight perturbation to bound the input sensitivity to I and thus calculate the sensitivity of w easily. We utilize a Poisson sub-sampling batch size of 128 for gradient methods.
We utilized the SVM packages in Sklearn gradient descent methods based on Pytorch 30 All experiments were run on an Intel(R) Xeon(R)
28 for weight perturbation, and the Opacus 29 for
CPU E5-2680 v3 @ 2.50GHz and a single NVIDIA GeForee RTX 4090.
Code is available at hattps://o /ttes:///itttt titb... com SaatissengP//rrvvee wwaivvatemutttte _svm
Refer to
Appendix Cior further details of datasets and experimental settings.
5.2 Classification Results
Table prrsents the multi-class classification results of weight and gradient perturbation methods. In both perturbation strategies, our method, based on all-in-one SVM, surpasses previous SVM strategies in multi-class settings. For weight perturbation, our method significantly improves the performance, especially with small e, where the decision is more perturbed with noise, and thus reducing noise in our method gives a big potential for utility improvement. The observed underperformance on the Vehicle dataset likely stems from the poor baseline performance of the all-in-one SVM itself, as we used a uniform hyperparameter C' across all methods.
8

---

ProvteSii
OVERA
Ours-iP
GRPJA
Unear
(+4
(48
Weight Perturbation
(b) Gradient Perturbation
Figure 2: Accuracy gap between DP-SVM methods and their non-private baselines = oo). Lower value indicates a smaller accuracy -rivvacy-privecy trade-off, thus indicating DP-friendly property.
Gradient perturbation methods typically outperform weight perturbation methods by mitigating instability, adding noise incrementally during training rather than afterward. In both the standard gradient descent and its adaptive variant, our approach exceeds the performance the existing gradient method, GRPUA. Additionally, CE loss, confirming observations by [17 within DP scenarios.
maarin-maximizn gradients surpass linear layers with
To show the DP-friendly advantages of employing an all-in-one method, we depict the accuracy gap between DP and non-DP (e o0) settings for each method in Fig. 2 Specifically, we calculate non-DP accuracy and show the average accuracy gap across datasets listed in Table 2 where the lower value has better utility-privart trade-offs. Within a low level of privacy guarantce (higher e), the accuracy gap remains small (under 0.15), and differences among methods also small. Conversely, under tighter privacy constraints (lower e), the accuracy gap widens significantly, emphasizing the strength of each method for DP. Consequently, the proposed PMSVM method proves to be DP- friendly and consistently robust across diverse multi-class datasets. Detailed individual dataset results available in Appendix C
5.3 Additional Experiments
We now present additional experiments concerning our proposed methods.
Convergence Fig. shows the training loss, training accuracy, and test accuracy used evaluate the convergence of our method. Smaller values introduce larger noise, which hinders convergence and leads to loss divergence at 1. In contrast, with larger e, the model effectively minimizes the loss and converges well for understanding the generalization performance. Overall, adaptive optimizers achieve faster convergence the early training stages.
Accuracy
Accuracy
0.7
0.9
0.50
0.75
0.5
0.70
0.4
0.55
0.3
m=1
AGF
0.2
CP pnc
CP 2=2
A2F
A27
AGF
Epech
Spech
Epoch
Figure 3: Convergence curves of training loss, training accuracy, and test accuracy for the proposed PMSVM-GP and PMSVM-AGP methods.
Learning rate decay Classical gradient- SVMs utilize a decaying learning rate schedule 9 for convergence, while DP-based deep learning approaches often use a constant learning rate [31 to reduce the number of interactions. To investigate this further, we report accuracy and absolute
error under linear learning-rate decay Table 3] The results, including additional datasets in the Appendix, show clear advantage for either strategy.

---

Table 3: Ablation study on the effect of learning rate decay for the proposed gradient perturbation
methods. We bold the better performance in bold and Diff indicates the absolute difference w/ and w/o Ir decay. Results for other datasets are shown in Appendix C
Dataset
PMSVM-GP
+ decay
Diff
PMSVM-AGP
decay
Diff
0.663-0.010
0.67310.033
0.010
0.692-10.05
0.69211.0022
0.000
2
0.719=0.023
0.743+1.009
0.024
0.728=0.018
0.706=+0.021
0.022
Comell
4
0.771=0.014
0.752=0.010
0.019
0.772+#0019
0.748+00013
0.024
0.770=0.012 8
0.765++0001
0.005
0.769=00.029
0.774+00014
0.005
0.895=0.038
0.90810.029
0.013
0.900-10.031
0.82410.065
0.076
0.949=0.022
0.938:10.043
0.011
0.941=0.024
0.930=10.040
0.011
Dermatology
0.973=0.017
0.938+00021
0.035
0.984=0.006
0.973+00010
0.011
0.976=0.015
0.957+0..06
0.019
0.984=0.006
0.984+0.0006
0.000
Computation We then compare the computational time of existing multi-class DP-SVMs based on weight and gradient perturbation in Table Because pertureertrratiion baselines rely on the built-in scikit-learn implementations, their running times are essentially those of the OvR and all-in-one strategies: the Soummer-Singee formulation solves a single joint QP with variables, whereas OvR decomposes into с independent binary SVMs, each with n variables. Given that standard
QP solvers scale as (num of params Crammer Singer entails (nn²c²), while OvR requires O(en)). In practice (e.g., in scikit-learn using LIBLINEAR), the observed gap is smaller practically. This explains the runtime gap between OPERA and PMSVM-WV such as ISOLET. However, we highlight that the time for noise addition is negligible to ensure DP. For gradient methods, GRPUA performs e separate binary classifications and therefore takes several times longer than the proposed gradient-based private SVM, which updates all parameters all at once.
Table 4: Computation time for weight and gradient perturbation methods. We measured total training time for weight perturbation methods with seikit-learn built-in SVM in seconds, and per-iteration time for gradient perturbation methods in milliseconds (ms).
Method
Comell
Dermatology
HHAR
ISOLET
USPS
Vehicle
Average
OPERA
0.04+:001
0.01+00.0
1.37+0.11
0.62+0.08
1.10=0.68
0.01=:0.00
0.53 (sec)
Weight
Ours-WP
0.06::0.22
0.01
1.68:0.50
1.55#0.44
1.27=0.73
0.01+:0.00
0.76 (scc)
GRPUA
37.57+00.73
24.13-+0.34
44.90=3.03
86.60+ .24
47.47:2222
19.39
43.34 (ms/iter)
Gradient
Ours-GP
16.04:11.4
5.90++0.00
5.47+2.44
19.0944.26
5.03++0.51
4.06:t0.18
9.27 (ms/iter)
Further datasets and detailed results, including ablation studies on clipping threshold and batch sizes, provided in Appendix C
6 Conclusion
This paper presents a novel issue of repeated data access found existing multi-class SVM approaches under DP scenarios. By employing all-in-one methods, our framework significantly reduces the noise level through decreased data access, eliminating the need for multiple binary classifiers for both weights and gradients.
multi-class SVM framework designed to mitigate the
Limitation and Social Impact: We contribute to enhancing the trustworthiness of machine learning models through improved privacy protections. However, further experiments are necessary in domains where privacy is particularly crucial, such as healthcare, face recognition, or IoT domains.
Acknowledgments
This research was supported by the National Research Foundation of Korea (NRF) (No. RS-2024- 00338859), and the Institute of Information & communications Technology Planning & Evaluation grant funded by the Korean government (MSIT). Jinseong Park
(ITT)) (No. RS-2022-11220988 is supported by KIAS Individual Grant (AP102301) via the Center for AI and Natural Sciences Korea Institute for Advanced Study. This work was supported by the Center for Advanced Computation at Korea Institute for Advanced Study.
10

---

References
[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[2] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 933-4))21-407,, 2014. 2014
[3] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of machine learning research: JMLR, 12: 12:1099-1109 2011.
[4] Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). International Conference on Learning Representations, 2021.
[5] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20(3): 273-297, 1995.
[6] Sacrom Park, Junyoung Byun, Joohee Lee, Jung Hee Cheon, and Jaewook Lee. He-friendly algorithm for privacy-preserving svm training. IEEE Access, 8:57414-57425, 2020.
[7] Yange Chen, Qinyu Mao, Baocang Wang, Pu Duan, Benyu Zhang, and Zhiyong Hong. Privacy- preserving multi-class support vector machine model on medical diagnosis. IEEE Journal of Biomedical and Health Informatics, 26(7):3342-3353, 2022.
[8] Di Wang, Minwei Ye, Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
[9] Jiahao Ding, Sai Mounika Errapotu, Yuanxiong Guo, Haixia Zhang, Dongfeng Yuan, and Miao Pan. Private empirical risk minimization with analytic gaussian mechanism for healthcare system. IEEE Transactions on Big Data, 1(7):1107 2022.
[10] Arun Ganesh, Mahdi Haghifam, Thomas Steinke, and Abhradeep Guha Thakurta. Faster differ- entially private convex optimization via second-order methods. In Thirty- Conference on Neural Information Processing Systems, 2023.
[11] Benjamin IP Rubinstein, Peter I. Bartlett, Ling Huang, and Nina Taft. Learning in a large function space: Privacy-preserving mechanisms for svm learning. Journal of Privacy and Confidentialityy 4(1):65-100, 2012.
[12] Prateek Jain and Abhradeep Thakurta. Differentially private learning with kernels. In Interna- tional conference on machine learning, pages 118-126. PMLR, 2013.
[13] Jinseong Park. Yujin Choi, Junyoung Byun, Jaewook Lee, and Saerom Park. Efficient differen- tially private kernel support vector classifier for multi-class classification. Information Sciences, 619:889-907, 2023.
[14] Ürün Dogan, Tobias Glasmachers, and Christian Igel. A unified view on multi-class support vector classification. The Journal of Machine Learning Research, 17(1):550-1881, 2016.
[15] Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
[16] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kemel- based vector machines. Journal of machine learning research, 2DDe,) 2001.
[17] Feiping Nie, Zhezheng Hao, and Rong Wang. Multi-class support vector machine with max- imizing minimum margin. In Proceedings of the AAAI Conference Artificial Intelligence. volume 38, pages 14466-14473, 2024.
[18] Borja Balle and Yu-Xiang Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394-403. PMLR, 2018.

---

[19] Tong Zhang. A leave-one-out cross validation bound for kernel methods with applications in learning. In International Conference on Computational Learning Theory, pages 427-443. Springer, 2001.
[20] 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 ACM SIGSAC conference computer and communications security, pages
2016.
[21] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71-79. PMLR, 2013.
[22] Ilya Mironov, Kunal Talwar, and Li Zhang. R 'nyy differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6965 2014.
[24] Roan Gylberth, Risman Adnan, Setiadi Yazid, and Basaruddin. Differentially private opti- mization algorithms for deep neural networks. In 2017 International conference advanced computer science and information systems (ICACSIS), pages 387-394. IEEE, 2017.
[25] Zhenlong Sun, Jing Yang, Xiaoye Li, and Jianpei Zhang. Differentially private kernel sup- port vector machines based the exponential and laplace hybrid mechanism. Security and Communication Networks, page 9506907, 2021.
[26]
Makhamisa Senekane. Differentially private image classification using support vector machine and differential privacy. Machine Learning and Knowledge Extraction, 1(1):483 491, 2019.
[27] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http::////achhtv ics. uci. edu/ml ml
[28] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
[29] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, et al. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 1229989..229,... 2021.
[30] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, et al. Pytorch: An imperative style, high- performance deep learning library. In Advances in neural information processing systems, pages 2019.
[31] Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.16550 2022.
[32] Jinseong Park, Hoki Kim, Yujin Choi, and Jaewook Lee. Differentially private sharpness- aware training. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 27204-27224, PMLR, 23-29 Jul 2023.
[33] Jinseong Park, Yujin Choi, and Jaewook Lee. In-distribution public data synthesis with diffu- sion models for differentially private image classification. Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pages 12236-1224 2024.
12

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will attach our code as supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttpe//gguudeeeoeeouuuummbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
(f) Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:
[Yes]
Justification: is reported in the Experimental section and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, the appendix, or as supplemental material.
(g) Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report standard deviations of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
(h) Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: is written in the Experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
(i) Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This research complies with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
(i) Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
The social impact discussed the Conclusion section.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
(k) Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our method rather provides mechanism to train the model with privacy.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
()) Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We only used public code or data, and cited in the paper.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
(m) New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Our implementation relies existing assets except for code implementation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
(n) Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
(o) Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
(p) Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Notations
We summarize the important notation used in the paper Table
Table 5: Summary of notations.
Differential Privacy
M
randomized mechanism neighboring datasets privacy parameter Ly-sensitivity of Euclidean norm
D.
c
A
11
Support Vector Machine
D ((x,,;:))
training set # of samples feature dimension feature vector flattened weight vector bias term
n
d
X; E Rd
Rdxe
&
slack variable
regularization parameter dual variables
(x)
decision function # of classes
Wk E Rdd ba E RR
class-wise weight & bias weight matrix bias vector dual var for sample i, class non-true class indices
W = [WI..... wo] E RR
b = [b,...., bo] E R
0g Py. = =Y
V.kpp Cyukk Cp.
encoding vector interaction matrix
M yi P.95.8
Ex=1 w.p.k U3.9
Methodology
W
optimal primal weight
+ 2, (0, (Vy.p vn
noisy weight Gram matrix convexity, top eigenvalue learning rate clipping norm bound
G
X, Amax
T/
a 2 4V Tln(1/))
noise scale (moments accountant) margin violation
Yik - (w.. bb, w - by)
smoothing parameter sampling prob. in minibatch
q
T
total update steps
(0,
noise scaling factor
B Proofs
B.1 Proof of Theorem 1
(Restated) Lemma For a convex function T, dataset D, and input scaler g(.), let wD En áxg(x:), where a....., ā.) is the solution
Σ
Pi )(x g(x;))+ + Σ T( T(-
min
i.P 3-9
i.p
20

---

Let D" be D with the n-th point x, removed, and let wp- be defined similarly. Then the difference of the weights between original and leave-one-out SVMs is bounded as:
Iw
w < (G) (1gxxx))
1=1
Proof. Let & be the solution of Equation 10 and a!*) be the solution of Equation 10 when n-th training element removed (WLOG). Then, following the proof of Zhang [19]. taking a subgradient of T at 0ip with respect 0i the following first-order optimality condition holds:
-VIT(- aip)) + Σ
Mycpamna X Xj dia 0 vi S n, E Pa..
(17)
ja
Multiply (ā - p the equation:
(d aip) +
Σ
M
MyN x x, 03 Ōs.p) =0 vis n 1,p E py.
(18)
By the definition of subgradient, we have
-V VVT ai.p) S ST((a. T( @āāpp
(19)
Therefore, we can get
T(-ā.) Σ Man x X3 (5 dipp) $ T( -(a
(20)
1.9
Then, taking summation over i.
T T(-āa) Σ Mnnpsse x (3
x (a! a(p)
+
M Ma.pa x7 x, 0ip0
[ix]
3.9
(21)
T( T(-a
[n]
+
1
M M....u..9 X xj Cip
aln) [|]]]
(22)
2
3.
< a-1
n-1 n-1
Σ T(-ā;) + U.P
Σ
M My..p.s. x. Xy aij Σ
(23)
i.P
3a
The second inequality follows from the definition of a(m), as the proof of Lemma
Note that
since the domain of depends on i, we simply notate Σ Epep,, as Σi, and Σ Epepy Ps
Σ
T2 i.p
(and the same with j and q). Next, denote =In| 0, then,
1
ΣΣ
Σ
M My.p.uu.. X; x, (a! (a.p) āzg) S Σ Σ M yo P.Na.g Xn Ön
ip 3.
(24)
Vyn.p.k V Un Xn an.
(25)
2 P
1
x
X,. Önn (My 11 yn.
(26)
2
P-q
1
1
x x, a Gā S ||x,1ll > ( (G)ll 112
(27)
The last inequality holds because the Gram matrix is PSD. Therefore,
w wxll2 S Amax (G) 1| 112.
(28)
21

---

Using this Lemma, we can calculate the sensitivity of the weights w of all-in-one SVMs.
(Restated) Theorem 1 (DP guarantee of weight perturbation) w w (Definition 3 satisfies (e, DD when 2 ~ N (0, o I). For aw in Remark the sensitivity of the all-in-one SVM weight Aw is:
2C Vmmax(G),
Aw
Gpg = (Vy.r Vy.g)
(29)
where Amax is the largest eigenvalue of the Gram matrix G, and Vyg E IR is a vector that kth component Vy.g.k. Moreover, the support function f(xx arg max W x] is also (e, d)-DP
Proof. Firstly, we need to find the sensitivity of W. Let T(-ar.)) = - -i.p. which is affine and therefore convex. Then, Lemma | the following inequality holds:
| w S Xmax (G) || 1|,1?
(30)
For |x,||| S (xx). usually set 1 with normalization,
CR || W Vmmax (G).
(31)
By triangle inequality,
|W W < || W + |/
2Ck V Amax(())
WD
(32)
Therefore, for flattened weight w for W.
20k Axmax (G).
|W wpll2 = IWD - WDll I
(33)
Adding isotropic Gaussian noise for ow in Remark 4 therefore guarantees 6)-DP, and the post- processing property extends the guarantee the decision function f(-).
B.2 Proof of Theorem 3
(Restated) Lemma 3.
(121) Suppose F(w) is X-strongly convex and let w = arg minw F(w).
Consider the stochastic gradient update
W411 Wt mpo (M.,, D)]
where M[MM(( (w:),, D] (W:):) (..l < G and the learning rate schedule ve Then, for any T > I,
B F(wT) - F(w)] = of (og(T)
XT
(Restated) Theorem (Utility Advantage) Let each single-example loss f(w, 24) be L-Liipshitz and the population objective F(w) = E.[ ( 2)] be >-strongly convex. Consider the noisy gradient update
W =
w. (on-nn((V((.... (n
2..).
2, ~10,
where T E (0, 1] the ratio of a the Gaussian noise. Let w (5) be the T-th iterute produced with noise scale and wT is without scaling.
We follow the utility guarantee of the gradient methods strong convex case
Proof. Define
M, vV Zz,
M
n [ f(W,(W 21) + 2T77
where is sampled uniformly from the dataset, z, ~ (0, and z (7)
~
22

---

By taking expectation over 2 and then over the noise, we can obtain
BLM, we]
Vf(w,, 2;) + Elz]] = VWW,,,,
and similarly B( (T)
we] (F.w). which indicates both are unbiased estimators for gradient.
Moreover, since each f(, 2) is I.-L.ipschizz and the noise is independent of the gradient,
B|IM 2 = E n V f(w,,(wwW... 21) 11 2 V (w,, 2)). zt) + El
S n²² L + 0 do² =: G., M 1 12 S n²22 + d =: G.
By Lemma with 1/2 = 1/(At),
[[F(wT)- F(w]] = 0
00=xx
Go log XI
B[F(wL)) (r) F(w)] =0
G log T
XI
Subtracting gives
B[F(WT) - F(w,7 [w] = 0
(G--63) log
Of do d log
X7
Similarly, for constant step size c/> (0 cs f). Lemma
yields
B[F(wT)- F(W)] (n) B| B[F(w( F(w)] =0 G?),
hence
( On (62 - G?)) = O(co0 (1++))
C
Experiments
C.1
Experimental Settings
We provide the dataset statistics Table including sample size, dimensionality, and number of classes for each dataset.
Table 6: Summary of benchmark datasets used in the experiments.
Datasel
samples (n1)
dims (d)
classes (c)
Cornell HHAR
827
4,134
7
10,229
561
6
USPS
9,298
256
10
ISOLET
1,560
617
26
Dermatology
366
34
6
Vehicle
946
4
We present the experimental details the DP SVMs: weight-perturbation settings are summarised in Table 7 and gradient-perturbatin settings in Table g For weight perturbation, the regularization constant C/n is fixed across methods, as it governs the standard deviation of the Gaussian noise; the search space is (0.001, 0.005, 0.01, 0.05, 0.10. 1.0]. For gradient perturbation, we adopt the base learning rate (Base LR) and regularization C/n provided in the official implementation of Nie al. [17]. Each method is fine-tuned over epochs (5, 10, 20, 303 and learning-rate scales (0.1, 0.5, 1.0, 2.0, 5.0}; the resulting learning rate is Base LR x LR scale. Hyperparameters are selected at 4 and used for all other privacy budgets.
C.2 Additional Experiments
We present additional results on the accuracy gap shown in Fig. for the remaining datasets. Fig. 4 reports the results for weight-perturbation methods, and Fig. shows the results for gradient- perturbation methods. We present additional results on the convergence shown in Fig. for the remaining datasets in Fig. o
23

---

Table 7: Regularization constant C used in all the weight-perturbation methods.
Dataset
Cornell
Dermatology
HHAR
ISOLET
USPS
Vehicle
0.005
0.005
0.001
0.001
0.005
0.001
Table 8: Search space and best hyperparameters of gradient perturbation methods.
LR
GRPUA
Lineur
PMSVM-GP
PMSVM-AGP
Dataset
Epochss
Scule
Epochs
LR Scale
Epochs
Scale
Epochs
Scale
Cornell
0.10
0.005
10
0.1
30
0.1
HHAR
0.02
0.0005
20
0.5
30
0.1
USPS
0.01
0.001
30
5.0
30
0.5
20
0.5
20
0.5
ISOLET
0.001
0.001
20
1.0
30
2.0
30
2.0
30
5.0
Dermatology
10
0.5
10
2.0
Vehicle
0.05
0.0001
1.0
10
0.5
1.0
30
Cameel
HHAR
1.
3:3-
(a) Cornell
(b) HHAR
3.22
84
62
e4
e-4
(c) USPS
(d) Vehicle
Dermatslogy
(c) ISOLET
(f) Dermatology
Figure Weight Perturbation; Accuracy gap between DP-SVM methods and their non-private baselines (e oo). Lower value indicates smaller accuracy-privacy trade-off, thus indicating DP-friendly property.
We present additional results on the ablation studies of learning rate shown in Table for the remaining datasets in Table Furthermore, Table 10 shows the difference between selecting Rt. It is true that there is no universal rule to choose R, we concluded that R from [3 reasonable choice for the gradient method [33] Table shows the results of different batch sizes for the Poisson

---

Cennel
OPA
Can UKCP
(a) Cornell
(b) HHAR
U:5S5
1334
3.4
3.0
8.04
(c) USPS
(d) Vchicle
28
039
44
3:3
ISOLET
(f) Dermatology
Figure 5: Gradient Perturbation; Accuracy gap between DP-SVM methods and their non-priven non-private baselines (e = oo). Lower value indicates smaller accuracy-privacy trade-off, thus indicating DP-friendly property.
subsampling in Opacus 29 We use min(batch size, of training data). Compared to full batch
gradients, the results of subsampling show better performance.
25

---

Train Loss
Trainn Accuracy
Test Accuracy
1.0
0.8
0.8
0.6
0.6
Accuracty
0.4
[e]
ACP [=]
C-7
0.2
-
0.0
Epoch
Epoch
(a) Dermatology
Train Loss
Train Accuracy
Test Accuracy
0.20
0.950
0.90
0.925
0.10
0.80
0.875
0.550
0.05
0.70
0.500
Epoch
Epech
Epech
(b) HHAR
Loss
Train
Test Accuracy
0.8
0.6
Acorray
t:1
-e- AGP r:1
0.2
e-2
-a-
AGP e-
ACP
ACP p-8
Spoch
Spoch
Epach
(c) ISOLET
Train Loss
Train Accuracy
Test Accuracy
0.175
0.55
0.50
0.92
0.125
Acouracy
0.85
0.075
0.80
0.850
0.86-
0.025
Esech
Epoch
Epoch
USPS
Train Loss
Train Accuracy
Test. Accuracy
0.7
0.6
0.7
Accuracy
Accuracy
6.6
0.3
x=2
s=1
-e- AGP s=1
8 AgP u=2
0.2
- E-8
-8 AGP s-6
0.4
Epoch
Epoch
(e) Vehicle
Figure 6: Convergence curves of training loss, training accuracy, and test accuracy for the proposed PMSVM-GP and PMSVM-AGP methods.
26

---

Table 9: Ablation study the effect of learning rate decay for the proposed gradient perturbation methods. We bold the better performance in bold and Diff indicates the absolute difference w/ and w/o Ir decay.
Dataset
PMSVM-GP
Ir decay
Diff
PMSVM-AGP
+ Ir decay
Diff
0.663+000000
0.673:10.033
0.010
0.692:0.025
0.692::00222
0.000
0.71911.023
0.743-10.009
0.024
0.728
0.7061100211
0.022
Cornell
0.77110.014
0.752:10.010
0.019
0.019
0.748=1.013
0.024
0.770=1.011
0.765-10.015
0.005
0.769=0.029
0.77410.014
0.005
1
0.895
0.908
0.013
0.030
0.82411.066 0.065
0.076
2
0.949=0.022
0.908-10.043
0.011
0.021
0.93011.040
0.011
Dermatology
0.07310.017
0.938-1.0211
0.035
0.004
0.973
0.011
8
0.97610.015
0.957=0.026
0.019
0.984
0.984
0.000
0.908
0.942-40.003
0.004
0.945=0.002
0.941=0.001
0.004
2
0.953+0.004
0.953+00.002
0.000
0.956=0.001
0,949=0.003
0.007
HHAR
0.900=0.003
0.906+0.0022
0.004
0.959=0.004
0.956=0.003
0.003
8
0.962+0.002
0.056+000002
0.006
0.959
0.959+0.003
0.000
1
0.336=10.027
0.312+00.03
0.024
0.339
0.246+0.021
0.093
2
0.496+10.031 0.502
0.046
0.572=0.022
0.497=0.044 0..4
0.075
ISOLET
4
0.717=0.047
0.645=000047
0.072
0.014=0.045
0.667=00.038
0.047
0.789=0.017 8
0.687-00.022
0.102
0.023
0.789=00022
0.025
0.007
0.0004
0.012
0.908-0.005
0.912+0.005
0.004
2
0.917+00005
0.022+00001
0.005
0.909
0.921 0.001
0.002
USPS
4
0.927=10.004
0.924+0.003
0.003
0.006=0.003
0.926
0.000
0.900 8
0.927
0.003
0.927
0.929
0.002
0.604+000083
00,060
0.062
0.671-0.000
0.662+-0.021
0.009
2
0.678+00033
0.709+0.027
0.031
0.724-0.016
0.707+00025
0.017
Vehicle
4
0.727=10.030
0.729::0.020
0.002
0.753
0.739=0.011
0.014
8
0.7411:00028
0.749:10.016
0.008
0.768=0.015
0.76010.011
0.008
Table 10: Ablation study on the effect of selecting R E {0.01, 0.1, 10
Dataset
= 0.01
== 0.1
R=
1
0.677 0.007
0,681 = 0.000
0.693
0.347 0.110
2
0.679 0.003
0.687 0.006
0.707 0.002
0.560 0.034
Cornell
4
0.683
0.745 = 0.017
0.002
0.022
8
0.747 +744+000000
0.765 0.024
0.765 +.0024
0.657+
1
1.0028
0.878 = 0.070
0.171 0.0051
0.
2
0.950+0.011
0.955 0.028
0.951 +00042
0.230 + 0.084
Dermatology
0.000
0.978 = 0.016
0.97810.012
0.559 1 0.034
8
0.982 0.008
0.978 = 0.016
0.976
0.743 + 0.036
0.922 1 0.000
0.929 - 0.002
0.009
0.885 1 0.007
2
0.943
0.947 = 0.002
0.006
0.913 = 0.004
HHAR
4
0.948 0.0001
0.951 - 0.002
0.006
0.931 0.002
8
0.953
0.953 = 0.001
0.059
0.938 0.003
0.0007
0.458 0.013
0.501
0.057 0.030
2
0.661 00002
0.662 = 0.026
0.687
0.076 0.029
ISOLET
4
0.013
0.746 : 0.010
0.001
0.119 : 0.022
8
0.825
0.849 0.014
0.840+0.013
0.110 0.002
1
0.003
0.920 = 0.001
0.006
0.810 0.004
2
0.002
0.927 0.000
0.007
0.856 0.003
USPS
4
0.927 0.002
0.929 + 0.003
0.002
0.873 0.002
8
0.928 +
0.931 = 0.002
0.004
0.891 0.003
1
0.641 +0.026
0.680 0.050
0.696
0.329 0.010
2
0.716 0.001
0.007
0.484 - 0.019
Vehicle
0.015
0.727 0.014
0.733+0.023
0.578 0.071
0.009 8
0.741 + 0.020
0..069
0.673 0.038
27

---

Table 11: Ablation study on the effect of batch size for subsampling.
Dataset
bs=32
bs=64
bs=128
bs=256
bs=512
bs=full
0.478 1 10.112
0.681
1 1..000
0.693
0.032
0,408 1 0.0130
0,424 1 0.041
0,480 1 0.066
0.564 1 0.021
0.687
0.000
0.707
0.022
0.584 1 0.034
0.544 0.019
0.590
0.0224
Cornlll
0.005 0.058
0.630 0.02
0.602
0.645
0.667 0.019
0.761 0.004
0.765=0.02
=
0.661 0.02
0.671 0.007
0.297 1 0.059
0.883 10007
0.905
1.0017
0.365 1 0.068
0.260 0.2227
0.243 L0.143
1.066
1.0034
0.379 1..042
1.0097
0.320
Dermatology
1.599100.066
0.919 0.0023
0.002
0.527 1.1115
0,522 1.
0.541 1.166
0.062
0.924
0.076
0.680
0.635 0.003
0.635 0.059
0.878 0.009
0.000
0.0007
1..00
1.012
0.884
0.908 1 0.000
0.941 1.0004
0.906
1.91610.006
0.912
0.913 0.008
HHAR
0.928 0,000
0.954
0.004
0.006
0,932
0.928 1 0.000
0.932 0,005
0.000
0.000
0.009
0.004
0.000
0.943 0.003
0.059 0.010
0.045
0.501
0.025
0.063
0.03
0.014
1.022
0.004
0,687
0.017
0.034
0.060
0.037 0,005
ISOLET
0.034
0.769
0.010
0.034
0.08410.012
0.105 0.030
0.013
0.834110018
0.013
0.010
0.144 0.045
0.003
0.918
0.006
0.803 = 0.007
0.813
0.829 = 0.008
00.01
0.022
0.907
0
4854+000144
0.854 0.009
USPS
0.004
0.920
0.017
0.880 0.004
0.878 0.000
0.874 0.005
1..002
0.931
0.004
0.006
0.895 0.000
0.887 = 0.010
0.363
0.024
0.060
0.065
0.444300032
0.424 0.064
0.410 0.094
0.024
0.753
0.480
0.445 0.131
0.480 0.075
Vehicle
0.524 0.080
0.718 0.018
0.733
0.569 0.034
0.563 + 0.05
0.571 0.031
0.651 + 0.056
0.731 0.007
4.766+000009
0.659 + 0.020
0.624
0.639 + 0.040
28


Reviews:
[{"review_id": "iLfQK4ncqP", "reviewer": "Reviewer_N89T", "summary": "This paper studies the problem of ensuring differential privacy for training data in multi-class SVMs. Specifically, it proposes private training algorithms for multi-class SVMs: one based on weight perturbation (by solving the empirical risk minimization problem), and another based on gradient perturbation. The paper also analyzes the privacy guarantees of both methods.", "questions": "**1. Clarification on utility advantage in Theorem 3:** How does Theorem 3 demonstrate a utility advantage over existing approaches?\n\n**2. Technical contribution of Theorem 1:** Theorem 1 appears to be a direct application of Lemma 1 and the DP-ERM framework to the standard multi-class SVM setting. What is the technical novelty of this result? The connection between these components seems straightforward and, to a large extent, already known.\n\n**3. Novelty of Theorem 2:** The gradient perturbation method described in Theorem 2 appears to be a specific instance of the well-established DP-SGD framework, which is broadly applicable to many learning problems. What, then, is the novel contribution of Theorem 2 in this context?\n\n**4. Notation in Equation (7):** The use of notation such as $(y_i = k)$ and $(y_i = l)$ in Equation (7) is unclear and should be clarified. \n\n**5. Access frequency vs. privacy-utility trade-off:** What is the precise relationship between the number of accesses per sample and the privacy-utility trade-off? This connection is not clearly articulated in the current manuscript.\n\n6. What does $\\approx$ in (16) mean precisely?\n\n**Typo:** There appears to be a typo in the definition of the function $T(\\cdot, \\cdot)$ on Line 377. \n\nWhile I am open to revising my evaluation if the authors can provide convincing responses to these points, I currently believe that the theoretical contributions of the paper are insufficient for acceptance.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper designs differential privacy (DP) mechanisms tailored for general all-in-one multi-class SVMs.\n2. It includes comprehensive empirical evaluations.\n\n**Weaknesses:**\n\n**1. Limited novelty.** The contributions appear to be straightforward applications of existing general results to the specific setting of multi-class SVMs, largely drawn from prior work. \n\n**2. Lack of formal discussion on improved privacy-utility trade-off.** Although the abstract and introduction claim improvement in the privacy-utility trade-off, the paper does not seem to present a formal or substantial treatment of this aspect.\n\n**3. Heavily based on prior work.** Much of the content is a recollection or adaptation of existing results, with minimal original contributions.", "was_revised": true, "final_justification": "I thank the authors for taking note of my concerns, and for responding to them in a detailed manner. \nAuthors have addressed my concerns and have suggested revisions that would improve the quality (i.e., positioning with respect to prior work, technical writing and discourse) of the paper.\n\nTaking into account the authors' rebuttal, and other reviewers' comments, I am happy to increase my score to 4.", "rebuttal": "Thank you for your insightful questions. Below, we first address the major concerns [W1, W3, Q5] and then respond to the remaining points. We kindly ask that you reconsider your score after reviewing our detailed responses.\n\n**W1 Limited novelty.**\n\nWe acknowledge the reviewer's concern about novelty. However, as highlighted by other reviewers [N89T, orwF, EHLs], we strongly believe our paper presents significant novelty through the lens of differential privacy. As detailed in our Introduction and Related Works sections, following the initial DP-SVM proposal [1] or general ERM case [2], subsequent research focused exclusively on binary DP-SVM cases, leaving the multi-class scenario unexplored. However, as discussed in subsection 3.1 and Table 1, **OvR or OvO methods necessarily increase per-sample data access for each class, severely impacting DP training effectiveness** (detailed in **Q5**).\n\nWhile [3] also identified this privacy-unfriendly issue with SVM for multi-class classification, they detoured this issue with a private support vector-based clustering without actually solving the problem. On the other hand, we provide a direct solution, which is orthogonal to the existing advantages of all-in-one SVM in a non-private scenario.\n\n[1] Learning in a large function space: Privacy-preserving mechanisms for SVM learning, Journal of Privacy and Confidentiality (2012)\n\n[2] Differentially private empirical risk minimization. Journal of machine learning research (2011)\n\n[3] Efficient differentially private kernel support vector classifier for multi-class classification. Information Sciences (2023)\n\n**W3 Heavily based on prior work.**\n\nBuilding on our **W1** response, we clarify that our method is not a simple combination of existing methods.\nFirst, implementing an all-in-one SVM in DP contexts is far from trivial. In a non-private scenario, it is hard to say that all-in-one methods are significantly preferred over OvR classifiers in practice. However,  in the privacy domain, we can dramatically reduce the privacy budget of multi-class classification to the same level as binary classification. This advantage appears in neither the previous DP-SVM nor the all-in-one SVM literature.\n\nSecond, we introduce weight and gradient-based methods to guarantee DP for the all-in-one SVM.  Since SVM solves a fixed margin maximization problem using the specific objective function, previous works developed how to inject the noise within existing SVM formulations or develop a DP version of kernel tricks, not developing a new formulation of SVMs. To the best of our knowledge, existing DP-SVM research follows: within binary SVM formulations, (i) establishing efficient DP guarantees via noise injection in various components, and (ii) proving DP sensitivity, while minimally addressing multi-class scenarios.\n\nThus, our paper follows the similar flow as follows: (i) demonstrating how binary SVM-based OvO and OvR negatively impact privacy budgets in multi-class settings, (ii) developing new methods for DP-SVM with all-in-one frameworks, and (iii) theoretically proving sensitivity and showing empirical advantages across diverse experiments.\n\n**Q5. Access frequency vs. privacy-utility trade-off**\n\nWe appreciate the reviewer's question about the precise relationship between per-sample access frequency and the privacy-utility trade-off. This represents the core contribution of our paper, and we believe a thorough explanation will benefit both the reviewer and future readers. We will add the detailed explanation in the paper after the rebuttal.\n\nOur goal is to reduce the number of data accesses to individual data samples; thus, “All-in-one SVMs utilized in this work avoid redundant data accesses compared to existing one-vs-rest and one-vs-one approaches for multi-class DP-SVM, which reduce the redundant consumption for privacy budget,” noted by reviewer [orwF].\n\nThe composition theorem, one of differential privacy's most fundamental properties, is presented in Remark 1 (line 65) for two mechanisms. When we consider the general composition for $(\\epsilon,\\delta)$‑d.p. algorithms for multiple $k\\ge2$ mechanisms [1], we can similarly formulate the composition as follows (shorted version):\n\n---\n\nLet $\\mathcal{M_1}\\colon D\\to\\mathcal{C_1}$ be $(\\epsilon,\\delta)$‑d.p., and for each $k\\ge2$ let\n$\\mathcal{M_k}\\colon (D, s_{k-1},\\dots,s_{1}) \\to\\mathcal{C_k}$\nbe $(\\epsilon,\\delta)$‑d.p. for all given $(s_{k-1},\\dots,s_{1})\\in\\bigotimes_{j=1}^{k-1}\\mathcal{C_j}$.\nThen for any neighboring datasets $D,D'$ and any $S\\subseteq\\bigotimes_{j=1}^{k-1}\\mathcal{C_j}$,\n$$\\Pr\\bigl((\\mathcal{M_1},\\dots,\\mathcal{M_k})\\in S\\bigr)\\le e^{k\\epsilon}\\Pr'\\bigl((\\mathcal{M_1},\\dots,\\mathcal{M_k})\\in S\\bigr)+k\\delta$$\n\n---\n\nSimply, the composition theorem indicates that the number of accesses to data $D$ directly affects the noise level if each mechanism has a dependency on training data. When applying this principle to the OvR case, the composition of c classifiers requires c$\\epsilon$ privacy budget when each binary classifier requires $\\epsilon$. Therefore, to maintain the same total privacy budget (e.g., $\\epsilon$=8), we can only allocate $\\frac{8}{c}$ to each binary classifier, amplifying the amount of noise on each classifier.\nIn contrast, our method PMSVM requires only one data access to build a multi-class classifier, allowing us to utilize the full privacy budget $\\epsilon$. This is why we propose a multi-class DP SVM based on the all-in-one method.\n\nThanks to the reviewer’s comment, we will change Remark 1 into the above formulation and add a detailed explanation about the precise relationship between per-sample access frequency and the privacy-utility trade-off.\n\n[1] The algorithmic foundations of differential privacy, *Foundations and trends in theoretical computer science* (2014)\n\n**Q1. Clarification on utility advantage in Theorem 3**\n\nAdapting Lemma 3, which proves the convergence of optimal weight $\\tilde{\\mathbf{w}}$ and the solution of gradient update $\\mathbf{w}_T$ in a convex scenario, we prove the utility advantage in terms of convergence. We theoretically prove that the reduced noise level in the all-in-one classifier results in smaller error compared to non-private updated points.\n**Since the utility-privacy trade-off indicates how much performance we sacrifice compared to the non-private model**, the smaller convergence gap between private and non-private models demonstrates the utility advantage of our private model with reduced noise addition.\n\nTo clarify our argument, we will change line 188 to “Let $\\mathbf{w_T}^{ (\\tau)}$ be the $T$‑th iteration with noise $\\boldsymbol{z}_\\tau$ and $\\mathbf{w}_T$ is without noise addition”.\n\n**W2. Lack of formal discussion on improved privacy-utility trade-off**\n\nIn **Q5**, we explain why our method achieves better privacy-utility trade-offs through better privacy budget allocation in multi-class settings. Similarly, for gradient updates, the reduced noise level improves convergence toward the non-private optimum, as proven in Theorem 3 (line 186), detailed in **Q1**.\n\nVarious experimental results support our hypothesis about privacy-utility trade-off, which means that we obtain higher accuracies in the same privacy budget $\\epsilon$ or we require a smaller privacy budget $\\epsilon$ to get similar performance.\n\n**Q2. Technical contribution of Theorem 1 (and Typo on Line 377).**\n\nFirstly, we argue that Theorem 1 is derived with our own proof, which is not directly obtained from Lemma 1. Our method follows **a similar proof** of Lemma 1, rather than directly utilizing it. When taking a closer look at the proof of Theorem 1 in Appendix B.1, we can summarize the novelty of the proof in Theorem 1 as follows:\n\n1. We first prove that the bound of $\\mathbf{w}$ of all-in-one SVM\n2. Then, we apply the sensitivity to bound the weight parameters in the all-in-one SVM\n3. The calculated bound is tighter than o other DP-ERM methods\n\nTo push further, our proof is totally different from that of PrivateSVM, which most DP-ERM approaches rely on. We found that extending PrivateSVM's method to the all-in-one SVM is non-trivial, and our proof gives a tighter bound of sensitivity.\n\nAfter consideration, we agree that the current Lemma 1 can be confusing to the readers about our technical contribution, so we will remove Lemma 1 (originally from [1]) and replace it with a new lemma that we have proved. The lemma specific to our all-in-one SVM can be stated as follows:\n\n---\n\nFor a convex function $T$, a dataset $D$, and input scaler $g(\\cdot)$, let $\\tilde{\\mathbf{w}} _D = \\sum _{i=1}^n \\tilde{\\alpha}_i g(\\mathbf{x}_i)$, where $(\\tilde{\\alpha}_1,\\ldots,\\tilde{\\alpha}_n)$ is the solution to:\n\n$$\\min _{\\boldsymbol{\\alpha}} \\left( \\frac{1}{2} \\sum _{i,p} \\sum _{j,q} \\sum _{k} \\alpha _{i,p} \\alpha _{j,q} \\nu _{y_i,p} \\nu _{y_j,q} g(\\mathbf{x}_i)^T g(\\mathbf{x}_j) + \\sum _{i,p} T(-\\alpha _{i,p}) \\right)$$\n\nLet $D^n$ be $D$ with the $n$-th point $\\mathbf{x}_n$ removed, and let $\\tilde{\\mathbf{w}} _{D^n}$ be defined similarly. Then the difference of the weights between original and leave-one-out SVMs is bounded as:\n$\\sum _{k=1}^c ||\\mathbf{w}_k^{[n]} - \\mathbf{w}_k||^2 \\leq \\lambda _{\\max}(G) \\|\\tilde{\\alpha} _{n}\\|^2 ||g(\\mathbf{x}_n)||^2$.\n\n---\n\n**Typo.** Thus, for Line 377, the function $T$ in our proof does not need to be the same as that in Lemma 1. If we were to strictly follow the notation of the current Lemma 1, the function $T$ should be written as $T(-\\alpha_i, \\textbf{x}_i) = -\\alpha_i$. However, since $T$ is a constant function with respect to $\\textbf{x}_i$, we denoted $T$ as $T(-\\alpha _{i,p}) = -\\alpha _{i,p}$ for simplify.\n\n[1] Leave-one-out bounds for kernel methods. *Neural computation (2003).*\n\n**We will continue the response in the comments below.**"}, {"review_id": "lcZZPV4NUY", "reviewer": "Reviewer_Fj1B", "summary": "This paper studied how DP can be properly applied to multi-class SVMs. The authors presents a novel privacy-preserving multi-class SVM framework designed to mitigate the issue of repeated data access found in existing multi-class SVM approaches under DP scenarios. By employing all-in-one methods, their framework significantly reduces the noise level through decreased data access, eliminating the need for multiple binary classifiers for both weights and gradient. They provide rigorous sensitivity and convergence analyses to ensure DP in all-in-one SVMs. Empirical results demonstrate that our approach surpasses existing DP-SVM methods in multi-class scenarios.", "questions": "Please refer to the weakness section for questions.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strength__\n\nThis paper studied multi-class classification using DP-SVM, which is not actively investigated.\n\n1. To address the issue of multiple data accesses in multi-class classification, they introduce the differentially Private Multi-class SVM (PMSVM) based on the all-in-one multi-class SVM framework. This approach allows to access each data point only once.\n\n2. Their methods include two differentially private variants: PMSVM with weight perturbation and PMSVM with gradient perturbation.\n\n3. In summary, the proposed PMSVM framework reduces the number of data accesses per sample and achieves better utility-privacy trade-off.\n\n4. Empirical results show the practicality of the proposed methods.\n\nThe paper is logically written and well-organized. The empirical result (_e.g._, Figure) supports their claims.\n\n__Weakness__\n\nHere are some questions that I think may help improve this paper.\n\n1. Line 92: the preprositional phrase _Instead of calculating support vectors for each support vector, ..._ is confusing. Could the authors clarify what is meant here?\n\n2. Line 94: The $y_{i,kl}$ appears only once. What does this term mean?\n\n3. The first two constraints in Eq. (7) are ambiguous. _e.g._ What does $\\xi_{ikl}(y_i = k)$ represent?\n\n4. Lemma 1 presents a leave-one-out bound for SVM. Could the authors clarify the form of the input scaler $g(\\cdot)$ and the convex function $T$ look like in the binary support vector machine defined in Eq. (4)?\n\n5. Line 143: The $\\sigma_w$ does not appear in Eq. (3). Instead, it first appears in Remark 3.\n\n6. What is the difference between $\\hat{w}_t$ and $w_t$ in Definition 4 or Lemma 3? Is it a typo?\n\n7. Line 164: Could the authors give a brief proof on the convexity of Eq. (12)?\n\n8. Line 175: The hyperparameter $R$ is fixed at 1. Is there any guiding principle for selecting an appropriate value of $R$?\n\n9. It is well-known that strict convexity does not necessarily imply strong convexity. Could the author provide a brief proof to demostrate the strong convexity of Eq. (12)?\n\n10. Lines 221 and 224: Is the $\\varepsilon$ in $\\varepsilon=4$ equivalent to the $\\epsilon$ defined as the privacy budget?\n\n11. Why is the difference significant between Ours-WP and OPERA on ISOLET? Could the authors give some insights?", "was_revised": true, "final_justification": "The authors have addressed my concerns that include:\n\n(1) Give a clear introduction on how they use Lemma 1 and Theorem 1 to guarantee the validity of the proposed method.\n\n(2) Show a detailed proof of the convexity of Eq. (2), which ensures the convergence of the loss function to the global minimum\n\n(3) Provide a concise and insightful analysis on the gap of computational time between OPERA and PMSVM-WP", "rebuttal": "First of all, we thank the reviewer for reading our paper carefully and suggest various ways to improve the quality of our paper. We now answer the question individually.\n\n**W1.  Line 92 “*Instead of calculating support vectors for each support vector”***\n\nThank you for advising on the clarity of the proposed paper. We agree that this phrase might confuse the readers. We will change it to “***Instead of calculating support vectors for each binary classification”.***\n\n**W2. Line 94 notation $y_{i,kl}$**\n\nIt means the label of $y_{i}$, when we consider the binary classification of class $k$ and $l$, similar to line 94 “$\\upsilon_{y_i,k}$ equals 1 if $k=y_i$ and 0 otherwise.”\n\nHowever, the notation is used only once, and the $y_i, i \\in [n]$ indicates a multi-class label in Equation 5; Thus, we remove the notation of $y_{i,kl}$.\n\n**W3. Equation 7**\n\nAs the reviewer suggested, we will revise Equation (7) as follows:\n\n\\begin{cases}\nf_{kl}(\\mathbf x_i) \\ge 1 - \\xi_{ikl}, & \\text{where } y_i = k \\\\\\\\\nf_{kl}(\\mathbf x_i) \\le -1 + \\xi_{ikl}, & \\text{where } y_i = l\n\\end{cases}\n\n**W4. Lemma 1 compared to the binary case**\n\nWe apologize for the confusion. Firstly, we explain how the current Lemma deals with the binary SVM case and decide to change the Lemma with the proof part of the all-in-one case proof of Theorem 1, which is now in the Appendix.\n\n**The clarity of the current Lemma 1 in binary SVM.** Lemma 1 is a generalized version of the leave-one-out bound for kernel methods [1] and can be applied to cover binary SVM, since the proof of the lemma is for general case using subgradient of the convexity of $T$ and the definition of optimal $\\tilde{\\alpha}$ and $\\tilde{\\alpha}^{[k]}$.\nSpecifically, let transform Eq. (4)\n\n$\\max_{\\alpha} \\sum_{i=1}^{n} \\alpha_i - \\frac{1}{2} \\sum_{i=1}^{n} \\sum_{j=1}^{n} \\alpha_i \\alpha_j y_i y_j x_i^\\top x_j =  \\min_{\\alpha}  \\frac{1}{2} \\sum_{i=1}^{n} \\sum_{j=1}^{n} \\alpha_i \\alpha_j y_i y_j x_i^\\top x_j - \\sum_{i=1}^{n} \\alpha_i$.\n\n(We skip bold for vector due to the limit.) In this setting, $g(x) = x$ and $T(-\\alpha, x)$ is convex (affine) with respect to $\\alpha$.\n\nWith this formula, the lemma can be modified as:\n\n$\\min_{\\alpha}  \\frac{1}{2} \\sum_{i=1}^{n} \\sum_{j=1}^{n} \\alpha_i \\alpha_j y_i y_j g(x_i)^\\top g(x_j) +\\sum_{i=1}^{n} T(-\\alpha_i, x_i)$\n\nThis version of Lemma 1 can be proved in the same way as the original proof:\n\n---\nproof:\n\nSince $-\\nabla_1 T(-\\tilde{\\alpha}_i, x_i) +  \\sum _{j=1}^{n}\\tilde{\\alpha}_j y_i y_j  g(x_i)^\\top g(x_j) = 0$,\n\n$-\\nabla_1 T(-\\tilde{\\alpha}_i, x_i)(\\tilde{\\alpha}_i^{[k]}-\\tilde{\\alpha}_i) +  \\sum _{j=1}^{n} \\tilde{\\alpha}_j y_i y_j g(x_i)^\\top g(x_j)(\\tilde{\\alpha}_i^{[k]}-\\tilde{\\alpha}_i) = 0$. By the definition of subgradient, we have\n\n$-\\nabla_1 T(-\\tilde{\\alpha}_i, x_i)(\\tilde{\\alpha}_i^{[k]}-\\tilde{\\alpha}_i) \\leq T(-\\tilde{\\alpha}_i^{[k]},x_i)-T(-\\tilde{\\alpha}_i, x_i)$.\n\nTherefore, $T(-\\tilde{\\alpha}_i, x_i)- \\sum _{j=1}^{n} \\tilde{\\alpha}_j y_i y_j g(x_i)^\\top g(x_j)(\\tilde{\\alpha}_i^{[k]}-\\tilde{\\alpha}_i) \\leq T(-\\tilde{\\alpha}_i^{[k]}, x_i)$.\n\nSumming over $i$, utilizing the definition of $\\tilde{\\alpha}_i^{[k]}$, and denote $\\tilde{\\alpha}_i^{[n]}=0$ as in the original proof. WLOG $k = n$, and since $y_i^2 =1$, then we can obtain:\n\n$\\sum_{i=1}^{n}\\sum_{j=1}^{n} y_iy_jg(x_i)^\\top g(x_j)(\\tilde{\\alpha}_i^{[k]}-\\tilde{\\alpha}_i) (\\tilde{\\alpha}_j^{[k]}-\\tilde{\\alpha}_j) \\leq \\tilde{\\alpha}_n^2 ||g(x_n)||_2^2$\n\nTherefore, for $\\tilde{w}_D =\\sum _{i=1}^{n} \\tilde{\\alpha}_i y_i g(x_i)$, we can get  $||{\\tilde{w}_D}-{\\tilde{w} _{D^k}}||_2 \\leq |\\tilde{\\alpha} _{k}| ||g(x_k)||_2.$\n\n**New Lemma 1.** As pointed out by reviewer [N89T], we do not utilize Lemma 1 directly, *but just adopt the proof strategy.* To avoid confusion, we will remove Lemma 1 (originally from [1]) and replace it with a new lemma that we have proved in the proof of Theorem 1. The lemma specific to our all-in-one SVM can be stated as follows:\n\n---\n\nFor a convex function $T$, a dataset $D$, and input scaler $g(\\cdot)$, let $\\tilde{w}_D=\\sum _{i=1}^n \\tilde{\\alpha}_i g(x_i)$ where $(\\tilde{\\alpha}_1,\\ldots,\\tilde{\\alpha}_n)$ *is the solution to:* $\\min _{{\\alpha}} \\left(\\frac{1}{2} \\sum _{i,p}\\sum _{j,q}\\sum _{k}\\alpha _{i,p}\\alpha _{j,q}\\nu _{y_i,p}\\nu _{y_j,q} g(x_i)^\\top g(x_j)+\\sum _{i,p} T \\left(-\\alpha _{i,p}\\right)\\right).$\nLet $D^n$ be $D$ with the $n$-th point $x_n$ removed, and let $\\tilde{w} _{D^n}$ be defined similarly. Then the difference of the weights between original and leave-one-out SVMs is bounded as:\n$\\sum _{k=1}^c ||\\tilde{w} _k^{[n]} - \\tilde{w} _k||^2 \\leq \\lambda _{\\max}(G) |\\tilde{\\alpha} _{n}\\|^2\\|g(x_n)||^2.$\n\n---\n\nWe believe that this change makes the connection between Lemma  and Theorem clear.\n\n[1] Leave-one-out bounds for kernel methods. *Neural computation (2003).*\n\n**W5, W6, W10. Typos**\n\nThank you. It is obvious typos. We will revise it. \n\nFor W6, we will also include the following rules for readability concerning the notations of $\\mathbf{\\cdot}, \\tilde{\\cdot}, \\hat{\\cdot}$.\n\n$\\mathbf{\\cdot}$: general case such as subsection 2.2\n\n$\\tilde{\\cdot}$: optimal (or empirical) weight without noise addition (as in Definition 3)\n\n$\\hat{\\cdot}$: perturbed (thus private) weight with noise addition\n\n \n\n**W7, W9. Convexity of Eq. (12)**\n\n**Convexity**. We first prove the convexity of Eq. (12). We follow the proof of [1], detailed in Appendix A.1.\n\n$$\n\\min_{W,\\mathbf{b}}  \\sum _{i=1}^{n}\\sum _{k\\neq y_i}        \\frac{\\gamma _{ik}+\\sqrt{\\gamma _{ik}^{2}+\\varsigma^2}}{2}  +    \\frac{C}{n}\\sum _{k<l}||\\mathbf{w}_k-\\mathbf{w}_l|| _{2}^{2} \n$$\n\nFor the first term, it is obvious that the hinge loss term is convex. In detail, \n\n$$\ng(x)=\\frac{x+\\sqrt{x^2+\\delta^2}}{2},\n\\quad\ng''(x)=\\frac{\\delta^2}{4(x^2+\\delta^2)^{3/2}}\\ge0,\n$$\n\n$$\n\\gamma_{ik}(W,b)\n=1-\\bigl(w_{y_i}^\\top x_i - w_k^\\top x_i + b_{y_i}-b_k\\bigr),\n\\quad\n\\gamma_{ik}\\bigl(\\mu(W,b)+(1-\\mu)(V,c)\\bigr)\n=\\mu\\gamma_{ik}(W,b)+(1-\\mu)\\gamma_{ik}(V,c),\n$$\n\n$$\nf_1(W,b)\n=\\sum_{i=1}^n\\sum_{k\\neq y_i}g\\bigl(\\gamma_{ik}(W,b)\\bigr),\n\\quad\nf_1\\bigl(\\mu(W,b)+(1-\\mu)(V,c)\\bigr)\n\\le\\mu f_1(W,b)+(1-\\mu) f_1(V,c).\n$$\n\nFor the second term, it is also convex because\n\n$$\n\\mathcal{M}(\\mu W + (1-\\mu)V)\n= \\sum _{k=1}^{c-1}\\sum _{l=k+1}^{c}\nh\\bigl(\\mu(\\mathbf{w}_k - \\mathbf{w}_l) + (1-\\mu)(\\mathbf{v}_k - \\mathbf{v}_l)\\bigr)\n\\le \\sum _{k=1}^{c-1}\\sum _{l=k+1}^{c}\n\\bigl(\\mu h(\\mathbf{w}_k - \\mathbf{w}_l) + (1-\\mu) h(\\mathbf{v}_k - \\mathbf{v}_l)\\bigr)\n= \\mu\\mathcal{M}(W) + (1-\\mu)M(V).\n$$\n\nDetailed analysis is in Appendix A.1 of [1].\n\n**Strong convexity.**\nIt is true that the (strict) convexity does not guarantee strong convexity; thus, the theoretical analysis of Theorem 3 might not be true. The Hessian of both the first and second terms of Equation 12 is positive semi-definite, and thus can be zero. For strong convexity, we need a **positive definite** Hessian matrix.\n\nSpecifically, for the first term, since $g''(x) = \\frac{\\delta^2}{4(x^2+\\delta^2)^{3/2}} \\to 0$ as $|x| \\to \\infty$ and $\\gamma_{ik}$ is linear in $W$, the Hessian can vanish along certain directions. For the second term, the pairwise regularization $\\sum_{k<l}\\|\\mathbf{w}_k-\\mathbf{w}_l\\|_2^2$ has a null space corresponding to uniform translations $\\mathbf{w}_k \\to \\mathbf{w}_k + \\mathbf{v}$ for all $k$, yielding $\\mathbf{v}^T\\nabla^2 f_2\\mathbf{v} = 0$ for $\\mathbf{v} = [\\mathbf{u}, \\mathbf{u}, \\ldots, \\mathbf{u}]^T$. Thus, both terms have a **positive semi-definite** Hessian.\n\nWe thus revisit [1] and revised Equation 12 to have a regularization term $\\mu(||{W}||^2_F+||\\mathbf{b}||_2^2)$ term (Eq 25 in [1]). As the regularizer is the sum of quadratic terms w.r.t. $W$ and $\\mathbf{b}$, it ensures a **strong convexity**. \n\n$$\n\\min_{W,\\mathbf{b}}  \\sum _{i=1}^{n}\\sum _{k\\neq y_i}        \\frac{\\gamma _{ik}+\\sqrt{\\gamma _{ik}^{2}+\\varsigma^2}}{2}  +    \\frac{C}{n}\\sum _{k<l}||\\mathbf{w}_k-\\mathbf{w}_l|| _{2}^{2} + \\mu(||{W}||^2_F+||\\mathbf{b}||_2^2)\n$$\n\nThen, we can ensure the total Hessian is $\\mathbf{x}H\\mathbf{x}>0$ for $\\forall \\mathbf{x} \\neq 0$ with a positive definite regularization term, thus strong convexity. We will revise the gradient updates in Theorem 2 correspondingly. \n\n**Experiments.** In experiments, as we used the base code of [1], we already used $\\mu>0$ (para.lam in main-opacus.py in supplementary code, e.g., 0.0005 for HHAR, 0.005 for Cornell, …). \n\nWe really appreciate the reviewer of this analysis.\n\n[1] Multi-class Support Vector Machine with Maximizing Minimum Margin, AAAI 2024.\n\n**W11. Ours-WP and OPERA on ISOLET**\n\nWe understand this question concerns the runtimes in Table 4. If not, please let us know.\n\nRegarding runtime between OPERA and PMSVM‑WP, we use scikit‑learn’s “LinearSVC,” which implements the OvR method for multi‑class classification for OPERA. In contrast, PMSVM‑WP uses the “crammer_singer” option.\nThus, the difference relies only on the implementation of two methods in sklearn because the proposed weight perturbation requires only an additional single noise‑addition step: $O(1)$ per parameter, i.e., $O(\\text{num of params})$ overall. \n\nTo explain the computational part, we can think that the Crammer–Singer formulation solves a single joint QP with $nc$ variables, whereas OvR decomposes into $c$ independent binary SVMs, each with $n$ variables. Given that standard QP solvers scale as $O(\\text{num of params}^3)$, Crammer–Singer entails $O(n^3c^3)$, while OvR requires $O(cn^3)$. In practice (e.g., in scikit‑learn using LIBLINEAR), the observed gap is about $O(c)$ times practically. This explains the runtime gap between OPERA and PMSVM‑WP. We will add this discussion to the main paper and the appendix on weight‑perturbation computation. \n\nOn the other hand, for gradient perturbation, because the model is updated in a single pass rather than via sequential OvR training, PMSVM‑GP is superior to GRPUA in both performance and computational efficiency.\n\n**We will continue the response of W8. hyperparameter $R$ in the comments below.**"}, {"review_id": "Zbq8b3kvhw", "reviewer": "Reviewer_orwF", "summary": "This work focuses on using differential privacy for SVM. The methods in the binary case are not applicable. Also, the existing methods for multi-class classification require multiple binary SVMs with repeated data accesses for repeated consumption of the privacy budget. To address so, this work utilizes the all-in-one SVMs, which allows a single access to each data.", "questions": "1. You used CS-SVM for the all-in-one SVM in this work. Can you also explain more why you use it and compare it with WW-SVM and M3-SVM by a table? It is ok to include such information in your appendix.\n2. For gradient perturbation, is it possible to use techniques in the DP-SGD approaches to enhance PMSVM?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. All-in-one SVMs utilized in this work avoid redundant data accesses compared to existing one-vs-rest and one-vs-one approaches for multi-class DP-SVM, which reduce the redundant consumption for privacy budget.\n2. This work provides DP guarantees for weight perturbation by using leave-one-out bound and extends to multi-class case with low cost.\n3. With moments accountant, this work lowers the privacy cost of the composition in gradient perturbation. Also Theorem 3 guarantees the post-processing property.\n\nWeakness:\n\n1. The SVM used as a multi-class classifier in the LLM era is relatively out-dated, hence the importance of DP-SVM is probably not significant, although this work advances the traditional ML with privacy-enhance techniques.", "was_revised": true, "final_justification": "Although SVM is outdated for the LLM era, this paper is a valuable contribution to the field of SVM with DP. Hence, it is probably worths for some real-world downstream tasks, which may not have the deployment ability of LLMs. To conclude, I agree to accept it.", "rebuttal": "First of all, we thank the reviewer for acknowledging the novelty of our paper. We now answer the question individually.\n\n**W1 Traditional ML in LLM Era**\n\nWe fully agree with the reviewer’s concern about the importance of traditional ML in the LLM era. As researchers in ML and privacy, we believe the study of traditional ML techniques remains crucial, even if they may be undervalued today. Traditional methods such as SVM, regression, and clustering can still offer practical advantages. With small datasets, deep learning performance is not guaranteed. Moreover, privacy is especially important with small and limited data, since DP addresses the effect of changing a single sample.\n\nIn this perspective, we can design a hybrid approach in the LLM era. As LLM‑based agents and multi‑modal models advance, designing automated pipelines for privacy‑preserving learning becomes feasible. For example, an LLM agent could select training strategies for private data: using DP deep learning with large models when data is sufficient, or choosing smaller ML models when data is limited or when training time or model complexity is constrained.\n\nWe believe this line of research on lightweight machine learning models remains valuable in the LLM era. We authors are actively considering future direction and welcome any suggestions from the reviewer regarding this paper or potential follow‑up work.\n\n**Q1. Selection of base models in all-in-one SVMs**\nWe agree with the reviewer’s question about using other all‑in‑one methods. As explained on line 102, different methods handle the maximum margin differently and, consequently, use different slack variables.\n\nWe clarify that we use CS‑SVM for weight perturbation (subsection 3.2) and M3‑SVM for gradient perturbation (subsection 3.3) in our DP all‑in‑one SVMs. Because Equation 8 provides a unified view of all‑in‑one SVMs, Theorem 1 can also be applied to other variants, as the reviewer suggested. However, computing the largest eigenvalue of the Gram matrix $\\lambda_{max}$ is difficult for those models; CS‑SVM allows easier calculation due to its orthogonal‑basis properties. Note that CS-SVM is the only method officially supported by the sklearn SVM package, thus having the ease of implementation for paper readers.\n\nFor gradient perturbation, all other all‑in‑one SVMs can likewise be formulated with Huber‑style losses, similar to Equation 12. We choose M3‑SVM because it performs well with gradient descent, as shown in [1].\n\nWe recognize that readers may wish to understand our choice of base models, and we will add a more detailed explanation in the Appendix.\n\n[1] Multi-Class Support Vector Machine with Maximizing Minimum Margin, AAAI 2024.\n\n**Q2. Advanced techniques in DP-SGD**\n\nIt is true that since the development of DP-SGD in 2016, clipping‑based gradient updates in DP‑SGD is that these approaches are extensively studied, allowing us to leverage recent analytical techniques for gradient‑based optimization. As noted on line 228, we use Opacus, a modern library developed by Meta Open Source. Opacus is actively updated with new DP‑SGD algorithms, including optimizers and sampling strategies. \n\nFor the adaptive gradient perturbation in Equation 16, we employ the DP‑Adam [1] optimizer, which is officially supported by the Opacus library. Thus, adopting advanced techniques is also feasible within our framework. When we consider the private gradient of Theorem 2 as $\\hat {\\mathbf g}_ t$, the adaptive update formulation is as follows:\n\n$$\\hat{\\mathbf m} _ t = \\beta_1 \\hat{\\mathbf m} _ {t-1} + (1-\\beta_1)\\hat{\\mathbf g} _ t,\\ \\hat{\\mathbf v} _ t = \\beta_2 \\hat{\\mathbf v} _ {t-1} + (1-\\beta_2)(\\hat{\\mathbf g} _ t \\odot \\hat{\\mathbf g} _ t)$$\n\n$$\\hat{\\mathbf m} _ t = \\frac{\\hat{\\mathbf m} _ t}{1-\\beta_1^t},\\ \\hat{\\mathbf v} _ t = \\frac{\\hat{\\mathbf v} _ t}{1-\\beta_2^t},\\ \\hat  {\\mathbf w} _ t = \\hat {\\mathbf w} _ {t-1} - \\eta\\frac{\\hat{\\mathbf m} _ t}{\\sqrt{\\hat{\\mathbf v} _ t} + \\gamma}.$$\n\nFurthermore, for sub-sampling methods, we first clarify that we used a batch size of 128 rather than full batch gradient descent. We apologize for this confusion and will clarify the use of subsampling methods in the paper. \nWe utilized a batch size of 128 rather than using a full batch for gradient descent. By utilizing Opacus, we also include recent Poisson subsampling for mini-batch update. The paper [2] suggested by the reviewer [hEqw] provides mathematical guarantees for the composition method (which performs better than basic composition in Remark 1 or moment accounting in Lemma 2) for subsampling approaches. Compared to using full batch gradient descent, a moderate batch size, such as 64 or 128, shows better performance ($\\\\approx$ means the mean batch size of Poisson sampling).  \n\n| Dataset | ε | bs$\\\\approx$32 | bs$\\\\approx$64 | bs$\\\\approx$128 | bs=full |\n| --- | --- | --- | --- | --- | --- |\n| Cornell | 1 | 0.478±0.112 | 0.681±0.000 | **0.693±0.032** | 0.480±0.066 |\n|  | 2 | 0.564±0.021 | 0.687±0.000 | **0.707±0.023** | 0.590±0.024 |\n|  | 4 | 0.641±0.058 | 0.737±0.015 | **0.752±0.023** | 0.645±0.034 |\n|  | 8 | 0.667±0.019 | 0.761±0.004 | **0.765±0.024** | 0.671±0.007 |\n| Dermatology | 1 | 0.297±0.059 | 0.883±0.077 | **0.905±0.017** | 0.243±0.143 |\n|  | 2 | 0.369±0.068 | 0.937±0.034 | **0.951±0.042** | 0.320±0.021 |\n|  | 4 | 0.599±0.056 | 0.919±0.023 | **0.978±0.012** | 0.541±0.166 |\n|  | 8 | 0.712±0.067 | 0.964±0.028 | **0.976±0.018** | 0.635±0.059 |\n| HHAR | 1 | 0.878±0.009 | **0.934±0.003** | 0.929±0.007 | 0.884±0.005 |\n|  | 2 | 0.908±0.002 | 0.941±0.004 | **0.946±0.004** | 0.913±0.008 |\n|  | 4 | 0.928±0.001 | 0.954±0.004 | **0.956±0.006** | 0.932±0.005 |\n|  | 8 | 0.940±0.000 | 0.950±0.002 | **0.959±0.003** | 0.943±0.003 |\n| ISOLET | 1 | 0.059±0.010 | 0.465±0.042 | **0.501±0.025** | 0.037±0.014 |\n|  | 2 | 0.054±0.022 | 0.614±0.013 | **0.687±0.017** | 0.037±0.005 |\n|  | 4 | 0.124±0.034 | 0.769±0.039 | **0.804±0.010** | 0.105±0.030 |\n|  | 8 | 0.120±0.013 | 0.834±0.018 | **0.840±0.013** | 0.144±0.045 |\n| USPS | 1 | 0.813±0.002 | **0.918±0.002** | 0.897±0.006 | 0.829±0.008 |\n|  | 2 | 0.855±0.011 | **0.922±0.001** | 0.907±0.006 | 0.854±0.009 |\n|  | 4 | 0.876±0.004 | **0.920±0.003** | 0.917±0.002 | 0.874±0.005 |\n|  | 8 | 0.891±0.002 | **0.931±0.003** | 0.924±0.003 | 0.887±0.010 |\n| Vehicle | 1 | 0.363±0.163 | 0.688±0.024 | **0.696±0.060** | 0.424±0.064 |\n|  | 2 | 0.410±0.094 | 0.684±0.024 | **0.753±0.007** | 0.480±0.075 |\n|  | 4 | 0.524±0.080 | 0.718±0.018 | **0.733±0.023** | 0.571±0.031 |\n|  | 8 | 0.651±0.056 | 0.731±0.007 | **0.766±0.009** | 0.639±0.040 |\n\nWe will include this result in the paper and clarify the use of the subsampling method. \n\n[1] Large Language Models Can Be Strong Differentially Private Learners, ICLR 2022\n\n[2] Composition of Differential Privacy & Privacy Amplification by Subsampling, Arxiv (2022)\n\n\n**[General]** Additionally, we kindly request the reviewer to take a look at any interesting topics during the rebuttal period. In summary, we received positive feedback on: (i) reducing redundant privacy budget consumption for multi-class SVM in DP scenarios [Fj1B, orwF, hEqw, EHLs], (ii) empirical strengths [N89T, Fj1B, hEqw, EHLs], and (iii) a well-written and well-executed paper [Fj1B, hEqw].\n\nFor each rebuttal concerning “weakness” and “question”, we addressed the following topics:\n\n- [**N89T**] Our novelty and the importance of single data access in DP, and details of theorems\n- [**Fj1B**] Clarity of Lemma 1, convexity analysis of Eq. (12), and selection of hyperparameter $R$\n- [**orwF**] DPSVM in LLM era, selection of all-in-one base model, and advanced techniques in DP-SGD\n- [**hEqw**] Sub-sampling in gradient descent, low performance, and limitations\n- [**EHLs**] Inefficiency, additional comparison methods/related works, membership inference attack, and realistic impacts\n\nIf the reviewer has any questions about these topics, please refer to our rebuttals for the corresponding reviewers."}, {"review_id": "a0NpkCSoXh", "reviewer": "Reviewer_hEqw", "summary": "Past work has considered differentially private versions of support vector machines, focusing on binary classification. This paper focuses on multi-class classification, arguing that methods based on reduction to many binary classifiers do not give a good privacy-utility trade-off as the number of classes grows. Instead, an \"all in one\" formulation that treats SVM multiclass classification as a single optimization problem, is used as a starting point. Empirical studies on standard benchmarks show that this approach most often outperform previous methods.", "questions": "- Did you consider privacy amplification by subsampling as a way of speeding up the algorithm?\n- The classification accuracy is modest for most of the problems studied, even for rather large epsilon. Did you consider approximate DP and/or larger datasets for which it is easier to achieve high accuracy?", "limitations": "The limitations discussed in the conclusion do not appear very thorough. For example, since the method is based on private gradient descent I would expect it to be slow for large datasets, which would be another limitation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "The paper is well-written and well carried out. The empirical results show that the proposed method is interesting in practice.\n\nThe main weakness is that the contribution is mainly empirical. The theoretical contribution essentially consists of putting together a known optimization problem and known techniques for private ERM. It would have been nice if techniques more modern than [3] had been used, for example amplification by subsampling which is key in analyzing private SGD (see e.g. https://arxiv.org/abs/2210.00597)", "was_revised": true, "final_justification": "The authors provided a solid rebuttal including new results that improve the empirical part of the paper. My assessment remains positive.", "rebuttal": "First, we thank the reviewer for raising various theoretical questions and suggesting ways to improve experimental performance. We now answer the question individually.\n\n**W1, Q1 Sub-sampling techniques**\nWe completely agree with the reviewer regarding the use of sub-sampling techniques. The paper suggested by the reviewer [1] provides mathematical guarantees for the composition method (which performs better than basic composition in Remark 1 or moment accounting in Lemma 2) for subsampling approaches. While this is not directly connected to the theoretical analysis in our paper, such as convergence (Theorem 3), we still utilize subsampling methods for improved composition.\n\nFor the experiments, we first clarify that we used a batch size of 128 rather than full batch gradient descent. We apologize for this confusion and will clarify the use of subsampling methods in the paper. As the reviewer suggested, better subsampling methods can achieve improved performance. Fortunately, as noted on line 228, we use Opacus, a modern library developed by Meta Open Source. Opacus is actively updated with new DP-SGD algorithms, including optimizers and Poisson sampling strategies.\n\nThe results using different batch sizes are shown in the table below. We can observe that Poisson sub-sampling techniques, as described in [1], demonstrate better performance than full batch gradient descent. However, when the batch size is too small, the noise effect becomes stronger, thus the performance decreases. This analysis aligned with deep learning with DP-SGD, which uses a comparably large batch size for calculating noisy gradients. With Poisson sampling, the batch size is not always guaranteed, but it indicates the approximate average. \n\n| Dataset | ε | bs$\\\\approx$32 | bs$\\approx$64 | bs$\\approx$128 | bs=full |\n| --- | --- | --- | --- | --- | --- |\n| Cornell | 1 | 0.478±0.112 | 0.681±0.000 | **0.693±0.032** | 0.480±0.066 |\n|  | 2 | 0.564±0.021 | 0.687±0.000 | **0.707±0.023** | 0.590±0.024 |\n|  | 4 | 0.641±0.058 | 0.737±0.015 | **0.752±0.023** | 0.645±0.034 |\n|  | 8 | 0.667±0.019 | 0.761±0.004 | **0.765±0.024** | 0.671±0.007 |\n| Dermatology | 1 | 0.297±0.059 | 0.883±0.077 | **0.905±0.017** | 0.243±0.143 |\n|  | 2 | 0.369±0.068 | 0.937±0.034 | **0.951±0.042** | 0.320±0.021 |\n|  | 4 | 0.599±0.056 | 0.919±0.023 | **0.978±0.012** | 0.541±0.166 |\n|  | 8 | 0.712±0.067 | 0.964±0.028 | **0.976±0.018** | 0.635±0.059 |\n| HHAR | 1 | 0.878±0.009 | **0.934±0.003** | 0.929±0.007 | 0.884±0.005 |\n|  | 2 | 0.908±0.002 | 0.941±0.004 | **0.946±0.004** | 0.913±0.008 |\n|  | 4 | 0.928±0.001 | 0.954±0.004 | **0.956±0.006** | 0.932±0.005 |\n|  | 8 | 0.940±0.000 | 0.950±0.002 | **0.959±0.003** | 0.943±0.003 |\n| ISOLET | 1 | 0.059±0.010 | 0.465±0.042 | **0.501±0.025** | 0.037±0.014 |\n|  | 2 | 0.054±0.022 | 0.614±0.013 | **0.687±0.017** | 0.037±0.005 |\n|  | 4 | 0.124±0.034 | 0.769±0.039 | **0.804±0.010** | 0.105±0.030 |\n|  | 8 | 0.120±0.013 | 0.834±0.018 | **0.840±0.013** | 0.144±0.045 |\n| USPS | 1 | 0.813±0.002 | **0.918±0.002** | 0.897±0.006 | 0.829±0.008 |\n|  | 2 | 0.855±0.011 | **0.922±0.001** | 0.907±0.006 | 0.854±0.009 |\n|  | 4 | 0.876±0.004 | **0.920±0.003** | 0.917±0.002 | 0.874±0.005 |\n|  | 8 | 0.891±0.002 | **0.931±0.003** | 0.924±0.003 | 0.887±0.010 |\n| Vehicle | 1 | 0.363±0.163 | 0.688±0.024 | **0.696±0.060** | 0.424±0.064 |\n|  | 2 | 0.410±0.094 | 0.684±0.024 | **0.753±0.007** | 0.480±0.075 |\n|  | 4 | 0.524±0.080 | 0.718±0.018 | **0.733±0.023** | 0.571±0.031 |\n|  | 8 | 0.651±0.056 | 0.731±0.007 | **0.766±0.009** | 0.639±0.040 |\n\n**Better Optimizer.** Since the development of DP-SGD in 2016, clipping-based gradient updates have been extensively studied, allowing us to leverage recent analytical techniques for gradient-based optimization. For the adaptive gradient perturbation in Equation 16, we employ the DP-Adam [2] optimizer, which is officially supported by the Opacus library. When we consider the private gradient of Theorem 2 as $\\hat {\\mathbf g}_ t$, the adaptive update formulation is as follows:\n\n$$\\hat{\\mathbf m} _ t = \\beta_1 \\hat{\\mathbf m} _ {t-1} + (1-\\beta_1)\\hat{\\mathbf g} _ t,\\ \\hat{\\mathbf v} _ t = \\beta_2 \\hat{\\mathbf v} _ {t-1} + (1-\\beta_2)(\\hat{\\mathbf g} _ t \\odot \\hat{\\mathbf g} _ t)$$\n\n$$\\hat{\\mathbf m} _ t = \\frac{\\hat{\\mathbf m} _ t}{1-\\beta_1^t},\\ \\hat{\\mathbf v} _ t = \\frac{\\hat{\\mathbf v} _ t}{1-\\beta_2^t},\\ \\hat  {\\mathbf w} _ t = \\hat {\\mathbf w} _ {t-1} - \\eta\\frac{\\hat{\\mathbf m} _ t}{\\sqrt{\\hat{\\mathbf v} _ t} + \\gamma}.$$\n\nTherefore, adopting advanced techniques is also feasible within our framework. We will include the details of the above analysis in the paper.\n\n[1] Composition of Differential Privacy & Privacy Amplification by Subsampling, Arxiv (2022)\n\n[2] Large Language Models Can Be Strong Differentially Private Learners, ICLR 2022\n\n\n**Q2. Low performance** \n\nWe agree that overall performance remains low, despite our method outperforming previous DP-SVM methods. Although larger datasets might yield better performance, as the reviewer noted, our primary objective in choosing machine learning approaches is to address scenarios with limited data samples where deep learning models underperform. \n\nInstead, we show the difficulty of ensuring DP in small datasets, even for deep learning with DP. The linear model in Table 2 uses the same single nn.Linear architecture as ours, so we cannot demonstrate differences in \"deep\" properties. Therefore, we added experiments with \"Residual,\" which employs a significantly deeper architecture with 9 linear transformation layers consisting of an input layer, four residual blocks (2 linear layers each), and an output head.\nThe experimental results below indicate that DP deep learning methods also show poor performance on small datasets, and in some cases perform worse than simple Linear networks. Following [1], it is true for the small data case that deeper networks may not always be effective for DP methods. While we agree that better feature extractors [1] or alternative architectural designs [2] could be used for DP, we leave this as a future direction since our focus is on DPSVM.\n\n\n| Dataset | ε | Linear | **Residual (NEW)** | Ours |\n| --- | --- | --- | --- | --- |\n| Cornell | 1 | 0.624 | 0.685 | **0.693** |\n|  | 2 | 0.695 | 0.685 | **0.707** |\n|  | 4 | 0.747 | 0.699 | **0.752** |\n|  | 8 | **0.792** | 0.763 | 0.765 |\n| Dermatology | 1 | **0.911** | 0.752 | 0.905 |\n|  | 2 | 0.930 | 0.815 | **0.951** |\n|  | 4 | 0.970 | 0.901 | **0.978** |\n|  | 8 | 0.973 | 0.941 | **0.976** |\n| HHAR | 1 | 0.887 | **0.930** | 0.929 |\n|  | 2 | 0.920 | 0.940 | **0.946** |\n|  | 4 | 0.936 | 0.950 | **0.956** |\n|  | 8 | 0.949 | **0.960** | 0.959 |\n| ISOLET | 1 | 0.466 | 0.340 | **0.501** |\n|  | 2 | 0.672 | 0.571 | **0.687** |\n|  | 4 | **0.820** | 0.737 | 0.804 |\n|  | 8 | **0.858** | 0.827 | 0.840 |\n| USPS | 1 | 0.875 | 0.877 | **0.897** |\n|  | 2 | 0.904 | 0.899 | **0.907** |\n|  | 4 | 0.922 | **0.925** | 0.917 |\n|  | 8 | 0.928 | **0.933** | 0.924 |\n| Vehicle | 1 | 0.661 | 0.418 | **0.696** |\n|  | 2 | 0.722 | 0.523 | **0.753** |\n|  | 4 | 0.711 | 0.588 | **0.733** |\n|  | 8 | 0.729 | 0.688 | **0.766** |\n\n[1] Differentially Private Learning Needs Better Features (or Much More Data), ICLR 2021\n\n[2] DPNAS: Neural Architecture Search for Deep Learning with Differential Privacy, AAAI 2022\n\n**L1. Limitation.**\n\n**Computation of the gradient method.** For the computational time of gradient methods, we show the results in Table 4. For gradient methods, GRPUA performs c separate binary classifications and therefore takes several times longer than ours-GP, which updates all parameters simultaneously.\n\n**Additional limitations.** We will add the limitation in detail. For example, our framework is limited to linear feature spaces without kernel tricks, which fail to capture non-linear decision boundaries. Additionally, the scalability to large-scale datasets with thousands of classes and comprehensive evaluation against modern DP deep learning methods remains unexplored.\n\n**[General]** Additionally, we kindly request the reviewer to take a look at any interesting topics during the rebuttal period. In summary, we received positive feedback on: (i) reducing redundant privacy budget consumption for multi-class SVM in DP scenarios [Fj1B, orwF, hEqw, EHLs], (ii) empirical strengths [N89T, Fj1B, hEqw, EHLs], and (iii) well-written and well-executed paper [Fj1B, hEqw].\n\nFor each rebuttal concerning “weakness” and “question”, we addressed the following topics:\n\n- [**N89T**] Our novelty and the importance of single data access in DP, and details of theorems\n- [**Fj1B**] Clarity of Lemma 1, convexity analysis of Eq. (12), and selection of hyperparameter $R$\n- [**orwF**] DPSVM in LLM era, selection of all-in-one base model, and advanced techniques in DP-SGD\n- [**hEqw**] Sub-sampling in gradient descent, low performance, and limitations\n- [**EHLs**] Inefficiency, additional comparison methods/related works, membership inference attack, and realistic impacts\n\nIf the reviewer has any questions about these topics, please refer to our rebuttals for the corresponding reviewers."}, {"review_id": "aYVPVTpkJ2", "reviewer": "Reviewer_EHLs", "summary": "This paper presents a differentially private multi-class Support Vector Machine (PMSVM) designed to enhance data privacy in machine learning. It addresses the inefficiency of traditional multi-class SVM approaches (one-versus-rest and one-versus-one), which repeatedly access data, by proposing all-in-one SVM methods. These methods reduce privacy budget consumption by requiring only a single access to each data sample when constructing multi-class SVM boundaries. The paper details two primary methods for achieving privacy: Weight Perturbation (WP) and Gradient Perturbation (GP), providing rigorous analysis for both. Empirical results presented demonstrate that this PMSVM approach outperforms existing differentially private SVM methods in multi-class classification scenarios in most cases.", "questions": "1. See weaknesses\n2. The differential privacy of the proposed work is only established theoretically. Is it possible to empirically evaluate the differential privacy of the proposed methods compared to the all-in-one SVMs [12-15], perhaps with a membership inference attack?\n3. SVM models are already very lightweight and thus fast compared to deep learning models. What is the realistic impact of the proposed method to be more efficient, particularly for the Gradient Perturbation-based approach? In particular, what type of scenario or application would benefit from the proposed method, since the total time difference seems small?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well written and presents clear arguments\n- The work presents a theoretical analysis of the proposed method to demonstrate differential privacy and illustrate time complexity\n- The proposed method seems to outperform the baselines in most cases\n\nWeaknesses\n- The paper is motivated by the inefficiency of applying differential privacy to SVM. However, the work skips some baselines, and is not more efficient than OPERA, for the runtime measurements (Table 4)\n- The work has a limited scope of baseline comparison and deliberately excludes certain types of differentially private Support Vector Machine (DP-SVM) models from its comparisons.\n- The work neglects to discuss some related works:\n  - Privacy-preserving multi-class support vector machine model on medical diagnosis\n  - A novel weighted support vector machines multiclass classifier based on differential evolution for intrusion detection systems", "was_revised": true, "final_justification": "My points have been taken and my rating has been adjusted accordingly.", "rebuttal": "First, we thank the reviewer for suggesting we find more related work and explore realistic scenarios. We now answer each question individually.\n\n**W1 Inefficiency of proposed method (and runtime measurements)**\n\nFirst, we make it clear that we do not use the term “efficiency” to explain our strength, which might confuse the reader about our strength in computational time. We will also revise the “efficiency” in line 114, even though it is not directly connected to this idea. \n\n**Inefficiency.** We agree that the reader might be confused about how the all-in-one SVM enhances the existing OvR approaches when applying differential privacy to SVM. However, our goal is to reduce the number of data accesses to individual data samples; thus, “all-in-one SVMs utilized in this work avoid redundant data accesses compared to existing one-vs-rest and one-vs-one approaches for multi-class DP-SVM, which reduce the redundant consumption for privacy budget,” noted by reviewer [**orwF**]. Although we know that the reviewer is already familiar with the dilemma of data access and privacy, we will explain it again for a clear understanding of the paper.\n\nThe composition theorem, one of differential privacy's most fundamental properties, is presented in Remark 1 (line 65) for two mechanisms. When we consider the general composition for $(\\epsilon,\\delta)$‑d.p. algorithms for multiple $k\\ge2$ mechanisms [1], we can similarly formulate the composition as follows (shorted version):\n\n---\n\nLet $\\mathcal{M_1}\\colon D\\to\\mathcal{C_1}$ be $(\\epsilon,\\delta)$‑d.p., and for each $k\\ge2$ let\n$\\mathcal{M_k}\\colon (D, s_{k-1},\\dots,s_{1}) \\to\\mathcal{C_k}$\nbe $(\\epsilon,\\delta)$‑d.p. for all given $(s_{k-1},\\dots,s_{1})\\in\\bigotimes_{j=1}^{k-1}\\mathcal{C_j}$.\nThen for any neighboring datasets $D,D'$ and any $S\\subseteq\\bigotimes_{j=1}^{k-1}\\mathcal{C_j}$,\n$$\\Pr\\bigl((\\mathcal{M_1},\\dots,\\mathcal{M_k})\\in S\\bigr)\\le e^{k\\epsilon}\\Pr'\\bigl((\\mathcal{M_1},\\dots,\\mathcal{M_k})\\in S\\bigr)+k\\delta$$\n\n---\n\nSimply, the composition theorem indicates that the number of accesses to data $D$ directly affects the noise level if each mechanism has a dependency on training data. When applying this principle to the OvR case, the composition of c classifiers requires c$\\epsilon$ privacy budget when each binary classifier requires $\\epsilon$. Therefore, to maintain the same total privacy budget (e.g., $\\epsilon$=8), we can only allocate $\\epsilon=\\frac{8}{c}$ to each binary classifier, amplifying the amount of noise on each classifier. Note that DPSGD has similar constraints on training steps despite utilizing modern composition theorems such as batch sampling.\n\nIn contrast, our method PMSVM requires only one data access to build a multi-class classifier, allowing us to utilize the full privacy budget $\\epsilon$. This is why we propose a multi-class DP SVM based on the all-in-one method.\n\n[1] The algorithmic foundations of differential privacy, Foundations and trends in theoretical computer science (2014)\n\n**Computational time.** To address the reviewer’s concern about runtime, we restate that we design two approaches, i.e., weight perturbation and gradient perturbation.\n\nRegarding runtime between OPERA and PMSVM‑WP, we use scikit‑learn’s “LinearSVC,” which implements the OvR method for multi‑class classification for OPERA. In contrast, PMSVM‑WP uses the “crammer_singer” option.\n\nThus, the difference relies only on the implementation of two methods in sklearn because the proposed weight perturbation requires only an additional single noise‑addition step: $O(1)$ per parameter, i.e., $O(\\text{num of params})$ overall. \n\nTo explain the computational part, we can think that the Crammer–Singer formulation solves a single joint QP with $nc$ variables, whereas OvR decomposes into $c$ independent binary SVMs, each with $n$ variables. Given that standard QP solvers scale as $O(\\text{num of params}^3)$, Crammer–Singer entails $O(n^3c^3)$, while OvR requires $O(cn^3)$. In practice (e.g., in scikit‑learn using LIBLINEAR), the observed gap is about $O(c)$ times practically. This explains the runtime gap between OPERA and PMSVM‑WP. We will add this discussion to the main paper and the appendix on weight‑perturbation computation. \n\nOn the other hand, for gradient perturbation, because the model is updated in a single pass rather than via sequential OvR training, PMSVM‑GP is superior to GRPUA in both performance and computational efficiency.\n\n**W2 Limited Scope and Comparison Method**\n\nWe agree that the readers can think that our paper may have a limited scope of comparison methods. Nonetheless, the methods included represent the principal prior DP techniques for SVM. In summary, we introduce various DP-SVM papers as summarized in the table below.\n\n| Algorithm | Privacy | Noise Injection | Model Publish | Multi Class |\n| --- | --- | --- | --- | --- |\n| **PrivateSVM (Rubinstein et al., 2012)** | $(\\epsilon, 0)$ | Weight | O | X |\n| DPKL‑PINP (Jain et al., 2013) | $(\\epsilon, \\delta)$ | Output | X | X |\n| **OPERA (Ding et al., 2022)** | $(\\epsilon, \\delta)$ | Weight | O | X |\n| **GRPUA (Ding et al., 2022)** | $(\\epsilon, \\delta)$ | Gradient | O | X |\n| Ours | $(\\epsilon, \\delta)$ | Weight (WP) / Gradient (GP) | O | O |\n\nThe only related work we omitted from the comparison is DPKL (Jain et al., 2013), which requires interaction with end users and therefore cannot publicly release the trained SVM’s hyperparameters. Among the previous works, existing binary DP-SVMs cannot be directly extended to multi-class settings because OvO/OvR training reuses the dataset multiple times. Hence, despite the small pool, we believe our comparisons can show our own strength.\n\nWe address additional related work in response to W3 below.\n\n**W3. More Related works**\n\nAt the time of the submission, we initially excluded domain-specific approaches (e.g., medical or IoT) mentioned by the reviewer because we think our focus is on general DP algorithms. In rebuttal, we agreed with the reviewer's comment about investigating the domain-specific paper. We first took a look at the papers the reviewer suggested.\n\n[1] Privacy-preserving multi-class support vector machine model on medical diagnosis, IEEE Journal of Biomedical and Health Informatics (2022). \n\n- This paper proposes a cryptographic scheme for privacy-preserving multi-class SVM; this is orthogonal to DP but worth noting.\n\n[2] A novel weighted support vector machines multiclass classifier based on differential evolution for intrusion detection systems, Information Sciences (2017)\n\n- This paper employs differential evolution rather than differential privacy and is thus out of scope.\n\nFollowing the reviewers' suggestion, we found some more papers that can be relevant in terms of SVM in DP versions, or their application in specific domains.\n\n[3] Z. Sun, J. Yang, X. Li, Differentially Private Singular Value Decomposition for Training Support Vector Machines, Computational Intelligence and Neuroscience (2022)\n\n- This paper investigates data-wise perturbation (called local DP) for SVM with singular value decomposition.\n\n[4] Differentially private image classification using support vector machine and differential privacy, Machine Learning and Knowledge Extraction (2019)\n\n[5] Privacy-preserving RBF kernel support vector machine, BioMed research international (2014)\n\n- These methods adopt PrivateSVM in their specific domain, such as medical settings.\n\n[6] Differentially Private Kernel Support Vector Machines Based on the Exponential and Laplace Hybrid Mechanism., Security and Communication Networks (2021)\n\n[7] A differential privacy support vector machine classifier based on dual variable perturbation, IEEE Access 7 (2019) \n\n- We additionally find more methods for DP-SVMs, but perturbing only either dual variables or support vectors cannot guarantee the DP of outputs.\n\nWe will incorporate these works as related works.\n\n**Q3. Realistic impact of the proposed method in terms of efficiency or application**\n\nAs discussed in **W1**, our primary contribution is improved generalization of DP‑SVMs in multi‑class settings, rather than computational efficiency. Because SVMs are compact, they remain useful compared with deep learning, as the reviewer noted. In practice, multi‑class classification is more common than binary classification. Prior DP‑SVM work largely targets binary setups, which limits practical impact. In contrast, our method provides a DP model that is (i) a lightweight, fast SVM relative to deep learning models and (ii) naturally suited to multi‑class scenarios.\n\nIn terms of applications, our approach aligns with the above domain-specific papers, including medical data and resource‑constrained devices such as IoT.\n\n**[General]** Additionally, we kindly request the reviewer to take a look at any interesting topics during the rebuttal period. In summary, we received positive feedback on: (i) reducing redundant privacy budget consumption for multi-class SVM in DP scenarios [Fj1B, orwF, hEqw, EHLs], (ii) empirical strengths [N89T, Fj1B, hEqw, EHLs], and (iii) well-written and well-executed paper [Fj1B, hEqw].\n\nFor each rebuttal concerning “weakness” and “question”, we addressed the following topics:\n\n- [**N89T**] Our novelty and the importance of single data access in DP, and details of theorems\n- [**Fj1B**] Clarity of Lemma 1, convexity analysis of Eq. (12), and selection of hyperparameter $R$\n- [**orwF**] DPSVM in LLM era, selection of all-in-one base model, and advanced techniques in DP-SGD\n- [**hEqw**] Sub-sampling in gradient descent, low performance, and limitations\n- [**EHLs**] Inefficiency, additional comparison methods/related works, membership inference attack, and realistic impacts\n\nIf the reviewer has any questions about these topics, please refer to our rebuttals for the corresponding reviewers.\n\n**We will continue the remaining response of **Q2. Empirical evaluation of membership inference attack** in the comments below.**"}]

Author rebuttal:

Meta-review: While past work on private SVMs has focused on binary classification, this paper tackles multiclass classification. It argues that methods based on reducing the problem to many binary classifiers do not give a good privacy-utility trade-off as the number of classes grows. Instead, the authors privatize an "all-in-one" multiclass SVM formulation that requires only a single access to each data sample, thereby reducing the privacy composition cost. The paper addresses a classic problem, and its empirical studies show that this approach often outperforms previous methods. All reviewers support the paper.
Decision: Accept (poster)