# Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling

arXiv: https://arxiv.org/abs/2205.14189 · HTML: https://mlsanity.com/paper/2205.14189/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 31 references that are in the map.
- First posted on arXiv 27 May 2022.

## Builds on (most cited first, 12 of 12)

- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming](https://mlsanity.com/paper/2010.11645/) (2020)
- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [Lagrangian Decomposition for Neural Network Verification](https://mlsanity.com/paper/2002.10410/) (2020)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (2020)

## Built on by (most cited first, 11 of 11)

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks](https://mlsanity.com/paper/2312.16699/) (2023)
- [Model-based feature selection for neural networks: A mixed-integer programming approach](https://mlsanity.com/paper/2302.10344/) (2023)
- [Deep Learning for Two-Stage Robust Integer Optimization](https://mlsanity.com/paper/2310.04345/) (2023)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [Learning Prescriptive ReLU Networks](https://mlsanity.com/paper/2306.00651/) (2023)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [Quantum Boltzmann Machines for Sample-Efficient Reinforcement Learning](https://mlsanity.com/paper/2511.04856/) (2025)
- [Monotone Optimisation with Learned Projections](https://mlsanity.com/paper/2601.20983/) (2026)

## Abstract (arXiv)

This paper introduces scalable, sampling-based algorithms that optimize trained neural networks with ReLU activations. We first propose an iterative algorithm that takes advantage of the piecewise linear structure of ReLU neural networks and reduces the initial mixed-integer optimization problem (MIP) into multiple easy-to-solve linear optimization problems (LPs) through sampling. Subsequently, we extend this approach by searching around the neighborhood of the LP solution computed at each iteration. This scheme allows us to devise a second, enhanced algorithm that reduces the initial MIP problem into smaller, easier-to-solve MIPs. We analytically show the convergence of the methods and we provide a sample complexity guarantee. We also validate the performance of our algorithms by comparing them against state-of-the-art MIP-based methods. Finally, we show computationally how the sampling algorithms can be used effectively to warm-start MIP-based methods.