Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
Authors: Erchi Wang
Yuqing Zhu
Yu-Xiang Wang
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Learning half-spaces
margin theory
private optimization
Primary area: social_aspects->privacy

Abstract: This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification. 
  We obtain an efficient $(\varepsilon,\delta)$-DP algorithm with an empirical zero-one risk bound of $\tilde{O}\left(\frac{1}{\gamma^2\varepsilon n} + \frac{|S_{\mathrm{out}}|}{\gamma n}\right)$ where $n$ is the number of data points, $S_{\mathrm{out}}$ is an arbitrary subset of data one can remove and $\gamma$ is the margin of linear separation of the remaining data points (after $S_{\mathrm{out}}$ is removed). Here, $\tilde{O}(\cdot)$ hides only logarithmic terms. In the agnostic case, we improve the existing results when the number of outliers is small. Our algorithm is highly adaptive because it does not require knowing the margin parameter $\gamma$ or outlier subset $S_{\mathrm{out}}$. We also derive a utility bound for the advanced private hyperparameter tuning algorithm.

Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
Erchi Wang'
Yuqing Zhu
Yu-Xiang Wang'
Abstract
McSherry & Talwar, 2007a; Dwork al., 2014). A single point change can cause the margin to shift drastically, from a positive value to zero or the reverse, as demonstrated in Figure 1. Despite the theoretical challenge. empirically, a larger margin is believed to be the reason why pre-trained features help private learners to work better (De al., 2022).
This paper studies the problem of differentially private empirical risk minimization (DP-ERM) for binary linear classification.. We obtain an effi- cient (e, 8DP algorithm with an empirical zero- one risk bound of Ô 1 +
[Sutl] where y
fen
the number of data points, Sout is an arbitrary subset of data one can remove and is the margin of linear separation of the remaining data points (after Sout is removed). Here, Ó(-) hides only log- arithmic terms. In the agnostic case, we improve the existing results when the number of outliers small. Our algorithm is highly adaptive because it does not require knowing the margin parameter or outlier subset Sout. We also derive utility bound for the advanced private hyperparameter tuning algorithm.
positive margin
zero margin
Figure Margin unstable after changing one point (marked by the green square), thus hard to design data-dependent DP- mechanism using standard techniques (e.g.. smoothed sensitivity (Nissim al., 2007) or tropose-tes-rclease (Dwork & Lei, 2009)).
To validate this hypothesis, we evaluated the margin of SVM classifiers trained on the CIFAR-IO dataset using pre-trained features from Vision Transformer (VTT) (Dosovitskiy et al., 2021) and ResNet-50 (He et al., 2016). Interestingly, as reported in Figure 2, while the margin remains zero for the whole dataset, if we allow removing few "trouble makers" (misclassified or other points near the decision boundary), it becomes clear that ViT-based features achieve a larger margin and increase more quickly than ResNet-50-based features as removing more outliers.
1. Introduction
We investigate differentially private empirical risk mini- mization (DP-ERM) (Chaudhuri et al., 2011; Bassily et al., 2014) under the setting of learning large-margin halfspaces. In classification problems, algorithms that create decision boundaries with larger separations between classes, a.k.a. large margins, tend have stronger generalization perfor- mance (Vapnik, 1998; Panagiotakopoulos T Tsampouka, 2011). This principle has been leveraged in many classical machine learning algorithms, such as the Perceptron (Rosen- blatt, 1958; Novikoff, 1962), AdaBoost (Freund & Schapire, 1997), and Support Vector Machine (Vapnik, 1998; Cortes & Vapnik, 1995). natural to ask whether we can design a data-vde DP algorithm to benefit from a marge-margin condition. This is challenging because differential privacy requires the algorithm's output be "close enough" when two datasets differ by one data point (Dwork et al., 2006;
After approximately 0.1% of points removed, the re- maining data become linearly separable for both ViT and ResNet-50-based features. This phenomenon also relates to neural collapse theory (Papyan et al., 2020; Wang et al., 2024), which states that the last layer of deep neural net- work trained on K-class classification task converges to K distinct points. The geometric margin (Eq. 1) does capture this phenomenon. Since the CIFAR-10 dataset is not linearly separable, the geometric margin is zero. This inspires us to ask:
Halhcoolu Data Science Institute, UC San Diego Linkeddn.. Correspondence to: Yu-Xiang Wang syuxiangw @ udus. Er- chi Wang serw0l ucsd.edu>.
Can we design an efficient differentially private algorithm for agnostic learning halfspaces while adapting to linear separable subsets with large margins?
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Table Summary of the results the population zero-one loss (with high prohability). Realizable means that the data is linearly separable with geometric margin at least ?. In the agnostic case, y the data data-independent confidence margin parameter in Row and 3. Row 4, y denotes the geometric margin of data subset after Sout is removed. For clean comparison, assume ||x]|, | w|l to be (1)), the privacy loss I 1, and omit the dependence on factors of order polylog(n, e, 1/5, 1/8); (g() (RG(-) denotes average of empirical y-hinge loss (empirical 7-ramp loss).
Source
Realizable case
Agnostic case
polynomial-ting -tme??
Nguyên et al. (2020, Thm. 6, Thm. 11)
known TV
NA
8
Bassily et al. (2022, Thm. 3.1)
1
+ min (E)
RZ((W) +
+ (
RR((w))
x
n
72
Bassily et al. (2022. Thm. 3.2)
1
min wEB
[3(w))
r 1/
n V
1
Soutl
Theorem
min CS
ny
my?E
yemmargin
technique allows to achieve v improvement in the population risk bound compared to Theorem 3.2 in (Bassily et al., 2022). Moreover, the term 1Smutl/T0 naturally adapts to the problem's complexity, allowing our results to extend to the agnostic case, where directly applying Theorem from (Nguyên al., 2020) not feasible. Finally, this analysis technique enables us extend to unbounded parameter space. This avoids the assumption the bounded domain as stated in (Nguyên et al., 2020; Bassily al., 2022).
method
Besliet55
maigin
0.020
0.038
0.010
1.2. Related Work
0.000
Prior work on DP large-margin learning. To the best of our knowledge, Nguyên al. (2020) is the first work to achieve dimension-free excess population risk for differ- entially private learning of large-margin halfspaces. Under the assumptions linear separability and known geometric margin, they are able achieve fast rate of Ô my using an efficient approximate DP algorithm. However, in practice, the linear separability of the data and the geometric margin value are often unknown without directly accessing the data. To address this, Bassily et al. (2022) uses the confidence margin (Mohri al., 2018), a data-independent quantity, and achieves an Ô 7/n + Gome) excess empiri- cal risk on surrogate loss in the agnostic case.
1.0
percentage of removed points
Figure The number of removed points (in percentage of r)) vs normalized margin. Classes 1 and from the CIFARIO training set are used. As more points are removed, the margin increases. We include more implementation details in Appendix N.
We give an affirmative answer to this question and summa- rize our contribution here.
1.1. Our Contribution
An efficient algorithm adapting to large margins We propose an efficient algorithm adapting to large margin sub- sets differential privately, without the need for any tuning parameters nor assumptions of realizability, as stated in Algo. 3.
Pure-DP algorithms are also discussed in Nguyēn al. (2020) and Bassily et al. (2022). However, they suffer from computational inefficiency due the use of exponential mechanisms on candidate sets of size O(exp(1/r)) For completeness, we include these results for both the agnos- tic and realizable cases and present a comparison with our result in Table 1.
Intier-outlier analysis of gradient descent We propose margin inlier/outlier (Definition 6.1), as a generalization of geometric margin. We obtain data adaptive upper bounds on both empirical and population risk, which depend on the number of margin outliers (Theorem 4.1). This analysis
Bun et al. (2020) and Ghazi et al. (2021) study private learning of margennargin halfspaces with an emphasis on
2

---

Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
robustness. Both two works make specific assumptions about realizability and noise oracles. Moreover, proposed algorithms require taking the geometric margin as input, i.e., Bun et al. (2020, Algo. 4) and Ghazi et al. (2021, Algo. 1).
nality. The L2 projection operator onto A is denoted as (x)ja(x) == arg mig ||v - x||. The power set of A is vEA
denoted by 24. The probability generating function of a random variable K is represented by PGF K ((). Through- out this paper, the notation O is used to suppress universal constants, while θ hides polylog(n, 1/3, 1/6) factors.
For earlier works with poly(d) dependence in population risk, we refer the readers to Section 1.2 of Nguyên et al. (2020) for a comprehensive survey.
Differential Privacy. We call two datasets X, XX E X neighboring datasets if they differ up to one element.
Private hyperparameter tuning. To achieve the desired results, the margin parameter also needs to be selected. Bass- ily et al. (2022) addresses this by privately selecting the optimal confidence margin using the generalized exponen- tial mechanism (Raskhodnikova & Smith, 2016). However, their approach relies on a score function that incorporates the minimized empirical risk over the hypothesis space, which is generally hard to compute (Bassily et al., 2022,
Definition 2.1 (Differential privacy (Dwork et al., 2006)).
A randomized algorithm M : X + Ω is (e, 6DD (dif- ferential private) for e, E 1) if for any neighbouring datasets X' E X and any measurable subset O S Ω M satisfies:
P(M(X) E S P((((X)) E
+ +6
Lemma F.3).
Definition 2.2 (Gaussian Differential Privacy (GDP) (Dong et al., 2022)). We say a mechanism M satisfies μ-GDP if for any neighbouring dataset X, X' X".
In addition to classical differentially private selection mech- anisms such as the exponential mechanism (McSherry & Talwar, 2007b), the report-noisy-mat (Dwork et al., 2014), and the sparse vector technique (Dwork et al., 2009; Zhu & Wang, 2020), there have been notable advancements in pri- vate hyperparameter tuning. This research direction began with (Liu& & Talwar, 2019) and was further refined by (Pa- pernot& & Steinke, 2022), which utilized Rényi differential privacy, and by (Koskela & Kulkarni, 2024), which incor- porated subsampling techniques. More recently, (Koskela et al., 2024) further improves the practicality by provid- ing tighter privacy accounting through the use of privacy profiles. These advanced methods allow the final privacy budget to grow logarithmically with the number of repeti- tions, as opposed to the (sub)linear growth observed with (advanced) naive composition (Dwork et al., 2014).
Her (M((MM()))) < H (N(0, 1)I 1)), As E R,
where NN 1) stands for standard normal distribution and Her (-Il-)) denotes the hockey-stick divergence between two probability distributions (Sason & Verdu, 2016).
Remark 2.3. While (e, 6)D offers a direct description of privacy leakage, it's messy and loose when composing mul- tiple mechanisms together (Near Abuah, 2021, Chapter 6). Instead, GDP not only has a clean form for composition: composing (Mi) mechanisms with each mechanism being μ -DP yields (VEi_, 14 -DP,, but offers a tight characterization for Gaussian mechanism: Gaussian mecha- nism with L2 sensitivity A and noise parameter satisfies A/o-GDP. Thus, throughout this paper, we use GDP and its composition when possible, though the final result is still stated in 5)-D).
We examine two hyperparameter tuning methods: a simple brute-force approach (Algo. 2) and an advanced private tuning method (Algo. 4). Their utility and computational efficiency are compared in Section 7.
Geometric margin. We first define the margin of dataset S with respect to a linear classifier Iow (x, y) + sign(y(w, x)) to be:
2. Preliminary
Symbols and notations. We use boldface letters (e.g., x) to denote vectors. Calligraphic letters are used as follows: F represents the function class, H denotes the classifier class, X' represents the data universe, and A denotes a ran- dom algorithm. The notation Ex[-] indicates the expecta- tion taken over the randomness of algorithms. The binary operation A denotes taking the minimum between the two inputs. Throughout this paper, (+-)) represents the in- ner product, and || denotes the induced L2 norm. The set (r) == (x E IRd ||x|| < r) is defined as the La ball in IRd with radius r. The sign function is denoted by sign(.), and the indicator function is represented by (-)). For a set A C Rd. we use A to denote its cardi-
V(W, x) [[
Margin(w; (w; S) = max min (x.))e
We say dataset S is linear separable if there exists some linear classifier w with (w; S)) > O. The geometric margin for dataset S is defined to be:
7SS) = max Margin(w;S)) wERd
As shown in Figure 2, a dataset may initially have a zero margin. However, after removing certain "outliers," " the re- maining dataset can exhibit a positive margin. We formalize this concept and introduce the definitions of margin inliers and outliers in Definition 6.1.
3

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
3. Settings
The proof builds on Theorem 6.5 and Theorem 6.7, with the details deferred to Appendix H and Appendix I.
Loss function. We use le to represent hinge loss with confidence margin parameter c:
Let's make a few observations. In the realizable case, M naturally adapts to the margin without requiring prior knowl- edge of its value, in contrast to the approach proposed by Nguyên et al. (2020, Theorem 6& 11). In the agnostic set- ting. Sout can be interpreted as outliers. When |Souel is sufficiently small x o(vr))). our results achieve a vn improvement over Bassily et al. (2022, Theorem 3.2). For detailed comparison, see Table 1.
Co(w; (x, y)) - max -/ww///
L.((;;)) (w::ww; S)) represents the averaged (summed) empirical hinge loss for estimator w over the dataset S. Remark 3.1. Throughout this paper, the confidence margin is only used as a parameter for hinge loss. It is unrelated to the data-dependent quantities we defined, such margin inliers/outliers (Definition 6.1).
The algorithm M in Theorem 4.1 does not need any tuning parameters. It is highly adaptive as it can compete with the best Sout E 2 that minimizes the bound without having to explicitly search for Sant. It also does not incur the typical statistical costs of log(2") of adaptivity to 2-, which would render the bound vacuous. In addition, M is also computationally efficient. We will see in the next section that M has a modular design, and it only requires invoking an off-the-sher the-shelf solver for the convex DP-ERM problem a few times.
In our optimization algorithm, we use hinge loss. It is impor- tant to note that varying confidence margin parameters can result in different loss values, even with the same estimator w and dataset S. To ensure a fair comparison, we express utility upper bounds using zero-one loss:
1 (w; (x, v)) = 1 (v(w,) <0}
For an estimator w, we denote its averaged empirical zero- one loss on dataset S as R2 (w) and its summed version Rs(w). Furthermore, (D) represents the population- level zero-one risk for the data distribution D.
5. Algorithtms
Assumptions. We make the following assumptions: the training dataset S = ((x1.9),, ............ (Xn; 3n)} is sam- pled ii.d. from an unknown distribution D defined on (1) x {+ We consider the function class F ((,w) w E Rd) and the hypothesis class of classifiers H H= (x > sx)n( | E F). The assumption that x and w lie in the unit ball is made without loss of generality. In Section 1, we extend our results to the more general case where x E (b) and w E Rdd
In this section, we provide details for our algorithms. The algorithm M (Algo. 3) is designed as a composition of two components: the private hyperparameter tuning algorithm Aner (Algo. 2) and the noisy gradient descent algorithm with Lonnsonn-Lnndenstrauss projection AJLGD (Algo. 1).
5.1. Base Algorithm: JL-Noisy Gradient Descent
To obtain a dimension-free rate, we apply the Johnson- Lindenstrauss (JL) projection to reduce the dimensionality while preserving the linear separability of projected data. The "adequate" projection dimension for maintaining sepa- rability is determined by the data margin. Informally:
Problem Setup. We address the problem of agnostic proper learning of halfspaces with differential privacy- Given dataset S and privacy budget e, 8, our goal is to design an algorithm that takes S, e, and 5 as input and outputs a classifier Wout from the hypothesis class H. ensur- ing a small (empirical) population zero-one risk (Rs (Wout)) RD( (Wout).
Lemma 5.1 (Informal version of Lemma B.2). Let dataset S = {xxx,,))) 1i) C Rd x {+1} satisfying 7SS) > O, choosing k = ((1/-((S)) in the JL projection ensures that the projected dataset &$ := {(xx,, y.) satisfies
7 > -
x(S) with high probubility.
4. Main Result
In Algo. 1, the data is first projected into a lower- dimensional space using a JL matrix tb E Rixdd Next, we further clip the L2 norm of data using projection to bound the sensitivity. After running noisy gradient de- scent for T iterations, we can choose to output either the last-iterate estimator Wout the averaged estimator Wout - w. (described in ANGD (Algo. 5)), These two choices correspond to utility guarantees in ex- pectation form or high probability form, as stated in the Theorem 6.5.
We state our adaptive margin bound as follows:
Theorem 4.1. There exists an efficient algorithm M (Algo. for any input dataset S. privacy budgets e, 8 satis- fying 5 E (0, 1) and E (0, llg({)/)) such that: (I) M is ()P (2) With high probability, for any Sout 2 with y : >S Sunt) O. simultaneously:
Sout
(s( < ny min(e,
A1
yn
1
|ouu]
RD( S uoy2min(e,1 1}
A1
We note that using JI. projection to preprocess data in pri-
yn
4

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
vate learning of halfspaces has been explored in previous work such Nguyên al. (2020); Bassily al. (2022). Compared to Nguyên et al. (2020, Algo. 1), we do not as- sume that the projection dimension k is calculated from the actual data margin 7(5), which we provide more details in Algo. 3. Compared to Bassily et al. (2022, Algo. 2), our projection dimension chosen to be ((1/7") instead of (nE)). In addition, we use a full-batch gradient descent algorithm rather than SCO-type methods, which avoids the 1/vni term in the convergence rate.
tions in I and identify the margin parameter that minimizes the zero-one risks. Given that the size of the margin grid is (x)]+ 1, we utilize a brute force approach that iterates through all configurations, as described in Algo. 2. To mini- mize empirical risk, we use the average empirical zero-one loss as the scoring function. We employ a penalized scoring function to minimize population risk, defined in Eq. 3.
The input to Algo. includes only the dataset S and the privacy parameters and 5. Since the margin grid I' is con- structed in a data-independent manner, no prior knowledge of the data margin is required.
Algorithm 1: AJLGO c,
Input: Dataset S = (x,, M:) with ||x| S v,
Algorithm 3: DP Adaptive Margin M
IL projection matrix o E B
Input: dataset 5 {x,, Vi -== Privacy budget e,
Hinge loss parameter c, GDP budget j
Set: Margin grid I (
2 n
1 2loora m1
11.
2 45: := ((Projx*(22))
a
GDP budget μ 2/ (og(//0)))
3 w- -NGG (fc, 45, p))
D Algo. 5
Output: + T w
failure probability for JL projection 3
Initialize hyperparameter set O = {Φ} b empty set for y ] do
ki O (++ log( (l(tt))nnt))
5.2. Construction of Main Algorithm .M"
Φ ~ (Rad())) V ) jey
Our main algorithm M (Algo. 3) contains three steps:
6
θ 0- 2T)}
Step 1. (Line 2 of Algo. 3) We begin by discretizing the range of possible margin values to create a set of margin parameters, denoted as r. This set is constructed as a log- arithmic grid over the interval [o, 1]. The analysis of the approximation error introduced by this discretization pro- vided in Theorem 6.4.
(Wout, Yout, rone) ) = Aner (Auao( S, Output: (Wout; Yout, $ yont)
For computational efficiency, Algo. 3 is constructed by running Algo. for [log(nn] + times, making it a polynomial-time algorithm because Algo. I itself runs in polynomial time. Additionally, as shown in Section 6.1, our convergence analysis (Eq. 2) is compatible with any black- optimization method, allowing the replacement of full-batch gradient descent with more efficient DP-ERM methods, such as DP-SGD, to improve computational eifi- ciency further.
Step 2. (Line 4-7 of Algo. 3) For each margin parameter y in the set I, we construct corresponding projection matri- ces pyy The projection dimension k, is set to ((17²) to ensure margin preservation, as demonstrated in Lemma 6.2. Importantly, the construction of each by is independent of the data, meaning it does not consume any additional privacy budget.
Algorithm 2: (M,
6. Proof Sketch
Input: Base mechanism Mbase. hyperparameter set O dataset S,
We provide privacy and utility analysis of our algorithms. To begin with, we define the margin inliers (Sna) and the margin outliers (Sout), which help extend the definition of the geometric margin.
GDP budget μ
2 Choose: Criterion function U with sensitivity A
3 for 0 E θ do
mg Mhasc (8; S.
The motivation for defining Sour(r) arises from the obser- vation that after removing few "outliers" denoted as Souts the remaining dataset 7(8 Sooue) becomes 7-separable. To avoid the combinatorial explosion associated with selecting Sout (7), we take "dual view." Rather than directly defin- ing the margin outliers, we first define the margin inliers, the subsets of S that are 7-separable. The margin outliers are then simply the complement of the margin inliers.
/2/0
E ~ (0, 2/0/22
5
Ugg U Umm::S) S) +
7 Oout = arg min uig Aee 8 Output: (Mo.... awn))
Step3. 3. (Line of Algo. 3) We evaluate all margin configura-
Definition 6.1 (Margin inliers/outliers. We define the mar-
5

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
gin inliers / outliers of the dataset S with respect the
The proof is included in Appendix B. Since the margin y is preserved for the largest margin inlier set in Sin can formulate the following utility lemma for Algo. 1:
margin value y E [0, 1] follows:
Sin (i) = (5' c S ((5))(2)))))))) 2}
Sour (v) =- ( 1' (n)
Lemma 6.3. Given GDP budget μe > O, failure probability
This characterization enables us to divide the dataset into two subsets and analyze the optimization error for each separately, as explained in the following section.
8 E (0, 1). and y E (0, 1), running AJLGO (Algo. 1) with & from Lemma 6.2 and hinge loss parameter //3 is p-GDP. Further, w.p. at least 1 - 23, the last-iterate estimator T w E Rd satisfies:
6.1. Inlier-outlier Analysis of Noisy Gradient Descent
δ (p3
We provide an overview of our onlier-outiier analysis proce- dure. For a fixed 7 E [o, I], we can appropriately decrease the hinge loss parameter e so that the minimum empirical c-hinge loss on Sm (7) is reduced zero:
I ( W: min
Souc ESout (7)
72
+
?n
Lemma 6.3 indicates that Algo. adapts to the smallest margin outlier set for a given margin level. We defer the proof to Appendix D.2.
T.o((: (w: 5) S (ww:;; ; FER
Utility bounds for noisy gradient methods often include a Vd term (Bassily et al., 2014). In contrast, the bound pro- vided in Lemma 6.3 is diimension-indeeendeee to existing utility bounds for private gradient descent meth- ods that leverage JL projections, such as Bassily et al. (2022, Lemma 3.1) and results from Arora et al. (2022, Appendix A.4), our Lemma 6.3 avoids a strict O(n On221/2) dependence.
s (win: (1)) + L.(win Sout (7)) + +EER
Compared
(2) zero if $7
(b)s (1)1/c
S (o((sou((7))/0) + EER
(2)
is worth noting that w can generated by any opti- mization algorithm, offering the flexibility to replace our full-batch gradient descent (Algo. 5) with alternative meth- ods.
6.2. Adapting to the Optimal Margin
Lemma 6.3 suggests that larger "y and smaller [oout lead to a tighter upper bound on the empirical risk. However, increasing the margin y simultaneously causes the size of Sout to grow. To minimize this upper bound, it is necessary to determine the optimal y E [0, 1].
As shown in Eq. 2, there is a trade-off between achieving a larger margin and removing fewer data points. As the size of (7) increases, the margin r(5') \ Suut also in- creases. However, removing more points makes the remain- ing dataset less representative of the original distribution, leading to a high error on (T) In extreme case, for any non-degenerate binary classification problem, at most 2 points can be removed to make the remaining data linearly separable, However, adapting to such a margin is not meaningful. Since Eq. 2 holds for any Sin E Sin()), (7),, we aim minimize (S (7)), ensuring that only the smallest number of "outliers" are removed.
We approach this as hyperparameter tuning task. First, we discretize the margin range to create a set of candidate hyperparameters. Then, we evaluate each hyperparameter privately and select the one that minimizes the empirical zero-one risk.
Specifically, we construct doubling grid over [0, 1]. de- fined as (1/n, 2/n, 4/n,..,, 2 2 ". /n, 1). and then apply the AAloo 2) using the empirical zero-one loss as the score function. By leveraging the monotonicity of margin outliers, the doubling grid guarantees an acceptable approximation guarantee, as demonstrated in the following lemma:
In the next two lemmas, we show that the analysis procedure of Eq. 2 remains valid for random projection based gradient descent. We begin by presenting margin preservation lemma, leveraging the data-oblivious property of Johnson- Lindenstrauss projections (Larsen & Nelson, 2017).
Lemma 6.4. Given dataset S E (B) x (=1))" and E > 0, for doubling set I = {1/n, n, 2/nz n, 4/n, "...." 21 ml /1, 1}:
Lemma 6.2 (Margin preservation after random projection). Let S {(x;, ys) 11 C (1) x {+11} and y E [0, 1]. Construct a JL projection matrix & E RRixd with entries i..dd. as 1 Rad(b) where l O (1n(((++)((++2/())) For /R any Sm E Sin()), we have?:
|outt]
1
min Ter SousES
+ 2y2E
A
nyy
Soue ny
1 ny?e
min Spece CS (S
A
Po (7(95m)) >
7 2 1 3
'EER stands for Excess Empirical Risk (Definition A.11); Win denotes the normalized max-margin separator for S., (7): w" arg win S)
We now state the empirical risk bound for Algo. 3:
Theorem 6,5 (Empirical risk bound for M*). Running
RRd(( denotes the Rademacher distrihution
M with Rs satisfies (c, 8)P,, for 8 E (0, 1) and e
6

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
(0, 8 8lo)(1/5))- In addition,
7. Advanced Hyperparameter Tuning
(1) For the averaged estimator Wout TRdd we have utility guarantee in expectation:
In practice, practitioners often tune multiple hyperparam- eters, with each of which follows an exponential grid. It- erating over all parameter configurations (as in Algo. 2) would significantly degrade the privacy guarantee. This mo- tivates us to consider an advanced private hyperparameter tuning approach ((Paperot & Steinke, 2022), outlined in Algo. 4), where the final privacy budget grows only loga- rithmically with the number of repetitions. Compared to Algo. 2, Algo. determines number of repetitions from a specific distribution Q, implemented here geometric distribution (TNB),, Appendix A.I).
|oont y:
E[Rs(Wout)] 1
min
+ n22
7
(2) For the last-iterate estimator Wout E IR, wap. at least
1 1- -3/n²:
1 | 7
) + n2
Rs( (Wott S
min Sout CS (Smn))
A1
We defer the proof details of Lemma 6.4 and Theorem 6.5 to Appendix G and Appendix H.
Algorithm 4: AprivTune (M, O Q,
Input: Base mechanism M, hyperparameter set O run time distribution Q, dataset S,
6.3. Proof for the Population Risk
In this section, we show a population risk bound for M We begin by presenting an upper bound on the population risk, derived by applying the AM-GM incquality to refine Bassily et al. (2022, Lemma A.1):
GDP budget μ
Choose: Criterion function U with sensitivity A
Sample number of runs K ~ Q
for t = 1.... K do
0, Uniform(O)
Lemma 6.6. Let S be training set containing data points sampled ii.d from the distribution D, and let the hypothesis
m, M, (22
class defined as Hy- = {xx + sign((x, w)) x E R*}, J. For any w E Hy, the following holds w.p. at least 1 - 3 over the randomness of sampling:
& ~ N(0, 223)
u U(me; 5) Et
tou arg gegginnee/ (I.....) K3 Ut
RD((w) <2Rs(ww)+ 5(VC(H&) log(2n))
log(2n)) - 13/(3/4)
10 Output: (m+.w Otom))
Thus, instead of directly using the empirical zero-one loss for selection, as in the previous section, where the goal was to minimize empirical risk, loss for selection to minimize population loss:
To incorporate Algo. 4 into our main algorithm, one can simply replace Atter with Apritune in line 8 of Algo. 3 (see Appendix K. I for the full statement). The following lemma presents the privacy and utility guarantees, with proofs de- ferred to Appendix K.4.
the penalized zero-one
5 R.(Sool) ) + 2 (VC(H)) log(2n) (3/4)
Theorem 7.1. Running Algorithm 3 with ApriTune as the hyperparameter selector, margin hyperparameter set + 10, Q TNB, _ and GDP budget ensures (E + 5,5)-DP, for any 8 E (0, and & E (6, 24 (og (1/6)). For the av- eraged estimator Wout E Rd, we achieve a utility guarantee in expectation:
The remainder of the proof for hyperparameter selection follows from a union bound over private hyperparameter selection. Finally, we provide the population risk guarantee for Algo. 3.
/ 2/2l @iih 13/a)
Theorem 6.7. Under the same conditions e, 8, I, and as in Theorem 6.5, Algo. 3, using the score defined in Eq. 6.6, satisfies (E, 0D-P. Whh.p. the output last-iterate
estimator Wout E Rd satisfies:
T3| ( S
min 7EB Sout Sout (S)
o
( [og((O)n/0) 7/.n
[Sant] 7m
+
1 n2
RDD (Woot) <
min Sugn C y:=r(3"(
④ min
(
1
Sourl ym
As observed, the final utility bound scales only logarithmi- cally with the size of the hyperparameter set θ. In contrast, for the brute force method Atter. the utility bound grows as 1// (Eqn. 17). We note that our utility bound for private hyperparameter tuning extends beyond linear classification (Lemma K.4). To further demonstrate the utility improve- ment, we examine a general hyperparameter tuning problem
When |Sout o(vT), the population risk in Theorem 6.7 is on the order of (1/ VT), improving upon Theorem 3.2 in Bassily et al. (2022), where the bound is ((1 In the realizable case, when data has margin y with probability 1, Theorem 6.7 also recovers the ((/nn) rate. We defer the proof details to Appendix I.
7

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Table Results on the population zero-one loss (with high prohability). Capital letters X, W denote data space and parameter space correspondingly. is the data-indepee data-independent confidence margin parameter in Row and 2. In Row 3, denotes the geometric margin of a data subset after Sout is removed. W.L.O.G., we assume the privacy loss e S 1. results are stated the agnostic case.
Source
Constraints
Result
C2
C²
Bassily et al. (2022, Thm. 3.1)
|x||| S b,
|w|
sC
+
72n
?2
Ri((w) +
(2((W)
C222
1
min wEBu(C)
Bassily et al. (2022, Thm. 3.2)
||x|| I b,
|| c
ō n//
yn
Cb
yn
Cb
wEB
min
L,
b²
b|Soul
Theorem L.2
| S b
min
Sonc
1o725
ny
mrmmaaginnS ( Soas)
with K hyperparameters, each associated with grid of size m, yielding m total configurations. In this setting, the utility upper bound for Atter scales as m ((K), whereas for ApriTunee reduces to O (Km).
8. Discussion
8.1. More General Case
We extend the risk guarantees to any bounded data space, i.e. ||x|| S b, showing that this generalization introduces additional dependency
7.1. Private Hyperparameter Tuning on Small Set
b, scaling proportionally to 1/y. A comparison of population risk results is presented in Table 2. We defer proofs to Appendix L. Compared with the results in (Bassily et al., 2022), our bound applies even when the parameter space is unbounded. This is because of the reference point in our inlier-outlier convergence analysis of Algo. the normalized max- max-margin separator rather than the empirical risk minimizer. (section 6.1)
In our setting, Algo. 2 and Algo. 4 yield upper bounds with the same dependence on 00). This is because the size of the hyperparameter set is only log(n) and dominated by other (nly(n) factors from random projection. In terms of runtime, Aper requires just (log(n)) repetitions, whereas APrivTue has expected runtime of (n log(n)) repe- titions. Since AprivTune employs uniform random selec- tion (line 5 in Algo. 4), it needs more repetitions to en- counter the optimal hyperparameter 0" To ensure that the probability of failing to select 6* remains below 3, i.c., (0" not selected) < 3, the expected number of repeti- tions cannot be too small.
8.2. Further Improvements and Future Directions
An open question is whether the dependence on Y in SSaut can be climinated for privately proper learning of halfspaces: Question 8.1. Given an unknown distribution D and n i..d. samples drawn from it, does there exist an efficient DP algorithm A such that with high probability, the following holds:
Lemma 7.2. Suppose Q 1. and fauilure probabil- ity is set be B. [[ = 1/r 2 9/n-90(11-11, Algo. 4 ensures P (0 not selected) < 8
δ (po
Sout
RD(A(S)) S
min Soart CS Sout)
+
poly(n,
We defer the proof to Appendix M.2. To achieve polyno- mial decay the failure probability, i.e., B On (a). the expected number of repetitions E[Q] should be larger than (10) - (n) - 1). which grows polynomially with n. One might wonder whether truncated negative binomial distri- butions with different parameters could achieve (l)g(()) repetitions while preserving the same utility guarantee of Theorem 7.1. In Appendix M.3, we further explore this topic and show that using truncated negative binomial distribution may not be feasible.
The proper agnostic learning of halfspaces in non-private settings is NP-hard (Guruswami & Raghavendra, 2009; Feld- man al., 2006; Daniely, 2016). Therefore, achieving this improvement is unlikely without making certain assump- tions about the noise model.
One might consider the Massart halfspace model (Di- akonikolas et al., 2019; Chen et al., 2020; Chandrasekaran et al., 2024; Diakonikolas & Zarifis, 2024). However, since our algorithms rely on convex HRM, directly applying our
8

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
approach does not achieve a bound of | 13 as stated by
Chen, S., Koehler, F,, Moitra, A., and Yau, M. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 8391-8403. Curran Associates, Inc., 2020.
the lower bound in Diakonikolas et al. (2019, Theorem 3.1). More recently, (Chandrasekaran et al., 2024; Diakoniko- las & Zarifis, 2024) introduce efficient algorithms that at- tain an excess population risk of 1/2 Exploring whether similar guarantees can be extended to the differ- entially private setting remains an interesting direction for future research.
Cortes, C. and Vapnik, V. Support-vector networks. Ma- chine Learning, 20:273-297, 1995.
Acknowledgments
Daniely, A. Complexity theoretic limitations on learning halfspaces. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pp. 105-117, 2016.
The work is partially supported by NSF Award #2048091. The authors would like to thank Vasilis Kontonis, Ming Yin, Lydia Zakynthinou, and Shiwei Zeng for helpful discussions and for pointing out related work. E.W. would also like to thank Yingyu Lin for helpful suggestions on writing.
De, S., Berrada, L.., Hayes, J., Smith, S. L., and Balle, B. Un- locking high-accuracy differentially private image classi- fication through scale. arXiv preprint arXiv:2204.13650 2022.
Impact Statement
Diakonikolas, I. and Zarifis, N. A near-optimal algorithm for learning margin halfspaces with massart noise. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Diakonikolas, I., Gouleakis, T., and Tzamos, C. Distribution- independent pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019.
References
Arora, R., Bassily, R., Guzmán, C., Menart, M., and U1- lah, E. Differentially private generalized linear models revisited. Advances in Neural Information Processing Systems, 35:22505-22511, 2022.
Dong. J., Roth, A., and Su, W. J. Gaussian Differential Privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37, 02 2022.
Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foun- dations of computer science, pp. 464 474.473.7 IEEE, 2014.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Bassily, R., Mohri, M., and Suresh, A. T. Differentially pri- vate learning with margin guarantees. Advances in Neural Information Processing Systems, 35:32127-3211 2022.
Dwork, C. and Lei, J. Differential privacy and robust statis- tics. In Proceedings of the forty-first annual ACM sympo- sium on Theory of computing, pp. 371-380, 2009.
Bun, M., Carmosino, M. L.,, and Sorrell, J. Efficient, noise- tolerant, and private learning via boosting. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 1031-1077. PMLR, 09-12 Jul 2020.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cal- ibrating noise sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryp- tography, TCC 06, pp. 261-2662220 2244,28,775 2006.
Chandrasekaran, G., Kontonis, V., Stavropoulos, K., and Tian, K. Learning noisy halfspaces with margin: Mas- sart is no harder than random. In The Thirty-eighth An- nual Conference on Neural Information Processing Sys- tems, 2024.
Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the Forty-Firs Annual ACM Symposium on Theory of Computing, STOC '09, pp. 381-390, 2009.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differ- entially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3-4)2211 1-077 2014.
9

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Feldman, V., Gopalan, P., Khot, S., and Ponnuswami, A. K.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
New results for learning noisy parities and halfspaces. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006.
Near, J. P. and Abuah, C. Programming Differential Privacy, volume 1. 2021.
Freund, Y. and Schapire, R. E. A decision theorettic general- ization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119-
Nguyēn, H. L., Ullman, and Zakynthinou, L. Efficient Pri- vate Algorithms for Learning Large-Margin Halfspaces. In Kontorovich, A. and Neu, G. (eds.), In the 31 Interna- tional Conference on Algorithmic Learning Theory, vol- ume 117 of Proceedings of Machine Learning Research, pp. 704-724. PMLR, 08 Feb-11 Feb 2020.
139, 1997.
Ghazi, B., Kumar, R., Manurangsi, P., and Nguyen, T. Ro- bust and private learning of halfspaces. In International Conference on Artificial Intelligence and Statistics, pp. 1611. PMLR, 2021.
Nissim, K., Raskhodnikova, S., and Smith, A. Smooth sensitivity and sampling in private data analysis. In Pro- ceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 75-84, 2007.
Guruswami, V. and Raghavendra, P. Hardness of learning halfspaces with noise. SIAM Journal on Computing. 39 (2):742-765, 2009.
Novikoff, A. Proceedings of the symposium on the mathe- matical theory of automata, pp. 615-621, 1962.
He, K., Zhang, X., Ren, S., and J. Deep residual learn- ing for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Panagiotakopoulos, C. and Tsampouka,
P. The perceptron with dynamic margin. In Algorithmic Learning Theory: 22nd International Conference, pp. 204-218, 2011.
Johnson, W. B., Lindenstrauss, J., and Schechtman, G. Ex- tensions of lipschitz maps into banach spaces. Israel Journal of Mathematics, 54(2):129-15) 138, 1986.
Papernot, N. and Steinke, T. Hyperparameter tuning with renyi differential privacy. In International Conference on Learning Representations, 2022.
Koskela, A. and Kulkarni, T. D. Practical differentially pri- vate hyperparameter tuning with subsampling. Advances in Neural Information Processing Systems, 36, 2024.
Papyan, V., Han, X., and Donoho, D. L. Prevalence of neural collapse during the terminal phase of deep learn- ing training. Proceedings of the National Academy of Sciences, 117(40)
Koskela, A., Redberg, R. E., and Wang, Y.-X. Privacy profiles for private selection. In Forty-first International Conference on Machine Learning, 2024.
2020.
Raskhodnikova, S. and Smith, A. Lipschitz extensions for node-private graph statistics and the generalized exponen- tial mechanism. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 495-504, 2016.
Larsen, K. G. and Nelson, J. Optimality of the johnson- lindenstrauss lemma. In 2017 IEEE 58th Anmual Sympo- sium on Foundations of Computer Science (FOCS), pp- 633-638, IEEE, 2017.
Liu, and Talwar, K. Private selection from private candi- dates. In Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, pp. 298-309, 2019.
Rosenblatt, F. The perceptron: A probabilistic model for information storage and organization in the brain. Psy- chological Review, 65:386-400 1958.
Liu, Z. and Zhou, Z. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth Interna- tional Conference on Learning Representations, 2024.
Sason, I. and Verdu, S. f divergeecce inequalities. IEEE
Transactions on Information Theory, 62(11):5973-6008 November 2016. ISSN 1557-9654.
McSherry, and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp. 94- 103, 2007a.
Vapnik, V. Statistical learning theory. 1998.
Wang. C., Zhu, Y.. Su, W. J., and Wang, Y.-.. Neural collapse meets differential privacy: Curious behaviors of NoisyGD with near-perfect representation learning. In Proceedings of the 41st International Conference on Ma- chine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 22334-52366 PMLR, 21-27 Jul 2024.
McSherry, F. and Talwar, K. Mechanism design via dif- ferential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) 07)) pp. 94- 103, 2007b.
10

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Zhu, Y. and Wang, Y.-.. Improving sparse vector technique with renyi differential privacy. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 20249- 2020.

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
A. Extended preliminary and auxiliary lemmas
A.1. Truncated Negative Binomial Distribution
Definition A.1 (Truncated Negative Binomial Distribution (Papernot & Steinke, 2022))), Let E (0, 7 E (-1, oo), and K ~ gf with support on E (1.).3...)
1) + 0:
(1 - +)** A-1
[+
E[K] 711 - r)
PGF(x) = (1 - -)))
PKKK = k)) = p- 1=0
1+1)
r(1 rq)"
r -
r) = 0:
r)*
1/r E[K]
PGF(x) log(1 (1 r)x)
P(K- = k)
k log (1/))
log(1/r)
log(r)
Remark A.2. When 7) = 1, T,B corresponds to geometric distribution. When 1y = 0, TN corresponds to logarithmic
distribution.
Fact A.3 (Cumulative distribution function for TNB1,). For t 2 1, P(TNBI,- 5 = (1- r))
Lemma A.4 (Tail bound for 1) For 3 E (0, IP TNB
Tog(1-r)
log(8)
3
Proof. By Fact A.3, let (1- - r) < B, we have t 2
log(3) Tog( Tog(I-r) I-r)
A.2. Concentration Ineqialities
Lemma A.5 (Concentration of maximum of Gaussians). Let E1.... En ~ N(0, o.), then:
Bdd
(in expectation):
E
max & iEIn
I <oV2loon
(with high probability): For any 3 E 1), we have:
max & 2 20 2lgggn) + v 12log(11/)) 1/3) I EEIn]
Corollary A.6 (Concentration for range of Gaussians). Let En,-..En ird No let M == max and min & then:
iE|n] iE(m)
P(M m 2 20 2 (2n) 2 2 (log(2/) s B
Proof. For any 12 0:
t P(M m 2 21) s
< m <MM < t
2 19
2
t
PPM )
+ P(m 2 -
(4)
= 2P(M 2 )
Set 1 20 22 + 2 log((2/)), we have:
2P(M 2 ) = 2P 2 2logg(2)) + 2loog(2/8) s B
12

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Lemma A.7 (Upper bound for maximal of random number of Gaussians). Let K ~ TNB,r and EI, ~ 02), we have
iid
77 - r)
E
min
S og 2 log
[E[K]
r(1
Proof.
min &e [E(K]
min & (EE)
PP( =
j=1
$
v 2log(j) P(K = j]
Lemma A.5
(5)
V20EK~INB,.. IIAANBB,...Ioolle [lg(KK)
S 22 (VIggERWTTNB,.. (K))
Apply Jensen's 's Inequality twice
1111 ((1-r) r(1 rm)
v 2
Remark A.8. K ~ 1, then E Keve
min &r [E(K]
S ///2logl///
A.3. Other lemmas
Lemma A.9 (First order condition for convexity). Let f 12d + IR be a differentiable convex function. The for any x, E. D, we have:
- x) f(y) - f(x) N y
with g being sub- gradient for f at
Lemma A.10 (L2 sensitivity for the gradient of c-hinge loss). Let X, the La sensitivity of (wLc(w;:))
Σ (wl(,x),
(X.))S
(a) (adding/removvin):: max |x]|
zEX
(b) (replacement): max |
DEA
Proof of Lemma A.10. Lipschitz constant of Lo(y(ss x)) is upper bounded by ||x||/c.
A.4. Other definitions
Definition A.11 (Excess Empirical Risk). Given dataset S' E X and loss function L W x X - R, the excess empitical risk for parameter E W is defined as follow:
EER ()) [.w;; S) min L(w; S)
wEW
B. Proofs of Margin preservation Lemma 5.1 and Lemma 6.2
The distance and angle preservation lemma presented here is derived from the renowned Johnson-Lindeessrrus lemma (Johnson et al., 1986):
Lemma B.1 (Lemma A.3 in Bassily al. (2022)). Let X = (xI,.., Xn) C Rdd distortion rate E (0, 1]. and & be k x d random matrix with 2 sid L Rad( with & = login(x+1)/8)) ~
Then w.p. at least 1 - 3 over the randomness of 4
V%
the following two statements hold simultaneously for any u, v E X:
13

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
(a) V1 5 ||| < | S +T+ |
(b) ( Pv) (u, v) v
B.1. Proof Lemma 5.1
formal version Lemma 5.1 is provided below:
Lemma B.2 (Formal version of Lemma 5.1). Let S = {(x, 1i) C R2 x {=1} with ||x|| S. b, distortion rate parameter
E (0, 1), + ~ II == V 2a) (xd with k = 0 (=s((nt)((xt2/(8)) Then, for any S' E 2 with 7(S") 2 we have
eb 2 1-
Paw1 ((055)) 2
Proof. For any S' C 2 with (S') 2 yo there exist some unit vector we E I2 s.t. (Wwr) 5*) % running JL projection over S [Wsr} and k O (1n((++2)()+))1 yields the following guarantee by Lemma B.1 (b):
E Fa-n (K(bwsr, 4x) (W x
2 1
3
This implies the following happens w.p. at least - 3 over the randomness of Φ:
eb
eb
min y (Bws, (x) (x
min y(Ws x) (x.))
3
Under the same event, with norm preservation stated in Lemma B.1 (a), we get Combing things all together, get a lower bound for ($bS"):
@wws - 1
|| || = 1+
3
3
y(ows' 4x)
eb
2 ?
eb
min (x.y)ES
/ +
2
where the last inequality is by E [0, 1]. Thus,
Paw1l (((55) 2 ? eb
2 -
B.2. Proof of Lemma 6.2
The proof of Lemma 6.2 is by directly applying Lemma B.2
Lemma B.3 (Restate of Lemma 6.2). Let S = {(x,, ni) C (1) x {+1} and 7 E [0, 1). Construct JL projection matrix O E Rexd with entry i.i.d. Jx Rad(?) ()) and O log (1)((++))))))))) For any S.n Sm((), we have?:
Po (7(S)nn) 2 2 3)
2 3
Proof. Recall that
(nn()) = (S' CS: 7(')) 7
Thus, for any S E arg max |8', by Lemma B.2 with distortion rate = 7, we have: ('))
Pown (7(55 >
2) -Pa (>(0S;)2 > 2) 3
2 21-8
6
*Rad(H) denotes Rademacher distrihution
14

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
C. Technical Lemmas for noisy gradient descent (Algo. 5)
C.1. Noisy Gradient Descent
Algorithm 5: ANGD (NG Noisy Gradient Descent (Bassily et al., 2014)
Input
:Data S {x,, 3e I& {=1}, loss function f(), GDP budget
2 Choose some reference point wrof E Rd,, initialization wo Rd
3
Set : (L(w;)) = ((x,))s <(w; (Iz; 1i)) and L2 sensitivity of L is A,
number of iteration T n=²11?
noise parameter o- = AVT nA.
learning rate 1j = W Wo A'
for O.... do & (0 L2a)
Wi41 VV LWw, S) + Et)
7 Output
:Averaged estimator:
El= We or Last-iterate estimator: WT
C.2. Convergence in expectation
Lemma C.I. Algo. is μ-GDP. Furthermore, for the averaged estimator w:
//W Wo Avd
EA [[W:))] [( 5) S
Proof of Lemma C.I. The privacy guarantee comes from GDP composition. For notational convenience, denote gt V WwL(w;;)) 9. 9t & then Wx+1 119t. have:
[[ Wrar|l 2 = || 199: Wret
||we Wrefll - ( -weet) + 17² [| 112
Taking expectation conditioned on we, and by EB we] = It. Eig. wT] S $n²12 do² we have:
B||lw-11 Wief |2]] = EE [E [|/w+11 Wref 12 (w:))
= E [|/we W w.] - 2n7 ww We - - + 11 1/111
| w. Wreel - 27/ S) Ż Z(Wret; 5)) + (n² + do²2 Lemma A.9
By telescoping sum and dividing both sides by T, we get:
T-1 (ww:s)
L( L(WT; S)] ((wert: ret:: 5) S
-(Wrert S)
T
Wrel
woll2
WT Wret
+ m)? + doo2)
Tn
woll
+ nn22 do²)
Tn
Since =
n2pp² 0² n?2, and choosing 17
W woll 12d44 to meet the equality condition of AM-GM, we get:
Wref Woll ( + do2)
E [) - L(Wref: 5) 5 2/
T
2n W -wll
2v 2v / woll
VT
VT
4/ 4A /dll woll
p
15

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
C.3. Convergence with high probability
Lemma C.2 (Theorem 3.5 Liu Zhou (2024)). Running Algo. with step size 1) V T( 2 log(1/3)
and output
last-iterate estimator w. With probability at least 1 B,
L(w: S) - L( S) S 50 |Iwret wo dollAA/logg1//33
(8)
D. Margin Inlier-outlier based convergence analysis for AJLGD (Algo. 1)
In this section, we derive convergence bound for AJLGD (Algo. characterized by margin inlier-outliers.
D.1. Expected guarantee
We derive the convergence guarantee for AJLOD (Algo. 1), with expectation taking over the randomness of the ERM algorithm.
Lemma D.1 (Expected convergence bound). Suppose S Sin Sott C Bd) {=1} with ((Sm) 27 Run Algo. with hinge loss (-)))(),, GDP budgel μs, and dataset S. The averaged estimator R& satisfies: w.p. least 3 over the randomness of JL matrix 4:
62 1 1/2 ((n + + 1)/3)
Souu
E /alln/s(W;;5S)) so
+
n
ym
Proof of Lemma D.I. Denote the projected dataset Φ5 = ((Proja)22)) (xx;), ui))i=, Since ((S.)) 2 by assumption, apply Lemma B.2 with distortion e 7/b and O ((((++))(+++88)) we have 7(bS 2 w.p. least
1 B. We denote this event by E1. Let Win IK be the normalized max-margin separator for SS we have 1y/3(Win) (ix, y)) 0 for any (fxx y) & under event Ej.
Now, initialize ANGO with hinge loss function b733. dataset 4S, GDP budget μi, reference point Wief Wins initialization point Wo and learning rate 7 = V | woll
+dozj- w be the averaged estimator outputed from ANGD (Algo. 5). Conditioned on the event E1, which happens w.p. least 8 over the randomness of 4, have:
Win: $5) + 4AVM
Ea(ley/a(W; +5)) & Ly (win:
Lemma C.1
4AVT
- (win D.S.)) + L @Sont)
4AVK /
- (Wi: S +
under event E3
Under the same event, we analyze the worst-case guarantee on the margin outlier set S
Ly/a(Wm: (Sout Σ /Sut
+
Win
max
||xx||
xESuut
3b
Sott
1
V
1 +
3b
Lemma B.1 norm preservation
23b Soutl
5%
Given that the projection dimension is k
O
(olgg((n+2))+=11// and the L2 sensitivity of ly3 is A S
62
12b
16

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
(Lemma A.10), we have, with probability at least
B over Φ the following bound for the averaged loss:
EAlly/s(w QS)] so 60 log
(( 10lgg"2(11 + 2) + 1)/B)
b|Sout]
ny²
ny
Using the above expected convergence Lemma D.I and margin preservation Lemma 6.2 we have the following corollary:
Corollary D.2. Given 7 E [0,b], b), running Algo. I with hinge loss (-)3()), GDP budget μs, and dataset S. The averaged estimator E RR. satisfies: wap. least - 3 over the randomness of JL. matrix +:
( b² 1ogg22((1 + 2n + 1)/3) min E
b Sout
E EAl 4S)] <
O
ny2p
yn
D.2. High Probability Guarantee, Lemma 6.3
Using Lemma C.2, we can also establish the high-probability version of Lemma D.I. Lemma D.3 (High probability convergence bound, Lemma 6.3). Under the same algorithmic conditions as Corollary D.2, with probability at least 1 28, the last-iterate estimator from Algo. 1 satisfies:
(B log 1/2 (1/3) log' 1/2 ((n + 1)(n + 2)/3)
6) S
Ln/3(we DS)
min Sout ESont (1)
+
2y22
7/12
Proof. Let the projected dataset be denoted as +S = {( (2 (xx)
Mi) v:) H. Given the assumption that ((Sm)) 2 apply Lemma B.2 with a distortion rate = 7/b and k O lou( (on((x+2)(
This ensures that ((9. 3 with probability at least B. denote this event as ET. Let Win E R be the normalized max-margin separator for $ Under event E1, we have Ey/3(Wnn ($x, 9)) for any (1xx, y) D
We initialize ANGD with the loss function E Lx/3. dataset 45, GDP budget μ4, reference point Wzef Win. Waet wall2
initialization point Wo = 0, and learning rate 1j = T(n 4 (og(1/8]) V T(n (od444(( Let w denote the last-iterate estimator obtained from ANGD (Algo. 5). Conditioned the margin-preserving event and the successful exccution of ANGD, which occurs with probability at least - 23, we have:
A A lolog(1//3
(y/ 45) <
L (mm) 2 @Sout) +
Lemma C.2
A Avklog(1/2
Lnss(Wini SSon)) +
under margin preservation event E
b) Soutl
by bolog(1/3)
by log((1 (n + 1)(n + 2)/B)
0
14y
7
b/ S/ut
b2
(og((113) log((n (n + 1)(n + 2)/3)
-
2
Finally, dividing both sides by n and applying margin preservation Lemma 6.2 we obtain, with probability at least 2,:
112 (/llog/2(11) log 1/2 + 1)(n + 2)/3)
b) b/uS
L,,/((: (W: <
min Sant (Sou(())
+
njua
17

---

Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
E. Privacy Analysis for Atter (Algo. 2)
E.1. Technical lemmas
We first present a conversion lemma from Gaussian DP to approximate DP:
Lemma E.1 (GDP to approximate DP conversion). Suppose mechanism M satisfies μ-GDP, then M is also (e, with
S 1²
20/glog(10))
Proof. By the definition of Gaussian Differential Privacy, we know that M is dominated by the Gaussian mechanism with sensitivity of and noise parameter 1/14, i.e.
He (M((X)IMM(X)) & Har Har (N(O,, (u, H.r (
The rest of the proof follows the same procedure in the proof of Lemma 5.5 (Koskela al., 2024), with e be =²a 2 + /V 2 log(1/8).
Under a high privacy regime, we have a cleaner upper bound for e: Corollary E.2. Under the same condition as Lemma E.I, E.I,for for any fixed > 0 further assume μ S 22/2log(1/0) then M
satisfies 2p 22 (
E.2. Privacy analysis for Atter
It's equivalent to analyzing the privacy guarantee for compositions between GDP mechanisms:
Lemma E.3 (Privacy for Alter (Algo. 2)). Given any > and ε < 8 (1))) let {M:} being a sequence of
mechanisms with M, satisfing 2/22m log(1/6)
-GD. The composed mechanism M == Mm o... o M1 satisfies (8, 8DP
Proof. By adaptive composition of Gaussian DP, we have: MM satisfies have M satisfies ()DP
GDP. Thus, applying Corollary E.2, 2/21og(1/8)
F. Utility analysis for Atter 2)
In this section, consider generalized version of Ater. Namely, we have noisy observations (Us + foloce, and Oout = arg min e + } where &e ~ o0), We are interested in bounding the deviation between Un... and min Ug 0-
e5e
F.1. Expected guarantee
Lemma F.1 (Expected guarantee). For possibly random (Uo Jeee we have:
Eg
min Uo + 20 / 2 ()) 9EB
where the expectation is taken over the randonmess of Gaussian noise
Proof.
min {e} = Upan + EBous
definition 0out
> Udon + min to
which implies:
Un.n min(Us + Eo}
min &o #20
(9)
8E0
On the other hand:
min
{o} < min Uo max Eo
#EB
#EG
AE0
18

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Putting things together, have:
Ugan
min Up + max Eo
min Eo
Finally, by taking expectation w.r.t. Gaussian noises, we have:
E(Uo
min Uo Emmax Eo] BEB
E[min En] 82e
BE0
By & is symmetric, have:
E min {el = E max [8] = -E[max Eol AEB
Thus,
E [ Bont I min Up + 2E mmax Ee]
DEB
min Uo 2a / (og(
where the last inequality is by Lemma A.5.
E2. High probability guarantee
Lemma F22 (High probability guarantee). For possibly random {Ue) w.p. at least B over the randomness of Gaussians:
Ubo.s min Up + 20 2lgg2))(() + + logg223
0EG
where the expectation taken over the randomness of Gaussian noise
Proof. Similarly, as the proof in the previous Lemma, we have:
Ug S min Up + max Eo min Eo
8EB 8E8 860
The remaining proof is by applying Lemma A.6.
G. Proof of Lemma 6.4
Lemma G.1. Given dataset (1) {+1))", for any y [1/n, 1], there exist 5 from doubling set r 11/n,2/n, 4/n,.., 1}, such that:
Souu nz
(
((Soucl ny
min Sout ESue (
+
< min
+
(10)
njpe
Sons ESnut (7)
ny?E
Proof. For any Sout Sout (7) with 2 4, by the property of the doubling set I' from 1/n to 1, there always exists 7 E such that 7/2 < 7 < Also, for any Sout E Sout(7) observe that:
SSuut
min
|$]
min SeS.ur(A)
|$|
SESoue
The facts together imply that:
Sontt nz
Sout
min
+
<
min Sous E (9)
Sout ESuut
1538
nty
17725
(11)
|oout
min Sout ESun
nzy
2
Taking minimum on both sides implies:
Sout! ny
Souu ny
1
min RET Sout (S (3)
+
min ve(1/n,1] Son Eonu (x)
(12)
n528
ny?e
19

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
G.1. Proof of Lemma 6.4
Proof of Lemma 6.4. W.L.O.G., assme n. 7 1/n implies ny
Together with Lemma G.I, we have:
Sout ny
1
( | n2y
min yET Sout (Sous())
+
A1
min 7E10.11 Sont (Sout
+
Al
ny?E
ny?E
(13)
|outt
1
min Sant S
A
my28
n/y
(5
We note that Lemma 6.4 remains valid even when the data are not confined to the unit ball:
Corollary G.2. Given dataset S E (Bd(b) {+1})", and doubling set I = (b/n, 2b/n, 4b/n, ..., bJ. we have:
Sont n2yy
Sout
min YET' Sont (S)
AIS
min Sont CS (5
+ my?5)
A1
(14)
ny?e
reyy
H. Proof of Theorem 6.5, empirical risk bound for Algo.
Theorem H.1 (Theorem 6.5 restated). Running M with Rs satisfies (e, D), for 5 E (0, 1) and & E (0, 8 8log(1/6)) In
addition,
(I) For the averaged estimator Wont E RRd, we have utility guarantee in expectation:
Ô (p2ne
|Soue
n? )
[Wou)) E
min Sane CS ( Montt 1
72nE
+ ym
a
(2) For the last-iterate estimator Wout E Rdd w.p. at least 1 33/n²:
Souel
+ 1 Al
Rwowt 1
min Sene CS (SS Sow))
72 +
mm 11
The privacy analysis is the composition of GDP mechanisms, which directly follows Lemma E.3.
H.1. Proof of Theorem 6.5, in expectation version
We first introduce the following utility lemma:
Lemma H.2 (Expected ERM). Under the condition of Theorem 6.5, let Wout E Rdd be the average estimator output from Algo. 3, we have:
62 15 +
b|Sout]
1
1
RR (Wout)))) min min yel Sout ESuut (t)
+
yn
ns
n²
Proof. Since Alter (Algo. 2) allocates privacy budget evenly, let's denote μ to be the GDP budget for each call of AAloo(Algo. 1).
By Lemma D.2, the following convergence guarantee holds, w.p. at least 3 over the randomness of JL projection, for running AILO with margin loss L,/3:
6 log 1/2 12 + 2)(n 1)/8)
log
b/Sout]
Balir/s(Ww;; (75)
min Sau ESou (t)
O
(15)
2
mm
20

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Since the additive Gaussian noise has distribution (0,11//2) by Lemma F.1 the expected guarantee of Antr is:
$ min Eu (RlRs( w 2 llg(([])
E. EA(Rs(Wout)
yer
nu
[ /1 Wy: S, + 2 (Tg(
min E TeT
np
b² loog'" 1/2 ((n 2) + 1)/3)
b|Sout] yn
2 2 (lg
min 7EL
min Sout ESun
2y2p
np
where the second inequality is by hinge loss upper bounds zero-one loss, and the third inequality is by Eq. 15. Thus, w.p. 1 - B over the randomness of JL projection, we have:
ba log 1/2g//2( (( 22 1)/8)
b|Soucl
2 2 (I'(
EA (Rs(R( (Worr]
S min 7ET Sous ES (1)
min
O
1
7
ni
(a)
(b)
Plug in [T] = [n)] + 1. lo and scale 3 by 1/[r], we have:
12 log 1/2 ((n + 2)(n + 1)/3)
(a)
2
yn
4b2 log 1/2 (TT + 2)(n + 1)/3) log (
SuSu
+
(16)
ny?E
862 log 1/2
(n) 122(n2)(()))))))))
1/3 (2(n h 2)(n (n)2 (2(1/))
b/St
+
where the last inequality holds when n 2 2, we have [ = [log [n)] + 1 4 (n)
(b) 2 2 (Tl)
n/
1/2 8 2/2/2/2/2 log 1/2 (1/5) log' 1/2 ((T)
(17)
1/2 1/2(n) (n) 16.2 2ogg
log 1/2 (1(5))))))))) log 1/2 (4 (og)
nE
Setting 1/n² and noticing that zero-one loss upper bounded by have:
802 log 1/2 (og")o""" 2/ 2)(n + (ogg(())
log
b|Sout
R.,4 ( Wout]] S min Tel
min Sout (Son(t))
+
2
7/
16 log?
1/2 //221/2()) (n) log 1/2 (1/8) (244ggg
ns
n2
ò
b/St
1
1
min 7ET'
min Sant (Sme(())
+
+
+
1172
nn
ns
n?
Now, we start the proof of Theorem 6.5, in expectation version:
21

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Proof. By Lemma H.2, have:
(11
1
Sout
1
1
E EA(RR(Woot]] S min yel Sout (Son(())
min
+
+
11722
7
ne
n²a
Since Roowout) is upper bounded by 1, we have
Sout
(A(Rs(Wout]) I min yel Sout ESont())
min
+
+
A
11722
11.2
[oot
min Sont CS 7: (oa))))
+
+
A
?
n2
where the first inequality is by y < 1 and the second line is by Lemma 6.4
H.2. Proof of Theorem 6.5, high probability version
Lemma H.3 (High probability ERM). Under the condition of Theorem 6.5, let Wout E Rd be the last-iterate estimator outpul from Algo. 3, we have w.p. at least 3/n²:
(
b² 1
bjS
1
Rww S min HET Sout (Sout(?) (+))
min
+
+
+
7/
ne
12
Proof. By Lemma D.3, for a single call of AJLGD that optimizing b//3. w.p. at least -23/11%, the last-iterate estimator Wy satisfies:
b2 log ((1g) 1/2 (11 1)(n 2)/B)
b|S
(W.y; +S)
min Sont ESout
ny2p p
7m2
Similarly as the proof for Lemma and notice that additive gaussian noise has distribution (N, 1/p²), and by union bound over [ calls AJLGD we have w.p.
38:
R. (Wou)) < min Rs ( w.) 2. log(2[11)
2 2 log(2/3)
7ET'
nu
2 2 log(2(T)
2 2 log(2/3)
min TET L T 5)
np
1f (IT) (BB) 1/ 1/2 log
1/2 ( (n + 1)(n + 2)/3)
< min Tell
min Sout (S.us())
+
n22
ym
+ [T
2 (2gB2/5)
(b)
Notice that [T] [log, (n)] 1 $4 4logg(n). p=
we have:
1/ 1//1 log(1///)
82 log 1/2 (TT)3 log 1/2 (2 1) + 2)/3)
B|Soul
(a) =
2=24
n
862 log 1/2 1/2 (4 (m) log <
1/2 1)(n 2) log, (n))33))))))))))))))))))))))()) (L/))
b Suut
nT2
n
2/2log(2TT) 16.2log 1/2 (/ log, (n)) log 1/2
(n) log" (1(8)
(b)
np <
nE
22

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Putting everything together and set B 1/n2, have:
Rs(ww (Wont)
17 (4lgg (4(n 1)(n + 2) (n))(())))))))))))))))))))))))) log2 (n) log (1/0))
b/Soutl
$ min yET Sout&Suun ESoncr))
min
+
ny2p
yn
16 log ( logg (n)) log2 (n) log 1/2 (1/0)
1/2
ne
2 2 1og(2/B)
+
(
b²
buSt
1
min
min
+
7ET Sout ES ESane (7)
1772
yn
T1E
Now, we start the proof of Theorem 6.5, high probability version:
Proof. By Lemma H.3, w.p. at least 3/n²:
(
Sout
1
1
Rs(Woul) I min min TET Seus ESurt (7)
+
1y?2
yn
ne
n
Since (Woo) is upper bounded by 1, < 1. and applying Lemma 6.4, we have
Sut
1
(wot) $
min Saut CS (S) Somr)
n
7/2
72
Proofs for population error bound, Theorem 6.7
Theorem I.1 (Restate theorem 6.7), Under the same conditions for E, 8, 1, and n as Theorem 6.5, Algo using score defined in Eq. 6.6 satisfies (e, 6).D. W.p. - 4/n². the output last-iterane estimator Wout E Rd satisfies:
S
RD( S
min Soat
Ö
2 min
7m
)
I.1. Proof of Lemma 6.6
We first state the relative deviation bound:
Lemma I.2 (Lemma A.1 in Bassily et al. (2022)). S ~ D For any hypothesis set H of functions mapping from to R. with probability at least over the randomness of samples, the following inequality holds for all h E H:
(h) < (h) 2 (h) logH)) + log(4/3) + (C((H)log(2m)) + (4/g)
Using this Lemma, we can prove Lemma 6.6:
Proof of Lemma 6.6. By AM-GM inequality,
2/ Rh) VC(H) (on((n) + log(4/3)
VC(H) log(2n) + log(4/3)
< RR)hh) +
n
Thus by Lemma 1.2:
RD(h) S (2Rs(h)+ +5 +5 (C(H))log(2) 14g(4/3)
71
23

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
1.2. Proof of Theorem 6.7
Proof. For any 7 since ki - log [oo<( 11/0)
Denote score(?) (u( S(VC(He,) (0g
7at
For privacy analysis, we notice that under the replacement neighboring relationship, A (sscore())) 1. With the same privacy parameter setting as in Theorem 6.5, we have the algorithm follows (e.8)-DP.
Now we begin utility analysis. In the beginning, we state the uniform convergence theorem for projected data:
For function class Hk. == {x ++ sign( (x, w)) x E IR by uniform convergence, we notice that w.p. 1 - 3 over the randomness of sampling from D, for any Wy R
RoD(ww) S (wa)(w,) + - (VCCHH,, log(2n) + log( (433))
By Lemma F.2 and uniform convergence, w.p. at least 1 23:
5 (og(H, + (og(4(11/8))
2 2 (21()
2 2 log(2/3)
RD(wont) S min yel'
2Rs(0, w.)
(18)
pm
(c)
log
Flln 12
)
Since 3 = 1/n², Notice that ky =
[T| < 4log2(n) when n > 2, we have VC(H)) S
7/2
log(1n2 (n 2 + (n))
32
4 (1/
8 (lgg(1) (n) log(1/8)
Also,
have:
(a) = (og())))og((1)) + log(4
5 5log(4n) (n (n + 2) + 1) (m)) (2g) 5log(16n² 5log(16n"1ogg(m))
=6 ny? + +
ny2
(b) 2 2 (lllog(((T)
16v 2 log 1/2 (n) log 1/2 (1/5) log (8logg()) =0
um
nE
(c) 2 (2/(3
1log logg 122) ①
n
Thus,
Rp (wou)) S min Ô (Rs(0 1 + +
1
(19)
7EL
my?
ne
By zero-one loss is upper bounded by hinge loss and applying Lemma 6.3:
Ô (111 11728 +
1
Souut]
RS( wy) [T()),,,)
Ln (. S) < min
(20)
Sout (Sout())
7m
Putting everything together:
Ô (11 (1 + -
|onnt]
+ 0 (0 +
R (Wou)) x
min 7ET Soat (Sme
my
|Sout]
min TEr Sout ESuntSuuth (7)
no? (1 + +
(21)
ny
Sout
min TEr Sout (T)
+
n min (iinn(1,e)
ny
24

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
where the second inequality holds by y < 1. Finally, by argument similar Theorem 6.4 and the fact that R (Wout) 1,
have:
(1+ Ô (1i + = + min Sout CS (800
|our
RD RD(Wout) (Wout)
(22)
ny
which holds w.p. at least 4/n².
J. Proof of Theorem 4.1
Proof of Theorem 4.1. The privacy guarantee and the empirical risk bound derived in Theorem 6.5; The population risk bound follows by Theorem 6.7.
K. Proof of Theorem 7.1
K.1. Alternative algorithm using advanced private hyperparameter tuning
Algorithm 6: &,,
Input: dataset 5 = (x, We J Privacy budget ε,
2 Set: Margin grid I = 1
2 mj
1}. Run time distribution Q = TNB
Fl
GDP budget μ /ogl (a2-
3 Initilize hyperparameter set
for 7 E I do
k O ( ( log( (
Φ (+) Vkin ) xd
θ = u (ur )
(Wout: Yout: yome
Algo. 4
Output: (Wout; Yout: T yonu)
K.2. Privacy guarantee for AprivTun (Algo. 4)
Lemma K.1 (Corollary 5.5 in (Koskela et al., 2024)). Let run time distribution Q ~ TNB1, suppose base mechanism is u-GDP. Then for fixed 8 0, the private selection algorithm A is (s, DDP for:
3 / 2 8 +
2 -²= + +3
(23)
where A defined in Theorem of Papernot Steinke (2022))
In the high privacy regime, we can relax the parameter E in the above lemma, obtaining simplified expression for e that depends linearly on μ.. This leads to more straightforward privacy accounting for Algo. 4.
Corollary K.2. Conditioned on Lemma K.I, if the GDP budget of base mechanism y S 2/ log (1)), then private
selection mechanism A also (6 2og log (+t) + 6,6)-DD.
Proof. By Lemma K.I and the upper bound on μ4, we have:
3 2 + 3/4 2 1
+ 885 6u
2log r +
(
25

---

Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning
Now, we begin prove the GDP guarantee for AprivTune (Algo. 4): Theorem K.3. AprivTune (Algo. 4) with run time distribution Q ,, and input GDP μ (122og(1/(r6)) satisfies
+ d, for any 24 log( (3)
Proof of Lemma K.3. For any 0 E θ, we view the instantiated "base" mechanism, denoted by Ag. as the adaptive composi- tion of two mechanisms:
(1) M,0;5, / with GDP budget
4 A²
(2) Gaussian mechanism with (2/v2)a* with A being the L2 sensitivity of score function U.
By GDP composition, Ag is μ-GDP. The remaining proof follows Corollary K.2.
K.3. Utility guarantee for ApriVTune (Algo. 4)
Lemma K.4 (Utility of ApriTune (Algo. 4), in expectation). Let U1, Viel be possibly random score corresponding to parameters in θ K T, observe {Ui, + &x herk" with Ei, ädd (O, o²), let Uou min (U;, + E.,) (break tie
=E(K]
arbitrarily) and tout be corresponding index, then w.p. at least 1 PGF K (1 - 1/101):
n((-r) 1 22
E[Uont] S min B(Uo]
8EB
r(1 rr)
Proof. First, notice that:
min (U:, + Ei Uout + Stout tE[K]
definition of Mout
Vout + min Ex 2E[K]
fout belongs to [K]
which implies:
Vout S min (Ur + E.. [E(K]
min E.. KE(K]
(24)
min (U,, + Eio rE|K]
max Ei, & - xe
On the other hand:
min (U, + E., S min (U [E[K]
+ max {5r,} [E[K]
[E]K]
Denote Y = findex((*) E (ig) where 8" arg min E (wa)) Conditioned on Y, we have: dee
E[min (Ug + H. < E
min (U, |Y] + E max {5a, H[] YE
kE(K]
KE[K]
[
min E (w)) + E max Ed]
tE[K]
The last inequality is by (1) using Jensen's inequality and then by the fact E I under event Y: (2) & and event are independent. Putting things together, we have:
E|U.nt Y S E min {U. + Exx Jx E max & YY]
[E[K]
min
E [wm]] + 2 max Ec] 2E[K]
1 2(1--))
min E[L(( + 0 2 0e0
Lemma A.7
r(1 (11-1))
The remaining step is by noticing that PVY) > 1 - PGF 1/(01).
"(gbetkk is multi-set of (1,2....,(9)
26

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
K.4. Proof of Theorem 7.1
We first prove a utility lemma for non-private hyperparameter selection over 7 E I::
Lemma K.5 (union bound for non-private grid search). P > O, For every Y E I, set projection dimension ki log (T(++2(xx+)) )
and JL projection matrix Φ E IRdxky, running ALGGO( By f7 S. p) to get averaged estimator D Wy. Then the following holds w.p. at least 1 3:
log 1/2 ((T] 22 1)/3) |Sout] y/
min Ter
Ea 2,5) s
min yeT Sout ESunl))))
A
(25)
npp
proof of Lemina K.5. By Lemm 6.3, for any fixed y, we have the following holds w.p. least 1 -B/ over the randomness of Øy;
log " + 2)(n + 1)/8)
S
/ s
min Sous ESaut (7)
O
22
7
The remaining proof is by taking union bound over I' and taking minimum over y on both sides of the inequality above.
Lemma K.6. Let P any finite subset of [0, 11, 3 3 = --TQ--TB, TI / (222
M (Algo. 6) invokes with S, Q. T and p is (E + 5, -DDP for any S 24 (olo(((((())) 1)/5). In addition, the oulput averaged estimator Wout Rd satisfies: w.p. at least 23,
|og 1/2 (1 2n + 1)/8) log 1/2 (1
|Sut ney
12 log(n" /8)
E[Rs v
min TE Son (Suu(T)
+
7PEn
nE
Proof of Theorem K.6. By Theorem K.3, the M is (e + 6,6)-DP.
Denote event
{>* being selected), we get PVY) 2 f3. Under event Y:
V2
([Rs(Woot))
< min
TET E R.
v log [ - 1))
Lemma K.4
12 log 1/2 (2(T 1)) 1/2 (( 1)/8)
min
ELL / w 2 S)]
wer'
12 log(n (
min E /3/ "EI
(w,
Wyj S)
log 1/2 ([ + 2) + 1)/3)
Souu
12 12g
min Ter Sout ESuu (1)
+
Lemma K.5
1ry2
log (2 2)(n + 1)/8) log 1/2 (IT 1)/8)
|Sout| ?
12 [oggn?((T)/0
min TET Sent ES (7))
?28
E
Thus, at least 1 - 2,3
log 1/ (T] + 2) + 1)/8) log 1/2 (TT 1)/5)
[ont
log(n2)T))
E <
min Ter San ES (7)
+
7en
nyy
ne
(26)
27

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
Proof of Theorem 7.1. By Lemma K.6 and [T]
(n))(n) when 2, we have
1
Sout
12 log(n (og2(n)/))
min Ter Sous CSustS (1)
2,3
?2
yn
ne
Sout
log 1og2(1)) (n)/ö)
min YET Sous ESout
+
+
7
yn
ne
n2
(27)
1
Sout
1
1
min 7eT Sous ESur (7)
+
0
+
118
n2
1
Sout 1
min TEN Sous ESout (X)
①
72
yn
n
By the fact that Rs(Woul) S 1, we have:
(122
Sout
E R Rs (Wout]]
S
min 7ET Sonr (7)
+
+ n²
A
(28)
Finally, apply Theorem 6.4,
δ (1p11e
|Sout
E R[R (Wout)]
min Sang CS (8
+
(29)
72ne
7n
n2
L. Beyond unit norm assumption on data
For the ERM result, note that the dependence on arises solely through the sensitivity and projection dimension, as described in Lemma 6.3, Lemma D.1, and Lemma D.3. Combined with the adaptivity result established in Corollary G.2, we obtain: Theorem L.1 (Empirical risk bound for M*). Running M with Rs satisfies ()DP, and:
(I) For the averaged estimator Want E RRd, we have utility guarantee in expectation:
δ (
62
b|Sout!
1 n2
ER((Rs(Woull s
min Sout CS 7 (StSon))>
772n5
+
+
A1
(2) For the last-iteratt estimator Wout E Rdd, w.p. 1 13/n²:
min Ô 62
(
(
b)Sout
1
(wot)) S
+
+
A
Soms CS 7(5)Sou))20
ym
ne
For the population risk, the additional dependence on 12 arising from the VC dimension can be absorbed into the ERM bound. Consequently, we have:
Theorem L.2. Running M with Rs satisfies (e, DD.P, and w.p. 4/n² over that last-iterate estimator Wout E Rd.
min δ Sous CS 7(S)Sont)) 20
122 1 (1 + =--
S/Suu ny
+ 1 +
1 1) A1 A)a n
RD (Wut)> s
(30)
ne
M. Derivations for general distribution
M.I. Settings
Without loss of generality, we assume that θ contains a single item of interest, denoted as 8*. We upper bound the probability that 6* is not selected, PP(*" is not selected) = PGF(1 - 1/))),, by 3, and then determine the corresponding distribution parameters. For notational convenience, let := 1/10].
28

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
M.2. Upper bound on parameter for Truncated Negative Binomial distribution with rj > 0 Lemma M.1. Suppose T, and P(O" is not selected) S B. then 01
8²/"
We first do the relaxation:
(1 (1 r)
-
PGE TNB(n))
r- (r + + -rt) -
5-
Then we let:
(-b1-r)) 3
7 81/1(1 + -t)
1,31/1
(31)
7r5 1 ///1 tB//n
/1/"
0 B1/ 10/-//0///7 31/0
Proof of Lemma 7.2. For 1, we can do direct calculations as follows:
(1
PGF (1 (1=
1/r-1
r(1 1/101)
1 (1- (1
3
which yields:
-1- rL1-8)(1 - 1/101) 3/1
B
3 rs 0 -
1-3
M.3. Deferred discussion
In this section, we set the failure probability as B n= for some > 0 and the hyperparameter set size as |O] (ng.
From Lemma M.1, we obtain > B 1/ + (1 - (T)) (n²/1 - 1) log(n) + 1, which implies that the expected number of repetitions should be at least Onn//))
N. Removal-Margin experiment
N.1. Setting of the experiment
We train linear SVM classifiers on the CIFAR-10 dataset preprocessed by three methods: (1) pre-trained ViT features, (2) extracted features from pre-trained ViT, and (3) no preprocessing.
We iteratively eliminate "outliers," " defined data points with the smallest normalized margin value '(Defn. N.I), After each removal, we refit the SVM and recompute the updated margin.
To account for variations in data scale across different classes, we plot the normalized margin, defined as follows:
Definition N.1 (Normalized Margin). Given dataset S and a linear classifier hw (x,y) y) >> sign(y(w, x)), we define normalized margin w.r.t. w to be:
v(w, x)
Margin max (xx))s ||||||||
(32)
'before setting negative values to zero
29

---

Adapting to Lincar Separable Subsets with Large-Margin in Differentially Private Learning
N.2. Results
While the margin remains zero for the entire dataset, removing few outliers reveals clear trend: ViT-based features (green line) achieve larger margin and grow more rapidly than ResNet-50- --seee features (red line) more outliers removed. Even after removing 1% of the outliers, the dataset remains non-linearly separable, indicated by the blue lines.
[o, 11
[0. 8]
[1. 9]
method
method
raw
0.025
raw
res50
res50
normalized margin
normaliieed margin
0.030
VIT
normalized margin
0.020
VIT
0.025
method raw
0.04
0.015
res50
0.03
VIT
0.015
0.010
0.02
0.010
0.01
0.000
0.000
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
percentage removed points
percentage removed points
percentage removed points
[1, 5]
[2, 4]
[4, 7]
0.05
margin
normalized margin
normalized margin
0.04
0.06
method raw
0.03
method
methad
raw
raw
res50
0.04
VIT
VIT
0.02
VI
0.01
0.01
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
percentage of removed points
percentage of removed points
percentage of removed points
Figure 3. The number of removed points (in percentage of n) vs normalized margin. The classes from the CIFAR10 training set are labeled each subtitle. more points are removed, the margin increases.
30


Reviews:
[{"review_id": "a0DIsfEoEy", "reviewer": "Reviewer_1JSf", "summary": "This paper studies empirical risk minimization of large (geometric) margin half spaces, in the agnostic setting. They have the following major contributions:\n\na) They give an algorithm for this problem that works even without knowledge of the margin. Prior work by Nguyen et al. (2019) required knowledge of the margin $\\gamma$. Their approach closely follows Nguyen's in this setting- they perform a JL transform to project the data down into lower dimension, and apply noisy SGD to learn in the lower dimension (arguing that the margin is preserved under the JL transformation, which significantly improves the dependence on the dimension). The main technical difference is that instead of requiring knowledge of the margin, they create a logarithmic discretized grid of the margin, and run the above base algorithm on all $\\log n$ possible margin discretizations. They then noisily compare the average empirical risk in order to select the best margin (they also consider a version that uses private hyperparameter tuning developed in prior work by Talwar-Liu and Papernot-Steinke). They show that the bound of $O(1/\\gamma^2 n \\epsilon)$ with known margin can be matched even without knowing it.\n\nb) To extend their result to the agnostic setting, they consider a notion of inliers (subsets of the datasets that are linearly separable with some margin), and outliers, and argue that a bound of $O(1/\\gamma^2 \\epsilon n + |S_{out}|/\\gamma n)$ applies where $S_{out}$ is the set of outliers and $\\gamma$ is the margin of the remaining points (note that this bound automatically applies for the best such subset $S_{out}$). They argue in their introduction that this is a practical way to think about margin, because for some learning problems (and some pretrained features), removing a few 'troublemaker' data-points results in much larger margin. \n\nIn addition to DP ERM, they also give similar bounds for the population risk version of the problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Regarding your comment on weaknesses\n> Weakness 1\n\nWe thank the reviewer for their valuable feedback. We agree that our work builds upon the JL transform and gradient descent (GD) techniques, which have been explored in prior works such as Nguyen et al. and Bassily et al. However, our algorithm introduces several key innovations that go beyond a straightforward combination of these tools:\n\n**(1) Novel Margin Definition and Analysis:**\nOur analysis is based on a new definition of margin inliers/outliers, which, to the best of our knowledge, has not appeared in prior work. This definition is data-dependent (as discussed in Remark 3.1), in contrast to the confidence margin used in Bassily et al., which is data-independent. This distinction is not only conceptual but also technical: our data-dependent margin enables a new analysis technique that is not limited to the JL + GD setting (please refer to comments from Line 291 to Line 295). Most importantly, it leads to a data-adaptive generalization bound that avoids the hard $1/\\sqrt{n}$ rate in the agnostic case that appears in Bassily et al.\n\n**(2) Practical and Efficient Private Margin Selection:**\n\nWhile Bassily et al. employs a grid search combined with the exponential mechanism, their approach involves a more complex score function. Additionally, the exponential mechanism appears hard to implement, as evaluating the score function requires solving non-convex optimization problems (Lemma F.3). In comparison, our method is computationally efficient and straightforward to implement.\n\n\n> Weakness 2\n\nThank you for the insightful question. To address it more generally, we note that the problem of tolerating a constant fraction of outliers—under certain additional assumptions on the noise model—remains open, as discussed in Section 8. We have also included a comparison between our bound and that of Bassily et al. in Lines 165 to 168.\n\n\n\n# Regarding your question\n\nThank you for this thoughtful question. First, we clarify that this section extends our main result by analyzing utility in the context of general hyperparameter sets, which may not be small. For completeness, we provide a utility analysis of hyperparameter tuning. Specifically, advanced tuning methods yield a utility bound with a $\\log(|\\Theta|)$ dependence, whereas naively evaluating all base mechanisms and selecting the best incurs a $|\\Theta|$ dependence. However, in the small hyperparameter setting considered in our paper, the utility bound is not dominated by the $\\log\\log(n)$ as it is obscured by other $\\log(n)$ factors (see Section 7.2). In addition, to the best of our knowledge, the explicit form of the utility bound has not been previously derived. \n\n\n\nLê Nguyễn, Huy, Jonathan Ullman, and Lydia Zakynthinou. \"Efficient private algorithms for learning large-margin halfspaces.\" Algorithmic Learning Theory. PMLR, 2020.\n\nBassily, Raef, Mehryar Mohri, and Ananda Theertha Suresh. \"Differentially private learning with margin guarantees.\" Advances in Neural Information Processing Systems 35 (2022): 32127-32141.", "claims_and_evidence": "Yes, the proofs all seemed convincing and correct to me.", "methods_and_evaluation_criteria": "This is primarily a theoretical work, and so this is not a relevant section.", "theoretical_claims": "I read through the important details of all of the proofs related to DP-ERM for this problem and am convinced that they are correct.", "experimental_designs_or_analyses": "Not relevant.", "relation_to_broader_scientific_literature": "This paper fits into the larger literature on DP learning theory- it considers the natural class of large margin half spaces studied in previous work (Nguyen et al. [2019], Bassily et al. [2022]) and gives utility bounds via a new notion of margin inliers and outliers. Prior work studied different notions of margin and/or assumed that the geometric margin was known.", "essential_references_not_discussed": "All essential references that I could think of were discussed.", "other_strengths_and_weaknesses": "Strength:\n1. The definition of margin inliers and outliers, and developing a utility bound based on them seems like it could be useful, especially since the intro demonstrates that this phenomenon arises in natural learning settings. Additionally, unlike some prior work, this analysis technique also applies when the domain is bounded. \n\nWeakness:\n1. The main weakness of the paper is that the algorithm itself does not seem technically novel (the JL transform + GD approach has been used in prior work by Nguyen et al. and Bassily et al.), and the idea of choosing the margin by private selection over a grid was used in a different capacity (under a different margin definition) in Bassily et al. While the technical details vary slightly, I am not convinced that this algorithm is a significant contribution of this paper. \n2. One issue is that for the bounds to be better than Bassily et al., the number of outliers needs to be relatively small (smaller than $O(\\sqrt{n})$ where $n$ is the size of the dataset) whereas the intro discusses that in practical examples, a large portion (0.1% of the data) needs to be removed to achieve linear separability, so for large datasets, it's not clear that the utility bounds via this method would be better than existing bounds.", "other_comments_or_suggestions": "No other comments/suggestions", "questions_for_authors": "I did not fully understand the relevance of the private hyperparameter tuning results- since the discretized hyperparameter set is sufficiently small (as the authors point out), is there really a need for this? Additionally, what parts of this analysis are novel- it seems like things should follow from the prior work on private hyperparameter tuning in a blackbox way.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SZImTYiHSH", "reviewer": "Reviewer_Ld9c", "summary": "The paper addresses the problem of DPERM for binary linear classification. The authors propose an efficient algorithm that achieves an empirical zero-one risk bound of $\\widetilde{O}\\left(\\frac{1}{\\gamma^2 \\varepsilon n}+\\frac{\\left|S_{\\text {out }}\\right|}{\\gamma n}\\right)$. The algorithm is highly adaptive, requiring no prior knowledge of the margin parameter $\\gamma$ or the outlier subset $S_{o u t}$. The paper also derives a utility bound for advanced private hyperparameter tuning. The main contributions include an efficient algorithm that adapts to largemargin subsets, an inlier-outlier analysis, and improved results in the agnostic case when the number of outliers is small.\n\n## update after rebuttal\nI am generally satisfied with the rebuttal and have raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Regarding your comments\n> \"The experiments in the introduction....Additional explanation would be helpful.\"\n\nThanks for asking this insightful question. Before presenting our explanations, we want to clarify that the “normalized margin”, labeled in the y-axis of Figure 2, measures the distance between decision boundaries. We believe you're essentially asking two related questions: \n\n**(1) Why do better feature representations imply a larger margin?**\n\nThis analysis relates to neural collapse theory. Figure 2 in [WZSW 24] shows that improved feature representations yield smaller feature shift vectors—measuring deviation from ideal neural collapse features—indicating that empirical features align more closely with the equiangular tight frame structure and exhibit larger margins. Accordingly, ViT-pretrained features display smaller shift vectors than those from ResNet-50, reflecting a larger margin.\n\n**(2) How does it relate to the increase of margin as outliers got removed?**\n\nThe intuition is that removing outliers makes classes linearly separable, yielding a positive margin. Continued removal of boundary-near points increases the normalized margin (y-axis, Figure 2) until it stabilizes near the data margin—a trend clearly seen in Figure 3 (top-left). Models with better feature representations show larger margins, explaining the ordering in Figure 2: ViT > ResNet-50 > Raw.\n\n[WZSW 24] Wang, C., Zhu, Y., Su, W. J., & Wang, Y. X. (2024). Neural collapse meets differential privacy: curious behaviors of NoisyGD with near-perfect representation learning. arXiv preprint arXiv:2405.08920.\n\n> Line 402, is 5m a typo? \n\nThank you for bringing up this question. Our intended message is as follows: suppose we have $K$ hyperparameters, each with $m$ possible choices. Using $A_{\\text{iter}}$ incurs an overhead that scales as $m^{\\mathcal{O}(K)}$, whereas employing the advanced tuning methods leads to an overhead that scales as $\\mathcal{O}(Km)$.\n\n> Other comments\n\nThank you for pointing these out. We corrected the hyperlink and resolved the LaTeX \\cite issues. Eq. 2 is defined as the geometric margin in Line 148.\n\n# Regarding your questions\n## Question 1\n> “Why this exhaustive collection is necessary? Could something like … be defined instead?”\n\nThank you for asking this thoughtful question. These definitions serve as tools for proving and stating the main theorem. For instance, they are directly used in the proofs of the margin preservation lemmas (Appendix B) and Lemma 6.4. (for proving adaptivity using a doubling grid). \nWe found the definition you referenced is actually dependent on Definition 6.1. We assume you are referring to $\\arg\\min_{|S'|} \\{ \\gamma(S\\/S') \\geq \\gamma \\}$, which is equivalent to $ \\arg\\min_{S \\in S_{\\text{out}}(\\gamma)} |S|$, where $S_{out}(\\gamma)$ is defined in Definition 6.1. \n\n> “Also, as I understand, the choice for S_{out} … So I think some infimum can be taken right?”\n\nYes, the infimum is indeed taken over all $S_{out}$ such that $\\gamma (S \\/ S_{out})>0$, as demonstrated in Theorems 6.5 and 6.7, specifically on the left-hand side of the inequality in each case.\n\n> “This is a minor point, but it seems to me that the bound depends..less conclusive”\n\nWe appreciate your thoughtful question. Our bound is data-adaptive. We explain our result using Theorem 6.5 as an example.\n\nSince the dataset is finite, there must exist at least one optimal outlier subset $S_{out}^*$ that minimizes the upper bound:\n$\\frac{1}{n\\varepsilon\\gamma(S_{out}^* )} + \\frac{|S_{out}^*|}{n\\gamma(S_{out}^*)}$\nWhile the minimizer of the upper bound depends on the optimal subset, this dependency reinforces the fact that the bound is data-adaptive. This stands in contrast to previous results, which are data-independent and yield a fixed rate of $n^{0.5}$, as reported in Table 1.\n\nSince this optimal subset is unknown—and identifying it via brute-force search is NP-hard—our algorithm, which runs in polytime can effectively adapt to it through a hyperparameter search over a logarithmic grid on the margin, as demonstrated in Theorem 6.5 and also pointed out by other reviewer. \n\n\n## Question 2\nThat's a good question. The order of k is determined by the JL lemma. The k is chosen to ensure every $\\gamma$-level margin inlier set has preserved margin after projection with high probability.\n\nSpecifically, from the statement of Lemma 6.2, the probability is taken over the randomness of the Johnson–Lindenstrauss matrix $\\Phi$. It can be interpreted as the following conditional probability: $P_{\\Phi} ( \\gamma ( \\Phi S_{in} ) \\geq \\gamma/3 \\mid S_{in} ) \\geq 1 - \\beta$ rather than $P_{\\Phi} (   \\forall S_{in} \\in \\mathcal{S_{in}} (\\gamma), \\gamma ( \\Phi S_{in}) \\geq \\gamma/3 ) \\geq 1-\\beta$. We note that the second inequality is a stronger condition, which is what you mentioned in the question. However, throughout this paper, the first one is sufficient for our proof.", "claims_and_evidence": "The main claims are supported by proofs.", "methods_and_evaluation_criteria": "The proposed methodology is well-explained and aligns with intuitive expectations. However, I found the explanation of the experiments somewhat confusing. Please refer to my comments for further details.", "theoretical_claims": "The proofs are reviewed but not rigorously verified. Nevertheless, the results are consistent with intuition and appear to be sound.", "experimental_designs_or_analyses": "Experiment details are less explained and the experiments mainly serves as a motivation of study.", "relation_to_broader_scientific_literature": "The paper builds on prior work in differentially private half-space learning with large margins (e.g., Nguyên et al., 2020, and Bassily et al., 2022), with significant theoretical improvements. It also connects to the broader literature on neural collapse theory, which suggests that the last layer of a deep neural network trained on a classification task converges to distinct points.", "essential_references_not_discussed": "To the best of my knowledge, all necessary references are adequately discussed in the paper.", "other_strengths_and_weaknesses": "The writing of the paper is clear and fluent.", "other_comments_or_suggestions": "- The experiments in the introduction appear confusing to me. I understand that the authors are trying to validate the idea that \"a larger margin is believed to be the reason why pre-trained features help private learners to work better.\" However, the logic connecting better features, large margins, and the quick increase in performance when removing outliers seems somewhat incoherent. Additional explanation would be helpful.\n- Please ensure the correct usage of \\cite, \\citep, and \\citet. Note that the formatting of citations may vary depending on the LaTeX template used.\n- Line 75, where is equation (2)? The position where the hyper-link jumps to does not have (2). \n- Line 402, is $5m$ a typo?", "questions_for_authors": "- I am still a bit confused by Definition 6.1. As defined, $\\mathcal{S_{in}} ( \\gamma) $ is the collection of subsets that have $\\gamma$ seperation. Can the author further explain why this exhaustive collection is necessary? Could something like $S_{out} = {\\arg \\min_{|S'|}} \\gamma(S')\\geq \\gamma$ be defined instead? Also, as I understand, the choice for $S_{out}$ in the final bound can be arbitrary as long as it pertains $\\gamma$ seperation. So I think some infimum of $|S_{out}|$ can be taken right? This is a minor point, but it seems to me that the bound depends on the selected subset, which makes it less conclusive.\n- In Lemma 6.2, is the order of $k$ a worst case choice to guarantee that every $S_{in}$ in $\\mathcal{S}_{in}(\\gamma)$ has preserved margin?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3DHY6OeS9O", "reviewer": "Reviewer_TPCg", "summary": "In this paper, the authors propose a $(\\epsilon,\\delta)$ differentially private algorithm for binary linear classification. The risk bound depends linearly on the arbitrary subset of data points $S_{out}$ , which if removed makes the data linearly separable with margin $\\gamma$. The algorithm is adaptive as the knowledge of $\\gamma$ or $S_{out}$ is not required by the algorithm.\n\n ### update after rebuttal\nThe authors have answered my questions and I would like to maintain my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and thoughtful question. We appreciate your recognition of our work. We have corrected all the typographical errors you identified.\n\nRegarding your question, you are indeed correct: $\\tilde{w_t}$ in Algorithm 5 should indeed be $w_{t+1}$. We thank the reviewer once again for their careful reading and valuable feedback.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "Yes. I checked supplementary material section A through F.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "It improves the results over  Bassily et al. 2-22 and Nguyen et. al. 2020.", "essential_references_not_discussed": "To the best of my knowledge essential references are mentioned.", "other_strengths_and_weaknesses": "The paper is very well written and makes important contributions.\n\n1. When $|S_{out}|$ is small, the proposed work improves the risk bound of previous work by a factor of $\\sqrt{n}$.\n\n2. Knowledge of $\\gamma$ or $S_{out}$ is not required. \n\n3. Analysis of utility bound of advanced private hyperparameter tuning algorithm.", "other_comments_or_suggestions": "1. On line 572 (proof of Lemma A.4), $(1-t)^t$ should be $(1-r)^t$.\n\n2. On line 602, $beta$ should be $\\beta$.\n\n3. In Algorithm 5, step 6, $\\tilde{w}_t$ should be $w\\_{t+1}$.", "questions_for_authors": "Is the 3rd typo listed above indeed a typo? Otherwise, it is not clear how $w_t$ is being updated in Algorithm 5.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses empirical risk minimization for large-margin half-spaces under differential privacy, proposing a margin-adaptive method that does not require prior margin knowledge. The reviewers appreciate the introduction of a novel definition distinguishing margin inliers and outliers, offering improved bounds especially beneficial when the outlier fraction is small. However, concerns were raised about the technical novelty, as the core algorithmic techniques (Johnson-Lindenstrauss transform combined with noisy gradient descent and margin selection via discretization) closely follow prior work. Authors effectively clarified the unique contributions in their rebuttal, emphasizing the data-dependent margin definition and practical efficiency improvements over existing methods. Given the support for the paper, we recommend acceptance.
Decision: Accept (poster)