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

Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

github.com

Post reply on HN
Print view View original

41–50 of 67 posts

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#41

Post by szvsw »

frankling_ wrote: post #36
usgroup wrote: post #33

I used to replace strict Boolean conditionals with sigmoids in order to achieve continuous transfer for Bayesian change-point models. Does this do something similar or is it fancier?

Great point, the sigmoid approximation works well for certain problems and that's in fact what I used in the exploratory papers that lead to this work. The downsides are the lack of a clear interpretation how the original program and its smooth counterpart are related, and the difficulty of controlling the degree of smoothing as programs get longer. What DiscoGrad computes has a statistical interpretation: it's the c…

I’ve also used the sigmoid approximation to relax some problems (specifically for step changes in field properties in PINN problems) into continuous variables, cool to see this discussion here from a different perspective! Slightly off topic but the only other things I’m aware of that are vaguely related are things like the gumbel-softmax trick for making sampling from categorical distributions differentials or the Gaussian reparam trick (eg as used in VAEs). I’m curious if this is at least somewhat related to the approach taken in your work, in spirit if not in technical implementation?

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#42

Post by frankling_ »

sundalia wrote: post #38

This is very interesting. A few questions: - Why do you think similar approaches never landed on jax? My guess is this is not that useful for the current optimizations in fashion (transformers) - How would you convince jax to incorporate this?

Well, the most common ML problems can be expressed as optimization over smooth functions (or reformulated that way manually). We might have to convince the ML world that branches do matter :) On the other hand, there are gradient-free approaches that solve problems with jumps in other ways, like many reinforcement learning algorithms, or metaheuristics such as genetic algorithms in simulation-based optimization. The jury's still out on "killer apps" where gradient descent can outperform these approaches reliably, but we're hoping to add to that body of knowledge...

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#43

Post by frankling_ »

szvsw wrote: post #41
frankling_ wrote: post #36

Earlier quoted context omitted.

Great point, the sigmoid approximation works well for certain problems and that's in fact what I used in the exploratory papers that lead to this work. The downsides are the lack of a clear interpretation how the original program and its smooth counterpart are related, and the difficulty of controlling the degree of smoothing as programs get longer. What DiscoGrad computes has a statistical interpretation: it's the c…

I’ve also used the sigmoid approximation to relax some problems (specifically for step changes in field properties in PINN problems) into continuous variables, cool to see this discussion here from a different perspective! Slightly off topic but the only other things I’m aware of that are vaguely related are things like the gumbel-softmax trick for making sampling from categorical distributions differentials or the G…

Yeah, those tricks are highly related to what we do, the main difference being that we don't require a priori information about the distributions involved in the program. Instead, we compute a density estimation of the distribution of branch conditions at runtime, which makes things quite general and fully automatic, at the cost of some accuracy.

As an aside, the combination "known distributions + automation" is covered in the Julia world by stochasticAD (https://github.com/gaurav-arya/StochasticAD.jl).

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#44

Post by HarHarVeryFunny »

frankling_ wrote: post #32
HarHarVeryFunny wrote: post #31

What do you mean by plain autodiff being mostly useless with normal/discrete branching? Wouldn't branches normally just be "ignored" by autodiff - each training sample being a different computational graph (but with parts in common) due to branching points, so the only effect of branching is which computational graph gets executed and backpropagated through? What's the general type of use case where this default beha…

That's right, plain autodiff just ignores branches. Our canonical "why is this even needed" example is a program like "if (x >= 0) return 1; else return 0", x being the input. The autodiff derivative of this is zero, wherever you evaluate it, so if you sample x and run your program on each x as in a classical ML setup, you'd be averaging over a series of zero-derivatives. This is of course not helpful to gradient des…

Thanks, but could you briefly expand on what's happening in the minimal if (x >= 0) case with the discograd modification? What source code modification could the user could have made to achieve the same effect?

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#45

Post by frankling_ »

HarHarVeryFunny wrote: post #44
frankling_ wrote: post #32

Earlier quoted context omitted.

That's right, plain autodiff just ignores branches. Our canonical "why is this even needed" example is a program like "if (x >= 0) return 1; else return 0", x being the input. The autodiff derivative of this is zero, wherever you evaluate it, so if you sample x and run your program on each x as in a classical ML setup, you'd be averaging over a series of zero-derivatives. This is of course not helpful to gradient des…

Thanks, but could you briefly expand on what's happening in the minimal if (x >= 0) case with the discograd modification? What source code modification could the user could have made to achieve the same effect?

In DiscoGrad, smoothing would be applied by adding Gaussian noise with some configurable variance to x and running the program on those x's. The gradient would then be calculated based on the branch condition's derivative wrt. x (which is 1) and an estimate of the distribution of the condition (which is Gaussian).

In this specific example, the smoothed derivative happens to be exactly the Gaussian cumulative distribution function, so the user could just replace the program with that function. However, for more complex programs, it'd be hard to find such correspondences manually.

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#46

Post by cma »

usgroup wrote: post #34
dwrodri wrote: post #19

This is the sort of thing I expected to see when Chris Lattner moved to Google and started working on the Swift for Tensorflow project. I am so grateful that someone is making it happen! I remember being taught how to write Prolog in University, and then being shown how close the relationship was between building something that parses a grammar and building something that generates valid examples of that grammar. Whe…

Not really. The world of Bayesian modelling has much fancier tools: Hamiltonian MC. See MC Stan. There’s also been Gibbs samplers and other techniques which support discrete decisions for donkeys years. You can write down just about anything as a BUGS model for example, but “identifying the model” —- finding the uniquely best parameters, even though it’s a globally optimisation —- is often very difficult. Gradient de…

MC: Monte Carlo

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#47

Post by epr »

frankling_ wrote: post #5
eranation wrote: post #2

Laymen question - I sort of understand what gradient descent is, but I'm not sure I fully understand what DiscoGrad is doing, my probably incorrect naive understanding is: to find optimal params for a program by converting the branches of a program into something that resembles a "smooth" loss function so a tradition gradient descent algorithm can find local minima and suggest the optimal params / weights? EDIT: remo…

Yep, that's exactly it. The smoothness can either come from randomness in the program itself (then the objective function is asymptotically smooth and DiscoGrad estimates the gradient of that smooth function), or the smoothness can be introduced artificially. As an example, the very first thing we looked into was a transportation engineering problem, where the red/green phases of traffic lights lead to a non-smooth o…

Obviously, some of this branching, etc. is not differentiable. Is it doing finite differences?

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#48

Post by zaitanz »

So this confuses me slightly and I am keen to know the advantage of using this. I work on projects that heavily use auto-differentiation for complex models. The models are defined by user input files at run-time, so the state and execution pathway of the model is unknown at compilation time. Would this help?

Given that all auto-differentiation is an approximation anyways. I've found existing tooling (CppAD, ADMB, ADOL-C, Template Model Builder (TMB)) work fine. You don't need to come up with a differentiable problem or re-parameterize. Why would I pick this over any of those?

Re: Show HN: Boldly go where Gradient Descent has never gone before with DiscoGrad

#49

Post by Y_Y »

frankling_ wrote: post #32
HarHarVeryFunny wrote: post #31

What do you mean by plain autodiff being mostly useless with normal/discrete branching? Wouldn't branches normally just be "ignored" by autodiff - each training sample being a different computational graph (but with parts in common) due to branching points, so the only effect of branching is which computational graph gets executed and backpropagated through? What's the general type of use case where this default beha…

That's right, plain autodiff just ignores branches. Our canonical "why is this even needed" example is a program like "if (x >= 0) return 1; else return 0", x being the input. The autodiff derivative of this is zero, wherever you evaluate it, so if you sample x and run your program on each x as in a classical ML setup, you'd be averaging over a series of zero-derivatives. This is of course not helpful to gradient des…

Plain autodiff gives the correct derivative, but you modify the derivative to push people towards your global minimum?
Post reply on HN