- 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
[cGZh 2]
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.
[cGZh 3]
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].
[cGZh 1]
Reviewer comment
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.