Global Optimization of Objective Functions Represented by ReLU Networks
- URL: http://arxiv.org/abs/2010.03258v3
- Date: Thu, 9 Sep 2021 19:00:37 GMT
- Title: Global Optimization of Objective Functions Represented by ReLU Networks
- Authors: Christopher A. Strong, Haoze Wu, Aleksandar Zelji\'c, Kyle D. Julian,
Guy Katz, Clark Barrett, Mykel J. Kochenderfer
- Abstract summary: Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts.
Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures.
We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
- Score: 77.55969359556032
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Neural networks can learn complex, non-convex functions, and it is
challenging to guarantee their correct behavior in safety-critical contexts.
Many approaches exist to find failures in networks (e.g., adversarial
examples), but these cannot guarantee the absence of failures. Verification
algorithms address this need and provide formal guarantees about a neural
network by answering "yes or no" questions. For example, they can answer
whether a violation exists within certain bounds. However, individual "yes or
no" questions cannot answer qualitative questions such as "what is the largest
error within these bounds"; the answers to these lie in the domain of
optimization. Therefore, we propose strategies to extend existing verifiers to
perform optimization and find: (i) the most extreme failure in a given input
region and (ii) the minimum input perturbation required to cause a failure. A
naive approach using a bisection search with an off-the-shelf verifier results
in many expensive and overlapping calls to the verifier. Instead, we propose an
approach that tightly integrates the optimization process into the verification
procedure, achieving better runtime performance than the naive approach. We
evaluate our approach implemented as an extension of Marabou, a
state-of-the-art neural network verifier, and compare its performance with the
bisection approach and MIPVerify, an optimization-based verifier. We observe
complementary performance between our extension of Marabou and MIPVerify.
Related papers
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural
Networks [94.63547069706459]
#DNN-Verification problem involves counting the number of input configurations of a DNN that result in a violation of a safety property.
We propose a novel approach that returns the exact count of violations.
We present experimental results on a set of safety-critical benchmarks.
arXiv Detail & Related papers (2023-01-17T18:32:01Z) - A Learning-Based Optimal Uncertainty Quantification Method and Its
Application to Ballistic Impact Problems [1.713291434132985]
This paper concerns the optimal (supremum and infimum) uncertainty bounds for systems where the input (or prior) measure is only partially/imperfectly known.
We demonstrate the learning based framework on the uncertainty optimization problem.
We show that the approach can be used to construct maps for the performance certificate and safety in engineering practice.
arXiv Detail & Related papers (2022-12-28T14:30:53Z) - Gleo-Det: Deep Convolution Feature-Guided Detector with Local Entropy
Optimization for Salient Points [5.955667705173262]
We propose to achieve fine constraint based on the requirement of repeatability while coarse constraint with guidance of deep convolution features.
With the guidance of convolution features, we define the cost function from both positive and negative sides.
arXiv Detail & Related papers (2022-04-27T12:40:21Z) - Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
Inspired by sum-of-infeasibilities methods in convex optimization, we propose a novel procedure for analyzing verification queries on networks with extensive branching functions.
An extension to a canonical case-analysis-based complete search procedure can be achieved by replacing the convex procedure executed at each search state with DeepSoI.
arXiv Detail & Related papers (2022-03-19T15:05:09Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Bayesian Optimization of Function Networks [20.73717187683924]
We consider Bayesian optimization of the output of a network of functions, where each function takes as input the output of its parent nodes, and where the network takes significant time to evaluate.
Our approach delivers greater query efficiency by leveraging information that the former ignores: intermediate output within the network.
We show that our approach dramatically outperforms standard Bayesian optimization methods in several synthetic and real-world problems.
arXiv Detail & Related papers (2021-12-31T05:35:21Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.