Optimization Over Trained Neural Networks: Taking a Relaxing Walk
Besides training, mathematical optimization is also used in deep learning to model and solve formulations over trained neural networks for purposes such as verification, compression, and optimization with learned constraints. However, solving these formulations soon becomes difficult as the network size grows due to the weak linear relaxation and dense constraint matrix. We have seen improvements in recent years with cutting plane algorithms, reformulations, and an heuristic based on Mixed-Integer Linear Programming (MILP). In this work, we propose a more scalable heuristic based on exploring global and local linear relaxations of the neural network model. Our heuristic is competitive with a state-of-the-art MILP solver and the prior heuristic while producing better solutions with increases in input, depth, and number of neurons.
Code (1)
Similar Papers 제목 키워드 기반
Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More
Algorithms for node clustering typically focus on finding homophilous structure in graphs. That is, they find sets of similar nodes with many edges within, rather than across, the clusters. However, graphs often also exh…
ClusteringNode ClusteringWalkability Optimization: Formulations, Algorithms, and a Case Study of Toronto
The concept of walkable urban development has gained increased attention due to its public health, economic, and environmental sustainability benefits. Unfortunately, land zoning and historic under-investment have result…
Combinatorial OptimizationDifferentially Private Consensus-Based Distributed Optimization
Data privacy is an important concern in learning, when datasets contain sensitive information about individuals. This paper considers consensus-based distributed optimization under data privacy constraints. Consensus-bas…
Distributed OptimizationPredicting Electricity Consumption with Random Walks on Gaussian Processes
We consider time-series forecasting problems where data is scarce, difficult to gather, or induces a prohibitive computational cost. As a first attempt, we focus on short-term electricity consumption in France, which is …
Decision MakingFew-Shot LearningGaussian ProcessesTime Series+1On the Constrained Least-cost Tour Problem
We introduce the Constrained Least-cost Tour (CLT) problem: given an undirected graph with weight and cost functions on the edges, minimise the total cost of a tour rooted at a start vertex such that the total weight lie…