Discrete Input Landscapes of Neural Networks

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.