Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

jmlr.org

Post reply on HN
Print view View original

21–30 of 51 posts

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#21

Post by adamnemecek »

throwawaymath wrote: post #19
adamnemecek wrote: post #2

The idea of duality is insane. Its present in linear logic, automatic diff, constructive mathematics, probability, quantum theory, game design, discrete optimization, etc. I wonder if it's related to chirality.

I think characterizing duality in this way is kind of superfluous, because the only way all those meanings of duality are the same is in the most abstract sense of the word. In other words, lots of things have duals. But the duality between any given pair of things doesn't necessarily expose any deep, fundamental connection to another pair of things which have duality. So it's not that duality features so heavily thr…

> I think characterizing duality in this way is kind of superfluous,

It's an analysis done out of necessity. These dualities might not be a 100% in every case, but maybe I care about the ways in which they are similar.

> because the only way all those meanings of duality are the same is in the most abstract sense of the word.

So is a monad. Do you think that in the future, the level of abstraction in mathematics is going to increase or decrease?

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#22

Post by adamnemecek »

throwawaymath wrote: post #20
KenoFischer wrote: post #15

Earlier quoted context omitted.

Forward AD is the pushforward of a tangent vector (an element of the tangent space), Reverse AD is a pullback of a cotangent vector (an element of the cotangent space). The duality notion between tangent and cotangent spaces is the same as the duality notion of spaces in optimization. Unfortunately, I'm only passingly familiar with discrete optimization, but I would suspect the notion extends from optimization. That'…

Yeah, but all you're really describing here is linear algebra. Vector spaces and linearity are a significant part of every single discipline the grandparent commenter mentioned, but they picked out duality. I would agree with the critique: I don't think highlighting duality here is particularly useful. For example, the way dual numbers are used to extend the reals for automatic differentiation doesn't have a deep con…

> For example, the way dual numbers are used to extend the reals for automatic differentiation doesn't have a deep connection to duality in vector spaces.

They don't. Because certain operations are hard to reason about in linear spaces. Such as optimization.

Don't get me wrong, I'm not shitting on vector spaces. All I'm saying is that some problems are hard to do in vector spaces, that are easy in the smooth spaces and vice versa. Like having these two APIs to the same space much more powerful, because again, you generalize over the conversions between the two spaces. You use whichever API is more appropriate in the particular context.

In some sense the linear spaces deal with things like infinity, the smooth spaces deal with cyclical things (signals, wavelets, modular arithmetic).

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#24

Post by adamnemecek »

throwawaymath wrote: post #16
adamnemecek wrote: post #8

Earlier quoted context omitted.

They aren't, the underlying idea is the same, or very similar. Pick two of them and I'll provide reference on the connection.

Okay, automatic differentiation and probability.

https://math.stackexchange.com/questions/2593296/why-is-prob...

Automatic differentiation is something that you get for free if you use dual numbers. Lie theory describes the relationship between the discrete and continuous spaces. Probability has this deep connection to Lie groups.

To give you some intuition (and I'm really rephrasing the stackexchange post above), the only way you can only measure randomness (or generate randomness) is if each draw has a "reference" to some global object that has the global, normalized view of the discrete space.

Are you familiar with Vovk's foundations of probability? That brings you from probability to game semantics. Duality is right next to it.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#25

Post by wenc »

adamnemecek wrote: post #17
wenc wrote: post #14

Earlier quoted context omitted.

Curious, can you expand on the connection to convex optimization? To my understanding, discrete optimization is nonconvex by nature due to discontinuities in the feasible space.

There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the g…

I’m not sure. I’m not entirely convinced that discrete and continuous spaces are dual spaces. They are connected, but they are not duals.

Same with sampling vs continuous. One cannot interchange the order of the composing morphisms while preserving the properties of the original. The sampled object cannot reconstruct the continuous object in all situations due to effects like aliasing.

In optimization, the concept of duality is also a much stronger idea: the primal and the dual of a problem are opposing views of the same problem that correspond exactly (not approximately) in their dual properties.

Discrete optimization is nonconvex by nature (does not satisfy convexity definitions) so I’m not sure if it has any duality relations to convex optimization. There is a relationship but it is not a dual relationship.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#26

Post by throwawaymath »

adamnemecek wrote: post #21
throwawaymath wrote: post #19

Earlier quoted context omitted.

I think characterizing duality in this way is kind of superfluous, because the only way all those meanings of duality are the same is in the most abstract sense of the word. In other words, lots of things have duals. But the duality between any given pair of things doesn't necessarily expose any deep, fundamental connection to another pair of things which have duality. So it's not that duality features so heavily thr…

> I think characterizing duality in this way is kind of superfluous, It's an analysis done out of necessity. These dualities might not be a 100% in every case, but maybe I care about the ways in which they are similar. > because the only way all those meanings of duality are the same is in the most abstract sense of the word. So is a monad. Do you think that in the future, the level of abstraction in mathematics is g…

It will increase, which I guess is sort of my point. We already know there's a lot of abstraction. If these things are only alike semantically (two pairs of dual things can be completely unrelated), what does it gain you to point out they've everywhere?

I don't mean to be obtuse, but it strikes me as saying that a city is full of concrete.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#27

Post by throwawaymath »

adamnemecek wrote: post #24
throwawaymath wrote: post #16

Earlier quoted context omitted.

Okay, automatic differentiation and probability.

https://math.stackexchange.com/questions/2593296/why-is-prob... Automatic differentiation is something that you get for free if you use dual numbers. Lie theory describes the relationship between the discrete and continuous spaces. Probability has this deep connection to Lie groups. To give you some intuition (and I'm really rephrasing the stackexchange post above), the only way you can only measure randomness (or ge…

Wait, what?

> Automatic differentiation is something that you get for free if you use dual numbers. Lie theory describes the relationship between the discrete and continuous spaces. Probability has this deep connection to Lie groups.

This...doesn't follow. Probability has a connection to Lie groups because it's fundamentally analytic ("continuous"). But you haven't explained how you make the connection to the dual numbers.

What you're showing here is that a lot of things in mathematics can be described analytically (and saying that would be likewise pretty superfluous). But just because you're working with continuous spaces doesn't mean you've engaged the duals. It generally means you're using the reals.

This gets to the heart of what I'm saying - if I wanted to be flippant I could have said the real numbers, or continuity, or analysis, etc are at the heart of so many distinct subfields of mathematics. It doesn't mean quite a lot.

Duality features in a lot of different parts of mathematics, but that doesn't mean you can productively draw connections between dual things in one area and dual things in another. I'm not seeing how you get from dual numbers to Lie groups.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#28

Post by throwawaymath »

adamnemecek wrote: post #22
throwawaymath wrote: post #20

Earlier quoted context omitted.

Yeah, but all you're really describing here is linear algebra. Vector spaces and linearity are a significant part of every single discipline the grandparent commenter mentioned, but they picked out duality. I would agree with the critique: I don't think highlighting duality here is particularly useful. For example, the way dual numbers are used to extend the reals for automatic differentiation doesn't have a deep con…

> For example, the way dual numbers are used to extend the reals for automatic differentiation doesn't have a deep connection to duality in vector spaces. They don't. Because certain operations are hard to reason about in linear spaces. Such as optimization. Don't get me wrong, I'm not shitting on vector spaces. All I'm saying is that some problems are hard to do in vector spaces, that are easy in the smooth spaces a…

Quite a bit of optimization is easy to reason about in linear algebra. Take linear and mixed integer programming, for example. And convex optimization subsumes linear optimization in general. There is a lot of nonlinear optimization, but I can assure you with extremely high confidence that the common thread you're seeing here isn't duality, but more abstractly linearity.

Likewise cyclic things show up all the time in purely algebraic (read: discrete, non-smooth) contexts. We have that in vector spaces, group theory, rings, modules, etc.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#29

Post by throwawaymath »

adamnemecek wrote: post #17
wenc wrote: post #14

Earlier quoted context omitted.

Curious, can you expand on the connection to convex optimization? To my understanding, discrete optimization is nonconvex by nature due to discontinuities in the feasible space.

There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the g…

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two.

Re: Automatic Differentiation in Machine Learning: A Survey (2018) [pdf]

#30

Post by adamnemecek »

throwawaymath wrote: post #29
adamnemecek wrote: post #17

Earlier quoted context omitted.

There are two types of spaces, discrete and continuous. These are in a dual relationship. Duality is the isomorphism between these two. For example, for humans, it's easier to reason about discrete spaces. However a lot of things simply cannot be done that way. Think of anything that is tangential (pun intended) to Lie theory. In the context of Lie theory, you have the discrete group and the continuous algebra (the g…

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two.

Unless I'm severely misunderstanding you, a discrete set (or function) cannot be a dual of a continuous set (or function). If nothing else, the former is countable and the latter is uncountable; there can be no isomorphism between the two.

There is. Discrete samples are samples of the continuous space. In order to capture the continous space, you only really need to capture a particular set of samples that you then interpolate between.

The way I interpret isomorphism in this context is if you can capture one space in the other and then convert to the other without a loss of information.

Imagine a polynomial (in the smooth space). You can capture a particular set of points that uniquely determines the polynomial. In some circumstances you can use these samples to reconstruct the original polynomial by interpolating between any of the two points.

Post reply on HN