acceptodds
Under review as a conference paper at ICLR 2027

Reconfiguration of Hypotheses: A Connectivity Perspective on Learning

Abstract

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.

Primary area:
learning theory
Keywords:
hypothesis reconfiguration, version spaces, connectivity, computational complexity, mode connectivity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_LvFCOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper asks whether two models that fit the training data or have low training loss can be connected by a sequence of local changes without exceeding a given loss budget. The authors apply an existing complexity classification for Boolean constraint reconfiguration to this problem. They then give margin and grid-resolution conditions for connecting halfspaces, show that allowing classification errors can introduce barriers, and construct discrete low-loss paths for two-layer networks. The network result requires width at least twice the sample size, together with the stated loss and parameter assumptions.

Critical strengths

The halfspace and network results give explicit bounds involving margins, grid resolution, and path loss. The paper also explains which results come from prior work and what is added by the discrete analysis

Critical weaknesses
  1. The paper gives loss bounds for discrete paths, but no numerical results showing how large the loss increase is at a fixed precision. It is hard to tell how conservative the bounds are or how these paths compare with continuous paths between the same models.

  2. The time and number of updates needed to construct and follow these paths are not evaluated. The construction also allows output weights up to mK, where m is the network width and K bounds the endpoint weights. It is unclear whether the paths remain practical when both computation and weight ranges are limited.

  3. The paper mentions model migration and local search as motivations. However, it is not clear why these settings need updates that change only one parameter by one grid step. A concrete example would help explain why this restriction matters.

Questions for authors
  1. Could the authors construct these paths between trained two-layer networks and report the maximum loss along them for different grid resolutions, widths, and sample sizes? How do the results compare with the bound and with continuous paths between the same models?

  2. In the model-migration or local-search examples, why would updates need to change one parameter by one grid step at a time? What would the discrete guarantee help us do in that setting?

Reviewer_T3PeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies whether two hypotheses with low empirical loss can be connected through small parameter changes while maintaining low loss. It relates this question to reconfiguration problems and presents theoretical results for discrete hypothesis classes, halfspaces, and two-layer neural networks.

Critical strengths
  1. The paper offers a unified perspective connecting hypothesis reconfiguration with learning and loss-landscape connectivity. This provides a useful framework for studying transitions between low-loss models.

  2. The analysis covers both halfspaces and neural networks, giving concrete settings beyond the abstract formulation. The treatment of discrete parameter changes also highlights the role of parameter resolution.

Critical weaknesses
  1. The significance of the advance over existing theory is not sufficiently established. While the connections are interesting, the paper could more clearly explain which new insight substantially improves our understanding of model connectivity.

  2. The main text emphasizes presenting multiple results, with less explanation of their implications. A clearer central takeaway and discussion of the assumptions would help readers assess the scope and importance of the contribution.

Questions for authors
  1. Could you highlight the single most important new insight beyond existing reconfiguration and mode-connectivity results, and explain its significance?

  2. Could you clarify how the width and grid-resolution assumptions affect the interpretation and scope of the network connectivity guarantee?

  3. Could you clarify how the proposed reconfiguration perspective relates to existing work on neural-network loss landscapes, particularly results on wide networks and suboptimal basins [1, 2]? What additional insight does the discrete connectivity formulation provide?

[1] Li D, Ding T, Sun R. On the benefit of width for neural networks: Disappearance of basins[J]. SIAM Journal on Optimization, 2022, 32(3): 1728-1758. [2] Ding T, Li D, Sun R. Suboptimal local minima exist for wide neural networks with smooth activations[J]. Mathematics of Operations Research, 2022, 47(4): 2784-2814.

Reviewer_87USOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes to use reconfiguration theory to analyze model learning. Given two models evaluated on the same data, does a path exist from one parameter configuration to another that does not decrease the loss below a specific threshold?

Critical strengths

None

Critical weaknesses

This paper is impossible for me to parse, much less to understand. The structure does not make sense. It has only two sections: an Introduction (section 1) of 7 Pages, which tries to do everything without providing the foundations. It contains everything from an actual introduction, results, conclusions, and discussion. After Discussion and open problems, it presents a paper organization at the end of page 7. Section 2, Preliminaries, then starts on Page 8, at the end of the paper. The paper is cut off at the page limit, inserts disclosure statements and references, and then continues for another 30+ pages in the appendix.

The sections themselves have no logical flow or structure. They are jargon-heavy to the point of making them incomprehensible even to expert readers, and provide little intuition, rationale, or motivation. Furthermore, the paper is spiked with theorems, Corollaries, and Propositions, many of those are merely re-statements of established results. These theorems are mostly stated, without connecting them to each other or into a cohesive argument.

Even after sustained reading, I could not reconstruct what the paper establishes, what it's contribution is beyond prior work, or why it matters. I believe that in its current form, the paper is not approachable to a human reader.

Questions for authors

An acceptance rating would require a full rewrite of the paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.