Tight Generalization Bounds for Large-Margin Halfspaces
Authors: Kasper Green Larsen
Natascha Schalburg
Venue: NeurIPS 2025 spotlight ()
Keywords: Learning theory
Generalization Bounds
Large-Margin Halfspaces
Rademacher complexity
Primary area: theory
TL;DR: We prove the first generalization bound for large-margin halfspaces that is asymptotically tight.

Abstract: We prove the first generalization bound for large-margin halfspaces that is asymptotically tight in the tradeoff between the margin, the fraction of training points with the given margin, the failure probability and the number of training points.

Tight Generalization Bounds for Large-Margin Halfspaces
Kasper Green Larsen Department of Computer Science
Natascha Schalburg
Department of Computer Science
Aarhus University
Aarhus University
Aarhus, Denmark
Aarhus, Denmark
larsen@cs. .u.dk
n. s scsaschllbii burg@cs au.
Abstract
We prove the first generalization bound for large-margin halfspaces that is asymp- totically tight in the tradeoff between the margin, the fraction of training points with the given margin, the failure probability and the number of training points.
Introduction
Halfspaces are arguably among the simplest and most fundamental classic learning models. Given normal vector w E Rd and a bias b E R defining hyperplane, the corresponding halfspace classifier predicts the label data point æ E Rd by returning sign( (w, x) + b). corresponding to a +11 label on points inside the halfspace above the hyperplane, and 1 on points below.
Classic examples learning algorithms for obtaining a halfspace classifier from training set of points S = {(x;, yı }))), with (zt, 31) E Rd x {-1,1} 1]. includes the Perceptron Learning Algorithm (PLA) (Mcculloch and Pitts (1943) and Support Vector Machines (SVM) (Cortes and Vapnik (1995)). A key intuition underlying SVM, is the empirical observation that halfspaces with large margin to the training data tend to generalize well. Ignoring the bias variable (which we later handle by adding special feature) and assuming w E Sd-1 (i.e. w has unit length), the margin of the halfspace with normal vector w on labeled point (Ir, y) y(w, 2). Observe that (w. x)) gives the signed distance of from the hyperplane, and the margin is positive when sign( (w,x)) correctly predicts the label With this definition, hard-margin SVM computes the normal vector w of the hyperplane with the largest minimum margin. There are also margin variants of the Perceptron (Freund and Schapire [1999] that computes a halfspace with minimum margin approuching the optimal, as in hard- mard-margin SVM.
To handle data that is not linearly separable, and add robustness outliers, the saft-margin SVM relaxes the optimization problem to the following
min w|lm 3
Σ &
s.t. z (w, 2 1 E.. 2
Here À >> 0 is regularization parameter. The soft-margin SVM thus allows for smaller margins some training points at the cost of a penalty Ag,- For fast implementations of SVM, see Gu et al.
(025 S.d Shalev-Shwartz and Cotter [2011].
To theoretically justify and explain the empirical success of focusing on large margins, Bartlett and Shawe-Taylor [1999] proved the first generalization bounds upper bounding the probability
(D(w) : 1= (x sign( (w, x)) A y] of misclassifying the label of new data point. Concretely, Bartlett and Sahawe-Taylon first studied the hard-margin case and proved that for any distribution D
over BBd x {-1, 1} and any < < 1, it holds with probability at least - 8 over a training set
D that for every w dd-1 and every margin y 1, y(w, x) y for all (z, v) E
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

then
(n) n
In(e/6)
LD(W) se.
n
for a constant 0. Here By is the d-dimensional unit ball and 8d-1 is the d-dimensional unit sphere, both with respect the no-nomm. The restriction to [B can be relaxed by multiplying the first term by R for x E R B.. A dependency on the scaling of input points is inevitable as margins scale with ||| Throughout the paper, we state bounds for = and remark that bounds generalize to arbitrary R by replacing 7 by n/R2. R..
Defining C3 w) as the fraction of data points training set where has margin at most y. Bartlett and Shawe- Taylor [1999] also prove more general result, saying that with probability over D holds for every E 8 that
In (n) In(e/8) Co(w) & Cz(w) +c 1 2
(2)
n
This was later improved by Bartlett and Mendelson [2002] using Rademacher complexity arguments, replacing the In (n) term (empirical) margin loss.
by 1. Here, and throughout the paper, we refer C3 (w) as the
First-Order Bounds. The first work interpolate between the hard-margin and soft-margin bounds was due to McAllester 2003). who gave a general tradeoff of
(V Inn
In 7
In + In(e/5)
LD(w)= < (g(w) +c.
72n
Notice how the Lg(1)) (w) term is multiplied onto In n inside the first square-root. Since the hard-margin case corresponds this term being this gives way of interpolating between the cases. Such bounds are often referred to as first-order bounds. Unfortunately, (3) still has the seemingly superfluous / (In + (n(e/)))/n term even when (w) = 0 and thus falls short of even in the hard-margin case.
matching ①
The current state-of-the-arr generalization bound due to Grønlund et al. 2020a and states that with probability 1 - 8 over S ~ D", it holds for every w E a that
(V (rg(
In n. 2
In(e/d)
+ In
+ In(e/5)
[D(w)= (w) +
(4)
7
This improves previous hard-margin bounds by a logarithmic factor and gives a cleaner interpolation between the hard- and soft-margin cases. Furthermore, the bound is close to optimal. Concretely, the dependency on d is optimal by tweaking standard results for agnostic PAC learning, see e.g. Devroye et al. 1996 [Chapter 11]. Moreover, Grønlund et al. [2020a] complemented their upper bound by the following lower bound
Theorem 1 (Gronlund et al. (020aa).. There is a constant c > O such that for any en 1/2 < < < c any parameter () < f < 1, and any c, there is a distribution 'D such that holds with constant probability over S ~ D that there is a w E Sd-1 such that (ww) S T and
In(e/T)
In(72n)
CD(w)= 2 (w) +c.
+ 72n
P2n
In(e/L((w) (w))
In In(?2n)
2 (w) tc.
22n
2
Notice how the parameter 7 allows for showing that the upper bound is nearly tight across the range of (w)) (w). Let us also remark that Grønlund et al. [2020a] states their lower bound with a n rather than In), but require that 7 > 0.199 careful examination of their proof however reveals the more general lower bound stated here.

---

Unfortunately, there still remains discrepancy between the lower bound and 44 Concretely, there is a gap of "/nn/nn(e Sg (w))). Moreover, for constant L (w). the Rademacher complexity based
bound 2 improves over both of the first-order bounds (3) and ( and matches the lower bound
in Theorem This seems to suggest that a better upper bound might be possible.
Our Contribution. In this work, we settle the generalization performance of large-margin half- spaces by proving new upper bound matching the lower bound in Theorem T across the entire tradeoff between 7, (((w) and n (and is also tight in terms 8). Our result stated the following theorem
Theorem 2. There is a constant > 0 such that for any distribution D over B4 x {-1,1}, it holds with probability at least - over S ~ DDn that for every w E Sa-1 and every margin
1/2 1-12 7 S 1, we have
CD(w) - (z(w) + (V (
[n(e//((ww) 72n
+ In(e/0)
In(ey"n)
In(e/8)
+
22n
n
Using simple reduction, results generalize all non non-homogeneous halfspaces (i.e. including bias term) and data in a ball of radius R, yielding Theoremp]ww 7/ in place of 7. See Appendix
While one might argue that our improvement is small in magnitude, this finally pins down the exact generalization performance
classic learning model. Furthermore, our proof of Theorem brings several novel ideas that we hope may find further applications in generalization bounds.
We next proceed to give an overview of our proof and new ideas in Section 2 before giving the full details of the proof in Section 3
2 Proof Overview
In this section, we present the main ideas in our proof of Theorem 2 As our proof builds on, and greatly extends, the work of Grønlund al. [2020a] establishing the previous state-of-the-art in (4). we first present their overall proof strategy and the barriers we need to overcome to obtain our tight generalization bound. Throughout this proof overview, we use the notation S to denote that there is an absolute constant c > 0 so that r S cy.
2.1 Previous Proof
The proof of Grønlund et al. [2020a] follows framework proposed by SShapire et al. [1998] for proving generalization of large-margin voting classifiers (i.e. boosting). The main idea is to randomly discretize the infinite hypothesis set Sd-1 to obtain finite set C Rd + f-1, 1}. If G is small enough, then a standard union bound over all h E & suffices to bound the difference between the empirical error and the true eгrоr (h) for every h G. The key trick is to exploit large margins to allow for a discretization to a smaller G.
To elaborate on the above, let us first generalize our notation (D(w) and (3( bit. For distribution I over By x {1,,1), let (w) == P P(xxy)=D (wy S 7) that is, (w) is the probability over a fresh sample (x,y) from D, of w having margin no more than 7 on y), ). For training set S, we slightly abuse notation and write (x,y)
denote a uniform random sample
from S. We thus have
by S]]= H(x,)) 3) E S y(w S 7
Cz(w)
P (x,)>s
[S]
When writing LD (D(w) we implicitly mean (W)) and note that this coincides with our previous definition of (D(w) = ((xx)) (sign ((w, x)) * (defining (0g 0).
Random Discretization. With this notation, the main idea in the proof of Grönlund et (020al] transform (Johnson and Lindenstrauss (1944). followed by
is to apply Johnson-Lindenssine a random snapping to a grid, in order to map each w S to a point on grid G of size exp(ck) in _ with > 0 a sufficiently large constant. In more detail, let A be k x d matrix
3

---

with i..d. (N 1/k) normal distributed entries. Such a matrix is a classic implementation of the Linnessn-nndsssrruuss transform and has the property that (Aw, Az) (w.,x) is greater than with probability at most exp(- (en0-ePpp - k/cc) when || ||æ||2 < 1 (Dasgupta and Gupta (2003). ). Note that this also preserves the norm of vector w by considering x w and noting (tr, w) = wwl.. Secondly, following an idea of Alon and K Klartag (017) in lower bound proof for the Johnson-Linee Lindeenstnassssss transform, Grønlund et al. (020aa randomly round Aw to a point h A, (,,t(w) with coordinates integer multiples of k 1/2 while guaranteeing that (ha,((w) Ar) (Aw, Ar) is less than e, except with probability exp(-e kk/c) Here we use to denote the randomness involved the rounding.
Now choosing = 7/4 gives, by the triangle inequality, that (h,,t(w). Ax) {w, z>| - 7/2, except with probability 2 cxp((>2k we can also deduce that [ S 2 except with probability exp(-k/c). Simple counting arguments show that there are only exp(ck) many vectors of norm at most with all coordinates integer multiples of k-1/2, That is, except with probability hop((-/cc.. h (t)) belongs to a finite set 9 of exp(ck) many points.
Furthermore, by plugging in 2: = w and setting = = 1,
Framework. With the above random discretization, the proof of Grønlund et al. 2020a] now follows the framework of Schapire et al. [1998] by relating (D(w) to C (h A.t (w)) and (1(w) to CX3 (hA, Here AD is the distribution obtained by sampling (x,
'D and returning y) Similarly, AS is the training set obtained by replacing each (ar, y) E S by (Ax, y). The intuition is that the random discretization changes margins by no more than 7/2 for most data points and hence points with margin at most 0 under D often have margin at most 7/2 under AD and similarly for and AS. Let us make this more formal. We have for any A, in the support of A, that
CD(w) S CXB(ha, P
x (0A((hal(W). Ax) > 7/2].
(5)
Similarly, we have
[z(w)= 2 C7/2 C7 (w)))(w)) P (xx))~sly(w..) > ( AX) S//2].
(6)
Taking expectation we see that
Lo(w) - (w) = EA. (A.w) Cz(ww]
EA, ( (w)) CX3 (ha,
(7)
+ EA, P (xy))Dly (w, x) S 0 y
Ax) > >/2|
(8)
+ (A..) (w, x) > 7 A y (h Ax) S <//]].
(9)
To bound 77. we exploit that (w) belongs to the grid G, except with probability exp( sxp(-k/c) k/c).
Using Bernstein's 's inequality (and a careful partitioning of hypotheses depending on 23 (w) )) is possible to union bound over the entire grid and conclude
EA. EAII (hs,, Cx (hA,(((())
EA,((sup (x C7 (h)) - PA.tl/AA $9 heg
Cz(()) In(191/5) 11
+ In([91/8)
+ +epp cxp(-k//c) S
11
k In(e/o) (10)
+=(eee)) +
+ exp((kk//)
(10)
n
To bound 9 we use the guarantees of the random discretization to conclude that
E.. [IP (xy)ss x) > Y A (w). Ax) S 7/2]]
[x.))~ [P (y (w, x) > 7 A ( (w), Ax) S 7/2]] <
{(x,y)~s PA. (y ( (w), Ax) S 2/2 y (w, x) > 7]] S 2 2xxp(_>2k/(166))
We can bound (8) in similar fashion (even with slightly better guarantees scaled by Lo but this does not help for The final generalization error thus becomes
(D(w)= S (ww +c'. (Ve3(m) + In(e//))
++ ++(ee//8) + exp(->>k/d))
(II)

---

where c' 0 is sufficiently large constant. Comparing this expression with the desired bound from Theorem we see that we have choose k large enough that c' exp((>"k/c)) is no larger than
(In(e/ (g())/ In(c/0))
In(eyen)
In(e/5)
Cz(w)-
7/n
7Pn
n
This basically solves to
7 (wr In(e/ Cig (n)))
#21 2 2n
2 27 2n (?²n).
Inserting this l in (TT) recovers the bound by Grønlund et al. 2220a stated in (4).
Barriers. In light of the above discussion, identify some key barriers for the previous proof technique. Concretely, if we examine (T]) the term v (W requires us choose k larger than ey ey 2 In(e/ Lig (w)) to match the optimal bound we get in Theorem 2 Unfortunately, the additive exp(-7"k/c) term originating from handling ( and (9) then becomes poly (C') (w)), which is too expensive. In fact, even the additive exp(-k/ term from handling (7) is too expensive for e.g. constant y. Nonetheless, will in fact choose such i and identify tighter strategy for analysing [D(w)- - (g)
2.2 Our Key Improvements
Our first main observation is that the two upper bounds in (5) and (6) are not completely tight, i.e. they are inequalities, not equalities. In (5) we for instance ignore points (I. v) that had margin greater than 0 for w, but where the margin of (Az, y) is less than 7/2 for (w,) Taking these into accounts, we get the tighter bounds
Co(w) () + (x.))
Ax) > 2/21
- P(xx))~ (w0 (w
> 0 Ax) - 7/2],
and
(z(W) = ((a)))))))) > Ay Ax) S 1/2]
-
+ + (ww, S ( Ax) > 7/2]-
With these refined bounds, now split (D( (w) into sum of three terms:
+ + x) s Ax) > 7/2] - Psly (w, x) S ( Ax) > 7/21
(12)
+ Psly x) 7 A (h., Ax) < 7/2 Paly ( 0 (Ay, Ax) - 7/2).
(13)
The first line is the same as ? from before, but and 13 improves over (8) and ( by subtracting off term. Intuitively,
more refined bounds allow us argue that if the randomized rounding
creates a big difference between LD and CTd (w))) then creates a comparably large difference between (w) and /3/2 (w)). thereby canceling out, We will carefully exploit this in the following. Let us focus on (12) and remark that (13) is handled symmetrically. For (12,, we see that
((x.))ssy(,,xx x) S (7)y(ha,(w)) Ax) > 7/2] 2 P (l S O (lh,hh, Ax) > 7/2],
and thus 12 is most
P (xx.)>D(y(w, x) I 0 ( Ax) > 7/2] Pix.))ssy(ux x) S SOA (h,, (w), Ax) > 7/2
Now introducing the expectation over the randomized rounding A and t as in the previous proof, and using linearity of expectation, want bound the following expression with probability 1 8 over
5

---

S ~ D"
sup w1584-1
EA. (Ax=IP(xy)--lluuu = (0A((A, Ax) > 7/2
EA. (A.. /0 7/211
sup w w4
[0 ((x.y) x ( Ax) 7/21]
E (x.)ss (w, x) S 50Ay(hA Ax) > 7/21
(14)
This now has a form that looks familiar. Concretely, we have function
Min (1, v) = (v) 0} (P..,(((hh, Aa) 7/2].
(15)
for each S and wish to bound supw (x) (4 (x. y) v) Now y with high
probability over S ~ Dr, Rademacher complexity (see e.g. Shalev-Shwartz and Ben- 2014))
one key tool for bounding such differences. In particular, the contraction principle from Ledoux
and Talagrand [991] allows us to bound such a supremum when the functions V. are composite functions 1h w
o Iu with f : IR + R having bounded Lipschitz constant. In (Bartlett and Mendelson 2002 this method is used, with f being the ramp loss, resulting in a bound on (14) of
V1/(?2n). We wish to take similar approach for our ah. in (5)
To argue that the ffo fo 9w with (2, y) y(w, z). we need the probability in 15 to only depend on the original margin v( This is precisely the statement of Claim 3 which proven in Appendix B.T We thus proceed to bound the Lipschitz constant of the function f in (15). To
avoid discontinuities, we have to alter the (2; y) somewhat to not include the discontinuous indicator function, and we eventually bound the Lipschitz constant L by roughly
L PPP.-PPA (w)), (w),A) > 7/2 y(w,x) = =0].
With slight abuse of notation, we write (A.,(y(hA,,l the probability P PA, (w), Ar) > 7/2] for an arbitrary æ, w &td-1 and y E [-1, with xw, 0 as y(w, x) completely determines this probability as argued above.
Ar) 7/2 y x)) = 0] to denote
Since our randomized rounding preserves inner products within 7/2 except with probability exp(-7"k/c) we get L S 5--1 --xpp( kk/c.. This finally bounds (14) by
exp( 2k/c)
22n
This should be compared to proof by Grønlund et al. [2020a] that got bound of cexp(->2k and the v1/(22n) bound mentioned above. This improvement is precisely enough to derive our tight Theorem Indeed, as mentioned in (10), we can bound (hs, EXS (h,,)(w) by
(z(w). k In(e/0) + k In(e/0) + exp(-k/oo) n
n
If we ignore the exp(-k/c) term and set k = c'n 2 In (ale/C((w)) this gives the tight bound in Theorem
Unfortunately, we cannot afford to ignore the exp(- -k/c term and we need additional ideas for dealing with it. Recall that in the previous proof by Grønlund et al. (220a). it originates from bounding
EA (EA.LCX((AAAA CX3 (ha, S (sup -X3() PA,. 9], heg
and upper bounding (AA,(hA,t(w) & 9] by exp(-k/c). Here we instead consider an infinite sequence of discretizatioos/griiss Go, .i...., and argue that the random rounding A, t and training set S is simultancously good (for some appropriate definition) for all grids with high probability. Here the grids G; correspond to increasingly large norms of hw,(ww) i.e. G, contains all vectors of norm at most 1 and all coordinates integer multiples of 11/2 Multiple careful applications of Schwartz, Jensen's inequality and upper bounds on the probability that hA,s (w)) & 9, allows us to finally get rid of the exp(-k/c factor.

---

3
Main Proof
We now set prove Theorem following the proof outline sketched in Section 2 We start by a series of reductions that allow us to focus on simpler task of establishing Theorem 2 only for small range of y and (w))). We describe these reductions in Section 3.1 and then proceed to the main arguments in Section 3.2
3.1 Setup
When eventually bounding the I. Lipschitz constant, as discussed in Section 2 the task turns out be simpler if || = 1 (and not just | < 1) for all I in the support of and if [w,, x)) < by for constant G, sufficiently smaller than 1 for all hypotheses w and data points (æ, y) the support of D. We reduce to this
in Appendix A The reduction maps every E S
vector in
H = Sd-1 x {0), and every x in the support of 'D to a vector in X, where X' is the set of all vectors x' in St where the norm of x' without its (d + 1) coordinate is at most C.y.
From hereon, we let D be an arbitrary distribution over A' {-1, 1), and set out to prove that there constant > 1, such that with probability least over S D", holds for all margins y (n-1/2, en] and all H that
( CD(w)= S (w) c E3((e)) (In(e/C3(w)) 72n
In(e/0)
In(e?2n) n
+ In(e/6)) (16)
n
Theorem 2 follows corollary.
Smaller Tasks. We now break the task establishing (66] into smaller tasks, where we consider
margins y in a small range (x-7i-1) and only vectors E H with LP c(3/477 (w) in small range (e,, (.]] The purpose here is, that for one sub-task, we can treat margins and margin losses as the same within constant factors. A union bound over all the sub-tasks then suffices to establish (16).
For given distribution D. partition the range of values of the margin 7 E (n (1/2 c.] into intervals r, 1n1/2 2 for 1,.... (g, Similarly, partition the possible values of (w)w) [o, 1] into intervals Lo [0, and L, (2i-1n-! 2,2nn=1) with 1,... Ig. n.
For a pair (T,, Lz) with I, (7, / define
H(T, L,) {w H 23/4m/ (w) Ly}.
For each pair (T', Lj) we now prove an equivalent of (66. but tailored to the sub-task. The result is stated in the following lemma
Lemma 3. There is constant 1, such that for any 0 < 5 < 1 and any pair (T Lÿ) ((1, 7441), (Eg, ()), it holds with probability at least 1 over a random sample DD that
sup (CD(w) [z(ww] S (V/er we (.)
(In(e/Egt1) + In(e/0)) + In(e/Ef+1) R24m
+ In(e/5) n
(17)
Observe that while (16) depends on and 17) depends on 744. this is fine since S 7441 for all
Y E r However, recall that H(T,, I.j) refers w E H with c(3/4) (w) E L, = (ly, ff+ But the f-+1 terms in 17 need to be replaced by (g(w) to obtain (T6). Thus we relate the two via the
following lemma
Lemma 4. There is constant 1, such that for any 0 < 5 < 1 and any D (76, 7441), it holds with probability at least 1 over a random sample ~ 4d that
(3/4)) (w)
In (n(e77211))
In(e/0)
Yw H: C3 (w)
(18)
4
22
7
We combine the sub-tasks and conclude

---

Claim 1. For any 0 < 6 < 1, it holds with probability 1 5 over S ~ DD that equations and simultaneously hold for all (T)) and ;, with slightly different constants
17
Since Claim follows by a simple union bound, exploiting that for different values of fs+1 and 7++ we can afford to use different ōG, = 8 5cxp(- In(e/E541)) and 6; = ò exp(--144 In(er(t)))) have deferred the proof to Appendix
simple combination of 117 and (8 now gives
Claim 2. For any 0 < 8 < 1 and training set S, if equations 17 and (18) hold simultaneously
for all iT,, In)) and a then equation (T6) holds for all 7y E 172 C-y and all w E H for a large
enough constant > 1 in (6).
Claim 2 follows by using that y N41 for y I₁ and by using Lemma 4 to relate all occurrences of fJ+1 in (17) to [3(ww) (w)). ) As this is rather straight forward calculations, we have deferred the proof to Appendix
What remains thus to establish Lemma 3 and Lemma where we may now focus on small range o and ((8/4))( (w). While both require substantial work and non-trivial arguments, the proof of Lemma follows mostly the previous work by Grønlund al. [2020a] and has thus been deferred to Appendix D
3.2 Random Discretization
We now set out to prove Lemma So let 0 < 8 < 1, and fix pair (T,, Lÿ). Following the proof
outline in Section 2 we now consider the following random discretization of hypotheses H(,, L,): Let j) j) be integer parameter to be determined. Sample random & x d matrix A with each entry N (0, 1/k) distributed as well as random offsets (t1....,
.a....,ta/ tx) all independent and
uniformly distributed in [0, 1].
Let G be the set of all vectors in IR* with coordinates in
(10/))
2(10v EZZ
For w E H and an outcome (A, t) of (A, t), define hw,(ww) E 9 as the vector obtained as follows: Consider each coordinate (Aw), and let 2; denote the integer such that
(1/2)(10V)))+ (10V < (Aw); (1/2) + (2s 1)(10V))
Let (h),(w)), equal (1/2) -1 2 (10Vk)
p((A)); ((Aw); rounded down) and (2: + (10vk)-1. By standard arguments, which we
otherwise let it equal (1/2) have deferred Appendix E choose p(Aw);; E [0, such that the expected value of the (Aw); The random discretization has the desirable property
coordinates satisfy E. (( that it approximately preserves margins/inner products as stated in the following
Lemma 5. There is a constant c > 0, such that for any integer k 2 1, w E H. E X and any 7 (0, 1), holds that IP (h (wr), Ar) (w,,)) 7]
The proof of Lemma follows the work by Alon and Klartag 2017] in their work lower bounds for the Johnson-Lindens Lindenstrauss transform, and has thus been deferred to Appendix E We now observe that
Co(w) CT./2 C (ha,(ww) + P ((x.)))-l((baaal Ax) n/2 yw, S0] - -P(xy) (hwoolyynai,iai (w), Ax) < 4/2AA x) 0].
Similarly, we have for H; and any training set S that
Cz(w) L (hs, +Poos)ssyy(Hhh
- (y(x))s)((hh.. Ax) - / >7].

---

We now have for any > E F3 that
(Golw)-C3(10)) =
sup
WEH(T..L,)
sup FEA. LXS (ha,,
wER(TT,L))
EA. (PDYy(l(AA Ax) > A
w/2AA(u x) Poly-Pssy(hAAttC Ax) > w/2 y x) S +|]+
EA. (A..ssl((hA Ax) S / 7 x(,,)) > (ply(hh AX) S / (w,x) > 01]
(19)
A critical observation is that the distribution of y (w), Ar) depends only on y(w, x).
Claim 3. For any (I.y) E X {-1,1} } and any w E H. the distribution of y( (w), Ar) is
completely determined from y ((w, x).
We prove Claim 3 in Appendix B. by exploiting that the entries of A are i.i.d. (0, 1/k) distributed and using the rotational invariance of the Gaussian distribution.
As outlined in the proof overview in Section 2 we can now use Claim 3 togetherr with the contraction inequality of Rademacher complexity to bound several of the terms in (19). Similarly the intro- duction of the ramp loss in classic proofs of generalization for large-margin halfspaces, we need to introduce a continuous function upper bounding the probabilities above. With this in mind, we now define the following functions & and p:
IP (A Ax) > 7 v(w,z) aa] (Te P PA A..l Az) > n/2 x( =0
if - c, saso if a 2/ if < a S by
((a)=
(A..l((h,, Ar) S ///2 x) al
if <asa
p(a.)
a (w) Ax) S s\/2 y(w,z) = ml if0 <00055
if $a50
Here we slightly abuse notation and write P PA.lIv(h,, (w), > 2/2 y(w, a| to denote
the probability PA.+ (ha,,, e, (w), Ax) > %/2] for arbitrary H. (z, v) X x 1, with y(w, x)- = a and remark that this probability is the same for all such w, x. y by Claim
We now observe that é and p upper and lower bounds the terms in 19
Remark 6. For any training set S and distribution D over x { 1, 1}, we have
EA,t P (xx)))))DDD)) (oon))/oy(h..... ( Ax) > n1/2 y(u, x) - 0] < D(x.)) (v,( Ax) > 7t/2 A y( x) S 7]] > ( x]
EA, (x..)P(x..)sss(((( ( (w),
EA, (A.)| (( Ax) S 7h/2 A y (w,x) > 7]1 < (ply (w, x))]
EA, P (xXx) (hA, Ax) I 7h/2 y (w, x) > O]] Z - (w,
The proof of Remark 6 follows from the definition of & and p. along with monotonicity of
P FA.el((hart Ax) 7 y(w, x) =a] as function of a. The proofs have been deferred
to Appendix E Continuing from (19) using Remark 6 linearity of expectation and the triangle inequality, we have for any 7 E I; that
sup CD(w)- Cz(w) < mEH(T..).))
sup we wEA(T.,F.))
E /2 (ha,(w)) - C3/ (hx,(()) A,t
(20)
sup w WEH(T,
E (x.y)>> (Ø ( x))]
E
jo (oly x))]
(21)
(x.y)~
sup WEH(T ,.)))
E (x.y)>>
[ply (w, x\)]
E
jply xX)]
(22)
(x.y)~
In Appendix C we carefully use Bernstein's 's plus a (highly non-trivial) union bound over infinitely many grids of increasing size to bound 20 follows

---

Lemma 7. There is constant > 0 such that with probability at least 1 over S ~ Dr we have
(Cs+1 exp(( In(e//)) (k + In(e/o))
20
S
n
In Appendix B we then use Rademacher complexity and a bound on the Lipschitz constants of Φ and to bound 21 and (22) as follows
Lemma 8. There are constants c, d' > 0 such that when &s 2 d
2 it holds with probability at least
1 8 over S D= that
max 21
22
< cexp( (orp(-144k//) ( w In(e/6))/n.
To balance the expressions in Lemma 7 and Lemma sufficiently large constant
now set c In(e/(f+1) for
so that exp( exp(->f++1 k/ S f/+//e and k d' Combining
Lemma and Lemma 8 via a union bound with 8' 6/2 and inserting into (20) and (22) gives
sup CD(w)= [z(()) sc (etta (T In(e + wEH(TT.))))
+ ( Geal In(e/(/11) In(e//))
M In(e/(411) In(e/8)
n
n
for constant > 0. This completes the proof of Lemma which together with Lemma completes the proof our main result, Theorem
Conclusion
We have established the first asymptotically tight generalization bound for large-margin halfspaces, resolving long-standing gap between upper and lower bounds in this fundamental setting. Our main theorem precisely characterizes the interplay between the margin, empirical margin loss, sample size, and confidence parameter. The proof introduces several new analytical techniques, including refined initial analysis and a Rademacher- beaemaccer--aeeed treatment of randomized rounding.
Beyond settling the generalization theory large margin halfspaces, our framework provides novel tools that may prove useful for deriving tight bounds in related models. Concretely, are in essence a refinement of the techniques introduced by [Schapire et al.) (1998] for proving generalization of large margin voting classifiers. For voting classifiers, the best known generalization upper (Gao and Zhou (013)) and lower bounds (Grønlund et al. (2020b)) for finite hypothesis sets have similar logarithmic gap as our techniques managed remove for halfspaces. Another related topic is kernel methods, in particular in the context of support vector machines. Here there are also prior works deriving generalization bounds based margins, see e.g. Cortes al. (2010), however these works are not "first-order bounds". i.e. the V- terms in the generalization bounds do not decrease with 23 (w). We are hopeful that our techniques may also yield improvements these areas of interest. In particular, it is worth mentioning that the original Lindenstrauss 1984 also provides dimensionality reduction from infniitedimmensional Hilbert spaces (e.g. kernel space), thus suggesting that similar randomized discretization might be possible.
techniques
transform Johnson and
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Clement Svendsen for valuable measure theoretic insight.
Kasper Green Larsen is co-funded by DFF Sapere Aude Research Leader Grant No. 9064-00068B by the Independent Research Fund Denmark and co-funded by the European Union (ERC, TUCLA, 101 125203). Natascha Schalburg is funded by the European Union (ERC, TUCLA, 101125203). Views and opinions expressed are however those of the author(s) only and do necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
References
N. Alon and Klartag. Optimal compression of approximate inner products and dimension reduction. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 639-650, 2017.
P. Bartlett and J. Shawe-Taylor. Generalization performance of support vector machines and other pattern classifiers. In Advances Kernel Methods-Suppon Vector Learning, pages 43-54. MIT Press, Cambridge, MA, 1999.
L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463 2002.
C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273-277, 1995.
C. Cortes, M. Mohri, and A. Rostamizadeh. Generalization bounds for learning kernels. In J. Fürnkranz and T. Joachims, editors, Proceedings of the 27th International Conference on Machine Learning (ICMI-110) pages 247-254, Haifa, Israel, June 2010. Omnipress. URL http://wwtz i wtc.cmm11000.m wro.0...rg//ppeee http://000000.r/p/////////
Dasgupta and A. Gupta. An elementary proof a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms, 22(1):600- 10166006-52260 2003.
Devroye, L.. Györfi, and Lugosi. Probabilistic Theory of Puttern Recognition. Springer, New York, 1996. ISBN 978- 378-0-387-946188 doi:
Y. Freund and R. Schapire. Large margin elassification using the perceptron algorithm. Machine Learning, 37(3) Dec. 1999. ISSN 0885-6125. doi: 10. 10.1023/4411007664477466 URL pdff
http://csewee: uesd. www...eeddd...e.eeeeeeee.ee http:///wweeeeeeeeeee//eaaaaaaaa
W. Gao and Z. Zhou. On the doubt about margin explanation of boosting. Artif. Intell., 203:1-18, 2013.
A. Grønlund, L. Kamma, and K. G. Larsen. Near-tight margin-based generalization bounds for support vector machines. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 3779-3788. PMLR, 2020a.
A. Grønlund, L. Kamma, and K. G. Larsen. Margins are insufficient for explaining gradient boosting. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020b.
Y. Gu. Z. Song, and L. Zhang. Faster algorithms for structured linear and kernel support vector machines. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openrevier mett/forum?.d-DDDFII..
W. Johnson and Lindenstrauss. Extensions Lipschitz mappings into a Hilbert space. In Confer- ence in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemporary Mathematics, pages 189-206. American Mathematical Society, 1984.
A. Klenke. Probability Theory: A Comprehensive Course. Springer Cham, 2020. ISBN URL btttpp::/ddoi.or////
978-3-030-5644025.. doi: 10.10077978-3-030--566 978 3- 030--

---

B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. The Annals of Statistics, 28(5):1302 1338. 2000. doi: N0.1214/aox/0015955539 URL https
7/doi. 10w..111//a0 ht////o///100 101595739
M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. A Series of Modern Surveys in Mathematics Series. Springer, 1991. ISBN 9783540520139, URL
https://books http://bboooo.oggeeee... dbtp/ooolllPPdd-cKK/Vvvaaaaaa
D. A. McAllester. Simplified pac-bayesian margin bounds. In B. Schölkopf and M. K. Warmuth, editors, Computational Learning Theory and Kernel Machines, 16th Anmual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777 of Lecture Notes in Computer Science, pages 203-215. Springer, 2003.
W. Mcculloch and W. Pitts. logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5:7, 1943.
N. S. Shalev-Shwartz, S. Yoram and A. Cotter. Pegasos: primal estimated sub-gradient solver for svm. Mathematical Programming, 127(1):3 - 30, 2011. doi: 10. 10.10077110000-00000042--- URL
httpp:///oo..org//000////////// 01t.:/0001107/111100000000000000
R. E. Schapire, Y. Freund, P. Bartlett, and W. S. Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651-1666 1998.
S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5.
M. J. Wainwright. High-Dimensiones Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
12

---

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

---

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

---

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

---

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

---

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

---

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

---

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

---

A Simplifying the Setting
As is usual in analysis of halfspace classifiers, we restrict to data a of at most unit norm and normalized halfspaces w without bias. Our main result stated under this restriction. The more general result, for non-homogenous halfspaces and data x of any norm, stated below, follows from the homogeneous case.
Theorem 9. There is a constant O such that for any radius R 0 and distribution D over R. BB x {-1,1}, it holds with probability at least 1 - over S ~ DD' that for every w E S
1.b. E IR
and every margin Rn- 1/2 I S R, we have
(D( b) s ())
R2 (/ln(e// [e(ee///((..)) b))
In(e/6)) +
R (n((e?Pn/Te))
22n + In(e/6)
+c(1 (3( (z(w.b)
2
where Cp(w,b) == P(x.))-Dliin bligu ((w, x) + b) + y) and (z(w,b) = H(x,v) S ((w, + b) S (r]l//Ssfor a set of samples S.
Proof. First observe that for points in the ball of radius R. any halfspace (w, b) with [6| R makes the same classifications as the halfspace (w, sign We thus assume wlog. that |b| S R. Let D be a distribution over R TB: x (-1,1). Map any sample (x, y) in the support of D to the sample (x', v) where x' is obtained by prepending coordinate hardcoded to R and then scaling the resulting vector by 1/V2R22 Similarly, map any non- oon-homogeneous halfspace (w, b) E S x [- R. R] the homogeneous halfspace w' obtained by prepending coordinate to that is hardcoded to b/ R and then scaling the resulting vector by 1/ L/V(b/RB
I. We have ||w'|| = 1 and ||>'|| || S 1. Furthermore (wo,, a²)) (2 ((//())) + 1)) + x)). ). It follows that w' makes the same prediction on a' as (wc, b) does x. Furthermore, the resulting margin least factor (2 R)² + 1)) > 1/(2R) of the original margin. Theorem now follows from Theorem by replacing all occurrences
of y by (2R)..
In the main proof we reduce to a setting more favorable for analysis, here we give the details for the reduction, and the argument that generality was lost.
Observation 1. Without loss of generality, we can assume that the vectors x in the support D have unit norm and all margins lie in the range [-cy, for a constant 0 < Ciy < 1.
Proof. Consider the following distribution D' obtained by sampling (x, y) D and replacing E S for sufficiently small constant 0 < Cy 1. That is, scale down all coordinates of x by Cy and append a (d + 1)'st coordinate taking the value
by x' (c,x) 1/1 -
/1 - | |12 Then the norm of the resulting point x' is v / | +
1 1. Similarly,
{0). We observe that for any x. w. have that (w',x') x²) = (w, C..r) = Cy (w. æ) and thus lies in the range [-cy; cy] by Cauchy-Schwand This also implies that sign( (w xx") sign((n ((w, x)) and thus the generalization error of w' under D and to under are the same.
for any Sa-1 consider instead the hypothesis w'
Theorem 2 follows transformation the input distribution. Since e, is a constant, this disappears in the constant factor e in Theorem 2 (note that for margins y E in 1/2 c 1n11/2,,,, 1//1,, n -1/2) in Theorem we cannot use the reduction, but here Theorem 2 follows trivially as c cln(e?2n)/(>²n)) > for sufficiently large c). O
immediate corollary of (16). since margins change by C. factor in our
B Rademacher Bounds
In this section, we use Rademacher complexity and the contraction inequality to prove Lemma We focus on bounding 21 and note that (22) is handled symmetrically.
20

---

For training set S E (X' {-1,1))" consider the empirical Rademacher complexity (for (oi,..,, .n) vector of independent and uniform variables in {-1.1}):
(o.H(T,))(S)) = Eo
sup (E (aniBe)s
Σ
a 2z)))
B sup WEN (Mi-3A)
Σ
Φ is Lg-Lisschitz, then the contraction inequality from Ledoux and Talagrand 1991 gives that
Le n
(S)
S
Ea
sup wEH (3E
Σ
oayi(w, 2i)
Using Cauchy-Schwand this is bounded by
La Er
RS. (S) S
W Σ
sup
WE
(si.3))
Lsp
sup WEH H
|w|l2
Eg
Σ
JiyiT
L
E
Σ
(x..BiJES
L
Σ
Σ
E (a (xs,
n (a..))) (x)a)))S
V
L
Vn
Since this inequality holds for all S' with each (x, E satisfying ||>|| 1, we have for the distribution D that the Rademacher complexity
Ro....( = Egn z RR.H((S))
satisfics RD.,.((1) S Lo/ Vn. By Lemma 5 and % = 7/-1/2, we have that ø is bounded by
5 d(a)
P PA..lv(h.. Ar) 7\/2 y(w, z) = al s eexp(-kyi+
Sa
for constant > O. We conclude from standard results on Rademacher complexity (see e.g. Shalev Shwartz and Ben-David (2144). ) that with probability over sample S ~ D it holds that
sup w (.
[Exxy)>Dlo(y (w, x)) -(x (w, x))1
In(1/8)
2RD + cR
cexp(-h>72 vel
n
2L + CR
In ln(1/8)
cexp(-k>
Vn
where en is constant. Symmetric arguments bounds p by the same, with the Lipschitz constant Lp of p in place of L.g.
We now the following bound on the Lipschitz constants of Φ and
21

---

Lemma 10. There are constants CL, >> 0 such that the Lipschitz constants Lg and Lp of & and are bounded by
cr. exp( exp(- k/cr)) (Vi+nitt)).
when k 2 07441
We prove this lemma in the next section. We thus conclude that with probability at least 8 over
S ~ D", we have
sup wE
( x))] ((x,))~s(((y)) x])]| S
eL exp( 1 1 k/c))
(Vk+ + +
In(1/6)
2
cexp(-kr /c)
The same bound holds for via Lemma
10 which completes the proof of Lemma
B.1 Bounding the Lipsehitz Constants
In this section, proceed bound the Lipschitz constants of é and and thereby prove Lemma T0 We split into two tasks depending on the value of a. The simplest case is the following
Lemma 11. There is a constant > 0 such that the Lipschitz constants of o and p. when 0 < a S % are less than:
cexp(-kn241/
Proof. Since ø is linear when 0 %/a its Lipschitz constant equals the slope of the line, i.e.
PA. PA..y((ha.e Ar) > 7/2 y(w, x) = 0).
By Lemma 5 and using " = #+112, 2, this bounded by
ccxp(- kcxp(-n2+1kkc)
Yi+1
for a constant > 0. The same arguments applies immediately to
The trickier case is when a E [- 0] for ø and when (1i,cy) for If we set ey 1/V22 then we have
Lemma 12. There is a constant >> 0 such that the Lipschitz constant of ó when [-1/v2,0) and p when a E (7/, 1/22 less than
cexp (- 2422k/c/ Vk,
for k 2 cY141-
Combining this result with Lemma II completes the proof of Lemma
To prove Lemma 12 need to bound the Lipschitz constants of & when a [-1/V2, 0j and p when (Yi, 1/V2j. We will go through the details for o, and comment how the argument for p differs along the way.
First recall the following claim
Restatement of Claim 3, For any (x.y) E X' x (-1,1} and any w E H. the distribution of (h Az) completely determined from y(w,x))
As we need to understand the distribution of the random variable y(hs, (w), Ar) to bound the Lipschitz constants of & and p. we proceed to give the proof Claim 3 while introducing convenient notation for establishing Lemma 12
22

---

Proof. Firstly, write (w,(ww) = Au + v with v= (hA,((w)- - Aw). Then observe that (Aw); = (a,, w) ~ NN( [k]l _ #0 1/k) where a, denotes the i'th row of A. Here & denotes equality in distribution. Now write x = (w, z/w + where (u, w) 0 and ||ull step). We have (Ar); (a., w) (w, z) + (a,, u). By rotational invariance of the Gaussian distribution and orthogonality of w and u, we have that (a,, u) ~ W( (1 (w,, 2/k) and that this is independent of (a,, w)) (a,,e).
||-||² (w,x)²
1 1- (w, x²² (i.e. a Gram-Schminn
Using the independence, we also conclude that if we condition on any fixed outcome of c; (Aw),, we have that oi (a u) is NO oi - (w, /k)) distributed.
We now argue that we can sample from the distribution of ( Ax) ( (w), yAx)
knowing only y(w,,, æ) as follows: Sample independent A/(0, 1/k) distributed random variables XI....,X, Next sample independent (O,,, (1 y2 (w., 2/k) distributed random variables YI...., Yv and let Z; y/w,,), + Y, "(=,( + yY, where the last step follows from independence of X; and Y; and symmetry in the distribution of Y; Let X be the vector with the X,'s 's entries and Z similarly. Then the joint distribution of (X, Z) equal the joint distribution of (Aw, ).. Finally draw offsets ty tt uniformly and independently in [o, 1] and round X;
to number of the form (1/2)(10VR)- =(10vk) for E Z as in the definition of hA,t. The resulting variables X satisfy that (w), Ar) 2)
With Claim established, we will use the notation in the proof as we proceed with bounding the Lipschitz constants of and p.
Let a yyww,)) for some w E H and (x, v) E X x (-1.1) and a E [-1/V2, (for let E (n. 1/v2). X;; ~ (N 1/k), Y, ~ N(. (1 (1-a))))) and let X be the random rounding of X, We argued, in the proof of Claim 3 that (w)),,(w)),.) Az) _ (X', aX + Y). Let additionally E, be the event that X is rounded up. For notational convenience, let M, vix, and observe that M. ~ (O, 1). With this notation, we have that X has the form
1 10VA:
1 (LIOM. - 2Vk10
1(B.) + +12)
X
Hence,
((,,, Ax) d (X' ax
x M) + (X', Y). Vk
Recall that the variables t, and M, determine X,, E, and thus also X'. If we condition on an outcome t, = f, and M; M,, only Y, remains random. We may thus write
Piy(ha,u(W), x/2]
P
X' M) + (X', Y) > n/2
J (M,
a x
M) + (X', Y) > 71/2
M, = Me, t = d(M,t)
LV
Jee (M, t)P
a
(x', M) + (X' Y) 11/2 d(M,t),
where (M,,) is the joint probability density function of M and
Let us now define N, such that Y; = k and the event
~ N, and let = (N NR). Then N₂~ 1))
X', M) + (X) Y) > 7/2
23

---

may be rewritten as
(X' M) + (X', Y) > 1/2 = (X', Y) 1/2
a
(X' M) =
Vk
a²
(X', N) 1/22
a
(X', .M) =
k
V
/1X NY 4/2 Vk
(X', M)
(X Vky.2
a: (X', MM) a
Observe that (X/IIXX/l2, N) (0 1). If we let & denote the cumulative density function of standard normal distribution, then we have established
(ly(ha,c(w) 7t/2] Sec (MM(M.)) (1-0
[ (1 a2 | - d(M,)) v1
))
a - <21-021X'11 )) d(M,t).
-Se Jer (M((M) (1
(23)
In the last equality, t is since each t; is uniform in [0, 1]. This reduces JM,(MM, () to the probability density function (MM of M alone.
that M and are independent and that the probability density function of
The same arguments for p also gives the integral 23
with the small difference that (1 - (1))(-))
is replaced by (-)). This difference is irrelevant, since to bound the Lipschitz constant, we will differentiate and bound the differential's absolute value.
Let g(M, a) be the integrant above, we want to differentiate fg ((,tt,a) d(M,t) t) by
differentiating under the integral. Standard measure theory results (Theorem 6.28, Klenke (2020)) allows us to do this if we satisfy three conditions. These conditions are, in this case, equivalent to the following
i) for all constant a the integral fR fa* g(M,t, a, d(M,t) t) is finite.
ii) for all constant M,t, t, the partial differential of g(M, t, a) with respect to a exists.
iii) There exists function 1(M, (), where S h(M,t) d(M, is finite and such that du a)) h(M, for all a.
The first two conditions are straightforward: The integral is equal to a probability, which is finite. And is a combination of differentiable functions making it differentiable itself. The last condition is more cumbersome, but the goal of this proof is to upperbound the integral by constant, which clearly doesn't 't depend on a. Hence the last condition will be satisfied during the proof.
Hence we can continue with our differentiation by differentiating under the integral.
(M Ax) > 76/2]
da
Ueen x/,1 10 Da (M) (1-8)
Vkrr22 12- - a(x' M) a(X.M)
)
a² - |X'll2
d(M.1)
1 Vkys/2 - axx',
ovTr (X', M) -=)a))// X2112
(M exp
2
d(M,t)
2m
JBtx|o.11
a1-a2 12112111
1
(VKry/ - a(X', M))²
ovTor (X' M)
fm(
d(M,t).
2T
2(1 x
(1 02-0// 1
24

---

For both a E [-1/v2,00 0] and a E (x, 1/v2]. we have that 1 2 (1 11-a3) a²) 2 1/2 and thus, for both @ and p. the above is upper bounded by
2
(VhT1/2 aaX'(, M))²
Vhy + MMX d(M,t)
fM(M))exp
2
211
||x1|2
(vTrr//2 /2 aaX', ,()'
ViTu + (1Ml1a ) a(M,)). |
< (M(M) exp
2 X
We now use that |X 2 (102) for all i. This implies ||''|l2 2 /A(1/4)(OOE))=
1/20. We may thus further upper bound the above by
[VExx/2 a(X', MYP) (Vix+ + (1M712) d(M,)). (24)
20
(M) exp
2
We will bound
24
by splitting it into cases:
4 k.
iJ |MMI3 S
10 K-
üj k S
S
ii) | N
10
The arguments for cases and tii) do not depend on a, and hence identical for and Φ. In those
cases, we simply exploit that || - ~ X² and thus these cases are very unlikely. This implies that afford upper bound the exponential term in (24
the integral over Jar [Mr is so small that by 1. For case it), we can use the assumptions on |M 1/ to show that the exponential term is no more than
k/c) for a constant O. We proceed to the three cases.
case i). We simply upper bound the exponential term in 24 by and use the assumption that || 1 < To k to conclude
exp (- (Vhr//2 - (XX) (0t7:/2a(XX,M1)
(VTTH + [M]22 2vk.
211x'112
Now since M is multivariate standard normal, [M]] is x2 distributed. Let Z ~ Xi with probability density function fz(2). Then the integral in (24p in is bounded by:
(M(M) dM = 40 [
9k/10
40
fz(z) de = -400=: PPZz < 9k/10],
Dk/10)EB
which by Theorem 17 less than
80 expp (-k-²² /800)
case ii). We use the assumption that 1/ < | 1 together with the following observations
Remark 13. If || < 4/3, then || 1/2 2.
Remark 14. If || 2 9/10, then (8/9)||X S (X, X') S (10/9)|
We prove Remark and Remark 14 in Appendix (8/10) Vi and hence
Since VkX M, Remark 14 gives (X', MM >
Vkn 2
3 <0-
Vhr - a(xx ,XX,,)
9k7
> 7/4
xX'X', M) <
10
2
100
Vkn a(X', M) >
Viy
kn
<
a(X' ,M)
2
2
4
Hence for both Φ and p. the last two factors of the integral in (24 are bounded by:
(Vhr//2 (xX' M)>)) (VT+x + (1Mll2)
S Vhepp (-100-
5
96-7
exp
2
Which gives the following:
ky?
ky
50vkexp
[M((M dM < 50Vkexp
[50
50
25

---

case tii). We bound the last two factors of the integral (24 under the assumption that | 2 g/..
Here we simply upper bound the exponential by 1 and get
exp (-
- -ali M.). (Virs [1ar]la) s 2|
2
hence the integral (24 is bounded by:
[
40
(Va/3.B33 fM(M)) d.M
(25)
Recall that |M
x² and let Z x² with probability density function fz(z). Then the inte-
gral 25 is equal to
0C 40
fz(z)Vz de.
4k/3
Let also L; [ 2", zk 2 for i Zza. By definition, the L partition 1 x0), and upper bound with:
40
f2(2)/ 3 22t2 de s 70v
P E L/2 < 70v K
Z 2 2 2:/2
1=0
L,
1=0
2=0
Using the following remark:
Remark 15 (Laurent and Massart
2000 equation 4.3, page 1326).
Let Z X y >>
then:
PIZ 2/ + 2y + k) S exp(-y).
With ogk, where ==
1 g2
We have:
2 ky + 2y + Ve
+
8 +1
k
4v3
+
1
+1
k- - -
2:.
v3
24
24
Hence we can finish the bound for this case, using the assumption that
2 3/
272 In(2)
70 h:
2
2:/2 < 70Vk
Σ
exp
1
k
2
2:/2
48
i=0
< 70vk exp
00
exp
1
k
2:/2
48
48
(-1
1
< 140v/exp
km?
48
Collecting the three cases. are bounded by:
Hence in total
9 of for E 1-1//22 0J and
a 8y pl for a (m 1v2]
(- 500keepp
ky
+ 1400kexp
(m1
kn?
50
S 140 / exp (-k7?
Using that 7/41 = 27,, this completes the proof of Lemma
12
C Meet in the Middle Bound
The goal of this section is to prove the following
26

---

Restatement of Lemma] 7 ~ Dr we have
There is constant > 0 such that with probability at least 6 over
sup (.)((T.,T.))
(Cst1 + exp( 1 +I(ee/)) (k ln(e//))))
n
Notice here that the two losses 2X/2 (02-(hg (hA.e (w)) and 2X52 (ha,(w)) refer to the same margin k// and h has been discretized to have coordinates of the form (1/2)(10/k) + =(10v/) for integer 2. Intuitively, we will try exploit this discretization to union bound over grid of finitely many hypotheses. Unfortunately, the random matrix A may increase the norm w arbitrarily much, and thus a single grid is insufficient. Instead, need infinite sequence of grids. For this, let Go denote the set of all vectors in 4B2 whose coordinates are of the form (1/2)(10v/)) k) + 2(10v/)== for integer 2. More generally, let Gj for i >> 0 denote the set of all vectors in (2 4B/) whose coordinates are of this form. Since ||0||| S vkl|arl2 for any E IR have that 9i C (2' A Vk(2' 4B For vector E Gs, let i(x) (i1...... ....,,,, is) denote the integers that x (10
(1/2)110/R)) with RR* the all-1's vector. Then by the triangle inequality, we have (10v/) [=x))] I ||ж|| (1/2)(10V\) | S 2 4 1/20. This implies [|((=)]l1 S (10//) 4 1/200) S (5- 2 + 1)k. Since each coordinate of (ax) an integer, there are thus at most 2 choices for the signs and Σ (3.2 + +1)8 (K++-1) choices for the absolute values of the integers. That is, we have
(5-2113+1)k
19,1 S 2
Σ
k (k+t-1) 1)
< <2152 843) s 222
(26)
We now start by considering fixed outcome A of the random matrix A. For such a fixed A, the training set S behaves well in the sense that L (w) and L7 (w) are close with high probability for any w. This is formalized in the following remark
Remark 16. For any distribution D over X' x (-1,1}, fixed w H. margin and any A E Rexd holds with probability at least - over S ~ D that
1 - - (w) In 21n(1/5)
The proof of Remark 16 a simple application of Bernstein's and can be found in Appendix
In Lemma 7 the matrix A is not fixed but random. Thus we need to find a formal property of the training set S under which LX//" (hs,, (w)) and CXF2 (ha,,(w) are close in expectation over the random choice of A. With this goal in mind, we now say that matrix in the support of A and training set S has distortion at least 3, if there is grid Go and vector Go such that
1C (w) - 22/2 (w)) > B. (V
8L (2 (2) In(1/5)
2(24+7k lm(1/))
+
For training set S, we use (S(S) denote the set of matrices with distortion least B for S. We observe that for a fixed matrix A, grid Go and 3 > 1, we have by Remark 16 with 5% = (8/2 (6/222*'0 22ppp and a union bound over all Ga. that with probability at least 1 Ig. 8 it holds for
27

---

all w E Ga that
SC AD (w) ln(1/5)) 2ln(1/6))
[ - -2,//
-LAS (w)1=$ (w) -
AD
n
XD (52 kh + 3lm(1/)))
2(320+7h: + 11 (m((6/)
8D (2) In(1/5)
2(2a+ + (n(166)
S B.
+
Thus for 3 2 2, we have
Ps[A Dp(S)]
- Σ 9oloa
6=0
8 2 (8-1)22**A
<
a=0
S 88 2-1-2-11-2- 1
By Markov's inequality, we have
[A E Ds(S)
[ssPA[A E Ds(S)) 2- 58/2 2- 2- 2-
- 2 88/3. 2- 2-(-11):20
EA Ps|A E D3(S)]
2 83/2 2--.2211--220
- 88/2 2 (8--1))
Now call training set representative if holds for every 8 = 2 with integer h 2 that
PA[A E D₂(S)) < 2 88/2 2 (/--1)11 2*
union bound implies that is representative with probability least
2 82h-1 22(2"-1)2* 2 1 22 2 1 - 5.
h=1
Now define for integer h 2 the set
Ks(S) = D24 (5) \ 1
Let Ko(S) be defined as
Ko(S) = supp(A) A) (U (S))
For any w E H. we may use the triangle inequality to conclude
EAN (ha,((w) LX6 (har(W))] s
8
Σ EAt (hA,t()())) - CA. (C((((hA, A E (n(S) PAIA E Ks(S)). A=
Now consider an A E Kn(S). Then A has distortion no more than 2 by definition of (S).). This implies that if (w)) is in Ga but not G, for b < a, then [ 12 2 20+1 by definition of G6 and we get
|C (hA,((w)) LT//2 (w),
24+1, (v 1/8C% (C))(())(2477) In(1/))
2(2" Tk ln(1/)))
(v
|SC (w)(k + Im(1/8))
(w)
2(k + lm(18))
2d (0=8l/aa((w)1l
n
28

---

Using Schwartz, we thus get for any w E H. that
(hA,,()())
(V
(VSA SCAAD 8L (w) + In(1/0))
||A.a(W)]la Σ 2 BA.t
n
A
2(k: + In(1/66)
A KW)) PA PAIAE Kn(S)) S
8
Σ 2
v |AxillbAc(u)) A (A(S)
2
B (w)(k + lm(1/6))
2(k + In(1/6))
EAt
I E KN(5) PALA E KA(S)).
By Cauchy-Schwards this is at most
22h+ I0 (.A.ll/A,, A E (A(S)]PA[A E KR(S))
4=0
SLXD (w)(k In(1/6)
2(k + In(1/66) |A (AE
EA.t
PAJA E KN(S))-
n
h=
Using Stuchy-Schwarte again and Jensen's 's inequality, the first sum is bounded by
2h+ 16 EA,
h (w) A (n(S)]PPAAA KA(S))
h=0
+4 AA Kn(S)]
EA. [[) A KA(S))PPAAA E KR(S))
24 A |A E (S)
EA (A, A K,(S))PP E
h 0
h
24:+612(8/2344411r 11/2, (Aa)llha z
h=
233
Using Jensen's inequality on the second sum, find that
8.2 8.22/2 (w) + In(1/)))
2(k In(1/8))
EA.t
| KN(S)
PA Kn(S)]
n
n
7=
8CX/2 12 (w) In(1/8))
2(k + In(1/5))
BA.
+
n
n
For positive constants co, C1, C22 we have that the function f(t) (Veot + ci + c2) is concave for t 2 0. To this, we compute derivative
f(( = 2( oot + +2) 2/co +
Co = Cp +
CgC2
Vot +
29

---

and its second derivative
-c02
f"(t) 2(cot + 01 c/)3/2
This is negative function for / 2 O. We thus use Jensen's inequality conclude
+ In(1/6)) 8 SC (w) (C
2(k In(1/5))
EA,t
n
n
A,A,t (2 (w) (k + In(1/8))
2(h + In(1/5))
Combining all, we have thus shown
EALLAAD AD (ha,(w)) CXL (hA,((W)) 1.
SEA, 121/2 (m)) (xb(w))
(A: 1h+1n( (n(/8(1)))
2(k + In(1/5))
233 (A.ull/Acc(u>)l
11
n
8EA. (xb(w))
(k: + In(1/6))
2(k: In(1/)))
2d EA.t BA,, (wv)l)3
n
n
We now bound EA. [ as follows
BA. (
|A (hA Aw) S
SA.[[[|AA]]] + ((0) Awll2)
(IAAbOll== + (((IOVA)))) 47
FAI
BA.t
(l|Alllz 1/10)*
4
Σ
FA Awl 11-001-
b
6=0
Recalling that ||Aw|| (1/k)x²- have from the moments of the chi-square distribution that for even 1: 2
= (2
k/2)!
EA
< E...[|Aulll] k 2 (k: Am 12) k-
(k/2)) S 4.
Hence
E.. EA.ell/a.
S
4 10 (a-b) 1 (4 (4+11110 1/10)* < 54.
h=0
We thus have
EA CCT AD (ka,(w))
LX- (ha,(()) s
SEA, 2X (w)
(A: (k++I((1/0)
2(k: + In(1/5)
220
30

---

Finally, exploit that for any w E H(T, Ln)), we have by definition that 2l/44)7)110) (w)) S 2tt Thus for any such w, we have
/2 (w) EA.
EA,t (Ax(P((x))>DDy>b/A. (w), Ax) m//2]
(PR.) Ax) S 1//2
I ( (3/4)/)
+ B PA ( Ax) S <4/22 yw, x) > (3/4)ml
- cb (23/1)7 (w) + sup
[A Ar) S 7//2 y(w,x) = p4].
p>(3/4m
Using Lemma 5 and that 2 that this is bounded by
2(3/4)7 (w) E Lg by definition of H(',, L3), there is a constant c > 0 such
(3/ (3/4)) (w) cexp(=k(xx44))) 51t1 c (116c))
We have thus reached the conclusion that there is constant >> 0, such that with probability at least
1 8 over ~ D it holds that
EA (ha,,(w)) (A - (ha,t()))]] S
sup LE,,TT
(C++1 + exp( /c))(() lm(1/0))
+ ln(111/))
This completes the proof of Lemma] 7
D Within Constant Factors
In this section we prove Restatement Lemma There is a constant c > 1, such that for any < and any
r, (76 7411, it holds with probability at least - 8 over random sample S ~ D that
(3/4)/ (w)
(In(e72+1")
+ In(e/8)
Vu E H: (w)
The proof follows mostly the ideas in Grønlund et al. 2020a that were outlined in the proof overview in Section 2
Proof. Let l: > be a parameter be determined and consider the random construction of and as defined in Section 3.2 Let Ga be defined as in Section i.e. Gn contains all vectors in 2 4BC We say that matrix A in the support of and a training set is a-unusual, there is vector E Go such that
(1T/8) (w) < A
AD
(7/88/ (w)
2 + In(1/a)
2
n
For fixed matrix A and vector E Wh. we have by Bernstein's 's inequality and Es (7/8)) (w:) c(7/8)7) (w) that
(
J12 (7/8)7 (w) +
Ps
( (7/8) (w)
-
(7/8)7
(w)
t/ml < exp
nL
Setting
L (7/8)1 (w)
AD
= n
+
2
31

---

with = = 1n /a/n/////// an/n gives
C (w)
Ps
AA (w) -D
((7/8)7
(17/887 (w) >
+1
2
(1/5)11(() (w)
n²
LAD
+ +Z
2
2
< exp
n. n.AD
(7/8)/
(w)
Cap
(1//4)1 (wo) + +%)
AD
n² max m (1(7 (w), 233
I exp
2n m ([7/8)7
(w), 3} (
nZ
S exp
16
a.
A union bound over all w Go with a' a//22k gives that fixed matrix A is a-unusual for DD with probability at most
19u1 e
Now call training set S a-representative A is a-unusual for S with probability less than 1/4. By Markov's inequality, have
Es A [S, A) is a-unusual]]
Iss [SS A) is a-unusual] 2 1/4)
1/4
= 4. EA Ps (S, is a-unusual]]
< 4a.
Thus
Ps[S o-representative] 4a.
(27)
We claim that if the training set S is ô-representative, then it holds for all H that
(3//1)² (w) 2 + In(4/0) 30
(z(w) 2
n
To see this, consider an arbitrary such S and a w E H. Sample A and as in the previous section.
Call A, t good for u if it satisfies both ( s 4 and (7/8)) (hA.e 2 cb c33/4)) (w) 25 exp(-kr?2 (244). For ease of notation, let G denote the set of (A, t) that are good for w. Similarly, let Us denote the set of A where is d-unusual for S.
For all w E H. 7 E T, A and f, we have that
(3(w) > -T7 (ha,t(w) - PP PIxx)~sly(U,x)) > (Ayhha((w) Ax) S (7/8)
Thus
(w) EA,t AS (7/55/7 (hA, (wi) PIxcy)ssy(re x) 7 y Ax) & (7/8)sl]
2 EA,t ( (w)) (A, E G A A & Us]PPA, 1) E G.,. A A $ Us!
(28)
EAt s x) > >7Ay(bA.(w)), Ax) & (7/
(29)
For the term (88. we observe that conditioned on (A, t) E Gw, we have that ( 9. since [ Secondly, when A & Us. this implies by the definition of d-unusual that
(7/8) (hA,(w))
2 + In(1/o)
(7/819 (N)+ 2
LAD
2
Hence
(7/8)), (hA,((w)) CAA AS
EA.
(7/8)) (w)+ AD
2 + In(1/0)
EAt
(m Us CAAAAAAAAAPPAAAAAAGGAAAAA AMA
2
n
(30)
32

---

Using again that (A, t) Gwa we have that (30 is at least
(33/4)T (w)
2 k In(1/6)
2 PA, E G A U
25 expp(kh2++111 /2 (31)
We now bound P((A,t) t) E Gwd), and PIAA & Us}. For this, we recall that A 2 (1/k)x² k Thus X2-
E|ll Aw w and by Markov's, we get PI|| Awll 2 9 s 1/9. Conditioned on || < 9, we
have (M))(w)l22 - | Awwll + [ Awll2 I v + Vk(1OVK)22 < 4. Next observe that
AD
17 (hA.t(w)) 2 /3/10 (w) P (x (w, x) I
Ax) (7/8)74)
We have by Lemma that there is a constant > 0 so that E (xy)))/yyyy...... x) s (3/4)% A (w) Ax) > (7/8)
(xy))= P PAIly (w, x) S (3/4)% A Ax) > (7/8) S
Ph Ar) (7/8)al
sup
cexp(- (-((n-k)///o) S
cexpl ky, cexp(-ky,,11/ (22)))
Thus by Markov's inequality, we conclude
PANICAD (haL(w) LD (3/447 (w) - (ocxpp--h2+1/110
s FA. [IP (x.y))Dly( S A3/A))))(( Ax) (7/8)R8 5cexp(- ( (2))) < 1/5.
Finally, since assumed S is d-representative, ò-representative. We conclude by a union bound that
have PA A E Us} 1 1/4 by definition of
IAA:[((, t) E G A & Us] 2 1 1/9 1/5 1/42 1/2. In summary, we have shown that 31 is at least
c (3/44)
1
2 k In(1/0) -cexp((
2
Recalling that 28
gives
EA AS
(7/8)
(w)) 1 (A, E Gv A S G. A A $ Us| 2
c (3/44((w)
2 ln(1/5)
//
4
The term can be bounded using Lemma 5 by
EA by (Wi, x) > Y A y ()) Ax) & (7/8)n]] =
E E(x,y)-s PA
( (w), Ax) I (7/8))ll S
sup =EX:(1,0)>?
P Phe ( Ar) S (7/8)/] S
cexp( (hpp--k(y-0 - (7/8)1))/ed)
cexp( k- / (64c)) <
c)).
In summary, we have shown that for represetttteetttttvivee S, holds for all w E that
(w) c (3/4)) (w) 2 + In(4/0)
(=
n
We finally conclude from (27 that with probability at least 1 - 8 over S, it holds for all w E H that
(3/4 (3/4)a (w) 2 l + ln(4/)) 6cexp((k)
(z(w)= 2
4
n
Picking A: = 28 -2 In In(724 n) finally results in
cl
(3/44m (w)
220 220cl1(72+1))
2 (nee/)
(3(w) 2
4
7 n
This completes the proof.
33

---

E Auxiliary Results
In this section, we prove number of auxiliary results used throughout the paper. For this, need the following concentration inequality:
Theorem 17 /Wainwright 2019 example 2.11). Ler Xie then for any x E (0, 1) holds that
Y k
P
2exp(-ka² /8).
Restatement of Claim For any 0 < ô < L, it holds with probability - å over S ~ DD that 17 and 18) simultaneously hold for all Lg) and F; with slightly different constants
Proof. Let (76, M+1] be such that 7++1 = 2'n 1/2, Similarly, let (lg, EJ+1] be such that lJ+1
2 -1. Do union bound over all (T,, Lr)) for 1,... (g2 and j = O,... 182 n with 5.g = (8/e)² exp(-%%+ 2
In(e///+1) in (7). We see that
(ga //2)
182 n
lga
Σ
Σ
(0/e)² exp( In(e/Ej+1))
)=
1/((e,n"/))1g 1g2
Σ
Σ
(5/e) exp(-22 2- (nln(en2-)))
Ø=
182(e,n
Iga
Σ
(on))(en2-))-2
Doing the substitutions j t 1g2 n - j and i i (c,(cnn + - i, this equals
18a(e, 12) 1ng n
Σ
Σ
(8/e) ( ( -20
18 18a(e.n 1/2) 18g n
(5/e) 3 22 2-1
1=0
18. (/.n
2(8/e)3e-2"0 -01-2
< 6/2.
Similarly, do union bound over all P3 with 8, = (xc0))expp(771 In(e)))1)) in (8 We have
(sa(enn 1/2)
(2,
8, =
Σ
(6/e)* expl@exppppp exp(->xi In(e24)))
122(enn
Σ
(0/e)> -
182(aan
(o/e)²
Σ
(0/e)²
22
< (5/e)²
6/2
34

---

We thus have that with probability at least 1 - that for all (T;, Lj), we have
sup "EH(T.La)EE.
(D((w) Lz( S
c o( (vee
(I(e//(411) In(e/ôn)) n
In(e/(/+1)
In(e/Ona))
12
1411
n
(V/se (In(ef/sts)
+ In(e/drs)
In(e/(541)
+ In(e/6)
+
2412
and for all ; we have
LD
((3/4))3 (w)
In(e72+11)
In(e/de)
inf WEH
Lg) (w) 2
4
1 n
n
Lp
(3/44)
(w)
c c(2
In(e 3 In(e/d)
4
2
Restatement Claim 2 For any 6 < and training set S. if 17 and (8) hold simaltaneously for all (T;, L,) and T then (16) holds for all E (n=1/2, Cy) and all E H for large enough constant e (T6).
Proof. Let 0 < 8 < and assume as in the claim that (17) and 18 holds for all (T Lj) and F,. Now consider arbitrary 7 (n-1/2,co ..] and E H. Let and be such that (7 M41l and ((3/4))(()) (w) E (fa, with 7441 = 2'n 112 and lj+1 2 -1 We consider two cases. Let be the constant in Lemma First, if
9
(3/4)) (w) S 16 4 C
(In(e2(11))
+ In(e/5)
then since Co(w)= < 2/3/4)0 (w) and 7++ (using that In(er?n))(?2nn is decreasing in y for y n 1/2), we have already shown (16) for sufficiently large constant in (16). So assume this is not the case. Our goal is to show that Ej+1 and L (w) are within constant factors of each other so that we may replace occurrences of ljt1 by (w(w)) in (17). We first see that our assumption implies
In (nn( In(e/o)
lf+1 2 C
(3/4)/ (w) N 16
(32)
This also implics j + and hence l = 28, and therefore lstz < 22
2//3/4/3 (w). Letting x be the
constant in Lemma 3 we get from 17 and (32). that
(Ver e
In(e/(g1)) In(e/8)) 12t1
In(e/E5+1) 22
In(e/D) In(e/6)
[](w) (D(w) + H
n
n
c (3/4)) (w) + x (V (2220 (3/3))
In(e/8) Im(e7?+1n)
In In(en
+
12-1
n
n
< LD (w) +
(3/4)
(3131)7 (105/))((w))22)
(w)) (w)) (3/11)) (w) + L ((3/1)7((w)
(3/4)mc (w).
<3
Cp
We thus also have lj+1 2 LD
(3/4)) (w)
(3)) > (3 R
(1))..) Inserting this and In (In(3e (2)w))
32 in 17 gives
In(e/o))
In In(e
In(e/8)
Co(w) S (3( +
H
P2
n
2211 n
n
(33)
35

---

Finally from 18 and 7 2 Y/s we have
(3(w) 2 L (w))
(3/44) (w)
In(e7 In(e/6)
4
724
2 3+1
IIn (In(ey4+1n)
In(e/0)
4
12t1 n
n
From 32
this is at least f/1//1 and thus ly+1 S 1623(w). Inserting this in (33
finally gives us
3 (V |663(w))
In [In(2egg) (2((w)
In(e/6) In In(e 14441110 m)
In(e/0)
CD(w)= < (w) +
P+11"
7
14 n
n
Since 7++, this completes the proof of Claim for sufficiently large Onn
16
Restatement of 5, There is constant >> O, such that for any integer k: 2 and any 7 (0, 1], holds that P. PA.ell (l Ax) (w, x>) 7] < cexp(-"2kk/o
H. X
Proof. We start by observing that ||Aw]| || 12 and A - x) 2) 11//1/ w| - x=12 are all (1/k)x²
distributed. Using Theorem 17 with = 7/3, we have with probability at least 1 6exp( 1oxp((>>77 /72) that || A wll2 E 1 7/3, A = 7/3 and ||[ x) || 1 + 7/3). By the polar identity, this implies
1 (||Aw|)
(Aw, Aw)
| A ||A(W x))
(11wl122 + ||
||I
<11²) = 12
(mww) + || + ||2 - x=13)
4
S (w, + 7 (1+1+4)
12
(w,x) +
Let us condition outcome A of A satisfying the above. We then observe that
(w), Ax) = (h) Aw, Az) + (Aw, Ar).
By the randomized rounding procedure, we have that each coordinate i satisfies E,, ( (Aw).. Moreover, these coordinates independent. Letting A, (w),,(w)): (Aw); we then have that E[A] 0 and that A; lies in an interval of length (10v -_ Hoeffding's inequality
(w))
implies
PP (e) Aw, Ax)) > 7/2) PAA....
Σ A. (Ax)); > 7/12
A
2(7/2)22
2exp
E
(
50-21
2exp
||Ax||3/
S 2exp (-25>²k)
In summary, it holds with probability at least 1 - 6 eexp( kr² /72) 2expp(222)> 2 1
eexp(-ky2/25) that
(h), Ar) (w. x))
I (h),((w) Ar) (Aw, Ar)l + I(Au, Ar) (w,
< (1), - Aw, Ax)) +7/2
%
36

---

Remark 18. The value (AAw)) chosen such that E, (,((h,,(ww)) = (Aw), ie satisfying that
(Aw); = p(((w))) 20VE
1
Zi
+11 (1-p((Aw))))
24 ++
10vk)
2010
10VK
where 2, an integer such that
(1/2)(10()) + zi (10V/)) < (Aw); < (1/2)(10VI) + (+ 1)(00A)))
is nonnegative, and less than I.
Proof. By definition of 24-
(11/))(1V\)) + (100 (1- (1 = (Aw); + - (Aw);
(I-P((Aw):))
By definition of 2;, we have that the left hand side is a number in [0, (10v/)--] and thus we conclude
(1 p(((o)))) E [0, 1] + p((Aw)) E [0, 1].
Restatement of Remark 6 For any training set S and distribution D over X x {-1, 1}, we have
EA,t P (x,)) y (h), Ax) > n1/2 A y(w, x) s 0]] - E (x,y) D ( (w)
EA, PP (x.y) (ha,, Ax) > 7s/2 A y (w, x) S |]] > B @yy x))
EA IP (x,)) (x.1) (b Ax) S <n// A y (w,x) > 71] < (xx.)~s(p(y(ee
EA, P (xX))(())))))))) by ( Ax) S 4n/2 (w) x) > 0]] 2 (laxy>>D(p((())
In the proof, we will need the following monotonicity properties
Claim 4. We have PA..ly(hA, (w))),))........ Az) > k/2 y(w, x\ anl s FA.ll(hh.e())) Ar)
7s/2 y(w, 2) = for any 0 S 0
I a2
S %--
(..((w) (w), Az) < n/2 y(w,x) = azl s PA..u(hA.eu)) Ar) S Claim 5. We have PA l (h A,
/s/2 y(w, x) = anl for any 0n S 02 S %-
First we will prove Remark 6 using the two claims. Afterward, we will prove Claim and Claim 5
Proof of Remark
For convenience, let us recall the definitions of & and p:
P PAtly((A (w), Ar) > n v(w,x) a
if G, 5a50
((a)=
(r--a) A. (.) Aa) > r/2 ((w,))=
if < a S
if a <ase,
(AA))((hAa(w)).AA)) S 7/2 y(w,)) =a
if <asc
p(a)
(PA.s((ha Ax) n/ x(w,z)= nl
if0 < a <
TO
- c, 5a
We handle each of the inequalities in turn. First we see that
EA.
(w), Ax) 1/2 (w, x) < 0]
E PA Ax) > 7//2 / x) < 0]] V
E E(xy)) ( x))]
Here the inequality follows from the observations that (y x)) > 0 for y(w, x) > 0. whereas
P P (y (w), Ax) > n//AAy(u, x) < <0 = 0 for such y(w, x). Similarly for (w, = a < 0.
we have ((y(w, x)) = (Ps.U((A, Aa) > 7/2 y(w, x) = a) = PAA Az)
7/22 A y(w, x) < 0 y(w,z)= a].
37

---

Similarly, we have
EA, PAyyP Ax) > 71/2 y (we x) S 5n]
(Fxx)>s((AAAlyyahaaaa Az) > n/2 y (.,)) x) S 7|]
B(x,y)~ (PAA Ax) > 7// y (1c, x) S ni] 2 B(x,)) (0yyssll(((uu) (w, x))].
The last inequality follows by observing that if y(w,z) > T. we have o(v(u,,)) .)) 0 and PA.t (A,,,yh ; Ax) > 71/2 A y(u, x) 77]] = 0. For a = y(w,4) with 0 < a I %. we have ((a) = --- PA. (PP..ly(aaaa.. (h., Ax) > y x) = 0] s Padlv(h),(()) Az) > >//2 y(w, X) al. This uses the monotonicity in Claim Finally for y(w,z) = a S 0, the two coincide as in the above argument.
y(w,z) = a] = PA. u (w), Ax) > >n/2 A y(w,z) 2) S
Symmetric arguments for P gives
EA,, IP (x.) Ax) /1/2 A y (w, x) = [x Sa (PA.,)y(hh,, Ax) 21/ y (w,x) 7 S
Ax) S / A y (1,
71 S
( (w,,
Here the last inequality follows from the following considerations. For y(w, x) = a with a S % we have that IP A, ju ((.,), Az) S x/2 A y(w, > 7:] = 0 and p always non-negative. For a > The we have p(a)) = PA (h Ar) S n/2 ((w,, .) = a] = (())) Ax) S 7s/2 A y(w,,) > 7 v(w,x) a] and the two coineide.
Finally, we have
Ef IP (x.lPexx))-lly(haaa Ax) S 4/2 A y(,,) 0J =
Ea.
E BI PA (w), Ax) S 4/2 y (w, x) > 0J 2
Px (w, (w)))))
Here the inequality follows by observing that for y(w, x) = a with I O, both p(a) and F (A.ely(hA,e Ax) < 7a/2 22 A y(w, x)
S 7i we have by definition are For 0 < a
Ar) S n/2 v(w,,x = a] < PPAlu((h, y(uxx) a] = FA. (AA, Ax) I n/2 2 A y(w,,) > 0 y(w,z) = al. where we used that
that p(a) = "o
Ax) 3 x/2
P
I 7 v(w,z) = a: is decreasing in a (as stated in Claim 5 Finally, for %o the two coincide above.
Proof of Claim 4 Let T1, Y1 be such that 0j := yn (w), 21) and let W2, T2, 3/2 be such that
02 = y2 (W2, T2). Consider sampling X,, Y. ~ NNO0. 1/k) independently. Also sample offsets
t t,, t/ uniformly and independently in [0, 1] and let X be X; rounded based on t/ as above. Let
Z, = Y a + /1- Y and Z2 x2 + /1 /1-agy Y Then the marginal distribution of
(X', Z2) equals the distribution of (hA, (w;) y/ Ar = yj (h,,) Ar2))-
Consider now an arbitrary outcome X', X of X, X'. We have (Z,,'') 2 n/2 if and only if 7/22. We also have that (Y,X') ~ (0, | /k) and thus ax(X, + / 11 2
P[ X") 2 h/2
X') 2 71/2) =
1 1- 1 (VT. 24/2 az (x, VT.
- ))
1 1- + VT: 11/2 a1 (x ))
VI 11aa oz
VI-at
① Vk. 1/2 - a1 (X,X')
(Vk. 11/2 as X')
$
(34)
V1-
V
Here (--) denotes the cumulative density function of the normal distribution with mean 0 and variance 1. Now let
== Vk. 7 - 01 (X,
V1 of
38

---

and
t:= Vk. 11/2 - ax2
V1 $1-az az
Consider now the derivative
Vk. 71/2 oxX, vk. 0n - (X, -X, x")
da
-1-
(1-a2)3/4 a2)3//2
Assume first that || 2 9/10. Then (X,X") 8/9 by Remark
14 Now since o /2 S n2/22 S
2 & 1/9 for by small enough. Thus the derivative when |
9/10 is no more than
V (1/9 8/9) S kV
This implies u -22 7(a2 - a1)/k/9 > 0 and therefore
PZ X') 2 / ž Pi X') 2 %/2].
If we in addition have that | S 4/3, then we may even show that the difference in probabilities large as a function of (r2 <x as follows
P[ X') 2 ///2 x2
1
12 dx
2T sa
2 e maxag a²/2 7Vk(a2 a1)
9v/2
Observing that
max a² S (E(,,)) 1 2
-max (X,
use Remark 14 to conclude X') < (10/9) 12 and thus u² < 2k < 3k77 for
cy S 1/v2.. This gives that for any X with 10 - | v 4/3, it holds that
34m /2 7Vk(o2 a1)
PiZZz, X") 2 // / - (2, X") 2 /
9/2
For |X|] 9/10, we have |X | - x 2 S | X + |X|1 S V k(10Vk)-2
99/10 10 & 11/10. It follows by Cauchy- Cauchy-Schwartz that (X, - ||x||2 || S V9/10-
11/10 < 11/10. For S S 2 < /2 < 1/v8 for c, - 1/v2, this upper bounds the derivative by
Vi. 11/10 2v/
(1 11-1/833/2
2 we already have that
P p(Zz2,') 2 7/2/ - - X') 71/2 20.
So assume u f. The bound on the derivative gives that l -- u S 2Kk(122 - -ai) and conclude
PIZZZ x² 2 2/ P 74/2
122
2m Juu
2 2V - aa)
2 - mi
V2T
2VT(a2200 aa)
22
We finally conclude
PIIZ2, X") 2 - P( X') 2 7//2/
7Vk(a2 - -1) PI| 1 <9/10]
2V a1)
P99/00 < |X| < 4/3] - -3/7//2
(35)
9
/2
39

---

Using Theorem 17 we get
P|9/10 - | 4/3]
2 eexp(=k/800)
(36)
and
X 2 9/10 - 2 2exp(-k/800)
For h at least a sufficiently large constant, we have that 336 is at least 1/ 1/2 and we get that 35 is at least
/2 7Vi(a2 ai)
k/8000 4vh(a2 a1)
18
2t
For the constant ey sufficiently small, this is positive as 7/ S Cy.
Proof of Claim 5 Similarly to the proof of Claim 4 let wi, T1 l/1 by such that = (w1.1.2)
and let W2, Z2, 4/2 be such that 02 1/2 (2)) Draw X, X and Zi Zz as above. Consider again an arbitrary outcome X", X of X' We have (Zj, X²) S 76 if and only if (X, X')
03 Y. X') (Y) I 12/2. Hence
P((Z1, X") S S//2 P( x²) S ///2==
① Vk. n/2 a1 (X)
- $ Vk. n/ 1 a2,
V1
V1-
This has the exact same constraints 0 a1 S a2 S 7/s and exact same form thus follows from the proof of Claim
33 The conclusion
Restatement of Remark 13
x < 4/3, then
X 3 < 2.
Proof. By the triangle inequality, and using that all coordinates of X - X'' are bounded by (10v K)) in absolute value, we have
X = ||X - x + x
S (IIX' X112 + 1|x111)
< [k(lovk)= ([ 2 v4/3
(1/10+ + /4/322
2.
Restatement of Remark 14 1 2 9/10, then (8/9)||X < (X, X') (10/
Proof. We have:
(X' = - =
|
Since each coordinate of X' -X is bounded by (10 k) -1 in absolute value, it follows by Cauchy- Schwartz that
XX' - X, $ |X X 12 ||||2
X
1(10VA)
X |
X 1
10 9/10
X 1//99.
The conclusion follows.
40

---

Restatement of Remark 16
For any distribution D over X x (-1,1}, 1), fixed w E H. margin y and any A E kxd it holds with probability at least over DD' that
8C ( In (1/6) 2
(w) - C (w))) _
"
Proof. Since As (w) is an average of n i.i.d. 0/1 random variables with mean LAD (w), we get from Bernstein's inequality that
8L 8L (n)(111((11))
2 2l((1/)
PSWD
(1)(1)) - [hs(w))>>
n
1 (V8CAD())n + (101)))222mmmmm (l((1
exp
(l) + (V + 2lm(1/8)
max (8C)) (w)n, (
exp
8 max (w) 4lm(1/)) V2 max (w), In(1/6)) In(1/5)
Using that In(1/0) < 1 max ( (1) this is most
1n(110)
dXs
I <xp( ln(1/)) = 6.
5 +
41


Reviews:
[{"review_id": "vGQ6nrwE1s", "reviewer": "Reviewer_kXmV", "summary": "The paper studies the risk of large-margin halfspaces in a standard statistical learning setting.\nThe authors prove a novel bound on the generalization error $L\\_D(w) - L\\_S^{\\\\gamma}(w)$ for any $w$ in the unit $d$-dimensional sphere, where $L\\_D(w)$ is the true risk of $w$, which exactly matches the best known lower bound for every margin $\\\\gamma$, empirical $\\\\gamma$-margin loss $L\\_S^{\\\\gamma}(w)$, sample size $n$, and confidence $\\\\delta$.\nBy doing so, they close the residual gap in the generalization error upper and lower bounds from previous work.", "questions": "- Do the authors believe some of the techniques adopted can be easily extended to other settings, or are they particularly tailored to the geometric nature of the large-margin halfspaces?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The main result of this paper is pretty clear: it pins down the generalization error of large-margin halfspaces up to a constant factor.\nThis optimality is achieved through a careful random discretization that first projects with Johnson-Lindenstrauss and then rounds so that the distribution of the rounded margin equals the original one, allowing a cancellation between terms that previous approaches could not exploit.\nIn their \"meet in the middle\" bound, the authors even employ a clever multi-scale chaining argument over a countable sequence of grids that removes another residual $\\\\exp(-k/c)$ factor, thus allowing to select the optimal projection dimension without compromise.\nThe combination of various different techniques in such a way shows a deep understanding of the problem and a solid technical advancement.\n\nA minor flaw of the paper is that it often omits some central definitions as they are given for granted, which makes it hard to follow the paper for readers not familiar with the topic.\nJust to give one example, the authors never define $\\\\mathbb{B}^d_2$ nor $\\\\mathcal{S}^{d-1}$, which one may assume to be the unit ball and sphere in $\\\\mathbb{R}^d$, respectively.\nI suggest the authors to clearly define all the adopted notations like these ones in the introduction or in some preliminary section, mainly to avoid any ambiguity.\nHowever, this is not a major issue as the paper is otherwise well-written.\nIn particular, the proof of the novel generalization error upper bound has a clear structure and can be followed despite its technical nature.", "was_revised": true, "final_justification": "I keep my already positive initial evaluation since no sudden concern arose during the discussion.", "rebuttal": "Thank you for the thorough review.\n\nWe agree that omitting definitions makes the paper hard to follow, we will make sure to include definitions of $\\mathbb{B}^d_2$ and $\\mathcal{S}^{d-1}$ in the final version. We will also skim through the paper to make sure that there aren't other missing definitions.\n\nAs for the question: Do the authors believe some of the techniques adopted can be easily extended to other settings, or are they particularly tailored to the geometric nature of the large-margin halfspaces?\nYes, we believe the techniques are general enough that they should have applications elsewhere. In particular, random discretizations have previously been used in generalisation bound proofs of e.g. voting classifiers as mentioned in the first line of Section 2.1 [Schapire et al. 1998]. For voting classifiers, a similar gap remains between the upper and lower bounds. We believe our technique is not as such tied to the geometry of half spaces, but instead gives a general way of performing a tighter analysis of random discretisation techniques via the use of Rademacher complexity. Of course, there would be many new problem specific details to work out, but we find the direction promising."}, {"review_id": "i4IhErLZtM", "reviewer": "Reviewer_fuQC", "summary": "This paper proves the first generalization bound for large-margin halfspaces that is asymptotically tight in the tradeoff between margin, fraction of training points with the given margin, failure probability, and number of training points. The authors improve upon previous work by Grønlund et al. (2020) by closing the gap between upper and lower bounds. The improvement in tightness pins down the exact generalization performance for the classical halfspace classifier model. The novel techniques used in this paper may also inspire future theoretical analysis on the generalization bounds of other ML models.", "questions": "## Major questions\n1. **Future direction**: In lines 65-66 on page 3, the authors claim that “Furthermore, our proof of Theorem 2 brings several novel ideas that we hope may find further applications in generalization bounds”. What are the possible future research directions of this work? For example, could the tighter bound be applied to improve other theoretical results?\n2. **Extension of the proposed method**: Do the techniques developed here have potential applications to other learning models beyond halfspaces?\n\n## Minor Issues\nHere are some minor punctuation problems and typos:\n1. Eq. (5) requires a period (“.”) at the end.\n2. Eq. (17) requires a period (“.”) at the end.\n3. All the terms in Eq. (19) are right-aligned, which is inconsistent with the formatting of other equations in the paper. I could be wrong, but it might be clearer if the second and third terms on the right-hand side of Eq. (19) could be shortened by introducing intermediate notations, allowing for a more consistent left-aligned format. \n4. There is an additional space before line 255 on page 8.\n5. It would be better if the equation between lines 284 and 285 on page 9 could be left-aligned.\n\n## Missing citations related to SVM \n[1] Yuzhou Gu, Zhao Song, Lichen Zhang. “Faster Algorithms for Structured Linear and Kernel Support Vector Machines”. ICLR 2025.\n[2] Vladimir Vapnik, Rauf Izmailov.  “Learning using privileged information: similarity control and knowledge transfer”. JMLR 2015.\n## Missing citations related to Kernel method\n[3] Timothy Chu, Josh Alman, Gary L. Miller, Shyam Narayanan, Mark Sellke, Zhao Song. “Metric Transforms and Low Rank Representations of Kernels for Fast Attention”. NeurIPS 2024.\n[4] Josh Alman, Timothy Chu, Aaron Schild, Zhao Song. “Algorithms and Hardness for Linear Algebra on Geometric Graphs”. FOCS 2020.\n[5] Corinna Cortes, Mehryar Mohri, Afshin Rostamizadeh. “Generalization Bounds for Learning Kernels”. ICML 2010. \n[6] Jan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein. “Training (Overparametrized) Neural Networks in Near-Linear Time”. ITCS 2021.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "## Strengths:\n1. **Clear paper organization**: The proof is thorough and well-structured, with clear organization into lemmas and auxiliary results. The authors carefully handle all technical details.\n2.  **Well Justification**: Despite the technical complexity, the paper provides good intuition through a detailed proof overview (Section 2) that explains the key ideas and improvements over previous approaches.\n3. **Novel technical contributions**: The proof introduces several innovative techniques that collectively enable the tight bound. First, the authors develop a more refined analysis that tracks both positive and negative changes in margins during random discretization, moving beyond previous one-sided approaches that only considered margin violations in one direction. Second, they employ a sophisticated application of Rademacher complexity theory with carefully bounded Lipschitz constants, achieving sharper control over the generalization gap through an improved use of the contraction principle. Third, to handle the challenge of varying norms in the discretized hypotheses, they introduce an infinite sequence of grids with an intricate union bound argument.\n## Weaknesses:\n1.  **Lack of a formal conclusion section**: The paper ends after completing the main proof without a dedicated conclusion section that summarizes the contributions, discusses the broader implications of achieving tight bounds, or suggests future research directions. This is a minor structural issue that could be easily addressed by adding a brief concluding section.\n2.  **Lack of a related work section**: The paper lacks a related work section that positions the contribution within the broader landscape of generalization theory and margin-based learning. However, this is not a major concern, as the clear comparison with Grønlund et al. (2020) in Section 1 has already highlighted the novelty of the contribution, and this issue can be easily fixed by adding a related work section.", "was_revised": true, "final_justification": "The paper proves a fundamental result, I recommend acceptance.", "rebuttal": "Thank you for the thorough review.\n\nThank you for suggesting the creation of additional conclusion and related work sections. We agree that the paper ends rather abruptly, and will strongly consider including a summarizing/concluding section in the final version. We were severely challenged by the page limit and went for giving as clear an overview of the proof structure as possible. As the (potential) final version for NeurIPS allows an additional page, we will prioritise a proper conclusion.\n\nIn the introduction of the paper, we aimed to give an overview on how the result improves over the most closely related prior works. Given an additional page, we will put emphasis on discussing related literature more broadly as suggested by the reviewer.\n\nAs for your questions, In lines 65-66 on page 3, the authors claim that “Furthermore, our proof of Theorem 2 brings several novel ideas that we hope may find further applications in generalization bounds”. What are the possible future research directions of this work? For example, could the tighter bound be applied to improve other theoretical results?\n\nDo the techniques developed here have potential applications to other learning models beyond halfspaces?\n\nWe have one joint answer for the two questions (if we understand them correctly). As also mentioned in our response to reviewer kXmV, we believe our techniques also have a chance of improving known generalisation bounds for voting classifiers as the proofs there rely on the same random discretisation strategy and is lossy in the same way as the Gr\\o nlund et al. paper. If the technique can indeed also be applied there, we see no reason why it shouldn't have other applications as well.\n\nAdditionally, thank you for pointing out typos and additional references, we will carefully go over each of the proposed references to make sure an expanded related works sections covers all necessary references."}, {"review_id": "zHvHQstK86", "reviewer": "Reviewer_kkYb", "summary": "This paper presents a new, asymptotically tight generalization bound for large-margin halfspace classifiers. The primary contribution is a novel upper bound (Theorem 2) that characterizes the trade-off between the true error of a classifier and its empirical margin loss on a training set. This new bound matches the existing state-of-the-art lower bound. \n\nThe work builds upon the previous state-of-the-art bound by Grønlund et al. [2020], which had a small gap compared to the established lower bound. The authors identify and overcome key barriers in the prior proof technique, which relied on random discretization and a framework from Schapire et al. [1998].", "questions": "1. The proof relies on a sophisticated random discretization process involving a Johnson-Lindenstrauss transform and random snapping to a grid. While this is used as a proof technique, does it offer any algorithmic insights? Could a learning algorithm based on this discretization be practical or offer any advantages?\n2. \"While one might argue that our improvement is small in magnitude, this finally pins down the exact generalization performance of a classic learning model\". Could you elaborate on the importance of closing this final gap? Does it resolve any long-standing theoretical questions or open up new avenues of inquiry that were previously blocked by the discrepancy in the bounds?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. The paper proves the first generalization bound for large-margin halfspaces that is asymptotically tight. This result is significant as it settles the precise generalization performance of a classic and fundamental learning model. \n2. The proof introduces several novel ideas that could be applicable to other generalization bounds. These include a more refined analysis of error terms that avoids inequalities used in prior work, a new application of Rademacher complexity to bound these refined terms, and a method using an infinite sequence of discretization grids to handle error probabilities more effectively. \n3. The paper provides a clear and detailed proof overview to build intuition before presenting the full proof. The main theorem is rigorously proven with all assumptions stated, and complex arguments are broken down into smaller, more manageable lemmas with deferred proofs in the appendix for clarity. \n\nWeakness:\n\nN/A", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thorough review.\n\nAs for your questions: The proof relies on a sophisticated random discretization process involving a Johnson-Lindenstrauss transform and random snapping to a grid. While this is used as a proof technique, does it offer any algorithmic insights? Could a learning algorithm based on this discretization be practical or offer any advantages?\n\nThis is a very interesting question. We are aware of one previous work that has actually built on exactly this idea to develop a new learning algorithm. The paper \"Replicable Learning of Large-Margin Halfspaces\" from ICML'24 builds on the Gr\\o nlund et al. proof technique, with JL + random snapping, to get a better learning algorithm. It seems highly likely that other applications exist. \n\n\"While one might argue that our improvement is small in magnitude, this finally pins down the exact generalization performance of a classic learning model\". Could you elaborate on the importance of closing this final gap? Does it resolve any long-standing theoretical questions or open up new avenues of inquiry that were previously blocked by the discrepancy in the bounds?\n\nYes we believe it solves a long-standing open question. Proving generalisation bounds for large margin half spaces has been an active line of research at least since the first bounds by Bartlett and Shawe-Taylor in 1999. They considered the exact same setup and thus we believe it is fair to say that we close a line of research that has been going for 25+ years. As also mentioned in our reply to reviewers fuQC and kXmV, we believe our new technique may also be applicable to other learning problems now that we finally have a technique capable of proving completely tight bounds."}, {"review_id": "eHmnmCWmiL", "reviewer": "Reviewer_VQkK", "summary": "The paper considers the problem of learning halfspaces with large-margin and provides tight generalization bounds for this problem. More precisely, assume that we have an unknown distribution $\\mathcal{D}$ over $B^d\\times\\{0,1\\}$ where $B_d$ is the $d$-dimensional unit-ball, and assume that we have a sample $S$ of $n$ i.i.d. samples $\\mathcal{S}:=(x_i,y_i)_{1\\leq i\\leq n}\\sim\\mathcal{D}^n$. We are interested in relating the true loss $\\mathcal{L}_D(w)$ for a unit vector $w\\in\\mathcal{D}$ (which is defined as the probability under $\\mathcal{D}$ that $\\mathrm{sign}(\\langle w,x\\rangle)\\neq y$) to the $\\gamma$-margin empirical loss, which is defined as the fraction of samples $(x,y)\\in S$ satisfying $\\langle w,x\\rangle\\leq\\gamma$.\n\nThere are previously known results providing lower bound and upper bounds of $\\mathcal{L}_D(w)$ in terms of $\\mathcal{L}_S^\\gamma(w)$. While the previous upper and lower bounds are very close and almost match, there were still a gap between the two. The paper provides a tighter upper bound which asymptotically matches the previously known lower bound, and hence it is (asymptotically) tight.", "questions": "- Page 1, line 17: What is $\\mathbb{B}_2^d$? Is it the hypercube $\\{0,1\\}^d$ or is it a $d$-dimension ball?\n> - If it is the hypercube, is this restriction important?\n> - From the discussions in the text it seems to me that most likely it is a $d$-dimensional ball, but then what does the 2 subscript represent? Is it the radius?\nPlease explain and properly define the non-standard notations in the paper.\n\n- Page 6, line 195: What is $\\mathcal{X}$? I might have missed the definition but it doesn't seem to me that it was introduced anywhere. From the discussions in the paper, it seems to me that it is the set of all unit vectors satisfying $\\langle w,x\\rangle \\leq c_\\gamma$. Is this correct? If so, please explicitly say that.\n\n- Page 7, line 224: Claims 2: I think that \"with probability at least $1-\\delta$\" should be added to the claim, right?\n\n- Page 8, line 243: Shouldn't \"$p(z_i)$\" rather depend on $(Aw)_i$? Perhaps it should be written $p((Aw)_i)$ to be more formal?\n\n- Page 8, line 254: (Minor comment:) The formatting/rendering of equation (19) is a bit weird.", "limitations": "Since this is a theoretical paper, I do not see any potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper provides an asymptotically tight upper bound of the generalization loss on terms of the margin empirical loss. This closes the gap between the upper and lower bounds and settles the problem of characterizing the the generalization loss in this setting.\n- In terms of novelty and originality, I find the idea of writing the difference between the loss as an exact sum of difference terms (including Equations (12) and (13)) particularly elegant. This ultimately enabled the authors to perform a very tight analysis of these difference leveraging the powerful machinery of Rademacher complexity.\n- In terms of technical correctness, while I cannot 100% vet that all the details of the proof are correct as I have not read the appendices, I did not find major mistakes in the high-level description of the proof in the main body of the paper. Though I have not thoroughly checked all the math, the general proof strategy makes sense to me.\n- In terms of clarity and presentation, I find that the structure of how the high-level ideas are presented to be generally done well: I like how the authors motivated their work by starting with a high-level description of the proof of the tightest known upper bounds. The authors described the barriers for such approach to achieve an upper bound matching the lower bound and then explained their strategy (to overcome these barriers in order) to get a tighter upper bound matching the lower bound.\n\nWeaknesses:\n- The paper sometimes use notations without properly defining/introducing them. The reader can generally understand the intended meaning from the context in most cases, but this is not always the case. Carefully defining the non-standard notations would definitely improve the readability of the paper. Please refer to the questions below.\n- Even though the overall clarity is good, the math writing can be made slightly clearer and more formal in some cases.", "was_revised": true, "final_justification": "The authors have addressed the questions that I had (which were mostly minor), and I can see that the reviews of the other reviewers were similarly positive. I hence keep the score of 5.", "rebuttal": "Thank you for your thorough review.\n\nAs other reviewers have said as well, there are definitions missing. Thank you for pointing it out, and for the given examples. In the final version of the paper, we will take special care to make sure that the notation is clear.\n\nAs for your questions, Page 1, line 17: What is $\\mathbb{B}_2^d$? Is it the hypercube ${0,1}^d$ or is it a $d$-dimension ball?\n\nBy $\\mathbb{B}_2^d$ we refer to the unit ball, in $d$ dimensions, with respect to the $\\ell_2$-norm. So it is the Euclidian unit ball. We will make this more explicit in the final version of the paper.\n\nPage 6, line 195: What is $\\mathcal{X}$? I might have missed the definition but it doesn't seem to me that it was introduced anywhere. From the discussions in the paper, it seems to me that it is the set of all unit vectors satisfying $\\langle w,x\\rangle \\leq c_\\gamma$. Is this correct? If so, please explicitly say that.\n\nYou are correct, it is already explicitly stated on page 6, line 193-194, but phrased a bit convoluted. The sentence \"which is the set...\" is meant to define $\\mathcal{X}$.\n\nPage 7, line 224: Claims 2: I think that \"with probability at least $1-\\delta$\" should be added to the claim, right?\n\nActually not. We can see that this is phrased in a slightly confusing way. line 224 refers to eq. (17) and (18) both holding simultaneously. Indeed these two equations hold with probability 1-delta. But what we are claiming here is that whenever (17) and (18) hold for some value of delta (delta appears in those two equations), then (16) also holds. The claim that (17) and (18) together imply (16) doesn't really need to know what the probability is that (17) and (18) hold. Of course, we eventually use the claim via union bound over the events in (17) and (18) to establish the claim in lines 195-197.\n\nPage 8, line 243: Shouldn't \"$p(z_i)$\" rather depend on $(Aw)_i$? Perhaps it should be written $p((Aw)_i)$ to be more formal?\n\nYes, you are correct, p(z_i) does depend on (Aw)_i. We will make that more clear in the final version of the paper.\n\nPage 8, line 254: (Minor comment:) The formatting/rendering of equation (19) is a bit weird.\n\nWe agree that the formatting is weird, we will try our best to make it less weird."}]

Author rebuttal:

Meta-review: The paper proves tight generalization bounds for large margin classifiers with classification loss bounded by gamma margin loss on the right. The paper is well written and clear and all reviewers agree that the paper is a strong contribution.

Please include the references pointed to by reviewer fuQC with detailed discussion, these seem very relevant to the result at hand, especially the one on generalization on kernel methods.
Decision: Accept (spotlight)