I agree that A* and gradient descent are central examples of search; for realistic problems these algorithms typically evaluate the objective on millions of candidates before returning an answer.
In contrast, human problem solvers typically do very little state evaluation—perhaps evaluating a few dozen possibilities directly, and relying (as you said) on abstractions and analogies instead. I would call this type of reasoning “not very search-like”.
On the far end we have algorithms like Gauss-Jordan elimination, which just compute the optimal solution directly without evaluating any possibilities. Calling them “search algorithms” seems quite strange.
a general search process is something which takes in a specification of some problem or objective (from a broad class of possible problems/objectives), and returns a plan which solves the problem or scores well on the objective.
This appears to be a description of anyoptimization process, not just search—in particular it would include Gauss-Jordan elimination. I guess your ontology has “optimization” and “search” as synonyms, whereas mine has search as a (somewhat fuzzy) proper subset of optimization. Anyways, to eliminate confusion I’ll use Abram Demski’s term selection in future. Also added a terminology note to the post.
My ontology indeed has search and a narrow notion of optimization as approximately synonyms; they differ only somewhat in type signature and are easily interchangeable. Conceptually, both take in an objective, and return something which scores highly on the objective. (This is narrower than e.g. Flint’s notion of “optimization”; in that ontology it might be called a “general-purpose optimizer” instead.)
Anyway, insofar as any of this is relevant to the arguments for mesa-optimization, it’s the notion of search/optimization as general problem solving which applies there.
I agree that A* and gradient descent are central examples of search; for realistic problems these algorithms typically evaluate the objective on millions of candidates before returning an answer.
In contrast, human problem solvers typically do very little state evaluation—perhaps evaluating a few dozen possibilities directly, and relying (as you said) on abstractions and analogies instead. I would call this type of reasoning “not very search-like”.
On the far end we have algorithms like Gauss-Jordan elimination, which just compute the optimal solution directly without evaluating any possibilities. Calling them “search algorithms” seems quite strange.
This appears to be a description of any optimization process, not just search—in particular it would include Gauss-Jordan elimination. I guess your ontology has “optimization” and “search” as synonyms, whereas mine has search as a (somewhat fuzzy) proper subset of optimization. Anyways, to eliminate confusion I’ll use Abram Demski’s term selection in future. Also added a terminology note to the post.
My ontology indeed has search and a narrow notion of optimization as approximately synonyms; they differ only somewhat in type signature and are easily interchangeable. Conceptually, both take in an objective, and return something which scores highly on the objective. (This is narrower than e.g. Flint’s notion of “optimization”; in that ontology it might be called a “general-purpose optimizer” instead.)
Anyway, insofar as any of this is relevant to the arguments for mesa-optimization, it’s the notion of search/optimization as general problem solving which applies there.