ICML 2026 Papers

We show how an adversarial model trainer can plant backdoors in a large class of deep, feedforward neural networks. These backdoors are statistically undetectable in the white-box setting, meaning that the backdoored and honestly trained models are close in total variation distance, even given the full descriptions of the models (e.g., all of the weights). The backdoor provides access to invariance-based adversarial examples for every input, mapping distant inputs to unusually close outputs. However, without the backdoor, it is provably impossible (under standard cryptographic assumptions) to generate any such adversarial examples in polynomial time. Our theoretical and preliminary empirical findings demonstrate a fundamental power asymmetry between model trainers and model users.

Decision-based image attacks commonly rely on zeroth-order (ZO) Monte Carlo probing to estimate decision-boundary normals and iteratively refine adversarial perturbations to minimize the $\ell_2$ norm. We theoretically analyze and empirically demonstrate an intrinsic inefficiency arising from heterogeneous input sensitivity, where only a small subset of coordinates strongly affects the target model’s predictions. Empirically, with one-bit feedback and a limited query budget, updates on low-sensitivity coordinates are overwhelmed by initialization and sampling noise, preventing their perturbations from exhibiting consistent improvement. By modeling ZO refinement as a stochastic dynamical system, we formally characterize its asymptotic behavior: the optimization enters a stationary regime, where the perturbation aligns (in expectation) with the normal and its coordinate-wise magnitudes encode a local sensitivity ranking. However, this stationarity does not generally yield $\ell_2$-optimal perturbations under nonlinear boundaries. Building on this observation, we propose a novel and effective algorithm, Sensitivity-Aware Rescaling (SAR), that leverages this sensitivity signal to infer an importance map from the current best perturbation, then progressively suppresses low-importance regions through a coarse-to-fine schedule to reduce the $\ell_2$ norm. Extensive experiments show that SAR achieves consistent improvements in perturbation norm, attack success rate, and visual imperceptibility. The code is available at https://github.com/Flyingssheep/SAR.

Adversarial imitation learning (AIL) achieves high-quality imitation compared to behavioral cloning (BC), but demands substantial online environment interaction. Recent empirical work has explored initializing AIL algorithms with BC-pretrained policies to address this limitation, yet a rigorous theoretical understanding of pretraining's role in AIL remains elusive. This paper provides a systematic theoretical analysis and introduces principled pretraining algorithms for accelerating AIL. We begin by analyzing AIL with policy pretraining alone, identifying reward error as the dominant source of suboptimality. This reveals a critical and previously overlooked gap: the absence of reward pretraining. Motivated by this finding, we develop a principled policy–reward co-pretraining approach grounded in a reward-shaping analysis. Our analysis uncovers a fundamental connection between expert policies and shaping rewards, which naturally gives rise to CoPT-AIL, an approach that jointly pretrains both policy and reward through a single BC procedure. We prove that CoPT-AIL achieves an improved imitation gap bound over standard AIL, establishing the first theoretical guarantee for the benefits of pretraining in AIL. Experimental results confirm CoPT-AIL's superior performance over existing AIL methods.

We introduce Hybrid Space-aware Stochastic Convolution Attention Noise (HySCAN), a hybrid randomized defense that helps close the long-standing gap between provable robustness under ℓ2 certificates and empirical robustness against strong ℓ∞ attacks, while maintaining strong generalization across diverse imaging benchmarks. HySCAN jointly explores complementary sources of stochasticity at both training and inference: (i) implicit weight-space randomness via stochastic-aware Random Weights, and (ii) explicit feature-space randomness via Stochastic Attention Noise Injection modules. By incorporating randomness at both the parameter and representation levels, HySCAN enables meaningful certified guarantees while improving empirical robustness in practice. Comprehensive experiments on diverse imaging datasets, e.g., CelebA, CIFAR-10, and CIFAR-100, ImageNet-1k, HAM10000, and NIH Chest X-ray, demonstrate that HySCAN outperforms existing certified and empirical defenses, improving certified robustness by up to ≈ 9.6% and empirical robustness by up to ≈ 5% without reducing clean accuracy.

Reinforcement learning (RL) fine-tuning has become a key technique for enhancing large language models (LLMs) on reasoning-intensive tasks, motivating its extension to vision language models (VLMs). While RL-tuned VLMs improve on visual reasoning benchmarks, they remain vulnerable to weak visual grounding, hallucinations, and over-reliance on textual cues. We show that simple, controlled textual perturbations—misleading captions or incorrect chain-of-thought (CoT) traces—cause substantial drops in robustness, and that these effects are more pronounced when CoT consistency is taken into account across open-source multimodal reasoning models. In contrast, closed models exhibit similar failure modes but maintain markedly greater robustness and reasoning consistency, suggesting that the gap reflects a shortcoming in current RL fine-tuning methods rather than an inherent limitation of the task. To better understand these vulnerabilities, we further analyze RL fine-tuning dynamics and uncover an accuracy–faithfulness trade-off: fine-tuning raises benchmark accuracy, but can simultaneously erode the reliability of the accompanying CoT and its robustness to contextual shifts. Although adversarial augmentation improves robustness, it does not by itself prevent faithfulness drift. Incorporating a faithfulness-aware reward can restore alignment between answers and reasoning, but when paired with augmentation, training risks collapsing onto shortcut strategies. Together, these findings highlight the limitations of accuracy-only evaluations and motivate training and assessment protocols that jointly emphasize correctness, robustness, and consistency in visually grounded reasoning.

Recent studies show that Hypergraph Neural Networks (HGNNs) are vulnerable to adversarial attacks, while adversarial learning in the context of hypergraphs remains substantially under-investigated. In particular, all existing attacks on HGNNs are white-box and customized for either structural or feature perturbation. But in reality, the attacker might not have access to the target model parameters. Motivated by this knowledge gap, we propose a generic meta-objective-based learning framework, MeLA, that leverages the hypergraph Laplacian to conduct gray-box, structural, and feature perturbations under explicit perturbation budgets. In contrast to the attack literature, there is no adversarial training mechanism for HGNNs to defend against such attacks. Hence, we propose a novel adversarial training mechanism for HGNNs to obtain a robust classifier. We further prove the convergence of our robust training. Extensive experiments across various HGNN models and datasets show that (a) our proposed attack is effective in poisoning and evasion settings, and (b) our adversarial training enhances defense against adversarial attacks.

The work presents an approach for addressing the challenge of robustness in Large Language Models (LLMs) to alterations and potential errors caused by semantically similar but textually different prompts. Recent works have shown that these kinds of prompt variations can significantly impact the performance of LLMs on tasks. The central question is: can LLMs' robustness to semantically-neutral prompt alterations be acquired without expensive retraining of the entire model? We address this question both theoretically and through experiments. Our theoretical analysis reveals a crucial factor impacting model robustness -- a systematic expected shift or perturbation-induced bias in neural network module outputs. Motivated by this analysis, we show that robustness can be achieved via a simple fine-tuning process: debiasing for robustness. We identify conditions when debiasing helps and when it does not, and demonstrate, through both theory and extensive experiments, that debiasing for robustness may indeed be a quick and efficient tool to enhance robustness and provide certification against random prompt perturbations.

We study algorithms in the resettable streaming model, where the value of each key can either be increased or reset to zero. This model is suitable for applications such as active resource monitoring with support for deletions and machine unlearning. We show that all existing sketches for this model are vulnerable to adaptive adversarial attacks that apply even when the sketch size is polynomial in the length of the stream. To overcome these vulnerabilities, we present the first adaptively robust sketches for resettable streams that require only polylogarithmic space complexity in the stream length. Our framework supports (sub) linear statistics including $L_p$ moments for $p\in[0,1]$ (in particular, Cardinality and Sum) and Bernstein statistics. We bypass strong impossibility results known for linear and composable sketches by designing dedicated single-stream sketches robustified via Differential Privacy. Unlike standard robustification techniques, which provide limited benefits in this setting and still require polynomial space in the stream length, we leverage the Binary Tree Mechanism for continual observation to protect the sketch's internal randomness. This enables accurate prefix-max error guarantees with polylogarithmic space.

We study the Awakening Crowd of Experts (ACE) problem, an online learning problem where the set of experts available to the learner grows at each round. ACE is a special case of the well-known sleeping experts problem (Kleinberg et al., 2010), where the number of experts is huge $(K=T)$. Existing results on sleeping experts preclude any learner from achieving a sublinear regret when the number of available experts is linear in $T$. Inspired by real-world applications, such as Q\&A platforms and social proof marketing, we thus focus on the awakening version of the sleeping experts problem, where a new expert arrives at every round and never leaves. We show that in the stochastic version of ACE, it is possible to obtain regret $\tilde{\mathcal{O}}(T^{2/3})$ using an unusual pessimism in the face of the uncertainty principle. Moreover, we characterize the dependence of the regret on the stability of an optimal strategy. For both results, we present matching lower bounds. Surprisingly, the adversarial version of ACE is sensibly harder. In particular, we provide a lower bound precluding sublinear $\alpha$-regret when the competitive ratio is constant. We provide an algorithm to face this crucial trade-off between competitive ratio and regret, and bound its $\alpha$-regret, almost matching the aforementioned lower bound. As a corollary, we get a $\tilde{\mathcal{O}}(\log(\log(T))$ competitive ratio when an optimal strategy enjoys a reward linear in $T$.

Multi-objective reinforcement learning (MORL) must often support preferences that change online or are specified only after data collection. We study finite-horizon MORL with vector feedback in linear MDPs under two protocols: (i) predictable adversarial preferences revealed before each episode, and (ii) reward-free preference-free exploration (PFE), where exploration observes only transitions and must later answer arbitrary preference queries. Standard reductions are protocol-unsafe: re-scalarizing past stochastic rewards with future weights breaks the martingale structure needed for self-normalized confidence bounds, and hypervolume evaluation must account for episode-start randomization, which yields a deployable convex hull of return vectors. We propose a protocol-safe reward interface that estimates each reward coordinate via regression and performs scalarization only at query time, and we formalize deployable hypervolume semantics with a stability chain from support-function error to hypervolume error. Consequently, we obtain filtration-safe regret bounds for any predictable preference sequence without discretizing the simplex (only $\log m$ dependence) and matching near-minimax rates in linear MDPs, as well as sharp reward-free PFE guarantees: a (near-)minimax decision-optimal query answering rate $\tilde{O}(d^2 U_{\mathrm{ret}}^2/\varepsilon^2)$ and a tight separation from explicit transition-model recovery $\Theta(d(|\mathcal{S}|-1)/\varepsilon_P^2)$. These results connect online learning, preference-free deployment, and hypervolume-aware evaluation through a single protocol-aligned theory.

Full-Reference image quality assessment (FR IQA) is important for image compression, restoration and generative modeling, yet current neural metrics remain slow and vulnerable to adversarial perturbations. We present BiRQA, a compact FR IQA metric model that processes four fast complementary features within a bidirectional multiscale pyramid. A bottom-up attention module injects fine-scale cues into coarse levels through an uncertainty-aware gate, while a top-down cross-gating block routes semantic context back to high resolution. To enhance robustness, we introduce Anchored Adversarial Training, a theoretically grounded strategy that uses clean "anchor" samples and a ranking loss to bound pointwise prediction error under attacks. On five public FR IQA benchmarks BiRQA outperforms or matches the previous state of the art (SOTA) while running $\sim 3 \times$ faster than previous SOTA models. Under unseen white-box attacks it lifts SROCC from 0.30-0.57 to 0.60-0.84 on KADID-10k, demonstrating substantial robustness gains. To our knowledge, BiRQA is the only FR IQA model combining competitive accuracy with real-time throughput and strong adversarial resilience.

With the widespread application of Video Diffusion Models (VDMs), video synthesis has achieved remarkable temporal dynamics. Image-to-Video (I2V) generation allows users to provide reference images, which enables attackers to inject adversarial noise into these conditions. Due to the robust spatio-temporal priors in VDMs, conventional frame-level attacks merely induce superficial artifacts and struggle to suppress the synthesis of motion semantics. In this work, we approach the problem by exploring the underlying mechanism of temporal dynamics. We reveal that the static video manifests as a temporal rank collapse, a degenerate state characterized by rank-1 degeneracy within the temporal attention matrix. Guided by this insight, we propose Motion Elimination in Diffusion Using Spectral Attack (MEDUSA) to freeze the video. It minimizes the nuclear norm of the attention matrix to induce the temporal rank collapse. This objective circumvents the vanishing gradient problem encountered when directly imposing a rigid temporal mapping on the attention matrix. Furthermore, we provide a mathematical analysis of this phenomenon and the gradient vanishing problem during the optimization. Experiments confirm that MEDUSA achieves excellent performance and validates the effectiveness of spectral constraints.