Aleksander Madry

TMLR Journal 2025 Journal Article

Ask Your Distribution Shift if Pre-Training is Right for You

• Benjamin Cohen-Wang
• Joshua Vendrow
• Aleksander Madry

Pre-training is a widely used approach to develop models that are robust to distribution shifts. However, in practice, its effectiveness varies: fine-tuning a pre-trained model improves robustness significantly in some cases but *not at all* in others (compared to training from scratch). In this work, we seek to characterize the failure modes that pre-training *can* and *cannot* address. In particular, we focus on two possible failure modes of models under distribution shift: poor extrapolation (e.g., they cannot generalize to a different domain) and biases in the training data (e.g., they rely on spurious features). Our study suggests that, as a rule of thumb, pre-training can help mitigate poor extrapolation but not dataset biases. After providing theoretical motivation and empirical evidence for this finding, we explore two of its implications for developing robust models: (1) pre-training and interventions designed to prevent exploiting biases have complementary robustness benefits, and (2) fine-tuning on a (very) small, non-diverse but *de-biased* dataset can result in significantly more robust models than fine-tuning on a large and diverse but biased dataset.

ICLR Conference 2025 Conference Paper

Machine Unlearning via Simulated Oracle Matching

• Kristian Georgiev
• Roy Rinberg
• Sung Min Park
• Shivam Garg
• Andrew Ilyas
• Aleksander Madry
• Seth Neel

Machine unlearning---efficiently removing the effect of a small "forget set" of training data on a pre-trained machine learning model---has recently attracted significant research interest. Despite this interest, however, recent work shows that existing machine unlearning techniques do not hold up to thorough evaluation in non-convex settings. In this work, we introduce a new machine unlearning technique that exhibits strong empirical performance even in such challenging settings. Our starting point is the perspective that the goal of unlearning is to produce a model whose outputs are *statistically indistinguishable* from those of a model re-trained on all but the forget set. This perspective naturally suggests a reduction from the unlearning problem to that of *data attribution, where the goal is to predict the effect of changing the training set on a model's outputs. Thus motivated, we propose the following meta-algorithm, which we call Datamodel Matching (DMM): given a trained model, we (a) use data attribution to *predict* the output of the model if it were re-trained on all but the forget set points; then (b) *fine-tune* the pre-trained model to match these predicted outputs. In a simple convex setting, we show how this approach provably outperforms a variety of iterative unlearning algorithms. Empirically, we use a combination of existing evaluations and a new metric based on the KL-divergence to show that even in non-convex settings, DMM achieves strong unlearning performance relative to existing algorithms. An added benefit of DMM is that it is a meta-algorithm, in the sense that future advances in data attribution translate directly into better unlearning algorithms, pointing to a clear direction for future progress in unlearning.

ICLR Conference 2025 Conference Paper

MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineering

• Jun Shern Chan
• Neil Chowdhury
• Oliver Jaffe
• James Aung
• Dane Sherburn
• Evan Mays
• Giulio Starace
• Kevin Liu

We introduce MLE-bench, a benchmark for measuring how well AI agents perform at machine learning engineering. To this end, we curate 75 ML engineering-related competitions from Kaggle, creating a diverse set of challenging tasks that test real-world ML engineering skills such as training models, preparing datasets, and running experiments. We establish human baselines for each competition using Kaggle's publicly available leaderboards. We use open-source agent scaffolds to evaluate several frontier language models on our benchmark, finding that the best-performing setup — OpenAI's o1-preview with AIDE scaffolding — achieves at least the level of a Kaggle bronze medal in 16.9% of competitions. In addition to our main results, we investigate various forms of resource-scaling for AI agents and the impact of contamination from pre-training. We open-source our benchmark code https://github.com/openai/mle-bench to facilitate future research in understanding the ML engineering capabilities of AI agents.

ICLR Conference 2025 Conference Paper

Small-to-Large Generalization: Training Data Influences Models Consistently Across Scale

• Alaa Khaddaj
• Logan Engstrom
• Aleksander Madry

Choice of training data distribution greatly influences model behavior. Yet, in large-scale settings, precisely characterizing *how* changes in training data affects predictions is often difficult due to model training costs. Current practice is to instead extrapolate from scaled down, inexpensive-to-train proxy models. However, changes in data do not influence smaller and larger models identically. Therefore, understanding how choice of data affects large-scale models raises the question: how does training data distribution influence model behavior across compute scale? We find that small- and large-scale language model predictions (generally) *do* highly correlate across choice of training data. Equipped with these findings, we characterize how proxy scale affects effectiveness in two downstream proxy model applications: data attribution and dataset selection.

ICML Conference 2024 Conference Paper

Decomposing and Editing Predictions by Modeling Model Computation

• Harshay Shah
• Andrew Ilyas
• Aleksander Madry

How does the internal computation of a machine learning model transform inputs into predictions? To tackle this question, we introduce a framework called component modeling for decomposing a model prediction in terms of its components—architectural "building blocks" such as convolution filters or attention heads. We focus on a special case of this framework, component attribution, where the goal is to estimate the counterfactual impact of individual components on a given prediction. We then present COAR, a scalable algorithm for estimating component attributions, and demonstrate its effectiveness across models, datasets and modalities. Finally, we show that COAR directly enables effective model editing. Our code is available at github. com/MadryLab/modelcomponents.

ICML Conference 2024 Conference Paper

DsDm: Model-Aware Dataset Selection with Datamodels

• Logan Engstrom
• Axel Feldmann
• Aleksander Madry

When selecting data for training large-scale models, standard practice is to filter for examples that match human notions of data quality. Such filtering yields qualitatively clean datapoints that intuitively should improve model behavior. However, in practice the opposite can often happen: we find that selecting according to similarity with "high quality" data sources may not increase (and can even hurt) performance compared to randomly selecting data. To develop better methods for selecting data, we start by framing dataset selection as an optimization problem that we can directly solve for: given target tasks, a learning algorithm, and candidate data, select the subset that maximizes model performance. This framework thus avoids handpicked notions of data quality, and instead models explicitly how the learning process uses train datapoints to predict on the target tasks. Our resulting method greatly improves language model (LM) performance on both pre-specified tasks and previously unseen tasks. Specifically, choosing target tasks representative of standard LM problems and evaluating on diverse held-out benchmarks, our selected datasets provide a 2x compute multiplier over baseline methods.

ICLR Conference 2023 Conference Paper

Distilling Model Failures as Directions in Latent Space

• Saachi Jain
• Hannah Lawrence
• Ankur Moitra
• Aleksander Madry

Existing methods for isolating hard subpopulations and spurious correlations in datasets often require human intervention. This can make these methods labor-intensive and dataset-specific. To address these shortcomings, we present a scalable method for automatically distilling a model's failure modes. Specifically, we harness linear classifiers to identify consistent error patterns, and, in turn, induce a natural representation of these failure modes as directions within the feature space. We demonstrate that this framework allows us to discover and automatically caption challenging subpopulations within the training dataset. Moreover, by combining our framework with off-the-shelf diffusion models, we can generate images that are especially challenging for the analyzed model, and thus can be used to perform synthetic data augmentation that helps remedy the model's failure modes.

ICML Conference 2023 Conference Paper

ModelDiff: A Framework for Comparing Learning Algorithms

• Harshay Shah
• Sung Min Park
• Andrew Ilyas
• Aleksander Madry

We study the problem of (learning) algorithm comparison, where the goal is to find differences between models trained with two different learning algorithms. We begin by formalizing this goal as one of finding distinguishing feature transformations, i. e. , input transformations that change the predictions of models trained with one learning algorithm but not the other. We then present ModelDiff, a method that leverages the datamodels framework (Ilyas et al. , 2022) to compare learning algorithms based on how they use their training data. We demonstrate ModelDiff through three case studies, comparing models trained with/without data augmentation, with/without pre-training, and with different SGD hyperparameters.

ICML Conference 2023 Conference Paper

Raising the Cost of Malicious AI-Powered Image Editing

• Hadi Salman
• Alaa Khaddaj
• Guillaume Leclerc
• Andrew Ilyas
• Aleksander Madry

We present an approach to mitigating the risks of malicious image editing posed by large diffusion models. The key idea is to immunize images so as to make them resistant to manipulation by these models. This immunization relies on injection of imperceptible adversarial perturbations designed to disrupt the operation of the targeted diffusion models, forcing them to generate unrealistic images. We provide two methods for crafting such perturbations, and then demonstrate their efficacy. Finally, we discuss a policy component necessary to make our approach fully effective and practical—one that involves the organizations developing diffusion models, rather than individual users, to implement (and support) the immunization process.

ICML Conference 2023 Conference Paper

Rethinking Backdoor Attacks

• Alaa Khaddaj
• Guillaume Leclerc
• Aleksandar Makelov
• Kristian Georgiev
• Hadi Salman
• Andrew Ilyas
• Aleksander Madry

In a backdoor attack, an adversary inserts maliciously constructed backdoor examples into a training set to make the resulting model vulnerable to manipulation. Defending against such attacks involves viewing inserted examples as outliers in the training set and using techniques from robust statistics to detect and remove them. In this work, we present a different approach to the backdoor attack problem. Specifically, we show that without structural information about the training data distribution, backdoor attacks are indistinguishable from naturally-occuring features in the data—and thus impossible to "detect" in a general sense. Then, guided by this observation, we revisit existing defenses against backdoor attacks and characterize the (often latent) assumptions they make, and on which they depend. Finally, we explore an alternative perspective on backdoor attacks: one that assumes these attacks correspond to the strongest feature in the training data. Under this assumption (which we make formal) we develop a new primitive for detecting backdoor attacks. Our primitive naturally gives rise to a detection algorithm that comes with theoretical guarantees, and is effective in practice.

ICML Conference 2023 Conference Paper

TRAK: Attributing Model Behavior at Scale

• Sung Min Park
• Kristian Georgiev
• Andrew Ilyas
• Guillaume Leclerc
• Aleksander Madry

The goal of data attribution is to trace model predictions back to training data. Despite a long line of work towards this goal, existing approaches to data attribution tend to force users to choose between computational tractability and efficacy. That is, computationally tractable methods can struggle with accurately attributing model predictions in non-convex settings (e. g. , in the context of deep neural networks), while methods that are effective in such regimes require training thousands of models, which makes them impractical for large models or datasets. In this work, we introduce TRAK (Tracing with the Randomly-projected After Kernel), a data attribution method that is both effective and computationally tractable for large-scale, differentiable models. In particular, by leveraging only a handful of trained models, TRAK can match the performance of attribution methods that require training thousands of models. We demonstrate the utility of TRAK across various modalities and scales: image classifiers trained on ImageNet, vision-language models (CLIP), and language models (BERT and mT5). We provide code for using TRAK (and reproducing our work) at https: //github. com/MadryLab/trak.

NeurIPS Conference 2022 Conference Paper

3DB: A Framework for Debugging Computer Vision Models

• Guillaume Leclerc
• Hadi Salman
• Andrew Ilyas
• Sai Vemprala
• Logan Engstrom
• Vibhav Vineet
• Kai Xiao
• Pengchuan Zhang

We introduce 3DB: an extendable, unified framework for testing and debugging vision models using photorealistic simulation. We demonstrate, through a wide range of use cases, that 3DB allows users to discover vulnerabilities in computer vision systems and gain insights into how models make decisions. 3DB captures and generalizes many robustness analyses from prior work, and enables one to study their interplay. Finally, we find that the insights generated by the system transfer to the physical world. 3DB will be released as a library alongside a set of examples and documentation. We attach 3DB to the submission.

ICML Conference 2022 Conference Paper

Adversarially trained neural representations are already as robust as biological neural representations

• Chong Guo
• Michael J. Lee
• Guillaume Leclerc
• Joel Dapello
• Yug Rao
• Aleksander Madry
• James J. DiCarlo

Visual systems of primates are the gold standard of robust perception. There is thus a general belief that mimicking the neural representations that underlie those systems will yield artificial visual systems that are adversarially robust. In this work, we develop a method for performing adversarial visual attacks directly on primate brain activity. We then leverage this method to demonstrate that the above-mentioned belief might not be well-founded. Specifically, we report that the biological neurons that make up visual systems of primates exhibit susceptibility to adversarial perturbations that is comparable in magnitude to existing (robustly trained) artificial neural networks.

ICML Conference 2022 Conference Paper

Combining Diverse Feature Priors

• Saachi Jain
• Dimitris Tsipras
• Aleksander Madry

To improve model generalization, model designers often restrict the features that their models use, either implicitly or explicitly. In this work, we explore the design space of leveraging such feature priors by viewing them as distinct perspectives on the data. Specifically, we find that models trained with diverse sets of explicit feature priors have less overlapping failure modes, and can thus be combined more effectively. Moreover, we demonstrate that jointly training such models on additional (unlabeled) data allows them to correct each other’s mistakes, which, in turn, leads to better generalization and resilience to spurious correlations.

ICML Conference 2022 Conference Paper

Datamodels: Understanding Predictions with Data and Data with Predictions

• Andrew Ilyas
• Sung Min Park
• Logan Engstrom
• Guillaume Leclerc
• Aleksander Madry

We present a conceptual framework, datamodeling, for analyzing the behavior of a model class in terms of the training data. For any fixed “target” example $x$, training set $S$, and learning algorithm, a datamodel is a parameterized function $2^S \to \mathbb{R}$ that for any subset of $S’ \subset S$—using only information about which examples of $S$ are contained in $S’$—predicts the outcome of training a model on $S’$ and evaluating on $x$. Despite the complexity of the underlying process being approximated (e. g. end-to-end training and evaluation of deep neural networks), we show that even simple linear datamodels successfully predict model outputs. We then demonstrate that datamodels give rise to a variety of applications, such as: accurately predicting the effect of dataset counterfactuals; identifying brittle predictions; finding semantically similar examples; quantifying train-test leakage; and embedding data into a well-behaved and feature-rich representation space.

ICLR Conference 2022 Conference Paper

Missingness Bias in Model Debugging

• Saachi Jain
• Hadi Salman
• Eric Wong 0001
• Pengchuan Zhang
• Vibhav Vineet
• Sai Vemprala
• Aleksander Madry

Missingness, or the absence of features from an input, is a concept fundamental to many model debugging tools. However, in computer vision, pixels cannot simply be removed from an image. One thus tends to resort to heuristics such as blacking out pixels, which may in turn introduce bias into the debugging process. We study such biases and, in particular, show how transformer-based architectures can enable a more natural implementation of missingness, which side-steps these issues and improves the reliability of model debugging in practice.

ICLR Conference 2021 Conference Paper

BREEDS: Benchmarks for Subpopulation Shift

• Shibani Santurkar
• Dimitris Tsipras
• Aleksander Madry

We develop a methodology for assessing the robustness of models to subpopulation shift---specifically, their ability to generalize to novel data subpopulations that were not observed during training. Our approach leverages the class structure underlying existing datasets to control the data subpopulations that comprise the training and test distributions. This enables us to synthesize realistic distribution shifts whose sources can be precisely controlled and characterized, within existing large-scale datasets. Applying this methodology to the ImageNet dataset, we create a suite of subpopulation shift benchmarks of varying granularity. We then validate that the corresponding shifts are tractable by obtaining human baselines. Finally, we utilize these benchmarks to measure the sensitivity of standard model architectures as well as the effectiveness of existing train-time robustness interventions.

NeurIPS Conference 2021 Conference Paper

Editing a classifier by rewriting its prediction rules

• Shibani Santurkar
• Dimitris Tsipras
• Mahalaxmi Elango
• David Bau
• Antonio Torralba
• Aleksander Madry

We propose a methodology for modifying the behavior of a classifier by directly rewriting its prediction rules. Our method requires virtually no additional data collection and can be applied to a variety of settings, including adapting a model to new environments, and modifying it to ignore spurious features.

FOCS Conference 2021 Conference Paper

Faster Sparse Minimum Cost Flow by Electrical Flow Localization

• Kyriakos Axiotis
• Aleksander Madry
• Adrian Vladu

We give an $\tilde{O}(m^{3/2-1/762}\log(U+W))$ time algorithm for minimum cost flow with capacities bounded by $U$ and costs bounded by $W$. For sparse graphs with general capacities, this is the first algorithm to improve over the $\tilde{O}(m^{3/2}\log^{O(1)}(U+W))$ running time obtained by an appropriate instantiation of an interior point method [Daitch-Spielman, 2008]. Our approach is extending the framework put forth in [Gao-Liu-Peng, 2021] for computing the maximum flow in graphs with large capacities and, in particular, demonstrates how to reduce the problem of computing an electrical flow with general demands to the same problem on a sublinear-sized set of vertices—even if the demand is supported on the entire graph. Along the way, we develop new machinery to assess the importance of the graph's edges at each phase of the interior point method optimization process. This capability relies on establishing a new connections between the electrical flows arising inside that optimization process and vertex distances in the corresponding effective resistance metric.

ICML Conference 2021 Conference Paper

Leveraging Sparse Linear Layers for Debuggable Deep Networks

• Eric Wong 0001
• Shibani Santurkar
• Aleksander Madry

We show how fitting sparse linear models over learned deep feature representations can lead to more debuggable neural networks. These networks remain highly accurate while also being more amenable to human interpretation, as we demonstrate quantitatively and via human experiments. We further illustrate how the resulting sparse explanations can help to identify spurious correlations, explain misclassifications, and diagnose model biases in vision and language tasks.

ICLR Conference 2021 Conference Paper

Noise or Signal: The Role of Image Backgrounds in Object Recognition

• Kai Yuanqing Xiao
• Logan Engstrom
• Andrew Ilyas
• Aleksander Madry

We assess the tendency of state-of-the-art object recognition models to depend on signals from image backgrounds. We create a toolkit for disentangling foreground and background signal on ImageNet images, and find that (a) models can achieve non-trivial accuracy by relying on the background alone, (b) models often misclassify images even in the presence of correctly classified foregrounds--up to 88% of the time with adversarially chosen backgrounds, and (c) more accurate models tend to depend on backgrounds less. Our analysis of backgrounds brings us closer to understanding which correlations machine learning models use, and how they determine models' out of distribution performance.

NeurIPS Conference 2021 Conference Paper

Unadversarial Examples: Designing Objects for Robust Vision

• Hadi Salman
• Andrew Ilyas
• Logan Engstrom
• Sai Vemprala
• Aleksander Madry
• Ashish Kapoor

We study a class of computer vision settings wherein one can modify the design of the objects being recognized. We develop a framework that leverages this capability---and deep networks' unusual sensitivity to input perturbations---to design ``robust objects, '' i. e. , objects that are explicitly optimized to be confidently classified. Our framework yields improved performance on standard benchmarks, a simulated robotics environment, and physical-world experiments.

ICLR Conference 2020 Conference Paper

A Closer Look at Deep Policy Gradients

• Andrew Ilyas
• Logan Engstrom
• Shibani Santurkar
• Dimitris Tsipras
• Firdaus Janoos
• Larry Rudolph
• Aleksander Madry

We study how the behavior of deep policy gradient algorithms reflects the conceptual framework motivating their development. To this end, we propose a fine-grained analysis of state-of-the-art methods based on key elements of this framework: gradient estimation, value prediction, and optimization landscapes. Our results show that the behavior of deep policy gradient algorithms often deviates from what their motivating framework would predict: surrogate rewards do not match the true reward landscape, learned value estimators fail to fit the true value function, and gradient estimates poorly correlate with the "true" gradient. The mismatch between predicted and empirical behavior we uncover highlights our poor understanding of current methods, and indicates the need to move beyond current benchmark-centric evaluation methods.

FOCS Conference 2020 Conference Paper

Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs

• Kyriakos Axiotis
• Aleksander Madry
• Adrian Vladu

We present an m 4/3+o(1) logW-time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the maximum absolute value of any edge weight. For sparse graphs, this improves over the best known running time for this problem and, by well-known reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite b-matching when ||b||1=O(m), and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (Liu-Sidford, 2020). Our algorithm relies on developing an interior point method-based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which is partially inspired by previous work on the unit-capacity maximum flow problem (Liu-Sidford, 2019), and subsequently refined based on the very recent progress on this problem (Liu-Sidford, 2020). The resulting step problem can then be computed efficiently using the recent work on lp-norm minimizing flows (Kyng-Peng-Sachdeva-Wang, 2019). We obtain our faster algorithm by combining this new step primitive with a customized preconditioning method, which aims to ensure that the graph on which these circulations are computed has sufficiently large conductance.

NeurIPS Conference 2020 Conference Paper

Do Adversarially Robust ImageNet Models Transfer Better?

• Hadi Salman
• Andrew Ilyas
• Logan Engstrom
• Ashish Kapoor
• Aleksander Madry

Transfer learning is a widely-used paradigm in deep learning, where models pre-trained on standard datasets can be efficiently adapted to downstream tasks. Typically, better pre-trained models yield better transfer results, suggesting that initial accuracy is a key aspect of transfer learning performance. In this work, we identify another such aspect: we find that adversarially robust models, while less accurate, often perform better than their standard-trained counterparts when used for transfer learning. Specifically, we focus on adversarially robust ImageNet classifiers, and show that they yield improved accuracy on a standard suite of downstream classification tasks. Further analysis uncovers more differences between robust and standard models in the context of transfer learning. Our results are consistent with (and in fact, add to) recent hypotheses stating that robustness leads to improved feature representations. Code and models is available in the supplementary material.

ICML Conference 2020 Conference Paper

From ImageNet to Image Classification: Contextualizing Progress on Benchmarks

• Dimitris Tsipras
• Shibani Santurkar
• Logan Engstrom
• Andrew Ilyas
• Aleksander Madry

Building rich machine learning datasets in a scalable manner often necessitates a crowd-sourced data collection pipeline. In this work, we use human studies to investigate the consequences of employing such a pipeline, focusing on the popular ImageNet dataset. We study how specific design choices in the ImageNet creation process impact the fidelity of the resulting dataset—including the introduction of biases that state-of-the-art models exploit. Our analysis pinpoints how a noisy data collection pipeline can lead to a systematic misalignment between the resulting benchmark and the real-world task it serves as a proxy for. Finally, our findings emphasize the need to augment our current model training and evaluation toolkit to take such misalignment into account.

ICML Conference 2020 Conference Paper

Identifying Statistical Bias in Dataset Replication

• Logan Engstrom
• Andrew Ilyas
• Shibani Santurkar
• Dimitris Tsipras
• Jacob Steinhardt
• Aleksander Madry

Dataset replication is a useful tool for assessing whether improvements in test accuracy on a specific benchmark correspond to improvements in models’ ability to generalize reliably. In this work, we present unintuitive yet significant ways in which standard approaches to dataset replication introduce statistical bias, skewing the resulting observations. We study ImageNet-v2, a replication of the ImageNet dataset on which models exhibit a significant (11-14%) drop in accuracy, even after controlling for selection frequency, a human-in-the-loop measure of data quality. We show that after remeasuring selection frequencies and correcting for statistical bias, only an estimated 3. 6% of the original 11. 7% accuracy drop remains unaccounted for. We conclude with concrete recommendations for recognizing and avoiding bias in dataset replication. Code for our study is publicly available: https: //git. io/data-rep-analysis.

ICLR Conference 2020 Conference Paper

Implementation Matters in Deep RL: A Case Study on PPO and TRPO

• Logan Engstrom
• Andrew Ilyas
• Shibani Santurkar
• Dimitris Tsipras
• Firdaus Janoos
• Larry Rudolph
• Aleksander Madry

We study the roots of algorithmic progress in deep policy gradient algorithms through a case study on two popular algorithms: Proximal Policy Optimization (PPO) and Trust Region Policy Optimization (TRPO). Specifically, we investigate the consequences of "code-level optimizations:" algorithm augmentations found only in implementations or described as auxiliary details to the core algorithm. Seemingly of secondary importance, such optimizations turn out to have a major impact on agent behavior. Our results show that they (a) are responsible for most of PPO's gain in cumulative reward over TRPO, and (b) fundamentally change how RL methods function. These insights show the difficulty, and importance, of attributing performance gains in deep reinforcement learning.

NeurIPS Conference 2020 Conference Paper

On Adaptive Attacks to Adversarial Example Defenses

• Florian Tramer
• Nicholas Carlini
• Wieland Brendel
• Aleksander Madry

Adaptive attacks have (rightfully) become the de facto standard for evaluating defenses to adversarial examples. We find, however, that typical adaptive evaluations are incomplete. We demonstrate that 13 defenses recently published at ICLR, ICML and NeurIPS---and which illustrate a diverse set of defense strategies---can be circumvented despite attempting to perform evaluations using adaptive attacks. While prior evaluation papers focused mainly on the end result---showing that a defense was ineffective---this paper focuses on laying out the methodology and the approach necessary to perform an adaptive attack. Some of our attack strategies are generalizable, but no single strategy would have been sufficient for all defenses. This underlines our key message that adaptive attacks cannot be automated and always require careful and appropriate tuning to a given defense. We hope that these analyses will serve as guidance on how to properly perform adaptive attacks against defenses to adversarial examples, and thus will allow the community to make further progress in building more robust models.

NeurIPS Conference 2019 Conference Paper

Adversarial Examples Are Not Bugs, They Are Features

• Andrew Ilyas
• Shibani Santurkar
• Dimitris Tsipras
• Logan Engstrom
• Brandon Tran
• Aleksander Madry

Adversarial examples have attracted significant attention in machine learning, but the reasons for their existence and pervasiveness remain unclear. We demonstrate that adversarial examples can be directly attributed to the presence of non-robust features: features (derived from patterns in the data distribution) that are highly predictive, yet brittle and (thus) incomprehensible to humans. After capturing these features within a theoretical framework, we establish their widespread existence in standard datasets. Finally, we present a simple setting where we can rigorously tie the phenomena we observe in practice to a {\em misalignment} between the (human-specified) notion of robustness and the inherent geometry of the data.

ICML Conference 2019 Conference Paper

Exploring the Landscape of Spatial Robustness

• Logan Engstrom
• Brandon Tran
• Dimitris Tsipras
• Ludwig Schmidt
• Aleksander Madry

The study of adversarial robustness has so far largely focused on perturbations bound in $\ell_p$-norms. However, state-of-the-art models turn out to be also vulnerable to other, more natural classes of perturbations such as translations and rotations. In this work, we thoroughly investigate the vulnerability of neural network–based classifiers to rotations and translations. While data augmentation offers relatively small robustness, we use ideas from robust optimization and test-time input aggregation to significantly improve robustness. Finally we find that, in contrast to the $\ell_p$-norm case, first-order methods cannot reliably find worst-case perturbations. This highlights spatial robustness as a fundamentally different setting requiring additional study.

NeurIPS Conference 2019 Conference Paper

Image Synthesis with a Single (Robust) Classifier

• Shibani Santurkar
• Andrew Ilyas
• Dimitris Tsipras
• Logan Engstrom
• Brandon Tran
• Aleksander Madry

We show that the basic classification framework alone can be used to tackle some of the most challenging tasks in image synthesis. In contrast to other state-of-the-art approaches, the toolkit we develop is rather minimal: it uses a single, off-the-shelf classifier for all these tasks. The crux of our approach is that we train this classifier to be adversarially robust. It turns out that adversarial robustness is precisely what we need to directly manipulate salient features of the input. Overall, our findings demonstrate the utility of robustness in the broader machine learning context.

ICML Conference 2018 Conference Paper

A Classification-Based Study of Covariate Shift in GAN Distributions

• Shibani Santurkar
• Ludwig Schmidt
• Aleksander Madry

A basic, and still largely unanswered, question in the context of Generative Adversarial Networks (GANs) is whether they are truly able to capture all the fundamental characteristics of the distributions they are trained on. In particular, evaluating the diversity of GAN distributions is challenging and existing methods provide only a partial understanding of this issue. In this paper, we develop quantitative and scalable tools for assessing the diversity of GAN distributions. Specifically, we take a classification-based perspective and view loss of diversity as a form of covariate shift introduced by GANs. We examine two specific forms of such shift: mode collapse and boundary distortion. In contrast to prior work, our methods need only minimal human supervision and can be readily applied to state-of-the-art GANs on large, canonical datasets. Examining popular GANs using our tools indicates that these GANs have significant problems in reproducing the more distributional properties of their training dataset.

NeurIPS Conference 2018 Conference Paper

Adversarially Robust Generalization Requires More Data

• Ludwig Schmidt
• Shibani Santurkar
• Dimitris Tsipras
• Kunal Talwar
• Aleksander Madry

Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

NeurIPS Conference 2018 Conference Paper

How Does Batch Normalization Help Optimization?

• Shibani Santurkar
• Dimitris Tsipras
• Andrew Ilyas
• Aleksander Madry

Batch Normalization (BatchNorm) is a widely adopted technique that enables faster and more stable training of deep neural networks (DNNs). Despite its pervasiveness, the exact reasons for BatchNorm's effectiveness are still poorly understood. The popular belief is that this effectiveness stems from controlling the change of the layers' input distributions during training to reduce the so-called "internal covariate shift". In this work, we demonstrate that such distributional stability of layer inputs has little to do with the success of BatchNorm. Instead, we uncover a more fundamental impact of BatchNorm on the training process: it makes the optimization landscape significantly smoother. This smoothness induces a more predictive and stable behavior of the gradients, allowing for faster training.

STOC Conference 2018 Conference Paper

k-server via multiscale entropic regularization

• Sébastien Bubeck
• Michael B. Cohen
• Yin Tat Lee
• James R. Lee
• Aleksander Madry

We present an O ((log k ) 2 )-competitive randomized algorithm for the k -server problem on hierarchically separated trees (HSTs). This is the first o ( k )-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy. When combined with Bartal’s static HST embedding reduction, this leads to an O ((log k ) 2 log n )-competitive algorithm on any n -point metric space. We give a new dynamic HST embedding that yields an O ((log k ) 3 logΔ)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most Δ.

ICML Conference 2018 Conference Paper

On the Limitations of First-Order Approximation in GAN Dynamics

• Jerry Li 0001
• Aleksander Madry
• John Peebles
• Ludwig Schmidt

While Generative Adversarial Networks (GANs) have demonstrated promising performance on multiple vision tasks, their learning dynamics are not yet well understood, both in theory and in practice. To address this issue, we study GAN dynamics in a simple yet rich parametric model that exhibits several of the common problematic convergence behaviors such as vanishing gradients, mode collapse, and diverging or oscillatory behavior. In spite of the non-convex nature of our model, we are able to perform a rigorous theoretical analysis of its convergence behavior. Our analysis reveals an interesting dichotomy: a GAN with an optimal discriminator provably converges, while first order approximations of the discriminator steps lead to unstable GAN dynamics and mode collapse. Our result suggests that using first order discriminator steps (the de-facto standard in most existing GAN setups) might be one of the factors that makes GAN training challenging in practice.

STOC Conference 2018 Conference Paper

Round compression for parallel matching algorithms

• Artur Czumaj
• Jakub Lacki
• Aleksander Madry
• Slobodan Mitrovic
• Krzysztof Onak
• Piotr Sankowski

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture the nature of large-scale computation. In particular, compared to the classic distributed algorithms or PRAM models, these frameworks allow for much more local computation. The fundamental question that arises in this context is though: can we leverage this additional power to obtain even faster parallel algorithms?

NeurIPS Conference 2018 Conference Paper

Spectral Signatures in Backdoor Attacks

• Brandon Tran
• Jerry Li
• Aleksander Madry

A recent line of work has uncovered a new form of data poisoning: so-called backdoor attacks. These attacks are particularly dangerous because they do not affect a network's behavior on typical, benign data. Rather, the network only deviates from its expected output when triggered by an adversary's planted perturbation. In this paper, we identify a new property of all known backdoor attacks, which we call spectral signatures. This property allows us to utilize tools from robust statistics to thwart the attacks. We demonstrate the efficacy of these signatures in detecting and removing poisoned examples on real image sets and state of the art neural network architectures. We believe that understanding spectral signatures is a crucial first step towards a principled understanding of backdoor attacks.

FOCS Conference 2017 Conference Paper

Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

• Michael B. Cohen
• Aleksander Madry
• Dimitris Tsipras
• Adrian Vladu

In this paper 1, we study matrix scaling and balancing, which are fundamental problems in scientific computing, with a long line of work on them that dates back to the 1960s. We provide algorithms for both these problems that, ignoring logarithmic factors involving the dimension of the input matrix and the size of its entries, both run in time Õ(m log κ log 2 (1/ε)) where ε is the amount of error we are willing to tolerate. Here, κ represents the ratio between the largest and the smallest entries of the optimal scalings. This implies that our algorithms run in nearly-linear time whenever κ is quasi-polynomial, which includes, in particular, the case of strictly positive matrices. We complement our results by providing a separate algorithm that uses an interior-point method and runs in time Õ(m 3/2 log(1/ε)). In order to establish these results, we develop a new secondorder optimization framework that enables us to treat both problems in a unified and principled manner. This framework identifies a certain generalization of linear system solving that we can use to efficiently minimize a broad class of functions, which we call second-order robust. We then show that in the context of the specific functions capturing matrix scaling and balancing, we can leverage and generalize the work on Laplacian system solving to make the algorithms obtained via this framework very efficient.

SODA Conference 2017 Conference Paper

Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in Õ ( m 10/7 log W ) Time (Extended Abstract)

• Michael B. Cohen
• Aleksander Madry
• Piotr Sankowski
• Adrian Vladu

In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem, and the weighted perfect bipartite b -matching problem under the assumption that‖b‖ 1 = O ( m ). We show that each of these four problems can be solved in Õ( m 10/7 log W ) time, where W is the absolute maximum weight of an edge in the graph, providing the first polynomial improvement in their sparse-graph time complexity in over 25 years. At a high level, our algorithms build on the interior- point method-based framework developed by Mądry (FOCS 2013) for solving unit-capacity maximum flow problem. We develop a refined way to analyze this framework, as well as provide new variants of the underlying preconditioning and perturbation techniques. Consequently, we are able to extend the whole interior-point method-based approach to make it applicable in the weighted graph regime.

FOCS Conference 2016 Conference Paper

Computing Maximum Flow with Augmenting Electrical Flows

• Aleksander Madry

We present an Õ (m 7/10 U 1/7)-time algorithm for the maximum s-t flow problem (and the minimum s-t cut problem) in directed graphs with m arcs and largest integer capacity U. This matches the running time of the Õ (mU)10/7)- time algorithm of Madry [30] in the unit-capacity case, and improves over it, as well as over the Õ (m√n log U)-time algorithm of Lee and Sidford [25], whenever U is moderately large and the graph is sufficiently sparse. By well-known reductions, this also implies similar running time improvements for the maximum-cardinality bipartite b-matching problem. One of the advantages of our algorithm is that it is significantly simpler than the ones presented in [30] and [25]. In particular, these algorithms employ a sophisticated interior-point method framework, while our algorithm is cast directly in the classic augmenting path setting that almost all the combinatorial maximum flow algorithms use. At a high level, the presented algorithm takes a primal dual approach in which each iteration uses electrical flows computations both to find an augmenting s-t flow in the current residual graph and to update the dual solution. We show that by maintain certain careful coupling of these primal and dual solutions we are always guaranteed to make significant progress.

SODA Conference 2015 Conference Paper

Fast Generation of Random Spanning Trees and the Effective Resistance Metric

• Aleksander Madry
• Damian Straszak
• Jakub Tarnawski

FOCS Conference 2013 Conference Paper

Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back

• Aleksander Madry

We present an Õ(m 10/7 ) = Õ(m 1. 43 )-time 1 algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{√m, n 2/3 }) running time bound due to Even and Tarjan [16]. By well-known reductions, this also establishes an Õ(m 107 )-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated O(m√n) running time bound of Hopcroft and Karp [25] whenever the input graph is sufficiently sparse. At a very high level, our results stem from acquiring a deeper understanding of interior-point methods - a powerful tool in convex optimization - in the context of flow problems, as well as, utilizing certain interplay between maximum flows and bipartite matchings.

FOCS Conference 2011 Conference Paper

A Polylogarithmic-Competitive Algorithm for the k-Server Problem

• Nikhil Bansal 0001
• Niv Buchbinder
• Aleksander Madry
• Joseph Naor

We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log 3 n log 2 k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.

STOC Conference 2011 Conference Paper

Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

• Paul F. Christiano
• Jonathan A. Kelner
• Aleksander Madry
• Daniel A. Spielman
• Shang-Hua Teng

SODA Conference 2010 Conference Paper

An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem

• Arash Asadpour
• Michel X. Goemans
• Aleksander Madry
• Shayan Oveis Gharan
• Amin Saberi

We consider the Asymmetric Traveling Salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O (log n / log log n ) of the optimum with high probability.

FOCS Conference 2010 Conference Paper

Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs

• Aleksander Madry

We present a general method of designing fast approximation algorithms for cut-based minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a poly-logarithmic factor in the approximation guarantee. To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands and the balanced separator problem. By a simple use of our framework, we obtain poly-logarithmic approximation algorithms for these problems that run in time close to linear. The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cut-flow structure. This decomposition is inspired by the cut-based graph decomposition of R\"acke that was developed in the context of oblivious routing schemes, as well as, by the construction of the ultrasparsifiers due to Spiel man and Teng that was employed to preconditioning symmetric diagonally-dominant matrices.

STOC Conference 2010 Conference Paper

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

• Aleksander Madry

We combine the work of Garg and Konemann, and Fleischer with ideas from dynamic graph algorithms to obtain faster (1-ε)-approximation schemes for various versions of the multicommodity flow problem. In particular, if ε is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match -- up to poly-logarithmic factors and some provably optimal terms -- the Ω(mn) flow-decomposition barrier for single-commodity flow.

FOCS Conference 2009 Conference Paper

Faster Generation of Random Spanning Trees

• Jonathan A. Kelner
• Aleksander Madry

In this paper, we set forth a new algorithm for generating approximately uniformly random spanning trees in undirected graphs. We show how to sample from a distribution that is within a multiplicative (1+ ¿) of uniform in expected time O¿(m¿n log 1/¿). This improves the sparse graph case of the best previously known worst-case bound of O(min {mn, n 2. 376 }), which has stood for twenty years. To achieve this goal, we exploit the connection between random walks on graphs and electrical networks, and we use this to introduce a new approach to the problem that integrates discrete random walk-based techniques with continuous linear algebraic methods. We believe that our use of electrical networks and sparse linear system solvers in conjunction with random walks and combinatorial partitioning techniques is a useful paradigm that will find further applications in algorithmic graph theory.