I think the only problem with this paper is that it is picked up as a breakthrough, where all that it does is to exploit some holes in the applied computation model. Publishing such an exploit is fine, though a well-written such paper would warn the reader that this is a heck. Papers like this reteach the lesson of that models of computation have limitations. Though the problem with this one is that we kinda already knew these limitations and so why would you need another 30 page long paper about this?
A very nice post about FFT, OpenAI, and CS theory. However, I worry that terse calls for collective action ("we should consider doing something else") are detached from science culture (status quo, funding, institutional bias, fragile egos, ...) in the way that CS theory is detached from actual computers.
In defense of "exact complex arithmetic" (not OAI's ridiculous paper dump): plenty of people work on this sort of thing (keyword Blum-Shub-Smale model), and it has merit in providing potentially more tractable settings for various questions (like analyzing numerical algorithms, or "easier" versions of P vs NP.) There are also some high-profile people in TCS who are careful about things like controlling the bit-sizes and rounding errors in real/complex arithmetic.
All that said, there is your broader point that the paper dump "amplifies the unspoken cultural practices no one likes", such as not implementing an algorithm. Here, I completely agree!
I'm not against real computation as a lens on actual computation. The Blum-Shub-Smale work and related inquiry show that numerical conditioning is often the heart of complexity. Morgenstern and Ailon's work is closely related. I'm just saying that if you are going to all for real-valued coefficients, you have to show you can approximate your algorithm on a standard computer. And for that, you can't have exponentially large coefficients in matrices with infinite condition numbers.
One nice thing about proving that something is possible epsilon faster than O(f(n)) time is that you can stop looking for a proof that the best you can do is O(f(n)).
I had the impression that the successes of AI in applied math were rather measured anyway. One would think that AI companies have a large interest in, say, faster implementations of stochastic gradient descent. But either they haven't let their agents loose on this, or they found nothing.
Thank you for bringing this down to earth for us math tourists. Not sure how I feel about your description of the theoretic formalism in computer science. It seems very unfortunate for a discipline that should be application focused. On the other hand, makes me feel better that economics is not the only discipline that has lost its way with pseudo formalism.
This, the faster integer multiplication, faster matrix multiplication all have the same issue of being thoroughly impractical, and even theoretically they don’t see to be anything a human would even attempt, looking at how ugly the results are.
The unique games conjecture proof is something far more practical and stunning that OpenAI proved in Theoretical CS.
Unreasonable complaint imo. Wow mathematics is ungrounded from physical reality? This has really torn the foundations out from under me — I always hoped my work in arithmetic geometry might cure cancer someday.
It's not a "failure of the culture" that the *complexity theorists* care more about the asymptotic behaviour than numerical improvements. Were it otherwise they ought to drop out of academia and become consultants for Google or something. You're more or less just arguing against the study of abstract objects in general.
Is this the best defence we can mount of our discipline? Complaints about *practicality*, of all things? (Mathematicians begging for mercy on the grounds of applicability to the real world — we really are fucked).
Thanks for the nice summary.
I think the only problem with this paper is that it is picked up as a breakthrough, where all that it does is to exploit some holes in the applied computation model. Publishing such an exploit is fine, though a well-written such paper would warn the reader that this is a heck. Papers like this reteach the lesson of that models of computation have limitations. Though the problem with this one is that we kinda already knew these limitations and so why would you need another 30 page long paper about this?
A very nice post about FFT, OpenAI, and CS theory. However, I worry that terse calls for collective action ("we should consider doing something else") are detached from science culture (status quo, funding, institutional bias, fragile egos, ...) in the way that CS theory is detached from actual computers.
In defense of "exact complex arithmetic" (not OAI's ridiculous paper dump): plenty of people work on this sort of thing (keyword Blum-Shub-Smale model), and it has merit in providing potentially more tractable settings for various questions (like analyzing numerical algorithms, or "easier" versions of P vs NP.) There are also some high-profile people in TCS who are careful about things like controlling the bit-sizes and rounding errors in real/complex arithmetic.
All that said, there is your broader point that the paper dump "amplifies the unspoken cultural practices no one likes", such as not implementing an algorithm. Here, I completely agree!
I'm not against real computation as a lens on actual computation. The Blum-Shub-Smale work and related inquiry show that numerical conditioning is often the heart of complexity. Morgenstern and Ailon's work is closely related. I'm just saying that if you are going to all for real-valued coefficients, you have to show you can approximate your algorithm on a standard computer. And for that, you can't have exponentially large coefficients in matrices with infinite condition numbers.
One nice thing about proving that something is possible epsilon faster than O(f(n)) time is that you can stop looking for a proof that the best you can do is O(f(n)).
I had the impression that the successes of AI in applied math were rather measured anyway. One would think that AI companies have a large interest in, say, faster implementations of stochastic gradient descent. But either they haven't let their agents loose on this, or they found nothing.
Thank you for bringing this down to earth for us math tourists. Not sure how I feel about your description of the theoretic formalism in computer science. It seems very unfortunate for a discipline that should be application focused. On the other hand, makes me feel better that economics is not the only discipline that has lost its way with pseudo formalism.
This, the faster integer multiplication, faster matrix multiplication all have the same issue of being thoroughly impractical, and even theoretically they don’t see to be anything a human would even attempt, looking at how ugly the results are.
The unique games conjecture proof is something far more practical and stunning that OpenAI proved in Theoretical CS.
What is the practical impact of the Unique Games Conjecture being true?
There is an entire agenda to explore average and beyond worst case analysis - https://cacm.acm.org/research/beyond-worst-case-analysis/
Unreasonable complaint imo. Wow mathematics is ungrounded from physical reality? This has really torn the foundations out from under me — I always hoped my work in arithmetic geometry might cure cancer someday.
It's not a "failure of the culture" that the *complexity theorists* care more about the asymptotic behaviour than numerical improvements. Were it otherwise they ought to drop out of academia and become consultants for Google or something. You're more or less just arguing against the study of abstract objects in general.
Is this the best defence we can mount of our discipline? Complaints about *practicality*, of all things? (Mathematicians begging for mercy on the grounds of applicability to the real world — we really are fucked).