Beyond automatic differentiation • Hacker News Board

Re: Beyond automatic differentiation

#21

Post by bollu » Fri, Apr 14, 2023, 6:10 PM UTC

nyrikki wrote: post #10

abeppu wrote: post #7

My main question is whether this is still helpful in an SGD context? I.e. if you have $f = \sum_i^n f_i$ and with every batch you make $f_S = \sum_{j\in S} f_j$ for that batch ... being able to take a step which definitely causes $f_S$ to decrease doesn't necessarily cause $f$ to decrease / the window for $f_S$ may be different than the window for $f$? If it only really makes sense for cases where you can evaluate th…

The newton method has the nasty Wada property arise, which is often glossed over as being the same as scale invariant noise in class but which is better thought of as a topological feature rather than scale invariant noise. It is indecomposable continua and not the imperfect knowledge of initial conditions like chaotic systems often invoke. Boundary conditions becoming indeterminate is a problem with 3 or more attrac…

Could you provide a link to some more reading about this? i do not know what a wada property is, nor why it is topological

Re: Beyond automatic differentiation

#22

Post by ftxbro » Fri, Apr 14, 2023, 6:11 PM UTC

ogogmad wrote: post #19

ftxbro wrote: post #9

I'm interested what fdej thinks about this one. arb has recently been merged with flint under his maintainership and is getting some generic rings wrapper and more interfaces with other languages. But maybe its focus is more like algebraic things like modular forms and less like tensor libraries for machine learning and GPGPU. https://news.ycombinator.com/user?id=fdej https://news.ycombinator.com/item?id=26054520 htt…

I've just looked at the documentation for eigenvalues and eigenvectors in arblib. I was thinking that: - Eigenvectors are not computable in regions surrounding eigenvalue clashes. Therefore you should never compute them. - Let M be a symmetric matrix being eigen-decomposed. The decomposition should be A = P D P^(-1) where only D is interval-valued, and P and P^(-1) are NOT UNDER ANY CIRCUMSTANCE INTERVAL-VALUED , and…

I see what you mean, but say you have such a matrix and there are two eigenvalues that you can't separate from each other. Then wouldn't their corresponding eigenvectors define like a 2d plane? Couldn't there still be some interval for that plane, like say that the plane is defined by the linear combination of two vectors and both vectors have zero on some coordinate, say the x coordinate. The interval could still be helpful by saying that any combination will also be zero there, right?

Re: Beyond automatic differentiation

#23

Post by cs702 » Fri, Apr 14, 2023, 6:51 PM UTC

GaggiX wrote: post #12

cs702 wrote: post #2

Interesting, but I have questions. The OP shows how SafeRate improves plain-vanilla Adam, but almost no one uses that anymore. The most commonly used optimizer nowadays is probably AdamW. Does SafeRate improve AdamW to the same extent, or at all? How does using SafeRate compare with Bayesian hyperparameter search? How does it compare with rule-of-thumb hyperparameter selection methods? Many people seem to get a lot o…

It improves Adam in the full-batch setting, which is not usually done or desired since minibatch should regularize and improve the loss.

Ah yes, that too. I forgot to point it out. Thanks!

Re: Beyond automatic differentiation

#24

Post by nyrikki » Fri, Apr 14, 2023, 7:00 PM UTC

bollu wrote: post #21

nyrikki wrote: post #10

Earlier quoted context omitted.

The newton method has the nasty Wada property arise, which is often glossed over as being the same as scale invariant noise in class but which is better thought of as a topological feature rather than scale invariant noise. It is indecomposable continua and not the imperfect knowledge of initial conditions like chaotic systems often invoke. Boundary conditions becoming indeterminate is a problem with 3 or more attrac…

Could you provide a link to some more reading about this? i do not know what a wada property is, nor why it is topological

The Wada property is when you have 3+ disjoint sets that share the same boundary set, at least for the complete Wada property.

In Newton's fractal, any circle you draw will either have a single root or all roots, no matter how small you draw that circle. If your initial conditions are near that boundary the exit basin you take is indeterminate because that point wise boundary point is the boundary of multiple exit basins and isn't simply connected.

This differs from other scale invariant features like self similar fractal scattering which will have similar 'noise'at different scales but is somewhat deterministic if treated like noise as an example.

The Wada property arises in several places like Hamilton systems, delayed partials and predator prey with food and refuge.

If you look for papers on light exiting binary black holes there are some good papers.

This page may help, but the Wada property is counter intuitive.

https://users.math.yale.edu/public_html/People/frame/Fractal...

Re: Beyond automatic differentiation

#25

Post by DougBTX » Fri, Apr 14, 2023, 7:10 PM UTC

GaggiX wrote: post #12

cs702 wrote: post #2

Interesting, but I have questions. The OP shows how SafeRate improves plain-vanilla Adam, but almost no one uses that anymore. The most commonly used optimizer nowadays is probably AdamW. Does SafeRate improve AdamW to the same extent, or at all? How does using SafeRate compare with Bayesian hyperparameter search? How does it compare with rule-of-thumb hyperparameter selection methods? Many people seem to get a lot o…

It improves Adam in the full-batch setting, which is not usually done or desired since minibatch should regularize and improve the loss.

Batch size can be used for regularisation, but using it for that will limit training performance. From the Google Research Tuning Playbook:

> The batch size governs the training speed and shouldn't be used to directly tune the validation set performance. Often, the ideal batch size will be the largest batch size supported by the available hardware.

> […]

> As long as all hyperparameters are well-tuned (especially the learning rate and regularization hyperparameters) and the number of training steps is sufficient, the same final performance should be attainable using any batch size (see Shallue et al. 2018).

https://github.com/google-research/tuning_playbook#choosing-...

The ideal case is full-batch with tuneable regularisation, just the hardware gets expensive.

Re: Beyond automatic differentiation

#26

Post by ogogmad » Fri, Apr 14, 2023, 7:28 PM UTC

ftxbro wrote: post #22

ogogmad wrote: post #19

Earlier quoted context omitted.

I've just looked at the documentation for eigenvalues and eigenvectors in arblib. I was thinking that: - Eigenvectors are not computable in regions surrounding eigenvalue clashes. Therefore you should never compute them. - Let M be a symmetric matrix being eigen-decomposed. The decomposition should be A = P D P^(-1) where only D is interval-valued, and P and P^(-1) are NOT UNDER ANY CIRCUMSTANCE INTERVAL-VALUED , and…

I see what you mean, but say you have such a matrix and there are two eigenvalues that you can't separate from each other. Then wouldn't their corresponding eigenvectors define like a 2d plane? Couldn't there still be some interval for that plane, like say that the plane is defined by the linear combination of two vectors and both vectors have zero on some coordinate, say the x coordinate. The interval could still be…

That makes sense, but what can be done with it?

Re: Beyond automatic differentiation

#27

Post by 6gvONxR4sf7o » Fri, Apr 14, 2023, 7:41 PM UTC

modeless wrote: post #11

> We can use a similar idea to take an existing optimizer such as Adam and convert it to a hyperparameter-free optimizer that is guaranteed to monotonically reduce the loss (in the full-batch setting). I'm not a huge fan of analyses like this that make one huge assumption that never holds in practice. Nobody uses full-batch gradient descent. It's not possible in practice or even desirable in theory. The stochasticity…

So what? This isn't some kind of gotcha. They're being explicit about the limitation. The built an interesting thing and showed that it does interesting things in a toy setting. This gets me excited about future work down this path.

Re: Beyond automatic differentiation

#28

Post by 6gvONxR4sf7o » Fri, Apr 14, 2023, 7:48 PM UTC

kelseyfrog wrote: post #18

That's great. Interval arithmetic is an underappreciated area of study, not because it's particularly difficult - anyone can grasp it in short order, but it's rarely the first, second, or third tool used for the job when confronted with a problem. Perhaps it's just not prestigious enough compared to more sophisticated methods.

How does this generally work in high dimensions? In 1d, an interval is a really simple thing. In higher dimensions, it generalizes in a bunch of ways, from a box to an arbitrary convex region. Given that practical problems tend to have the interesting bits constrained around a lower dimensional region, I imagine that the wrong representations (e.g. just an axis-aligned box) could make the intervals meaningless. Is that the case? Is it simple to overcome that (e.g. just align the box along the interesting subspace), or in practice is it harder to have useful high dimensional "intervals?"

Re: Beyond automatic differentiation

#29

Post by popinman322 » Fri, Apr 14, 2023, 7:51 PM UTC

modeless wrote: post #11

> We can use a similar idea to take an existing optimizer such as Adam and convert it to a hyperparameter-free optimizer that is guaranteed to monotonically reduce the loss (in the full-batch setting). I'm not a huge fan of analyses like this that make one huge assumption that never holds in practice. Nobody uses full-batch gradient descent. It's not possible in practice or even desirable in theory. The stochasticity…

I also liked the graph that showed only training loss vs Adam. Would have been nice to see validation loss as well; are we just helping Adam overfit the data?

Re: Beyond automatic differentiation

#30

Post by modeless » Fri, Apr 14, 2023, 8:18 PM UTC

DougBTX wrote: post #25

GaggiX wrote: post #12

Earlier quoted context omitted.

It improves Adam in the full-batch setting, which is not usually done or desired since minibatch should regularize and improve the loss.

Batch size can be used for regularisation, but using it for that will limit training performance. From the Google Research Tuning Playbook: > The batch size governs the training speed and shouldn't be used to directly tune the validation set performance. Often, the ideal batch size will be the largest batch size supported by the available hardware. > […] > As long as all hyperparameters are well-tuned (especially the…

The source you cite is talking about "large" batch sizes which are still a miniscule fraction of the training set. Their (good) advice has no relevance at all in a discussion of full-batch training.

Full-batch training is not the ideal case. It's a recipe for overfitting. We don't optimize models for their training set performance. We need them to generalize to the true data, of which our training set may not even be a representative sample. SGD works exceptionally well for that.