Well, if it is regularized (so there is an effective prior), then this isn't true!

Yeah. But not on the original networks, but on the compressed ones!

This is a 0-1 loss. It can be applied to top-1 or top-5 defining the loss appropriately!

this is far from SOTA. right?

Ok, that is non-vacuous, but just, right?

But remember that the compression scheme technically shouldn't depend on the data, for the bound to be valid (as the PAC-Bayes prior depends on the compression scheme)

On the training error, or the test error?

wow, they are very weight-compressible indeed

Independence increases concentration

You are normalizing the log not the distribution here!

Exp missing

It is minus this!

These are the sizes of the codes for encoding the vector of weight indices and discretized weight values, according to coding scheme \(c\)

isn't \(2^{64}\ bytes \(2^{67}\) bits, as each byte is \(2^3\) bits?

Bound on KL divergence for Universal prior, and point posterior

By Kraft inequality, and \(m\) being a probability measure

An important question is: are the bounds valid for the compressed network, or for the original one as well? (as isn't the case in the related work: https://arxiv.org/abs/1802.05296 )

Well. If this is the case it means that proving a generalization bound for one of these procedures "implies" a bound for the standard training procedure, as you are claiming that the standard one generalizes not (much) worse than these ones

To understand phenomenon described by Saxe and in the video at 43:00, we can think of this: Low eigenvalues in XX^T correspond to directions with little variations in the input. However, by the random fluctuation eta, the output could have an O(1) variation, even for arbitrarily small input variation, which requires a large weight to fit, and produces large generalization error.

for $\alpha<1$ the probability of this directions in input space with low variation decreases, as we get less directions overall with points I think (directions with no points/variation are ignored for the algorithm which projects weight into input subspace, and these are the 0 eigenvalue parts of the Marchenko-Pastur distr)

why does interacting weakly cause high sharpnes??

I think the reason is that for layers which interact strongly random perturbations tend to cause smaller relative change on the output, than for layers that interact strongly. And this smaller relative change on outputs probably translates into a smaller absolute change in the Loss...

think about aligned eigenvectors and stuff

Aren't VC dim bounds for NNs linear in depth also?

This is what's done in Wu et al https://arxiv.org/abs/1706.10239 also

For a fixed expected sharpness the KL (and thus the effective capacity/bound) increases less for true labels than for random lables. Also, in both cases, it increases monotonically

This is the "curse of dimensionality"!

Probably can prove using covering numbers which bound RadComp (via Massart's lemma)

but are the generalization error bounds for Lipschitz functions tight?

Unless inputs lie on a slow dimensional manifold I guess

This has been used in several papers on generalization bounds for neural nets.

I think the idea is like that for margin bounds for SVMs. You can't bound the RadComp using the 0-1 loss as it's Lipschitz (related to above arguments). But you can bound the Hinge loss (which is related to having a margin!), and then use the fact that the Hinge loss upper bounds the 0-1 loss.

The intuition I guess is that the previous troublesome cases with norm-based capacity can be solved by taking margin into account, as the extremes in both cases are reducing/increasing the margin (for weights going to zero/infinity).

This comes from the Rademacher complexity of the neural network. See here: http://www.stats.ox.ac.uk/~rebeschi/teaching/AFoL/18/material/lecture3.pdf#page=4 for a derivation

They just state this, but they should maybe cite some work on nonuniform learnability, SRM, MDL, so that people unfamiliar with it can see why this is!

These are all SRM based.

They depend (most often implicitly via the training data) on the data-distribution/target function, and the algorithm (also implicitely) If you get a good bound with SRM it's most likely because your algorithm is biased towards the right kind of solution (kind basically corresponds to the classes used in SRM). In other words, a bad algorithm (relative to target fun) will be very unlikely to produce a good bound. On the other hand, a good algorithm may produce a bad bound, if the prior is chosen badly. So that SRM bounds may not be tight in general

typo \(\theta\) shouldn't be here

is

I don't think the \(+1\) is actually necessary

Remember: larger metric correspond to smaller rulers

there

5.3

shouldn't there be a \(\lambda\) here too?

And in fact another \(\lambda\) from Rad(A_1)?

this should be \(\leq\),

thought I would have used \(\mathcal{L} \cup -\mathcal{L}\) instead

appostrophe shouldn't be there

hull

missing parenthesis

$$j$$

\(\leq\)

? How does this define what \(\rho\) is?

typo

less

distribution

I don't get this formula. What are C_i and C_j supposed to mean. Or rather, where is the randomness over which we average?

Well, what is nontrivial about this is generalizing (as usual), how do you generate novel samples, what are samples that "look like" the rest of the data. How do you define that?

Well, you are attempting to define it as "the alignment given by the lowest complexity meme".

I think this doesn't address the question, which is more generally addressed to the whole field of cross-domain mapping, I think. Why aren't the new neural network approaches compared with previous approaches of unlabelled cross-domain mapping, which can be formalized as different forms of alignment between sets of points. I think the main difference here is that in those approaches you typically know the whole target domain, while here we don't quite know it, we just have a few samples from it, but I feel this is a surmontable problem

The minus is because we are translating the world in the opposite way that the camera was translated to get it right relative to the camera, while putting the camera at the origin. The R^-1 is because we first rotate by R and then translate by T, so to get the original translation vector we need to undo the rotation to T

It is multiplied by the z component of the point because we want to translate by a fixed amount in the u-v plane. However, after being acted by the camera matrix, they are in homogeneous coordinates, scaled by the z component!

Why??

I see, I think the derivative wrt \(\theta\) here is supposed to be while z satisfies the constraints in (32)...

But it has whatever restriction being an ODE imposses. How does the expressivity and learnability of the ODEnet compare with ResNets?

Can you not just compute the gradient for each input, and average them?

typo?

This second term comes from the fact that we want the probability of observations at times \(t_1, ..., t_N\), and at no other time between \(t_{start}\) and \(t_{end}\)

corresponding to weight matrices of rank 1

This is just the differential form of the continuity equation

What are the residual blocks precisely? Single layer + ReLU?

Adaptive computation time

\(\theta(t)\)

1:00:00 scale separation as a way to go beyond Markov (local interactions) assumption

~32:00 What about the domain of the function being effectively lower dimensional, rather than a strongly regularity assumption? That would also work, right? Could this be the case for images? (what's the dimensionality of the manifold of natural images?)

Nice. I like the idea of regularity <> low dimensional representation. I guess by that general definition, the above is a form of regularity..

He comments about this on 38:30

it should be +? This typo carries through to later parts

This works because the marginal variance is independent of the orientation of the input vector. This can be proven by noting that a random Gaussian matrix doesn't change its distribution when rotated by an orthonormal similarity matrix..

Why is this the variational loss???

Cool idea!

Not true (for finite width nets) I think. the terms are conditionally independent, when conditioned on the value of the final hidden layer. If we consider the joint distribution over all the weights over all layers, then the terms won't be independent. However, in the limit of infinite widths, they do become independent. This is because their covariance is \(0\) and in the infinite width limit, they become Gaussian with that 0 covariance, and therefore independent.

Remember also that this is for a fixed input (and later analysis is for a finite collection of inputs)

is this concentration phenomenon related to the asymptotic equipartition properties of large collections of independent (or weakly dependent) variables?

this means the functional inverse

this should be the other phi?

What are semantic consequences? Is there such a thing as syntactic consequences? Is the statement said here different for them? I don't think so right?

subsets are defined as properties in Logic. Second-order logic goes above first-order logic by being able to quantify over properties (and thus over subsets)

I would say more that it determines the appearance of correlations between the elements of Y.

Also, this isn't quite the covariance matrix, unless the mean of Y is zero?

Reason why evolutionary methods are useful in RL, but not so much in SL. What about UL?

Is this what they mean https://en.wikipedia.org/wiki/Random_search ?

No training on singular directions.

However, it seems like sloppy directions. Those with small eigenvalue in input correlation matrix causes overfitting. This is because in these direction there is small variability on the inputs, and yet there is variability on the output due to noise. To fit the small variability, we learn large weights, which are in fact too large, and don't generalize well..

See here. This is the cross-entropy between the likelihood for $\theta$, $q(X|\theta)$, and $q(X|\theta_0)$. It is the same as the disorder-averaged energy of state $\theta$, that is averaged over $X$. Note that because the energy is a mean over $x$, and each $x$ is independent, then for the disorder-averaged energy, we can just calculate the average for one $X$.

If we evaluate this at $\theta=\theta_0$, then we have the Shannon entropy of $q(X|\theta_0$. $\theta_0$ is the disorderd-averaged ground state (it's not hard to see that it is the $\theta$ which minimizes $H(\theta;\theta_0), this is just a property of cross-entropy).

The other one is the empirical version of this.

This is equal to

$$\int_\Theta d\theta \bar{\omega}(\theta)\prod_{X\in x^N}q(X|\theta)$$

which is just the probability of observing the samples $x^N$.

But the interesting thing is that it can be written as a partition function where $\theta$ is the physical state vector as said after.

What is this?