1 Introduction↩︎

Modern machine learning systems rarely operate directly on raw data. Instead, representation-learning pipelines commonly map text, images, or other types of user records to vector embeddings that can be reused by downstream task-specific classifying heads [1]–[4]. This representation layer creates a false sense of privacy. Embeddings may not be human-readable, yet a model trained on them can reveal information about the training records. In the informed-adversary model, for example, an attacker knowing all but one training record can identify or reconstruct training records from a released model, even if the release is a simple convex model rather than a memorizing neural network [5].

Privacy-preserving AI requires guarantees that remain meaningful even against strong adversaries with side information. Differential privacy (DP) provides such a guarantee by requiring the released model to look nearly the same under arbitrary changes to a single training record [6]. The parameters \((\varepsilon,\delta)\) control the strength of this indistinguishability requirement, with smaller values giving stronger protection. A common implementation is output perturbation: train the model, then add enough noise to mask the effect of any single record [7]. This worst-case calibration is simple and broadly applicable, but it can require substantial noise and therefore reduce accuracy when strong privacy is desired.

DP is naturally aligned with membership inference attacks (MIA), which ask whether a particular record was used to train the model: by making the released model nearly indistinguishable under any single-record changes, DP limits what an attacker can infer about involvement of specific record. However, participation is not always the sensitive fact of interest [8], [9]. In many settings, it may already be known that a person contributed data; the real privacy concern is whether the released model reveals the private content of their record.

This motivates training-record reconstruction attacks, where an adversary uses side information to recover the hidden record itself, often by choosing from a set of plausible candidates. The connection between DP guarantee and reconstruction risk is, however, quite loose [8], [9]. DP mechanisms provide indistinguishability against worst-case single-record substitutions that can be arbitrarily far from each other in the embedding space. While a reconstruction adversary is interested in generating an estimate (i.e., choosing an element from the candidate set) that is in proximity to the target record. Thus, to prevent reconstruction, it suffices to induce indistinguishability over single-record substitutions that are close to each other in the underlying embedding space.

Ball-DP.  We propose Ball-DP, which deploys the usual \((\varepsilon,\delta)\)-indistinguishability but applies it to only single-record substitutions within the ball of declared radius \(r\). The radius becomes an explicit privacy parameter: smaller \(r\) efficiently mitigates local reconstruction threats using less noise, while larger \(r\) expands the protected set at a corresponding utility cost. For the regularized convex prediction heads that we consider, we can ensure \((r, \varepsilon, \delta)\)-Ball-DP via Gaussian output perturbation whose noise scales with \(r\) in addition to the indistinguishability parameters \((\varepsilon, \delta)\). As shown in Figure 1, Ball-DP allows an adversary to differentiate between the target record and a candidate outside the ball of radius \(r\), by enforcing \((\varepsilon,\delta)\)-indistinguishability over the ball it forces the adversary to incur an error that scales with \(r\) in estimating the target record. We can tune \(r\) according to our privacy requirement; recovering the standard DP guarantee when \(r\) is large enough to cover the entire admissible record domain.
Contributions.  We make the following contributions.

1. We define \((r, \varepsilon, \delta)\)-Ball-DP formally, i.e., \((\varepsilon, \delta)\)-indistinguishability over \(r\)-adjacency, and establish its connection to standard DP.

2. We derive \(\ell_2\)-sensitivity of strongly convex empirical-risk minimization (ERM) under \(r\)-adjacency, and present the Gaussian release mechanism calibrated to Ball-DP guarantee.

3. We formally connect Ball-DP to reconstruction robustness; bounding an attacker’s reconstruction success rate as a function of the oblivious prior and the privacy parameters \((r,\varepsilon,\delta)\).

4. We empirically validate our theoretical bounds, and compare the accuracy-reconstruction robustness trade-off of Ball-DP and standard DP across seven learning benchmarks.

Our empirical evidence suggests that Ball-DP provides comparable reconstruction robustness while requiring less noise, thereby mitigating the accuracy–reconstruction robustness trade-off. At \(\varepsilon=2\) and \(\delta=10^{-6}\), Ball-DP improves mean accuracy over the standard global-radius DP comparator across all seven embedding benchmarks at the reported local policy radii. For example, at the \(q50\) label-preserving policy radii, Ball-DP improves mean accuracy by \(0.57\)–\(36.47\) percentage points. Even at the broader \(q95\) local radii, Ball-DP remains more accurate than the global-radius comparator on every benchmark. Finite-prior maximum a posteriori (MAP) audits show comparable empirical exact-identification rates for candidate sets of size \(m=10\).
Comparisons with metric-DP  We emphasize that Ball-DP should not be confused with metric-DP, or \(d_X\)-privacy [10], [11]. In its usual form, metric-DP imposes a distance-dependent privacy-loss bound, so privacy degrades continuously with the distance between records. By contrast, \((r,\varepsilon,\delta)\)-Ball-DP uses the metric only to define a binary adjacency relation \(D\sim_r D'\), and then enforces the standard \((\varepsilon,\delta)\) indistinguishability inequality uniformly over that restricted adjacent subset of records. Ball-DP need not provide any guarantee for substitutions outside the radius, nor does it require privacy loss to shrink for pairs that are closer than \(r\). The advantage of this formulation is that it separates the privacy policy from the mechanism calibration. In particular, mechanisms whose privacy analyses depend on the adjacency relation only through a sensitivity bound can be adapted by replacing the usual sensitivity to \(r\)-adjacency sensitivity. We show this explicitly in the following wherein we adapt the standard Gaussian mechanism to Ball-DP.
Paper organization.  The rest of the paper is organized as follows. Section 2 fixes the ERM setup, the informed reconstruction threat model, and the Gaussian output-perturbation notation used throughout. Section 3 introduces Ball-DP as a radius-restricted adjacency policy and gives the corresponding Gaussian calibration for strongly convex ERM. Section 4 translates these privacy guarantees into Ball-ReRo reconstruction certificates and states the finite-prior MAP audit used in the experiments. Section 5 reports the utility and reconstruction-audit results on fixed embedding benchmarks. Section 6 collects the model-specific technical statements needed for the experimental calibration. Section 7 discusses related work on metric privacy, private convex ERM, reconstruction robustness, and prototype-based learning. Finally, Section 8 provide a summary of the paper. Proofs and auxiliary derivations are deferred to the appendices.

2 Preliminaries: ERM, Reconstruction, and Gaussian Releases↩︎

This section formalizes the learning problem, the reconstruction threat model, and the Gaussian-release notation used throughout the paper. The order is as follows: we first specify what is learned from embeddings, then describe why reconstruction is a meaningful privacy breach, and lastly discuss DP and Gaussian output-perturbation guarantees.
Embedding ERM setup.  Let raw examples live in an application-dependent space \(\mathcal{X}_0\), e.g., photos, text and tabular records, and let labels lie in space \(\mathcal{Y}\). A public encoder \(\phi:\mathcal{X}_0\to\mathbb{R}^d\) maps each raw example to an embedding. From this point onwards, a training record is \[z_i=(x_i,y_i)=(\phi(a_i),y_i)\in\mathcal{Z}:=\mathbb{R}^d\times\mathcal{Y},\] where \(a_i\in\mathcal{X}_0\) is the corresponding raw example. The label space may either be binary, \(\mathcal{Y}=\{0,1\}\), or multiclass, \(\mathcal{Y}=\{1,\ldots,K\}\). A dataset is an ordered tuple \(D=(z_1,\ldots,z_n)\in\mathcal{Z}^n\). We consider \(\ell_2\)-regularized empirical risk minimization (ERM) on the training records. For a parameter \(\theta\in\mathbb{R}^p\), a loss function \(\ell(\theta;z)\), and regularization parameter \(\lambda>0\), we define \[\label{eq:generic-erm} F_D(\theta) := \frac{1}{n}\sum_{i=1}^n \ell(\theta;z_i) + \frac{\lambda}{2}\|\theta\|_2^2, \quad \widehat\theta(D) := \arg\min_{\theta\in\mathbb{R}^p} F_D(\theta).\tag{1}\] When \(\ell(\cdot;z)\) is convex for every record \(z\), the objective in 1 is \(\lambda\)-strongly convex, hence the minimizer is unique. This is a standard convex-learning template behind regularized linear and generalized-linear heads [12], [13].
Reconstruction threat model.  Embedding-space training does not by itself eliminate record-level privacy risk. We consider an informed reconstruction adversary, following the setting proposed and studied in [5], [8], that observes the released model and has substantial side information about the training set. In particular, all records except one target record \(z\) are treated as known; when needed below, we denote this ordered tuple of known records by \(D^-\in\mathcal{Z}^{n-1}\). The adversary also knows the training algorithm, hyperparameters, release rule, and any public information used to form beliefs about the hidden record.

The relevant reconstruction task is therefore not an unconstrained search over the full record space. Side information typically narrows the target to a finite shortlist, or more generally a prior distribution, over plausible alternatives [5]. A privacy breach occurs when the released model lets the adversary identify the hidden record, or a sufficiently close substitute, better than what could be achieved otherwise from its prior information alone. For example, if the adversary has narrowed the target to \(m\) plausible candidates and has no further information, an oblivious exact-identification guess succeeds with probability \(1/m\); a meaningful reconstruction audit should be interpreted relative to this baseline.
Differential privacy.  The gold standard for privacy-preservation of training records is differential privacy [14]. Two datasets \(D,D'\in\mathcal{Z}^n\) are adjacent, written \(D\sim D'\), if they comprise identical records except one. The two differing records must lie in the admissible record domain. A randomized mechanism \(M:\mathcal{Z}^n\to\Theta\) is said to satisfy \((\varepsilon,\delta)\)-differential privacy if for every adjacent pair \(D\sim D'\) and every measurable set \(S\subseteq\Theta\), \[\label{eq:dp-definition} \Pr[M(D)\in S] \le e^\varepsilon \Pr[M(D')\in S]+\delta.\tag{2}\] This indistinguishability prevents any adversary from inferring the inclusion of any record in the training. By extension, DP prevents even an informed adversary, described above, from extracting the hidden record with certainty.
Gaussian output perturbation.  In convex learning, we can ensure DP by output perturbation. Specifically, instead of releasing the ERM output \(\widehat\theta(D)\), we release a perturbed model: \[\widetilde{\theta}(D)=\widehat\theta(D)+\xi, \qquad \xi\sim\mathcal{N}(0,\sigma^2 I_p).\] Here, \(\mathcal{N}(0,\sigma^2 I_p)\) denotes a Gaussian distribution with mean \(0\) and covariance matrix \(\sigma^2 I_p\). This is commonly referred to as the Gaussian mechanism applied to the trained parameter vector. The variance \(\sigma^2\) scales with the \(\ell_2\) sensitivity of the original unperturbed model [7], [14], [15]: \[\Delta_2:=\sup_{D\sim D'}\|\widehat\theta(D)-\widehat\theta(D')\|_2.\] Specifically, when \(\sigma \geq \frac{\Delta_2}{\varepsilon}\sqrt{2\log(1.25/\delta)},\) the Gaussian mechanism satisfies \((\varepsilon, \delta)\)-DP.
Finite-prior exact-identification audit.  The reconstruction threat model above still leaves open how an audit should instantiate the adversary. Prior reconstruction studies often optimize directly for a reconstructed object using attack-specific machinery, such as generative priors or training traces [5], [8]. In experimental evaluations, we take a complementary route that is natural for Ball-DP (presented in the following): side information narrows the target to a small set of plausible candidates inside the declared neighborhood, the adversary’s task is exact identification.

Concretely, the audit asks which candidate record would most likely have produced the observed Gaussian-perturbed model. For each candidate \(z_i\), the auditor forms the model that would have been released if \(z_i\) were the hidden target, compares it with the observed release, and chooses the most likely candidate under the prior. Under a uniform finite prior, this becomes a nearest-model rule: choose the candidate whose simulated trained parameter vector is closest to the observed noisy release. Section 4.1 formalizes this MAP rule and gives the corresponding audit algorithm.

3 Ball-DP: Indistinguishability Over Restricted Adjacency↩︎

Ball-DP introduces an explicit adjacency policy for mitigating reconstruction threats. Specifically, instead of asking the privacy mechanism to hide every admissible one-record replacement, it hides one-record replacements inside a declared metric ball. The radius of this ball becomes part of the overall privacy budget along with the indistinguishability parameters.

3.1 Adjacency policy definition↩︎

Fix a public metric \(d\) on the record domain \(\mathcal{Z}\). For embeddings, \(d\) is typically the Euclidean distance on the embedding coordinate, possibly with label constraints as in  3 .

We now define Ball-DP as \((\varepsilon, \delta)\)-indistinguishability over \(r\)-adjacency.

The radius \(r\) changes the scope of the adjacency relation being protected, not the semantics of \((\varepsilon,\delta)\) indistinguishability on that relation. For \(0 \le r' \le r\), every mechanism satisfying \((r, \varepsilon,\delta)\)-Ball-DP also satisfies \((r', \varepsilon,\delta)\)-Ball-DP. Increasing \(r\) enables protection against a larger number of substitutions, at the cost of additional noise; a trade-off made precise later in the following.

The distance metric \(d(\cdot, \cdot)\) and radius \(r\) makes the scope of privacy by Ball-DP explicit in the following sense. If a model release mechanism satisfies \((r, \varepsilon, \delta)\)-Ball-DP then it prevents an informed adversary with access to all but the hidden record \(z^*\) to estimate \(z^*\) within distance \(r\). Throughout this paper we consider the following label-preserving distance metric. The analyses, however, can be extended in the future to general distance metrics.
Label-preserving distance metric.  Throughout this paper, records are pairs \((x,y)\) and we use the label-preserving Euclidean metric: \[\label{eq:label-preserving-metric} d\big((x,y),(x',y')\big)= \begin{cases} \|x-x'\|_2, & y=y',\\ \infty, & y\ne y'. \end{cases}\tag{3}\] Finite-radius adjacency therefore protects embedding changes conditional on the label. It does not protect label changes; that would require a metric assigning finite distance to cross-label substitutions. This choice also makes class counts invariant over adjacent datasets, which is why count-aware calibration does not violate indistinguishability.

The metric, radius, embedding map, norm bound, and any count metadata used for calibration are treated as public or fixed by the adjacency policy. This is consistent with settings where a private learner is trained on fixed embeddings supplied by an external representation model. If any of these calibration quantities are estimated from sensitive records, that estimation must be privatized or justified as public side information before the Ball-DP claim applies.

3.2 Ball-DP for convex learning↩︎

We next connect radius-restricted adjacency to Gaussian output perturbation for the ERM problem 1 . The key quantity is how much a single record replacement can change the gradient contribution of the loss. We capture this through the following uniform regularity assumption.

Section 6 gives the constant \(L_z\) for the ridge-prototype model used in the main experiments and records the corresponding constants for the additional convex heads. The derivations for the secondary heads are deferred to Appendix 12.

The proof of Theorem 2 can be found in Appendix 9.2. The theorem shows that the distance between the corresponding ERM solutions is bounded linearly in the radius \(r\). Therefore, the Gaussian output perturbation can be calibrated to the protected radius \(r\) rather than to any arbitrary replacement.

In what follows, \(\Phi\) denotes the standard normal cumulative distribution function (CDF). For sharper Gaussian calibration, we use the analytic Gaussian mechanism scale of [15]. Given an \(\ell_2\) sensitivity bound \(\Delta\), define \[\mathsf{AGM}(\varepsilon,\delta,\Delta) := \inf\left\{ \sigma>0: \Phi\left(\frac{\Delta}{2 \sigma}-\frac{\varepsilon \sigma}{\Delta}\right)-e^{\varepsilon} \Phi\left(-\frac{\Delta}{2 \sigma}-\frac{\varepsilon \sigma}{\Delta}\right) \leq \delta \right\},\] where \(\mathsf{AGM}(\varepsilon,\delta,0)=0\) by convention.

Alternatively, if \(\sigma\ge \frac{\Delta_r}{\varepsilon}\sqrt{2\log(1.25/\delta)}\), then the same conclusion follows from the classic Gaussian mechanism bound [14]. Moreover, under Assumption 1, due to Theorem 2 it suffices to use \(\Delta_r=\frac{L_z}{\lambda n}r\). Note that the Gaussian mechanism calibrated to \((r, \varepsilon, \delta)\)-Ball-DP also satisfies \((t, \varepsilon_t, \delta_t)\)-Ball-DP for \(t > r\) as long as the indistinguishability parameters \(\varepsilon_t, \delta_t\) scales with the ratio \(t/r\). The proof of Proposition 4 is deferred to Appendix 9.3.

In particular, if a mechanism has been calibrated for radius \(r\), and one later evaluates substitutions at a larger radius \(t>r\), the same Gaussian release still yields a weaker but valid accounting guarantee, with privacy parameter inflated from \(\varepsilon\) to \(\varepsilon \frac{t}{r}\). Hence, when \(\left\lVert{z}\right\rVert_2 \leq B\) for all records \(z\), combining Proposition 1 with Proposition 4, the Ball-DP privacy guarantee can be converted into standard DP guarantee by setting \(t = 2B\).

4 Ball-ReRo Certificates and Audits↩︎

We now translate the radius-restricted indistinguishability guarantee into reconstruction-robustness statements. The goal is not to define a new attack model, but to make precise what an informed adversary can gain from the released Gaussian-perturbed model beyond its prior information. The section has three parts. First, we state the exact finite-prior MAP audit used in the experiments. Second, we define the Ball-ReRo baseline and show how Ball-DP and Ball-RDP imply reconstruction certificates. Third, we give the direct Gaussian Ball-ReRo bound used as the empirical certificate.

Throughout this section, the adversary knows the public remainder dataset \(D^-\), the training algorithm, the hyperparameters, the Ball-DP policy radius, and the candidate-construction protocol. The hidden record is denoted by \(Z\), the completed dataset is \(D^-\cup\{Z\}\), and the released model is \[\widetilde{\theta} = \widehat\theta(D^-\cup\{Z\})+ \xi, \qquad \xi\sim\mathcal{N}(0,\sigma^2I).\] The audit asks whether \(\widetilde{\theta}\) identifies the hidden record better than what is already possible from the prior and the allowed candidate set.

4.1 Finite-prior MAP audit for Gaussian releases↩︎

We consider a finite candidate set \[S=\{z_1,\dots,z_m\}\subseteq \mathcal{B}_{d}(u,r)\] that contains the hidden target, with prior weights \(\pi_1,\dots,\pi_m>0\) satisfying \(\sum_{i=1}^m\pi_i=1\). This is an adversary-favorable audit: the side information has already reduced the reconstruction problem to choosing among plausible local alternatives. The remaining question is whether the released model identifies which candidate was used as the hidden training record.

For a uniform prior on \(S\), the \(\log\pi_i\) term is constant and the attack reduces to constrained least squares over the candidate set. The proof is deferred to Appendix 11.

4.2 Ball-supported priors and feasible outputs↩︎

A reconstruction certificate must be interpreted relative to the adversary’s side information. In particular, if the audit protocol restricts the reconstructor to a feasible output set, then the oblivious baseline should obey the same restriction. We therefore define the prior support, the allowed-output baseline, and the Ball-ReRo property using the same feasible-output family.

For finite exact-identification audits, the reconstructor is constrained to output one of the candidates in \(S\). With a uniform prior on \(m\) candidates and exact-identification loss, the baseline in Definition 4 is therefore \(\kappa=1/m\). A smaller policy radius may make it harder to construct a large, well-separated feasible set near a given anchor; this is part of the operational trade-off and must be reported explicitly with the audit.

The proof is in Appendix 10.1. Theorem 6 is the radius-restricted analogue of the standard observation that DP limits reconstruction attacks [5]. The important operational term is the baseline \(\kappa\): it is the best success probability achievable without observing the mechanism output, under the same prior and feasible-output restriction as the reconstructor. If the prior and side information already make this baseline large, then a high raw reconstruction rate may mostly reflect the audit setup rather than additional information leaked by the release. The relevant empirical question is therefore how far the observed success probability rises above \(\kappa\).

We next adapt Rényi-DP (RDP) [16] to Ball-DP, which we call Ball-RDP, and state the corresponding Ball-ReRo guarantee.

The Gaussian release mechanism can be adjusted as follows to ensure Ball-RDP.

Lastly, we obtain the following Ball-ReRo guarantee for the Gaussian Ball-RDP mechanism.

The proof of Lemma 1 is in Appendix 10.2, and the proof of Theorem 7 is in Appendix 10.3.

4.3 Gaussian Ball-ReRo bounds↩︎

The preceding theorems apply to Ball-DP and Ball-RDP mechanisms, but they can be loose for Gaussian releases. We therefore use the testing, or blow-up-function, viewpoint on reconstruction robustness [5], [8], [17]. For distributions \(P\) and \(Q\) on the release space and \(\kappa\in[0,1]\), write \[\mathcal{B}_\kappa(P,Q) := \sup\{P(E): E\text{ measurable and }Q(E)\le \kappa\}.\] This quantity asks how large an attack-success event can be under the target-dependent release law if the same event has baseline probability at most \(\kappa\) under a reference release law. In our Gaussian output-perturbation setting, the relevant output laws have equal covariance, so this testing problem has a closed form; Appendix 10.4 proves the Gaussian identity used below. The next results are the certificates plotted in the experiments and should be read as release-level upper bounds under the stated feasible-set prior.

The proof is in Appendix 10.6. The direct bound is the main certificate plotted in the experiments. Under homogeneous Gaussian calibration at fixed \((\varepsilon,\delta)\), the ratio \(\Delta_2(r)/\sigma\) is fixed by the calibration rule, so shrinking \(r\) does not by itself improve the numerical Ball-ReRo bound. The radius still matters because it changes both the protected adjacency scope and the amount of noise needed to reach that certificate. The empirical MAP audit then measures the resulting identification trade-off for the feasible candidate sets that can actually be constructed inside the policy ball. A sharper support-specific Gaussian exact-identification bound is available, but it is not used in the reported experiments; we state it in Appendix 10.7.

5 Experimental Analysis↩︎

5.1 Goals and scope↩︎

The empirical evaluation asks three operational questions. First, at the same target \((\varepsilon,\delta)\), how much accuracy is recovered by calibrating to a declared local radius rather than to the global bounded-replacement radius? Second, for a fixed reconstruction certificate \(\gamma\), how much utility is lost as the protected local neighborhood grows? Third, when an informed adversary is restricted to a finite local candidate set, how do empirical MAP attack rates compare with the oblivious baseline and the theorem-backed certificate?

All reported ERM results use \(\delta=10^{-6}\), \(m=10\), and Gaussian output perturbation. We choose the Ball-DP radius \(r\) through empirical local-radius policies. For each benchmark, \(q50\), \(q80\), and \(q95\) denote the radii obtained from the \(50\)th, \(80\)th, and \(95\)th percentiles of the same-label distance distribution under the label-preserving metric 3 . These three policies represent progressively larger protected neighborhoods; Sections 5.3 and 5.6 describe how they are used in the accuracy and MAP audits. The standard comparator uses the full bounded-replacement radius \(r_{\mathrm{std}}=2B\) for utility experiments and an empirical same-label diameter in the finite-prior attack audit.

5.2 Experimental model↩︎

The seven-dataset utility table and the finite-prior MAP audit use a ridge-prototype classifier on fixed embeddings. This head is the closed-form audit case: its optimizer, sensitivity, and noiseless informed-adversary inverse problem are explicit, which lets us separate privacy calibration from numerical approximation error. The Ball-DP calibration theorem itself is not ridge-specific; Section 6.2 verifies the required \(L_z\) constants for binary logistic regression, softmax logistic regression, and squared-hinge SVMs, and Section 5.5 reports an IMDb utility–certificate sweep for two of these additional heads alongside ridge prototypes.

For record \((z,y)\) with \(z\in\mathbb{R}^d\) and \(y\in\{1,\ldots,C\}\), the ridge-prototype model learns one prototype \(\mu_c\in\mathbb{R}^d\) per class by minimizing \[\label{eq:ridge-proto-objective} F_D(\mu)=\frac{1}{n}\sum_{i=1}^n\|z_i-\mu_{y_i}\|_2^2+\frac{\lambda}{2}\sum_{c=1}^C\|\mu_c\|_2^2.\tag{4}\] Prediction uses the nearest prototype. The full ridge-prototype statements are collected in Section 6, with the core learning proofs in Section 9. In the reported runs \(\lambda=0.01\).

For this model, Corollary 2 gives the count-worst-case exact local sensitivity \[\Delta_{\mathrm{proto}}(r)=\frac{2r}{2+\lambda n}.\] When class counts are public, the count-aware variant is stated separately in Proposition 10. Gaussian output perturbation is then calibrated by substituting the relevant sensitivity into Theorem 3.

5.3 Utility at local policy radii↩︎

Table 1 reports the main utility comparison at \(\varepsilon=2\) across seven embedding benchmarks. It replaces the earlier single-radius noise-ratio table because it answers the operational question directly: what accuracy do stakeholders get when they choose a protected neighborhood? At this privacy level, all tabulated Ball-DP radii improve over the global-radius comparator. Smaller local radii generally yield higher utility, with near ties at the reported precision across several datasets; \(q95\) provides the broadest local protection among the three local policies.

4pt

For text datasets, the fixed embeddings are computed with the all-MiniLM-L6-v2 Sentence Transformers model, which is based on Sentence-BERT and MiniLM [3], [18], [19]. For image datasets, the fixed embeddings are computed with ImageNet-pretrained ResNet-18 features implemented in TorchVision [20]–[22]. The embedding maps are treated as public preprocessing components of the adjacency policy. The benchmark suite consists of AG News [23], BANKING77 [24], CIFAR-10 [25], Emotion [26], IMDb [27], MNIST [28], and TREC-6 [29].

The absolute accuracies should not be read as benchmark-leading numbers: the ridge-prototype head is intentionally simple and can be poorly matched to some fixed embeddings, notably on Emotion and TREC-6. We retain these rows as stress tests for the privacy calibration rather than as claims of competitive task performance.

The gains are not uniform, which is itself useful for deployment planning. At \(q50\), improvements over the standard comparator range from \(0.03\) percentage points on AG News to \(14.00\) points on BANKING77. At \(q80\), the range is \(0.04\)–\(12.37\) points; at \(q95\), it is \(0.03\)–\(11.09\) points. These differences quantify the utility cost of protecting a larger local neighborhood at the same \((\varepsilon,\delta)\).

5.4 Accuracy at a fixed reconstruction certificate↩︎

The most interpretable privacy–utility visualization is accuracy as a function of the certified exact-identification upper bound \(\gamma\) from Corollary 1. A higher point means better utility; a farther-left point means a smaller certified exact-identification risk. Figure 3 shows the regenerated seven-dataset private-ERM accuracy–certificate trade-off from the publication report. The plot uses the finite rows for the direct certificate column and aggregates seed-first before plotting.

The important interpretation is that the radius labels do not denote different certificate values at the same \(\varepsilon\). Under matched Gaussian calibration, \(\gamma\) is determined by \(m\), \(\varepsilon\), and \(\delta\) through \(\Delta_2/\sigma\). The radius instead tells the reader which substitutions are protected and how much utility is retained while achieving that numerical certificate.

5.5 Convex-head comparison on IMDb↩︎

The preceding seven-dataset frontier uses ridge prototypes to keep the exact finite-prior inverse problem explicit. The calibration theorem, however, applies to every convex head for which Assumption 1 is verified. Proposition 12 gives those constants for binary logistic regression, softmax logistic regression, and squared-hinge SVMs. To make this scope visible empirically, Figure 4 repeats the private-ERM utility–certificate sweep on IMDb embeddings at the local radius policy \(q50\) for binary logistic regression, ridge prototypes, and the squared-hinge SVM. This experiment uses five Gaussian release seeds per mechanism and nominal privacy levels \(\varepsilon\in\{8,16,32\}\).

4pt

At every displayed privacy level and for all three convex heads, Ball-DP has higher mean accuracy than the global-radius comparator at the same reported ReRo certificate. The gains are largest at the strongest privacy level, \(\varepsilon=8\): \(4.12\) accuracy points for binary logistic regression, \(2.65\) points for ridge prototypes, and \(4.80\) points for the squared-hinge SVM. As privacy weakens, the gap shrinks: at \(\varepsilon=32\), the corresponding gains are \(0.96\), \(0.53\), and \(1.49\) points. This pattern is consistent with the calibration story: local radius-aware noise matters most when the Gaussian perturbation is large.

The head comparison also shows a utility trade-off that is separate from the privacy certificate. When one can afford high \(\varepsilon\), the secondary convex heads can outperform the ridge prototype: at \(\varepsilon=32\), the squared-hinge SVM reaches the highest mean accuracy in this sweep, \(0.776\) under Ball-DP. However, these higher-utility heads are also more sensitive to stronger privacy in the reported experiment. From \(\varepsilon=32\) to \(\varepsilon=8\), Ball-DP accuracy drops by \(3.68\) points for binary logistic regression and \(5.54\) points for the squared-hinge SVM, compared with \(2.00\) points for the ridge prototype. Thus the secondary heads can be attractive in the high-utility, weak-privacy regime, while the ridge prototype remains a stable closed-form audit head for the main seven-dataset reconstruction study.

5.6 Finite-prior reconstruction diagnostics↩︎

This diagnostic is not a new privacy definition; it is an attack audit for a concrete finite candidate support. The prior on that support is part of the attack specification. In the reported audit we use the uniform prior over \(m=10\) candidates, so the oblivious exact-identification baseline is exactly \(1/m=0.1\) and comparisons are not confounded by prior imbalance. Proposition 5 also covers non-uniform initial priors: changing the prior adds the term \(\log \pi_i\) to the MAP score and changes the exact-identification baseline to \(\max_i \pi_i\). Such priors are useful for deployment-specific stress tests, but the aggregate table below uses the uniform prior throughout.

Within this uniform-prior protocol, the radius-grid audit varies \(\varepsilon\in\{2,4,8\}\) and the Ball-DP radius policy in \(\{q50,q80,q95\}\), while evaluating the Standard-DP comparator on the same radius-\(q80\) feasible-set protocol. For each setup seed, we construct four public-only same-label feasible supports inside the policy ball. Each support has size \(m=10\) and is chosen by a farthest-point procedure to stress-test identification among well-separated feasible candidates. We then cycle through the support: for each candidate \(z_i\in S\), we treat \(z_i\) once as the hidden target, release a Gaussian-perturbed ridge-prototype model trained on \(D^-\cup\{z_i\}\), and run the exact MAP rule of Proposition 5. Thus each setup seed contributes \(4\times 10=40\) raw release-and-attack trials, and the ten setup seeds give \(400\) raw trials per dataset and mechanism. The reported uncertainty is computed seed-first: raw trials are first averaged within each setup seed, and the displayed confidence intervals are then computed across the ten setup-seed averages. The standard mechanism in this audit uses the empirical same-label diameter and count-aware ridge calibration.

The radius-grid audit in Figure 5 and Table 3 should not be read as saying that Ball-DP and the standard comparator protect the same adjacency relation. They do not. Ball-DP uses less noise because it protects the declared local ball, whereas the standard comparator uses the global replacement radius. The empirical exact-ID rate therefore need not be lower for Ball-DP and can be higher depending on the sampled feasible-set geometry. The ReRo reference line gives the corresponding direct Gaussian worst-case certificate \[\gamma_{\mathrm{rel}} = \Phi\!\left(\Phi^{-1}(1/m)+\Delta/\sigma\right),\] with the calibration values reported in Table 4. Across the reruns shown here, the empirical success probabilities remain below the certificate lines while staying interpretable relative to the chance baseline \(1/m\).

6 Technical Statements for the Experiments↩︎

This section records the model-specific facts used by the experimental section. The statements serve two purposes: they specify the Gaussian sensitivity calibration for the ridge-prototype head, and they show how the generic Ball-DP theorem extends to the additional convex heads used in the IMDb comparison. Proofs are deferred to the appendices.

6.1 Ridge-prototype head↩︎

The ridge-prototype head is the closed-form audit case. Its optimizer, sensitivity, and informed-adversary inverse problem are explicit, so it supports exact MAP reconstruction diagnostics without numerical approximation error. The statements below are therefore the ridge-specific instantiation of the general convex-ERM theory, not the full scope of the method.

Corollary 2 is count-worst-case: it allows the changed record to be the only record in its class. If class counts are public, or are fixed component metadata of the label-preserving adjacency graph, the calibration can instead use the smallest nonzero public class count.

The maximum is attained by a class with count \(n_{\min}\), since one changed record moves rare-class prototypes the most. Because \(n_{\min}\ge1\), the count-aware calibration is never looser than the count-worst-case bound \(2r/(2+\lambda n)\), and it is strictly tighter whenever \(n_{\min}>1\).

The only label-identification obstruction is the degenerate event in which the missing example equals the \(D^-\)-implied prototype of its own class. In that case, adding the missing record does not move the corresponding released prototype.

Thus, for a uniform finite prior with common known label \(y\), the exact MAP attack is nearest-neighbor decoding of \(W_y\) over the candidate support.

6.2 Logistic and SVM heads↩︎

The same ERM sensitivity theorem applies to the additional convex heads used in the experiments once Assumption 1 is verified for each model. For the main text, we record only the resulting constants needed for the Ball-DP calibration; the proof of Proposition 12 is deferred to Appendix 12.

Throughout this subsection we use the label-preserving metric, assume \(\|z\|_2\le B\), and write \[\widetilde{B}:=\sqrt{B^2+1}\] for the augmented feature norm.

7 Related Work↩︎

Adjacency design beyond the global worst case.  The choice of adjacency is central to the meaning of DP [14]. Metric formulations such as \(d_X\)-privacy and later work on metric DP replace the uniform adjacency graph by guarantees that depend on a record metric, especially in location and embedding domains [10], [11]. Ball-DP is simpler and more policy-oriented: it keeps the standard \((\varepsilon,\delta)\) semantics unchanged and restricts the protected substitutions to a declared radius-\(r\) neighborhood.

Private convex ERM and output perturbation.  Private ERM under convexity has a long history, including output- and objective-perturbation methods [7]. In the Gaussian output-perturbation regime, analytic calibration improves over the classical tail-bound formula [15]. Our generic ERM sensitivity theorem is the local counterpart of the usual output-perturbation analysis. Ridge prototypes give an exact equality rather than only an upper bound, while the binary-logistic, softmax-logistic, and squared-hinge SVM constants show how the same local-calibration argument extends to common convex linear heads.

Reconstruction attacks and reconstruction robustness.  Balle, Cherubin, and Hayes formalized the informed-adversary reconstruction setting and showed that convex models can admit exact or near-exact inversion from noiseless releases [5]. Hayes, Mahloujifar, and Balle derived reconstruction bounds and matching attacks for DP-SGD [8]. The hypothesis-testing view of privacy, developed in the \(f\)-DP line of work, provides a natural route from privacy guarantees to attack bounds [30]. Kaissis et al. used this perspective to derive direct reconstruction bounds for Gaussian and subsampled mechanisms [17]. Our Gaussian Ball-ReRo result is the local, radius-thresholded analogue of that direct Gaussian testing argument.

Prototype-based private learning.  Prototype representations are common in classical nearest-centroid classifiers and modern embedding-based learning [31]. Recent private learning work has also explored prototype releases in transfer-learning settings [32]. Our use of prototypes is different: the model is chosen as the closed-form audit case because its convex structure yields exact local sensitivity and an exact informed-adversary audit. The broader convex-head contribution is captured by the generic ERM theorem and the explicit logistic/SVM constants.

8 Summary and Future Directions↩︎

This paper introduced Ball-DP, a radius-restricted adjacency relation that makes the locality of a privacy guarantee an explicit, auditable policy choice rather than an implicit byproduct of noise tuning. The standard \((\varepsilon, \delta)\)-indistinguishability semantics are preserved within the declared neighborhood; only the scope of the guarantee changes. For strongly convex ERM, we showed that sensitivity under \(r\)-adjacency scales linearly with \(r\), giving a direct route to recalibrated Gaussian output perturbation. The theorem is instantiated for ridge prototypes, binary logistic regression, softmax logistic regression, and squared-hinge SVMs through explicit record-Lipschitz constants. For ridge-regularized prototype classifiers, the sensitivity, the noiseless informed-adversary inversion, and the finite-prior Gaussian MAP attack are all exact, allowing privacy calibration and reconstruction auditing to be studied without confounding approximation error.

The experiments show that this local calibration recovers meaningful accuracy, while empirical exact-identification rates remain below the theorem-backed Ball-ReRo certificates. The additional IMDb convex-head sweep shows the same utility–certificate pattern for binary logistic and squared-hinge SVM heads, supporting the claim that the method is a convex-ERM calibration principle rather than a prototype-only construction. The current analysis is, however, confined to convex, one-shot Gaussian releases with public calibration metadata; it does not address label-changing substitutions, transcript-level releases from private SGD, or nonconvex representation-learning pipelines. Extending the Ball-DP accounting to these settings, particularly multi-step DP-SGD transcripts where sensitivity no longer admits a closed form, is the main direction for future work.

Ethics considerations↩︎

This paper studies privacy guarantees and reconstruction attacks for machine-learning models trained on potentially sensitive data. The experiments use fixed embedding representations and theorem-aligned attack protocols whose purpose is to audit privacy leakage under controlled assumptions, not to facilitate unauthorized extraction of personal data from deployed systems. Empirical attack evaluations should be run only on datasets for which the researchers have authorization, and released artifacts should omit raw private records. No human-subject intervention is involved in the analysis reported here. The experiments evaluate candidate identification in embedding space rather than recovered raw images or text.

9 Proofs for Main Results↩︎

9.1 Proof of Proposition 1↩︎

9.2 Proof of Theorem 2↩︎

We first state a generic optimizer-perturbation bound that does not depend on the metric or on any Lipschitz-in-sample assumption.

9.3 Proof of Proposition 4↩︎

9.4 Proofs for the Ridge-Prototype Model↩︎

9.4.1 Proof of Theorem 9↩︎

9.4.2 Proof of Corollary 2↩︎

9.4.3 Proof of Proposition 10↩︎

9.4.4 Proof of Theorem 11↩︎

9.4.5 Proof of Corollary 3↩︎

10 Proofs for Ball-ReRo↩︎

10.1 Proof of Theorem 6↩︎

10.2 Proof of Lemma 1↩︎

10.3 Proof of Theorem 7↩︎

10.4 A Gaussian testing lemma↩︎

10.5 Proof of Theorem 8↩︎

10.6 Proof of Corollary 1↩︎

10.7 Support-specific finite-Gaussian exact-identification bound↩︎

The following bound is a sharper finite-prior statement for equal-covariance Gaussian releases. It is useful as a technical comparison point, but it is not the quantity plotted in the experiments; the main text uses the simpler direct certificate from Corollary 1.

11 Proof of Proposition 5↩︎

12 Derivations for Secondary Convex Head Constants↩︎

12.1 Squared Hinge↩︎

Fix a label \(y\in\{-1,1\}\) and a parameter vector \(w\in\mathbb{R}^d\). For a feature vector \(z\), define \[q(z):=1-yw^\top z, \qquad h(z):=q(z)_+=\max\{0,q(z)\}.\] The squared-hinge loss is \[\ell(w;z,y)=h(z)^2.\] The scalar map \(u\mapsto (u_+)^2\) is differentiable everywhere: its derivative is \(0\) for \(u<0\), is \(2u\) for \(u>0\), and is also \(0\) at \(u=0\) because the one-sided derivatives both equal \(0\). Hence, by the chain rule, \[\nabla_w\ell(w;z,y) =2h(z)\nabla_w(1-yw^\top z) =2h(z)(-yz) =-2yzh(z).\] Write \[g(z):=\nabla_w\ell(w;z,y)=-2yzh(z).\] We first bound the scalar hinge difference. The map \(m(a):=a_+=\max\{0,a\}\) is \(1\)-Lipschitz on \(\mathbb{R}\). Indeed, if \(a,b\le0\), then \(m(a)=m(b)=0\); if \(a,b\ge0\), then \(|m(a)-m(b)|=|a-b|\); and if \(a\ge0\ge b\), then \(|m(a)-m(b)|=a\le a-b=|a-b|\), with the remaining mixed case symmetric. Therefore, \[\begin{align} |h(z)-h(z')| &\le |q(z)-q(z')| \\ &= |(1-yw^\top z)-(1-yw^\top z')| \\ &= |yw^\top(z'-z)| \\ &= |w^\top(z'-z)| \\ &\le \|w\|_2\,\|z'-z\|_2 =\|w\|_2\,\|z-z'\|_2 . \end{align}\] Next, for any admissible feature vector \(u\) with \(\|u\|_2\le B\), \[\begin{align} h(u) &=\max\{0,1-yw^\top u\} \\ &\le 1+|w^\top u| \\ &\le 1+\|w\|_2\|u\|_2 \\ &\le 1+B\|w\|_2 . \end{align}\] In particular, \(h(z')\le1+B\|w\|_2\).

Now subtract the gradients and add and subtract \(zh(z')\): \[\begin{align} g(z)-g(z') &=-2yzh(z)+2yz'h(z') \\ &=-2y\bigl(zh(z)-z'h(z')\bigr) \\ &=-2y\bigl(z(h(z)-h(z'))+(z-z')h(z')\bigr). \end{align}\] Taking Euclidean norms and using \(|y|=1\) gives \[\begin{align} \|g(z)-g(z')\|_2 &\le 2\Bigl(\|z\|_2|h(z)-h(z')|+\|z-z'\|_2|h(z')|\Bigr) \\ &\le 2\Bigl(B\|w\|_2\|z-z'\|_2+(1+B\|w\|_2)\|z-z'\|_2\Bigr) \\ &=\bigl(2+4B\|w\|_2\bigr)\|z-z'\|_2 . \end{align}\] Thus, on \(\Theta_R=\{w:\|w\|_2\le R\}\), \[\|\nabla_w\ell(w;z,y)-\nabla_w\ell(w;z',y)\|_2 \le (2+4BR)\|z-z'\|_2,\] so \(L_z(R)=2+4BR\) is valid.

It remains to bound the radius of ERM minimizers. Let \[F_D(w)=\frac{1}{n}\sum_{i=1}^n \max\{0,1-y_iw^\top z_i\}^2+\frac{\lambda}{2}\|w\|_2^2,\] and let \(w^\star\in\arg\min_w F_D(w)\). Since \(w^\star\) minimizes \(F_D\), \[F_D(w^\star)\le F_D(0).\] At \(w=0\), every hinge value is \(\max\{0,1\}=1\), so \[F_D(0)=\frac{1}{n}\sum_{i=1}^n1^2+\frac{\lambda}{2}\|0\|_2^2=1.\] The empirical squared-hinge term is nonnegative, hence \[F_D(w^\star) =\frac{1}{n}\sum_{i=1}^n \max\{0,1-y_i(w^\star)^\top z_i\}^2 +\frac{\lambda}{2}\|w^\star\|_2^2 \ge \frac{\lambda}{2}\|w^\star\|_2^2.\] Combining the last three displays, \[\frac{\lambda}{2}\|w^\star\|_2^2\le F_D(w^\star)\le F_D(0)=1,\] so \[\|w^\star\|_2\le \sqrt{\frac{2}{\lambda}}.\] Substituting \(R=\sqrt{2/\lambda}\) into \(L_z(R)=2+4BR\) gives the ERM-minimizer constant \[L_z\le 2+4B\sqrt{\frac{2}{\lambda}}.\]

12.2 Binary Logistic↩︎

Let \(y\in\{-1,1\}\), let \[\widetilde{z}:=\begin{pmatrix}z\\1\end{pmatrix}\in\mathbb{R}^{d+1}, \qquad \widetilde{\theta}:=\begin{pmatrix}w\\b\end{pmatrix}\in\mathbb{R}^{d+1}, \qquad \widetilde{B}:=\sqrt{B^2+1}.\] Then \(\|\widetilde{z}\|_2\le \widetilde{B}\), and for same-label pairs, \[\|\widetilde{z}-\widetilde{z}'\|_2 = \left\|\begin{pmatrix}z-z'\\0\end{pmatrix}\right\|_2 =\|z-z'\|_2.\] Define the score \(s(\widetilde{z}):=\widetilde{\theta}^\top\widetilde{z}\) and the sigmoid \(\sigma(u):=(1+e^{-u})^{-1}\). The binary logistic loss is \[\ell(\widetilde{\theta};\widetilde{z},y)=\log\bigl(1+\exp(-ys(\widetilde{z}))\bigr).\] With \(u=-ys(\widetilde{z})\), we have \[\frac{d}{du}\log(1+e^u)=\frac{e^u}{1+e^u}=\sigma(u), \qquad \nabla_{\widetilde{\theta}}u=-y\widetilde{z}.\] Therefore, \[\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta};\widetilde{z},y) =-y\sigma(-y\widetilde{\theta}^\top\widetilde{z})\widetilde{z}.\] For two same-label examples, set \[\alpha:=\sigma(-y\widetilde{\theta}^\top\widetilde{z}), \qquad \beta:=\sigma(-y\widetilde{\theta}^\top\widetilde{z}').\] Since \(0\le\sigma\le1\), \(0\le\alpha,\beta\le1\). The gradient difference satisfies \[\begin{align} &\left\|\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta};\widetilde{z},y) -\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta};\widetilde{z}',y)\right\|_2 \\ &\qquad =\left\|-y\alpha\widetilde{z}+y\beta\widetilde{z}'\right\|_2 \\ &\qquad =\left\|-\alpha\widetilde{z}+\beta\widetilde{z}'\right\|_2 . \end{align}\] Add and subtract \(\alpha\widetilde{z}'\): \[-\alpha\widetilde{z}+\beta\widetilde{z}' =\alpha(\widetilde{z}'-\widetilde{z})+(\beta-\alpha)\widetilde{z}'.\] Thus, \[\begin{align} \left\|-\alpha\widetilde{z}+\beta\widetilde{z}'\right\|_2 &\le |\alpha|\,\|\widetilde{z}'-\widetilde{z}\|_2 +|\beta-\alpha|\,\|\widetilde{z}'\|_2 \\ &\le \|z-z'\|_2+\widetilde{B}|\beta-\alpha|. \end{align}\] The sigmoid derivative is \[\sigma'(u)=\sigma(u)(1-\sigma(u)).\] For \(t\in[0,1]\), \[t(1-t)=\frac{1}{4}-\left(t-\frac{1}{2}\right)^2\le\frac{1}{4},\] so \(0\le\sigma'(u)\le1/4\) and \(\sigma\) is \(1/4\)-Lipschitz. Therefore, \[\begin{align} |\beta-\alpha| &\le \frac{1}{4}\left| -y\widetilde{\theta}^\top\widetilde{z}' + y\widetilde{\theta}^\top\widetilde{z}\right| \\ &=\frac{1}{4}\left|\widetilde{\theta}^\top(\widetilde{z}-\widetilde{z}')\right| \\ &\le \frac{1}{4}\|\widetilde{\theta}\|_2\,\|\widetilde{z}-\widetilde{z}'\|_2 \\ &=\frac{1}{4}\|\widetilde{\theta}\|_2\,\|z-z'\|_2 . \end{align}\] Substituting this into the gradient-difference bound gives \[\left\|\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta};\widetilde{z},y) -\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta};\widetilde{z}',y)\right\|_2 \le \left(1+\frac{\widetilde{B}\|\widetilde{\theta}\|_2}{4}\right)\|z-z'\|_2.\] Hence, on \(\Theta_R=\{\widetilde{\theta}:\|\widetilde{\theta}\|_2\le R\}\), \[L_z(R)=1+\frac{\widetilde{B} R}{4}\] is valid.

Now consider the regularized objective, with both weights and intercept regularized, \[F_D(\widetilde{\theta}) =\frac{1}{n}\sum_{i=1}^n \ell(\widetilde{\theta};\widetilde{z}_i,y_i) +\frac{\lambda}{2}\|\widetilde{\theta}\|_2^2.\] Let \(\widetilde{\theta}^\star\) be an ERM minimizer. First-order optimality gives \[0=\nabla F_D(\widetilde{\theta}^\star) =\frac{1}{n}\sum_{i=1}^n \nabla_{\widetilde{\theta}}\ell(\widetilde{\theta}^\star;\widetilde{z}_i,y_i) +\lambda\widetilde{\theta}^\star,\] so \[\lambda\widetilde{\theta}^\star =-\frac{1}{n}\sum_{i=1}^n \nabla_{\widetilde{\theta}}\ell(\widetilde{\theta}^\star;\widetilde{z}_i,y_i).\] Taking norms and using the triangle inequality, \[\begin{align} \lambda\|\widetilde{\theta}^\star\|_2 &\le \frac{1}{n}\sum_{i=1}^n \left\|\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta}^\star;\widetilde{z}_i,y_i)\right\|_2. \end{align}\] For each example, \[\begin{align} \left\|\nabla_{\widetilde{\theta}}\ell(\widetilde{\theta}^\star;\widetilde{z}_i,y_i)\right\|_2 &=\left\|-y_i\sigma(-y_i(\widetilde{\theta}^\star)^\top\widetilde{z}_i)\widetilde{z}_i\right\|_2 \\ &\le |y_i|\cdot 1\cdot\|\widetilde{z}_i\|_2 \\ &\le \widetilde{B}. \end{align}\] Therefore, \[\lambda\|\widetilde{\theta}^\star\|_2 \le \frac{1}{n}\sum_{i=1}^n\widetilde{B} =\widetilde{B},\] and hence \[\|\widetilde{\theta}^\star\|_2\le\frac{\widetilde{B}}{\lambda}.\] Substituting \(R=\widetilde{B}/\lambda\) into the fixed-parameter constant gives \[L_z\le 1+\frac{\widetilde{B}}{4}\cdot\frac{\widetilde{B}}{\lambda} =1+\frac{\widetilde{B}^2}{4\lambda} =1+\frac{B^2+1}{4\lambda}.\]

12.3 Softmax Logistic↩︎

Let \(y\in\{1,\ldots,K\}\), let \(\widetilde{z}=(z,1)\in\mathbb{R}^{d+1}\), and let \(\widetilde{W}\in\mathbb{R}^{K\times(d+1)}\). Define \[p(\widetilde{z}):=\mathop{\mathrm{softmax}}(\widetilde{W}\widetilde{z}), \qquad a(\widetilde{z}):=p(\widetilde{z})-e_y,\] where \(e_y\) is the \(y\)th standard basis vector in \(\mathbb{R}^K\). For scores \(s:=\widetilde{W}\widetilde{z}\), the softmax loss is \[\ell(\widetilde{W};\widetilde{z},y) =-s_y+\log\left(\sum_{c=1}^K e^{s_c}\right).\] For each class \(c\), \[\frac{\partial \ell}{\partial s_c} =-\mathbf{1}\{c=y\}+\frac{e^{s_c}}{\sum_{j=1}^K e^{s_j}} =p_c(\widetilde{z})-(e_y)_c.\] Thus \(\nabla_s\ell=p(\widetilde{z})-e_y=a(\widetilde{z})\). Since \(s_c=\widetilde{w}_c^\top\widetilde{z}\) for the \(c\)th row \(\widetilde{w}_c^\top\) of \(\widetilde{W}\), the row-wise chain rule gives \[\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z},y) =a(\widetilde{z})\widetilde{z}^\top.\] For a same-label pair, write \[a:=a(\widetilde{z}), \qquad a':=a(\widetilde{z}').\] Subtract the gradients and add and subtract \(a(\widetilde{z}')^\top\): \[\begin{align} &\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z},y) -\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z}',y) \\ &\qquad = a\widetilde{z}^\top-a'(\widetilde{z}')^\top \\ &\qquad = a(\widetilde{z}-\widetilde{z}')^\top+(a-a')(\widetilde{z}')^\top. \end{align}\] Taking Frobenius norms and using the triangle inequality, \[\begin{align} &\left\|\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z},y) -\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z}',y)\right\|_F \\ &\qquad\le \left\|a(\widetilde{z}-\widetilde{z}')^\top\right\|_F + \left\|(a-a')(\widetilde{z}')^\top\right\|_F. \end{align}\] For vectors \(u,v\), \(\|uv^\top\|_F=\|u\|_2\|v\|_2\), so \[\begin{align} \label{eq:softmax-gradient-split} &\left\|\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z},y) -\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z}',y)\right\|_F \\ &\qquad\le \|a\|_2\,\|\widetilde{z}-\widetilde{z}'\|_2 + \|a-a'\|_2\,\|\widetilde{z}'\|_2 . \notag \end{align}\tag{6}\] We bound the two factors separately.

First, since \(p(\widetilde{z})\) is a probability vector, \[\begin{align} \|a\|_2^2 &=\|p(\widetilde{z})-e_y\|_2^2 \\ &=(1-p_y(\widetilde{z}))^2+ \sum_{c\ne y}p_c(\widetilde{z})^2 \\ &\le (1-p_y(\widetilde{z}))^2+ \left(\sum_{c\ne y}p_c(\widetilde{z})\right)^2 \\ &=(1-p_y(\widetilde{z}))^2+(1-p_y(\widetilde{z}))^2 \\ &\le 2. \end{align}\] Thus \(\|a\|_2\le\sqrt2\).

Second, because \(a-a'=p(\widetilde{z})-p(\widetilde{z}')\), we need a Lipschitz bound for softmax. For \(p=\mathop{\mathrm{softmax}}(x)\), the Jacobian is \[J(x)=\operatorname{Diag}(p)-pp^\top.\] It is symmetric. In row \(i\), \[\begin{align} \sum_{j=1}^K |J_{ij}(x)| &=p_i(1-p_i)+\sum_{j\ne i}p_ip_j \\ &=p_i(1-p_i)+p_i\sum_{j\ne i}p_j \\ &=2p_i(1-p_i) \\ &\le \frac{1}{2}. \end{align}\] Therefore \(\|J(x)\|_\infty\le1/2\). Since \(J(x)\) is symmetric, \(\|J(x)\|_2\le\|J(x)\|_\infty\le1/2\). Applying the mean-value theorem to \(x\mapsto\mathop{\mathrm{softmax}}(x)\) along the segment between \(\widetilde{W}\widetilde{z}\) and \(\widetilde{W}\widetilde{z}'\) gives \[\begin{align} \|p(\widetilde{z})-p(\widetilde{z}')\|_2 &\le \frac{1}{2}\|\widetilde{W}\widetilde{z}-\widetilde{W}\widetilde{z}'\|_2 \\ &=\frac{1}{2}\|\widetilde{W}(\widetilde{z}-\widetilde{z}')\|_2 \\ &\le \frac{1}{2}\|\widetilde{W}\|_F\,\|\widetilde{z}-\widetilde{z}'\|_2. \end{align}\] Hence \[\|a-a'\|_2\le \frac{1}{2}\|\widetilde{W}\|_F\,\|\widetilde{z}-\widetilde{z}'\|_2.\] Since \(\|\widetilde{z}'\|_2\le\widetilde{B}\) and \(\|\widetilde{z}-\widetilde{z}'\|_2=\|z-z'\|_2\), substituting the two bounds into 6 yields \[\begin{align} &\left\|\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z},y) -\nabla_{\widetilde{W}}\ell(\widetilde{W};\widetilde{z}',y)\right\|_F \\ &\qquad\le \left(\sqrt2+\frac{\widetilde{B}\|\widetilde{W}\|_F}{2}\right)\|z-z'\|_2. \end{align}\] Therefore, on \(\Theta_R=\{\widetilde{W}:\|\widetilde{W}\|_F\le R\}\), \[L_z(R)=\sqrt2+\frac{\widetilde{B} R}{2}\] is valid.

It remains to bound the Frobenius norm of regularized ERM minimizers. Let \[F_D(\widetilde{W}) =\frac{1}{n}\sum_{i=1}^n\ell(\widetilde{W};\widetilde{z}_i,y_i) +\frac{\lambda}{2}\|\widetilde{W}\|_F^2,\] and let \(\widetilde{W}^\star\) minimize this objective. First-order optimality gives \[0=\frac{1}{n}\sum_{i=1}^n \nabla_{\widetilde{W}}\ell(\widetilde{W}^\star;\widetilde{z}_i,y_i) +\lambda\widetilde{W}^\star,\] so \[\lambda\widetilde{W}^\star =-\frac{1}{n}\sum_{i=1}^n \nabla_{\widetilde{W}}\ell(\widetilde{W}^\star;\widetilde{z}_i,y_i).\] Taking Frobenius norms and applying the triangle inequality, \[\lambda\|\widetilde{W}^\star\|_F \le \frac{1}{n}\sum_{i=1}^n \left\|\nabla_{\widetilde{W}}\ell(\widetilde{W}^\star;\widetilde{z}_i,y_i)\right\|_F.\] For one example, define \(p_\star(\widetilde{z}_i):=\mathop{\mathrm{softmax}}(\widetilde{W}^\star\widetilde{z}_i)\). Then \[\nabla_{\widetilde{W}}\ell(\widetilde{W}^\star;\widetilde{z}_i,y_i) =\bigl(p_\star(\widetilde{z}_i)-e_{y_i}\bigr)\widetilde{z}_i^\top,\] and hence, by the same probability-vector bound used above, \[\left\|\nabla_{\widetilde{W}}\ell(\widetilde{W}^\star;\widetilde{z}_i,y_i)\right\|_F =\|p_\star(\widetilde{z}_i)-e_{y_i}\|_2\,\|\widetilde{z}_i\|_2 \le \sqrt2\,\widetilde{B}.\] Therefore, \[\lambda\|\widetilde{W}^\star\|_F \le \frac{1}{n}\sum_{i=1}^n\sqrt2\,\widetilde{B} =\sqrt2\,\widetilde{B},\] so every ERM minimizer satisfies \[\|\widetilde{W}^\star\|_F\le\frac{\sqrt2\,\widetilde{B}}{\lambda}.\] Substituting \(R=\sqrt2\,\widetilde{B}/\lambda\) into the bounded-parameter constant gives \[\begin{align} L_z &\le \sqrt2+\frac{\widetilde{B}}{2}\cdot\frac{\sqrt2\,\widetilde{B}}{\lambda} \\ &=\sqrt2\left(1+\frac{\widetilde{B}^2}{2\lambda}\right) \\ &=\sqrt2\left(1+\frac{B^2+1}{2\lambda}\right). \end{align}\]

References↩︎