# 4

Formal ProofAI
Frontpage

Proposition 10: Mixture, updating, and continuous pushforward preserve the properties indicated by the diagram, and always produce an infradistribution.

We'll start with showing that mixture, updating, and continuous pushfoward are always infradistributions, and then turn to property verification.

We know from the last post that mixture, updating, and continuous pushfoward preserve all infradistribution properties (although you need to be careful about whether mixture preserves Lipschitzness, you need that the expected value of the Lipschitz constant is finite), but we added the new one about compact almost-support, so that's the only part we need to re-verify.

To show that mixture has compact almost-support, remember that

Now, fix an , we will craft a compact set that accounts for all but  of why functions have the expectation values they do. There is some n where , where  is the Lipschitz constant of the infradistribution . Then, let  be , the union of the compact -almost-supports for the infradistributions . This is a finite union of compact sets, so it's compact.

Now we can go:

The first equality is reexpressing mixtures, and the first inequality is moving the expectation outside the absolute value which doesn't decrease value, then we break up the expectation for the second equality. The second inequality is because the gap between  and  has a trivial upper bound from the Lipschitzness of , and for , we have that  and  agree on the union of the -almost-supports for the , so a particular infradistribution, by the definition of an almost-support, has these two expectations having not-very-different values. Then we just pull the gap between  and  out, and use the fact that for the mixture to work, , and we picked n big enough for that last tail of the infinite sum to be small. Then we're done.

Now, we will show compact almost-support for  assuming  has compact almost-support. Fix an . Your relevant set for  will be

Where the first term is a compact set that is a -almost-support for , and that last set is a sort of "this point must be likely enough".  will be the Lipschitz constant of the original . Yes, this intersection may be empty.

Now, here's how things go. Let  and  agree on that intersection. (if it's the empty set, then it can be any two functions). We can go:

So far, this is just a standard sequence of rewrites. The definition of the update, pulling the fraction out, using  to abbreviate the rescaling term, and unpacking what  means.

Now, let's see how different  and  are on the set . One of two things will occur. Our first possibility is that an  in that compact set also has . Then

and  were selected to be equal on that set, so the two functions will be identical on that point. Our second possibility is that  in that compact set will have . In that case,

Because .

Putting this together,  and  are only  apart when restricted to the compact set . By Lemma 2, we can then show that

And, we also know that:

Because . Making that substitution, we have:

Backing up to earlier, we had established that

and from shortly above, we established that

Putting these together,

For any two functions  and  which agree on

Witnessing that said set is an -almost-support for .

All we need to finish up is to show that this is a compact set in  equipped with the subspace topology. This can be done by observing that in the original space  it's a compact set, due to being the intersection of a compact set and a closed set. In the subspace topology, if we try to make an open cover of it, all the open sets that cover it in the subspace topology are the restrictions of open sets in the original topology, so we have an open cover of this set in the original topology, and we can make a finite subcover, so it's compact in the subspace topology as well.

Thus, for any , we can make a compact (in -almost-support for , so  has compact almost-support and we've verified the last condition for an update of an infradistribution to be an update.

Now for deterministic pushfoward. Fix an , and let your appropriate set for  be  where  is a compact -almost-support for . The image of a compact set is compact, so that part is taken care of. We still need to check that it's an -almost-support for . Let  be equal on this set. Then

And we're done. This is because, for any point , feeding it through  makes a point in , and feeding it through  and  produces identical results because they agree on . Therefore,  and  agree on  and thus can have values only  apart, which is actually upper-bounded by  is thus a compact -almost-support for , and this can be done for any , so  has compact almost-support.

Since these three operations always produce infradistributions (as we've shown, we verified the last condition). Updating only has two properties to check, preserving homogenity when  and cohomogenity when , so let's get that knocked out.

Homogenity using homogenity for h

Cohomogenity using cohomogenity for h

Now for mixtures, we'll verify homogenity, 1-Lipschitzness, cohomogenity, C-additivity, and crispness.

Homogenity:

1-Lipschitz:

Cohomogenity:

Crispness: Observe that both homogenity and C-additivity are preserved, and crispness is equivalent to the conjunction of the two.

Now for deterministic pushforwards, we'll verify homogenity, 1-Lipschitzness, cohomogenity, C-additivity, crispness, and sharpness.

Homogenity:

1-Lipschitzness:

Cohomogenity:

Crispness: Both homogenity and C-additivity are preserved, so crispness is preserved too.

Sharpness:

And  is the image of a compact set, so it's compact. And we're done!

Proposition 11: The inf of two infradistributions is always an infradistribution, and inf preserves the infradistribution properties indicated by the diagram at the start of this section.

We'll first verify the infradistribution properties of the inf, and then show it preserves the indicated properties if both components have them.

We must check monotonicity, concavity, normalization, Lipschitzness, and compact almost-support. For monotonicity, if , then

This was done by monotonicity for the components. For concavity,

The first  happened because  and  are concave, the second is because .

For normalization,

And the same argument applies to 0, so the inf is normalized.

For Lipschitzness, the inf of two Lipschitz functions is Lipschitz.

That just leaves compact almost-support. Fix an arbitary , and get a  compact -almost-support for , and a  for . We will show that  is a compact -almost-support for . It's compact because it's a finite union of compact sets.

Now, let  and  agree on . We can go:

There are four possible cases for evaluating this quantity. In case 1,  and . Then our above term turns into . However, since  and  agree on , they must agree on , and only have expectations  apart. Case 2 where  and  is symmetric and can be disposed of by a nearly identical argument, we just do it with  and .

Case 3 where  and  takes a slightly fancier argument. We can go:

The end inequalities are because  and  agree on the -almost-supports of  and , respectively, from agreeing on the union. The two inner inequalities are derived from the assumed inequalities in Case 3.
Thus,

Case 4 where the assumed starting inequalities go in the other direction is symmetric. So, no matter which infradistributions are lower in the two infs, we have

And we're done, we made a compact almost-support for  assuming an arbitrary . So the inf of two infradistributions is a infradistribution.

Now to verify homogenity, 1-Lipschitzness, cohomogenity, C-additivity, crispness, and sharpness preservation.

Homogenity:

1-Lipschitzness:

Now we can split into four cases. In cases 1 and 2 where the infs turn into  (and same for  in case 2), we have:

(and same for ), and we're done with those cases. In cases 3 and 4 where the infs turn into  (and vice-versa for case 4), we have:

Because  and  are 1-Lipschitz. Thus,

A symmetric argument works for case 4. So, no matter what,

And we're done, the inf is 1-Lipschitz too.

Cohomogenity:

Crispness: Homogenity and C-additivity are both preserved, so crispness is preserved.

Sharpness:

And we're done.

Proposition 12:

Proposition 13: If a family of infradistributions  has a shared upper bound on the Lipschitz constant, and for all , there is a compact set  that is an -almost support for all , then , defined as , is an infradistribution. Further, for all conditions listed in the table, if all the  fulfill them, then  fulfills the same property.

We'll first verify the infradistribution properties of the infinite inf, and then show it preserves the indicated properties if all components have them.

We must check monotonicity, concavity, normalization, Lipschitzness, and compact almost-support. For monotonicity, if , then

This was done by monotonicity for all components. For concavity,

The first  happened because  and  are concave, the second is because .

For normalization,

And the same argument applies to 0, so the inf is normalized.

For Lipschitzness, let  be your uniform upper bound on the Lipschitz constants of the . Then,

And then, for all the , they only think those functions differ by  or less, and the same property applies to the inf by picking a  and  that very very nearly attain the two minimums, and showing that if the infinimums were  apart, you could have  appreciably undershoot , and in fact, undershoot , which is impossible. Thus,

And we're done.

That just leaves compact almost-support. Fix an arbitary . We know there is some  that is a compact -almost-support for all the . We will show that  is an -almost-support for .

Let  and  agree on . We can go:

Pick a  and  that very very very nearly attain the inf. Then we can approximately reexpress this quantity as:

We're approximately in a case where  and , so we can go:

The end inequalities are because  and  agree on the -almost-support of  and . The two inner inequalities are derived from the assumed inequalities in our case. Thus,

And we're done, we made a compact almost-support for  assuming an arbitrary . So the inf of this family of infradistributions is a infradistribution.

Now to verify homogenity, 1-Lipschitzness, cohomogenity, C-additivity, crispness, and sharpness preservation.

Homogenity:

1-Lipschitzness: Same as the Lipschitz argument, everyone has a Lipschitz constant of 1, so the inf has the same Lipschitz constant.

Cohomogenity:

Crispness: Homogenity and C-additivity are both preserved, so crispness is preserved.

Sharpness:

We do have to check whether or not  is compact, however. We'll start by showing that for an arbitrary , any compact set  where  can't be an -support of  for any . The proof proceeds as follows:

Let  be some point in  but not in . It must be some finite distance away from . Craft a continuous function  supported on  is 1 on  and 0 on . Use the Tietze extension theorem to extend  to all of . Then

However,  and 1 agree on , so  can't be an -almost-support for any .

Thus, in order for there to be a compact set  that's an -almost-support for all , it must be that . Then

because all the  are in it and  is closed. So, the closure of our union is a closed subset of a compact set and thus is compact, so  is minimizing over a compact set and thus is crisp.

Proposition 14: If  and , then the supremum is an infradistribution.

The supremum is defined as:

We'll verify the infradistribution properties of the sup.

We must check monotonicity, concavity, normalization, Lipschitzness, and compact almost-support. For monotonicity, if , then

This was done by  so there's more options available. For concavity,