A recent line of work focused on making adversarial training computationally efficient for deep learning models.

Achieving the no-regret property for Reinforcement Learning (RL) problems in continuous state and action-space environments is one of the major open problems in the field. Existing solutions either work under very specific assumptions or achieve bounds that are vacuous in some regimes. Furthermore, many structural assumptions are known to suffer from a provably unavoidable exponential dependence on the time horizon H in the regret, which makes any possible solution unfeasible in practice. In this paper, we identify _local linearity_ as the feature that makes Markov Decision Processes (MDPs) both _learnable_ (sublinear regret) and _feasible_ (regret that is polynomial in H). We define a novel MDP representation class, namely _Locally Linearizable MDPs_, generalizing other representation classes like Linear MDPs and MDPS with low inherent Belmman error. Then, i) we introduce **Cinderella**, a no-regret algorithm for this general representation class, and ii) we show that all known learnable and feasible MDP families are representable in this class.

For models trained with multi-step AT, it has been observed that the loss function behaves locally linearly with respect to the input, this is however lost in single-step AT. To address CO in single-step AT, several methods have been proposed to enforce local linearity of the loss via regularization. Instead, in this work, we introduce a regularization term, called ELLE, to mitigate CO effectively and efficiently in classical AT evaluations, as well as some more difficult regimes, e.g., large adversarial perturbations and long training schedules. Our regularization term can be theoretically linked to curvature of the loss function and is computationally cheaper than previous methods by avoiding Double Backpropagation. Our thorough experimental validation demonstrates that our work does not suffer from CO, even in challenging settings where previous works suffer from it. We also notice that adapting our regularization parameter during training (ELLE-A) greatly improves the performance, specially in large ϵ setups. Adversarial Training (AT) (Madry et al., 2018) and TRADES (Zhang et al., 2019) have emerged as prominent training methods for training robust architectures. However, these training mechanisms involve solving an inner optimization problem per training step, often requiring an order of magnitude more time per iteration in comparison to standard training (Xu et al., 2023). To address the computational overhead per iteration, the solution of the inner maximization problem in a single step is commonly utilized. While this approach offers efficiency gains, it is also known to be unstable (Tramèr et al., 2018; Shafahi et al., 2019; Wong et al., 2020; de Jorge et al., 2022). CO is characterized by a sharp decline (even down to 0%) in multi-step test adversarial accuracy and a corresponding spike (up to 100%) in single-step train adversarial accuracy. Explicitly enforcing local linearity has been shown to allow reducing the number of steps needed to solve the inner maximization problem, while avoiding CO and gradient obfuscation (Qin et al., 2019; Andriushchenko and Flammarion, 2020). Nevertheless, all existing methods incur a 3 runtime due to Double Backpropagation (Etmann, 2019) Given this time-consuming operation to avoid CO, a natural question arises: Can we efficiently overcome catastrophic overfitting when enforcing local linearity of the loss? Partially done at Universidad Carlos III de Madrid, correspondance: elias.abadrocamora@epfl.ch We train with our method ELLE and its adaptive regularization variant ELLE-A.

Adversarial training (AT) and its variants are the most effective approaches for obtaining adversarially robust models. A unique characteristic of AT is that an inner maximization problem needs to be solved repeatedly before the model weights can be updated, which makes the training slow. FGSM AT significantly improves its efficiency but it fails when the step size grows. The SOTA GradAlign makes FGSM AT compatible with a higher step size, however, its regularization on input gradient makes it 3 to 4 times slower than FGSM AT. Our proposed NoiseAug removes the extra computation overhead by directly regularizing on the input itself. The key contribution of this work lies in an empirical finding that single-step FGSM AT is not as hard as suggested in the past line of work: noise augmentation is all you need for (FGSM) fast AT. Towards understanding the success of our NoiseAug, we perform an extensive analysis and find that mitigating Catastrophic Overfitting (CO) and Robust Overfitting (RO) need different augmentations. Instead of more samples caused by data augmentation, we identify what makes NoiseAug effective for preventing CO might lie in its improved local linearity.

Batch normalization (BN) has been widely used in modern deep neural networks (DNNs) due to fast convergence. BN is observed to increase the model accuracy while at the cost of adversarial robustness. We conjecture that the increased adversarial vulnerability is caused by BN shifting the model to rely more on non-robust features (NRFs). Our exploration finds that other normalization techniques also increase adversarial vulnerability and our conjecture is also supported by analyzing the model corruption robustness and feature transferability. With a classifier DNN defined as a feature set $F$ we propose a framework for disentangling $F$ robust usefulness into $F$ usefulness and $F$ robustness. We adopt a local linearity based metric, termed LIGS, to define and quantify $F$ robustness. Measuring the $F$ robustness with the LIGS provides direct insight on the feature robustness shift independent of usefulness. Moreover, the LIGS trend during the whole training stage sheds light on the order of learned features, i.e. from RFs (robust features) to NRFs, or vice versa. Our work analyzes how BN and other factors influence the DNN from the feature perspective. Prior works mainly adopt accuracy to evaluate their influence regarding $F$ usefulness, while we believe evaluating $F$ robustness is equally important, for which our work fills the gap.