CS Paper Radar

Probabilistic Adversarial Training

Andi Zhang, Xingyu Zhao, Siddartha Khastgir

cs.LG cs.AIstat.ML ·submitted 2026-09-30 14:12 UTC · v1
theory

Abstract

Building on a probabilistic perspective in which adversarial examples arise from the overlap between a distance-based distribution $p_{\mathrm{dis}}$ and a victim-classifier-induced distribution $p_{\mathrm{vic}}$, we start from a simple intuition: adversarial examples become harder to generate when these two distributions are pushed apart, as their overlap becomes smaller, thereby increasing robustness. This intuition naturally motivates a KL-based robustness objective. We then prove that $\mathrm{KL}(p_{\mathrm{dis}}\|p_{\mathrm{vic}})-\log Z_{\mathrm{vic}}$ is a lower bound on probabilistic robustness (PR), where $Z_{\mathrm{vic}}$ denotes the normalizing constant of $p_{\mathrm{vic}}$. Since PR is generally intractable to compute directly, maximizing this KL-based lower bound provides a tractable surrogate objective for improving PR. We further show that this objective recovers a scaled form of adversarial training, offering a probabilistic interpretation of adversarial training and a principled route to robustness improvement. We call the resulting method probabilistic adversarial training. Experiments show that it consistently improves PR, and ablation studies demonstrate that the induced scaling factor can even enhance the PR of non-probabilistic adversarial training methods.

Closest papers

Nearest neighbours by meaning across the whole index.

On the tradeoff between robustness and geometric accuracy in adversarial training

cs.LG math.AP ·2026-10-16 ·Rachel Morris, Ryan Murray, Kerrek Stinson
theory similarity 0.68
Abstract

For non-parametric binary classification in the presence of an adversary, we prove an optimal quantitative estimate for adversarial classifiers controlling geometric accuracy, as measured by the Hausdorff distance to the Bayes classifier, in terms or their robustness, as encoded by the adversarial budget $\varepsilon$. This rigorously shows that robust classifiers sacrifice at most $O(\sqrt{\varepsilon})$ or $O(\varepsilon)$ in accuracy, depending on the regularity of the underlying Bayes classifier. In contrast to prior work on the incompatibility of robustness and accuracy over low-complexity hypothesis classes, our work shows that high-complexity hypothesis classes allow for robust classifiers with precisely quantified accuracy. Our results apply for adversaries determined by any norm on Euclidean space and in both the infinite and finite data settings.

0.34

Adversarially Robust PAC Learning with Optimal VC Rates

cs.LG stat.MLmath.ST ·2026-09-21 ·Steve Hanneke, Amirreza Shaeiri
theory similarity 0.65
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

Rate-Optimal Algorithm for Adversarial Linear CMDPs

cs.LG ·2026-10-01 ·Kihyun Yu, Honghao Wei, Dabeen Lee
similarity 0.64
Abstract

We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves $\widetilde{\mathcal{O}}(K^{3/4})$ regret and cumulative constraint violation, leaving a gap to the optimal $\widetilde{\mathcal{O}}(\sqrt{K})$ dependence on the number of episodes $K$. We close this gap by proposing a new primal dual algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret and cumulative constraint violation without assuming Slater's condition. We further extend the algorithm to achieve the same $\widetilde{\mathcal{O}}(\sqrt{K})$ guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.

0.18

KAN-Robust-Bench: A Benchmark for Evaluating the Robustness of Kolmogorov-Arnold Networks

cs.LG cs.AI ·2026-08-21 ·Mohammad Meymani, Roozbeh Razavi-Far
benchmark similarity 0.63
Abstract

While machine learning models have demonstrated strong performance in many domains, these models have shown profound vulnerabilities when they are exposed to adversarial threats. While adversarial attacks fall into various categories, the most prominent category in research studies is evasion. In evasion attacks, the adversary generates perturbed versions of samples, which might not be observable by human eyes. These samples generally fool the machine learning models with high confidence. This phenomenon poses a significant security violation against machine learning models. In this paper, we investigate the certified and empirical robustness of various Kolmogorov-Arnold network architectures against strong evasion attacks. At first, we provide the mathematical foundations for randomized smoothing and interval bound propagation, and report the $\ell_2$-certified robustness of the models under randomized smoothing. After that, we systematically evaluate the robustness of various defended and undefended KAN models under FGSM, PGD, and C&W attacks in order to find out the optimal defense strategies and architectures.

0.23

Sequential Probability Assignment against Smoothed Adversaries with Unknown Base Measure

cs.LG stat.ML ·2026-11-19 ·Ziyi Liu, Daniel M. Roy
publishedtheory similarity 0.63
Abstract · NeurIPS 2026

Smoothed online learning has recently been studied as a way to bypass hardness results for the fully adversarial setting, which can be overly pessimistic. In this framework, the adversary is constrained to generate contexts from distributions having a bounded density with respect to some fixed base measure $μ$. Prior work makes the strong assumption that $μ$ is known to the learner, with notable exceptions including Block et al. (2024) and Blanchard (2025). In this paper, we study sequential probability assignment (a.k.a., online learning with log loss) with smooth, well-specified data in the more general setting where $μ$ is \emph{unknown}, without the Lipschitz condition imposed in the work of Block et al. (2024) and Blanchard (2025). We prove regret upper bounds against both adaptive and oblivious smoothed adversaries: the adaptive bound is controlled by empirical $\ell_\infty$ Hellinger entropy, while the oblivious bound improves this dependence to empirical $\ell_2$ Hellinger entropy, the notion that has been shown to characterize the complexity of learning with i.i.d. data (Bilodeau et al., 2023). Both bounds are obtained through algorithms based on truncated empirical Hellinger covers. We complement these results with a general lower bound, showing that our upper bounds are essentially tight for some natural classes, which implies a separation in the difficulty of smoothed online learning between regimes where $μ$ is known and where it is unknown.

0.15

Certifying Lower Bounds for Risk-Sensitive Reinforcement Learning under Adversarial State Perturbations

cs.LG math.OC ·2026-09-09 ·Tong Li, Saunak Kumar Panda, Yisha Xiang
theory similarity 0.62
Abstract · 26 pages, 3 figures

Reinforcement learning (RL) agents deployed in real-world environments are often vulnerable to adversarial perturbations in state observations, creating risks in safety-critical applications. Certification methods can improve robustness against adversarial perturbations by providing lower bounds on expected cumulative rewards. Existing certification methods, however, mainly focus on risk-neutral objectives. In this paper, we extend certification methods to risk-sensitive objectives by establishing lower bounds on the exponential utility of cumulative rewards under $l_{p}$-norm-bounded state adversarial perturbations ($1\leq p <\infty$). By introducing a $φ$-divergence relaxation of the perturbation set, we formulate the risk-sensitive certification problem as a convex optimization and derive its dual to obtain a tractable approximation of the certified lower bound. We further propose an empirical method that improves certified lower bounds by selecting the training risk-aversion parameter $β$ independently of the risk level used during evaluation. Experiments on both OpenAI Gym environments and a machine replacement problem show that, compared to risk-neutral training, risk-averse training generally yields policies with higher certified lower bounds, particularly under larger perturbation budgets. Moreover, under both risk-neutral and risk-averse evaluation settings, increasing risk aversion during training leads to non-monotonic certification performance, where certified lower bounds initially improve but eventually decrease due to overly conservative policies.

0.28

Adversarial Risk in the Generative AI Era Necessitates Dropping the Small Epsilon Ball

cs.LG cs.CR ·2026-11-10 ·Andrew C. Cullen, Neil G. Marchant, Paul Montague, Jiani Xie, Benjamin I. P. Rubinstein
position similarity 0.62
Abstract · neurips 2026, 10 pages, position paper on adversarial risk, certified robustness

Adversarial Machine Learning research is currently centered on the search for the epsilon-ball: minimal perturbations designed to fool models while remaining imperceptible to humans. We argue that this fixation on $\ell_p$ norms is a metrological trap that communicates a distorted perception of risk to defenders, one that is unaligned with real-world system vulnerabilities. This paradigm misleads defenders into optimizing for narrow, mathematical robustness at the expense of systemic security, while simultaneously incentivizing attackers to exploit non-overlapping alternative adversarial pathways. Ultimately, we argue that the dominance of the $\ell_p$ ball does not just fail to reduce harm---it may actively facilitate it by communicating a false sense of security against the wrong threats.

0.22

Structured Confidence Perturbation via Fisher Geometry for Adversarial Training

cs.LG cs.CV ·2026-11-10 ·Chenlong Wei, Hanling Wang, Chong Zhang, Qinkai Yu, Fangyu Wu +1 more
similarity 0.62
Abstract · 20 pages, 4 figures

Adversarial training is often plagued by "pseudo-attacks", perturbations that significantly increase the loss value but fail to truly alter the model's confidence structure. To address this, we propose two complementary approaches to directly attack and defend against confidence structure deformation. First, building upon the traditional loss maximization perspective, we introduce a hybrid objective that integrates cross-entropy and KL divergence, encouraging adversarial examples to simultaneously disrupt prediction accuracy and distribution consistency. Second, we geometrically reconstruct adversarial training by generating perturbations that maximize the distribution distance on the confidence manifold. Theoretical analysis shows that the optimal perturbation direction aligns with the principal eigenvectors of the Fisher information matrix. We also propose an efficient algorithm to avoid high-dimensional matrix computations. Experiments on multiple datasets and model architectures demonstrate that our method outperforms existing methods in adversarial robustness and robust transferability, particularly excelling in structural perturbations within high-confidence regions.

0.34