Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study

• A similar DNN 0-1 MILP model had been independently proposed for counting linear regions, so the authors do not claim their model is new [11].Source: §1 · pp. 1–2
• The paper discusses formulation properties and presents bound tightening to reduce solution times.The authors also aim to motivate improved, potentially heuristic, solution schemes.Source: §1 · p. 2
• The authors apply the model to feature visualization and adversarial examples [12], where finding almost-optimal solutions is important.Source: §1 · p. 2

• A DNN is represented layer by layer, with each unit applying an affine map to preceding activations and then a componentwise ReLU.Source: §2 · p. 2
• For each ReLU, nonnegative variables x and s split its affine input, and a binary activation variable enforces that one part is zero.Indicator constraints of this kind can create very hard mixed-integer instances for current solvers.Source: §2 · pp. 2–4
• The 0-1 MILP fixes network weights and biases, assigns binary activations across units, and imposes known bounds on activation and slack variables.Source: §2 · pp. 3–4
• Max pooling uses binary variables to represent argmax, whereas average pooling is linear and directly incorporated.Source: §2 · p. 4
• For a fixed input, all activations are uniquely determined and any input satisfying the input bounds extends to a feasible solution; zero-input ReLUs can leave a binary degenerate.Source: §2 · p. 4
• Layerwise bound tightening maximizes each unit's x and s in reduced models, reuses tightened bounds in subsequent layers, and can save or distribute preprocessing.The authors report that tighter upper bounds are important for practical resolution of the model.Source: §2 · p. 5

3 Applications

• The model is not suited to training, where optimizing weights and biases makes internal-layer terms bilinear; the authors instead target input optimization with fixed weights.They note prior MILP training experience suggesting that seeking proven optima may be unwise because of overfitting.Source: §3 · p. 5

3.1 Experimental setup

• The 784-pixel MNIST inputs were grayscale values in [0, 1]; the three-hidden-layer network used (8, 8, 8) ReLUs and reached 93.04% test accuracy after 50 epochs.The output layer had 10 units for digits 0 through 9.Source: §3.1 · p. 6

3.2 Feature Visualization

• Within 1 second, each unit’s maximum-activation model was solved with bound strengthening, and the solver was over an order of magnitude slower without it.The resulting optimal inputs showed no identifiable visual pattern, at least for this DNN.Source: §3.2 · p. 6, Figure 1 · p. 6

3.3 Building Adversarial Examples

• Adversarial inputs were constrained to make a specified wrong digit’s activation at least 20% larger than every other activation, while minimizing L1 distance from the original.The target digit was set to (original digit + 5) mod 10.Source: §3.3 · p. 7
• The model located 2–3 critical pixels whose changes tricked the DNN, and its optimized solutions differed from the random noise used by standard methods.The authors present these controls as a way to probe what the DNN has learned.Source: §3.3 · p. 7

4 Computational performance

• With a 0.2 per-pixel change cap, adversarial examples required more changed pixels than unrestricted examples.The examples target a label five digits from the true label, modulo 10.Source: Figure 2 · p. 8, Figure 3 · p. 9, Figure 4 · p. 10
• The five evaluated DNNs varied in depth and layer widths, with 784 MNIST pixel inputs and 10 digit-classification outputs.Their hidden-layer configurations are listed as DNN1–DNN5.Source: §4 · p. 11
• The networks were trained for 50 epochs and achieved 93–96% test-set accuracy.The best weights and biases were used to build the models.Source: §4 · p. 11
• The improved-model runs used precomputed tightened bounds for the x and s variables, with up to five minutes allowed for each bound computation.The time limit was reached only a few times for the largest networks.Source: §4 · p. 11
• Runs were averaged over 100 runs for each DNN and model; computational times used IBM-ILOG CPLEX 12.7 on a standard four-core notebook (Intel i7 at 2.3 GHz, 16 GB RAM), with a 300-second limit per run.Source: §4 · p. 11
• Table 1 reports the percentage solved to proven optimality, average branching nodes and CPU time, and the gap between best upper and lower bounds.Instances solved to optimality have a zero gap.Source: §4 · p. 11, Table 1 · p. 12
• The improved model consistently outperformed the basic model, which failed to prove optimality on many instances of the three largest DNNs.The comparison used a 300-CPU-second time limit.Source: §4 · p. 11, Table 1 · p. 12

5 Conclusions and future work

• The paper addresses a 0-1 MILP model for DNNs with ReLU and max/average pooling activations.The authors frame this as an early step toward using discrete optimization to study neural networks.Source: §5 · p. 12
• Bound tightening significantly reduces solution times, and the model is used for feature visualization and adversarial-example construction on trained networks.The formulation is not suited to training because it becomes bilinear in that setting.Source: §5 · p. 12
• For small DNNs, proven-optimal solutions take seconds on a standard notebook, while some larger MNIST networks take an hour or more.The authors suggest restricted-model heuristics for these harder cases.Source: §5 · p. 12
• Future work includes reducing exact-solution effort, developing heuristics for large-network adversarial examples, and finding further deep-learning applications.Source: §5 · p. 12