[wasabi991011]

The exponential blowup is in the symbolic regression section, where to search among depth K trees requires 2^K parameters.

As an example, searching for sqrt(x) would require a tree of depth ~40 which is in the trillion-parameter regime.

[danbruc]

But that is not an increase in the expression size, that is the effort for searching for an expression tree that fits some target function. And that is no different from searching an expression based on common functions, that is of course also exponential in the expression tree height. The difference is that a eml-based tree will have a larger height - by some constant factor - than a tree based on common functions. On the other hand each vertex in an eml-tree can only be eml, one, or an input variable whereas in a tree based on common functions each vertex can be any of the supported basis functions - counting constants and inputs variables as nullary functions.

[wasabi991011]

Ah I see I misunderstood your point, thanks for clarifying.

I think you are right, each node in some other expression tree formed of primitives in some set Prim would be increased by at most max(nodes(expr)) for expr in Prim.

That's essentially what the EML compiler is doing from what I understand.

[DoctorOetker]

yes, and even this search doesn't actually require trillions of parameters, since the switching parameters will be sparse, which means you can apply a FakeParameter trick: suppose I want a trillion sparse parameters, thats a million by a million. Let's just model those parameters as inner products of a million vectors each of some dimension N. Now its in the regime of megabytes or a GB.

For extreme regularization, one can even go down to 10 arbitrary precision numbers: if we have a single vector of 10 dimensions, we can re-order the components 10! different ways.

10! = 3 628 800

so we can retrieve ~3M vectors from it, and we can form about 10 T inner products.