PaperlayerView exact revision on arXiv

Source-linked AI summary

Exactly Computing the Local Lipschitz Constant of ReLU Networks

Matt Jordan, Alexandros G. Dimakis

arXiv:2003.01219v2stat.MLcs.LG

TL;DR

The paper asks how to compute Lipschitz constants for nonsmooth, vector-valued ReLU networks, which matter for robustness, generalization, and fairness. It characterizes them through generalized Jacobians, establishes when backpropagation is valid, and introduces exact mixed-integer computation despite strong inapproximability. Experiments compare estimators and examine effects of architecture and regularized training.

  • Problem

    Computing Lipschitz constants matters for robustness, generalization, and fairness, but ReLU networks are nonsmooth and often vector-valued, beyond classical smooth scalar-function analyses.

  • Method

    The paper characterizes local Lipschitz constants using generalized Jacobians, proves a sufficient general-position condition for valid chain-rule access, and formulates exact computation as a mixed-integer program.

  • Results

    The paper establishes strong inapproximability results and presents LipMIP as an exact method for ReLU-network Lipschitz constants under ℓ1 and ℓ∞ norms, alongside evaluations of estimators and training effects.

  • Takeaways & Limitations

    Exact Lipschitz computation provides a tool for evaluating estimator tightness and studying robustness- and fairness-relevant model behavior, while experiments support insights about architecture and regularization.

  • Takeaways & Limitations

    The exact method has exponential worst-case complexity, and accurate measurements are not tractably attainable for networks with millions of hyperparameters.

Abstract

from arXiv · show

The local Lipschitz constant of a neural network is a useful metric with applications in robustness, generalization, and fairness evaluation. We provide novel analytic results relating the local Lipschitz constant of nonsmooth vector-valued functions to a maximization over the norm of the generalized Jacobian. We present a sufficient condition for which backpropagation always returns an element of the generalized Jacobian, and reframe the problem over this broad class of functions. We show strong inapproximability results for estimating Lipschitz constants of ReLU networks, and then formulate an algorithm to compute these quantities exactly. We leverage this algorithm to evaluate the tightness of competing Lipschitz estimators and the effects of regularized training on the Lipschitz constant.

1 Introduction

The paper develops theory and algorithms for computing local Lipschitz constants of ReLU networks, addressing nonsmooth vector-valued functions and hard approximation problems.

  • Motivation: Lipschitz constants support robustness certification, generalization analysis, Wasserstein GAN constraints, and individual-fairness certification.The paper motivates Lipschitz computation as a tool for auditing models used in safety- or fairness-critical settings.
  • Analytic framework: The authors connect local Lipschitz constants of nonsmooth vector-valued functions to the supremal norm of their generalized Jacobians.They also give a sufficient condition ensuring that backpropagation returns a generalized-Jacobian element for ReLU networks.
  • Hardness: Approximating Lipschitz constants of scalar-valued ReLU networks under ℓ1 and ℓ∞ norms is provably hard, even though exact computation under ℓ2 was already known to be NP-hard.The inapproximability factor scales almost linearly with input dimension.
  • Experiments: The authors evaluate competing estimators against exact values and study how architecture and regularization affect ReLU-network Lipschitz constants.These experiments provide empirical information about estimator error and training-related changes.
  • Contributions: The paper presents LipMIP, a mixed-integer programming formulation that exactly computes the local Lipschitz constant of scalar-valued ReLU networks over polyhedral domains.The method is exact, though worst-case runtime is exponential.

2 Gradient Norms and Lipschitz Constants

This section extends the gradient-based characterization of Lipschitz constants from smooth scalar functions to nonsmooth vector-valued functions through Clarke generalized Jacobians.

  • Problem formulation: The framework addresses the limitations of prior gradient characterizations, which applied only to continuously differentiable scalar-valued functions.ReLU networks violate both smoothness and, in classification settings, scalar-output assumptions.
  • Generalized Jacobians: Clarke’s generalized Jacobian is the convex hull of limiting Jacobians from nearby differentiable points, providing a substitute where the ordinary Jacobian is undefined.For smooth functions it reduces to the singleton containing the ordinary Jacobian.
  • Generalized-Jacobian characterization: Theorem 1 expresses the local Lipschitz constant of any Lipschitz continuous vector-valued function as an optimization over the norms of generalized Jacobians.The result applies to arbitrary convex input and output norms.
  • Algorithmic focus: The paper’s central algorithmic task is to optimize the generalized-Jacobian norm characterization, recovering the standard dual-gradient formula in the smooth scalar case.Rademacher’s theorem supplies differentiability almost everywhere for the stated extension.

3 ReLU Networks and the Chain Rule

The section analyzes when chain-rule derivatives correctly represent generalized Jacobians in ReLU networks and identifies general position as a sufficient condition.

  • ReLU networks: A ReLU network is defined as a composition of affine maps and element-wise ReLU nonlinearities, represented recursively through layer preactivations.The chain-rule analysis concerns derivatives of this compositional representation.
  • Chain-rule failure: Naive automatic differentiation can produce an incorrect generalized-Jacobian element at ReLU kink points, as illustrated by PyTorch evaluating the identity example’s derivative at zero as 2 instead of 1.The issue arises because implementations choose a particular subgradient at zero.
  • General position: General position requires every intersection of ReLU kernels to be a finite union of polytopes with dimension reduced by the number of intersecting neurons.The condition excludes nonempty intersections of more than d ReLU kernels.
  • Chain-rule correctness: For a general-position ReLU network, the generalized chain rule returns exactly the generalized Jacobian at every input.This lets the paper replace the generalized-Jacobian feasible set with chain-rule-returnable elements when computing Lipschitz constants.
  • Generality of the condition: The set of ReLU networks that fail the general-position condition has Lebesgue measure zero in parameter space.Thus the sufficient condition holds for almost every parameter choice.

4 Inapproximability of the Local Lipschitz Constant

The paper shows that estimating ReLU-network Lipschitz constants is much harder than prior NP-hardness results suggest, with strong approximation barriers under ℓ1 and ℓ∞ norms.

  • No deterministic polynomial-time algorithm can provably return a tight Lipschitz estimate under mild complexity-theoretic assumptions.
  • The result matches the strong inapproximability of maximum independent set, with network encoding size scaling at least linearly in input dimension and neuron count.
  • Under the Exponential Time Hypothesis, approximating scalar-valued ReLU-network Lipschitz constants within Ω(d^(1−c)) is hard for both L∞ and L1.Here d is the input dimension, and c is any positive constant.

5 Computing Local Lipschitz Constants With Mixed-Integer Programs

The paper turns exact local Lipschitz computation into a mixed-integer program by encoding generalized-Jacobian backpropagation, yielding exact ℓ1 and ℓ∞ results under stated boundedness and network assumptions.

  • Because MIP is exponential in the worst case, the method is unlikely to scale to massive state-of-the-art image classifiers despite often lower practical solver runtimes.
  • Theorem 5 gives an efficiently encodable mixed-integer program whose optimum equals Lα(f, X) for general-position ReLU networks on neighborhoods of bounded polytopes, for α∈{1,∞}.
  • The construction unrolls backpropagation using affine, conditional, and switch operators, each shown to preserve mixed-integer-polytope encodability under suitable bounds.
  • LipMIP propagates bounds, lifts the feasible set, and adds constraints for the composition defining the generalized-Jacobian norm before optimizing with standard MIP solvers.
  • The framework extends to vector-valued networks and other norms, while LP relaxations and early-stopped MIP solvers provide provable upper bounds.

6 Related Work

The paper builds on generalized-Jacobian analysis, robustness-certification formulations, and prior Lipschitz estimators, while addressing gaps in exactness and approximation guarantees.

  • Prior work established Jacobian relationships for scalar smooth functions, whereas this paper targets vector-valued nonsmooth ReLU networks through generalized Jacobians.
  • Mixed-integer formulations for robustness certification provide the forward-pass encoding that this work extends to exact Lipschitz computation.
  • Existing estimators provide lower bounds, heuristic estimates, or provable upper bounds across different network classes and norms, but not the paper’s exact formulation.

7 Experiments

Experiments use LipMIP as a ground truth to compare estimator accuracy and study training effects, showing that estimator error grows during training and that regularization changes Lipschitz constants substantially.

  • The estimator comparison covers random networks, synthetic-data networks, and MNIST 1-versus-7 classifiers over the unit hypercube or specified ℓ∞ regions.
  • As training proceeds, existing Lipschitz estimates become less accurate relative to the true constant, limiting broad conclusions based on those estimators.
  • LipMIP is the slowest method but provides a provably exact answer, enabling reliable comparisons of competing estimators’ accuracy and efficiency.
  • During training, Lipschitz constants increase across the evaluated regularization settings; ℓ2 weight regularization exceeds the no-regularization baseline, while FGSM is most effective in this experiment.

8 Conclusion and Future Work

The paper frames local Lipschitz computation through generalized Jacobians, hardness results, and an exact mixed-integer method. It identifies exponential worst-case complexity while pointing to relaxations and scalable future methods.

  • The method optimizes over generalized Jacobians, establishes approximation hardness, and exactly computes ReLU-network Lipschitz constants with mixed-integer programming.The exact method has exponential worst-case time and supports LP relaxations that trade accuracy for efficiency.
  • The authors use the exact algorithm to evaluate existing estimators and study how training and architecture changes affect Lipschitz constants.
  • Future work includes stronger relaxation approaches and polynomial-time methods that scale to larger networks.Reliable exact evaluation may also support new empirical insights and mathematical conjectures.

9 Broader Impact

The paper positions exact Lipschitz computation as an auditing tool for safety and fairness. It connects Lipschitz bounds to robustness certificates over input subsets and to fairness metrics represented by arbitrary norms.

  • Lipschitz computation can support model auditing in safety- and fairness-critical applications.
  • Upper bounds on Lipschitz constants can generate robustness certificates for large input subsets rather than only individual inputs.
  • Arbitrary-norm Lipschitz estimation may accommodate fair metrics used to formulate individual fairness certificates.
  • The paper develops formal norm, dual-norm, matrix-norm, differentiability, and Lipschitz-continuity preliminaries for vector-valued functions.

A.2 Proof of Theorem 1

The proof establishes that maximal directional derivatives can be attained at differentiable points and uses this to equate local Lipschitz constants with supremal Jacobian norms for arbitrary norms.

  • Lemma 3 shows that, for any norm and direction, the maximal directional derivative is attained at a differentiable point.
  • The proof approximates nondifferentiable points by nearby differentiable points using directional derivatives, absolute continuity, and Rademacher’s theorem.
  • Theorem 6 equates the local Lipschitz constant of a locally Lipschitz vector-valued function with the supremal norm of its Jacobian over differentiable points.
  • The result recovers the familiar dual-gradient expression for scalar-valued continuously differentiable functions and the induced operator norm for affine maps.
  • The argument bounds finite differences by integrating directional derivatives along line segments and then applies norm inequalities.

B.2 Proof of Theorem 2

The proof uses polyhedral geometry of ReLU kernels to show that, for general-position networks, generalized chain-rule outputs coincide with the generalized Jacobian. It also establishes that nongeneral-position networks form a measure-zero set.

  • A cutting hyperplane intersects a polytope through its relative interior and divides it into two pieces of the same dimension.
  • Theorem 7 states that, for general-position ReLU networks, generalized chain-rule outputs exactly equal the generalized Jacobian at every input.
  • The proof shows that points lying on k ReLU kernels belong to multiple full-dimensional linear regions, using cutting hyperplanes and polytope faces.
  • Convexity of generalized chain-rule outputs and equality of extreme points with generalized-Jacobian extreme points yield equality after taking convex hulls.
  • The set of ReLU networks that are not in general position has Lebesgue measure zero in the fixed-architecture parameter space.

C.2 Proof of Theorem 4

The proof reduces locally independent sets to maximizing gradient norms of a ReLU network, establishing strong hardness results for local Lipschitz computation and an exact MIP formulation.

  • Complexity consequences: MAX-GRAD is the optimization problem of maximizing a differentiable point’s gradient norm, and its strict reduction implies MAX-GRADdec is NP-complete and MIN-LIPdec is CoNP-complete.The reduction also transfers approximation hardness from MAX-GRAD to MIN-LIP.
  • Reduction: MIS is reformulated as LIS, whose consistent collections encode independent sets and are more natural to represent with neural networks.An independent set specifies the centers of a consistent collection of locally independent sets, and the correspondence works in both directions.
  • Inapproximability: Under the exponential time hypothesis, no polynomial-time algorithm approximates L∞(f, X) or L1(f, X) within Ω(d^(1−c)) for any constant c > 0.The hardness applies to scalar-valued ReLU networks over X = R^d.
  • Reduction: The reduction maps each graph vertex to an input, constructs neurons for locally independent sets, and makes each selected set contribute to the network gradient norm.The construction uses the clipping function ψ(x) = σ(x + 1) − σ(x − 1) − 1 before assembling the locally independent-set gadgets.
  • Gradient correspondence: The constructed network satisfies ||∇h(x)||1 ≤ |I(x)|, while every x admits a point y with ||∇h(y)||1 ≥ |I(x)|.The active indices I(x) encode centers of a consistent collection of locally independent sets.
  • Exact computation: The exact LipMIP approach encodes ReLU-network gradients and norms using affine, conditional, and switch operators together with MIP-encodable formulations.Abstract interpretation supplies sound approximations that can make otherwise difficult optimization problems tractable, and extensions cover vector-valued networks and other norms.

E.2 Application to Untargeted Classification Robustness

The paper extends exact Lipschitz computation to vector-valued classifiers using a cross-norm that captures logit differences, yielding a LipMIP-computable robustness quantity under general-position assumptions.

  • Robustness formulation: For a vector-valued ReLU classifier, the cross-norm formulation relates label changes to Lipschitz constants of pairwise logit-difference functions.The multiclass construction considers the difference between the predicted class logit and each competing class logit.
  • Exact computation: When the cross-norm is linear and the network is in general position, LipMIP computes the local Lipschitz constant exactly.The result applies when the input norm is arbitrary and the output norm is the paper’s cross-norm.
  • Cross-norm: The cross-norm is defined from the convex hull of class basis vectors and pairwise difference vectors, producing a polyhedral norm with an efficient H-description.The construction includes e_i and e_i − e_j for all distinct classes.
  • Experimental setup: The synthetic evaluation dataset samples separated points in a unit hypercube, assigns random labels to leaders, and labels remaining points by their nearest leader.Figure 4 shows an example dataset and the decision boundaries of a classifier trained on it.
  • Estimator comparison: The experiments compare exact LipMIP against RandomLB, CLEVER, LipSDP, SeqLip, FastLip, and a naive product-of-layer-norms upper bound.LipMIP is evaluated without early stopping or timeout parameters, while the other methods provide bounds or estimates.

F.2 Experimental Details

The experiments evaluate estimator accuracy and efficiency on random, synthetic, and MNIST networks, then track exact Lipschitz constants during training and regularization.

  • Accuracy versus efficiency: The accuracy-versus-efficiency study evaluates 20 random networks, 20 synthetic-dataset networks, and 20 MNIST binary-classification networks.The architectures and training settings differ across the random, synthetic, and MNIST experiments.
  • Evaluation protocol: The reported metrics are compute time, standard deviation, and mean relative error relative to LipMIP’s returned answer.LipMIP serves as the reference for the relative-error comparisons.
  • Effect of training: The training-effect study trains a [2, 20, 40, 20, 2] network for 1000 epochs and evaluates LipMIP every 25 epochs over the [0, 1]^2 domain.The study compares different regularization schemes on a synthetic two-dimensional dataset.
  • Effect of training: Estimator accuracy during training is evaluated on the network trained only with CrossEntropy loss.This uses the same experimental setup as the training-effect study.
  • Random networks: The random-network experiment evaluates 5000 [10] networks over an origin-centered ℓ∞ ball of radius 1000.LipMIP computes the maximal ℓ1 gradient norm for each network.

F.3 Additional Experiments

Additional experiments examine how architecture, training, regularization, and estimator relaxations affect Lipschitz estimates across synthetic, random, and MNIST networks.

  • Effect of Architecture: Lipschitz constants rise exponentially with network depth, while changing width produces only a small increase in LipMIP’s returned value.Figure 5 uses a log-scale y-axis for depth, indicating greater sensitivity to depth than width.
  • L1(f, X) Estimation: The additional L1(f, X) experiments compare maximal gradient-norm estimates on random, synthetic, and MNIST networks.The MNIST setting uses a [784, 20, 20, 20, 2] network distinguishing 1s from 7s, with local regions defined by ℓ1-balls.
  • Training and Regularization: Training and regularization are evaluated with a [2, 20, 40, 20, 2] network on a synthetic dataset, where even LipSDP is not tight in the reported setting.Figure 6 compares training effects and regularization schemes for L1(f, X).
  • Relaxed LipMIP: Table 4 evaluates LipLP and early-stopped LipMIP as efficiency–accuracy relaxations of exact LipMIP on random and synthetic networks.The experiments vary LipMIP integrality gaps of 100%, 10%, 1%, and 0%.
  • Cross-Lipschitz Evaluation: Cross-Lipschitz evaluation tests naive and mixed-integer formulations for untargeted robustness verification on 100-class networks.The procedure uses 8-dimensional synthetic data, ℓ∞-balls of radius 0.1, and networks with layer sizes [8, 40, 40, 40, 100].
Loading 2003.01219v2…