Bounded Adversary

Follow this topic Ask about this topic

Momentum

3 papers in the last four weeks, down 25% on the four weeks before. 0.0% of all new papers.

Jul 6Week of Sep 21

Latest papers 36

Sep 21, 2026stat.ML

Adversarially Robust PAC Learning with Optimal VC Rates

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.

Steve Hanneke, Amirreza Shaeiri

Department of Computer Sciences, Purdue University, USA.

Bounded Adversary Learnability Voice Conversion

Sep 7, 2026eess.SP

Masking Radar Cognition under Adversarial Surveillance: A Distributional Privacy Framework

In this article, we propose an online electronic counter-countermeasure (ECCM) framework designed to conceal the strategic decision-making processes of a cognitive radar (CR) operating under adversarial surveillance. We model the CR under two distinct decision paradigms: a static constrained utility-maximizing behavior and a dynamic expected utility-maximizing behavior. The radar's utility function is modeled via a von Mises--Fisher (vMF) distribution, with the distributional parameter constituting the private information to be protected from adversarial inference. We adopt a distribution privacy framework to conceal this private information and provide formal distribution privacy guarantees for cognition masking. In this work, we develop cognition-hiding algorithms for both static constrained utility maximization (WDPCH-SU), and dynamic expected utility maximization (WDPCH-DU). Through rigorous mathematical analysis, we show that both WDPCH-SU and WDPCH-DU satisfy

ε

-distribution privacy (

ε

-DistP) against inference-based adversarial attacks and present the privacy--performance trade-off bounds, quantifying utility loss (in static setting) and expected utility deviation (in dynamic setting) as functions of

ε

. Numerical results show that WDPCH-SU gives about 15% improvement in utility loss at maximum privacy compared to the existing methodology while WDPCH-DU achieves a greater reduction in adversarial Fisher information without requiring explicit Fisher information constraints, at a moderate, analytically bounded utility deviation. These results are highly promising in many 6G communication scenarios such as network slicing for automated driving and swarm UAV coordination, where it is essential to keep the resource allocation policy robust against privacy attacks.

Sreedevi K, Nandhini K, Anup Aprem +1

Department of Electronics and Communication Engineering National Institute of Technology Calicut, India · Department of Electrical Engineering Indian Institute of Technology Madras, Chennai, India

Radar Bounded Adversary Utility Maximization Fisher Information Matrix Video Surveillance

Sep 1, 2026eess.SP

Real-Time Neuromorphic Spectrum Intelligence Simulator

We present the Real-Time Neuromorphic Spectrum Intelligence Simulator (RT-NuSIS), a modular framework to study spiking neural network (SNN) and memristor-inspired agents for dynamic spectrum access under constrained energy budgets and adversarial conditions. RT-NuSIS couples leaky integrate-and-fire neuronal dynamics, memristive synaptic models, physics-informed energy-harvesting models (triboelectric and RF), and adversary models including jamming and Byzantine behavior. We formalize the simulator mathematically, prove boundedness, present a mean-field adversary threshold, analyze per-step complexity, and provide a reproducible benchmark harness for energy-per-inference, latency, and robustness metrics. The codebase is modular, deterministic by seed, and designed for large-scale event-driven simulations.

Navaneetha Krishnan Kamalakannan

SIMATS Engineering Saveetha University

Neuromorphic Computing Reram Crossbar Real-Time Systems Bounded Adversary

Aug 12, 2026cs.LG

An Efficient Near-Optimal Algorithm for Adversarial $m$ -Set Bandits

We study adversarial combinatorial bandits with

m

-set actions, where at each round the learner selects

m

out of

d

items and observes only the aggregate loss of the selected items. The resulting action set contains

K=\binom{d}{m}

elements and can therefore be exponentially large. Nevertheless, the loss of every action is determined by the same

d

-dimensional vector of item losses. We propose a computationally efficient algorithm that exploits this structure without explicitly enumerating the action set. Against adaptive non-anticipating adversaries, it guarantees, with probability at least

1-δ

, regret against the best fixed action of

R_T = O\left(\sqrt{dT\log(K/δ)}\right).

This matches the high-probability regret bound of the finite-action EXP3-KW algorithm of Zimmert and Lattimore, whose direct implementation may require exponential space. Our algorithm instead represents each sampling distribution with

d

parameters and runs in polynomial time without enumerating the action set. Thus, it resolves the open problem posed by Maiti et al.

Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni

DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Multi-Armed Bandits Bounded Adversary Adversarial Robustness

Aug 6, 2026cs.LG

Bypassing Krum: Selection-Aware Backdoor Attacks in Federated Learning

Robust aggregation methods are widely used in federated learning to mitigate the impact of adversarial client behavior. Distance-based aggregation rules, such as Krum and Multi-Krum, select updates that are closest to the majority under the assumption that benign updates form a compact cluster. However, these methods rely on geometric properties that can be exploited by adaptive adversaries. We introduce the Krum-Proxy attack, a selection-aware backdoor injection strategy that consistently bypasses Byzantine-robust aggregation. Rather than relying on naive scaling or constraining, our method actively optimizes malicious updates to infiltrate the dense core of the benign distribution. The proposed method constructs adversarial updates that are not only similar to benign updates but are also optimized to lie in regions of the update space that are favored during aggregation. This is achieved through a two-stage optimization procedure that separates task-specific attack objectives from geometry-aware refinement, using a nearest-neighbor proxy, stochastic reference modeling, and anchor-guided alignment. To maintain stealth, we introduce a projection mechanism that constrains adversarial updates within realistic norm and variance bounds. Experiments on standard federated learning benchmarks show that Krum-Proxy achieves higher attack success while preserving clean accuracy, highlighting the vulnerability of distance-based aggregation to selection-aware adversaries.

Srinivasan Subramanian, Md. Abdullah Al Hafiz Khan, Kazi Aminul Islam

Department of Computer Science Kennesaw State University Marietta, USA

Federated Learning Bounded Adversary Adversarial Training

Aug 6, 2026cs.LG

Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attacks

We study online cooperative control of a multi-agent system under Byzantine attacks. Namely, an unknown, fixed subset of agents are Byzantine comprised and can stealthily overwrite its own coordinates of the team's planned joint action after observing that plan. The learner observes planned actions, public rewards, and public states, but neither the overwrite nor the executed joint action. Our objective is security: to optimize the team performance against the worst overwrites and achieve the optimal security value. We first show that the attacker's information determines the geometry. An attacker that observes the planned action induces an exact

(s,a)

-rectangular robust Markov decision process (MDP) whose rows are convex hulls of overwrite-induced public-outcome laws, whereas a blind attacker induces an

s

-rectangular model. We then identify the information-theoretic limit of security learning, showing that the security regret decomposes exactly into return regret against the response generating the data and a cumulative response gap

D_K

. Two indistinguishable horizon-one instances force

Ω(K)

expected security regret while return regret is zero, showing that dependence on

D_K

is unavoidable. Finally, we develop a stage-tied robust estimation-to-decisions learner and prove a regret bound of

\widetilde{\mathcal O}\!\left(H^2S\sqrt{AK}\right)+\mathbb E[D_K]

. Our studies thus provide comprehensive theoretical and algorithmic foundations of reliable multi-agent systems under Byzantine attacks.

Ximing Sun, Yue Wang

Department of Electrical and Computer Engineering University of Central Florida

Byzantine Attacks Model-Based Multi-Agent Systems Bounded Adversary Secure Aggregation Security Markov Decision Processes

Aug 6, 2026stat.ML

Optimal Rates for Learning with Monotone Adversaries

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error

O((d/n)\log(n/d))

for classes of VC dimension

d

, and that every known optimal learner can be pushed away from the

Θ(d/n)

rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension

d

and over known finite insertion budgets, the minimax expected error is

Θ(1/n)

at

d=1

and

Θ((d/n)\log(n/d))

for

d\geq 2

. The same rates hold with Littlestone dimension

d_{\mathrm L}

in place of

d

, so the clean online-to-batch rate

O(d_{\mathrm L}/n)

is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.

Anay Mehrotra

Stanford University

Optimal Sample Complexity Empirical Risk Minimization Optimal Learner Bounded Adversary Voice Conversion

Jul 27, 2026cs.LG

Generative Distributionally Robust Optimization

Generative models are increasingly adopted in distributionally robust optimization (DRO), but existing approaches trade off model compatibility and adversarial structure: methods that accept arbitrary samplers do not restrict worst-case laws to a generator family, while generator-parameterized adversaries rely on model-specific access such as likelihoods, scores, or training data. We propose Generative Distributionally Robust Optimization (GDRO), a principled framework that accepts any sampleable conditional generator as the nominal model and restricts worst-case laws to a chosen conditional generator family. The key is the sampler-Sinkhorn pairing: samplers represent the conditional laws exactly, while Sinkhorn divergence compares their induced distributions without likelihood access and can be estimated from samples alone. The resulting population problem admits a direct finite-sample approximation and differentiable primal-dual implementation at the active decision context. For Lipschitz losses, the population Sinkhorn radius bounds downstream degradation. Across explicit and implicit generators, our method reduces rare-context inventory regret by 60% and SocialGAN navigation collisions by 50% relative to nominal decisions.

Ziwei Zhang, Jonathan Yu-Meng Li, Zhihao Jin

1Telfer School of Management, University of Ottawa · Department of Electrical and Computer Engineering, Western University

Distributionally-Robust Optimization Robust Optimization Distributions Generative Models Primal-Dual Methods Bounded Adversary+1

Jul 21, 2026cs.RO

Stochastic Multi-Objective Kinodynamic Planning Against Adversaries

This paper addresses multi-objective kinodynamic planning in environments with stochastic hybrid adversaries that probabilistically transition to adversarial modes based on the ego state. The goal is to construct the Pareto-front of paths that trade off execution cost and the probability of safety constraint violation (risk). Existing chance-constrained planners evaluate risk over open-loop trajectories, yielding overly conservative solutions that fail to account for ego-agent reactivity. To address this limitation, we shift the planning space to sequences of closed-loop policies, and integrate sample-based risk evaluation directly into tree construction via Monte-Carlo particle rollouts. We first introduce Stochastic Multi-Objective RRT (SMO-RRT), for which we prove probabilistic completeness, followed by Stochastic Multi-Objective Stable Sparse RRT (SMO-SST), which leverages selective pruning to improve numerical performance at the cost of completeness. For both algorithms, we derive a finite-sample bound on the probability of chance constraint violation for systems with non-Gaussian, state-dependent uncertainty, enabling probabilistically safe planning in a broad class of environments applicable to multi-agent systems, social navigation, and autonomous driving.

Thomas Marshall Vielmetti, Daniel Cherenson, Dimitra Panagou

Geometric Planning Planning Stochastic Bounded Adversary Reactive Adversarial Robustness

Jul 13, 2026cs.LG

Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

We study the problem of efficient online proportional sampling from a high-dimensional domain under a

σ

-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as

O(t^d)

by round

t

in

d

dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a

σ

-smoothed adaptive adversary, we prove a tight

O(\sqrt{σT})

bound on the depth of our data structure, and an

O(\log T)

bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.

Amirmahdi Mirfakhar, Maria-Florina Balcan, Hedyeh Beyhaghi

University of Massachusetts Amherst · Carnegie Mellon University

Learning-Augmented Algorithms Bounded Adversary Adaptive Sampling High-Dimensional Reward Functions

Jul 10, 2026cs.GT

Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

Adversarial team games (ATGs) with asymmetric information, such as adversarial path-finding, goal search, and reachability games on graphs, require strategies that are robust to hidden opponent types, such as a hidden goal flag, and to deception. Under asymmetric information, deception is seen as strategic shifts in the type distribution such that the omniscient opponent can collude with Nature and condition its play on the observed type. Existing risk-neutral solution concepts, such as Bayesian Nash equilibrium (BNE), are sensitive to distribution shifts, while distributionally robust approaches provide guarantees only within a prescribed ambiguity set. To address these limitations, we introduce Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), a novel equilibrium concept that combines the distribution-free robustness of minimax-regret reasoning with probabilistic information from a nominal type distribution. PR-MRE minimizes worst-case regret over a high-confidence subset of the type space, providing protection against strategic redistribution of probability mass while avoiding the conservatism of fully distribution-free approaches. We show that, for normal-form Bayesian games, PR-MRE can be formulated as a robust bilinear program and derive a tractable semidefinite relaxation. We then adapt this relaxation into a novel meta-solver within a robust double-oracle framework, PRMRE-PSRO, enabling population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses. Experiments on graph-structured adversarial team games demonstrate that PR-MRE discovers strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibrium solutions, resulting in more robust behavior under strategic distribution shifts.

Naman Aggarwal, Jonathan P. How

Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology

Nash Equilibrium Bounded Adversary Minimax Information Asymmetry Adversarial Robustness

Jul 7, 2026cs.CR

The Power of Backdoor Absorption in Community Training

Backdoor attacks severely threaten large-scale AI models. When model owners delegate training to external compute providers within a decentralized training paradigm, adversaries can craft stealthy, low-frequency triggers to inject malicious behavior while evading standard audits. Traditionally, detecting these attacks requires a full re-computation of the training steps--a prohibitive overhead that directly contradicts the owner's resource constraints. To address this, we investigate the resilience of continuous optimization dynamics under Byzantine perturbations, where adversaries are forced to compete against a continuous influx of honest updates. Under a threat model where an adversary compromises f out of n total trainers, we quantify the minimum auditing overhead required by the model owner to probabilistically bound the attack success rate. We formalize this injection-absorption dynamic as a Discrete-Time Markov Chain (DTMC). Using this framework, we prove that the success probability of any bounded adversary asymptotically collapses to zero under a defense strategy combining natural absorption, a randomized scheduler, and lazy verification oracle. Empirical results demonstrate significant backdoor suppression with zero utility degradation even when invoking the verification oracle on merely 10% of the total training steps. This approach yields a provably sound and computationally efficient defense for safety-critical AI.

Issam Seddik, Sami Souihi, Mohamed Tamaazousti +1

Université Paris-Saclay, CEA LIST, Palaiseau, France

Clean Label Backdoor Attack Model-Agnostic Defense Bounded Adversary Attack-Success Rate Decentralized Learning

Jul 6, 2026cs.CV

Statistical Adversaries: Natural Backdoor-like Features in Vision Datasets

Model-specific adversarial attacks have been extensively studied. We study a different failure mode: naturally occurring statistical signals in vision data that can behave like backdoor-like triggers without being maliciously inserted. We call these signals statistical adversaries. We analyse Imagenet to find patterns that are strongly linked to certain labels. We then use statistical controls to remove random correlations from our candidate signals. Finally, we demonstrate that these signals directly and predictably alter model predictions. These statistical adversaries are more targeted than generic corruptions and transfer across different model architectures. This suggests that some vulnerabilities are driven by dataset structure and distribution rather than a single model's idiosyncrasies. We conclude that ordinary datasets can contain exploitable adversarial surfaces even in the absence of poisoning, and suggest that dataset audits should treat spurious structure not only as a source of bias or interpretability failure, but also as a latent attack surface for vision models.

Paul K. Mandal, Pavan Reddy, Tristan Malatynski

1Neurint, LLC, Baton Rouge, LA, USA. · 2U.S. Army Cyber Corps, U.S. Army Reserve, USA. · 3Northwestern State University of Louisiana, Natchitoches, LA, USA. +2

Black-Box Adversarial Attacks Vision Datasets Bounded Adversary Imagenet

Jul 6, 2026cs.LG

Active Learning on Adversarially Corrupted Graphs

Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph

G^*

. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and

G^*

, and its power is then measured by the size of the \emph{neighborhood} of the corrupted vertices in

G^*

. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the \emph{vertex expansion} of

G^*

, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.

Marco Bressan, Nicolò Cesa-Bianchi, Tommaso d`Orsi +2

Università degli Studi di Milano, Italy · Bocconi University, Italy · Google Research

Bounded Adversary Active Learning Corrupted Inputs

Jun 30, 2026cs.AI

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics for a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training distribution into the LLM-based evolutionary search loop. RAISE treats robust AHD as a constrained adversarial instance search problem: the outer loop evolves heuristics via LLM operators, while an LLM-free inner loop efficiently identifies hard instances within an epsilon-ball around the training instance set using a basis distribution parameterization with boundary projection. Comprehensive experiments on Online Bin Packing (OBP), Online Job Shop Scheduling (OJSP), and Online Vehicle Routing (OVRP) across five distribution families demonstrate that existing LLM-based AHD methods degrade by up to 19 times under distribution shift, while RAISE consistently maintains strong performance across all tested distributions and problem scales

Fei Liu, Alessio Figalli, Patrick Owen +1

University of Zurich · 2ETH Zurich

Automated Heuristic Design Bounded Adversary Evolutionary Search Vehicle Routing Problem

Jun 18, 2026cs.LG

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and

β

-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and

β

-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with

β

-smooth losses.

Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto

Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan

Convex Loss Convex Optimization Nonconvex Bounded Adversary Regret

Jun 9, 2026cs.LG

Signed Compression Progress on a Sealed Audit is Goodhart-Resistant

Compression progress is a long-standing proposal for intrinsic motivation: reward an agent when its world model becomes better at predicting or compressing experience. The folk claim is that this reward is "credible" because it is paid only for learning. We make this precise and prove it. If intrinsic reward is the signed decrease of a fixed sealed-audit loss, r_t = E(theta_{t-1}) - E(theta_t), then cumulative reward telescopes exactly to endpoint audit improvement, so no policy can push reward up indefinitely while true audit performance stagnates or degrades. For finite audit panels the same result holds with a sharp false-positive budget: cumulative empirical reward is at most true audit improvement plus 2 Delta_n(F, delta), the uniform audit deviation of the model class. This is horizon-free: adaptivity over time costs nothing once the sealed panel uniformly controls the class. The theorem also identifies the failure modes: the guarantee disappears if progress is clipped, scored on the agent's own stream, exposed to a high-capacity model on a reusable panel, or applied to a neural class that makes Delta_n vacuous. We give a Lean 4 mechanization of the structural core (telescoping, the finite-audit bound, finite Gibbs, and the entropy floor) and an experiment suite on ARC-TGI grid-transformation generators with adaptive holdout attacks. Experiments confirm the theory: finite-audit deviation scales as n^{-0.527}; signed progress resists clip-farming, stream leakage, and noisy-TV curiosity; naive reusable audits are exploitable by black-box scalar feedback, while standard release defenses keep the attack below the 2 Delta_n threshold. Signed compression progress on a sealed audit is an accounting signal of genuine improvement.

Ayush Mittal, Dhruv Gupta

Model Auditing Bounded Adversary Data Compression Methods

May 31, 2026cs.NI

SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search

Unmanned Aerial Vehicles (UAVs) equipped with radar sensors are deployed for target search missions in diverse environments, where targets exhibit characteristic signatures (e.g., respiration micro-motion in human search) detectable through occlusions. A fundamental challenge arises from shifts in radar statistics as the UAV moves through a dynamic and potentially non-stationary environment, rendering any fixed signal-processing strategy suboptimal; yet perception and adaptation must run onboard a resource-constrained aerial node in real time. Since no single detector performs well across all conditions, we adopt a multi-policy paradigm and formulate UAV target search as an online policy selection problem over a library of specialized detectors, with performance measured by regret, the cumulative loss gap relative to the best policy in each scene. The setting couples in-scene stochastic noise with inter-scene shifts. Whereas prior methods capture only one regime, we account for both through the Stochastically Extended Adversary (SEA) framework, without requiring oracle knowledge of scene dynamics. Because adaptation must run at the UAV, we instantiate SEA through \textsc{SEArch}, a lightweight optimistic Follow the Regularized Leader (OFTRL) selector with an adaptive learning rate, achieving regret

O(\barσ_T \sqrt{T} + \sqrt{J})

, where

\barσ_T

captures radar measurement noise and

J

is the number of scene transitions over the mission horizon

T

. To enable rapid adaptation under frequent scene changes, we further introduce \textsc{W-SEArch}, a windowed variant that restarts every

w

rounds and achieves regret

O(\barσ_I \sqrt{w})

under at most one transition per window. Experiments show up to 30% regret reduction compared to non-adaptive baselines across a range of non-stationary settings.

Noor Khial, Naram Mhaisen, Loay Ismail +1

College of Engineering, Qatar University, Qatar · Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands

Unmanned Aerial Vehicle Detection Unmanned Aerial Vehicles Bounded Adversary Rapid Adaptation Boltzmann Policies Resource-Constrained Edge Devices

May 23, 2026cs.CR

AI-Driven Adaptive Adversaries and the Erosion of Cryptographic Trust in Public Key Systems

This paper examines the erosion of Public Key Cryptography (PKC) security under adaptive adversarial optimisation driven by artificial intelligence. The problem addressed is the growing mismatch between algorithm-centric cryptographic security models and operational attack realities, where adversaries exploit implementation-level observability rather than breaking cryptographic primitives.

Petar Radanliev

Department of Computer Sciences, University of Oxford, Wolfson Building, Parks Rd, Oxford OX1 3QG · The Alan Turing Institute, British Library, 96 Euston Rd., London NW1 2DB

Diffie-Hellman Bounded Adversary Adversarial Training Partial Observability

May 22, 2026cs.LG

Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance of BTL estimation methods, such as spectral and maximum likelihood estimation, is well studied in the regime of uniformly sampled graphs, generalizing such results to a wider class of random graphs has proved challenging. In this work, we investigate the entry-wise error of spectral algorithms against a semi-random adversary that can arbitrarily boost the sampling probabilities of certain edges. We find that the performance of the unweighted spectral method is heavily dependent on the spectral properties of the generated graph. Furthermore, we show that asymptotic performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges to counteract the adversary and restore the spectral gap. Finally, we provide numerical simulations that support our theoretical findings.

Dongmin Lee, Anuran Makur, Japneet Singh

Department of Computer Science Purdue University West Lafayette, IN, USA · Department of Computer Science Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN, USA

Inhomogeneous Random Graphs Bounded Adversary

May 22, 2026cs.LG

Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays

We study adversarial multi-armed bandits with and without delayed feedback under a safety-aware goal: achieving minimax-optimal worst-case regret while keeping nearly constant regret relative to a designated "safe" baseline policy. Existing approaches can balance this trade-off with immediate feedback for smooth comparators, but arbitrary delays can mistime transitions between conservatism and exploration, endangering the safety guarantee. To bridge this gap, we propose Prudent-Banker, a novel algorithm that combines a delay-adapted variant of Online Mirror Descent with a modified phased-aggression mechanism. Its key technical contribution is a delay-calibrated restart threshold that rigorously accounts for the worst-case distortion induced by unobserved feedback and reliably detects comparator suboptimality. We also establish new lower bounds for safety-constrained adversarial delayed bandits, showing that the regret guarantees of Prudent-Banker are unimprovable, up to logarithmic factors, under the baseline-safety requirement. To the best of our knowledge, Prudent-Banker is the first algorithm to achieve the optimal safety--robustness trade-off: pseudo-regret

\widetilde{O}(\sqrt{T}+\sqrt{D})

together with

\widetilde{O}(1)

regret against the safe comparator, both with and without delays. Experiments across diverse delay distributions show that, unlike standard delay-robust baselines, Prudent-Banker effectively balances safety and learning.

Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison

Bandits Bounded Adversary Regret Banking

May 20, 2026cs.CV

Mind Your Margin and Boundary: Are Your Distilled Datasets Truly Robust?

Dataset distillation (DD) compresses a large training set into a small synthetic set for efficient training, but most DD methods optimize only clean accuracy and leave robustness uncontrolled. Recent robust DD methods improve robustness, yet they often suffer from a poor accuracy-robustness trade-off because they (i) treat all adversarially perturbed examples uniformly, despite robust risk being dominated by near-zero robust margins, and (ii) do not explicitly increase inter-class separation in the decision boundary where attacks concentrate. We present Contrastive Curriculum for Robust Dataset Distillation (C

^2

R), a framework that couples an attack-aware curriculum with a contrastive robustness objective. From a robust-margin perspective, we derive a perturbation score that approximates each sample's robust hinge, enabling a curriculum that prioritizes the smallest-margin adversaries that most directly drive robust error. In parallel, a class-balanced contrastive robustness loss enforces adversarial invariance while explicitly widening boundary separation across classes. Experiments on CIFAR-10/100, Tiny-ImageNet, and multiple ImageNet-1K subsets under six attacks show that C

^2

R achieves the best robust accuracy, outperforming prior robust DD by

2.8

% on average.

Muquan Li, Yingyi Ma, Yihong Huang +5

The Laboratory of Intelligent Collaborative Computing of UESTC, Chengdu, China · Guangdong Laboratory of Artificial Intelligence and Digital Economy (SZ), Shenzhen, China · Monash University, Melbourne, Australia

Diffusion-Based Dataset Distillation Adversarial Training Cross-Dataset Benchmark Contrastive Learning Bounded Adversary Curriculum+1

May 19, 2026cs.DC

Resilient Byzantine Agreement with Predictions

This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for

n

nodes and a parameter

α\in [0, 1]

, we present algorithms that tolerate up to

α\cdot n

faulty nodes when the predictor is correct (consistency), and up to

\frac{1-α}{2} \cdot n - 1

faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to

(1-α) \cdot n - 1

. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of

n

. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.

Julien Dallot, Darya Melnyk, Tijana Milentijevic +2

TU Berlin, Germany · TU Berlin and Weizenbaum Institute, Germany · HU Berlin, Germany

Byzantine Attacks Resilience Bounded Adversary Secure Aggregation Authentication

May 12, 2026cs.GT

Profit Maximization in Bilateral Trade against a Smooth Adversary

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a

\tilde{O}(\sqrt{T})

regret bound, which is tight in the time horizon

T

up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight

\tilde{O}(\sqrt{T})

regret bound for a related mechanism design model: the joint ads problem.

Simone Di Gregorio, Paul Dütting, Federico Fusco +1

Department of Computer, Control and Management Engineering Sapienza University of Rome · Google Research · Department of Computer Science Aarhus University

Bounded Adversary Maximization Adversarial Robustness

May 11, 2026cs.LG

Nearly-Optimal Algorithm for Adversarial Kernelized Bandits

This paper studies kernelized bandits (also known as Gaussian process bandits) in an adversarial environment, where the reward functions in a known reproducing kernel Hilbert space (RKHS) may be adversarially chosen at each round. We show that the exponential-weight algorithm achieves

\tilde{O}(\sqrt{T γ_T})

adversarial regret, where

T

and

γ_T

denote the number of total rounds and the maximum information gain, respectively. For squared exponential (SE) and

ν

-Matérn kernels, we also show algorithm-independent lower bounds that guarantee the optimality of our algorithm up to polylogarithmic factors. Furthermore, we present a computationally efficient variant of our algorithm using Nyström approximation while maintaining nearly optimal regret guarantees.

Shogo Iwazaki

LY Corporation Tokyo, Japan

Bandits Bounded Adversary Reproducing Kernel Hilbert Spaces Weight Decay

May 8, 2026cs.LG

\mathsf{VISTA}: Decentralized Machine Learning in Adversary Dominated Environments

Decentralized machine learning often relies on outsourcing computations, such as gradient evaluations, to untrusted worker nodes. Existing robust aggregation methods can mitigate malicious behavior under honest-majority assumptions, but may fail when adversaries control a majority of the workers. We study this adversary-dominated setting through an incentive-oriented framework in which reports are accepted and rewarded only when they are mutually consistent up to a threshold. This turns the adversary from a pure saboteur into a rational agent that trades off increasing estimation error against the risk of rejection and loss of reward. We consider iterative optimization under this model. Unlike one-shot computation, iterative learning requires long-horizon decisions: permissive acceptance rules enable faster early progress but admit more adversarial corruption, while strict rules improve estimation accuracy but cause frequent rejections. We propose \mathsf{VISTA}, an adaptive algorithm that tunes the acceptance threshold using the optimization history. Numerical results show that \mathsf{VISTA} improves convergence over static thresholds. We also provide a rigorous convergence analysis showing that, with suitable incentive-aware adaptation, adversary-dominated decentralized learning can retain the asymptotic convergence behavior of standard SGD without relying on an honest majority.

Hanzaleh Akbari Nodehi, Parsa Moradi, Soheil Mohajer +1

University of Minnesota

Bounded Adversary Adversarial Robustness Generative Control Policies Adversarial Corruption Vista

May 8, 2026cs.GT

Differentially Private Auditing Under Strategic Response

Regulatory audits of AI systems increasingly rely on differential privacy (DP) to protect training data and model internals. We study audit design when the audited developer can strategically respond to the privacy-constrained audit interface. We formalize privacy-constrained auditing as a bilevel Stackelberg game, in which an auditor commits to a query policy and DP budget allocation across harm dimensions, and a strategic developer reallocates mitigation efforts in response. We introduce the welfare-weighted under-detection gap

B_w

, the welfare-weighted true residual harm the audit fails to detect at the developer's strategic best response, and prove that naive DP auditing (uniform or harm-proportional allocation) induces a strictly larger

B_w

than any non-strategic mitigation baseline whenever effective detectability is heterogeneous, the welfare weights are not comonotone with detectability, and the developer's optimum is interior. We characterize the optimal auditor allocation as a four-factor balance of welfare weight, audit miss-probability, detectability elasticity, and mitigation-cost curvature, and provide a single-level reformulation of the bilevel problem via the developer's KKT system. We propose Strategic Private Audit Design (SPAD), a projected-gradient algorithm with hypergradients computed through the developer's best response.

Florian A. D. Burnat

University of Bath

Model Auditing Bounded Adversary Stackelberg Equilibrium Strategic Reasoning Responses

May 5, 2026cs.LG

Distributed Learning with Adversarial Gradient Perturbations

Privacy concerns in distributed learning often lead clients to return intentionally altered gradient information. We consider the problem of learning convex and

L

-smooth functions under adversarial gradient perturbation, where a client's gradient reply to a server query can deviate arbitrarily from the true gradient subject to a distance bound. Our study focuses on two fundamental questions: (i) what is the smallest achievable sub-optimality gap (i.e., excess error in optimization) under such responses, and (ii) how many queries are sufficient to guarantee a given sub-optimality gap? We establish tight feasibility thresholds on the sub-optimality gap and provide algorithms that achieve these thresholds with provable query complexity guarantees.

Nawapon Sangsiri, Yufei Tao

CUHK

Bounded Adversary Optimality Sample Complexity Adversarial Robustness

May 1, 2026cs.LG

Metric-Normalized Posterior Leakage (mPL): Attacker-Aligned Privacy for Joint Consumption

Metric differential privacy (mDP) strengthens local differential privacy (LDP) by scaling noise to semantic distance, but many machine learning (ML) systems are consumed under joint observation, where model-agnostic, per-record guarantees can miss leakage from evidence aggregation. We introduce metric-normalized posterior leakage (mPL), an attacker-aligned, distance-calibrated measure of posterior-odds shift induced by releases, and show that for single or independent releases, uniformly bounding mPL is equivalent to mDP. Under joint observation, however, satisfying mDP may still leave mPL high because learned aggregators compound evidence across correlated items. To make control practical, we formalize probabilistically bounded mPL (PBmPL), which limits how often mPL may exceed a target budget, and we operationalize it via Adaptive mPL (AmPL), a trust-and-verify framework that perturbs, audits with a learned attacker, and adapts parameters (with optional Bayesian remapping) to balance privacy and utility. In a word-embedding case study, neural adversaries violate mPL under joint consumption despite per-record mDP perturbations, whereas AmPL substantially lowers the frequency of such violations with low utility loss, indicating PBmPL as a practical, certifiable protection for joint-consumption settings.

Gaoyi Chen, Minghao Li, Weishi Shi +4

Department of Computer Science and Engineering, University of North Texas, Denton, TX, USA · Department of Electrical Engineering, University of North Texas, Denton, TX, USA

Δ)$-Differential Privacy Standard Differential-Privacy Privacy Leakage Bounded Adversary Joint Search+1

Apr 28, 2026cs.GT

Optimally Auditing Adversarial Agents

Fraud can pose a challenge in many resource allocation domains, including social service delivery and credit provision. For example, agents may misreport private information in order to gain benefits or access to credit. To mitigate this, a principal can design strategic audits to verify claims and penalize misreporting. In this paper, we introduce a general model of audit policy design as a principal-agent game with multiple agents, where the principal commits to an audit policy, and agents collectively choose an equilibrium that minimizes the principal's utility. We examine both adaptive and non-adaptive settings, depending on whether the principal's policy can be responsive to the distribution of agent reports. Our work provides efficient algorithms for computing optimal audit policies in both settings and extends these results to a setting with limited audit budgets.

Sanmay Das, Fang-Yi Yu, Yuang Zhang

Virginia Tech · George Mason University

Model Auditing Bounded Adversary Optimal Policies Strategic Agents Step-Level Credit

Apr 20, 2026cs.LG

Perturbation Sensitivity of Maximum-Likelihood Pairwise Ranking in Computational Decision Systems

Maximum-likelihood pairwise ranking is a com- mon computational mechanism for prioritization, reputation estimation, and comparison-driven decision support. Despite its broad use, the perturbation sensitivity of this estimator under structured changes in comparison data remains insufficiently characterized. We study this question as an applied-mathematics and computational-science problem in stability analysis. We for- mulate coordinated perturbation as a budgeted subset-selection problem over pairwise observations and introduce an Adaptive Subset Selection Attack (ASSA) as a scalable search heuristic for probing high-impact perturbation sets. Through experiments on synthetic and observed preference datasets, we show that MLE-based ranking can exhibit pronounced regime-dependent sensitivity: relatively small but coordinated perturbations may in- duce meaningful changes in output orderings, while the response profile varies across budgets and data conditions. By comparing ASSA with random, greedy, and randomized subset baselines under repeated trials, we characterize both the magnitude and the variability of perturbation-induced ranking shifts. These results position pairwise ranking sensitivity as a problem in computational reliability, numerical stability, and robustness auditing for engineering systems built on comparison-driven inference.

Junyi Yao, Zihao Zheng, Jiayu Long

Washington University in St. Louis USA

Ranking Bounded Adversary Majority Voting Emotional Manipulation Membership Inference Attacks

Apr 16, 2026stat.ML

Best of both worlds: Stochastic & adversarial best-arm identification

We study bandit best-arm identification with arbitrary and potentially adversarial rewards. A simple random uniform learner obtains the optimal rate of error in the adversarial scenario. However, this type of strategy is suboptimal when the rewards are sampled stochastically. Therefore, we ask: Can we design a learner that performs optimally in both the stochastic and adversarial problems while not being aware of the nature of the rewards? First, we show that designing such a learner is impossible in general. In particular, to be robust to adversarial rewards, we can only guarantee optimal rates of error on a subset of the stochastic problems. We give a lower bound that characterizes the optimal rate in stochastic problems if the strategy is constrained to be robust to adversarial rewards. Finally, we design a simple parameter-free algorithm and show that its probability of error matches (up to log factors) the lower bound in stochastic problems, and it is also robust to adversarial ones.

Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2

Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2

Stochastic Multi-Armed Bandits Bounded Adversary Bandits Learning-Augmented Algorithms Stochastic World

Mar 4, 2026math.ST

Bayesian Adversarial Privacy

Theoretical and applied research into privacy encompasses an incredibly broad swathe of differing approaches, emphases and aims. This work introduces a novel quantitative notion of privacy that is both contextual and specific. Building on and extending ideas from statistical disclosure control and differential privacy, our aim is to model the implications of a disclosure decision in an adversarial setting. Our definition relies on concepts inherent to standard Bayesian decision theory, while departing from them in several important respects. In particular, (i) inference about the data itself becomes meaningful and (ii) the party controlling the release of sensitive information should make disclosure decisions from the prior viewpoint, rather than conditional on the data, which is a feature shared with Bayesian design. Illuminating toy examples are exploited towards highlighting the specificities of the method.

Cameron Bell, Timothy Johnston, Antoine Luciano +1

CEREMADE, Université Paris Dauphine–PSL, France · Department of Statistics, University of Warwick, UK

Privacy Disclosures Bounded Adversary Adversarial Robustness

Aug 1, 2025stat.ML

Random Walk Learning and the Pac-Man Attack

Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.

Xingran Chen, Parimal Parag, Rohit Bhagat +2

Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA · Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore, Karnataka 560012, India

Decentralized Learning Bounded Adversary Worst-Case Attack Stealthiness Malicious Agents

Oct 17, 2024cs.LG

Adaptive and oblivious statistical adversaries are equivalent

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by [BLMT22] and further explored in [CHL+23]. Specifically, consider any algorithm

A

that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm

A'

that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of

A'

is simple and maintains the computational efficiency of

A

: It requests a polynomially larger sample than

A

uses and then runs

A

on a uniformly random subsample.

Guy Blanc, Gregory Valiant

Stanford

Bounded Adversary Optimal Sample Complexity Statistical Inference Adversarial Corruption Adaptive Sampling Indistinguishability+1

Oct 4, 2023cs.LG

Expected flow networks in stochastic environments and two-player zero-sum games

Generative flow networks (GFlowNets) are sequential sampling models trained to match a given distribution. GFlowNets have been successfully applied to various structured object generation tasks, sampling a diverse set of high-reward objects quickly. We propose expected flow networks (EFlowNets), which extend GFlowNets to stochastic environments. We show that EFlowNets outperform other GFlowNet formulations in stochastic tasks such as protein design. We then extend the concept of EFlowNets to adversarial environments, proposing adversarial flow networks (AFlowNets) for two-player zero-sum games. We show that AFlowNets learn to find above 80% of optimal moves in Connect-4 via self-play and outperform AlphaZero in tournaments.

Marco Jiralerspong, Bilun Sun, Danilo Vucetic +4

Mila – Qu´ebec AI Institute, Universit´e de Montr´eal

Generative Flow Networks Imperfect-Information Games Stochastic Self-Play Synthetic Environments Autoregressive Rollout+3