Exactly Computing the Local Lipschitz Constant of ReLU Networks

Introduction

We are interested in computing the Lipschitz constant of neural networks with ReLU activations. Formally, for a network $f$ with multiple inputs and outputs, we are interested in the quantity

Estimating or bounding the Lipschitz constant of a neural network is an important and well-studied problem. For the Wasserstein GAN formulation the discriminator is required to have a bounded Lipschitz constant, and there are several techniques to enforce this . For supervised learning Bartlett et al. have shown that classifiers with lower Lipschitz constants have better generalization properties. It has also been observed that networks with smaller gradient norms are more robust to adversarial attacks. Bounding the (local) Lipschitz constant has been used widely for certifiable robustness against targeted adversarial attacks . Lipschitz bounds under fair metrics may also be used as a means to certify the individual fairness of a model .

The Lipschitz constant of a function is fundamentally related to the supremal norm of its Jacobian matrix. Previous work has demonstrated the relationship between these two quantities for functions that are scalar-valued and smooth . However, neural networks used for multi-class classification with ReLU activations do not meet either of these assumptions. We establish an analytical result that allows us to formulate the local Lipschitz constant of a vector-valued nonsmooth function as an optimization over the generalized Jacobian. We access the generalized Jacobian by means of the chain rule. As we discuss, the chain rule may produce incorrect results for nonsmooth functions, even ReLU networks. To address this problem, we present a sufficient condition over the parameters of a ReLU network such that the chain rule always returns an element of the generalized Jacobian, allowing us to solve the proposed optimization problem.

We demonstrate our algorithm on various applications. We evaluate a variety of Lipschitz estimation techniques to definitively evaluate their relative error compared to the true Lipschitz constant. We apply our algorithm to yield reliable empirical insights about how changes in architecture and various regularization schemes affect the Lipschitz constants of ReLU networks.

We present novel analytic results connecting the Lipschitz constant of an arbitrary, possibly nonsmooth, function to the supremal norm of generalized Jacobians.

We present a sufficient condition for which the chain rule will always yield an element of the generalized Jacobian of a ReLU network.

We show that that it is provably hard to approximate the Lipschitz constant of a network to within a factor that scales almost linearly with input dimension.

We present a Mixed-Integer Programming formulation (LipMIP) that is able to exactly compute the local Lipschitz constant of a scalar-valued ReLU network over a polyhedral domain.

We analyze the efficiency and accuracy of LipMIP against other Lipschitz estimators. We provide experimental data demonstrating how Lipschitz constants change under training.

Gradient Norms and Lipschitz Constants

First we define the problem of interest. There have been several recent papers that leverage an analytical result relating the Lipschitz constant of a function to the maximal dual norm of its gradient . This analytical result is limited in two aspects: namely it only applies to functions that are both scalar-valued and continuously differentiable. Neural networks with ReLU nonlinearities are nonsmooth and for multi-class classification or unsupervised learning settings, typically not scalar-valued. To remedy these issues, we will present a theorem relating the Lipschitz constant to the supremal norm of an element of the generalized Jacobian. We stress that this analytical result holds for all Lipschitz continuous functions, though we will only be applying this result to ReLU networks in the sequel.

The quantity we are interested in computing is defined as follows:

And if $L^{(\alpha,\beta)}(f,\mathcal{X})$ exists and is finite, we say that $f$ is $(\alpha,\beta)$-locally Lipschitz over $\mathcal{X}$.

If $f$ is scalar-valued, then we denote the above quantity $L^{\alpha}(f,\mathcal{X})$ where $||\cdot||_{\beta}=|\cdot|$ is implicit. For smooth, scalar-valued $f$, it is well-known that

where $||z||_{\alpha^{*}}:=\sup_{||y||_{\alpha}\leq 1}y^{T}z$ is the dual norm of $||\cdot||_{\alpha}$ . We seek to extend this result to be applicable to vector-valued nonsmooth Lipschitz continuous functions. As the Jacobian is not well-defined everywhere for this class of functions, we recall the definition of Clarke’s generalized Jacobian :

The (Clarke) generalized Jacobian of $f$ at $x$, denoted $\delta_{f}(x)$, is the convex hull of the set of limits of the form $\lim\limits_{i\rightarrow\infty}\nabla f(x_{i})$ for any sequence $(x_{i})_{i=1}^{\infty}$ such that $\nabla f(x_{i})$ is well-defined and $x_{i}\rightarrow x$.

Informally, $\delta_{f}(x)$ may be viewed as the convex hull of the Jacobian of nearby differentiable points. We remark that for smooth functions, $\delta_{f}(x)=\{\nabla f(x)\}$ for all $x$, and for convex nonsmooth functions, $\delta_{f}(\cdot)$ is the subdifferential operator.

The following theorem relates the norms of the generalized Jacobian to the local Lipschitz constant.

where $\delta_{f}(\mathcal{X}):=\{G\in\delta_{f}(x)\mid x\in\mathcal{X}\}$ and $||M||_{\alpha,\beta}:=\sup\limits_{||v||_{\alpha}\leq 1}||Mv||_{\beta}$.

This result relies on the fact that Lipschitz continuous functions are differentiable almost everywhere (Rademacher’s Theorem). As desired our result recovers equation 3 for scalar-valued smooth functions. Developing techniques to optimize the right-hand-side of equation 4 will be the central algorithmic focus of this paper.

ReLU Networks and the Chain Rule

Theorem 1 relates the Lipschitz constant to an optimization over generalized Jacobians. Typically we access the Jacobian of a function through backpropagation, which is simply an efficient implementation of the familiar chain rule. However the chain rule is only provably correct for functions that are compositions of continuously differentiable functions, and hence does not apply to ReLU networks . In this section we will provide a sufficient condition over the parameters of a ReLU network such that any standard implementation of the chain rule will always yield an element of the generalized Jacobian.

To motivate the discussion, we turn our attention to neural networks with ReLU nonlinearities. We say that a function is a ReLU network if it may be written as a composition of affine operators and element-wise ReLU nonlinearities, which may be encoded by the following recursion:

where $\sigma(\cdot)$ here is the ReLU operator applied element-wise. We present the following example where the chain rule yields a result not contained in the generalized Jacobian. The univariate identity function may be written as $I(x):=2x-\sigma(x)+\sigma(-x)$. Certainly at every point $x$, $\delta_{I}(x)=\{1\}$. However as Pytorch’s automatic differentiation package defines $\sigma^{\prime}(0)=0$, Pytorch will compute $I^{\prime}(0)$ as 2 . Indeed, this is exactly the case where naively replacing the feasible set $\delta_{f}(\mathcal{X})$ in Equation 4 by the set of Jacobians returned by the chain rule will yield an incorrect calculation of the Lipschitz constant. To correctly relate the set of generalized Jacobians to the set of elements returnable by an implementation of the chain rule, we introduce the following definition:

Consider any implementation of the chain rule which may arbitrarily assign any element of the generalized gradient $\delta_{\sigma}(0)$ for each required partial derivative $\sigma^{\prime}(0)$. We define the set-valued function $\nabla^{\#}f(\cdot)$ as the collection of answers yielded by any such chain rule.

The subdifferential of the ReLU function at zero is the closed interval $$, so the chain rule as implemented in PyTorch and Tensorflow will yield an element contained in$\nabla^{\#}f(\cdot)$. Our goal will be to demonstrate that, for a broad class of ReLU networks, the feasible set in Equation 4 may be replaced by the set$\{G\in\nabla^{\#}f(x)\mid x\in\mathcal{X}\}$.

We say that a ReLU network with $n$ neurons is in general position if, for every subset of neurons $S\subseteq[n]$, the intersection $\cap_{i\in S}K_{i}$ is a finite union of $(d-|S|)$-dimensional polytopes.

We emphasize that this definition requires that particular ReLU kernel is a finite union of $(d-1)$-dimensional polytopes, i.e. the ‘bent hyperplanes’ referred to in . For a general position neural net, no $(d+1)$ ReLU kernels may have a nonempty intersection. We now present our theorem on the correctness of chain rule for general position ReLU networks.

Let $f$ be a general position ReLU network, then for every $x$ in the domain of $f$, the set of elements returned by the generalized chain rule is exactly the generalized Jacobian:

In particular this theorem implies that, for general position ReLU nets,

We will develop algorithms to solve this optimization problem predicated upon the assumption that a ReLU network is in general position. As shown by the following theorem, almost every ReLU network satisfies this condition.

The set of ReLU networks not in general position has Lebesgue measure zero over the parameter space.

Inapproximability of the Local Lipschitz Constant

In general, we seek algorithms that yield estimates of the Lipschitz constant of ReLU networks with provable guarantees. In this section we will address the complexity of Lipschitz estimation of ReLU networks. We show that under mild complexity theoretic assumptions, no deterministic polynomial time algorithm can provably return a tight estimate of the Lipschitz constant of a ReLU network

Computing Local Lipschitz Constants With Mixed-Integer Programs

While mixed-integer programming requires exponential time in the worst-case, implementations of mixed-integer programming solvers typically have runtime that is significantly lower than the worst-case. Our algorithm is unlikely to scale to massive state-of-the-art image classifiers, but we nevertheless argue the value of such an algorithm in two ways. First, it is important to provide a ground-truth as a frame of reference for evaluating the relative error of alternative Lipschitz estimation techniques. Second, an algorithm that provides provable guarantees for Lipschitz estimation allows one to make accurate claims about the properties of neural networks. We empirically demonstrate each of these use-cases in the experiments section.

We state the following theorem about the correctness of our MIP formulation and will spend the remainder of the section describing the construction yielding the proof.

Mixed-integer programming may be viewed as the extension of linear programming where some variables are constrained to be integral. The feasible sets of mixed-integer programs, may be defined as follows:

Mixed-integer programming then optimizes a linear function over a mixed-integer polytope.

From equation 7, our goal is to frame $\nabla^{\#}f(\mathcal{X})$ as a mixed-integer polytope. More accurately, we aim to frame $\{||G^{T}||_{\alpha}\mid G\in\nabla^{\#}f(\mathcal{X})\}$ as a mixed-integer polytope. The key idea for how we do this is encapsulated in the following example. Suppose $\mathcal{X}$ is some set and we wish to solve the optimization problem $\max_{x\in\mathcal{X}}(g\circ f)(x)$. Letting $\mathcal{Y}:=\{f(x)\mid x\in\mathcal{X}\}$ and $\mathcal{Z}:=\{g(y)\mid y\in\mathcal{Y}\}$, we see that

Thus, if $\mathcal{X}$ is a mixed-integer polytope, and $f$ is such that $f(\mathcal{X})$ is also a mixed-integer polytope and similar for $g$, then the optimization problem may be solved under the MIP framework.

From the example above, it suffices to show that $\nabla^{\#}f(\cdot)$ is a composition of functions $f_{i}$ with the property that $f_{i}$ maps mixed-integer polytopes to mixed-integer polytopes without blowing up in encoding-size. We formalize this notion with the following definition:

We say that a function $g$ is MIP-encodable if, for every mixed-integer polytope $M$, the image of $M$ mapped through $g$ is itself a mixed-integer polytope.

As an example, we show that the affine function $g(x):=Dx+e$ is MIP-encodable, where $g$ is applied only to the continuous variables. Consider the canonical mixed-integer polytope $M$ defined in equation 8, then $g(M)$ is the mixed-integer polytope over the existing variables $(x,a)$, with the dimension lifted to include the new continuous variable $y$ and a new equality constraint:

To represent $\{||G^{T}||_{\alpha}\mid x\in\nabla^{\#}f(\mathcal{X})\}$ as a mixed-integer polytope, there are two steps. First we must demonstrate a set of primitive functions such that $||\nabla^{\#}f(x)||_{\alpha}$ may be represented as a composition of these primitives, and then we must show that each of these primitives are MIP-encodable. In this sense, the following construction allows us to ‘unroll’ backpropagation into a mixed-integer polytope.

Then we have the two following lemmas which suffice to show that $\nabla^{\#}f(\cdot)$ is a MIP-encodable function:

Let $f$ be a scalar-valued general position ReLU network. Then $f(x)$, $\nabla^{\#}f(x)$, $||\cdot||_{1}$, and $||\cdot||_{\infty}$ may all be written as a composition of affine, conditional and switch operators.

This is easy to see for $f(x)$ by the recurrence in Equation 5; indeed this construction is used in the MIP-formulation for evaluating robustness of neural networks . For $\nabla^{\#}f$, one can define the recurrence:

where $\Lambda_{i}(x)$ is the conditional operator applied to the input to the $i^{th}$ layer of $f$. Since $\Lambda_{i}(x)$ takes values in $\{0,1\}^{*}$, $\text{Diag}(\Lambda(x))Y_{i+1}(x)$ is equivalent to $S(Y_{i+1}(x),\Lambda_{i}(x))$.

Let $g$ be a composition of affine, conditional and switch operators, where global lower and upper bounds are known for each input to each element of the composition. Then $g$ is a MIP-encodable function.

As we have seen, affine operators are trivially MIP-encodable. For the conditional and switch operators, global lower and upper bounds are necessary for MIP-encodability. Provided that our original set $\mathcal{X}$ is bounded, there exist several efficient schemes for propagating upper and lower bounds globally. Conditional and switch operators may be incorporated into the composition by adding only a constant number of new linear inequalities for each new variable. These constructions are described in full detail in Appendix D.

Related Work

We note the deep connection between certifying the robustness of neural networks and estimating the Lipschitz constant. Mixed-integer programming has been used to exactly certify the robustness of ReLU networks to adversarial attacks . Broadly speaking, the mixed-integer program formulated in each of these works is the same formulation we develop to emulate the forward-pass of a ReLU network. Our work may be viewed as an extension of these techniques where we emulate the forward and backward pass of a ReLU network with mixed-integer programming, instead of just the forward pass. We also note that the subroutine we use for bound propagation is exactly the formulation of FastLip , which can be viewed as a form of reachability analysis, for which there is a deep body of work in the adversarial robustness setting .

Experiments

We have described an algorithm to exactly compute the Lipschitz constant of a ReLU network. We now demonstrate several applications where this technique has value. First we will compare the performance and accuracy of the techniques introduced in this paper to other Lipschitz estimation techniques. Then we will apply LipMIP to a variety of networks with different architectures and different training schemes to examine how these changes affect the Lipschitz constant. Full descriptions of the computing environment and experimental details are contained in Appendix F. We have also included extra experiments analyzing random networks, how estimation changes during training, and an application to vector-valued networks in Appendix F.

Accuracy vs. Efficiency: As is typical in approximation techniques, there is frequently a tradeoff between efficiency and accuracy. This is the case for Lipschitz estimation of neural nets. While ours is the first algorithm to provide quality guarantees about the returned estimate, it is worthwhile to examine how accurate the extant techniques for Lipschitz estimation are. We compare against the following estimation techniques: CLEVER , FastLip , LipSDP , SeqLip and our MIP formulation (LipMIP) and its LP-relaxation (LipLP). We also provide the accuracy of a random lower-bounding technique where we report the maximum gradient dual norm over a random selection of test points (RandomLB) and a naive upper-bounding strategy (NaiveUB) where we report the product of the operator norm of each affine layer and scale by $\sqrt{d}$ due to equivalence of norms. In Table 1, we demonstrate the runtime and relative error of each considered technique. We evaluate each technique over the unit hypercube across random networks, networks trained on synthetic datasets, and networks trained to distinguish between MNIST 1’s and 7’s.

Effect of Training On Lipschitz Constant: As other techniques do not provide reliable estimates of the Lipschitz constant, we argue that these are insufficient for making broad statements about how the parameters or training scheme of a neural network affect the Lipschitz constant. In Figure 1 (left), we compare the returned estimate from a variety of techniques as a network undergoes training on a synthetic dataset. Notice how the estimates decrease in quality as training proceeds. On the other hand, in Figure 1 (right), we use LipMIP to provide reliable insights as to how the Lipschitz constant changes as a neural network is trained on a synthetic dataset under various training schemes. A similar experiment where we vary network architecture is presented in Appendix F.

Conclusion and Future Work

We framed the problem of local Lipschitz computation of a ReLU network as an optimization over generalized Jacobians, yielding an analytical result that holds for all Lipschitz continuous vector-valued functions. We further related this to an optimization over the elements returnable by the chain rule and demonstrated that even approximately solving this optimization problem is hard. We propose a technique to exactly compute this value using mixed integer programming solvers. Our exact method takes exponential time in the worst case but admits natural LP relaxations that trade-off accuracy for efficiency. We use our algorithm to evaluate other Lipschitz estimation techniques and evaluate how the Lipschitz constant changes as a network undergoes training or changes in architecture.

There are many interesting future directions. We have only started to explore relaxation approaches based on LipMIP and a polynomial time method that scales to large networks may be possible. The reliability of an exact Lipschitz evaluation technique may also prove useful in developing both new empirical insights and mathematical conjectures.

Acknowledgments and Disclosure of Funding

This research has been supported by NSF Grants CCF 1763702,1934932, AF 1901292, 2008710, 2019844 research gifts by Western Digital, WNCG IAP, computing resources from TACC and the Archie Straiton Fellowship.

Broader Impact

As deep learning begins to see use in situations where safety or fairness are critical, it is increasingly important to have tools to audit and understand these models. The Lipschitz computation technique we have outlined in this work is one of these tools. As we have discussed, an upper bound on the Lipschitz constant of a model may be used to efficiently generate certificates of robustness against adversarial attacks. Lipschitz estimates have the advantage over other robustness certificates in that they may be used to make robustness claims about large subsets of the input space, rather than certifying that a particular input is robust against adversarial attacks. Lipschitz estimation, if comuputable with respect to fair metrics, may be utilized to generate certificates of individual fairness (see for examples of this formulation of fair metrics and individual fairness). Our approach is the first to provide a scheme for Lipschitz estimation with respect to arbitrary norms, which may include these fair metrics.

Exact verification of neural networks has the added benefit that we are guaranteed to be generate the correct answer and not just a sound approximation. We argue that a fundamental understanding of the behavior of these models needs to be derived from both theoretical results and accurate empirical validation. As we have demonstrated, our technique is able to provide accurate measurements of the Lipschitz constant of small-scale neural networks. The computational complexity of the problem suggests that such accurate measurements are not tractably attainable for networks with millions of hyperparameters. Our experiments demonstrate that our technique is scalable to networks large enough that insights may be drawn, such as claims about how regularized training affects the Lipschitz constant. Further, exact verification techniques may be used as benchmarks to verify the accuracy of the more efficient verification techniques. Future Lipschitz estimation techniques, assuming that they do not provide provable guarantees, will need to assert the accuracy of their reported answers: it is our hope that this will be empirically done by comparisons against exact verification techniques, where the accuracy claims may then be extrapolated to larger networks.

References

Appendix

We first start with formal definitions and known facts. We present our results in general for vector-valued functions, but we will make remarks about the implications for scalar-valued networks along the way.

As we will be frequently referring to arbitrary norms, we recall the formal definition:

A norm $||\cdot||$ over vector space $V$ is a nonnegative valued function that meets the following three properties:

Triangle Inequality: For all $x,y\in V$, $||x+y||\leq||x||+||y||$

Absolute Homogeneity: For all $x\in V$, and any field element $a$, $||ax||=|a|\cdot||x||$.

Point Separation: If $||x||=0$, then $x=0$, the zero vector of $V$.

A convenient way to keep the notation straight is that $A$, above, can be viewed as a linear operator which maps elements from a space which has norm $||\cdot||_{\alpha}$ to a space which has norm $||\cdot||_{\beta}$, and hence is equipped with the norm $||A||_{\alpha,\beta}$. As long as $||\cdot||_{\alpha},||\cdot||_{\beta}$ are norms, then $||\cdot||_{\alpha,\beta}$ is a norm as well in that the three properties listed above are satisfied.

Every norm induces a dual norm, defined as

Indeed, assuming WLOG that neither $x$ nor $y$ are zero, and letting $u=\frac{x}{||x||_{\alpha}}$, we have

We can make a similar claim about the matrix norms defined above, $||\cdot||_{\alpha,\beta}$:

Indeed, assuming WLOG that $x$ is nonzero, letting $y=x/||x||_{\alpha}$ such that $||y||_{\alpha}=1$, we have

Then the Lipschitz constant, $L^{(\alpha,\beta)}(f,\mathcal{X})$, is the infimum over all such $L$. Equivalently, one can define $L^{\alpha,\beta}(f,\mathcal{X})$ as

Where we note that we are taking limits of a vector-valued function. We now add the following known facts:

If $f$ is lipschitz continuous, then it is absolutely continuous.

If $f$ is differentiable at $x$, all directional derivatives exist at $x$. The converse is not true, however.

If $f$ is differentiable at $x$, then for any vector $v$, $d_{v}f(x)=\nabla f(x)^{T}v$.

A.2 Proof of Theorem 1

Now we can state our first lemma, which claims that for any norm, the maximal directional derivative is attained at a differentiable point of $f$:

Essentially the plan is to say each of the following quantities are within $\epsilon$ of each other: $||d_{v}f(x)||_{\beta}$, the limit definition of $||d_{v}f(x)||_{\beta}$, the limit definition of $||d_{v}f(x^{\prime})||_{\beta}$ for nearby differentiable $x^{\prime}$, and the norm of the gradient at $x^{\prime}$ applied to the direction $v$.

By the definition of $\sup$, for every $\epsilon>0$, there exists an $x\in\mathcal{D}_{v}$ such that

Then for all $\epsilon>0$, by the limit definition of $d_{v}f(x)$ there exists a $\delta>0$ such that for all $t$ with $|t|<\delta$

Next we note that, since lipschitz continuity implies absolute continuity of $f$, and $t$ is now a fixed constant, the function $h(x):=\frac{f(x)}{||tv||_{\alpha}}$ is absolutely continuous. Hence there exists some $\delta^{\prime}$ such that for all $y\in\mathcal{X}$, $z$ with $||z||_{\alpha}\leq\delta^{\prime}$

Hence, by Rademacher’s theorem, there exists some differentiable $x^{\prime}$ within a $\delta^{\prime}$-neighborhood of $x$, such that both $\frac{||f(x^{\prime})-f(x)||_{\beta}}{||tv||_{\alpha}}<\epsilon/4$ and $\frac{||f(x^{\prime}+tv)-f(x+tv)||_{\beta}}{||tv||_{\alpha}}<\epsilon/4$, hence by the triangle inequality for $||\cdot||_{\beta}$

Combining equations 27 and 29 we have that

Taking limits over $\delta\rightarrow 0$, we get that the final term in equation 30 becomes $3\epsilon/4+||d_{v}f(x^{\prime})||_{\beta}$, which is equivalent to $3\epsilon/4+||\nabla f(x)^{T}v||_{\beta}$. Hence we have that

as desired, as our choice of $v$ was arbitrary.

Now we can restate and prove our main theorem.

Before we proceed with the proof, we make some remarks. First, note that if $f$ is scalar-valued and continuously differentiable, then $\nabla f(x)^{T}$ is a row-vector, and $||\nabla f(x)^{T}||_{\alpha,\beta}=||\nabla f(x)||_{\alpha^{*}}$, recovering the familiar known result. Second, to gain some intuition for this statement, consider the case where $f(x)=Ax+b$ is an affine function. Then $\nabla f(x)^{T}=A$, and by applying the theorem and leveraging the definition of $L^{(\alpha,\beta)}(f,\mathcal{X})$, we have

where the last equality holds because $\mathcal{X}$ is open.

It suffices to prove the following equality:

This follows naturally as if $x\in\text{Diff}(\mathcal{X})$ then $\delta_{f}(x)=\{\nabla f(x)\}$. On the other hand, if $x\not\in\text{Diff}(\mathcal{X})$, then for every extreme point $G$ in $\delta_{f}(x)$, there exists an $x^{\prime}\in\text{Diff}(\mathcal{X})$ such that $\nabla f(x^{\prime})=G$ (by definition). As we seek to optimize over a norm, which is by definition convex, there exists an extreme point of $\delta_{f}(x)$ which attains the optimal value. Hence, we proceed by showing that Equation 34 holds.

We show that for all $x,y\in\mathcal{X}$ that $\frac{||f(x)-f(y)||_{\beta}}{||x-y||_{\alpha}}$ is bounded above by $\sup_{x\in\text{Diff}(\mathcal{X})}||\nabla f(x)||_{\alpha,\beta}$. Then we will show the opposite inequality.

Fix any $x,y\in\mathcal{X}$, and note that since the dual of a dual norm is the original norm,

Moving the $\sup$ to the outside, we have

Further, there exists a lebesgue integrable function $g(t)$ that equals $h_{c}^{\prime}(t)$ almost everywhere and

We can assume without loss of generality that

where the supremum is defined over all points where $h_{c}^{\prime}(t)$ is defined. Then because $g$ agrees almost everywhere with $h_{c}^{\prime}$ and is bounded pointwise, we have the following chain of inequalities:

Where Equation 45 holds by Proposition 1, Equation 46 holds by Lemma 3, and the final inequality holds by Proposition 2. Dividing by $||x-y||_{\alpha}$ yields the desired result.

On the other hand, we wish to show, for every $\epsilon>0$, the existence of an $x,y\in\mathcal{X}$ such that

Fix $\epsilon>0$ and consider any point $z\in\mathcal{X}$ with $||\nabla f(z)^{T}||_{\alpha,\beta}\geq\sup_{x\in\mathcal{X}}||\nabla f(x)^{T}||_{\alpha,\beta}-\epsilon/2$.

Then $||\nabla f(z)^{T}||_{\alpha,\beta}=\sup_{||v||_{\alpha}\leq 1}||\nabla f(z)^{T}v||_{\beta}=\sup_{||v||_{\alpha}\leq 1}||d_{v}f(z)||_{\beta}$. By the definition of the directional derivative, there exists some $\delta>0$ such that for all $|t|<\delta$,

Hence setting $x=z+tv$ and $y=v$, we recover equation 48. ∎

Appendix B Chain Rule and General Position proofs

In this section, we provide the formal proofs of statements made in Section 3.

ReLU Kernels: For a ReLU network, define the functions $g_{i}(x)$ as the input to the $i^{th}$ ReLU of $f$. We define the $i^{th}$ ReLU kernel as the set for which $g_{i}=0$:

The Chain Rule: The chain rule is a means to compute derivatives of compositions of smooth functions. Backpropagation is a dynamic-programming algorithm to perform the chain rule, increasing efficiency by memoization. This is most easily viewed as performing a backwards pass over the computation graph, where each node has associated with it a partial derivative of its output with respect to its input. As mentioned in the main paper, the chain rule may perform incorrectly when elements of the composition are nonsmooth, such as the ReLU operator. Indeed, the ReLU $\sigma$ has a derivative which is well defined everywhere except for zero, for which it has a subdifferential of $$.

Consider any implementation of the chain rule which may arbitrarily assign any element of the generalized gradient $\delta_{\sigma}(0)$ for each required partial derivative $\sigma^{\prime}(0)$. We define the set-valued function $\nabla^{\#}f(\cdot)$ as the collection of answers yielded by any such chain rule.

While we note that our mixed-integer programming formulation treats $\nabla^{\#}(f)$ in this set-valued sense, most implementations of automatic differentiation choose either $\{0,1\}$ to be the evaluation of $\sigma^{\prime}(0)$ such that $\nabla^{\#}f$ is not set valued (e.g.,in PyTorch and Tensorflow, $\sigma^{\prime}(0)=0$). Our theory holds for our set-valued formulation, but in the case of automatic differentiation packages, as long as $\sigma^{\prime}(0)\in$, our results will hold.

B.2 Proof of Theorem 2

Before restating Theorem 2 and the proof, we introduce the following lemmas:

Let $\{K_{i}\}_{i=1}^{m}$ be the ReLU kernels of a general position neural net, $f$. Then for any $x$ contained in exactly $k$ of them, say WLOG $K_{1},\dots,K_{k}$, $x$ lies in the relative interior of one of the polyhedral components of $\cap_{i=1}^{k}K_{i}$.

Since $f$ is in general position, $\cap_{i=1}^{k}K_{i}$ is a union of $(d-k)$-dimensional polytopes. Let $P$ be one of the polytopes in this union such that $x\in P$. Since $P$ is an $(d-k)$-face in the polyhedral complex induced by $\{K_{i}\}_{i=1}^{m}$, each point on the boundary of $P$ is the intersection of at least $k+1$ ReLU kernels of $f$. Thus $x$ cannot be contained in the boundary of $P$ and must reside in the relative interior. ∎

The rest of the components are geometric. We introduce the notion of a cutting hyperplane:

We say that a hyperplane $H$ is a cutting hyperplane of a polytope $P$ if it is neither a separating nor supporting hyperplane of $P$.

We now state and prove several properties of cutting hyperplanes:

$H$ contains a point in the relative interior of $P$, and $H\cap P\neq P$.

$H$ cuts $P$ into two polytopes with the same dimension as $P$: $dim(P\cap H^{+})=dim(P\cap H^{-})=dim(P)$ and $H\cap P\neq P$.

Throughout we will denote the affine hull of $P$ as $U$. $\text{\ref{lemma:cut-a}}\implies\text{\ref{lemma:cut-b}}$: By assumption, $H$ is neither a supporting nor separating hyperplane. Since neither $H^{+}\cap P$ nor $H^{-}\cap P$ is $P$, $H\cap P\neq P$. Thus $H\cap P$ is a codimension 1 subspace, with respect to $U$. Since $H$ is not a supporting hyperplane, $H\cap U$ must not lie on the boundary of $P$ (relative to $U$). Thus $H\cap U$ contains a point in the relative interior of $P$ and so does $H$.

$\text{\ref{lemma:cut-b}}\implies\text{\ref{lemma:cut-c}}$: By assumption $H\cap P\neq P$. Consider some point, $x$, inside $H$ and the relative interior of $P$. By definition of relative interior, there is some neighborhood $N_{\epsilon}(x)$ such that $N_{\epsilon}(x)\cap U\subset P$. Thus there exists some $x^{\prime}\in N_{\epsilon}(x)$ such that $(N_{\epsilon^{\prime}}(x^{\prime})\cap U)\subset(H_{o}^{+}\cap P)$ and thus the affine hull of $H^{+}\cap P$ must have the same dimension as $U$. Similarly for $H^{-}\cap P$.

$\text{\ref{lemma:cut-c}}\implies\text{\ref{lemma:cut-a}}$: Since $P\cap H^{+}$ and $P\cap H^{-}$ are nonempty, then $P\cap H$ is nonempty and thus $H$ is not a separating hyperplane of $P$. Suppose for the sake of contradiction that $H^{+}\cap P=P$. Then $H_{o}^{-}\cap P=\emptyset$, this implies that $dim(H\cap P)=dim(P)$ which only occurs if $P\subseteq H$ which is a contradiction. Repeating this for $H^{-}\cap P$, we see that $H$ is not a supporting hyperplane of $P$. ∎

Let $F$ be a $(k)$-dimensional face of a polytope $P$. If $H$ is a cutting hyperplane of $F$, then $H$ is a cutting hyperplane of $P$.

Since $H$ is a cutting hyperplane of $F$, $H$ is neither a separating hyperplane nor is $P\subseteq H$. Thus it suffices to show that $H$ is not a supporting hyperplane of $P$. Since $H$ cuts $F$, there exist points inside $F\cap H_{o}^{+}$ and $F\cap H_{o}^{-}$, where $H_{o}^{+}$, $H_{o}^{-}$ are the open halfspaces induced by $H$. Thus neither $P\cap H_{o}^{+}$ nor $P\cap H_{o}^{-}$ are empty, which implies that $H$ is not a supporting hyperplane of $P$, hence $H$ must also be a cutting hyperplane of $P$.

Now we can proceed with the proof of Theorem 2:

Let $f$ be a general position ReLU network, then for every $x$ in the domain of $f$, the set of elements returned by the generalized chain rule $\nabla^{\#}f(x)$ is exactly the generalized Jacobian:

Part 1: The first part of this proof shows that if $x$ is contained in exactly $k$ ReLU kernels, then $x$ is contained in $2^{k}$ full-dimensional linear regions of $f$. We prove this claim by induction on $k$. The case where $k=1$ is trivial. Now assume that the claim holds up to $k-1$. Assume that $x$ lies in the ReLU kernel for every neuron in a set $S\subseteq[m]$, with $|S|=k$. Without loss of generality, let $j\in S$ be a neuron whose depth, $L$, is at least as great as the depth of every other neuron in $S$. Then one can construct a subnetwork $f^{\prime}$ of $f$ by considering only the first $L$ layers of $f$ and omitting neuron $j$. Now $K_{i}$ is a ReLU kernel of $f^{\prime}$ for every $i\in S\setminus\{j\}$, and further suppose that $f^{\prime}$ is a general position ReLU net. From the inductive hypothesis, we can see that $x$ is contained in exactly $2^{k-1}$ linear regions of $f^{\prime}$. By Lemma 4, $x$ resides in the relative interior of a $(n-k+1)$-dimensional polytope, $P$, contained in the union that defines $\cap_{i=1}^{k-1}K_{i}$. Since $j$ has maximal depth, $g_{j}(\cdot)$ is affine in $P$, and thus there exists some hyperplane $H$ such that $P\cap K_{j}=P\cap H$. Thus by Lemma 5 b, $H$ is a cutting hyperplane of $P$.

Consider some linear region $R$ of $f^{\prime}$ containing $x$. Then $g_{j}(x)$ is affine inside each $R$ and hence there exists some hyperplane $H_{R}$ such that $R\cap K_{j}=R\cap H_{R}$, with the additional property that $H_{R}\cap P=H\cap P$. By general position, $H\cap P\neq P$ and thus $H_{R}$ is a cutting hyperplane for $P$ by Lemma 5 b. Since $P$ is a $(n-k+1)$-dimensional face of $R$, we can apply Lemma 6 to see that $H_{R}$ is a cutting hyperplane for $R$ as desired.

Now we show that the implication proved in part 1 of the proof implies that $\nabla^{\#}f(x)=\delta_{f}(x)$. This follows in two steps. The first step is to show that $\nabla f^{\#}(x)$ is a convex set for all $x$, and the second step is to show the following inclusion holds:

Where, for any convex set $C$, $\mathcal{V}(C)$ denotes the set of extreme points of $C$. Then the theorem will follow by taking convex hulls.

To show that $\nabla^{\#}f(x)$ is convex, we make the following observation: every element of $\nabla^{\#}f(x)$ must be attainable by some implementation of the chain rule which assigns values for every $\sigma^{\prime}(0)$. If $\Lambda_{0}\in\nabla^{\#}f(x)$ is attainable by setting exactly zero $\sigma^{\prime}(0)^{\prime}s$ to lie in the open interval $(0,1)$, then $\Lambda_{0}$ is the Jacobian matrix corresponding to one of the full-dimensional linear regions that $x$ is contained in. Consider some $\Lambda_{r}\in\nabla^{\#}f(x)$ which is attainable by setting exactly $r$ $\sigma^{\prime}(0)^{\prime}s$ to lie in the open interval $(0,1)$. Then certainly $\Lambda_{r}$ may be written as the convex combination of $\Lambda^{(1)}_{r-1}$ and $\Lambda^{(2)}_{r-1}$ for two elements of $\delta_{f}(x)$, attainable by setting exactly $(r-1)$ ReLU partial derivatives to be nonintegral. This holds for all $r\in\{1,\dots k\}$ and thus $\nabla^{\#}f(x)$ is convex.

To show the equality in Equation 52, we first consider some element of $\mathcal{V}(\delta_{f}(x))$. Certainly this must be the Jacobian of some full-dimensional linear region containing $x$, and hence there exists some assignment of ReLU partial derivatives such that the chain rule yields this Jacobian. On the other hand, we’ve shown in the previous section that every element of $\nabla^{\#}f(x)$ may be written as a convex combination of the Jacobians of the full-dimensional linear regions of $f$ containing $x$. Hence each extreme point of $\nabla^{\#}f(x)$ must be the Jacobian of one of the full-dimensional linear regions of $f$ containing $x$. ∎

B.3 Proof of Theorem 3

The set of ReLU networks not in general position has Lebesgue measure zero over the parameter space.

We prove the claim by induction over the number of neurons of a ReLU network. As every ReLU network with only one neuron is in general position, the base case holds trivially. Now suppose that the claim holds for families of ReLU networks with $k-1$ neurons. Then we can add a new neuron in one of two ways: either we add a new neuron to the final layer, or we add a new layer with only a single neuron. Every neural network may be constructed in this fashion, so the induction suffices to prove the claim. Both cases of the induction may be proved with the same argument:

Consider some ReLU network, $f$, with $k-1$ neurons. Then consider adding a new neuron to $f$ in either of the two ways described above. Let $B_{f}$ denote the set of neural networks with the same architecture as $f$ that are not in general position, and similarly for $B_{f^{\prime}}$. Let $C_{f^{\prime}}$ denote the set of neural networks with the same architecture as $f^{\prime}$ that are not in general position, but are in general position when the $k^{th}$ neuron is removed. Certainly if $f$ is not in general position, then $f^{\prime}$ is not in general position. Thus

where $\mu_{f}(B_{f})=0$ by the induction hypothesis. We need to show the measure of $C_{f^{\prime}}$ is zero as follows. Letting $K_{k}$ denote the ReLU kernel of the neuron added to $f$ to yield $f^{\prime}$, we note that $f$ is not in general position only if one of the affine hulls of the polyhedral components of $K_{k}$ contains the affine hull of some polyhedral component of some intersection $\cap_{i\in S}K_{i}$ where $S$ is a nonempty subset of the $k-1$ neurons of $f$. We primarily control the bias parameter, as this is universal over all linear regions, and notice that this problem reduces to the following: what is the measure of hyperplanes that contain any of a finite collection of affine subspaces? By the countable subadditivity of the Lebesgue measure and the fact that the set of hyperplanes that contain any single affine subspace has measure 0, $\mu_{f^{\prime}}(C_{f^{\prime}})=0$. ∎

Appendix C Complexity Results

Here we recall some relevant preliminaries in complexity theory. We will gloss over some formalisms where we can, though a more formal discussion can be found here .

We are typically interested in combinatorial optimization problems, which we will define informally as follows:

A combinatorial optimization problem is composed of 4 elements: i) A set of valid instances; ii) A set of feasible solutions for each valid instance; iii) A non-negative cost or objective value for each feasible solution; iv) A goal: signifying whether we want to find a feasible solution that either minimizes or maximizes the cost function.

In this subsection, we will typically refer to problems using the letter $\Pi$, where instances of that optimization problem are $x$, and feasible solutions are $y$, and the cost of $y$ is $m(y)$. We will refer to the cost of the optimal solution to instance $x\in\Pi$ as $OPT(x)$. Optimization problems then typically have 3 formulations, listed in order of decreasing difficulty:

Search Problem: Given an instance $x$ of optimization problem $\Pi$, find $y$ such that $m(y)=OPT(x)$.

Computational Problem: Given an instance $x$ of optimization problem $\Pi$, find $OPT(x)$

Decision Problem: Given an instance $x$ of optimization problem $\Pi$, and a number $k$, decide whether or not $OPT(x)\geq k$.

Certainly an efficient algorithm to do one of these implies an efficient algorithm to do the next one. Also note that by a binary search procedure, the computational problem is polynomially-time reducible to the decision problem. As complexity theory is typically couched in discussion about membership in a language, it is slightly awkward to discuss hardness of combinatorial optimization problems. Since, every computational flavor of an optimization problem has a poly-time equivalent decision problem, we will simply claim that an optimization problem is NP-hard if its decision problem is NP-hard.

While many interesting optimization problems are hard to solve exactly, for many of these interesting problems there exist efficient approximation algorithms that can provide a guarantee about the cost of the optimal solution.

For a maximization problem $\Pi$, an approximation algorithm with approximation ratio $\alpha$ is a polynomial-time algorithm that, for every instance $x\in\Pi$, produces a feasible solution, $y$, such that $m(y)\geq OPT(x)/\alpha$.

Noting that $\alpha>1$ can either be a constant or a function parameterized by $|x|$, length of the binary encoding of instance $x$. We also note that this definition frames approximation algorithms as a “search problem".

A very powerful tool in showing the hardness of approximation problems is the notion of a $c$-gap problem. This is a form of promise problem, and proofs of hardness here are slightly stronger than what we actually desire.

Given an instance of an maximization problem $x\in\Pi$ and a number $k$, the c-gap problem aims to distinguish between the following two cases:

where there is no requirement on what the output should be, should $OPT(x)$ fall somewhere in $[k/c,k)$. For minimization problems, YES cases imply $OPT(x)\leq k$, and NO cases imply $OPT(x)>k\cdot c$.

Again we note that $c$ may be a function that takes the length of $x$ as an input. We now recall how a $c$-approximation algorithm may be used to solve the $c$-gap problem, implying the $c$-gap problem is at least as hard as the $c$-approximation.

If the $c$-gap problem is hard for a maximization problem $\Pi$, then the $c$-approximation problem is hard for $\Pi$.

Suppose we have an efficient $c$-approximation algorithm for $\Pi$, implying that for any instance $x\in\Pi$, we can output a feasible solution $y$ such that $OPT(x)/c\leq m(y)\leq OPT(x)$. Then we let $A_{k}$ be an algorithm that retuns YES if $m(y)\geq k/c$, and NO otherwise, where $y$ is the solution returned by the approximation algorithm Then for the gap-problem, if $OPT(x)\geq k$, we have that $m(y)\geq k/c$ so the $A_{k}$ will output YES. On the other hand, if $OPT(x)<k/c$, then $A_{k}$ will output NO. Hence, $A_{k}$ is an efficient algorithm to decide the $c$-gap problem. ∎

While hardness of approximation results arise from various forms, most notably the PCP theorem, we can black-box the heavy machinery and prove our desired results using only strict reductions, which we define as follows.

A strict reduction from problem $\Pi$ to problem $\Pi^{\prime}$, is a functions $f$, such that $f:\Pi\rightarrow\Pi^{\prime}$ maps problem instances of $\Pi$ to problem instances of $\Pi^{\prime}$. $f$ must satisfy the following properties that for all $x\in\Pi$

$\frac{|f(x)|}{|x|}\leq\alpha$, where $\alpha$ is a fixed constant

For which we can now state and prove the following useful proposition:

If $f,g$ are a strict reduction from optimization problem $\Pi$ to optimization problem $\Pi^{\prime}$, and the $c$-gap problem is hard for $\Pi$, where $c$ is polynomial in the size of $|x|$, then the $c^{\prime}$-gap problem is hard for $\Pi^{\prime}$, where $c^{\prime}\in\Theta(c)$.

Suppose both $\Pi$ and $\Pi^{\prime}$ are maximization problems, and the $c$-gap problem is hard for $\Pi$. We consider the case where $c$ is a function that takes as input the encoding size of instances of $\Pi$. We can define the function $c^{\prime}(n):=c(n/\alpha)$ for all $n$. Hence $c(|x|)=c^{\prime}(|f(x)|)$ for all $x\in\Pi$ by point 1 of the definition of strict reduction. Then for all $k$ and all $x\in\Pi$, the following two implications hold

Where both implications hold because $OPT_{\Pi}(x)=OPT_{\Pi^{\prime}}\left(f(x)\right)$. If the $c^{\prime}$-gap problem were efficiently decidable for $\Pi^{\prime}$, then the $c^{\prime}$-gap problem would be efficiently decidable for $\Pi$.

If $\Pi$ is a maximization problem and $\Pi^{\prime}$ is a minimization problem, then the following two implications hold:

Then letting $k=k^{\prime}\cdot c(|x|)$ we have that solving the $c^{\prime}$-gap problem for $\Pi^{\prime}$ would solve the $c$-gap problem for $\Pi$. The proofs for $\Pi,\Pi^{\prime}$ both being minimization problems, or $\Pi$ being a minimization and $\Pi^{\prime}$ being a maximization hold using similar strategies. ∎

C.2 Proof of Theorem 4

Now we return to ReLU networks and prove novel results about the inapproximability of computing the local Lipschitz constant of a ReLU network. Recall that we have defined ReLU networks as compositions of functions of the form :

If $x$ is contained in the interior of some linear region of a general position ReLU network $f$, then the chain rule provides the correct gradient of $f$ at $x$, where the $i^{th}$ coordinate of $\nabla f(x)$ is given by:

where $Paths(i)$ is the set of paths from the $i^{th}$ input, $x_{i}$, to the output in the computation graph, where the ReLU at each vertex is on, and $w_{j}$ is the weight of the $j^{th}$ edge along the path.

We define the following optimization problems:

MAX-GRAD is an optimization problem, where the set of valid instances is the set of scalar-valued ReLU networks. The feasible solutions are the set of differentiable points $x\in\mathcal{X}$, which have cost $||\nabla f(x)||_{1}$. The goal is to maximize this gradient norm.

MIN-LIP is an optimization problem where the set of valid instances is the set of piecewise linear neural nets. The feasible solutions are the set of constants $L$ such that $L\geq L(f)$. The cost is the identity function, and our goal is to minimize $L$.

Of course, each of these problems have decision-problem variants, denoted by $\texttt{MAX-GRAD}_{dec}$ and $\texttt{MIN-LIP}_{dec}$. We also remark that by Theorem 6, and proposition 4, the trivial strict reduction implies that it is at least as hard to approximate MIN-LIP as it is to approximate MAX-GRAD. For the rest of this section, we will only strive to prove hardness and inapproximability results for MAX-GRAD.

To do this, we recall the definition of the maximum independent set problem:

MIS is an optimization problem, where valid instances are undirected graphs $G=(V,E)$, and feasible solutions are $U\subseteq V$ such that for any $v_{i},v_{j}\in U$, $(v_{i},v_{j})\not\in E$. The cost is the size of $U$, and the goal is to maximize this cost.

Classically, it has been shown that MIS is NP-hard to optimize, but also is one of the hardest problems to approximate and does not admit a deterministic polynomial time algorithm to solve the $O(|V|^{1-\epsilon})$-gap problem .

For ease of exposition, we rephrase instances of MIS into instances of an equivalent problem which aims to maximize the size of consistent collections of locally independent sets. Given graph $G=(V,E)$, for any vertex $v_{i}\in V$, we let $N(v_{i})$ refer to the set of vertices adjacent to $V_{i}$ in $G$. We sometimes will abuse notation and refer to variables by their indices, e.g., $N(i)$. We also refer to the degree of vertex $i$ as $d(v_{i})$ or $d(i)$.

A locally indpendent set centered at $v_{i}$ is a $\{-1,+1\}$-labelling of the vertices $\{v_{i}\}\cup N(v_{i})$ such that the label of $v_{i}$ is $+1$ and the label of $v_{j}\in N(v_{i})$ is $-1$. Two locally independent sets are said to be consistent if, for every $v_{j}$ appearing in both locally independent sets, the label is the same in both locally independent sets. A consistent collection of locally independent sets is a set of locally independent sets that is pairwise consistent.

Then we can define an optimization problem:

LIS is an optimization problem, where valid instances are undirected graphs $G=(V,E)$, and feasible solutions are consistent collections of locally indpendent sets. The cost is the size of the collection, and the goal is to maximize this cost.

It is obvious to see that there is a trivial strict reduction between MIS and LIS. Indeed, any independent set defines the centers of a consistent collection of locally independent sets, and vice versa. As we will see, this is a more natural problem to encode with neural networks than MIS.

Now we can state our first theorem about the inapproximability of MAX-GRAD.

Next we define the second layer of ReLU’s, which has width $n$, and each neuron represents the status of a locally indpendent set. We define the input to the $i^{th}$ ReLU in this layer as $I_{i}$ with

for some fixed-value $\epsilon$ to be chosen later. Finally, we conclude our construction with a final affine layer to our neural net as

Let $\mathcal{I}(x)$ denote the set of indices of ReLU’s that are ‘on’ in the second-hidden layer of $h$: $\mathcal{I}(x):=\{i\;\;|\;\;I_{i}(x)>0\}$. Now we make the following claims about the structure of $h$.

For every $i$, if $i\in\mathcal{I}(x)$ then $x_{i}>1-\epsilon$ and $x_{j}<-1+\epsilon$ for all $j\in N(i)$. In addition, $\mathcal{I}(x)$ denotes the centers of a consistent collection of locally independent sets.

Indeed, if $I_{i}(x)>0$, then the sum of $(d(i)+1)$ $\psi$-terms is greater than $1-\epsilon$. As each $\psi$-term is in the range $$, each$\psi$-term must individually be at least$1-\epsilon$. And$\psi(x_{i})\geq 1-\epsilon$implies$x_{i}\geq 1-\epsilon$. Similarly,$-\psi(x_{j})\geq 1-\epsilon$implies that$x_{j}\leq-1+\epsilon$. Now consider any$i_{1},i_{2}$in$\mathcal{I}(x)$. Then the pair of locally independent sets centered at$v_{i_{1}}$and$v_{i_{2}}$ is certainly consistent. ∎

For any $x$ such that $h$ is differentiable at $x$, $\nabla h(x)_{i}\cdot x_{i}\geq 0$.

We split into cases based on the value of $x_{i}$ and rely on Claim C.1. Suppose $x_{i}\in(-1+\epsilon,1-\epsilon)$, then we have $I_{j}<0$ for any $j$ in $\{i\}\cup N(i)$ and hence $\nabla h(x)_{i}=0$. If $x_{i}\geq 1-\epsilon$, then every $j\in N(i)$ has $I_{j}<0$ and hence by Proposition 5, the only contributions to the $\nabla h(x)_{i}$ can be from paths that route from $x_{i}$ to the output through $I_{i}$. Hence

where both terms are nonnegative and hence so is $\nabla h(x)_{i}$. Finally, if $x_{i}\leq-1+\epsilon$, then the only contributions to $\nabla h(x)_{i}$ come from paths that route through $I_{j}$ for $j\in N(i)$, hence

where the first term is nonnegative and the second term is always nonpositive. We remark that because we have assumed $h$ to be differentiable at $x$, the chain rule provides correct answers, by Rademacher’s theorem. ∎

For any $x$, let $\mathcal{I}(x)$ be defined as above, $\mathcal{I}(x):=\{i\;\;|\;\;I_{i}(x)>0\}$. Then $||\nabla h(x)||_{1}\leq|\mathcal{I}(x)|$ and for every $x$. In addition, for every $x$, there exists a $y$ with $||\nabla h(y)||_{1}\geq|\mathcal{I}(x)|$.

where the final inequality follows because $||\nabla\psi(x_{i})||_{1}\leq 1$ everywhere it is defined. Combining equations 61 and 63 yields that $||\nabla h(x)||_{1}\leq|\mathcal{I}(x)|$.

On the other hand, suppose $\mathcal{I}(x)$ is given. Then we can construct $y$ such that $\mathcal{I}(y)=\mathcal{I}(x)$ and $||\nabla h(y)||_{1}=|\mathcal{I}(x)|$. To do this, set $y_{i}=1-\frac{\epsilon}{2n}$ if $i\in\mathcal{I}(x)$ and $y_{i}=-1+\frac{\epsilon}{2n}$ otherwise. Then note that $\mathcal{I}(x)=\mathcal{I}(y)$ and for every $i\in\mathcal{I}(y)$

and hence by Claim 2, we can replace the inequalities in equations 61 and 63 we have that

To demonstrate that this is indeed a strict reduction, we need to define functions $f$ and $g$, where $f$ maps instances of LIS to instances of MAX-GRAD, and $g$ maps feasible solutions of MAX-GRAD back to LIS. Clearly the construction we have defined above is $f$. The function $g$ can be attained by reading off the indices in $\mathcal{I}(x)$.

To demonstrate that the size of this construction does not blow up by more than a constant factor, observe that by representing weights as sparse matrices, the number of nonzero weights is a constant factor times the number of edges in $G$. Indeed, encoding each $\psi$ in the first layer takes $O(1)$ parameters for each vertex in $G$. Encoding $I_{i}(x)$ requires only $O(d(i))$ parameters for each $i$, and hence $2|E|$ parameters total. Assuming a RAM model where numbers can be represented by single atomic units, and $\epsilon$ is chosen to be $(n+2)^{-1}$, this is only a constant factor expansion.

The crux of this argument is to demonstrate that $OPT_{\texttt{MAX-GRAD}}(f(q))=OPT_{\texttt{LIS}}(q)$. It suffices to show that for every locally independent set $L$, there exists an $x$ such that $||\nabla h(x)||_{1}\geq k$, and for every $y$, there exists a locally independent set $L^{\prime}$ such that $|L^{\prime}|\geq||\nabla h(y)||_{1}$.

Suppose $L$ is a consistent collection of locally independent sets, with $|L|=k$. Any consistent collection of locally independent sets equivalently defines a labelling of each vertex of $G$, where $l_{i}$ denotes the label of vertex $v_{i}$: $l_{i}:=+1$ if the locally independent set centered at $v_{i}$ is contained in the collection, and $l_{i}:=-1$ otherwise. Then one can construct an $x$ such that $||\nabla h(x)||_{1}\geq k$. Indeed, for every $v_{i}$ with label $l_{i}$, set $x_{i}=l_{i}(1-\frac{\epsilon}{2n})$. By Claim C.1, under this $x$, $\mathcal{I}_{i}(x)\geq 0$ for every $i$ such that $l_{i}=+1$, $I_{i}(x)>0$. Then $|\mathcal{I}(x)|=k$ and by Claim C.3 there exists a $y$ such that $||\nabla h(y)||_{1}\geq k$.