Generalised Eigenvalue Geometry of Semantic Adversarial Attacks

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Generalised Eigenvalue Geometry of Semantic Adversarial Attacks

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Generalised Eigenvalue Geometry of Semantic Adversarial Attacks∗

arXiv:2606.19212v1 [stat.ML] 17 Jun 2026

Martin Anthony1,2

Kaveh Salehzadeh Nobari1,3

Abstract Recent empirical work shows that semantically equivalent paraphrases can systematically fool financial sentiment classifiers: the paraphrased input remains close to the original under a strong reference embedding model, yet shifts the target model’s representation far enough to flip the predicted class. Existing theoretical accounts of adversarial robustness are either restricted to single-model threat models or remain at the level of empirical algorithms. This paper develops a continuous local model of semantic paraphrase perturbations that captures the two-model structure, and shows that the worst-case local displacement of the target representation under a proxy budget is governed by the top generalised eigenvalue of a matrix pencil (A, B) formed from the Jacobians of the two embedders. The resulting attackability index λ∗ (x) is intrinsic to the chosen local paraphrase geometry and the two embedding maps, yields a closed-form prediction-flip condition for a fixed affine readout, and leads to conservative population and finite-sample attackability certificates. For uniform control across classes of affine readouts, we prove a distributionfree VC bound for the binary attackability indicator class and a scale-sensitive margin bound for an attackability-adjusted margin that subtracts a local geometric penalty from the ordinary classifier margin. A separate section bridges the continuous theory to the discrete paraphrase searches used in practice, identifying an asymmetry between success and failure of finite search and giving a covering condition under which the two settings agree. Finally, we outline an empirical verification strategy based on soft-token relaxations of one-hot token representations and finite sets of generated paraphrases, showing how the local eigenvalue geometry, prediction-flip condition, and finite-search approximation can be assessed on a deployed financial-text classifier.

Introduction

Adversarial attacks on machine learning models have been studied extensively in both computer vision and natural language processing. A large body of work has shown that small ∗1

Data Science Institute, London School of Economics and Political Science. Department of Mathematics, London School of Economics and Political Science. 3 The Inclusion Initiative, London School of Economics and Political Science. 2

input perturbations can cause otherwise accurate classifiers to produce confidently wrong predictions, demonstrated empirically in computer vision (Szegedy et al., 2014; Goodfellow et al., 2015) and analysed theoretically through the lens of robust optimisation (Madry et al., 2018; Tsipras et al., 2019). In natural language processing, the analogue is more delicate: text is discrete, and meaningful perturbations cannot be defined by an ℓp norm. Adversarial examples are instead constructed by word substitutions or paraphrases that preserve meaning while altering a classifier’s prediction (Alzantot et al., 2018; Jin et al., 2020). Recent empirical work in financial NLP has shown that this vulnerability is systematic: semantically equivalent paraphrases can reliably fool deployed sentiment classifiers while remaining close to the original input under a strong reference embedding model (Can Türetken and Leippold, 2026). The empirical evidence reveals a structural asymmetry. The paraphrase preserves meaning, as judged by a strong reference (or proxy) embedding model, yet displaces the representation produced by the deployed (or target) classifier far enough to cross the decision boundary. The adversary, in effect, exploits a disagreement between two models about how perturbations affect meaning. This paper asks what theoretical structure governs that disagreement. We take a different route from the prevailing empirical and algorithmic literature on adversarial attacks. Rather than proposing a new attack method, we study the local geometry of semantic paraphrase perturbations under a two-embedding threat model, in which a proxy embedding defines the adversary’s semantic budget, say η, and a target embedding determines the classifier’s response. Modelling paraphrases through a continuous local parameter u – motivated by the continuous relaxations that underpin gradient-based text attacks such as the GBDA framework of Guo et al. (2021), which in turn build on the Gumbel–softmax reparameterisation of Jang et al. (2017) – we show that the worst-case local displacement of the target representation under a proxy budget admits a closed-form characterisation as a generalised Rayleigh quotient. Its optimal value is the leading generalised eigenvalue of a matrix pencil (A, B) formed from the Jacobians of the two embedders at x. We refer to this leading eigenvalue λ∗ (x) as the local attackability index : a scalar diagnostic, intrinsic to the input and the two embedders, that quantifies the adversary’s leverage at x. From this characterisation, we derive a closed-form condition for prediction flips in the linearised local problem, and we show that the worst-case classifier-direction displacement is dominated by λ∗ (x). We then lift the analysis to the population level for a fixed affine readp out. Defining an attackability-adjusted margin Zw (x) := γw (x)/ Σw (x), where γw (x) is the geometric margin of the readout at x and Σw (x) measures the squared target displacement along the readout direction per unit proxy budget, we characterise the population attackability Aw (η) := P[Zw (x) < η] as a left-limit distribution function of Zw . A finite-sample concentration result follows from the Dvoretzky–Kiefer–Wolfowitz inequality. We also give uniform versions over data-dependent affine readout classes, using VC, fat-shattering, and Rademacher-complexity arguments in the spirit of classical margin theory, while keeping the

new geometric ingredient in the adjusted margin. The closest body of theoretical work to ours concerns the transferability of adversarial attacks across models. Papernot et al. (2016) and Demontis et al. (2019) examine when attacks crafted against a surrogate model remain effective against a different target, and Tramèr et al. (2018) studies ensemble adversarial training as a defence. Our setting is structurally different. We do not ask whether a single perturbation transfers across two trained classifiers, but rather how the local geometries of two embedding maps interact to determine semantic vulnerability under a shared paraphrase budget. Where Demontis et al. (2019) characterise transferability through a first-order cosine-alignment criterion between surrogate and target gradients, our local attackability index is characterised through the spectrum of the matrix pencil (A, B), with the leading generalised eigenvalue playing the role of a worst-case displacement quantity and the full spectrum recording relative anisotropy between the target and proxy geometries. Our use of local geometry is distinct from manifold-based decompositions of adversarial risk. Zhang et al. (2022) assume that data lie on a smooth manifold embedded in the ambient input space and decompose adversarial risk into tangential and normal components. By contrast, we keep the text space discrete and introduce only a local continuous relaxation of paraphrase directions. The central object in our analysis is therefore not the tangent–normal splitting of a data manifold, but the relative pullback geometry of two embedding maps, captured by the generalised eigenvalue spectrum of the pencil (A, B). Finally, we add an empirical verification exercise in the same financial-text setting that motivates the paper. We use the Financial PhraseBank of Malo et al. (2014) because it provides labelled economic and financial sentences on which financial sentiment classifiers are commonly evaluated. We take FinBERT (Araci, 2019) as the target model, treating its final classification head as the fixed affine readout in our theory, and use Sentence-BERT (Reimers and Gurevych, 2019) as the proxy embedding model that defines semantic closeness. The exercise assesses whether the local continuous perturbation geometry, the readout-specific eigenvalue flip condition, and the finite-search approximation predict observed vulnerability to semantically constrained paraphrases. Since the FinBERT readout is fixed rather than selected from the evaluation sample, the empirical analysis is tied primarily to the fixedreadout attackability and adjusted-margin quantities; the VC, fat-shattering and Rademacher bounds provide the corresponding uniform extensions for data-dependent readout classes. The contributions of the paper are as follows. We introduce a continuous local model of semantic paraphrase perturbations and a closed-form characterisation of worst-case local displacement as a generalised Rayleigh quotient (Section 2.1). We establish a linearised margin condition for prediction flips under semantic constraints, together with a conservative worst-direction no-flip certificate (Section 3). We lift the analysis to the population level for a fixed affine readout, giving a margin-tail attackability bound and a finite-sample concentration result for the empirical attackability curve (Section 4). We then give uniform versions

over data-dependent affine readout and margin classes (Sections 5 and 6), including both dimension-dependent covering bounds and a trace-sensitive Rademacher bound, and relate the idealised local adversary to finite paraphrase search through a covering-radius condition on the generated candidates (Section 7). Finally, we provide an empirical verification exercise in financial sentiment classification, using a fixed FinBERT affine readout, a Sentence-BERT proxy embedding, and labelled Financial PhraseBank sentences to assess the local eigenvalue geometry, the readout-specific flip condition, and the finite-search approximation (Section 8). Section 2 introduces the setup, and Section 9 concludes.

Setup

Let X denote the space of text samples. We keep X discrete throughout. The continuous objects introduced below are not coordinates on X itself, but local relaxations of paraphrase directions around a fixed base text. We consider the outputs of two embedding models, eP : X → S dP −1 ,

eM : X → RdM ,

(2.1)

where eM is the target model under attack, eP is a proxy model used by the adversary to measure semantic similarity, and S k−1 = {v ∈ Rk : ∥v∥2 = 1} is the unit hypersphere in Rk 1 . The embedding dimensions d ⊤ M and dP need not coincide; the local matrices A = JM JM and B = JP⊤ JP are q × q regardless, and the readout will act on RdM . Given x ∈ X , the adversary seeks a paraphrase x′ that preserves semantic meaning while maximally displacing the target representation eM (x). Semantic similarity is operationalised through the proxy distance dP (x, x′ ) := ∥eP (x′ ) − eP (x)∥2 , and the semantic neighbourhood of radius η > 0 is defined as Nη (x) := {x′ ∈ X : dP (x, x′ ) ≤ η}.

(2.2)

The adversarial representation problem is then sup x′ ∈Nη (x)

∥eM (x′ ) − eM (x)∥2 .

(2.3)

In other words, among all paraphrases judged semantically close to x by the proxy P , how far can the target M ’s internal representation be displaced? This formulation can be viewed as a theoretical abstraction of the empirical adversarial attack proposed by Can Türetken and Leippold (2026). 1

The target is left unnormalised so that the deployed affine head acts on it exactly; the proxy is normalised so that the proxy distance has the cosine reading used in Section 8.

We further assume a binary affine readout on top of the target representation: a weight vector w ∈ RdM and a bias b ∈ R such that the predicted class on input x is ŷ(x) := sign w⊤ eM (x) + b (2.4) where sign : R → {−1, +1} is the sign function, with the convention sign(0) := +1. In particular, ŷ(x) ∈ {−1, +1}, and we will work with this label convention throughout. We write sw,b (x) = w⊤ eM (x) + b for the affine readout or score, so that ŷw,b (x) = sign(sw,b (x)) is the induced binary classifier. The word “affine” refers only to the final readout; the embedding map eM may be an arbitrary nonlinear representation, such as a transformer embedding. For the pointwise geometric statements in Sections 3 and 4, we normalise w to have ∥w∥2 = 1, since rescaling (w, b) 7→ (w/∥w∥2 , b/∥w∥2 ) preserves the classifier (2.4). The decision hyperplane is then the level set {v ∈ RdM : w⊤ v + b = 0}, and the geometric margin of x is the perpendicular distance from eM (x) to it, γw (x) := w⊤ eM (x) + b ,

(2.5)

where the dependence on b is suppressed in the notation. In the later uniform margin bounds of Sections 5 and 6, the scale of w is kept explicit, because margin bounds depend on the norm constraint imposed on the readout class. There the same expression γw (x) = |w⊤ eM (x) + b| is a score margin rather than the perpendicular geometric distance. A paraphrase x′ induces a prediction flip at x if ŷ(x′ ) ̸= ŷ(x) (see Ch. 15 of Shalev-Shwartz and Ben-David, 2014, for definition of linear classifiers and margins in the context of support vector machines.). For a smooth nonlinear readout score g(eM (x)), the same first-order analysis applies locally with w replaced by ∇g(eM (x)) or, in the multiclass case, by the gradient of the relevant logit difference.

2.1

Local Semantic Perturbation Model

Since X is discrete, the maps eM and eP admit no direct notion of differentiation, and a local analysis at the text level is unavailable. We therefore model paraphrasing through a continuous local relaxation. The relaxation is local to the base text2 . For notational simplicity, we take the local coordinate dimension q to be fixed across x. Thus, for each x ∈ X , let Ux ⊂ Rq be an open neighbourhood of the origin, and assume the existence of two C 2 maps EM,x : Ux → RdM ,

EP,x : Ux → S dP −1 ,

EM,x (0) = eM (x),

EP,x (0) = eP (x). (2.6)

Section 8 describes empirical instantiations of this relaxation, including soft-token perturbations and finite generated paraphrase sets.

The latent coordinate u ∈ Ux parameterises an effective q-dimensional family of local paraphrase directions at x, and EM,x (u), EP,x (u) denote the target and proxy embeddings of the paraphrase indexed by u. This is not a claim that natural-language paraphrases globally form a smooth manifold. Rather, q is a chosen local coordinate dimension for a continuous approximation to paraphrase directions near x. The arguments below are pointwise and extend verbatim to input-dependent dimensions qx , provided B(x) is invertible on the chosen local coordinate space. When the base text x is fixed, we suppress this dependence and write (U, EM , EP ) := (Ux , EM,x , EP,x ). Lemma 2.1 (Local semantic representation). For each base text x, define the local Jacobians JM (x) :=

∂EM,x , ∂u u=0

JP (x) :=

∂EP,x , ∂u u=0

and the pullback metric matrices A(x) := JM (x)⊤ JM (x),

B(x) := JP (x)⊤ JP (x).

(2.7)

When x is fixed, write JM = JM (x), JP = JP (x), A = A(x), and B = B(x). Then JM is a dM × q matrix, and JP is dP × q, and a second-order Taylor expansion of the squared Euclidean distance at u = 0 yields ∥EP (u) − EP (0)∥22 = u⊤ Bu + o(∥u∥2 ),

(2.8)

∥EM (u) − EM (0)∥22 = u⊤ Au + o(∥u∥2 ),

(2.9)

where A and B are q × q positive semi-definite matrices, i.e., the pullbacks of the Euclidean metric on RdM and RdP through EM and EP , respectively. These quadratic forms encode the local geometry: u⊤ Bu measures local semantic displacement as seen by the proxy, and u⊤ Au measures local representation displacement in the target. Given the attacker’s objective (2.3) subject to the semantic neighbourhood constraint (2.2), together with the local representation in (2.6), the attacker’s problem becomes sup ∥EM (u) − EM (0)∥22

subject to

u∈U

∥EP (u) − EP (0)∥22 ≤ η 2 .

(2.10)

By Lemma 2.1, and for sufficiently small η so that the relevant proxy ellipsoid remains in the chart U , this reduces to the leading-order quadratic problem max u⊤ Au

u∈Rq

subject to

u⊤ Bu ≤ η 2 .

(2.11)

Throughout the main statements we assume B is positive definite. This means that the proxy embedding is locally sensitive to every retained paraphrase coordinate. If B is singular and 6

u⊤ Au > 0 for some u ∈ ker B, then there is a first-order target movement at zero proxy cost, the Rayleigh quotient u⊤ Au/u⊤ Bu is unbounded, and the local attackability problem is ill-posed. A finite quotient-space analysis therefore requires ker B ⊆ ker A, or an explicit modelling decision to remove or regularise the proxy-null directions (for example, replacing B by B + νI for some ν > 0). Proposition 2.2 (Attacker’s solution). Let A ⪰ 0 and B ≻ 0. Define the top generalised eigenvalue u⊤ Au λmax (A, B) := sup ⊤ = λmax B −1/2 AB −1/2 . (2.12) u̸=0 u Bu Then the optimal value of (2.11) is η 2 λmax (A, B). The optimum is attained at any B-normalised generalised eigenvector u∗ associated with λmax (A, B), that is, Au∗ = λmax (A, B)Bu∗ , u∗⊤ Bu∗ = η 2 . Recall that the operator norm of a matrix M ∈ Rd×d is ∥M ∥op := sup ∥M v∥2 , ∥v∥2 =1

and that for symmetric positive semidefinite M it coincides with the largest eigenvalue λmax (M ). ⊤ J . Then Remark 2.3 (Whitened-proxy interpretation). Assume B ≻ 0 and A = JM M λmax (A, B) = λmax B −1/2 AB −1/2 (2.13) = λmax (JM B −1/2 )⊤ (JM B −1/2 )

= ∥JM B −1/2 ∥2op . The matrix B −1/2 whitens the local paraphrase coordinate against the proxy metric. Hence the unit budget set {u⊤ Bu ≤ 1} becomes the Euclidean unit ball {z : ∥z∥2 ≤ 1}, and the target Jacobian becomes JM B −1/2 . The attackability index is therefore the squared operator norm of this whitened Jacobian: the adversary first equalises all paraphrase directions by the proxy budget and then asks how much the target embedding stretches the resulting whitened directions. Proposition 2.4 (Chart invariance). Let ϕ : Ũ → U be a C 2 diffeomorphism with ϕ(0) = 0, and let T := Dϕ(0) ∈ GL(q, R). Writing ẼM := EM ◦ ϕ and ẼP := EP ◦ ϕ, and denoting by Ã, B̃ the matrices of Lemma 2.1 computed in the chart ũ, we have Ã = T ⊤ AT,

B̃ = T ⊤ BT. 7

(2.14)

When B is invertible, B̃ −1 Ã = T −1 (B −1 A)T,

(2.15)

so the generalised eigenvalues of (A, B) are independent of the chosen paraphrase chart. Consequently, the local attackability index λ∗ (x) := λmax (A, B)

(2.16)

is intrinsic to the pair of local pullback metrics induced by (EM , EP ) at x. If u∗ solves Au∗ = λ∗ Bu∗ , then ũ∗ := T −1 u∗ solves the corresponding eigenproblem in the chart ũ, and the target-space tangent vector JM u∗ = J˜M ũ∗ is unchanged. In other words, changing the local parametrisation of paraphrase directions merely changes the coordinate representation of the two quadratic forms; it does not change the relative spectrum of the proxy and target geometries, the attackability index, or the induced firstorder target displacement. Remark 2.5 (Coordinate-free interpretation). Proposition 2.4 shows that λ∗ (x) is not an artefact of the particular coordinates used to index paraphrases. Geometrically, A and B are pullbacks of the Euclidean metric through EM and EP , and the spectrum of the matrix pencil (A, B) records one local metric relative to the other. Remark 2.6 (Intrinsic target-space sensitivity). The same reparameterisation calculation shows that the target-space sensitivity matrix S(x) := JM (x)B(x)−1 JM (x)⊤ is also intrinsic to the local pair of embedders. Indeed, under J˜M = JM T and B̃ = T ⊤ BT , ⊤ ⊤ ⊤ = (JM T )(T ⊤ BT )−1 (T ⊤ JM ) = JM B −1 JM . J˜M B̃ −1 J˜M

Consequently the readout-dependent quantity w⊤ S(x)w and the adjusted margins used below are independent of the chosen paraphrase chart. Moreover, S(x) = (JM (x)B(x)−1/2 )(JM (x)B(x)−1/2 )⊤ , which exhibits S(x) as symmetric and positive semidefinite. Applied to S(x), the matrixalgebra identity that CD and DC share the same nonzero spectrum, with C = JM (x)B(x)−1/2 and D = B(x)−1/2 JM (x)⊤ , gives ∥S(x)∥op = λmax (S(x)) = λmax B(x)−1/2 A(x)B(x)−1/2 = λ∗ (x). Remark 2.7 (Source-side and target-side descriptions). The identity ∥S(x)∥op = λ∗ (x) has a direct geometric reading. Two equivalent questions can be asked about the worst-case local 8

effect of a proxy-bounded paraphrase. The source-side question fixes the paraphrase budget in the local chart and asks which paraphrase direction induces the largest squared target displacement; the answer is η 2 λ∗ (x), attained by the leading generalised eigenvector of the pencil (A(x), B(x)). The target-side question fixes a unit direction w in the target embedding space and asks how much target displacement along w can be achieved by any proxy-bounded parap phrase; the maximum over w of this displacement is η ∥S(x)∥op . The two questions are dual descriptions of the same worst-case event, one viewed from the paraphrase side and one from the embedding side, and the identity expresses the agreement of their answers. The sourceside description is convenient when reasoning about the pencil and its generalised eigenvectors; the target-side description is convenient when reasoning about the readout and the adjusted margin.

Local prediction flips

Proposition 2.2 bounds the worst-case displacement of the target embedding under a proxy budget η. We now translate this into a condition on the adversary’s ability to flip the affine readout’s prediction. Let s0 := w⊤ EM (0) + b,

γw (x) := |s0 |.

(3.1)

A flip requires movement toward the decision boundary. If s0 > 0 the attacker must move the score in the negative direction; if s0 < 0 the attacker must move it in the positive direction. Under the local representation (2.6), the score change induced by u is w⊤ (EM (u) − EM (0)) = w⊤ JM u + o(∥u∥).

(3.2)

The exact calculation below is therefore a statement about the linearised local model slin (u) = s0 + w⊤ JM u

under

u⊤ Bu ≤ η 2 .

(3.3)

Theorem 3.1 (Linearised local prediction-flip condition). Fix a base text x and assume the conditions of Lemma 2.1 with B(x) ≻ 0. Define Σw (x) := w⊤ JM (x)B(x)−1 JM (x)⊤ w.

(3.4)

In the following identities, suppress the x-dependence and write JM = JM (x) and B = B(x). Then p (3.5) sup |w⊤ JM u| = η Σw (x). u⊤ Bu≤η 2

If Σw (x) > 0, one optimal linearised direction toward the decision boundary is B −1 J ⊤ w u∗flip = − sign(s0 ) η p M . Σw (x) 9

(3.6)

If Σw (x) = 0, the supremum in (3.5) is zero. Consequently, when γw (x) > 0, a prediction flip at x is achievable within proxy budget η in the linearised local model (3.3) if and only if p η Σw (x) > γw (x). (3.7) If γw (x) = 0, the base input already lies on the decision hyperplane. The strict flip formulation is then degenerate and depends on the convention for ties at the boundary, although (3.5) still gives the maximum first-order score displacement. The boundary set {x : sw,b (x) = 0} has probability zero under any distribution absolutely continuous on the target embedding, and the strict-versus-non-strict form of (3.7) is irrelevant to the population statements that follow. Theorem 3.2 (Finite-radius nonlinear error). Theorem 3.1 is exact for the linearised model. For the original smooth maps, define rM (η) :=

sup

w⊤ {EM (u) − EM (0) − JM u} .

u⊤ Bu≤η 2

p Then η Σw (x) > γw (x) + rM (η) is sufficient for a flip in the relaxed local model, while p η Σw (x) < γw (x) − rM (η) rules out a flip over the same ellipsoid. If the second derivative of EM is bounded and B ⪰ βI, then rM (η) = O(η 2 /β) as η ↓ 0. The factor 1/β enters because √ the proxy ellipsoid {u : u⊤ Bu ≤ η 2 } is contained in the Euclidean ball of radius η/ β, so that the quadratic Taylor remainder of EM is controlled by ∥u∥22 ≤ η 2 /β on the feasible set. An analogous second-order error is incurred when replacing the exact proxy constraint by u⊤ Bu ≤ η 2 . The quantity Σw (x) measures the squared maximum displacement of the target embedding along the readout direction w per unit proxy budget. Theorem 3.3 shows that this classifierspecific quantity is bounded above by the local attackability index λ∗ (x) of Proposition 2.2. Theorem 3.3 (Attackability index dominates classifier-direction displacement). Under the assumptions of Lemma 2.1 with B ≻ 0, the quantity Σw (x) defined in (3.4) satisfies, for every unit vector w ∈ RdM , Σw (x) ≤ λ∗ (x), (3.8) where λ∗ (x) = λmax (A, B) = λmax B −1/2 AB −1/2 = ∥S(x)∥op . ⊤. Equality in (3.8) holds when w is a top eigenvector of JM B −1 JM

Corollary 3.4 (Worst-direction no-flip certificate). Under the conditions of Theorem 3.1 and Theorem 3.3, for a fixed unit readout direction w, a sufficient condition for a local prediction flip at x to be unachievable within proxy budget η in the linearised local model is p η λ∗ (x) ≤ γw (x). This certificate is conservative: failure of the inequality does not imply that the particular readout direction w is flippable, since Σw (x) may be much smaller than λ∗ (x). 10

Population Attackability

So far the analysis has fixed a single input x and a single affine readout (w, b). We now lift the linearised prediction-flip condition of Theorem 3.1 to a population-level statement for this fixed readout. Let D be a distribution on X , write P for probability under D, and let X denote a random element with distribution D. Throughout Sections 4 to 6, we ignore the degenerate boundary case in which Σw (x) = 0 and γw (x) = 0 simultaneously, or assume it has probability zero under D for the readouts under consideration; the convention Zw (x) = 0 at this configuration is then irrelevant for population and uniform results. Definition 4.1 (Attackability margin). The attackability-adjusted margin of X for the fixed readout (w, b) is the extended nonnegative random variable  p   γw (x)/ Σw (x), Σw (x) > 0,    (4.1) Zw (x) := +∞, Σw (x) = 0 and γw (x) > 0,     0, Σw (x) = 0 and γw (x) = 0. The population attackability at proxy budget η > 0 is Aw (η) := P [Zw (X) < η] = FZ−w (η).

(4.2)

where FZ−w (η) := P[Zw (X) < η] = FZw (η−) is the left-limit version of the distribution function. We use the strict inequality because the strict flip condition in Theorem 3.1 gives p η Σw (x) > γw (x). If Zw has no atom at η, this agrees with the usual CDF FZw (η) = P[Zw (X) ≤ η]. To understand the intuition behind Definition 4.1, recall from Theorem 3.1 that, in the p linearised local model, a paraphrase can flip the readout on input x if and only if η Σw (x) > p γw (x). Rearranging, the flip is achievable if and only if η > γw (x)/ Σw (x) when Σw (x) > 0, and the right-hand side is exactly Zw (x). Thus Zw (x) is the smallest proxy budget at which the adversary can flip the linearised prediction on x: a large Zw (x) implies local robustness, and a small Zw (x) implies local fragility. Inputs with Σw (x) = 0 and γw (x) > 0 are first-order certifiably robust in the readout direction, since no proxy-bounded perturbation changes the score to first order. In the population setting, X is drawn from D and Zw (X) becomes a random variable. The quantity Aw (η) = Px∼D [Zw (X) < η] is the population fraction of inputs that are flippable at budget η in the linearised local model. It is non-decreasing in η, satisfies Aw (0) = 0, and obeys limη→∞ Aw (η) = P[Zw (X) < ∞]. The remainder of this section bounds Aw (η) in terms of margin and anisotropy tails and estimates it from finite samples.

Theorem 4.2 (Margin-tail bound on population attackability). Assume the conditions of Theorem 3.1 hold P-a.s. Then, for every η > 0 and every deterministic Λ > 0, h √ i Aw (η) ≤ P γw (X) < η Λ + P [λ∗ (X) > Λ] . (4.3) In particular, if λ∗ (X) ≤ Λ P-a.s., then h √ √ i Aw (η) ≤ P γw (X) < η Λ = Fγ−w η Λ ,

(4.4)

where Fγ−w (t) := P[γw (X) < t] = Fγw (t−). Equivalently, if Λ1−β is chosen so that P[λ∗ (X) > Λ1−β ] ≤ β, then h i p Aw (η) ≤ P γw (X) < η Λ1−β + β. (4.5) Remark 4.3 (Readout-specific quantile bound). The bound of Theorem 4.2 controls Aw (η) p through the worst-direction index λ∗ (x). Because Aw (η) = P[γw (X) < η Σw (X)] by Definition 4.1, the identical argument applied to Σw (X) in place of λ∗ (X) gives, for every deterministic Λ > 0, h √ i Aw (η) ≤ P γw (X) < η Λ + P[Σw (X) > Λ] , and, if Σ1−β is chosen so that P[Σw (X) > Σ1−β ] ≤ β, i h p Aw (η) ≤ P γw (X) < η Σ1−β + β. Since Σw (x) ≤ λ∗ (x) by Theorem 3.3, the (1 − β)-quantile of Σw is no larger than that of λ∗ , so this readout-specific bound is never looser than the readout-free bound of Theorem 4.2 at the same β. Theorem 4.4 (Empirical concentration of population attackability). Fix the affine readout (w, b). Let X1 , . . . , Xn be i.i.d. draws from D, and define the empirical attackability curve n

Ân,w (η) :=

1X 1 [Zw (Xi ) < η] . n

(4.6)

i=1

Then, for every δ ∈ (0, 1), with probability at least 1 − δ over the sample, r ln(2/δ) sup Ân,w (η) − Aw (η) ≤ . 2n η>0

(4.7)

Remark 4.5 (Fixed versus data-dependent readouts). Theorem 4.4 is an oracle concentration statement for a fixed readout and exactly observed values of Zw (Xi ). If the readout is learned or selected using the same sample, the DKW bound does not by itself justify uniform validity over the class of possible readouts. That extension requires sample splitting or a uniformconvergence bound for the class of attackability events {x 7→ 1[Zw (x) < η] : (w, b, η) ∈ W × R × (0, ∞)}. 12

Uniform Attackability over Classes of Affine Readouts

Section 4 treats the affine readout (w, b) as fixed. This is the right setting for auditing a single deployed classifier, and it is also the setting of the empirical exercise in Section 8, where FinBERT is treated as a deployed financial-sentiment classifier with a fixed pre-trained affine readout. However, in statistical learning the readout is typically trained, tuned, or otherwise selected from data. A pointwise concentration statement such as Theorem 4.4 does not by itself justify using the same sample both to choose the readout and to estimate its attackability. The goal of this section is to replace the fixed-readout DKW bound by a uniform bound over a class of affine readouts. Throughout this section we write z(x) := eM (x),

S(x) := JM (x)B(x)−1 JM (x)⊤ ,

where JM (x) and B(x) are the local target Jacobian and proxy pullback metric at x. By Remark 2.6, S(x) does not depend on the particular local chart used to parameterise paraphrases. The matrix S(x) is positive semidefinite and records how proxy-valid paraphrase directions move the target representation in the coordinates seen by the readout. For a readout parameter θ = (w, b), define fθ (x) := w⊤ z(x) + b,

γθ (x) := |fθ (x)|,

Σθ (x) := w⊤ S(x)w.

The linearised local attackability event at budget η is o n p Gθ,η (x) := 1 |fθ (x)| < η Σθ (x) .

(5.1)

Thus Gθ,η (x) = 1 means that, in the first-order local model, the margin of the readout is smaller than the displacement that the adversary can induce in the readout direction. For a class Θ of affine readouts, set GΘ := {x 7→ Gθ,η (x) : θ ∈ Θ, η > 0} .

(5.2)

The corresponding population and empirical attackability curves are 1 Abn,θ (η) := n

Aθ (η) := P{Gθ,η (X) = 1},

n X

Gθ,η (Xi ).

i=1

The empirical and population attackability curves Abn,θ (η) and Aθ (η) are the same objects as Abn,w (η) and Aw (η) in Section 4, with the subscript θ = (w, b) replacing w to make the dependence on the bias explicit. Definition 4.1 and Theorem 3.1 give Gθ,η (x) = 1{Zθ (x) < η} under the conventions already in place for Σθ (x) = 0, so the two notations refer to the same indicator function and to the same empirical and population averages. Throughout this section 13

and Section 6 we assume that P{γθ (X) = 0} = 0 for each readout θ ∈ Θ; this excludes the boundary-degeneracy case where both γθ (x) and Σθ (x) vanish, on which the strict inequality in (5.1) and the convention Zθ (x) = 0 in Definition 4.1 would otherwise disagree. The next theorem is a direct uniform-convergence analogue of the DKW result in Section 4. Instead of controlling the empirical CDF of one fixed random variable Zw (X), it controls all attackability indicators in GΘ simultaneously. We use the VC dimension (Vapnik and Chervonenkis, 1971) as the complexity measure of binary function classes. For a class F of {0, 1}-valued functions on a domain Z, a finite set {z1 , . . . , zk } ⊂ Z is shattered by F if, for every σ ∈ {0, 1}k , some f ∈ F satisfies f (zi ) = σi for all i. The VC dimension VC(F) is the largest cardinality of a shattered set, with VC(F) = ∞ if shattered sets of unbounded size exist. It controls the rate of uniform convergence of empirical to population frequencies and appears in distribution-free generalisation bounds. Theorem 5.1 (Uniform VC concentration for attackability). Let X1 , . . . , Xn be i.i.d. from D, and suppose that VC(GΘ ) = v < ∞. There is a universal constant C such that, for every δ ∈ (0, 1), with probability at least 1 − δ, r v log(en) + log(1/δ) . (5.3) sup Abn,θ (η) − Aθ (η) ≤ C n θ∈Θ, η>0 Theorem 5.1 says that empirical attackability remains a valid diagnostic even when the affine readout is chosen after seeing the sample, provided the induced class of attackability events has finite VC dimension. This is the learning-theoretic upgrade from a fixed classifier to a data-dependent classifier. The DKW bound is sharper for a single fixed readout, but it has no built-in protection against data-dependent choice of θ. The following proposition gives a simple dimension-dependent VC bound for all affine readouts on a d-dimensional target embedding. The proof is based on one observation: the attackability event is a quadratic inequality in the embedding coordinates, together with the entries of the local sensitivity matrix S(x), and such inequalities can be viewed as linear thresholds after an elementary feature lift. This is the degree-two instance of the standard polynomial-surface viewpoint: a polynomial threshold can be represented as an affine threshold in a higher-dimensional space of monomial features (Anthony, 1995). Proposition 5.2 (A VC bound for affine readouts). Assume z(x) ∈ RdM and S(x) is a symmetric positive semidefinite dM × dM matrix for every x. Let Θ ⊆ RdM × R be any set of affine-readout parameters θ = (w, b). Then VC(GΘ ) ≤ (dM + 1)2 .

(5.4)

The bound in Proposition 5.2 is conservative, since the elementary lifting treats the structured quadratic coefficients as if they were independent. A polynomial-threshold argument that exploits the parameterisation of GΘ by (w, b, η) gives a sharper rate. 14

Proposition 5.3 (Polynomial-threshold improvement). Under the assumptions of Proposition 5.2, VC(GΘ ) = O(dM ). Corollary 5.4 (Uniform attackability bound for affine readouts). Under the assumptions of Proposition 5.2, there is a universal constant C such that, with probability at least 1 − δ, r (dM + 2) log(en) + log(1/δ) sup Abn,θ (η) − Aθ (η) ≤ C . (5.5) n θ∈Θ, η>0 The bound follows from Theorem 5.1 combined with the polynomial-threshold VC bound of Proposition 5.3.

Attackability-Adjusted Margin Bounds

The VC bound above controls the binary attackability indicator directly. Classical margin theory suggests a complementary approach: rather than count only whether an input is attackable, measure how attackable it is. This replaces a binary event by a real-valued margin distribution, which can give sharper and more informative generalization bounds. The attackability event in Section 5 is label-free: it asks only whether the classifier’s prediction can be flipped, not whether the prediction is correct. The margin theory below introduces labels. Assume that the data are labelled, with Y ∈ {−1, +1}. For a readout θ = (w, b) and budget η > 0, we define the attackability-adjusted margin as follows. Recall from Section 5 the notation z(x) := eM (x) for the target embedding and S(x) := JM (x)B(x)−1 JM (x)⊤ for the local sensitivity matrix. q (6.1) mη,θ (x, y) := y w⊤ z(x) + b − η w⊤ S(x)w. The first term is the usual signed classifier margin. The second term is the largest first-order displacement, at proxy budget η, that any proxy-bounded paraphrase can induce against this readout direction. The adjusted margin therefore subtracts a local geometric penalty from the ordinary margin, reflecting the worst-case loss of margin available within the proxy budget. The linearised local robust risk is Rη (θ) := P{mη,θ (X, Y ) ≤ 0},

(6.2)

where a positive adjusted margin certifies correct classification after the linearised proxybounded perturbation. The flip event and the robust-risk event behave differently and it is worth recording how. The flip event from Section 5, {Zθ (X) < η} = {γθ (X) < η 15

Σθ (X)},

asks whether some proxy-bounded paraphrase moves X across the decision boundary of the readout. It depends on X but not on the label Y . The robust-risk event, p {mη,θ (X, Y ) ≤ 0} = {Y fθ (X) ≤ η Σθ (X)}, asks whether the readout either already misclassifies X or can be made to misclassify it by such a paraphrase. It depends on both X and Y . On a correctly classified input (Y fθ (X) > 0), Y fθ (X) = |fθ (X)| = γθ (X), and the two p p events become {γθ (X) < η Σθ (X)} and {γθ (X) ≤ η Σθ (X)} respectively, so they agree apart from the equality boundary. On a misclassified input (Y fθ (X) < 0), the two events diverge. The robust-risk event p automatically holds, because Y fθ (X) < 0 and η Σθ (X) ≥ 0, so the inequality Y fθ (X) ≤ p η Σθ (X) is satisfied regardless of the adversary. For the flip event, suppose Y = +1 but fθ (X) < 0, so that the classifier predicts −1 on a positive-labelled input. A paraphrase that moves the readout score fθ from negative through zero into positive territory would ”flip” the prediction, and the flip event would treat this as an adversarial success. But the flipped prediction is now +1, which is the correct label. The flip event has fired on what is, from the user’s point of view, a correction rather than an attack. The robust-risk event ignores such cases: it already counts the input as an error before the adversary acts, and a paraphrase that corrects the error does not remove that count. The adjusted margin therefore tracks robust classification risk, not prediction-flip frequency. The two coincide on correctly classified inputs and disagree on misclassified inputs, where robust risk is the right quantity for a learning-theoretic bound. For a margin slack ρ > 0, its empirical ρ-margin analogue is bn,η,ρ (θ) := 1 R n

n X

1 {mη,θ (Xi , Yi ) ≤ ρ} .

(6.3)

i=1

The slack parameter ρ plays the same role as in ordinary margin bounds. The empirical ρ-margin error counts two kinds of examples: those with adjusted margin at most zero, which are already locally non-robust on the sample, and those with adjusted margin in the interval (0, ρ], which are empirically robust but only by an amount small enough that uniform fluctuation between the empirical and population margin distributions could plausibly move them across the decision threshold. The slack ρ acts as a safety buffer. A wider slack counts more sample points as potentially fragile, but reduces the complexity penalty in Theorem 6.1, which depends on the fat-shattering dimension of the adjusted-margin class at scale ρ and is decreasing in ρ. Let Mη := {(x, y) 7→ mη,θ (x, y) : θ ∈ Θ} . (6.4) The following theorem is the standard fat-shattering margin bound applied to this adjustedmargin class. One route to this form is to combine the margin-covering bound of Anthony 16

and Bartlett (1999, Theorem 10.4) with the fat-shattering covering estimate of Anthony and Bartlett (1999, Theorem 12.13). We use the fat-shattering dimension as the scale-sensitive complexity measure of realvalued function classes. For a class F on a domain Z and α > 0, a finite set {z1 , . . . , zk } ⊂ Z is α-shattered by F if there exist reference levels r1 , . . . , rk ∈ R such that, for every σ ∈ {−1, +1}k , some f ∈ F satisfies σi (f (zi ) − ri ) ≥ α for all i. The fat-shattering dimension fatα (F) is the largest cardinality of an α-shattered set. It is a scale-sensitive analogue of VC dimension and appears in margin bounds because it controls the covering number of F at resolution α. Theorem 6.1 (Fat-shattering margin bound). Assume that every function in Mη takes values in [−M, M ]. Fix ρ ∈ (0, M ], and let dρ := fatρ/8 (Mη ). There is a universal constant C such that, for i.i.d. samples (Xi , Yi )ni=1 , with probability at least 1 − δ, uniformly over θ ∈ Θ, s 2 bn,η,ρ (θ) + C dρ log (CM n/ρ) + log(1/δ) . (6.5) Rη (θ) ≤ R n This theorem should be interpreted exactly like a classical margin bound. If most sample points have adjusted margin much larger than ρ, then the empirical term is small. The complexity term measures the cost of uniform control over the readout class Θ. The relevant p margin is not yfθ (x) alone, but yfθ (x) − η w⊤ S(x)w: points with large ordinary margin can still be fragile if their local displacement term is also large. For affine readouts, one can also obtain a more concrete norm-controlled covering bound. We use the following covering-number notation. If F is a class of real-valued functions on a domain Z, the supremum-norm distance between two functions f, g ∈ F is d∞ (f, g) := sup |f (z) − g(z)|. z∈Z

For ϵ > 0, N∞ (ϵ, F) denotes the supremum-norm covering number, i.e., the least cardinality of a finite set C ⊆ F such that for every f ∈ F there is a g ∈ C with d∞ (f, g) ≤ ϵ. If no finite such cover exists, we set N∞ (ϵ, F) = ∞. In the proposition below, the domain is Z = X × {−1, +1}, since functions in Mη take labelled examples (x, y) as input. Let ΘW,B0 := {(w, b) : ∥w∥2 ≤ W, |b| ≤ B0 }. The next proposition shows that the adjusted-margin class is Lipschitz in (w, b) when the embeddings are bounded and the local anisotropy matrices are uniformly bounded. The √ factor R + η Λ is the effective radius seen by the readout after accounting for adversarial displacement. 17

Proposition 6.2 (Norm-controlled covering bound). Assume ∥z(x)∥2 ≤ R and ∥S(x)∥op ≤ Λ for all x. By Remark 2.6, this is equivalent to λ∗ (x) ≤ Λ, the bounded-anisotropy condition used in Theorem 4.2. For the class Mη induced by ΘW,B0 , the supremum-norm covering number satisfies, for every ϵ > 0, N∞ (ϵ, Mη ) ≤

√ !dM 4B0 4W (R + η Λ) 1+ . 1+ ϵ ϵ

(6.6)

Moreover, every m ∈ Mη is bounded in absolute value by √ Mη := W R + B0 + ηW Λ.

(6.7)

Corollary 6.3 (Norm-controlled attackability-adjusted margin bound). Under the assumptions of Proposition 6.2, there is a universal constant C such that, for every fixed ρ ∈ (0, Mη ], with probability at least 1 − δ, uniformly over θ ∈ ΘW,B0 , v √ u u d log 1 + CW (R+η Λ) + log 1 + CB0 + log(1/δ) t M ρ ρ bn,η,ρ (θ) + C Rη (θ) ≤ R . (6.8) n Corollary 6.3 exhibits a two-sided dependence on the local geometry. Increasing the budget p η or the anisotropy bound Λ makes the displacement term η w⊤ S(x)w larger pointwise, which moves more sample points into the ρ-margin set and so increases the empirical term √ bn,η,ρ (θ). The same quantity also appears in the effective radius R+η Λ inside the complexity R term, where it inflates the covering number of the adjusted-margin class and so increases the uniform-convergence contribution. The bound is small only when both effects are small, i.e., when the budget is modest, the local anisotropy is well-controlled, and most sample points have adjusted margin comfortably above ρ. The preceding corollary uses a volumetric covering of the Euclidean ball in Rd . When d is large, a data-dependent Rademacher bound gives a more informative alternative. Let σ1 , . . . , σn be i.i.d. Rademacher random variables, independent of the sample, taking values ±1 with equal probability. For a sample Sn = ((Xi , Yi ))ni=1 and a class F of real-valued functions on labelled examples, the empirical Rademacher complexity of F is # " n X 1 b n (F) := Eσ sup σi f (Xi , Yi ) Sn , R f ∈F n i=1

where the conditional expectation Eσ [· | Sn ] integrates over the Rademacher variables with the sample held fixed. Also define the empirical trace sensitivity n

T n :=

1X tr S(Xi ). n i=1

The trace is the right dimension-free quantity for the sensitivity term in the Rademacher bound. The operator norm ∥S(x)∥op controls the largest single eigenvalue, i.e., the worst-case P sensitivity in any direction. The trace tr S(x) = k λk (x) sums the contributions from all eigendirections of S(x), capturing the aggregate sensitivity across all readout directions that the adversary can move in locally. The covering bound (Corollary 6.3) uses the operator norm because its Lipschitz argument depends on the worst direction; the Rademacher bound below uses the trace because the empirical-process sum aggregates across all directions. Theorem 6.4 (Trace-sensitive Rademacher margin bound). Assume S(x) ⪰ 0 for every x, and let Mη be the adjusted-margin class induced by ΘW,B0 . For every sample Sn ,  s  !1/2 n  pW 2 + B 2 X Tn 0 b n (Mη ) ≤ C (∥z(Xi )∥22 + 1) + ηW , (6.9) R  n n  i=1

where C is a universal constant. Consequently, for every ρ > 0, with probability at least 1 − δ, uniformly over θ ∈ ΘW,B0 , bn,η,ρ (θ) Rη (θ) ≤ R  p C  W 2 + B02 + ρ  n

n X (∥z(Xi )∥22 + 1) i=1

!1/2 + ηW

 r Tn log(1/δ) (6.10) +C . n  n

In particular, if ∥z(x)∥2 ≤ R and tr S(x) ≤ T for all x, then r r r ! q 2+1 C R T log(1/δ) bn,η,ρ (θ) + Rη (θ) ≤ R + ηW . W 2 + B02 +C ρ n n n

(6.11)

with the same probability, uniformly over θ ∈ ΘW,B0 . If, in addition, rank S(x) ≤ q and ∥S(x)∥op ≤ Λ, then one may take T = qΛ. This theorem is dimension-free in the target embedding dimension dM , but it is not free of geometric complexity. The sensitivity contribution is controlled by tr S(x), or by the effective local rank bound qΛ. This distinction is important: an operator-norm bound alone controls only the single most expansive proxy direction and does not control the richness of the whole p class x 7→ w⊤ S(x)w when many independent local sensitivity directions are present. Remark 6.5 (Relation to the VC bound). The VC result in Section 5 gives a distributionfree uniform bound for attackability indicators. The elementary lifting in Proposition 5.2 gives an O(d2 ) complexity, and the polynomial-threshold improvement in Proposition 5.3 sharpens this to O(d). The margin bounds above use additional regularity, namely bounded readout norm and bounded local anisotropy, or trace-sensitive control of the local sensitivity matrices, to obtain a scale-sensitive statement in terms of the empirical distribution of the adjusted margins. This is closer to classical margin-based learning theory and is likely to be the more informative bound when most training examples have large adjusted margin. 19

The deterministic anisotropy bound in Proposition 6.2 can be relaxed to a high-probability bound. This connects the tail perspective of Theorem 4.2 with the uniform adjusted-margin analysis above: high-anisotropy points are charged to a tail term, while the complexity term is computed using an anisotropy quantile. Corollary 6.6 (Quantile-relaxed adjusted-margin bound). Assume ∥z(x)∥2 ≤ R for all x and let ΘW,B0 = {(w, b) : ∥w∥2 ≤ W, |b| ≤ B0 }. Fix β ∈ [0, 1) and choose Λβ > 0 such that P{∥S(X)∥op > Λβ } ≤ β. Let Mη,β := W R + B0 + ηW

Λβ .

Then there is a universal constant C such that, for every ρ ∈ (0, Mη,β ], with probability at least 1 − δ, uniformly over θ ∈ ΘW,B0 , bn,η,ρ (θ) Rη (θ) ≤ β + R v u √ u CW (R+η Λβ ) CB0 u d log 1 + + log 1 + + log(1/δ) ρ ρ t +C . n

(6.12)

(6.13)

The price for avoiding a deterministic uniform bound on ∥S(x)∥op is the additional tail term β. The empirical margin term remains the ordinary adjusted-margin term from (6.3), computed with the actual S(x) on the observed sample, while the complexity term depends only on the quantile level Λβ . Since ∥S(x)∥op = λ∗ (x), this is the margin-bound analogue of the quantile relaxation in Theorem 4.2.

Finite Paraphrase Search

The preceding sections analyse an idealised local adversary that may choose any point in a proxy-defined ellipsoid. Practical text adversarial attacks are not of this form. They search over a finite set of candidate paraphrases PK (x) = {x′1 , . . . , x′K }, obtained from a paraphrase generator, beam search over substitutions, or gradient-based decoding of soft-token iterates (Guo et al., 2021; Jang et al., 2017). Each candidate is either proxy-valid (within distance η of x) or not, and the attack inspects them one by one. There is no continuous adversary in practice; there is a discrete list of K candidates and a decision on each. This section bridges the two settings. The continuous theory in the preceding sections gives a geometric characterisation of worst-case proxy-bounded displacement and a statistical theory of attackability. The finite-search setting is closer to what empirical work actually does. Connecting them requires care because success and failure of finite search have asymmetric implications. The connection is established inside a linearised local chart around the base text, 20

and the quantitative results below are local approximations rather than global geometric facts about the embeddings.

7.1

Finite-search analogues of the continuous quantities

Definition 7.1 (Search procedure). A search procedure of size K is a, possibly randomised, map PK : X → 2X that assigns to each base text x ∈ X a candidate set PK (x) ⊆ X of cardinality at most K. The procedure may depend on the readout (w, b) and the budget η; this dependence is suppressed in the notation. Practical realisations include paraphrase generators, beam search over substitution candidates, and gradient-based decoding of soft-token iterates (Guo et al., 2021; Jang et al., 2017). By abuse of notation, PK (x) refers either to the procedure or to its output at x. Fix a search procedure PK and write PK (x) = {x′1 , . . . , x′K } for its output at x, with the convention that some entries may be omitted when the procedure returns fewer than K candidates. Define the proxy-valid subset PK,η (x) := {x′ ∈ PK (x) : dP (x, x′ ) ≤ η}, where dP (x, x′ ) := ∥eP (x) − eP (x′ )∥2 is the proxy distance. The finite-search analogue of the worst-case representation displacement at budget η is ′ ′ ∆fin (x) := max {0} ∪ {∥e (x ) − e (x)∥ : x ∈ P (x)} . 2 M M K,η M,K,η The convention max{0} handles the case PK,η (x) = ∅, where no candidate is proxy-valid and no finite displacement is achieved. For a fixed affine readout (w, b), write sw,b (x) = w⊤ eM (x) + b,

σx = sign(sw,b (x)),

assuming sw,b (x) ̸= 0. The finite-search displacement toward the decision boundary is fin DK,η (x; w, b) := max {0} ∪ {−σx w⊤ (eM (x′ ) − eM (x)) : x′ ∈ PK,η (x)} . fin (x; w, b) ≥ γ (x), with A finite candidate reaches the decision boundary whenever DK,η w γw (x) = |sw,b (x)| the geometric margin. This is the finite-search analogue of the linearised p flip condition η Σw (x) > γw (x) from Theorem 3.1.

7.2

The asymmetry between finite and continuous attacks

fin (x; w, b) ≥ Finite-search success and finite-search failure carry asymmetric weight. Success, DK,η γw (x), exhibits an explicit proxy-valid paraphrase that crosses the decision boundary, and is fin (x; w, b) < γ (x), only certifies that the a direct certificate of non-robustness. Failure, DK,η w

particular set PK (x) contains no flip; paraphrases outside the candidate set may still be proxy-valid and may flip the prediction, and λ∗ (x) may be arbitrarily large. The corresponding empirical quantity is therefore the finite-search attackability fin Afin w (η; PK ) := P{DK,η (X; w, b) ≥ γw (X)} ≤ Aw (η),

where the inequality holds up to the second-order linearisation error inherent in passing from the exact finite-search displacement Dfin to its linearised analogue Dlin (cf. Theorem 3.2). A finite-search success at x exhibits an exact proxy-valid paraphrase flip, while Aw (η) is the population attackability of the linearised local model, so the two sides are aligned only up to the linearisation residual. A confidence bound on Afin w follows by inverting the binomial likelihood: if zero attacks are found in n independent trials then, with confidence 1 − δ, 1/n ≤ log(1/δ)/n. This bounds the procedure, not the continuous adverAfin w (η; PK ) ≤ 1 − δ sary; closing that gap is the role of the covering conditions in the next subsection.

7.3

A covering condition makes finite search faithful

The gap between continuous and finite attacks closes when the candidate set PK (x) is dense enough to approximate the continuous adversary. The relevant notion is a covering radius of the proxy ball in the local chart. By Lemma 2.1, paraphrases of x are parameterised locally by a coordinate u in some qdimensional neighbourhood U ⊆ Rq , with the proxy and target embeddings admitting linear approximations EP (u) − EP (0) ≈ JP (x)u and EM (u) − EM (0) ≈ JM (x)u at u = 0. Each candidate x′k ∈ PK (x) corresponds to some local coordinate uk ∈ U , and the candidate set defines a finite point cloud {u1 , . . . , uK } in local coordinates. Remark 7.2 (Local nature of the results). The bounds in this section are statements about the linearised local chart. They are meaningful for proxy budgets η inside the radius of validity of EP (u) − EP (0) ≈ JP (x)u and EM (u) − EM (0) ≈ JM (x)u; the unmodelled error is O(∥u∥2 ). At η much larger than this scale, the bounds have no immediate content for the original embedding geometry. fin (x; w, b), namely The propositions below operate on the linearised analogue of DK,η

lin DK,η (x; w, b) := max {0} ∪ {−σx w⊤ JM (x)uk : 1 ≤ k ≤ K, ∥uk ∥B(x) ≤ η} . Here −σx w⊤ (eM (x′ ) − eM (x)) is replaced by its first-order approximation −σx w⊤ JM (x)uk , and the proxy-validity test dP (x, x′ ) ≤ η is replaced by ∥uk ∥B(x) ≤ η. Both replacements incur second-order error in ∥uk ∥, so within the radius of validity of Remark 7.2, lin fin DK,η (x; w, b) = DK,η (x; w, b) + O(∥u∥2 ).

Proposition 7.3 (Finite search under a local covering condition). Fix a base text x and assume the conditions of Lemma 2.1 with B(x) ≻ 0. Let Bx (η) := {u ∈ U : u⊤ B(x)u ≤ η 2 } be the linearised proxy ball at budget η. Suppose δ < η and that the candidate set PK (x), in local coordinates {u1 , . . . , uK }, forms a δ-cover of Bx (η − δ) with respect to the proxy metric: p for every u ∈ Bx (η − δ) there is some uk with ∥u − uk ∥B(x) ≤ δ, where ∥v∥B(x) := v ⊤ B(x)v. Then for any affine readout (w, b), (η − 2δ)

p p lin Σw (x) ≤ DK,η (x; w, b) ≤ η Σw (x).

In particular, if δ ≤ ηϵ for some ϵ ∈ (0, 1/2), then lin DK,η (x; w, b) ≥ (1 − 2ϵ)η

p Σw (x).

The upper bound is automatic: every candidate with ∥uk ∥B(x) ≤ η has linearised readout p displacement at most the continuous worst-case displacement η Σw (x). The lower bound is the substantive content. It says that if the candidate set δ-covers the slightly smaller p ball Bx (η − δ), then the linearised finite-search displacement comes within 2δ Σw (x) of the continuous worst case. When δ is small (the candidate set is dense), the gap is small, and finite search faithfully approximates the continuous adversary up to the second-order error linking Dlin to Dfin . A direct consequence is a quantitative version of the failure-to-certify asymmetry: a candidate set that is a δ-cover of Bx (η −δ) with δ ≤ ηϵ turns failure of finite search into approximate robustness against the continuous adversary. Corollary 7.4 (Robustness certification under a covering condition). Under the assumptions of Proposition 7.3, suppose that the candidate set PK (x) is a δ-cover of Bx (η − δ) in the proxy lin (x; w, b) < γ (x), then metric with δ ≤ ηϵ for some ϵ ∈ (0, 1/2). If DK,η w (1 − 2ϵ)η

p Σw (x) < γw (x),

equivalently η

p γw (x) Σw (x) < . 1 − 2ϵ

Failure of finite search in the linearised chart, when the candidate set is a δ-cover of Bx (η −δ) with δ ≤ ηϵ, certifies robustness against the continuous adversary at budget η(1−2ϵ) rather than the original budget η. As the cover becomes denser (ϵ → 0), the certified budget approaches η and the certificate becomes tight.

7.4

Beyond covering: probabilistic candidate sets

Many empirical paraphrase generators do not aim for deterministic covering. They sample candidates from some distribution over proxy-valid paraphrases, either explicitly (sampling 23

from a paraphrase model) or implicitly (running a randomised optimisation procedure). For such procedures, a more natural condition is that the candidate set covers the proxy ball with high probability, where the probability is taken over the sampling distribution. Proposition 7.5 (Probabilistic covering). Suppose the candidate coordinates u1 , . . . , uK are drawn i.i.d. from a distribution on the local chart with density f satisfying f (u) ≥ c > 0 for p all u ∈ Bx (η), and set κ := c/ det B(x). Then for every δ ∈ (0, η), P{PK (x) is a δ-cover of Bx (η − δ)} ≥ 1 − N (δ/2, Bx (η − δ))(1 − κvq (δ/2)q )K , where vq is the volume of the unit Euclidean ball in Rq and N (δ/2, Bx (η − δ)) is the δ/2covering number of Bx (η − δ) in the proxy metric. Remark 7.6 (Applicability of the density-floor hypothesis). The density-floor condition f ≥ c requires the sampling distribution to be full-dimensional on the local chart. It covers uniform sampling on Bx (η) and noise-injection or randomised-optimisation schemes with continuous densities, but excludes samplers whose support is contained in a Lebesgue-null subset, such as discrete paraphrase samplers or one-dimensional samplers along a fixed direction. Proposition 7.7 gives the analogue for the one-dimensional case; discrete samplers fall outside the reach of both results and can only be analysed via the deterministic Proposition 7.3 or empirically. In particular, K = Θ(δ −q log(1/δ)) candidates suffice to δ-cover Bx (η − δ) with high probability. This is exponential in the local chart dimension q, the standard difficulty of dense sampling in high-dimensional spaces. Practical attacks circumvent this difficulty by exploiting structure in the embeddings: they bias the sampling toward directions where the readout score moves quickly, using gradient information (Guo et al., 2021), or they restrict to discrete paraphrases that are linguistically plausible (Alzantot et al., 2018; Jin et al., 2020).

7.5

Readout-aligned search

A practical attack that uses information about the readout can achieve much better effective coverage than uniform sampling. The basic move is to search not over the whole proxy ball but along the readout-specific worst-case direction of the linearised attacker, the closed-form solution of Theorem 3.1. Proposition 7.7 (Effective one-dimensional coverage). Let (w, b) be a fixed affine readout with Σw (x) > 0 and define the linearised worst-case direction rw (x) := −σx

B(x)−1 JM (x)⊤ w p , Σw (x)

which satisfies ∥rw (x)∥B(x) = 1. Suppose the candidate coordinates {u1 , . . . , uK } contain points {αj rw (x) : j = 1, . . . , J} for some scalars αj ∈ [0, η] that δ ′ -cover the interval [0, η]. Then p lin DK,η (x; w, b) ≥ (η − δ ′ ) Σw (x). The proposition is the readout-specific analogue of Proposition 7.3 along a single direction: p a J-point cover of [0, η] along rw (x) recovers the continuous worst case up to δ ′ Σw (x), without requiring a q-dimensional cover of the whole proxy ball. The direction rw (x) is not the leading generalised eigenvector v ∗ (x) of (A(x), B(x)): v ∗ (x) maximises target-representation displacement in the proxy metric and is the right object for λ∗ (x), but for flipping a fixed affine readout it is the readout-direction displacement that matters, and the direction that maximises it is rw (x). The limitation of one-dimensional readout-aligned search is that it exploits a single readout. If the empirical attack is to certify robustness over a class of readouts, the alignment direction has to be recomputed for each readout, and the bound applies only to the readouts covered.

7.6

Empirical interpretation

The section’s overall message for empirical work on text adversarial robustness can be summarised in three principles. First, successful attacks are unambiguous evidence of vulnerability and require no theoretical bridge. A paraphrase that is proxy-valid and flips the prediction is a witness. Second, failed attacks should be reported alongside the search procedure that produced them, not as evidence of robustness against the continuous adversary. The relevant population quantity for empirical evaluation is the finite attackability Afin w (η; PK ), not the continuous Aw (η). Third, the gap between the two attackabilities is controlled by the quality of the search procedure. Proposition 7.3 gives a deterministic sufficient condition (proxy-metric covering), Proposition 7.5 a probabilistic one (density-bounded random sampling), and Proposition 7.7 a structural one (one-dimensional search along the readout-specific direction rw (x)). Each gives a different way to certify, within the linearised local chart, that finite search faithfully approximates the continuous adversary. A practical attack that targets the readout direction rw (x), samples densely along the corresponding interval, and reports both successful and unsuccessful flips gives an empirical certificate that the continuous theory can interpret. Attacks that do not specify their search structure produce numbers that are difficult to compare across studies and that the continuous theory cannot underwrite.

Empirical verification

This section examines how the geometric quantities of the preceding sections behave on a deployed financial sentiment classifier. The theory rests on a continuous local relaxation of a discrete paraphrase space, and its guarantees are stated in terms of the Jacobians JM and JP , the attackability index λ∗ (x), and the adjusted margin. We report five experiments, instantiated across two local charts. Experiment 1 computes λ∗ (x) and the readout-direction sensitivity Σw (x) across inputs and tests the inequality Σw (x) ≤ λ∗ (x) of Theorem 3.3; it serves both as a numerical check on the Jacobian and generalised-eigenvalue pipeline and as a measurement of the slack ratio λ∗ (x)/Σw (x), which controls the looseness of the readout-free certificate of Corollary 3.4 and of the margin-tail bound of Theorem 4.2. Experiment 2 compares the linearised flip threshold η = Zw (x) of Theorem 3.1 against the realised nonlinear displacement along the same worst-case direction, calibrating the budget range over which the first-order model of Theorem 3.2 is informabn,w (η) and the deterministic tive. Experiment 3 estimates the empirical attackability curve A empirical-inclusion overlays implied by Theorem 4.2 and Remark 4.3, and compares it with the concentration rate of Theorem 4.4. Experiment 4 evaluates finite-search attackability against the candidate budget K, together with a one-dimensional coverage diagnostic and a best-of-all-candidates oracle, making explicit the failure-to-certify asymmetry of Section 7. Experiment 5 tests whether the adjusted margin Zw (x) predicts realised paraphrase flips. Experiments 1 and 3 are run in both charts; Experiment 2 in the soft-token chart only; Experiments 4 and 5 in the paraphrase-cloud chart. The theory is built on continuous local charts, but text is discrete. We therefore evaluate two procedures for instantiating these charts from the paraphrase space X . In Section 8.2, x ∈ X is represented as a sequence of one-hot token vectors and relaxed to soft distributions over the vocabulary, a continuous relaxation of discrete text inputs underlying gradient-based text attacks (Guo et al., 2021; Jang et al., 2017); the latent coordinate u ∈ U parametrises perturbations of those soft tokens, and the Jacobians are computed by automatic differentiation (Baydin et al., 2018) rather than estimated. In Section 8.3, we generate real paraphrases of x, embed each under M and P , and fit a local linear model, the finite-search regime of Section 7. Section 8.1 fixes the shared setup.

8.1

Experimental setup

The target model M is FinBERT (Araci, 2019), a financial sentiment classifier, whose head is a single affine layer on its pooled representation. The local results of Sections 3–6 depend on the target map eM only through its Jacobian JM , so we take eM (x) to be the raw pooled representation rather than its ℓ2 -normalisation; the readout (w, b) is then exactly the deployed FinBERT head, read off the model rather than imposed. The proxy

model P is the all-MiniLM-L6-v2 Sentence-BERT embedder (Reimers and Gurevych, 2019), whose output is mean-pooled and ℓ2 -normalised in the standard way and defines the semantic budget through the proxy distance dP . Since eP is unit-normalised, ∥eP (x) − eP (x′ )∥22 = 2 − 2 cos(eP (x), eP (x′ )), so the proxy ball {x′ : dP (x, x′ ) ≤ η} coincides with the cosine threshold {x′ : cos(eP (x), eP (x′ )) ≥ 1 − η 2 /2}. Both models share FinBERT’s WordPiece vocabulary, so the soft-token chart of Section 8.2 can parametrise a single latent coordinate feeding both embedding maps, a construction that is well defined only because the two models tokenise text over a common vocabulary. The embedding dimensions are dM = 768 and dP = 384 and so, as the theory permits, do not coincide. Inputs are drawn from the all-agreement subset of the Financial PhraseBank (Malo et al., 2014), on which all annotators assign the same sentiment label. The three sentiment classes of “Positive”, “Negative” and “Neutral”, are handled through a logit-gap construction. At a labelled example with true class t, we apply the binary affine analysis of Sections 3–6 to the effective readout w := wt − wi⋆ and b := bt − bi⋆ , where {(wi , bi )}3i=1 are the rows of the deployed FinBERT classification head and i⋆ ∈ arg min (wt − wi )⊤ eM (x) + (bt − bi ) i̸=t

is the closest competing class. The induced score w⊤ eM (x) + b is then the smallest gap between the true-class logit and any competing-class logit, and a sign change in this score is a prediction flip in the multiclass classifier; logit-gap objectives of this form are standard in adversarial-attack design (Carlini and Wagner, 2017). We sample 200 sentences uniformly without replacement from the all-agreement subset and retain the n = 190 on which FinBERT’s hard prediction matches the labelled sentiment, so that a realised paraphrase flip is unambiguously a flip away from the base prediction. The empirical attackability curve then concentrates around its population counterpart at the Dvoretzky–Kiefer–Wolfowitz rate of p √ Theorem 4.4, fixing the band half-width in Figure 3a at ln(2/δ)/2n = 1.36/ n ≈ 0.099 for δ = 0.05. The paraphrase-cloud construction of Section 8.3 is evaluated on the n′ = 185 inputs for which the cloud displacement pencil is non-degenerate and at least one paraphrase √ survives filtering, giving a half-width 1.36/ n′ ≈ 0.100 in Figure 3b. The proxy budget η is swept over a grid and reported as a fraction of the median proxy distance dP (x, x′ ) between an input and its generated paraphrases, so that η is interpretable on the scale of genuine paraphrasing rather than in raw embedding units. Proxynull directions are regularised by replacing B with B + νI, as discussed after (2.11) in Section 2.1, with ν = 10−3 tr(B)/q; we verify that reported quantities are stable as ν ranges over [10−4 , 10−2 ] tr(B)/q. Because νI is referred to the coordinate frame, the regularized pencil (A, B + νI) is not reparameterisation-invariant, so the reported λ∗ (x) and Σw (x) are coordinate-dependent approximations to the intrinsic quantities of Proposition 2.4. They are recovered as ν → 0 on non-degenerate inputs, and their stability across the stated ν range indi27

cates that the approximation does not affect the conclusions. Confidence bands use δ = 0.05. Jacobians are obtained by automatic differentiation in PyTorch, and the generalised eigenproblems for the pencil (A, B) in (2.12) are solved with a symmetric-definite solver applied to (A, B + νI). The local coordinate dimension q is method-specific and is fixed in Sections 8.2 and 8.3.

8.2

Soft-token relaxation

The chart instantiates the local model of Section 2.1 via a continuous relaxation of the discrete token sequence in the spirit of Gumbel–softmax adversarial decoding (Jang et al., 2017; Guo et al., 2021). GBDA samples from a Gumbel–softmax distribution to support stochastic gradient updates on the parameter matrix; we use the deterministic softmax at the basepoint u = 0 because our use of the relaxation is to compute Jacobians of EM , EP , not to sample adversarial candidates. Let V denote the common WordPiece vocabulary, with cardinality |V|. For an input of length L WordPiece tokens, let ℓ(0) ∈ RL|V| be a stack of position-wise (0) logit vectors initialised so that softmax(ℓi ) is a sharp approximation to the one-hot encoding of the original token at position i; concretely we set the logit of the original token to τ = 20 and all other entries to zero, which places mass e20 /(e20 + |V | − 1) ≈ 0.99994 on the original token over FinBERT’s WordPiece vocabulary (|V | = 30, 522), so the basepoint faithfully approximates the one-hot encoding. Each model m ∈ {M, P } ingests the soft-token sequence (m) through its own WordPiece embedding Etok : V → Rhm , (m) Tei (ℓ) =

(m)

softmax(ℓi )v Etok (v).

v∈V

The soft distribution softmax(ℓi ) is shared between the two models because they tokenise over a common vocabulary; the embedding matrices that follow are model-specific. The local coordinate u ∈ Rq parametrises perturbations of ℓ via ℓ(u) = ℓ(0) + Gu,

(8.1)

where G ∈ RL|V|×q has orthonormalised columns and is drawn independently for each input, so the measured geometry reflects directions adapted to each sentence rather than a single fixed random slice. The composition with the rest of M and P defines the smooth local maps EM (u) and EP (u) of Lemma 2.1, and the Jacobians JM (0) and JP (0) are obtained in closed form by forward-mode Jacobian–vector products on the columns of G, requiring q forward passes per input through each model. We report results at q ∈ {32, 64, 128} and verify qualitative stability across this range; the figures use q = 32. Experiment 2 is the single exception to τ = 20. At the near-one-hot basepoint the softmax Jacobian is vanishingly small, so β = λmin (B + νI) collapses and the worst-case direction leaves the chart’s first-order regime at budgets far below any genuine paraphrase. We therefore 28

evaluate the linearisation diagnostic at τ = 10 (mass ≈ 0.42 on the original token), a smoother operating point at which the first-order regime is resolvable; Experiments 1 and 3 retain τ = 20, at which λ∗, Σw , and Zw , being scale-invariant ratios, have converged. Experiment 1 (soft-token chart): Σw (x) ≤ λ∗ (x). For each input x in the sample we form the q × q pencil (A, B + νI) from the soft-token Jacobians, solve the symmetricdefinite generalised eigenproblem to obtain λ∗ (x), and compute the readout-direction sensi⊤ w for the logit-gap readout (w, b) of Section 8.1 by solving tivity Σw (x) = w⊤ JM (B +νI)−1 JM ⊤ w and forming (J ⊤ w)⊤ y. Figure 1 plots Σ (x) the q × q symmetric system (B + νI)y = JM w M ∗ ∗ against λ (x) across the n = 190 inputs together with the line Σw = λ that upper-bounds the scatter by Theorem 3.3. The empirical distribution of the slack ratio λ∗ (x)/Σw (x) is reported as a histogram in the same figure: a slack ratio concentrated near one indicates that the deployed readout is aligned with the worst direction of the local pencil, while a larger slack indicates that worst-direction movement is largely orthogonal to the readout. Experiment 2 (soft-token chart): linearisation error. For each input we take the closed-form linearised worst direction toward the decision boundary, u⋆flip (η; x) = − sign(s0 )η

⊤w (B + νI)−1 JM p , Σw (x)

of Theorem 3.1, apply it through the nonlinear EM , and record the actual readout displacement ∆snl (η; x) := w⊤ EM (u⋆flip ) − EM (0) . p The linearised prediction at the same u⋆flip is ∆slin (η; x) = − sign(s0 ) η Σw (x). Figure 2 P plots, separately, the mean absolute nonlinear displacement n−1 i |∆snl (η; xi )| and the mean P absolute linearised displacement n−1 i |∆slin (η; xi )|, and, in a second panel, the residual |∆snl − ∆slin | normalised per input by η 2 /βi with βi = λmin (B + νI), since the aggregate mean and median otherwise confound the η-scaling with heterogeneity in 1/β. By Theorem 3.2 the normalised residual is flat in the regime where the first-order model is informative; the experiment calibrates the budget range over which this holds, rather than testing a pass-or-fail radius of validity. Experiment 3 (soft-token chart): empirical attackability curve. The attackability p margin Zw (xi ) = γw (xi )/ Σw (xi ) is computed in the soft-token chart for each of the n = 190 inputs. Figure 3a shows the empirical strict left-CDF n

Ân,w (η) =

1X 1{Zw (xi ) < η} n i=1

√ together with the Dvoretzky–Kiefer–Wolfowitz band of width 1.36/ n at δ = 0.05 from Theorem 4.4. Two families of conservative quantile bounds are overlaid, each for β ∈ {0.10, 0.25}. The readout-free bound of Theorem 4.2 uses the empirical (1 − β)-quantile Λ̂1−β of λ∗ (xi ) and is labelled λ∗ in the figure; the readout-specific bound of Remark 4.3 uses the empirical (1 − β)-quantile Σ̂1−β of Σw (xi ) and is labelled Σw . These overlays are the deterministic empirical-inclusion bound, not a finite-sample population certificate. Writing Pn for the emb 1−β for the empirical (1 − β)-quantile of λ∗ (xi ), pirical measure and Λ q p √ b 1−β ] + β, bn,w (η) = Pn [γw < η Σw ] ≤ Pn [γw < η λ∗ ] ≤ Pn [γw < η Λ A b 1−β ] ≤ β). The analogous an exact in-sample inequality (the last step because Pn [λ∗ > Λ Σw overlay uses the empirical quantile of Σw ; since Σw ≤ λ∗ it lies below the λ∗ overlay bn,w (η) is the empirical looseness of the at matching β. The gap between each overlay and A quantile relaxation.

8.3

Paraphrase-cloud estimation

The chart instantiates the local model from a finite set of generated paraphrases rather than from a parameterised relaxation. For each input x, using the attack of Can Türetken and Leippold (2026), we generate up to K paraphrases. After discarding near-duplicates and candidates outside the proxy-similarity gate, the number retained varies per input, with a median of 35 and a maximum of 40 (the generator’s per-call cap). We form the target and proxy displacement matrices K DP (x) := eP (x′k ) − eP (x) k=1 ∈ RdP ×Kx . (8.2) K th th The local coordinate is u ∈ R x , with the k unit basis vector indexing the k retained paraphrase, and the local maps are linear interpolations between x and combinations of the candidates, EM (u) − EM (0) ≈ DM (x) u, EP (u) − EP (0) ≈ DP (x) u. (8.3) K DM (x) := eM (x′k ) − eM (x) k=1 ∈ RdM ×Kx ,

The chart Jacobians are then JM (x) = DM (x) and JP (x) = DP (x), and the pullback matrices ⊤D ⊤ A = DM M and B = DP DP are K × K; the local chart dimension is q = Kx . The two charts of Sections 8.2 and 8.3 yield different Jacobians and therefore different numerical values of λ∗ (x) and Σw (x). By Proposition 2.4 each chart is internally invariant under reparametrisation, but the two charts test the same structural predictions of Sections 3–4 rather than predicting the same scalars. Experiment 1 (cloud chart): Σw (x) ≤ λ∗ (x). We repeat Experiment 1 in the cloud ⊤ D , D ⊤ D + νI). Figure 1b plots Σ (x) against chart, using the cloud-chart pencil (DM w M P P λ∗ (x) across the n′ = 185 inputs. The comparison with Figure 1 is the substantive content: a 30

slack ratio concentrated more tightly near one in the cloud chart than in the soft-token chart indicates that the paraphrase generator is biased towards directions that move the readout, whereas a wider distribution indicates that the generator explores directions that the worstcase local geometry would not target. Experiment 3 (cloud chart): attackability curve. We repeat Experiment 3 in the cloud chart and overlay Ân,w (η), its DKW band, and the readout-free and readout-specific quantile bounds of Theorem 4.2 and Remark 4.3 (labelled λ∗ and Σw , each for β ∈ {0.10, 0.25}) on Figure 3b. Two qualitative outcomes are diagnostic. If the cloud-chart Ân,w tracks the softtoken Ân,w of Section 8.2 within their respective DKW bands, the two relaxations agree on the attackability of the deployed classifier. If the two curves disagree, the disagreement isolates the contribution of the paraphrase generator’s inductive biases relative to a model-agnostic local relaxation. Experiment 4 (cloud chart): finite-search flip events. For each input we compute the linearised prediction 1{Zw (x) < η} in the full cloud chart. The finite-search flip event fin (x; w, b) ≥ γ (x)} of Section 7 is then evaluated on subsampled candidate sets P (x) ⊆ 1{DK,η w K PKx (x) for K ∈ {4, 8, 12, 18, 25}, with each subsample drawn uniformly without replacement. Figure 4 reports the finite-search attackability n

Afin w (η; PK ) :=

1X fin 1{DK,η (xi ; w, b) ≥ γw (xi )} n i=1

as a function of η for each K. We report Afin w (η; PK ) for K ∈ {4, 8, 12, 18, 25} and a best-ofall-candidates oracle that uses each input’s full retained set, together with a one-dimensional coverage diagnostic: the median over inputs of the largest gap, normalised by η, between consecutive proxy-valid candidate positions along the readout-aligned direction rw (x) of Proposition 7.7. Subsampling cannot establish a proxy-ball cover, i.e., the candidate count for a fixed-radius cover of a q-dimensional ball grows exponentially in q, so the finite-search curve bn,w , and we present the result as the failure-to-certify asymmetry is not expected to reach A of Section 7, a found attack is evidence of vulnerability; a failed finite search is weak evidence bn,w is the linearised of robustness, rather than as confirmation of Proposition 7.3. Because A curve and over-states realised flips (Experiment 5), the gap between it and the oracle reflects both finite coverage and first-order over-prediction; the coverage diagnostic isolates the former. Experiment 5 (cloud chart): predictive validity of Zw . The decisive test of the term attackability index is whether Zw (x) predicts realised flips. For each cloud input we record the realised FinBERT prediction of every paraphrase and define the smallest realised flip budget

as the minimum proxy distance over paraphrases whose prediction differs from the base label (∞ if none flips). Since smaller Zw means more attackable, we report the Spearman rank correlation between Zw (x) and the realised flip budget over inputs that flip, and the AUC of −Zw (x) for predicting whether a proxy-valid flip exists within budget η.

8.4

Results

We first consider Figure 1. Across all inputs and in both charts, every (λ∗ (x), Σw (x)) pair lies strictly below the diagonal Σw = λ∗ , i.e., zero violations of Σw ≤ λ∗ in the 190 softtoken inputs, confirming Theorem 3.3 pointwise under the unit-norm readout. The slack is substantial: log10 (λ∗ (x)/Σw (x)) has median ≈ 2.05 in the soft-token chart and ≈ 1.47 in the paraphrase-cloud chart, so the worst local direction typically expands the target representation one-and-a-half to two orders of magnitude more than the deployed readout does. The cloud-chart slack is smaller and more concentrated, indicating that the paraphrase generator is mildly biased toward readout-moving directions relative to the model-agnostic soft-token relaxation, though in neither chart is the ratio close to one. For the linearisation diagnostic, Figure 2, the mean nonlinear displacement tracks the linear displacement closely up to η ≈ 3 × 10−2 and then peels below it as the soft-token embedding saturates within its convex hull while the linear term keeps growing; the break is saturation of ∆snl , not Taylor blow-up. The per-input normalised residual confirms this: its median is flat across the small-budget range, the regime in which the first-order model of Theorem 3.2 is informative, and rises only as saturation sets in, while the mean is inflated by a right-skewed minority of inputs that leave the first-order regime early. bn,w (η) is sigmoidal, Figure 3 presents the empirical attackability curves. In both charts A rising from near zero to ≈ 0.76 (soft-token) and ≈ 0.97 (cloud), with DKW half-widths ±0.099 bn,w , and the Σw overlay below the and ±0.100. Both empirical-inclusion overlays lie above A λ∗ overlay at matching β, as required; but both saturate at one for small budgets, λ∗ almost immediately, Σw by η ≈ 0.2, so over most of the range they are valid but close to vacuous. bn,w and either overlay is the curve-level counterpart of the large slack The wide gap between A in Figure 1. The soft-token and cloud curves agree in shape and lie within overlapping DKW bands. bn,w at every budget and every K Finite search, Figure 4, lies below the cloud-chart A and increases monotonically in K: the per-input ceiling rises from ≈ 0.11 at K = 4 through bn,w ≈ 0.97. No ≈ 0.31 at K = 25 to ≈ 0.39 for the best-of-all oracle, against a linearised A candidate is proxy-valid below η ≈ 0.25, so all curves are zero there. The coverage panel shows the median normalised gap along rw holding at one, fully uncovered, until η ≈ 0.35 and settling near 0.83 thereafter: the candidate sets barely populate the readout-relevant axis, so the finite-search shortfall is the expected consequence of sampling geometry, the quantitative bn,w form of the failure-to-certify asymmetry of Section 7. The gap between the oracle and A 32

(a)

(b)

median = 2.05

Frequency

Σw (x)

10 Σw = λ * inputs

1.5

2.0

2.5

3.0

log10 {λ * (x)/Σw (x)}

λ (x)

(a)

(b)

median = 1.47

−1

−2

Frequency

Σw (x)

(a) Soft-token relaxation

10 Σw = λ * inputs

−1

0 1.0

1.5

2.0

2.5

log10 {λ * (x)/Σw (x)}

λ (x)

(b) Paraphrase cloud

Figure 1: Σw (x) versus λ∗ (x) across inputs (log–log), with the line Σw = λ∗ that bounds the scatter by Theorem 3.3, and the empirical distribution of log10 {λ∗ (x)/Σw (x)}. Soft-token chart n = 190; paraphrase cloud n′ = 185.

(b)

linear |Δs| nonlinear |Δs| slope 1

Residual normalised by η 2 /βi

Mean readout displacement

(a)

−1

−3

−2

mean median local reference

−7

−1

−3

proxy budget η

−2

−1

proxy budget η

1.0

0.8

Attackability

Figure 2: Local linearisation diagnostic in the soft-token chart (τ = 10). (a) mean absolute linear and nonlinear readout displacement against the proxy budget η (log–log); (b) the residual |∆snl − ∆slin | normalised per input by η 2 /βi , βi = λmin (B + νI). The flat median in (b) marks the budget range over which the first-order model is informative.

0.6 Σw incl., β = 0.10 Σw incl., β = 0.25 λ * incl., β = 0.10 λ * incl., β = 0.25 DKW band ±0.099

0.4

0.2

0.4

0.6

0.8

Σw incl., β = 0.10 Σw incl., β = 0.25 λ * incl., β = 0.10 λ * incl., β = 0.25 DKW band ±0.100

0.4

0.2

An,̂ w (η)

0.0

0.6

An,̂ w (η)

0.0 1.0

0.2

proxy budget η

0.4

0.6

0.8

1.0

proxy budget η

(a) Soft-token relaxation

(b) Paraphrase cloud

bn,w (η) against the proxy budget η, with DKW Figure 3: Empirical attackability curves A bands and the empirical-inclusion overlays of Theorem 4.2 and Remark 4.3 (β ∈ {0.10, 0.25}). (a) soft-token chart; (b) paraphrase cloud.

reflects both this coverage shortfall and the first-order over-prediction quantified next, so we read the asymmetry from the coverage diagnostic rather than from that gap alone.

0.8

(a)

K=4 K=8 K = 12 K = 18

K = 25 K = 40 (oracle)

1.0

Normalised coverage gap along rw

Finite-search attackability

1.0

linearised An,̂ w

0.6

0.4

0.2

0.0

0.8

0.6

0.4

0.2

0.0 0.2

0.4

0.6

0.8

1.0

proxy budget η

(b)

uncovered median gap

0.2

0.4

0.6

0.8

1.0

proxy budget η

Figure 4: Finite-search attackability in the cloud chart against the proxy budget η. (a) Afin w (η; PK ) for K ∈ {4, 8, 12, 18, 25} and the best-of-all-candidates oracle, against the linbn,w ; (b) median normalised coverage gap along the readout-aligned direction rw (x). earised A Finally, the predictive-validity test, Figure 5, confirms that Zw orders attackability as intended: the Spearman correlation between Zw (x) and the smallest realised flip budget is ρ = 0.58 (n = 184), and the AUC of −Zw for predicting a realised flip within the median budget is 0.91. Every input lies above the identity, so the linearised Zw systematically understates the realised flip budget (the saturation seen in Figure 2) and Zw should be read as a ranking index of attackability rather than as a pointwise predictor of the realised budget.

(a)

1.0

(b)

0.8

AUC / flip rate

Smallest realised flip budget

Spearman ρ = 0.58 (n = 184)

−1

0.6

0.4

no skill AUC of −Zw realised flip rate

AUC = 0.91 at η = 0.468

0.2

−2

identity

−2

−1

0.0 0

0.2

0.4

0.6

0.8

1.0

proxy budget η

Zw (x)

Figure 5: Predictive validity of Zw in the cloud chart. (a) smallest realised flip budget versus Zw (x) with the identity line; (b) AUC of −Zw and the realised flip rate against the proxy budget η.

Discussion

The main contribution of the paper is the identification of the local geometric object that controls semantic attackability in a two-embedding setting. The matrix pencil (A(x), B(x)) describes how target and proxy embeddings assign length to the same local paraphrase directions, while the target-space matrix S(x) = JM (x)B(x)−1 JM (x)⊤ is the object seen by an affine readout. The former gives the worst-direction displacement λ∗ (x); the latter gives the readout-specific displacement Σw (x) = w⊤ S(x)w and hence the adjusted margin. The statistical bounds in the paper serve different purposes. The DKW bound in Section 4 is sharp and simple, but applies to a single fixed readout. The VC bound in Section 5 is fully distribution-free and uniform over data-dependent affine readouts. The elementary lifting in Proposition 5.2 gives an order-d2 bound by representing the attackability event as a quadratic feature lift, and the polynomial-threshold argument in Proposition 5.3 sharpens this to order d. The margin bounds in Section 6 are more scale-sensitive: they depend on p the empirical distribution of yfθ (x) − η w⊤ S(x)w and on norm, tail, or trace control of the local sensitivity. The covering-number version is explicit but dimension-dependent, whereas the Rademacher version replaces the ambient dimension by the empirical trace sensitivity P n−1 i tr S(Xi ). This mirrors the usual distinction between hard-indicator VC bounds and margin-based generalisation bounds. Empirically, the experiments in Section 8 confirm the paper’s central claims on a deployed classifier. The pointwise inequality Σw (x) ≤ λ∗ (x) of Theorem 3.3 holds without exception in both charts, and the attackability margin Zw (x) is empirically predictive of vulnerability: 36

it separates inputs that admit a proxy-valid flip from those that do not with AUC ≈ 0.91, and ranks inputs by realised flip budget at Spearman’s ρ ≈ 0.58, i.e., direct evidence that the local geometry identifies where the deployed model is fragile, and support for reading Zw as a screening index rather than, given the saturation of Figure 2, a pointwise predictor of the exact budget. The remaining findings sharpen this picture rather than qualify it. The one-and-ahalf to two orders of magnitude of slack between λ∗ (x) and Σw (x) shows that FinBERT’s readout sits far from the worst local paraphrase direction; this is precisely why the readoutfree certificate of Corollary 3.4 and the margin-tail bound of Theorem 4.2 are conservative on FinBERT, and why the adjusted margin is built from the readout-specific S(x), whose quantile bound (Remark 4.3) is correspondingly tighter. Likewise, the gap between finite search and the linearised attackability curve is the failure-to-certify asymmetry of Section 7 made quantitative: the candidate clouds barely populate the readout-relevant direction (oracle ≈ 0.39 against a linearised ≈ 0.97), so a failed search certifies robustness only against its own candidate set. The conservative quantities are conservative for reasons the theory names in advance, while the quantity the theory proposes for diagnosis, Zw , predicts realised attacks. Several limitations remain. First, the theory is local and first-order. The nonlinear error terms in Theorem 3.2 must be small for the linearised certificate to be predictive at a finite budget. Second, the local charts and metric matrices are assumed as part of the model; the paper does not prescribe a particular procedure for estimating them from a discrete paraphrase space. Third, finite paraphrase search gives explicit attacks when it succeeds, but failure of a finite search procedure is only a certificate relative to the generated candidate set unless a coverage condition such as Proposition 7.3 is available. Several natural extensions are not pursued here. One could study finite unions of attackability events to model compound fragility detectors that fire when any one of several readouts is locally attackable; the VC dimension of an m-fold union of a class with VC dimension d is at most O(dm log m) by standard results on Boolean combinations, and the corresponding generalisation bounds follow by substitution into Theorem 5.1. One could also formulate asymmetric, Neyman–Pearson-style certificates that separately control false positive and false negative declarations of fragility. Finally, nonlinear readout heads can be handled locally by replacing the affine direction with the gradient of the relevant score or logit gap, but uniform bounds for such heads would also require complexity control of the associated gradient class. These extensions would enlarge the scope of the present paper, whose focus is the geometric object S(x) and its consequences for affine readouts. The binary affine-readout assumption is mainly expositional. For multiclass linear logits, the relevant local quantity at a labelled example is the smallest gap between the true-class logit and any competing-class logit, adjusted by the worst-case proxy-bounded displacement along the corresponding gap direction. The local sensitivity matrix S(x) enters in the same way as in the binary case, contracted against each gap direction rather than against a single

readout direction, and the uniform bounds extend by the usual multiclass adjustments to the margin class.

Acknowledgments This work is supported by The London School of Economics and Political Science, and the Economic and Social Research Council (ESRC) under the “Diversity and Productivity: from Education to Work” (DAPEW) project [Grant Ref: ES/W010224/1].

References Alzantot, M., Sharma, Y., Elgohary, A., Ho, B.-J., Srivastava, M., and Chang, K.-W. (2018). Generating natural language adversarial examples. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 2890–2896, Brussels, Belgium. Association for Computational Linguistics. Anthony, M. (1995). Classification by polynomial surfaces. Discrete Applied Mathematics, 61(2):91–103. Anthony, M. and Bartlett, P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge University Press. Paperback edition 2009. Araci, D. (2019). Finbert: Financial sentiment analysis with pre-trained language models. arXiv preprint arXiv:1908.10063. Bartlett, P. L. and Mendelson, S. (2002). Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482. Baydin, A. G., Pearlmutter, B. A., Radul, A. A., and Siskind, J. M. (2018). Automatic differentiation in machine learning: a survey. Journal of Machine Learning Research, 18(153):1– 43. Can Türetken, A. and Leippold, M. (2026). Battle of transformers: Adversarial attacks on financial sentiment models. Journal of Banking & Finance, 188:107698. Carlini, N. and Wagner, D. (2017). Towards evaluating the robustness of neural networks. In 2017 IEEE symposium on security and privacy (SP), pages 39–57. IEEE. Demontis, A., Melis, M., Pintor, M., Jagielski, M., Biggio, B., Oprea, A., Nita-Rotaru, C., and Roli, F. (2019). Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. In 28th USENIX Security Symposium (USENIX Security 19), pages 321–338. 38

Goldberg, P. W. and Jerrum, M. R. (1995). Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18(2-3):131–148. Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015). Explaining and harnessing adversarial examples. In International Conference on Learning Representations. arXiv:1412.6572. Guo, C., Sablayrolles, A., Jégou, H., and Kiela, D. (2021). Gradient-based adversarial attacks against text transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 5747–5757, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics. Jang, E., Gu, S., and Poole, B. (2017). Categorical reparameterization with Gumbel-Softmax. In International Conference on Learning Representations. arXiv:1611.01144. Jin, D., Jin, Z., Zhou, J. T., and Szolovits, P. (2020). Is BERT really robust? a strong baseline for natural language attack on text classification and entailment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 8018–8025. Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018). Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations. arXiv:1706.06083. Malo, P., Sinha, A., Korhonen, P., Wallenius, J., and Takala, P. (2014). Good debt or bad debt: Detecting semantic orientations in economic texts. Journal of the Association for Information Science and Technology, 65(4):782–796. Maurer, A. (2016). A vector-contraction inequality for Rademacher complexities. In Algorithmic Learning Theory (ALT 2016), pages 3–17. Springer. Papernot, N., McDaniel, P., and Goodfellow, I. (2016). Transferability in machine learning: From phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv:1605.07277. Reimers, N. and Gurevych, I. (2019). Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP), pages 3982–3992. Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press. Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2014). Intriguing properties of neural networks. In International Conference on Learning Representations. arXiv:1312.6199. 39

Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D., and McDaniel, P. (2018). Ensemble adversarial training: Attacks and defenses. In International Conference on Learning Representations. arXiv:1705.07204. Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A. (2019). Robustness may be at odds with accuracy. In International Conference on Learning Representations. arXiv:1805.12152. Vapnik, V. N. and Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16(2):264–280. Zhang, W., Zhang, Y., Hu, X., Goswami, M., Chen, C., and Metaxas, D. N. (2022). A manifold view of adversarial risk. In International Conference on Artificial Intelligence and Statistics, pages 11598–11614. PMLR.

Proofs

A.1

Proof of Lemma 2.1

We prove the claim for a generic map E : U → S d−1 with Jacobian J at the origin. By differentiability, E(u) − E(0) = Ju + r(u), ∥r(u)∥ = o(∥u∥). Hence ∥E(u) − E(0)∥22 = ∥Ju + r(u)∥22 = u⊤ J ⊤ Ju + 2(Ju)⊤ r(u) + ∥r(u)∥22 = u⊤ J ⊤ Ju + o(∥u∥2 ). Applying this argument to EP and EM gives (2.8) and (2.9). Positive semidefiniteness follows from v ⊤ J ⊤ Jv = ∥Jv∥2 ≥ 0.

A.2

Proof of Proposition 2.2

If A = 0, then u⊤ Au = 0 for every feasible u, and the optimal value of (2.11) is 0 = η 2 λmax (B −1 A). Assume henceforth that A ̸= 0. The feasible set F := {u ∈ Rq : u⊤ Bu ≤ η 2 } is closed and, because B ≻ 0, bounded; hence compact. Continuity of u 7→ u⊤ Au then guarantees a maximiser u∗ ∈ F. Since A ⪰ 0 and A ̸= 0, some v has v ⊤ Av > 0, and rescaling v to satisfy v ⊤ Bv = η 2 produces a feasible point with strictly positive objective; hence u∗⊤ Au∗ > 0, and in particular u∗ ̸= 0. If u∗⊤ Bu∗ < η 2 , choose α > 1 with α2 u∗⊤ Bu∗ = η 2 ; then αu∗ is feasible with (αu∗ )⊤ A(αu∗ ) = α2 u∗⊤ Au∗ > u∗⊤ Au∗ , contradicting optimality. Therefore u∗⊤ Bu∗ = η 2 , and u∗ also maximises the equality-constrained problem max u⊤ Au

u∈Rq

subject to

u⊤ Bu = η 2 .

(A.1)

The constraint function g(u) := u⊤ Bu − η 2 has gradient ∇g(u) = 2Bu, which is nonzero whenever u ̸= 0, so the constraint is regular at u∗ . The Lagrange multiplier theorem applied to the Lagrangian L(u, µ) := u⊤ Au − µ(u⊤ Bu − η 2 ) (A.2) gives µ ∈ R such that ∇u L(u∗ , µ) = 0, that is, Au∗ = µBu∗ ,

(A.3)

the generalised eigenvalue equation for the pencil (A, B). Left-multiplying (A.3) by u∗⊤ and using the active constraint gives u∗⊤ Au∗ = µη 2 . Hence the optimal value equals η 2 µ for some generalised eigenvalue µ of (A, B), and sup u⊤ Au ≤ η 2 µmax , u∈F

(A.4)

where µmax is the largest generalised eigenvalue. The reverse inequality follows by exhibiting a feasible point that attains it: let umax ̸= 0 satisfy Aumax = µmax Bumax , and rescale so that 2 ⊤ 2 u⊤ max Bumax = η . Then umax Aumax = µmax η , attaining the bound. Since B is invertible, Au = µBu is equivalent to B −1 Au = µu, so µmax = λmax (B −1 A). The Cholesky decomposition B = LL⊤ with L invertible, combined with the substitution z = L⊤ u, identifies the generalised eigenvalues of (A, B) with the eigenvalues of the symmetric positive semidefinite matrix L−1 AL−⊤ , so they are real and non-negative. The optimal value of (2.11) is therefore η 2 λmax (B −1 A), attained at any top generalised eigenvector of (A, B) scaled to satisfy u∗⊤ Bu∗ = η 2 .

A.3

Proof of Proposition 2.4

By the chain rule, J˜M = JM T and J˜P = JP T , which gives (2.14). If B is invertible, then (T ⊤ BT )−1 = T −1 B −1 T −⊤ , and therefore B̃ −1 Ã = (T ⊤ BT )−1 (T ⊤ AT ) = T −1 B −1 T −⊤ T ⊤ AT = T −1 B −1 AT, so (2.15) holds and B̃ −1 Ã is similar to B −1 A. Equivalently, det(Ã − λB̃) = det(T )2 det(A − λB), so the generalised eigenvalues are preserved. If Au∗ = λ∗ Bu∗ and ũ∗ = T −1 u∗ , then Ãũ∗ = T ⊤ Au∗ = λ∗ T ⊤ Bu∗ = λ∗ B̃ ũ∗ . Finally, J˜M ũ∗ = (JM T )(T −1 u∗ ) = JM u∗ .

A.4

Proof of Theorem 3.1

Fix x and use the shorthand JM = JM (x) and B = B(x) introduced in the statement of the ⊤ w. The quantity to be maximised is |a⊤ u| subject to u⊤ Bu ≤ η 2 . Under theorem. Let a = JM the B-inner product ⟨u, v⟩B = u⊤ Bv, √ √ √ a⊤ u = ⟨B −1 a, u⟩B ≤ a⊤ B −1 a u⊤ Bu ≤ η a⊤ B −1 a. p ⊤ w = Σ (x), the supremum of |w ⊤ J u| is at most η Σ (x). Since a⊤ B −1 a = w⊤ JM B −1 JM w w M If Σw (x) > 0, equality is attained at B −1 J ⊤ w u = ±η p M . Σw (x) Choosing the sign − sign(s0 ) gives the direction toward the decision boundary. If Σw (x) = 0, then a = 0 and the supremum is zero. The linearised score crosses the boundary precisely when the maximum achievable movement toward the boundary exceeds γw (x) = |s0 |, which gives (3.7). 42

A.5

Proof of Theorem 3.2

Let RM (u) := EM (u) − EM (0) − JM u. For fixed u, define the curve t ∈ [0, 1].

ϕ(t) := EM (tu),

Assume that the line segment {tu : t ∈ [0, 1]} is contained in the local chart U . Since JM =

∂EM , ∂u u=0

ϕ′ (t) =

∂EM (tu)u ∂u

the chain rule gives

and ϕ′′ (t) =

∂ 2 EM (tu)[u, u], ∂u2

where

∂ 2 EM (v) : Rq × Rq → RdM ∂u2 is the second derivative of EM with respect to the local coordinate u, interpreted as a bilinear map. Using the fundamental theorem of calculus twice, applied componentwise to the vectorvalued curve ϕ, we have Z 1 ′ ϕ(1) − ϕ(0) − ϕ (0) = {ϕ′ (s) − ϕ′ (0)} ds 0 Z 1Z s ϕ′′ (t) dt ds = 0 0 Z 1 = (1 − t)ϕ′′ (t) dt. 0

Therefore, Z 1 (1 − t)

RM (u) = 0

∂ 2 EM (tu)[u, u] dt. ∂u2

For η > 0, define Uη := {tu : t ∈ [0, 1], u⊤ Bu ≤ η 2 }. For η sufficiently small, Uη ⊂ U . Define CM := sup v∈Uη

where

∂ 2 EM , (v) ∂u2 bil

∂ 2 EM ∂ 2 EM (v) := sup (v)[a, b] . 2 ∂u ∂u2 ∥a∥2 ≤1, ∥b∥2 ≤1 bil 2 43

Since EM is C 2 , this quantity is finite for sufficiently small η. Hence Z 1 ∂ 2 EM (1 − t) (tu)[u, u] dt ∥RM (u)∥2 ≤ ∂u2 0 2 Z 1 (1 − t)CM ∥u∥22 dt ≤ 0

CM = ∥u∥22 . 2 Therefore, using Cauchy–Schwarz and ∥w∥2 = 1, rM (η) =

w⊤ {EM (u) − EM (0) − JM u}

sup u⊤ Bu≤η 2

|w⊤ RM (u)|

sup u⊤ Bu≤η 2

≤

∥w∥2 ∥RM (u)∥2

sup u⊤ Bu≤η 2

≤

CM sup ∥u∥22 . 2 u⊤ Bu≤η2

Since B ≻ 0, let β := λmin (B) > 0. Then B ⪰ βI, so u⊤ Bu ≥ β∥u∥22 . Thus, on the feasible set u⊤ Bu ≤ η 2 , ∥u∥22 ≤

η2 . β

Substituting gives rM (η) ≤

CM η 2 = O(η 2 /β), 2β

η ↓ 0.

The same argument applied to EP gives, with RP (u) := EP (u) − EP (0) − JP u, the bound ∥RP (u)∥2 ≤ where CP := sup v∈Uη

CP ∥u∥22 , 2

∂ 2 EP . (v) ∂u2 bil

Consequently, |∥EP (u) − EP (0)∥2 − ∥JP u∥2 | ≤ ∥RP (u)∥2 ≤ 44

CP ∥u∥22 . 2

Since ∥JP u∥22 = u⊤ JP⊤ JP u = u⊤ Bu, replacing the exact proxy displacement ∥EP (u) − EP (0)∥2 by its linearised version (u⊤ Bu)1/2 incurs a second-order error in ∥u∥2 . This proves the claimed finite-radius error bound.

A.6

Proof of Theorem 3.3

Set C = JM B −1/2 . Then Σw (x) = w⊤ CC ⊤ w. For unit w, the Rayleigh quotient bound gives Σw (x) ≤ λmax (CC ⊤ ). The nonzero eigenvalues of CC ⊤ and C ⊤ C coincide, and ⊤ C ⊤ C = B −1/2 JM JM B −1/2 = B −1/2 AB −1/2 .

Therefore λmax (CC ⊤ ) = λmax B −1/2 AB −1/2 = λ∗ (x), ⊤. which proves (3.8). Equality holds when w is a top eigenvector of CC ⊤ = JM B −1 JM

A.7

Proof of Theorem 4.2

By Theorem 3.3, Σw (x) ≤ λ∗ (x) whenever Theorem 3.1 applies. If Zw (x) < η and λ∗ (x) ≤ Λ, then p p √ γw (x) < η Σw (x) ≤ η λ∗ (x) ≤ η Λ. Thus

√ {Zw (x) < η} ⊆ {γw (x) < η Λ} ∪ {λ∗ (x) > Λ}.

Taking probabilities gives (4.3). The almost-sure bounded case and the quantile form are immediate specialisations.

A.8

Proof of Theorem 4.4

For fixed (w, b), the random variables Zw (x1 ), . . . , Zw (xn ) are i.i.d. with left-limit distribution function FZ−w (η) = Aw (η). The empirical curve Ân,w is the corresponding empirical distribution function with strict threshold. The Dvoretzky–Kiefer–Wolfowitz inequality with Massart’s sharp constant gives, for every ϵ > 0, P sup Ân,w (η) − Aw (η) > ϵ ≤ 2 exp(−2nϵ2 ). η>0

Setting the right-hand side equal to δ and solving for ϵ gives (4.7). 45

A.9

Proof of Theorem 5.1

Write P for expectation under the population distribution of X and Pn for the empirical measure. For each pair (θ, η), the function Gθ,η is binary-valued, and Pn Gθ,η = Abn,θ (η),

P Gθ,η = Aθ (η).

Therefore the left-hand side of (5.3) is exactly sup |(Pn − P )g|. g∈GΘ

The standard VC uniform convergence inequality for a binary class of VC dimension v gives, with probability at least 1 − δ, r v log(en) + log(1/δ) , sup |(Pn − P )g| ≤ C n g∈GΘ for a universal constant C; see, for example, Vapnik and Chervonenkis (1971) or Anthony and Bartlett (1999). Substituting the identities above gives the result. The point of the theorem is that the supremum is taken over both the readout θ and the budget η, so the bound remains valid even if the readout is selected in a data-dependent way.

A.10

Proof of Proposition 5.2

Fix (θ, η), with θ = (w, b). Let z̃(x) := (z(x), 1) ∈ RdM +1 ,

w̃ := (w, b) ∈ RdM +1 .

The attackability event is |w⊤ z(x) + b| < η

w⊤ S(x)w.

Since S(x) ⪰ 0, the expression under the square root is nonnegative. Both sides of the strict inequality are therefore nonnegative, and squaring is an equivalent transformation; the case w⊤ S(x)w = 0 is handled the same way, since then both the original and the squared inequalities fail trivially. Hence the event is equivalently (w̃⊤ z̃(x))2 − η 2 w⊤ S(x)w < 0.

(A.5)

We now write the quadratic comparison as a linear threshold after an explicit feature lift. This is the same elementary lifting used for classification by polynomial surfaces, specialized here to degree two and augmented with the entries of S(x) (Anthony, 1995). Write zi (x) for the coordinates of z(x) and Sij (x) for the entries of S(x). Define Ψ(x) := 1, z1 (x), . . . , zdM (x), zi (x)zj (x) 1≤i≤j≤d , M

Sij (x) 1≤i≤j≤d ∈ Rm . M

(A.6)

This feature vector consists of a constant coordinate, the ordinary embedding coordinates, their distinct quadratic products, and the distinct entries of S(x). Expanding the two terms in (A.5) gives (w⊤ z(x) + b)2 − η 2 w⊤ S(x)w 2

= b + 2b

d X

wi zi (x) +

i=1

−η

dM X

d X i=1

wi wj zi (x)zj (x)

1≤i<j≤d

wi2 Sii (x) − 2η 2

i=1

wi2 zi (x)2 + 2

wi wj Sij (x).

1≤i<j≤dM

Therefore there is a coefficient vector aθ,η ∈ Rm , depending only on (w, b, η), such that (w⊤ z(x) + b)2 − η 2 w⊤ S(x)w = a⊤ θ,η Ψ(x). Equivalently, (A.5) is precisely a⊤ θ,η Ψ(x) < 0. Thus each attackability indicator in GΘ is the pullback, by Ψ, of a homogeneous linear threshold in Rm . It remains only to count the dimension of the lifted feature space. The feature map Ψ has one constant coordinate, dM linear embedding coordinates, dM (dM + 1) 2 distinct quadratic products zi (x)zj (x), and dM (dM + 1) 2 distinct entries of the symmetric matrix S(x). Hence m = 1 + dM +

dM (dM + 1) dM (dM + 1) + = (dM + 1)2 . 2 2

m Each indicator Gθ,η ∈ GΘ takes the form 1{a⊤ θ,η Ψ(x) < 0} for some aθ,η ∈ R depending on (θ, η). Therefore GΘ is contained in the class of homogeneous linear threshold sets on the lifted feature Ψ(x). Since VC dimension is monotone under set inclusion, VC(GΘ ) is at most that of the ambient class of homogeneous halfspaces in Rm , which is at most m (one less than the bound m + 1 for inhomogeneous halfspaces). Therefore

VC(GΘ ) ≤ m = (dM + 1)2 .

A.11

Proof of Proposition 5.3

By the squaring in the proof of Proposition 5.2 (equation (A.5)), the attackability event is equivalent to (w⊤ z(x) + b)2 − η 2 w⊤ S(x)w < 0. Set λ = η 2 ; the event becomes λ w⊤ S(x)w − (w⊤ z(x) + b)2 > 0, so GΘ is contained in the class indexed by (w, b, λ) ∈ RdM +2 defined by this single inequality, and VC dimension is monotone under inclusion. Represent an instance by T (x) = z(x), Sij (x) 1≤i≤j≤d . M

The membership condition is a single polynomial inequality. Expanding, λ w⊤ S(x)w − (w⊤ z(x) + b)2 =

λ wi wj Sij (x) −

i,j

wi wj zi (x)zj (x) − 2b

i,j

wi zi (x) − b2 ,

and, counting the concept variables (w, b, λ) and the entries of T (x) together, the monomials λ wi wj Sij (x) and wi wj zi (x)zj (x) each have degree 4, while b wi zi (x) has degree 3 and b2 degree 2; the total degree is therefore 4. By Goldberg and Jerrum (1995, Theorem 2.2), VC(GΘ ) ≤ 2(dM + 2) log2 (8e · 4 · 1) = 2(dM + 2) log2 (32e). This bound is set by the number of parameters dM + 2, the single predicate, and the degree 4, not by the number of entries of T (x), so VC(GΘ ) = O(dM ).

A.12

Proof of Corollary 5.4

Combine Theorem 5.1 with Proposition 5.3. The proposition supplies the bound VC(GΘ ) = O(dM ); substituting this into (5.3) and absorbing numerical constants into C gives (5.5).

A.13

Proof of Theorem 6.1

Proof. The proof uses a covering-number notation different from the one in Proposition 6.2. There, N∞ (ϵ, F) denoted the full-domain supremum-norm covering number, defined through the distance d∞ (f, g) = supz∈Z |f (z) − g(z)| over the whole domain. Theorems 10.4 and 12.13 of Anthony and Bartlett (1999) are instead stated in terms of an empirical supremum-norm covering number, which we now define. For a class F of real-valued functions on a domain Z, a positive integer N , and ϵ > 0, the empirical supremum-norm covering number is N∞ (ϵ, F, N ) :=

sup

N (ϵ, F, (z1 , . . . , zN )),

(z1 ,...,zN )∈Z N

where N (ϵ, F , (z1 , . . . , zN )) is the smallest cardinality of a finite set C ⊆ F such that for every f ∈ F there is a g ∈ C with maxi≤N |f (zi )−g(zi )| ≤ ϵ. The empirical version is bounded above by the full-domain version, N∞ (ϵ, F, N ) ≤ N∞ (ϵ, F), but is in general much smaller. The

third argument N distinguishes the empirical version from the full-domain version N∞ (ϵ, F) of Section 6. The proof proceeds in three steps. First, apply the margin-covering theorem of Anthony and Bartlett (1999, Theorem 10.4) to the class Mη at scale ρ. For every ϵ > 0, 2 n o ϵ n b . P ∃θ ∈ Θ : Rη (θ) > Rn,η,ρ (θ) + ϵ ≤ 2N∞ (ρ/2, πρ (Mη ), 2n) exp − 8 Here πρ is the clipping map of Anthony and Bartlett (1999, Section 10.4), which restricts function values to a ρ-neighbourhood of the decision threshold (zero in our margin convention); the empirical covering number on the right-hand side is taken over samples of size 2n, as required by the symmetrisation argument in the proof of Theorem 10.4. Second, the fat-shattering covering estimate of Anthony and Bartlett (1999, Theorem 12.13) bounds this empirical covering number in terms of the fat-shattering dimension of πρ (Mη ) at scale ρ/8. Since clipping does not increase the fat-shattering dimension, fatρ/8 (πρ (Mη )) ≤ fatρ/8 (Mη ) = dρ , and Theorem 12.13 gives log N∞ (ρ/2, πρ (Mη ), 2n) ≤ Cdρ log2 (CM n/ρ) for a universal constant C, after absorbing numerical constants. Third, set r 8 ϵ= (log N∞ (ρ/2, πρ (Mη ), 2n) + log(2/δ)). n This choice makes the displayed probability at most δ. Substituting the covering estimate from the second step into this expression for ϵ and absorbing universal numerical constants into C gives, with probability at least 1 − δ, uniformly over θ ∈ Θ, s 2 bn,η,ρ (θ) + C dρ log (CM n/ρ) + log(1/δ) , Rη (θ) ≤ R n which is (6.5).

A.14

Proof of Proposition 6.2

Fix two readouts θ = (w, b) and θ′ = (w′ , b′ ). For any labelled point (x, y), the difference between the adjusted margins is bounded by mη,θ (x, y) − mη,θ′ (x, y) ′

′

≤ ∥z(x)∥2 ∥w − w ∥2 + |b − b | + η

w⊤ S(x)w −

w′⊤ S(x)w′ .

The first two terms are the ordinary Lipschitz bound for affine scores. For the adversarial displacement term, use S(x) ⪰ 0 and ∥S(x)∥op ≤ Λ. Then q w⊤ S(x)w = ∥S(x)1/2 w∥2 , 49

and by the reverse triangle inequality, q q ⊤ w S(x)w − w′⊤ S(x)w′ = ∥S(x)1/2 w∥2 − ∥S(x)1/2 w′ ∥2 √ ≤ ∥S(x)1/2 (w − w′ )∥2 ≤ Λ∥w − w′ ∥2 . Using ∥z(x)∥2 ≤ R, we obtain the uniform Lipschitz bound √ mη,θ (x, y) − mη,θ′ (x, y) ≤ (R + η Λ)∥w − w′ ∥2 + |b − b′ |. √ Set L := R + η Λ. If the w-parameters are covered at Euclidean radius ϵ/(2L) and the bias interval is covered at radius ϵ/2, then the corresponding adjusted-margin functions are covered in supremum norm at radius ϵ. The Euclidean ball {w : ∥w∥2 ≤ W } ⊂ RdM has an ϵ/(2L)-net of size at most 4W L dM 1+ , ϵ by the standard volumetric covering bound. The interval [−B0 , B0 ] has an ϵ/2-net of size at most 4B0 1+ . ϵ Multiplying the two covering numbers gives (6.6). Finally, for any θ ∈ ΘW,B0 , q √ |mη,θ (x, y)| ≤ |w⊤ z(x)| + |b| + η w⊤ S(x)w ≤ W R + B0 + ηW Λ = Mη , which proves (6.7).

A.15

Proof of Corollary 6.3

We apply the margin-covering theorem of Anthony and Bartlett (1999, Theorem 10.4) to the adjusted-margin class Mη at scale ρ, exactly as in the proof of Theorem 6.1. The bound there is stated in terms of the empirical supremum-norm covering number N∞ (ρ/2, πρ (Mη ), 2n), which is bounded above by the full-domain covering number N∞ (ρ/2, Mη ) of Proposition 6.2 (clipping a cover of Mη gives a cover of πρ (Mη ), and the empirical version is dominated by the full-domain version). Substituting the covering bound of Proposition 6.2 at scale ρ/2 into Theorem 10.4 and calibrating as in the proof of Theorem 6.1 gives, with probability at least 1 − δ, uniformly over θ ∈ ΘW,B0 , r bn,η,ρ (θ) + C log N∞ (ρ/2, Mη ) + log(1/δ) . Rη (θ) ≤ R n Proposition 6.2 gives √ ! 8W (R + η Λ) 8B0 log N∞ (ρ/2, Mη ) ≤ dM log 1 + + log 1 + , ρ ρ and absorbing numerical constants into the universal constant C yields (6.8). 50

A.16

Proof of Theorem 6.4

Let L := {(x, y) 7→ y(w⊤ z(x) + b) : (w, b) ∈ ΘW,B0 } and Q := {x 7→

w⊤ S(x)w : ∥w∥2 ≤ W }.

By subadditivity of empirical Rademacher complexity, b n (Mη ) ≤ R b n (L) + η R b n (Q). R For the linear part, write w̃ = (w, b) and z̃i = (Yi z(Xi ), Yi ). Since ∥w̃∥2 ≤ " # n X 1 b n (L) = Eσ R sup σi w̃⊤ z̃i Sn (w,b)∈ΘW,B0 n i=1 p n X W 2 + B02 Eσ ≤ σi z̃i n i=1 2 !1/2 p n W 2 + B02 X ∥z̃i ∥22 ≤ n i=1 !1/2 p n W 2 + B02 X 2 . (∥z(Xi )∥2 + 1) = n

p W 2 + B02 ,

i=1

p For the sensitivity part, write Ai = S(Xi )1/2 , so that w⊤ S(Xi )w = ∥Ai w∥2 for each i. Writing hw (x) = S(x)1/2 w ∈ Rd for the vector-valued map indexed by w, the displacement p function w 7→ w⊤ S(Xi )w is the composition of the 1-Lipschitz scalar map u 7→ ∥u∥2 with the vector-valued map hw (Xi ) = Ai w. The Hilbert-space vector contraction inequality for Rademacher complexities (Maurer, 2016), applied to this composition, gives b n (Q) ≤ C Eg sup R n ∥w∥2 ≤W

n X i=1

gi⊤ Ai w,

where the gi ’s are independent standard Gaussian vectors in the target space and C is universal. Therefore n X CW b Rn (Q) ≤ Eg A⊤ i gi n i=1 2   2 1/2 n X CW   Eg A⊤ ≤ i gi n i=1

n X

CW n

!1/2 tr(A⊤ i Ai )

i=1

s = CW

Tn . n

Combining the two estimates proves (6.9). It remains to pass from a bound on the Rademacher complexity of Mη to a bound on the robust risk Rη (θ). Three ingredients are needed. First, the ramp loss. Let φρ : R → [0, 1] be defined by    1, t ≤ 0,   φρ (t) = 1 − t/ρ, 0 < t < ρ,    0, t ≥ ρ, which is 1/ρ-Lipschitz and takes values in [0, 1], and satisfies the two-sided inequality

1{t ≤ 0} ≤ φρ (t) ≤ 1{t ≤ ρ}. Let G = φρ ◦ Mη be the ramp-loss class. Second, the standard empirical Rademacher generalization bound for bounded losses (Bartlett and Mendelson, 2002) gives, with probability at least 1 − δ, uniformly over g ∈ G, r n 1X b n (G) + C log(1/δ) . g(Xi , Yi ) + 2R Eg(X, Y ) ≤ n n i=1

Specialising to g = φρ ◦ mη,θ for each θ ∈ Θ gives, uniformly over θ with the same probability, r n 1X b n (G) + C log(1/δ) . Eφρ (mη,θ (X, Y )) ≤ φρ (mη,θ (Xi , Yi )) + 2R n n i=1

Third, the Ledoux–Talagrand contraction inequality for Rademacher averages, applied to the 1/ρ-Lipschitz function φρ after centering (the constant φρ (0) does not affect the Rademacher average), gives b n (G) = R b n (φρ ◦ Mη ) ≤ 1 R b n (Mη ). R ρ 52

b n (Mη ) from (6.9) into the previous equation and absorbing Substituting the bound on R numerical constants into C gives, uniformly over θ ∈ ΘW,B0 , r n 1X 2b log(1/δ) Eφρ (mη,θ (X, Y )) ≤ φρ (mη,θ (Xi , Yi )) + Rn (Mη ) + C . n ρ n i=1

Finally, the two-sided ramp-loss inequality converts the expected ramp loss to the population robust risk and the empirical ramp loss to the empirical ρ-margin error: Rη (θ) = P{mη,θ (X, Y ) ≤ 0} ≤ Eφρ (mη,θ (X, Y )), n

i=1

1X 1X φρ (mη,θ (Xi , Yi )) ≤ 1{mη,θ (Xi , Yi ) ≤ ρ} = Rbn,η,ρ (θ). n n Combining these with the previous display gives (6.10). The specialisation in equation (6.11) follows from substituting the uniform bounds ∥z(x)∥2 ≤ R and tr S(x) ≤ T : n 1X (∥z(Xi )∥22 + 1) ≤ R2 + 1, T n ≤ T. n i=1

For the rank-q case, S(x) ⪰ 0 implies tr S(x) ≤ rank(S(x))∥S(x)∥op , so rank S(x) ≤ q and ∥S(x)∥op ≤ Λ together give T ≤ qΛ.

A.17

Proof of Corollary 6.6

Define the event Eβ := {(x, y) : ∥S(x)∥op ≤ Λβ }. By the choice of Λβ , P(Eβc ) ≤ β. The population robust risk decomposes as Rη (θ) = P{mη,θ (X, Y ) ≤ 0} = P{mη,θ (X, Y ) ≤ 0, (X, Y ) ∈ Eβ }+P{mη,θ (X, Y ) ≤ 0, (X, Y ) ∈ Eβc }. The second joint probability is bounded by P(Eβc ) ≤ β, so Rη (θ) ≤ P{mη,θ (X, Y ) ≤ 0, (X, Y ) ∈ Eβ } + β. It remains to bound the first joint probability. The indicator 1{mη,θ (X, Y ) ≤ 0, (X, Y ) ∈ Eβ } is a function of (X, Y ) with values in {0, 1}, and on the event Eβ the local sensitivity matrix satisfies ∥S(X)∥op ≤ Λβ by definition. The event Eβ is defined independently of the readout θ, so restricting the empirical-process argument to the subset {(X, Y ) ∈ Eβ } does not enlarge the covering number of the margin class; equivalently, one may replace each mη,θ by the modified function mη,θ · 1Eβ + M · 1Eβc , for M a constant exceeding the supremum of mη,θ on Eβc , and the covering number of the modified class at any scale is bounded by the covering 53

number of the original class restricted to Eβ , on which ∥S(X)∥op ≤ Λβ holds uniformly. The covering-number margin bound used in the proof of Corollary 6.3 therefore applies with Λ replaced by Λβ . This gives, uniformly over θ ∈ ΘW,B0 with probability at least 1 − δ, n

P{mη,θ (X, Y ) ≤ 0, (X, Y ) ∈ Eβ } ≤

1X 1{mη,θ (Xi , Yi ) ≤ ρ, (Xi , Yi ) ∈ Eβ } + ∆n,ρ,β , n i=1

where ∆n,ρ,β := C

v u √ u CW (R+η Λβ ) CB0 u d log 1 + + log 1 + + log(1/δ) ρ ρ t n

The empirical term with the additional condition (Xi , Yi ) ∈ Eβ is no larger than the empirical ρ-margin error: n

i=1

1X 1X 1{mη,θ (Xi , Yi ) ≤ ρ, (Xi , Yi ) ∈ Eβ } ≤ 1{mη,θ (Xi , Yi ) ≤ ρ} = Rbn,η,ρ (θ). n n Combining the three preceding inequalities gives bn,η,ρ (θ) + ∆n,ρ,β + β Rη (θ) ≤ R uniformly over θ ∈ ΘW,B0 with probability at least 1 − δ, which is (6.12).

A.18

Proof of Proposition 7.3

If Σw (x) = 0, both sides of the desired bound are zero and the claim is immediate. Assume henceforth that Σw (x) > 0. lin (x; w, b) The upper bound is immediate from inclusion. The candidates contributing to DK,η satisfy ∥uk ∥B(x) ≤ η, i.e., uk ∈ Bx (η), and the linearised worst-case readout displacement over p lin (x; w, b) ≤ Bx (η) is η Σw (x) by the closed-form attacker’s solution of Theorem 3.1, so DK,η p η Σw (x). For the lower bound, set p u⋆ := −σx (η − δ) B(x)−1 JM (x)⊤ w/ Σw (x). The B(x)-norm of u⋆ satisfies ∥u⋆ ∥2B(x) = u⋆⊤ B(x)u⋆ =

(η − δ)2 ⊤ w JM (x)B(x)−1 B(x)B(x)−1 JM (x)⊤ w = (η − δ)2 , Σw (x)

using σx2 = 1, the symmetry of B(x)−1 , and Σw (x) = w⊤ JM (x)B(x)−1 JM (x)⊤ w. Hence ∥u⋆ ∥B(x) = η − δ and u⋆ ∈ Bx (η − δ). A parallel computation, using the same identity for p Σw (x), gives −σx w⊤ JM (x)u⋆ = (η − δ) Σw (x).

By the covering assumption, there exists uk ∈ {u1 , . . . , uK } with ∥uk − u⋆ ∥B(x) ≤ δ. The triangle inequality gives ∥uk ∥B(x) ≤ ∥u⋆ ∥B(x) + ∥uk − u⋆ ∥B(x) ≤ (η − δ) + δ = η, so uk ∈ Bx (η) lin (x; w, b). and uk contributes to DK,η The readout displacement at uk decomposes as p −σx w⊤ JM (x)uk = (η − δ) Σw (x) − σx w⊤ JM (x)(uk − u⋆ ). To bound the second term, we apply Cauchy–Schwarz in the B(x)-inner product ⟨u, v⟩B(x) := ⊤ u B(x)v, which is a genuine inner product because B(x) ≻ 0, with induced norm ∥u∥B(x) . The covering condition is stated in this norm, so the argument has to be phrased in the same geometry. Set v := B(x)−1 JM (x)⊤ w. Then, using the symmetry of B(x)−1 , ⟨v, uk − u⋆ ⟩B(x) = v ⊤ B(x)(uk − u⋆ ) = w⊤ JM (x)(uk − u⋆ ), so the quantity to be bounded is exactly |⟨v, uk − u⋆ ⟩B(x) |. Cauchy–Schwarz in the B(x)-inner product gives |w⊤ JM (x)(uk − u⋆ )| ≤ ∥v∥B(x) · ∥uk − u⋆ ∥B(x) . The B(x)-norm of v is ∥v∥2B(x) = v ⊤ B(x)v = w⊤ JM (x)B(x)−1 JM (x)⊤ w = Σw (x), again using the same identity for Σw (x) as above. Combining with ∥uk − u⋆ ∥B(x) ≤ δ from the covering hypothesis, |w⊤ JM (x)(uk − u⋆ )| ≤

Σw (x) · ∥uk − u⋆ ∥B(x) ≤ δ

p Σw (x).

Therefore p p p lin DK,η (x; w, b) ≥ −σx w⊤ JM (x)uk ≥ (η − δ) Σw (x) − δ Σw (x) = (η − 2δ) Σw (x). lin (x; w, b) ≥ (1 − 2ϵ)η Setting δ ≤ ηϵ for ϵ ∈ (0, 1/2) gives DK,η

A.19

p Σw (x).

Proof of Corollary 7.4

lin (x; w, b) ≥ (1 − 2ϵ)η By Proposition 7.3, the covering assumption gives DK,η lin (x; w, b) < γ (x) then implies hypothesis DK,η w

(1 − 2ϵ)η which rearranges to η

p lin Σw (x) ≤ DK,η (x; w, b) < γw (x),

p Σw (x) < γw (x)/(1 − 2ϵ).

p Σw (x). The

A.20

Proof of Proposition 7.5

The argument has four steps: reduce the covering condition on the continuous ball Bx (η−δ) to a covering condition on a finite discretisation Z; bound the probability that a single random candidate u1 lands near any fixed point zi ∈ Z; amplify this per-point bound to the joint event over all K candidates using independence; and take a union bound over the N points of Z. Step 1: discretisation. Let Z = {z1 , . . . , zN } ⊆ Bx (η − δ) be a δ/2-cover of Bx (η − δ) in the proxy metric, of cardinality N := N (δ/2, Bx (η − δ)). Such a cover exists by the definition of the covering number. The point of discretising is that we want to reduce the continuous covering condition to a statement about a finite set of points zi , each of which we can analyse separately. Suppose every zi has at least one candidate within proxy-distance δ/2, that is, for every i there is some index k(i) with ∥zi − uk(i) ∥B(x) ≤ δ/2. Then for any u ∈ Bx (η − δ), choose zi with ∥u − zi ∥B(x) ≤ δ/2 (possible because Z is a δ/2-cover) and use the candidate uk(i) . The triangle inequality gives ∥u − uk(i) ∥B(x) ≤ ∥u − zi ∥B(x) + ∥zi − uk(i) ∥B(x) ≤ δ/2 + δ/2 = δ, so the candidate set δ-covers Bx (η − δ). It therefore suffices to upper-bound the probability of the failure event F := {∃ zi ∈ Z : no candidate lies within δ/2 of zi }. Step 2: hit probability for a single candidate. Fix zi ∈ Z and let Nδ/2 (zi ) := {u : ∥u − zi ∥B(x) ≤ δ/2} be the proxy ball of radius δ/2 centred at zi . This ball lies inside Bx (η), where the density floor applies: for any u ∈ Nδ/2 (zi ), the triangle inequality gives ∥u∥B(x) ≤ ∥zi ∥B(x) + ∥u − zi ∥B(x) ≤ (η − δ) + δ/2 < η. The probability that a single candidate u1 lands in this ball is therefore Z P{u1 ∈ Nδ/2 (zi )} = f (u) du ≥ c · vol Nδ/2 (zi ) , Nδ/2 (zi )

using f ≥ c throughout the integration domain. p The Lebesgue volume of Nδ/2 (zi ) is vq (δ/2)q / det B(x). To see this, write Nδ/2 (zi ) = zi + B(x)−1/2 vq -ball of radius δ/2 : the proxy ball at zi is the image of the Euclidean ball of radius δ/2 under the linear map B(x)−1/2 , translated by zi . Translations preserve Lebesgue p volume and B(x)−1/2 scales it by | det B(x)−1/2 | = 1/ det B(x). Combining, p P{u1 ∈ Nδ/2 (zi )} ≥ c · vq (δ/2)q / det B(x) = κ vq (δ/2)q , (A.7) p where κ = c/ det B(x). 56

Step 3: independence across candidates. The events {uk ∈ Nδ/2 (zi )}K k=1 are independent (the uk are i.i.d.), and each has marginal probability at least κvq (δ/2)q by (A.7). The probability that none of them lands in Nδ/2 (zi ) is therefore P{no candidate lies within δ/2 of zi } =

K Y

P{uk ∈ / Nδ/2 (zi )} ≤ 1 − κvq (δ/2)q

k=1

Step 4: union bound over discretisation points. The failure event F is the union of the N events from Step 3, one per zi ∈ Z. The union bound gives P(F ) ≤

N X

P{no candidate within δ/2 of zi } ≤ N 1 − κvq (δ/2)q

i=1

Taking complements and applying the reduction of Step 1 yields the stated inequality. The covering-number rate. The covering number N (δ/2, Bx (η − δ)) in the proxy metric is of order ((η − δ)/(δ/2))q = O((η/δ)q ) for δ ≤ η/2, by the standard volumetric bound (the ball of radius η − δ contains at most ((η − δ)/(δ/2))q disjoint balls of radius δ/4, each of volume comparable to the candidate ball). Setting K = Θ(δ −q log N ) then drives the failure probability below any prescribed level, recovering the K = Θ(δ −q log(1/δ)) rate quoted after the proposition.

A.21

Proof of Proposition 7.7

p The direction rw (x) = −σx B(x)−1 JM (x)⊤ w/ Σw (x) satisfies ∥rw (x)∥2B(x) =

w⊤ JM (x)B(x)−1 JM (x)⊤ w = 1, Σw (x)

lin (x; w, b). The so each candidate αj rw (x) with αj ∈ [0, η] lies in Bx (η) and contributes to DK,η readout displacement at αj rw (x) is

−σx w⊤ JM (x)αj rw (x) = αj ·

p w⊤ JM (x)B(x)−1 JM (x)⊤ w p = αj Σw (x). Σw (x)

By the covering assumption, the αj δ ′ -cover [0, η], so maxj αj ≥ η − δ ′ . Therefore lin DK,η (x; w, b) ≥ max αj j

p p Σw (x) ≥ (η − δ ′ ) Σw (x).

Record · ID 287132 · SHA-256 7fd78b8b64f19900
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.