Reconfiguration of Hypotheses: A Connectivity Perspective on Learning

Reconfiguration asks whether one feasible solution can be transformed into another by elementary, feasibility-preserving steps. We ask this for learning: configurations are the hypotheses of a concept class, feasibility is consistency with a sample, and the version space becomes a graph under local edits. For every efficiently evaluable class and polynomial-time-decidable local move relation, reachability lies in polynomial space. For classes admitting bidirectional polynomial-time translations between samples and Boolean constraint formulas, the satisfiability connectivity dichotomy transfers: hypotheses evaluating clauses give polynomial-space completeness, while linear concepts over the binary field admit polynomial-time reachability. The central object is the agnostic relaxation, where feasibility bounds the empirical loss: connectivity is governed by a bottleneck, the least budget admitting a path. For a clause class the bottleneck is polynomial-space-hard to approximate within any factor, yet collapses to the larger endpoint loss on finite landscapes without bad local minima whose minimizers are connected, a discrete form of mode connectivity. For halfspaces on a grid, sufficiently large functional margin guarantees zero-error paths, with a threshold sharp in the plane; positive error budgets can instead produce barriers at every resolution. In the chamber model, reachability is polynomial-time in every fixed dimension and for every fixed error budget. For two-layer networks with convex loss and width at least twice the sample size, lattice paths connect low-loss endpoints with an explicit loss allowance that vanishes under grid refinement.