Optimization by Directional Attacks: Solving Problems with Neural Network Surrogates

Abstract

This paper tackles optimization problems whose objective and constraints involve a trained Neural Network (NN), where the goal is to maximize $f(\Phi (x))$ subject to $c(\Phi (x))\le 0$, with $f$ smooth, $c$ general and non-stringent, and $\Phi$ a NN already trained and not given as a glass-box. We address two challenges regarding this problem: identifying ascent directions for local search, and ensuring reliable convergence towards relevant local solutions. To this end, we re-purpose the notion of directional NN attacks as efficient optimization subroutines, since directional NN attacks are designed to efficiently compute perturbations of $x$ that steer $\Phi (x)$ in prescribed directions. Precisely, we develop an attack operator that computes attacks of $\Phi$ at any $x$ along the direction $\nabla f(\Phi (x))$. Then, we propose a hybrid algorithm combining the attack operator with derivative-free optimization (DFO) techniques, designed for numerical reliability by remaining oblivious to the structure of the problem. We consider the Covering Direct Search Method (CDSM), which offers asymptotic guarantees to converge to a local solution under mild assumptions on the problem. The resulting method alternates between attack-based steps for heuristic yet fast local improvements of the current incumbent solution and CDSM steps for certified convergence and numerical reliability. Experiments on three problems show that this hybrid approach outperforms standard baselines.