is the condition \(\eta <\eta_{\text{critical}}\) on the learning rate just so that gradient descent and gradient flow give similar results?

Yeah the no-miss-inclusion property doesn't imply the hulls don't intersect. Think of two perpependicular rectangles which intersect but where the corners are not inside the other rectangle

lol yeah sure

but doesn't it necessarily have to be degenerate when the number of trainnig points is smaller than the number of parameters

wow. what's their train accuracy?

how does their phase diagram look like?

Is that likely given that it's so small that it can't be seen experimentally?

what exactly is the EOC for ReLU?

Right, but it may decrease its mean squared, which is what you are interested in.

Isn't this now assuming large dimensionality of inputs?

Well it seems to me that they just looked at the average over weights. But their basic result is true if you average over any input distribution.You just get the average squared norm of the input multiplying the variances at each layer, but the variance at each layer are still all the same

insert comma here

Unclear what you mean here

This is very nice. We don't need the infinite width assumption to calculate how variances propagate through the network. This is unlike for covariances or higher moments

so the fundamental assumptions is that the weights have a distribution which is symmetric around 0, not just of mean 0

Why is this?

The WANN is an example of meta learning architectures that can be trained with new algorithms

In the discussion they point out a couple of ways the work could be useful or interesting (transfer learning, training techniques beyond gradient-methods), but they don't make many clear points It seems the main point of the paper is to just point out that this is possible, and give food for thought.

Does this mean that erf networks are not fully expressive?

Do you mean the other way round? I thought the experiments in this section were running SGD until it reaches a small fixed loss value, like you say in Figure 5.

EDIT: Ah I see you repeat this in the end. Make sure you mention that you state that the experiments in Section 3.2 are for a fixed number of epochs.

The fact that you need to train for a fixed number of epochs is interesting. Perhaps, the self-similarity among different minima occurs within a "layer" of weight space corresponding to weights of a given norm, and different layers are related by rescaling also (see section about flatness vs epochs, assuming norm increases with epochs). But if you train to a fixed loss, i guess the norm/layer needed to reach that loss is different for different data/functions, so that's why the correlation vanishes?

as in the rest of the paper?

I think in the plots where you talk about flatness, the flatness axis should be -log(prod lambda), so that larger values correspond to higher flatness

what do you mean? flatness could increase by the same amounts, whether the lambda_max correlated with flatness or not, no? The two phenomena could be related though

The gradient here just indicates that larger flatness increases in flatness more right? It's the y-intercept that is showing here that the flatness increases after 100 epochs

I suppose because the function stops changing? Is this training on part of the inputs, rather than on all the inputs? If the latter is the case, it's trivial that, if the algorithm converges, it will not change the function it finds after enough epochs.

I thought the network was 7-40-40-1

This makes it seem to me like you corrupted a fraction of S_train, rather than appending an S_attack? We don't want that as then we are not fitting the same-sized (uncorrupted) training set.

You'll have to explain to me (and the reader) what precisely you did. What are each of the points in Figure 15? A different training set, the same training set?

Previously you said 512 examples. Which one is it?

pixels in the images of size 28x28

To be clear, S_train is fixed in size, but S_attack varies in size right? It's not S_train + S_attack that's fixed in size. You should make this clear, because both approaches have been used, but in this case, we want S_train to be fixed.

\(\alpha>1\) increases the norm and \(\alpha<1\) decreases it, it seems. I guess this is because in the former case, we are increasing more parameters than we are decreasing it, and viceversa in the latter case.

On the other hand, both increase the sharpness. This shows that sharpness and norm don't necessarily follow each other. However, it may be that for solutions that SGD finds, sharpness and norm do correlate. [ this is in a similar spirit to the alpha scaling rebuttal; while there are sharp regions with large and small norm, perhaps constrained to SGD-typical regions, the two quantities correlate. We could check this ]

what are you referring to here?

and standard optimization algorithms

well, we don't know if the flattest, but definitely flatter than alpha-scaled ones

the question here is: "if minima corresponding to the same function (which thus generalize identically) can have arbitrarily different flatnesses, how can flatness be used as a proxy for generalization?

where \(\alpha>0\)

as long as it is twice differentiable, so that the Hessian is defined

rather than "redundant", "have limitations", or "are inappropriate"?

in the sample

self-similarity is a better term, as it's more commonly used, specially in cases, where the similarity at different isn't exact

what complications?

How is this? I would have expected behavior to be symmetric under changing outputs 0 to outputs 1 (think of changing sign of last layer)

enough to reach global minimum / target function?

I would define the x axis as "sharpness", or if you want to call it flatness, make it negative. A minimum with larger -log(lambda) is more flat right?

this is expected because

This is the MDL argument right?

here we are assuming that the loss measures discrepancy on all input points, so that zero loss is only achieved by functions equal to the target function.

and can provide rigorous bounds in some cases via PAC-Bayes theory

the bound is always obeyed, but it is only tight if there is enough bias.

In other words, one only obtains simplicity bias (simple functions being more likely) if there is bias to begin with.

also, the MDL principle based on flatness doesn't provide nonvacuous bounds [lecun et al], except on few recent exceptions [dan roy et al]

Why?

how does this gamma term evolve?

Think of each step of Brownian motion as integrating many mini steps of SGD.

This is reminiscent of CLT

Only when the learning rate is very small

No bias towards complexity

How does this definition of the kernel as an integral operator fit in the rest of the story as a kernel of a Gaussian process? I thought a Gaussian process doesn't define an input over functions?

why does the larger step size cause more stability?

you haven't defined \(\Delta\) in the statement of the theorem

because it is not a polynomial

Why?? The operator norm of a random Gaussian matrix goes like \(O(\sqrt{n})\) ? (see https://terrytao.wordpress.com/2010/01/09/254a-notes-3-the-operator-norm-of-a-random-matrix/ e.g.)

Do they substitute \(a^{(k)}\) and \(w^{(k)}\) with \(A(t)\)? That is a valid bound, but seems quite loose. But it doesn't seem to be what they are saying. Substituting the LHS by RHS on Q, doesn't guarantee we obtain a polynomial on A(t) ?

should be \(Id_{n_0}\)

This is an extension of the definition of <>_pin to allow for vector-valued functions living in spaces of different dimensionality, in which case we take the outer product I think

An in fact SGD seems to work better in terms of both convergence, and generalization, in practice. Can we explain that theoretically?

As this has \(p\) columns, I'm assuming they only consider a stride of \(1\), for the convolutional networks (probably easy to generalize regardless)

\(\lambda_0\) is \(\lambda_\text{min}(H)\) I suppose

-extra word-

depends on

The rate of convergence is going to be very slow though for big \(n\), because the learning rate is very small

Is this guaranteed to be \(<1\)? Otherwise, the inequality couldn't be right.

Seems like this being less than \(1\) depends on what \(\lambda_{\text{min}}(\mathbf{K^{(H)}})\) is

Hmm, should this be \(\mathbf{A}_{ij}^{(H-1)}\)?

I think so. See page 40 for example.

These are the standard Neural Network Gaussian Process kernels I think

But, like for NTK paper, step size is effectively very small, because of using NTK parametrization. Except that because \(m\), is at least a finite step size :P

Should be \(\mathcal{E}_1\)?

Really? That sounds like a big difference with practice..

How does this compare to the unified treatment of Greg Yang?

They do, for a positive definite kernel right?

Technically we've shown that the variation in \(\alpha\) is \(O(1/\sqrt{n_L})\), but not the derivative? I think however, one can express the variation in the NTK as a sum over variations of alpha (by using the arguments here, and then integrating in time), giving us the desired result that the variation of the NTK goes to zero as \(O(1/\sqrt{n_L})\)

should be \(\mathbb{R}^{n_{l+1} \times n_l}\) I think?

Uses Cauchy-Schwartz for Operator norm of matrices, which can be obtained easily from definition

Why does it stay uniformly bounded on \([0,\tau]\) and not on \([0,T]\) ?

Which theorem are they applying from reference [6], Thm 4?

Each of the derivatives has a factor of \(\frac{1}{\sqrt{n_{L}}}\), plus we get an extra factor of \(\frac{1}{\sqrt{n_{L}}}\) from the derivative of \(\alpha_{i}^{(L)}\)

For the 2-norm, at least?

pre-activations?

as Frobenius norm bounds spectral norm (which is the same as operator norm for matrices)

Under the NTK parametrization, which they use, this limit implies that the learning rate (for GD on the standard-parametrization) is \(O(1/\sqrt{n}\) (where \(n\) is layer size). So the parameters move less and less for a fixed \(T\), in this limit, which is, intuitively, why the NTK stays constant for this period of time until \(T\)

The interesting thing is that the function \(f\) can change, as all the parameters "conspire" for it to change. Therefore it can potentially fit a function, and find a global minimum, while the parameters have almost not moved at all.

I think the intuition for this "conspiracy" is that the total change in \(f\) is given by a sum over all the parameters' individual gradients. The number of parameters grows like \(n^2\). gradient w.r.t. last hidden layer activations is \(O(1/\sqrt{n})\), w.r.t to second to last hidden layer activations is \(O(\sqrt{n}(1/\sqrt{n})^2) = O(1/\sqrt{n})\), where the \(\sqrt{n}\) comes from variance of summing over all the activations in last hidden layer. This means that the gradient w.r.t. to a weight, in NTK parameterization, is \(O((1/\sqrt{n})^2)=O(1/n)\) In GD, each weight changes by an ammount of the same order as the gradient (assumin \(O(1)\) learning rate, which we assume for NTK-parametrization learning rate), so each weight contributes to change \(f\) by \(O(1/n^2)\). Therefore the total contribution from all the weights is \(O(1)\). Note that the contributions all have the same sign as they are essentially the gradient w.r.t. that weight, squared, so they add linearly, (and not growing like \(\sqrt{n}\) if they were all randomly signed)

i guess the first product here is element-wise, although it's not explicitly said

From chain rule

huh? no \(1/\sqrt{n}\) ?

:O we studied the same object in our paper! But we called it the parameter-function map!

https://arxiv.org/abs/1805.08522

But early stopping doesn't seem to often help in ANN training

https://arxiv.org/abs/1805.08522

If high dimensionality is the reason, then why does the high dimensional linear model work so well?

Not always. If you scale all parameters of a ReLU network with biases, it changes the function. If biases are zero, it doesn't change the function.

It's true that batch-norm makes networks independent of parameter scaling, for the layer immediately before a batch norm layer.

This feels like it may be true for nonlinearities like tanh, but not sure if it will be for relu.

For ReLU, larger parameters increase the gradient of the outputs w.r.t. to parameters in lower layers. Exponentially in the number of layers! This is what allows the lazy regime (see literature on NTK / lazy training etc)

This is interesting in that it shows that "overparametrization" is not enought to get models that generalize well. Neural networks must have special properties beyond being overparametrized

YES. That's what we say too: http://guillefix.me/nnbias/

This is a very loose statement. They could be a set of very little measure that is just rather dense in the space. So yeah they could be "everywhere", but be very rare and hard to find, unless you are beeing trained to find them explicitly

I could only get

\(\mathbf{P}(|M x| \geq \sqrt{An}) \leq C^n \exp (-c A n)\)

Applying Markov inequality :P Did I do anything wrong?

citation 35 and 6 are the same citation (one in the conference, and one in arxiv). I think they should be merged.

square root of width?

Yeah but the NTK parametrization makes the gradients much smaller. For normal parametrization, gradient of individual weights is not infinitesimal right?

\(d\) is the input dimension. But also the number of parameters, because we are looking at a linear model here.

Noise model. Information space is the component of the inputs that live in a low-dim space (low rank component), and the nuisance space is the component that corresponds to i.i.d. noise, which will w.h.p. be of maximum rank

Wait, so it seems that in all the experiments with CNNs you just found that the lazy training didn't converge to a global minimum of training error. So it doesn't mean they aren't generalizing well!

Is your Jacobian degenerate for the first set of experiments (with squared loss), because if not, then your theorem implies that they should converge to a global minimum right?

zero training loss is achieved both in the lazy and non-lazy regime, but the non-lazy solution generalizes much better

I suppose that in both the lazy and non-lazy regime, it has reached a global minimum of training loss?

Convergence to local minimum, removing assumption about non-degeneracy of Jacobian

In terms of convergence results, this paper's main new result is the convergence of gradient flow, and showing that it stays close to the tangent (linearized) gradient flow.

And saying this for general parametrized models. The assumption of nondegenerate Jacobian is related to over-parametrization, as nondegeneracy is more likely when one is overparametrized.

size of step size for gradient flow to be a good approximation

How come it can find a minimum arbitrarily close to the initialization?

Ah I see by the non-degenerate Jacobian assumption, you can find a local change that will fit \(y^*\), and \(\alpha\) large is just needed to reach the overall size/scale of \(y^*\) with the local change

How realistic is this?

why do we need them to be square-integrable?

and the learning rate tending to zero..

Remember this nabla is w.r.t. to its argument not parameters \(w\)

Seems quite artificial, but ok

is this if the weights are tied only? Do they assume they are tied?

perhaps large initialization is like a small L2 norm bias, and small initialization like an L1 norm bias. So the kernel regime is bad for learning sparse networks (I think Lee also says this in his talk)

they showed that for GD and logistic regression, but what about SGD, and square loss? I think for square loss you need either early stopping or regularization to get min norm solution?

are all our base belong to us?

the kernel distance?

Only its expected value, see page 7 in Jacot2018, if I understood correctly

The fact that most naive learning algorithms work well, makes me question the "crucial" qualifier..

typo on above equation? this appears to be the same as the Schrodinger equation

This is the expected value of the kernel, not the actual kernel, which would correspond to a random features kernel right?

Hmm I think I remember random features converging when their number grows to infinity, but the product \(f(\theta,x)f(\theta,x')\) doesn't stochastically converge when the width grows to infinity right? Only its expectation converges

Maybe, but these kernels also correspond to those of a fully trained ideal Bayesian neural network, with prior over weights given by the iid initialization

philosology does affect you as well though...

If the optimum of (2) is given by this when function is unrestricted, if we consider a family with zero "approximation error" (so that the optimum is in the family), then the optimum on the family is the same as over all functions

Why are previous meta-RL algorithms typically on-policy?

I see this as one of the main innovations of the paper. This term is a discrepancy between the sample, and the true distribution \(\mu\). This would allow Z_m to be sampled from a different distribution for instance, allowing to get bounds that account for distributional drift, for instance.

This basically offers a measure of the variance of the loss (in a non-statistical sense) over the instance space, of the learned function.

Sure, but that is also avoided in some statistial learning approaches, like Structural Risk Minimization, PAC-Bayes, and the luckiness framework, which you cite!

smaller?

So if I understand correctly, with a single head, different parts of the d_model-dimensional query vector may "want" to attend to different parts of the key, but because the weight of the values is computed by summing over all elements in the dot product, it would just average these local weights. Sepparating into different heads, allows to attend to different value vectors for different "reasons".

log probability

~~

for Kmax

in relative terms

given the map \(f\)

first give x, and then enumerate ... identifying all inputs p mapping to x, namely \(f^{-1}(x)\)

is the main component in

:

of

for binary strings

suggested

Perhaps say "This suggests that, even though many maps are not UTMs, the principle that low K are high P should hold widely"

because it is not because they are not UTMs, but it is in spite of them not being UTMs, I would argue.

in parenthesis

should be \(k(y,x,y',x')\) right?

Remember that kernel functions with one of its arguments evaluated are members of the reproducing kernel Hilbert space to which all the functions supported by a particular Gaussian process belong.

Therefore adding kernels, amounts to adding the functions on these two spaces. That is why the resulting functions work like this when combining kernels!

Actually it's convex

Remember that the w sampled from the "posterior" isn't necessarely parallel to the original w, so that the stochastic classification rate isn't simply F(sign(margin)) but something more complicated; see the proof.

Oh, c'mon :PP You are just showing that PAC-Bayes is tight as a statement for all Q and for a particular P. As in you are saying that if we only let it depend on the quantities it can depend (namely KL divergence between Q and P, delta, etc), then it can't be made tighter, because then it would break for the particular choice of D, hypothesis class, Q, and for any value of KL in that case in the Theorem 4.4 above.

--> What I mean is this: that we say the bound is a function f(KL, delta, m, etc). Theorem 4.4 shows that there is a choice of learning problem and algorithm such that these arguments could be anything, and the bound is tight. Therefore, we can't lower this bound without it failing. It is tight in that sense. However, it may not be tight if we allow the bound to depend on other quantities!

Yeah, as in if it only depends on \(P(c)\) and the other quantities expressed there, and have it not depend on the algorithm, so it should be a general function that takes \(P(c)\), \(\delta\) etc, but the same function for any algorithm. Then yes. And this is what they mean here.

Depends what do you mean by For all \P(c)) are you fixing the hypothesis class or what? Because your proof assumes a particular type of hypothesis class... For P(c) having support over a hypothesis class where the union bound doesn't hold, then it is not tight any more..

Ok, so this has proven that the Occam bound is tight for this particular \(D\) for this particular hypothesis class, which is quite special, because it has the property that the union bound becomes tight. But that is a very special property of this hypothesis class (or more general, of this choice of support for \(P\) right??)

this is because having "too-small train error" here means (is equivalent to) having train error smaller than \(k\), so that the classifier with smallest train error also has it smaller than \(k\) and therefore it also has too small train error.

If we observe a zero empirical error, then the probability of observing that decreases very quickly with increasing true error. So I wouldn't really say it's the decrease in variance of the binomial (one could imagine distributions where the variance doesn't decrease as you go to 0, but which still have the property that makes the realizable case error rate smaller in the same way as here)

Remember they define training error as error count

Btw, this approach only works because \(c_D\) is a one dimensional random variable, so that {the set of \(k\) such that \(Bin(m,k,p)<\delta\)} equals {the set of \(k\) less than or equal to {the maximum \(k\) such that \(Bin(m,k,p)<\delta\)}}.

This happens because the different ("confidence interval") set of \(k\) defining \(Bin(m,k,p)\) (i.e. all \(k\) smaller than or equal to some \(k\)) are all nested. In more general situations with other confidence intervals defined (like for 2D cumulative distributions) this may not happen.

No,

Because Lemma 3.6 requires \(\frac{k}{m}<p\), then we need \(\delta\) to be small enough such that {{the \(c_D\) that results from solving the Chernoff bound = \(\delta\)} be larger than \(\frac{k}{m}\)}</p>

\(c_D\)

And any tighter bound would be violated a larger portion of the time, at least for some value of the true error (note that for fixed or constrained true error one can have tighter bounds).

The need for a sufficiently large true error is because for instance for true error zero, the bound is never violated.

But still the fact of it being perfectly tight is because of what I said above.

less

So not Bayesian statistics

so the EP approximation to the marginal likelihood?

how is the EP approximation good when the probit function as likelihood is shaped so differently from the unormalized Gaussian which is used to approximatie it!?

Adversarial training as an alternative to maximum likelihood training!

You'd need to sum over all \(y\) for that?

Ehm, in the line below you have \(q_\phi(z|y,z)\) not \(q_\phi(z|x)\)

In principle, just like for consistency, they could choose not to enforce permutation invariance (e.g. using just an RNN), and rely on the model learning it from data.

However, the contributions they are making (here and in the Neural Processes paper) is ways of putting the structure that Bayesian inference on stochastic processes should satisfy explicitly on the model, so that it has to learn well.

We are putting prior knowledge about how to use prior knowledge

I think in the context of CNPs consistency would imply things like

\(\sum_{y_1} p(y_1)p(y_2|y_1) =p_2\)

These things are not automatically guaranteed by the framework used here. The data should constrain the network to satisfy these approximately

So, the nice thing about NPs is that if you did the inference of \(z\) exactly it would be a stochastic process exactly (unlike CNPs that don't have a simple interpretation/approach that guarantees being an exact stochastic process). However, because of not doing the inference of \(z\) exactly, consistency of the resulting marginal distributions is not exactly guaranteed.

or even stochastic processes that aren't GPs and may not be describable by kernels

?? For GPs with Gaussian likelihood the functions don't pass exactly through the observation points, just near, as in here?

I think he meant \(h^{j_1},...,h^{j_k}\)

So we sample the A transposes independently from the As I see. That is the gradient independence assumption.

Btw is this related to some stuff I saw Hinton spoke about showing that you could do backprop with weights different from the forward prop, and they couldn't understand why. Is this the explanation? Could this, as they suggested, be related to a way the brain could be doing backprop?

"upon sampling of the first layer parameters" or "sampling the first layer parameters", I guess he meant?

oh ok , he kinda means sampling of the last layer parameters, but when we do backprop, it's the first layer..

Ah ok, the \(v^i\) are like the weights of the outputs in the loss function

NO. each \(v_i\) is a vector, the vector of weights which when multiplied by some \(\mathtt{g}\) or \(\mathtt{h}\) give a single real-valued output labelled \(i\). This we call a linear readout layer.

When we back propagate the loss we would multiply each of these vectors by the derivative of the loss w.r.t. to each of these outputs.

Can this be done in this formalism?

so that the \(\mathtt{f^l}\) are not polynomially bounded

again should be \(a_{j_i}^l\)

don't need \(m\) here?

Note that the Nonlin functions in the appended lines are allowed to depend on the previous \(\mathtt{g}\)s, which is necessary to compute the backpropagation of the gradient through the nonlinearity. The odness works for backprop because the Nonlin is just linear w.r.t. the \(v\)s

Generalized law of large numbers extended to a case where the i.i.d. r.v.s have a distribution that changes as we increase the number of samples (although the way it changes is constrained).

EDIT: see comment

The reason this is nontrivial is that the \(\phi(g_i^{\frak{c}t})\) have a distribution that changes with \(t\), although it approaches a limit. So it is different from the standard law of large numbers.

In words, here we are saying that the empirical averages as we increase \(t\) approach (almost surely) the expected value of \(Z\) distributed according to the limit distribution of \(\phi(g_i^{\frak{c}t})\)

the \(L\) at which exponential effect kicks increases like \(\sqrt{n}\) it seems according to these arguments. Nice

seems related to things in here http://papers.nips.cc/paper/7339-which-neural-net-architectures-give-rise-to-exploding-and-vanishing-gradients

\(\mu^\frak{c}\) is the vector of means of the tuple of \(i\)th components of the vectors in the argument of either \(\mathtt{f}^a\) or \(\mathtt{f}^b\), and \(K^\frac{c}\) is the covariance matrix of this tuple/vector.

Note (also useful for the above definition) that we are defining means and covariances for any individual component of the vectors \(\mathtt{g}\). That is, we are describing the distribution of \(\mathtt{g}^{\frak{c}}_i=(\mathtt{g}^l_i)_{g^l\in\frak{c}}\) for any \(i\). Different tuples of components are independently distributed, as explained in a comment in the beggining of the Setup section above

This is defined for \(g^l \in \frak{c}\)

This is defined for \(g^l, g^m \in \frak{c}\)

should be \(a^l_{j_i}\)

Note the subscript \(i\), so this is the distribution for the tuple of the \(i\)th components of all the Invecs in \(\frac{c}\).

We therefore allow the \(i\)th component of two different Invecs to be correlated (useful to model the distribution of the first hidden layer, as per the usual NNGP analysis). But we don't allow different components of Invecs, \(g_i^{lt}\) and \(g_j^{mt}\) for \(i\neq j\), to be correlated.

Thre is a typo, it should say for each \(i\).

what does this mean? Ah \(t\) is like a "time", so it is the index of the sequence. \(lt\) just represents two indices (not their product!)

Why?? Do you show that all functions that have the property of being insensitive to large changes in the inputs have high probability? If so, then say it, if not. Then not all such functions need be simple w.r.t. to all measures of complexity that are found to correlate with probability for a random NN

Dingle et al explore bias towards low complexity, but not the relation to generalization.

Although I think it is exponentially small in \(n\), why is that implied by your result? All that you know from what we've been told up to this point in the paper, is that it's probability has to be smaller than sqrt(log(n)/n), or using symmetry, we can divide this by 1/n

for \(n>> 1\), the probability of all of the Hamming-distance-1 neighbours giving the same result goes to 0. So the weight of the term corresponding to Hamming distance 1 goes to 1, in the average

Approximately a geometric distribution with success probability p=2, for large \(n\), and the mean of a geometric distribution is 1/p = 2

This is a Schmitt trigger :D, see here: https://youtu.be/Iu21laCEsVs?t=2m31s

How is this inspired by the method of Lagrange Multipliers?

This is not \(\delta u_k\), why is he using \(u_k\) ? I don't see what's the justification

What do they mean by "learning algorithms via constant fitting"?

Hyperparameter I guess