CS Paper Radar

Sharp margin-based generalization bounds for realizable SVM

Steve Hanneke, Aryeh Kontorovich

cs.LG stat.MLmath.ST ·submitted 2026-09-15 21:03 UTC · v1
theory

Abstract

Let the exact homogeneous hard-margin support vector machine be trained on \(m\) independent observations from a Borel probability law on a real Hilbert space. We prove that, with score zero counted as an error, there is a universal numerical constant \(C\) such that \[ \Pp\left( γ_m>0,\quad \Risk(u_m)> \frac{C}{m} \left( K_m+\log\frac1δ \right) \right) \le δ. \] Here \(γ_m\) is the empirical homogeneous margin, \(u_m\) is the exact minimum-norm unit-margin separator, \(r_m\) is the largest training radius, and \(K_m:=r_m^2\norm{u_m}^2=r_m^2/γ_m^2\) on \(\{γ_m>0\}\). The proof is driven by a deterministic deletion problem. Given vectors \(x_1,\ldots,x_n\) in the unit ball, delete a set \(B\) of constraints and let \(u_B\) be the closest point to the origin that satisfies every retained unit-margin constraint. Suppose that \(\norm{u_B}^2\le k\) and that every deleted vector has nonpositive score under \(u_B\). We prove that a family of such deletion sets of cardinality \(q\) has size at most \(\exp(8k+2q)\). The conceptual step is an exact identity obtained from the KKT representation of \(u_B\). For a random deletion set, the identity converts the mean squared spread of the separators into a weighted sum of score deficits. It therefore forces a coordinate whose deletion status separates the two conditional means by a quantitatively large amount. Revealing that coordinate decreases the conditional separator variance enough to control the binary entropy of the split. An entropy induction gives the deletion count, and an exact factorial ghost-sample identity converts that count into the stated high-probability SVM bound.

Closest papers

Nearest neighbours by meaning across the whole index.

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.58
Abstract · 35 pages, 2 figures

We study the problem of \emph{adversarially robust} PAC learning. In this framework, the learner observes independent samples from an unknown distribution over $\mathcal{X} \times \{0,1\}$, as in classical PAC learning. However, given a perturbation map $\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}}$ known to the learner, the goal is to output, with high probability, a predictor that correctly classifies \emph{every} perturbation $z \in \mathcal{U}(x)$ of most future examples $(x,y)$ drawn from the same underlying distribution. We determine the \emph{optimal} $\mathcal{U}$-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class $\mathcal{H}$ of $\operatorname{VC}$ dimension $d$, we prove upper bounds of $\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big)$ in the realizable setting and $\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big)$ in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs \emph{no additional} distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call \emph{binomial-bagging}. We believe that binomial-bagging and its analysis may be of independent interest.

0.17

Optimal VC Dimension of Contrastive Learning with Margin

cs.DS cs.LGstat.ML ·2026-09-30 ·Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo, Konstantin Makarychev
theory similarity 0.58
Abstract · Main result obtained in April 2026 without the use of AI

Contrastive learning is a successful paradigm for learning $d$-dimensional geometric representations from a collection of ``anchor--positive--negative'' triplets $(i,j^{+},k^{-})$, indicating that ``item $i$ is closer to $j$ than to $k$.'' Despite its success, understanding why contrastive learning leads to representations of high \textit{generalization} quality---beyond the often pessimistic predictions from PAC-learning---remains a central question. Recently, \citet*{alon2024optimal} proved that, for PAC-learning $d$-dimensional Euclidean representations of $n$-point datasets, $Θ(\min(nd, n^2))$ triplets are necessary and sufficient, while they posed as an open question whether their VC dimension bounds for the more realistic setting of \textit{contrastive learning with a margin} can be improved. For a margin parameter $α>0$, a triplet $(i,j^{+},k^{-})_α$ is satisfied by the embedding $φ:[n]\rightarrow \mathbb{R}^{d}$, if $\|φ(i)-φ(k)\|_2>(1+α)\cdot\|φ(i)-φ(j)\|_2$. In this work, we resolve their question by proving that the VC dimension of contrastive learning under any margin $α\in(0,1)$ is in fact $O(n/α^2)$, improving on the previous bound of $O(n\log(n)/α^2)$. We also establish that the bounds are optimal up to constant factors, by providing a matching lower bound of $Ω(\frac{n}{α^2})$ (the previously known lower bound was $Ω(\frac{n}α)$), for $α\geq \max(n^{-1/2},d^{-1/2})$.

0.24

Fast Learning Rates for Physics-Informed Kernel Methods

cs.LG stat.ML ·2026-09-16 ·Luc Brogat-Motte, Joachim Bona-Pellissier, Giacomo Meanti, Lorenzo Rosasco
theory similarity 0.57
Abstract

In physics-informed machine learning, a target function $u^*$ is learned from noisy value observations $y_i=u^*(x_i)+ \varepsilon_i$, together with differential information, given either by noisy observations $d_j=(Du^*)(z_j)+ξ_j$ or by a known physical constraint $Du^*=v$. We consider the setting where $D$ is a linear differential operator and analyze a physics-informed kernel estimator $\hat u$ combining $n$ value observations and $m$ differential observations. In this context, we ask how much can differential information improve predictions, and how does this improvement depend quantitatively on $n$, $m$, and $D$. We prove finite-sample bounds, supported by numerical simulations, revealing a two-regime structure for the prediction error. When $m$ is limited, the rate depends jointly on $n$ and $m$; when $m$ exceeds a problem-dependent threshold, the rate saturates and matches the oracle rate obtained when the perfect constraint $D \hat u = Du^*$ is imposed. Examples are discussed for Sobolev spaces which are reproducing kernel Hilbert spaces and include partial Laplacian constraints on the torus and gradient observations on bounded domains. These examples illustrate the range of possible learning rate improvements --- from the standard nonparametric $n^{-1/4}$ to the parametric rate $n^{-1/2}$. Finally, we derive physically consistent rates in a stronger norm that jointly controls the errors in $\hat u$ and $D\hat u$.

0.55

Euclidean SVP is deterministically NP-hard to approximate within any constant factor

cs.CC math.NT ·2026-08-12 ·Daqing Wan
theory similarity 0.56
Abstract · 27 pages, major revision

We prove that, for every constant $ρ>1$, the Euclidean shortest vector problem is NP-hard to approximate within any constant factor $ρ$ under a deterministic polynomial-time many-one reduction. This extends our previous deterministic NP-hardness result from $ρ<\sqrt 2$ to arbitrary constants and gives a deterministic version of Khot's randomized arbitrary-constant theorem.

0.45

Last-Iterate Convergence of Clipped SGD with Linear Decay

cs.LG math.OC ·2026-10-13 ·Wei Jiang, Haomin Bai, Zechao Li
similarity 0.56
Abstract

In this paper, we study the last-iterate convergence of clipped stochastic gradient descent under heavy-tailed noise. We assume that the stochastic gradients are unbiased and that the noise has a bounded central $p$-th moment, where $1<p\le2$. For smooth convex objectives, a linearly decreasing learning rate gives a high-probability error bound of order $O(LR^2\log(1/δ)/T+σR(\log(1/δ)/T)^{(p-1)/p})$. We further establish last-iterate guarantees for nonsmooth composite objectives and smooth composite objectives with proximal updates. In addition, when a causal adversary replaces at most $q$ gradients, the same clipped update achieves a bound with $\log(1/δ)$ replaced by $\log(1/δ)+q$. The corresponding lower bounds for the clean and corrupted oracle models are also provided.

0.33

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

cs.LG cs.ITstat.ML ·2026-10-06 ·Hazar Yueksel
similarity 0.56
Abstract · v2: title metadata corrected (no change to the paper). 61 pages, of which 8 pages main text. Code, data and the Lean 4 formalization are in …

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power $r\ge2$, on product distributions over a scaled sign cube in dimension at least linear in $n$, every proper learner with expected excess risk at most $\varepsilon$ on these distributions at the optimal sample size $n\asymp\varepsilon^{-2+2/r}$ has worst-case ld-CMI of order $n$ bits, and $Θ(n/(1+(τ/\varepsilon)^2))$ bits under Gaussian noise of standard deviation $τ$ on the loss differences. The same holds without a regularizer, at $n\asymp\varepsilon^{-2}$. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is $O(n^{-1/2})$. We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.

0.35

Outliers and the Hard-Margin Linear SVM in High-Dimension, Low-Sample-Size Settings

cs.LG stat.ML ·2026-11-10 ·Yugo Nakayama
similarity 0.55
Abstract

We study how outliers affect the hard-margin linear support vector machine when the dimension grows while the sample sizes remain fixed. For one-sided contamination, the centered Gram matrix converges to a constant inlier block plus an outlier-diagonal component, and the limiting dual problem has a closed-form solution. All outliers act through one effective distance. This representation yields explicit thresholds for loss of inlier support, margin shrinkage. intercept displacement, and asymptotic misclassification. We then treat contamination in both classes. The limiting intercept is the multiplier of the class-balance constraint, and the two classes pull it in opposite directions. Consequently, at most one class can collapse or be asymptotically misclassified, whereas symmetric contamination leaves the limiting discriminant function unchanged even though the margin shrinks. Seven numerical experiments verify the dual allocation, phase transitions, and discriminant limits.

0.19

Asymptotic Margins and Feature Confinement in Conic Classification Heads under Softmax Cross-Entropy

cs.LG eess.SP ·2026-11-13 ·Omer Nezih Gerek
code/data similarity 0.55
Abstract · 22 pages, 2 figures. Companion paper: to be uploaded. Code: https://github.com/ongerek/Conic

Classification heads built on conic functions give each class a bounded region of the feature space, and such regions are used to reject samples of unseen classes. We ask whether these regions also keep the features bounded when the head is trained with softmax cross-entropy. For a head whose class scores combine a linear term with a Euclidean norm, we first show that the region of each class is bounded by a quadric of revolution, whose eccentricity is the reciprocal of one learned ratio. We then attach to each class an asymptotic margin, which compares the growth of its score with the growth of all the other scores and can be computed by a second-order cone program. The loss of a class has infimum zero exactly when its margin is positive, and it then approaches zero only along diverging features. When the margin is negative, the loss is coercive and its minimizers lie in an explicit ball. Since softmax depends only on the differences between scores, a class with a bounded region can still have a positive margin, so bounded regions do not confine the features. The result extends to other norms, including the polyhedral conic functions. On CIFAR-10 and CIFAR-100, all 1210 cells of 67 trained conic heads have positive margins, whereas a prototype head keeps nine of its ten cells bounded, as the theory predicts.

0.55