[qsort]

If a C++ compiler depends on a C++ compiler to be compiled itself... do you see the problem?

I have only superficially looked at the paper, but it's pretty clear they are using an offline lookup table. There are no such problems involved.

[kazinator]

Yes, I do; your bootstrapping is dependent on a binary C++ compiler, which could be hiding something that isn't in the source code, but which propagates to newly bootstrapped compiler binaries which again pass it on to the next round of bootstrapping, ad infinitum.

Basically, we can't be sure that you really have a C++ compiler. The source code can be verified to be a C++ compiler, but the binaries deviate in some way, possibly malicious.

[robertlagrant]

Sure, but you seem to have gone off on a wild tangent. How does that relate to matrix multiplication?

[setr]

I believe he’s getting at the idea of nested levels of corruption, with no visibility into where that corruption happens (because recompilation of the compiler/ML produces a fresh inscrutable binary).

I suppose the better term in this context is error propogation

[kazinator]

It relates in the following way. Suppose you have some framework for calculation which depends on matrix multiplications. You use that framework to develop some approximation for matrix multiplications which are faster. Then to make that framework faster, you substitute that back into the framework. That is a sort of bootstrapping which user qsort has related to compiler bootstrapping.

The goal in compiler boostrapping is to reach a fixed point, in a single iteration. When the compiler binary compiles itself, what should come out is a faithful replica of that compiler binary. Having done compiler bootstrapping, I know about hair-pulling problems that occur when you don't have a fixed point. E.g. a bug in the optimization causes the compiler to subtly miscompile itself. The resulting compiler then severely miscompiles itself; e.g. fails to recompile itself entirely, or produces something that no longer runs at all. (And that's actually a lucky case; a compiler compiling itself is basically a dog food test. When that fails, you've caught a bug early. What keeps you awake at night is the compiler compiling itself perfectly fine, but rarely miscompiling other code in the wild.)

Anyway, this sort of malfunction is exactly what will happen if you take a working, self-hosted compiler and then replace some important chunk of it with some hokey machine-learning approximation. It's unlikely you can do that without breaking the fixed point.

I don't see how you can not have fixed point issues in the matrix scenario. Maybe it will stabilize if you iterate on it. You take the machine learning framework with approximate matrix multiplications in it and run the process for figuring out those matrix multiplications. You may get some different values in it, which you can substitute back and try again. Will that converge? If it does, how do you know the whole thing is still valid? (What definition of valid applies?)

[robertlagrant]

It's purely a performance increase. Its definition of valid will need to be that it matches the output of the non-ML version.

[coef2]

debugging a machine learning algorithm is already hard without this approximation method. I can see adding another layer could make it extremely harder.

[kazinator]

By "you", you mean user qsort, right?