4 ms·
The NUTS algorithm in hybrid monte carlo would be pretty close to this. The problem is that integration suffers from the curse of dimensionality much worse tha
by mlthoughts2018 6y ago
The NUTS algorithm in hybrid monte carlo would be pretty close to this.
The problem is that integration suffers from the curse of dimensionality much worse than differentiation.
Differentiation is a local activity. You approximate a derivative near any point. Integration is non-local, you must aggregate a function over a span of points in the domain space.
As the dimensions get higher, differentiation merely must apply local approximation to each successive dimension of a point in a grid. It only adds the computation cost.
Integration requires exponentially more data (for a given level of accuracy) because adding a new dimension enlarges the entire integration domain space that must be ranged over, and worse you generally need all that new “volume” of the enlarged space to be covered evenly to avoid bias.
So there are some fundamental asymmetries between differentiation and integration that play a role in why “automatic integration” isn’t as straightforwardly feasible as for differentiation.
- srean 6y agoThe selling point of Monte Carlo is that regardless of dimension the estimation error is going to go down as 1/sqrt(n). That hides the dimension part in the 'constants' and the sampling routine. Usually one cannot afford to visit all of the space. One visits high density regions preferentially.
- mlthoughts2018 6y agoYes, agreed, I just meant why we won’t see “automatic quadrature” in the same sense as “automatic differentiation”. It’s always going to rely on adaptive sampling, for exactly this reason of dimensionality.