acceptodds
Under review as a conference paper at ICLR 2027

Discrete Input Landscapes of Neural Networks

Abstract

Turning neural-network predictions into decisions often requires downstream optimization over the network’s inputs. Local search can offer a particularly efficient approach to such optimization when the feasible set is discrete and one can move between feasible solutions using simple local changes. However, theoretical understanding of local-search performance over the input of trained neural-network landscapes remains limited. In this paper, we study how training shapes the discrete input landscapes of multilayer perceptrons over cardinality-constrained binary sets, equipped with the natural exchange neighborhood. In particular, we study the smoothness of such landscapes in the infinite-width neural tangent kernel (NTK) regime (Lee et al., 2020) through their autocorrelation (Weinberger, 1990), a notion particularly relevant to local-search performance. Under natural assumptions, we show that training produces smooth interpolations of the training labels, with expected autocorrelation approaching one as the input dimension grows. We also show that filtering out components of the trained network’s output associated with smaller eigenvalues of the random-walk matrix on the exchange neighborhood can increase autocorrelation while approximately preserving the output values. Motivated by the latter result, we propose a Filtered Local Search (FLS) method and show that it improves average solution quality over ordinary local search both in controlled experiments close to our theoretical model and in applications with neural architectures and feasible sets beyond it.

Primary area:
optimization
Keywords:
predict-then-optimize, combinatorial optimization, autocorrelation, NTK

Reviews

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

This paper considers the problem of minimising some cost function with input x by estimating the cost function with a neural network, and performing a greedy local search around some initial x. Specifically, they consider the scenario in which x is a discrete set of binary vectors with at most k non-zero elements, equipped with a neighbourhood structure where x is a neighbour of y if their hamming distance is exactly 2 i.e. they correspond to the same vector with a pair of elements swapped. Using a simplifying NTK assumption, the authors derive bound on the smoothness of the learned neural network function, which is a desirable property since it means local search is less likely to get stuck in local minima. They then prove that filtering out less significant eigenspaces results in a smoother yet very similar function, an operation which can be approximated by locally averaging the function over its neighbours. The resulting algorithm, called Filtered Local Search, performs local search over this neighbourhood averaged function to find a good broad basin, followed by local search on the original function to identify a local optimum. They then demonstrate this algorithm's efficacy on a range of toy models and applications for the surrounding literature.

Critical strengths
  • The paper is very well written, guiding the reader through fairly complicated theoretical setups and results, signposting the logical flow of the paper at various points, and providing simple interpretations of the various results.
  • The resulting algorithm is simple to implement, making it easy to adopt and therefore potentially increasing its impact, and appears to improve performance on the relevant tasks.
  • The theoretical tools (NTK assumption combined with results from theory on random graphs) are appropriate and used to good effect, which the theorems directly justifying and motivating the algorithm.
  • Note:
    • I was able to follow the argument throughout the paper, but did not verify the correctness of the mathematics or proofs.
Critical weaknesses
  • The problem studied seems quite niche, limiting the paper's impact.
  • The paper does not include any discussion on the limitations of their approach / the theoretical simplifications used in their analysis. For example, NTK models do not capture feature learning, and use gradient flow instead of discrete optimisation dynamics, and ideally the authors would explain how these limitations affect the validity of their theoretical results.
  • The experimental results are very short in the main text, with relatively little discussion.
  • Some form of error bars or statistical significance tests would be a more standard way to explain how significant the improvement over the baseline method is. As it stands, the authors report the proportion of cases in which their method performs best, which is high, and therefore provides reassurance.
Questions for authors
  • I have no questions that would significantly alter my assessment at this time.
  • Suggestions
    • It would be nice to have the algorithm in the main text
    • It would also be nice to have more of the results in the main text, rather than the short summaries given.
    • Report some kind of error bars / significance test for the results.
10 comments

Reviewer comment

The problem studied seems quite niche, limiting the paper's impact.

Response

The problem we study is actually relevant to many applications. Many practitioners train neural networks to learn the cost or performance of decisions and then optimize over these trained models to select new decisions. Understanding how training shapes the input landscapes of neural networks and how this affects local-search performance is, we believe, an important practical question.

Our theoretical analysis focuses on the specific setting of cardinality-constrained binary sets and infinite-width networks to capture essential features of the problem while remaining simple enough to be mathematically tractable. The resulting insights, however, can help explain and guide optimization beyond that setting. For instance, our proposed method FLS can be used with architectures and feasible sets beyond those covered by the theory, as we do in our facility location and production scheduling experiments.

Reviewer comment

The paper does not include any discussion on the limitations of their approach / the theoretical simplifications used in their analysis. For example, NTK models do not capture feature learning, and use gradient flow instead of discrete optimisation dynamics, and ideally the authors would explain how these limitations affect the validity of their theoretical results.

Response

This is an interesting point. Our theoretical analysis indeed focuses on the infinite-width NTK regime under gradient flow. Our controlled experiments, however, use finite-width networks trained with discrete gradient descent and exhibit high autocorrelation and spectral bias, consistent with the theoretical predictions. This suggests that the analysis already captures these empirical behaviours.

To address the reviewer’s concern and clarify this distinction, we have expanded the following sentence in the conclusion.

Another direction is to extend the analysis to finite-width networks, other architectures, and broader feasible sets.

To become:

Our theory assumes an infinite-width NTK model under gradient flow and does not capture feature learning. Our experiments nevertheless show that finite-width networks trained with discrete gradient descent behave consistently with the theory’s predictions. Our applications also show benefits from filtering with other architectures and feasible sets. These findings motivate extending the theory to finite-width networks, other architectures, and broader feasible sets.

Reviewer comment

The experimental results are very short in the main text, with relatively little discussion.

Response

Please see our response to comment [eCDT 2].

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

The paper looks at the optimization landscape explored by local search for discrete decision problems. The authors use an NTK approximation to prove that trained networks tend to induce highly smooth landscapes. A major fraction of the network's output can be captured by a smoother, lower-complexity representation of itself. Based on these theoretical insights, the authors propose a method where an ordinary local search runs after one where each state's value is replaced by its neighborhood average (this producing an smoothed objective).

Critical strengths

The question the paper addresses (influence of training dynamics of search landscape) is not under-explored, so the the work looks relevant and timely.

Filtered Local Search is rather simple to conceptually simple and straightforward, requires no retraining, and is successfully evaluated on neural networks.The setup are documented thoroughly and the documentation is detailed and transparent.

My understanding is that the proofs are comprehensive and well articulated, although I cannot properly comment on them since my expertise is limited.

Critical weaknesses

The evaluation omits comparisons against the true objective functions. Given that some synthetic target functions are inherently smooth, reporting the smoothness metrics of the ground-truth function alongside the neural network's predictions would clarify whether training imparts additional smoothness or merely inherits it.

There seems to be a mismatch between the theoretical assumptions and the synthetic experiments. The theory assumes training samples are drawn from the identical subset of decisions being optimized, whereas the empirical evaluation utilizes a much broader distribution where virtually no training points overlap with the optimized set in larger instances. Furthermore, the problem scales remain small, failing to evaluate the asymptotic behavior predicted by theory.

Questions for authors
  • How does FLS perform relative to vanilla local search and standard discrete optimization heuristics when constrained to an identical computational time budget?

  • Does the theoretical smoothness guarantee persist when the network is trained on randomized labels?

  • What motivated the choice to sample training instances from outside the optimized decision set, and do the empirical results change if the distribution aligns with the theory?

9 comments

Reviewer comment

The evaluation omits comparisons against the true objective functions.

Response

Please see our response to comment [eCDT 6].

Reviewer comment

Given that some synthetic target functions are inherently smooth, reporting the smoothness metrics of the ground-truth function alongside the neural network's predictions would clarify whether training imparts additional smoothness or merely inherits it.

Response

This is a very good point. We compared the autocorrelation of the target functions and the trained networks in our controlled experiments. The networks have higher autocorrelation than their targets in 370 of 375 comparisons. The following table reports the mean autocorrelation for each target family.

Target familyMean target autocorrelationMean network autocorrelation
Quadratic0.62910.6711
Ising0.65170.6816
NK0.45080.6089

We have added this comparison to Section 5 and Appendix C.3.

Reviewer comment

There seems to be a mismatch between the theoretical assumptions and the synthetic experiments. The theory assumes training samples are drawn from the identical subset of decisions being optimized, whereas the empirical evaluation utilizes a much broader distribution where virtually no training points overlap with the optimized set in larger instances.

Response

Please see our response to comment [eCDT 7].

Reviewer_eCDTOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how training shapes the input landscape of a neural network when it is used as an objective for local search. They measure smoothness with autocorrelation, the correlation between predicted values at neighboring solutions.

In the infinite-width (NTK) limit, they show that the expected autocorrelation approaches one as the problem size grows, and that the output can be filtered to an even smoother version with little change in its values. The authors also propose a method called Filtered Local Search (FLS), which first runs local search on the neighborhood-averaged output and then refines on the original output.

Critical strengths
  1. I think the paper studies an interesting question: how standard training shapes the landscape that is later searched over by local search. Also, I think it connects two lines of work that have mostly been separate, namely spectral bias of the NTK on discrete inputs and autocorrelation from fitness-landscape analysis, and gives an explicit theory for cardinality-constrained binary sets. This is one of the key aspects of my assessment, since local search over trained networks is common in practice, and, as far as I know, prior guarantees rely on special architectures or assumed properties like sub-modularity rather than on what training actually produces.

  2. I also think the theoretical analysis is insightful. Theorem 1 accounts for randomly sampled training inputs and random initialization, using the part of the initialization that training cannot change to keep the output’s variance from collapsing. I skimmed through a few of the proofs, and they look correct to me. This matters for my assessment since it makes the high-autocorrelation result a real statement about trained networks, not just about the kernel, even though I think its practical meaning is overstated (see weaknesses).

Critical weaknesses
  1. One of my main concern is that the practical meaning of the high-autocorrelation result (Theorem 1) is somewhat overstated? When the number of selected items k stays a fixed fraction of the total number of items n (k/n bounded away from 0 and 1), the largest possible autocorrelation on the swap neighborhood is already 1 − Θ(1/n), so any function whose output is mostly in the first few spectral levels has autocorrelation 1 − O(1/n). The theorem therefore shows that the trained network is effectively low-degree, which is meaningful compared with a random function, but low degree does not imply easy local search. For example, for MAX-CUT objectives, which the paper itself cites as hard, are quadratic and so also have autocorrelation approaching one on these sets. This is important to my assessment since the paper's main claim, that training produces landscapes favorable for local search, rests on this theorem.

  2. The introduction lists FLS, the controlled experiments and the applications as main contributions, but the main text covers them only briefly and without any tables or figures -- making it very hard to interpret (Section 6 reports only win/tie/loss counts, and all objective values, runtimes and breakdowns appear only in the appendix. There is also missing closely related work on the spectral bias of neural networks on binary inputs.

  3. The evaluation of FLS does not yet show that it is useful in practice. FLS is compared with local search from the same starting points, not with the same compute, even though it is much slower in facility location and scheduling (where its gains are under 0.3%). The Gurobi baseline gets only about 0.6 s and never improves on its random starting solution, so beating it says little. All results are also measured on the network’s predictions rather than the true cost, even though both applications can evaluate the true cost. Comparisons under equal compute (e.g. local search with more restarts, simulated annealing) and true-cost results are needed to support FLS as a practical method.

Questions for authors
  1. Why are the training inputs sampled from the whole hypercube rather than from X? For n≥25n \geq 25, almost no training points lie in X, so the measured landscapes are mostly extrapolation. Do the results hold when training on X?
10 comments

Reviewer comment

One of my main concern is that the practical meaning of the high-autocorrelation result (Theorem 1) is somewhat overstated? When the number of selected items kk stays a fixed fraction of the total number of items nn (k/nk/n bounded away from 0 and 1), the largest possible autocorrelation on the swap neighborhood is already 1−Θ(1/n)1-\Theta(1/n), so any function whose output is mostly in the first few spectral levels has autocorrelation 1−O(1/n)1-O(1/n). The theorem therefore shows that the trained network is effectively low-degree, which is meaningful compared with a random function, but low degree does not imply easy local search. For example, for MAX-CUT objectives, which the paper itself cites as hard, are quadratic and so also have autocorrelation approaching one on these sets. This is important to my assessment since the paper's main claim, that training produces landscapes favorable for local search, rests on this theorem.

Response

The relationship between autocorrelation and local-search performance depends on the class of landscapes under consideration. Our introduction gives examples of landscape classes in which higher autocorrelation is associated with better local-search performance. However, this relationship is not universal, and there are classes where autocorrelation does not reliably predict search performance. More generally, autocorrelation should not be used on its own to compare search difficulty across different classes. One example from the literature of this dependence on the landscape class is Kinnear (1994), who reports an association between autocorrelation and genetic search difficulty for parity tasks, but not for sorting tasks.

Now, our controlled experiments provide empirical evidence of a positive association for the landscapes we study. Specifically, we ask whether, among different neural networks that fit some observations, those with larger autocorrelation have better local search performance. We do this by training networks on nested datasets and find a median Spearman correlation of 0.8940.894.

With this empirical evidence in place, Theorem 1 asks whether gradient-flow training in the infinite-width regime favors interpolants with high autocorrelation. Under its stated assumptions, it gives an affirmative answer. Expected autocorrelation is at least 1−C/n1-C/n, although the network can also fit the same training labels with autocorrelation arbitrarily close to the minimum −1/max⁡{k,n−k}-1/\max\{k,n-k\}. Thus, the theorem identifies a training bias toward smooth interpolants, although fitting the data alone does not require such smoothness.

This is why our introduction, after discussing diverse applications in which higher autocorrelation is associated with better local-search performance, explicitly states that we present experiments showing this association for the trained neural-network landscapes we study. However, to further clarify this, we added the following footnote after our first mention of this association in the introduction.

We note that the association between autocorrelation and search performance is nevertheless not universal and can be weak for some classes of landscapes (Kinnear, 1994). For the trained neural-network landscapes we study, we provide empirical evidence of a strong positive association.

Reviewer comment

The introduction lists FLS, the controlled experiments and the applications as main contributions, but the main text covers them only briefly and without any tables or figures -- making it very hard to interpret (Section 6 reports only win/tie/loss counts, and all objective values, runtimes and breakdowns appear only in the appendix.

Response

We placed the detailed tables and figures in the appendix due to space limitations. However, to address your concern, we made the following changes.

  • We rewrote the pseudocode for FLS more compactly and moved it to the main text.
  • We added direct references to the specific figures and tables supporting each result discussed in the main text (in addition to the general appendix references we had before), so readers can access them immediately in the relevant appendix.
  • We now follow the following consistent reporting convention throughout Section 6: (i) we first give a summary of the numerical results, and (ii) we then give win/tie/loss counts to show how consistently the improvements occur across instances.

Reviewer comment

There is also missing closely related work on the spectral bias of neural networks on binary inputs.

Response

We have added a paragraph after the discussion of Lemma 2 highlighting the analogy between our result and prior work on spectral bias toward low-degree Fourier components in neural networks on the Boolean hypercube, with references to Yang and Salman (2019), Abbe et al. (2024), and Gorji et al. (2023).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.