Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms

• URL: http://arxiv.org/abs/2302.12261v1
• Date: Thu, 23 Feb 2023 17:26:51 GMT
• Title: Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithms
• Abstract summary: We study the computational problem of the stationarity test for the empirical loss of neural networks with ReLU activation functions. We show that checking a certain first-order approximate stationarity concept for a piecewise linear function is co-NP-hard. We introduce an algorithmic scheme to test near-approximate stationarity in terms of both Clarke and Fr'echet subdifferentials.
• Score: 31.478874616470048
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational problem of the stationarity test for the empirical loss of neural networks with ReLU activation functions. Our contributions are: Hardness: We show that checking a certain first-order approximate stationarity concept for a piecewise linear function is co-NP-hard. This implies that testing a certain stationarity concept for a modern nonsmooth neural network is in general computationally intractable. As a corollary, we prove that testing so-called first-order minimality for functions in abs-normal form is co-NP-complete, which was conjectured by Griewank and Walther (2019, SIAM J. Optim., vol. 29, p284). Regularity: We establish a necessary and sufficient condition for the validity of an equality-type subdifferential chain rule in terms of Clarke, Fr\'echet, and limiting subdifferentials of the empirical loss of two-layer ReLU networks. This new condition is simple and efficiently checkable. Robust algorithms: We introduce an algorithmic scheme to test near-approximate stationarity in terms of both Clarke and Fr\'echet subdifferentials. Our scheme makes no false positive or false negative error when the tested point is sufficiently close to a stationary one and a certain qualification is satisfied. This is the first practical and robust stationarity test approach for two-layer ReLU networks.

Related papers

• Random test functions, $H^{-1}$ norm equivalence, and stochastic variational physics-informed neural networks [0.0]
  Dual norm characterisation of weak solutions of second-order linear elliptic partial differential equations is mathematically natural but computationally intractable.<n>We prove that the $H-1$ norm of any functional is equivalent to its expected squared evaluation against a random test function whose distribution depends only on the domain.<n>This equivalence introduces the notion of weak solutions, which coincide with classical weak solutions, and motivates variational physics-informed neural networks (SV-PINNs): neural networks trained by minimising an empirical approximation of the deterministic norm of the PDE residual.
  arXiv  Detail & Related papers  (2026-05-05T09:14:38Z)
• A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms [41.15017547767954]
  We introduce an a posteriori certification viewpoint for the generalized quantum Arimoto-Blahut (QAB) algorithm.<n>We prove a global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer.<n>As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels.
  arXiv  Detail & Related papers  (2026-01-14T09:10:41Z)
• The Implicit Bias of Minima Stability in Multivariate Shallow ReLU Networks [53.95175206863992]
  We study the type of solutions to which gradient descent converges when used to train a single hidden-layer multivariate ReLU network with the quadratic loss. We prove that although shallow ReLU networks are universal approximators, stable shallow networks are not.
  arXiv  Detail & Related papers  (2023-06-30T09:17:39Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience. We show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one.
  arXiv  Detail & Related papers  (2022-11-16T00:11:04Z)
• Intersection of Parallels as an Early Stopping Criterion [64.8387564654474]
  We propose a method to spot an early stopping point in the training iterations without the need for a validation set. For a wide range of learning rates, our method, called Cosine-Distance Criterion (CDC), leads to better generalization on average than all the methods that we compare against.
  arXiv  Detail & Related papers  (2022-08-19T19:42:41Z)
• A Simple Approach to Improve Single-Model Deep Uncertainty via Distance-Awareness [33.09831377640498]
  We study approaches to improve uncertainty property of a single network, based on a single, deterministic representation. We propose Spectral-normalized Neural Gaussian Process (SNGP), a simple method that improves the distance-awareness ability of modern DNNs. On a suite of vision and language understanding benchmarks, SNGP outperforms other single-model approaches in prediction, calibration and out-of-domain detection.
  arXiv  Detail & Related papers  (2022-05-01T05:46:13Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
  We propose continuous-domain formulations for one-dimensional regression problems. We control the Lipschitz constant explicitly using a user-defined upper-bound. We show that both problems admit global minimizers that are continuous and piecewise-linear.
  arXiv  Detail & Related papers  (2021-12-27T07:03:43Z)
• Geometric Path Enumeration for Equivalence Verification of Neural Networks [2.007262412327553]
  We focus on the formal verification problem of NN equivalence which aims to prove that two NNs show equivalent behavior. We show a theoretical result by proving that the epsilon-equivalence problem is coNP-complete. In a third step, we implement the extended algorithm for equivalence verification and evaluate optimizations necessary for its practical use.
  arXiv  Detail & Related papers  (2021-12-13T11:56:08Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Achieving Small Test Error in Mildly Overparameterized Neural Networks [30.664282759625948]
  We show an algorithm which finds one of these points in time. In addition, we prove that for a fully connected neural net, with an additional assumption on the data distribution, there is a time algorithm.
  arXiv  Detail & Related papers  (2021-04-24T06:47:20Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  We propose ADOM - an accelerated method for smooth and strongly convex decentralized optimization over time-varying networks. Up to a constant factor, which depends on the network structure only, its communication is the same as that of accelerated Nesterov method.
  arXiv  Detail & Related papers  (2021-02-18T09:37:20Z)
• PEREGRiNN: Penalized-Relaxation Greedy Neural Network Verifier [1.1011268090482575]
  We introduce a new approach to formally verify the most commonly considered safety specifications for ReLU NNs. We use a convex solver not only as a linear feasibility checker, but also as a means of penalizing the amount of relaxation allowed in solutions.
  arXiv  Detail & Related papers  (2020-06-18T21:33:07Z)

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.