Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve
summary
The gist
Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output The quantity to measure is therefore how much of a target’s…
In short
Genetic programming evolves programs where fitness measures a downstream learner's output, not just the program's. This shifts the goal from finding an answer to finding a good representation of nonlinearity. The key finding is that difficulty depends on which learner is attached; a linear learner forces the program to build exactly one through six levels of nonlinearity, showing that expressive learners offer limited advantage.
Key concepts
- Order of Nonlinearity
- This measures how complex the target function's nonlinearity is. It's quantified by finding the lowest total polynomial degree required to approximate the target function with a specific error margin relative to its variance.
- Relocatable Order (ONLdecεV(y))
- This concept determines if a bounded, simple learner can recover the target's nonlinearity. It checks if there exists a simple function that, when composed with the program, gets close enough to the target based on its variance.
- Orthogonality of Difficulty and Learner
- The paper shows that difficulty in finding a solution and choosing an appropriate learner are independent factors. A powerful learner doesn't automatically make a program easier; the choice depends on whether the target allows for a low-order representation achievable by that specific learner.
Terminology used across episodes
This episode discusses
- Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve · Paper Radio
The paper
Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve · Read on arXiv
University of Vermont
Genetic programming was conceived as a way of evolving solutions: the program is the answer, and fitness is the error of its own output. A substantial line of work instead makes the program an input to a separate learner, so fitness measures the learner's output. Which learner to attach matters and depends on the problem, with no account of what decides it. What makes a target hard for genetic programming is how much nonlinearity the program must build by composing primitives; any nonlinearity the learner supplies, the program is spared. Here we show that how much the program must still build is decided by which learner is attached, and is measurable on the programs themselves. In Boolean domains, where a target's nonlinearity is exactly its Fourier degree, we tune that degree from one to six with everything else fixed. Conditioned on success, a linear learner forces the evolved program to the target's degree exactly, at one through six without exception over thirty runs per setting, while tree ensembles succeed with far simpler programs and four times as often. Where the target's structure is known, the learner can be chosen from that structure rather than from the target's reputation for difficulty: our control target has lower degree than the parity problems yet gains nothing from a nonlinear learner. Where it is not, the same quantities serve as diagnostics: the degree of the evolved program is free to compute during any run and shows whether the learner is contributing nothing or carrying the model; on two measured datasets the resulting procedure picks the right learner before any evolution is run. A warning follows: evolution internalises what the learner supplies in only four of sixty-three conditions and grows more dependent on it in forty-four. The more capable the learner, the less of the model is left legible in the program.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Relocating Nonlinearity: How a Downstream Learner Reshapes What Genetic Programming Must Evolve".
Paper summary: Tom: They argue that this shift means we're not just finding a solution anymore; we're finding a representation. The paper says the difficulty for genetic programming is how much nonlinearity the program has to build by combining basic operations.
Lu: Exactly. And they quantify this as the target’s order of nonlinearity, which they calculate exactly on Boolean domains using something called the Fourier degree >
Conclusion: Jane: So, when you look at what this paper actually claims about how attaching a learner changes things, it seems to suggest that the difficulty isn't just about the target anymore. It’s about which specific learner you pair with it.
Tom: The authors show that the amount of nonlinearity the program still has to build is decided by which learner is attached, and they say this can be measured directly on the programs themselves >
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game