5 ms·

> For example, gradient descent is often used in machine learning in ways that don’t require extreme precision. But a machine learning researcher might want to

> For example, gradient descent is often used in machine learning in ways that don’t require extreme precision. But a machine learning researcher might want to double the precision of an experiment. In that case, the new result implies that they might have to quadruple the running time of their gradient descent algorithm. That’s not ideal, but it is not a deal breaker. > But for other applications, like in numerical analysis, researchers might need to square their precision. To achieve such an improvement, they might have to square the running time of gradient descent, making the calculation completely intractable. I think a silver lining here is that a company having access to 10,000 times as much computing power as a common consumer can only achieve, say, a 10x better model. So the inequality isn't as extreme as it could be.

scotth 5y ago
This is my favorite comment (please don't down vote)
mjburgess 5y ago
Is that how scientific modelling (ie., modelling of non-computable functions) works though? It's not necessarily that squaring precision leads to a "better model", its that it fails to be a model at all without that precision. Eg., consider a climate model with effects at the first-decimal place, and 10th decimal-place of some measurable quantity vs. time. The effects at the 10th dp. could aggregate to overwhelm the effects at the 1 dp. It isnt that the model is better if it can "compute at the 10th dp" -- its just wildly inaccurate otherwise.
- ben_w 5y ago
  10 decimal points reminds me of a conversation I had with my father. Last century my dad was working on radar/IFF simulations, and he had an anecdote (if you can call it that) about when they switched from normal to double precision, and needing to get more digits of π (I think from 10 to 20, the way he talked implied some very strange things about the programming language(s) he was using). The third time he told this story, late-teenage-me pointed out that the curvature of spacetime under GR had more impact than the extra digits. While the broader point is valid, IIRC climate (being about average and broad trends) is fine with the imperfections, and handles this by running multiple simulations with slightly different parameters and seeing what usually happens. Weather forecast likewise.
  - mjburgess 5y ago
    I'm not sure this is as true as it seems. When creating simulations we do so by defining a computable function (ie., over discrete binary strings) which approximates some non-computable function (ie., over the reals). It is important to note that those non-computable functions are derived, in part, analytically based on theorems which require infinite precision, ie., real numbers. When we define a computable approximation we can only do so by narrowing the simulation to a scale where "the numbers have only a few significant digits". This is really the only thing we can simulate, and even then, we are using mathematical analysis to derive much of it -- which cannot be simulated. If you really wanted to simulate across scales, ie., run a simulation "from atoms to tables", i think we'd be requiring many many many decimal places. It would likely, i think, be physically impossible to do. (Or if not, then atoms to planets would be) -- as the discrete precision required would require a theoretical minimum of mass that would create a black hole. eg., Consider that a table has 10^verylargenumber of "spherical" atoms, and so its aggregate shape would be extremely sensitive to a miscalculation of each atoms shape ... and we would require a precision in PI probably something like 10^-verylargenumber.
    - wcoenen 5y ago
      > Consider that a table has 10^verylargenumber of "spherical" atoms That "verylargenumber" exponent is not actually a large number. It's probably close to 28. E.g. for a rough estimate, pretend that the table has a mass of 120kg and is made of only carbon atoms. 120000 gram / (12 gram/mol) = 10000 mol = 6x10^27 < 10^28. On a related note, the estimated number of atoms in the visible universe is around 10^80.
      - mjburgess 5y ago
        So the volume of one atom can be calculated using, c. 30 dp. of pi -- +3 so that errors do not compound. So we need 30 bits/atom to store the volume, for 10^30 atoms -- this is 10^15 petabytes. Suppose we're trying to estimate the shape of the table using the relevant state vector for each atom (ie., radius, coordinate, EM-shell, etc.). Ie., how these atoms interact to produce a structure. Then we need perhaps 10 numbers/atom, so 10^16 petabytes. And consider the computation. The issue is that macroscopic structuring effects, ie., that the table has its tabular shape also exert a top-down effect constraining the structure of the atoms. We'd have to solve that problem through iteration. Ie., we compute a shape from local effects only, then iteratively recompute until increasing orders of scale are included. Suppose we perform 1 operation/atom to compute an interaction, that's 10^30 operations. At 1ns/op, we have 10^21 seconds -- optimistically. That's one scale, now we need to iterate; given the orders of effects are 1nm...1m that's c. 10 scales, say. We're now at 10^22 seconds with 10^16 petabytes of data. And also, since we're running a 10-fold iteration we need more than 10^30 precision, as errors will compound. This is for a table!. As I said, choose your scale, eg., atom to star, and the storage requirments have an essentially physically impossible mass.
legulere 5y ago
10x is a lot if the market follows a winner takes it all model.
madsbuch 5y ago
This would only be implied if gradient descent was the only way to write machine learning.
cblconfederate 5y ago
inequality stems from the fact that others cannot reach the same result, no matter how small it is
adrianN 5y ago
One has to keep in mind that these are worst-case bounds. It is perfectly compatible with the result that someone with access to 10000x the computing power can achieve a 10000x better model for all the functions that we care about in practice.
- kbelder 5y ago
  My general impression is that it's fairly easy to get moderately accurate models with simple procedures on cheap hardware... linear regressions, say. Maybe that'll get you 75% predictive accuracy. Then, you apply better techniques, that hit the limits of your PC, and you bring that up to maybe 80%. Then you bring in the PHDs, move your analysis to a cluster or into the cloud, and you gain another 2%. In other words, it's more often that 10000x the computing power gives you something like a 1.2x the model quality, not 10000x or even 100x. Still worth doing for a large enough company, though. Just my experience, and only a generalization. Some models just can't be built without a minimum amount of horsepower, etc.
nightski 5y ago
I thought that Deep Learning primarily used stochastic gradient descent. I did not get deep enough into the article, but wouldn't that change the picture? Or are the computational complexity limits the same?

scotth 5y ago

This is my favorite comment (please don't down vote)

mjburgess 5y ago

Is that how scientific modelling (ie., modelling of non-computable functions) works though? It's not necessarily that squaring precision leads to a "better model", its that it fails to be a model at all without that precision. Eg., consider a climate model with effects at the first-decimal place, and 10th decimal-place of some measurable quantity vs. time. The effects at the 10th dp. could aggregate to overwhelm the effects at the 1 dp. It isnt that the model is better if it can "compute at the 10th dp" -- its just wildly inaccurate otherwise.

ben_w 5y ago
10 decimal points reminds me of a conversation I had with my father. Last century my dad was working on radar/IFF simulations, and he had an anecdote (if you can call it that) about when they switched from normal to double precision, and needing to get more digits of π (I think from 10 to 20, the way he talked implied some very strange things about the programming language(s) he was using). The third time he told this story, late-teenage-me pointed out that the curvature of spacetime under GR had more impact than the extra digits. While the broader point is valid, IIRC climate (being about average and broad trends) is fine with the imperfections, and handles this by running multiple simulations with slightly different parameters and seeing what usually happens. Weather forecast likewise.
- mjburgess 5y ago
  I'm not sure this is as true as it seems. When creating simulations we do so by defining a computable function (ie., over discrete binary strings) which approximates some non-computable function (ie., over the reals). It is important to note that those non-computable functions are derived, in part, analytically based on theorems which require infinite precision, ie., real numbers. When we define a computable approximation we can only do so by narrowing the simulation to a scale where "the numbers have only a few significant digits". This is really the only thing we can simulate, and even then, we are using mathematical analysis to derive much of it -- which cannot be simulated. If you really wanted to simulate across scales, ie., run a simulation "from atoms to tables", i think we'd be requiring many many many decimal places. It would likely, i think, be physically impossible to do. (Or if not, then atoms to planets would be) -- as the discrete precision required would require a theoretical minimum of mass that would create a black hole. eg., Consider that a table has 10^verylargenumber of "spherical" atoms, and so its aggregate shape would be extremely sensitive to a miscalculation of each atoms shape ... and we would require a precision in PI probably something like 10^-verylargenumber.
  - wcoenen 5y ago
    > Consider that a table has 10^verylargenumber of "spherical" atoms That "verylargenumber" exponent is not actually a large number. It's probably close to 28. E.g. for a rough estimate, pretend that the table has a mass of 120kg and is made of only carbon atoms. 120000 gram / (12 gram/mol) = 10000 mol = 6x10^27 < 10^28. On a related note, the estimated number of atoms in the visible universe is around 10^80.
    - mjburgess 5y ago
      So the volume of one atom can be calculated using, c. 30 dp. of pi -- +3 so that errors do not compound. So we need 30 bits/atom to store the volume, for 10^30 atoms -- this is 10^15 petabytes. Suppose we're trying to estimate the shape of the table using the relevant state vector for each atom (ie., radius, coordinate, EM-shell, etc.). Ie., how these atoms interact to produce a structure. Then we need perhaps 10 numbers/atom, so 10^16 petabytes. And consider the computation. The issue is that macroscopic structuring effects, ie., that the table has its tabular shape also exert a top-down effect constraining the structure of the atoms. We'd have to solve that problem through iteration. Ie., we compute a shape from local effects only, then iteratively recompute until increasing orders of scale are included. Suppose we perform 1 operation/atom to compute an interaction, that's 10^30 operations. At 1ns/op, we have 10^21 seconds -- optimistically. That's one scale, now we need to iterate; given the orders of effects are 1nm...1m that's c. 10 scales, say. We're now at 10^22 seconds with 10^16 petabytes of data. And also, since we're running a 10-fold iteration we need more than 10^30 precision, as errors will compound. This is for a table!. As I said, choose your scale, eg., atom to star, and the storage requirments have an essentially physically impossible mass.

legulere 5y ago

10x is a lot if the market follows a winner takes it all model.

madsbuch 5y ago

This would only be implied if gradient descent was the only way to write machine learning.

cblconfederate 5y ago

inequality stems from the fact that others cannot reach the same result, no matter how small it is

adrianN 5y ago

One has to keep in mind that these are worst-case bounds. It is perfectly compatible with the result that someone with access to 10000x the computing power can achieve a 10000x better model for all the functions that we care about in practice.

kbelder 5y ago
My general impression is that it's fairly easy to get moderately accurate models with simple procedures on cheap hardware... linear regressions, say. Maybe that'll get you 75% predictive accuracy. Then, you apply better techniques, that hit the limits of your PC, and you bring that up to maybe 80%. Then you bring in the PHDs, move your analysis to a cluster or into the cloud, and you gain another 2%. In other words, it's more often that 10000x the computing power gives you something like a 1.2x the model quality, not 10000x or even 100x. Still worth doing for a large enough company, though. Just my experience, and only a generalization. Some models just can't be built without a minimum amount of horsepower, etc.

nightski 5y ago

I thought that Deep Learning primarily used stochastic gradient descent. I did not get deep enough into the article, but wouldn't that change the picture? Or are the computational complexity limits the same?