Meta: After a fun little motivating section, this post goes deep into the mathematical weeds. This thing aims to explore the mathematical properties of adversarial attacks from first principles. Perhaps other people are not as confused about this point as I was, but hopefully, the arguments are still useful and/or interesting to some. I'd be curious to hear if I'm reinventing the wheel.

TL;DR: 

1. When we invest the appropriate effort, the probability of random catastrophic events tends to decrease exponentially with a rate given by the^[1] rate function.
2. One way of estimating the rate function is to solve an optimal control problem, where we have to determine the "least surprising" way that the catastrophic event comes about. The rate function equals the catastrophic event's surprise (in nats).
3. Thus, intuitively, as we invest the effort to decrease the probability of random catastrophic events, the "difficulty" of performing an adversarial attack only increases linearly.

Real talk and real estate

Zillow is an American tech real-estate marketplace company that recently had (what the experts call) a small snafu. They decided they were done just being a marketplace and started buying up homes, completing light renovations, and then selling them with a profit. The whole thing went poorly; they bought houses too expensive and had to sell at a loss, costing the company $420 million and leading to large lay-offs.

This story is not very interesting^[2] for anyone not directly involved. The reason I remember the whole affair is a Twitter thread that also caught the attention of Eliezer:

The thread proceeds to lay out how Zillow relied too much on their automatic estimates, which (ex-ante) looked good on average, but (ex-post) manifested in the worst possible way^[3]. Or, in the words of the OP:

"[They mistook] an adversarial environment for a random one."

I have approximately zero knowledge about Zillow or the real estate business, so I can't comment on whether this actually is what went wrong (edit: see this comment for a more informed take!). But the distinction between a random and an adversarial environment applies beyond the Zillow example and is relevant for research in AI Safety: from adversarial examples, via adversarial training, all the way to conceivable existential risk scenarios. It is the distinction between a world where it's fine to go outside because getting struck by lightning is sufficiently unlikely and a world where somebody is trying to smite you.

This post works towards achieving a mathematical understanding of what distinguishes these two worlds. Perhaps other people are not as confused about this point as I was, but hopefully, the arguments are still useful and/or interesting to some. I'll introduce a bit of extreme value theory. Then I'll demonstrate a neat connection to control theory via large deviation theory, which shows that an exponentially decreasing risk of failure translates into a linearly increasing difficulty of adversarial attacks.

A random environment

I'll go over the basics quickly: When you (i.e. Zillow) think of your environment as random, each house you buy is essentially a coin flip with a biased coin. If you make sure that 

1. the expected value of a deal is positive and 
2. that all the deals are (mostly) independent of each other, 

then you're guaranteed to accrue profits eventually. 

This guarantee is the law of large numbers from probability theory 101 and probably not too revolutionary for you, dear reader. But what is the probability of things going very badly? What is the probability of an extreme event or a large deviation? It should decrease (given the law of large numbers), but how fast does it decrease?

Let's continue the example of buying and selling houses and say that there is a probability $p$  that a given deal ends up profitable. The worst-case probability that all your deals go poorly is $(1-p{)}^N$, which goes to $0$ exponentially fast as we increase the number of deals $N$.

It turns out that this toy example generalizes a lot, and the probability that the sum of independent random variables $X_i$ is less than some fraction $\xi$ times $N$ always^[4] goes down exponentially fast in $N$:

The function $J\left(\xi \right)$ is called the "rate function," and it determines the speed with which extreme events get unlikely.

How to compute the rate function^[5]? That is what we'll explore in the next section. There is a "standard" way of calculating $J\left(\xi \right)$ which is a bit involved and opaque^[6] for my taste; I prefer a slightly non-standard derivation^[7] of arriving at the rate function, which gives deeper insight into how adversarial attacks and extreme events relate.

Average surprise and optimal control

As I like to say: there is, of course, another way of looking at this. We can think of the sequence of house deals as a sequence of random events that fluctuate around the probability of failure $1-p$. 

For a truly random sequence of events, we can compute the average surprise by averaging the information content of all events:

where the information content of an individual event is given as

and the probability measure $P_p\left(x\right)$ is a Bernoulli measure, $P_p\left(x\right)=\{\begin{array}{cc}p& :x=1\\ 1-p& :x=0\end{array}$. In the picture, the probability of a random Bernoulli event is the distance from the dashed line, $P_p\left(x_i\right)=|x_i-(1-p)|$. Consequently, the information content is $I_p\left(x_i\right)=-\ln |x_i-(1-p)|$ and the average information content of the sequence is $-\frac{1}{N}{\sum }_i\ln |x_i-(1-p)|$.^[8]

Why am I bringing this up? It turns out that the rate function $J\left(\xi \right)$ is the solution to an optimal control problem that involves the average excess surprise. In particular^[9],

The intuition behind this equation is: If we want to know the rate function for an extreme event, $[x_1,\dots ,x_N]$ we get to pick how the extreme event comes about (that's the $inf$). The only thing we have to respect is that the extreme event does, in fact, come about (${\sum }_i{x}_i=\xi N$). And then we try to make it so that the average excess surprise, $I_p\left(\right[x_1,\dots ,x_N\left]\right)-I_{\xi }\left(\right[x_1,\dots ,x_N\left]\right)$, is as small as possible.

Let's see how this plays out in our house deal example. We want to determine the probability that the sum of independent random variables $X_i$ is less than some success fraction $\xi$ times $N$, $P({\sum }_i{X}_i\le N\xi )$, i.e. that a certain fraction $1-\xi$ of our $N$ house deals go badly.

Now we get to pick how the extreme event, $[x_1,\dots ,x_N]$, comes about. I went ahead and already did that in the illustration. I picked it so that the first $(1-\xi )N$ deals go wrong, and only the remaining $\xi N$ deals go fine. This configuration satisfies the constraint that ${\sum }_i{x}_i=\xi N$ and (thanks to commutativity^[10]) the average excess surprise of this configuration is identical to that of all possible permutations. Therefore, this configuration's average excess surprise is already the infimum of all possible configurations that satisfy the constraint. Given the expression we wrote above for the average information content of a Bernoulli sequence, we can write the average excess surprise as

Since we know that $x_1,\dots ,x_{\xi N}$ are equal to $1$ and that $x_{\xi N+1},\dots ,x_N$ are equal to $0$, we can simplify the expression for $J\left(\xi \right)$ by splitting up the sums and regrouping,

You might recognize this as the KL-divergence between two Bernoulli random variables, $D_{\text{KL}}\left(\Xi ||X\right)=E\left(\Xi \ln \frac{\Xi }{X}\right)$, one with success probability $p$, the other with success probability $\xi$. When we plug in the extreme event that all the deals go poorly, $\xi =0$, the rate function reduces to $J\left(\xi \right)=-\ln (1-p)$, and the probability of this extreme event is

as it should be.

An adversarial environment

Quick recap: 

1. When we find ourselves in a random environment, then we can leverage the law of large numbers to push the probability of failure close to zero by trying sufficiently many times^[11], $N$.
2. If we want to find out how fast the probability of failure goes to zero, we can find that out by solving an optimal control problem where we need to determine the least surprising way failure might come about, $J\left(\xi \right)$. 
3. The probability of failure then goes to zero exponentially fast, proportional to how surprised we would be and the number of tries, $\exp (-NJ(\xi \left)\right)$.

So far, so good, but... what is that sound in the distance^[12]?

As general as the theorems mentioned above are in terms of the underlying distributions^[13], they centrally rely on the assumption that the environment is random. This was not the case for Zillow, where homeowners and real estate agencies selling houses had additional information to select bad deals for Zillow systematically. Instead of pushing the risk of total failure strongly toward zero, Zillow only increasingly exposed itself to an adversary with more insight into the situation.

While the probability of complete failure,  $\exp (-NJ(\xi \left)\right)$, falls exponentially, the amount of surprise required to bring it about, $NJ\left(\xi \right)$, scales linearly! A few things of note:

1. The unit of "surprise" is nats, a measure of information. This interpretation maps only weakly onto the house buying example (where one bit of information might indicate whether a given deal is bad for Zillow). Still, it has a much more straightforward interpretation when we think about set-ups where information passes through a single channel and can be arbitrarily constrained.
2. Similarly, we can interpret the expected excess surprise, $I_p\left(\right[x_1,\dots ,x_N\left]\right)-I_{\xi }\left(\right[x_1,\dots ,x_N\left]\right)$, as a functional on a state space spanned by $[x_1,\dots ,x_N]$. The fact that we compute the infimum over this functional turns the problem into an instance of Hamilton's principle - the "true" evolution of the sequence of states is stationary w.r.t. the "action" given by the excess surprise. Through this lens, we're close to "intelligence as optimization power", which characterizes intelligence as the ability to steer reality into a small subset of possible states. But I can't quite put the pieces in the right place to make the connection click.
3. Since we compute $NJ\left(\xi \right)$ as the solution to an optimal control problem that minimizes excess surprise, it is the lower bound on the amount of surprise required. Catastrophe can also come about in more surprising ways, but highly improbable events tend to happen in the least improbable way. On the plus side, catastrophe cannot come about with less surprise, which might have applications for the set-ups with constrained communication mentioned in point 1.
4. The team at Redwood Research recently released their report on their research on high-stakes alignment, where they trained a filter to reduce the probability of harmful output from 2.5% in the training set to 0.003% after applying the filter to 0.002% after adversarial training. While OOM reduction in failure probability feels comforting, this only helps when the adversary is not actively trying to trick the filter (from 3.6 nats to 10.8 nats of information). This is consistent with their finding that their tool-assisted search for adversarial examples was 1000x more effective than naive sampling.

These factors combined make me excited about exploring this direction further to find reliable estimates of the lower bound of input required to bring about catastrophe^[14]. I'm also curious if there is more structure to the similarity between the information content of an adversarial attack and the characterization of intelligence in terms of optimization processes. If you know more about this or can point me to some literature on the topic, please let me know!

1. ^{^}

    (appropriately named)

2. ^{^}

   How much is $420 million again? My gut feeling is that this type of snafu happens somewhere in the world every other week.

3. ^{^}

   In the same way that the maximum of a set of random variables can be overwhelmingly good in expectation, the minimum of the same set is terrible (in expectation). That's the power of choice.

4. ^{^}

   Well, not always. That's the point of this post.

5. ^{^}

   you ask, presumably on the edge of your seat.

6. ^{^}

   (you need the logarithm of the moment generating function of your random variable, $\lambda \left(\theta \right)=\ln E\left(\exp \right(\theta X_i\left)\right)$, and then you need to compute the Legendre-Fenchel transformation, $J\left(\xi \right)={sup}_{\theta >0}[\theta \xi -\lambda (\theta \left)\right]$.)

7. ^{^}

   I don't have a reference that follows exactly the same path I choose, but I enjoy the texts by Touchette 2011 and Paninski 2006.

8. ^{^}

   Absolute values are a bit icky, but since we have the $\ln$ we can be a bit sneaky and write $-\frac{1}{N}\frac{1}{2}{\sum }_i\ln ||x_i-(1-p)|{|}^2$ instead. This now has an uncanny similarity to the Freidlin-Wentzell rate function, which can't be a coincidence.

9. ^{^}

   (I recommend staring at that for a while.)

10. ^{^}

    When the control problem gets more involved and the individual time points are not interchangeable this step gets a bit trickier and we have to recruit some mathematical machinery.

11. ^{^}

    Given that the expected value is positive ofc.

12. ^{^}

    

13. ^{^}

    and any additional structure you might want to slap on

14. ^{^}

    Perhaps we can manage to reliably stay below that bound?