PaperlayerView exact revision on arXiv

Source-linked AI summary

Lipschitz constant estimation of Neural Networks via sparse polynomial optimization

Fabian Latorre, Paul Rolland, Volkan Cevher

arXiv:2004.08688v1cs.LGstat.ML

TL;DR

Estimating neural-network Lipschitz constants tightly is important for robustness certificates and related applications, but standard upper bounds can be overly pessimistic. LiPopt addresses this by relaxing the problem to polynomial optimization and exploiting sparse connectivity to reduce computation; experiments report tighter ℓ∞-Lipschitz upper bounds than literature baselines.

  • Problem

    Tight Lipschitz upper bounds are needed for robustness certificates, while the product of layer-wise bounds is easy to compute but overly pessimistic.

  • Method

    LiPopt relaxes Lipschitz estimation to polynomial optimization and uses sparse connectivity to derive smaller positivity-certification programs.

  • Results

    LiPopt provides tighter ℓ∞-Lipschitz upper bounds than literature baselines on random-weight and MNIST-trained networks.

  • Takeaways & Limitations

    The framework offers empirically tight upper bounds while using network sparsity to reduce the computational burden of polynomial certificates.

  • Takeaways & Limitations

    The underlying polynomial optimization is NP-hard, and sparse-pattern convergence guarantees can be lost for non-dense networks.

Abstract

from arXiv · show

We introduce LiPopt, a polynomial optimization framework for computing increasingly tighter upper bounds on the Lipschitz constant of neural networks. The underlying optimization problems boil down to either linear (LP) or semidefinite (SDP) programming. We show how to use the sparse connectivity of a network, to significantly reduce the complexity of computation. This is specially useful for convolutional as well as pruned neural networks. We conduct experiments on networks with random weights as well as networks trained on MNIST, showing that in the particular case of the $\ell_\infty$-Lipschitz constant, our approach yields superior estimates, compared to baselines available in the literature.

1 INTRODUCTION

The paper formulates Lipschitz-constant estimation for neural networks and introduces LiPopt, which uses polynomial optimization and network sparsity to obtain tighter, smaller upper-bound programs. Experiments focus on the ℓ∞ norm and compare configurations across random and MNIST-trained networks.

  • Problem: The paper estimates the Lipschitz constant L(fd), the smallest L satisfying |f(x) − f(y)| ≤ L∥x − y∥ for all x and y.The constant matters for generalization, adversarial robustness, robust classification certificates, and Wasserstein GAN discriminators.
  • Motivation: Lower bounds and heuristic estimates do not provide robustness certificates, while products of layer-wise constants are easy to compute but often loose.The paper motivates tighter upper bounds despite their higher computational cost.
  • LiPopt: LiPopt upper-bounds neural-network Lipschitz constants by relaxing the problem to polynomial optimization, covering unit balls described by polynomial inequalities.The framework includes common ℓ2 and ℓ∞ norms.
  • Sparsity: Sparse connectivity yields a sequence of smaller linear programs whose size is analyzed in terms of neurons, depth, and network sparsity.The approach targets dense, convolutional, and potentially broader directed acyclic computation-graph architectures.
  • Experiments: Experiments on random-weight and MNIST-trained networks vary depth, width, and sparsity, showing tighter L(fd) upper bounds than literature baselines for the ℓ∞ norm.The reported experiments evaluate the proposed LP sequence across these network configurations.

2 POLYNOMIAL OPTIMIZATION FORMULATION

The paper converts Lipschitz estimation into polynomial optimization over derivative and dual-norm variables, then obtains tractable upper bounds through polynomial-positivity relaxations. It also supports local estimates using restricted inputs, with a focus on the ℓ∞ norm and differentiable activations.

  • Formulation: The Lipschitz constant can be represented through the supremum of the gradient’s dual norm over the input domain.A theorem under differentiability and Lipschitz-continuity assumptions provides this optimization starting point.
  • Assumptions: The analysis assumes a Lipschitz-continuous, differentiable activation, excluding ReLU while allowing activations such as ELU and softplus.This assumption ensures the network satisfies the theorem’s differentiability requirements.
  • Formulation: Introducing si = σ′(fi(x)) and using derivative bounds converts the gradient expression into a norm-gradient polynomial optimization problem.For ELU or softplus, the derivatives satisfy 0 ≤ si ≤ 1.
  • Choice of norm: For the ℓ∞ norm, the dual-ball constraints become polynomial inequalities −1 ≤ ti ≤ 1, enabling the polynomial optimization formulation.The framework can be adapted with minor modifications to certain even ℓp norms.
  • Computational approach: Polynomial optimization is generally NP-hard, so LiPopt obtains upper bounds through tractable approximations of the positivity-constrained problem.These approximations are described as a systematic way to bound L(fd).
  • Local estimation: Restricted input domains, such as image hypercubes or ε-balls around data points, allow computation of local Lipschitz constants.Tighter derivative bounds can be incorporated into the optimization problem for local estimates.

3 HIERARCHICAL SOLUTION BASED ON A POLYNOMIAL POSITIVITY

LiPopt converts the neural-network Lipschitz upper-bound problem into a hierarchy of tractable linear programs derived from polynomial positivity certificates. The hierarchy yields valid, increasingly tight bounds, while sparsity reduces program size and computation.

  • The network problem is rewritten as a polynomial optimization problem over [0, 1]^n using the substitution s0 := (t + 1)/2.
  • LiPopt uses Krivine’s positivity certificate to represent positivity of λ − p and, by degree truncation, constructs a hierarchy of linear programs.Sum-of-squares certificates are theoretically possible, but Krivine’s certificate produces LPs rather than SDPs.
  • The first nontrivial hierarchy level occurs at k = d, because the certificate degree must be at least the norm-gradient polynomial’s depth d.
  • Every hierarchy solution provides a valid upper bound on L(fd), and the sequence is non-increasing and converges to the maximum in the original upper-bound formulation.
  • The dense Krivine LP can scale as O(n^k), reaching approximately 9.3 × 10^8 for a one-hidden-layer MNIST network with 100 neurons.This motivates exploiting polynomial sparsity to obtain drastically smaller LPs with similar approximation properties.
  • For local Lipschitz bounds, tighter variable bounds are first obtained and then used to rescale the POP onto [0, 1]^n.

4 REDUCING THE NUMBER OF VARIABLES

The paper exploits network connectivity to construct sparse polynomial positivity certificates, reducing the LP size while preserving upper-bound estimation for Lipschitz constants. The resulting complexity depends on architecture-specific clique sizes, with especially favorable bounds for convolutional networks.

  • Sparsity pattern: Sparse connectivity enables smaller positivity certificates than the general Krivine certificate for networks with convolutional or pruned structure.The method uses a network-dependent graph to derive a sparsity pattern for the norm-gradient polynomial.
  • Sparse certificate: The sparse Krivine certificate yields a sequence of LPs approximating the polynomial-optimization upper bound on L(fd).The number of polynomials appearing at hierarchy degree k determines the certificate size and affects approximation quality.
  • Guarantees and limitations: For non-dense networks, the induced pattern remains an upper-bound certificate but may lose the guarantee that LP values converge to the POP maximum.A chordal completion can provide a valid sparsity pattern when that convergence guarantee is needed.
  • Architecture-dependent complexity: For fully connected networks, the induced pattern uses cliques of size n1 + . . . + nd−1 + 1 and requires O(n(n1 + . . . + nd−1 + 1)k−1) polynomials.This improves the general upper bound despite all network connections being nonzero.
  • Architecture-dependent complexity: For unstructured sparsity with at most r incoming connections per neuron, clique size is O(rd) and the polynomial count is O(ndrdk).The depth dependence is exponential in this bound, and the estimate may be loose when neurons share inputs.
  • Architecture-dependent complexity: For 2D convolutional networks with a constant number of channels, clique size is O(d3) and the certificate contains O(ndd3k) polynomials.This is a drastic complexity decrease compared with the unstructured-sparsity case.

5 QCQP REFORMULATION AND SHOR’S SDP RELAXATION

The paper reformulates the polynomial optimization problem as a QCQP and applies Shor’s SDP relaxation. This provides another upper-bounding route, but the extra relaxation can weaken tightness and SDPs scale less favorably than LPs.

  • QCQP reformulation: Polynomial optimization problems can be converted into QCQPs by introducing variables and quadratic constraints; for d = 2, no modification is necessary.The reformulation applies to both the ℓ∞- and ℓ2-norm cases.
  • QCQP reformulation: For d = 3, introducing product variables such as s1,2 converts the cubic norm-gradient polynomial into a quadratic objective.The resulting QCQP uses y = [1, s0, s1, s2, s1,2] with dimension 1 + n + n1n2.
  • Shor’s SDP relaxation: Shor’s relaxation replaces quadratic expressions with linear constraints on a positive semidefinite matrix X = yyT ≽ 0.When d = 2, the resulting SDP coincides with the formulation studied by Raghunathan et al.
  • Limitations: The SDP route is limited by an additional relaxation step and by the smaller problem sizes handled efficiently by off-the-shelf SDP solvers.For d = 2, the relaxation provides a constant-factor approximation to the original QCQP.
  • Relation to SOS: The QCQP and hierarchical SOS approaches are equivalent in essence at the first SDP degree, differing in their polynomial positivity certificates.Shor’s SDP relaxation corresponds to the first-degree SOS hierarchical SDP solution.

6 RELATED WORK

The paper positions LiPopt against existing Lipschitz-bound methods by emphasizing true upper bounds, broader norm support, and applicability beyond shallow or activation-specific settings. It also highlights local-domain refinement for robustness certification.

  • Existing estimators: SeqLip provides heuristic estimates without guarantees, whereas LipSDP provides true upper bounds but is formulated for the ℓ2-norm.The paper contrasts these methods with LiPopt’s polynomial-inequality formulation for broader norm support.
  • Norm coverage: LiPopt can accommodate any norm whose unit ball is describable by polynomial inequalities, unlike LipSDP’s ℓ2-specific formulation.The paper notes that converting an ℓ2 bound to an ℓ∞ bound through norm equivalence can be loose.
  • Local robustness certification: LiPopt can refine robustness bounds by restricting the POP domain to a local ball around a sample instead of estimating only a global Lipschitz constant.The paper states that this can potentially yield a tighter bound and a larger certified-robustness region.
  • Depth and relaxation scope: Raghunathan et al. derive an ℓ∞ upper bound through Shor’s relaxation for one-hidden-layer networks, while the paper identifies this as a special case of its broader SDP framework.The comparison concerns the depth restriction d = 2 in the earlier method.
  • Activation scope: Weng et al.’s local bound uses arguments specific to ReLU, whereas LiPopt applies to activations whose derivatives are bounded.This distinguishes LiPopt’s activation scope from an activation-specific robustness-bound method.

7 EXPERIMENTS

Experiments compare LiPopt with SDP, Lip-SDP, UBP, and sampling-based bounds on random and MNIST-trained networks. LiPopt provides tighter bounds while exploiting sparsity, with computation time depending strongly on network sparsity.

  • Random networks: The random-network study averages Lipschitz bounds over 10 networks for each width and sparsity configuration, using LBS as the relative-error reference.The reported relative error is (L̂ − LLBS)/LLBS because the true Lipschitz constant is unavailable.
  • Random networks: LiPopt-3 is competitive with SDP at the network-depth degree, while increasing the degree by one makes it uniformly better across tested configurations.UBP bounds were too large to plot, as were Lip-SDP bounds for one-hidden-layer networks.
  • Random networks: LiPopt-k computation time depends heavily on sparsity, whereas SDP time depends only on network size.With fixed sparsity, LiPopt-k becomes faster and produces better upper bounds as network size grows.
  • Trained networks: The MNIST experiment uses a 300–100 fully connected network with one-hot output, estimating the constant for label 8.Pruning removed 95% of weights while preserving the same test accuracy.
  • Trained networks: The MNIST Lipschitz bounds are 88.3 for LiPopt-4, 94.6 for LiPopt-3, 98.8 for SDP, and 691.5 for UBP, with LBS at 84.2.These values are reported for the pruned network and the selected output label.
  • Local constants: Local LiPopt bounds remain separated from sampled local lower bounds as the neighborhood radius increases, indicating potential for larger certified robustness regions.The local-versus-global plots use LiPopt-3 and sample 15 random networks.

8 CONCLUSION AND FUTURE WORK

The paper presents LiPopt as a polynomial-positivity approach for upper-bounding neural-network Lipschitz constants. It reports tight empirical bounds, while noting computational expense and proposing scalability directions that exploit network structure.

  • Conclusion: LiPopt computes neural-network Lipschitz upper bounds through polynomial positivity certificates and generalizes existing methods.The resulting optimization problems can be computationally expensive, but network sparsity can reduce the burden.
  • Future work: Future work targets larger and deeper networks through divide-and-conquer decomposition, parallel optimization, and low-memory custom SDP algorithms.The proposed directions are intended to further scale the methods.

A PROOF OF THEOREM 1

The proof establishes the Lipschitz constant–gradient relationship by proving both inequalities under differentiability, Lipschitz continuity, and an open convex domain.

  • Theorem setting: The theorem assumes a differentiable, Lipschitz-continuous function on an open convex Euclidean subset and uses the dual norm.These assumptions define the setting for the gradient characterization.
  • Upper inequality: The proof uses convexity of the domain to support the forward inequality connecting function differences with gradient norms.The cited step explicitly invokes convexity of X.
  • Reverse inequality: For the reverse inequality, the proof selects a point whose gradient norm approaches the supremum within an arbitrary positive epsilon.It then uses openness to construct a sequence of admissible increments approaching zero.
  • Reverse inequality: A first-order expansion along the constructed increments introduces a vanishing remainder term, after which division by the increment norm yields the Lipschitz lower bound.The remainder satisfies δ(h) → 0 as h → 0.

B PROOF OF PROPOSITION 1

The proposition derives a valid sparsity pattern for the norm-gradient polynomial by grouping variables associated with output neurons and their upstream paths. The proof uses path structure and chordal-graph maximal cliques.

  • Sparsity pattern: For each final-layer neuron, the proposed sparsity set contains that neuron and variables from neurons with directed paths to it.The sets are indexed by the output neurons of a dense network.
  • Coverage: The sparsity sets cover all neurons because every neuron connects to at least one neuron in the final layer.Otherwise, the disconnected neuron could be removed from the network.
  • Polynomial structure: The norm-gradient polynomial decomposes into path-based monomials, allowing terms involving each final neuron to depend only on its corresponding sparsity set.Writing p as the sum of these components establishes the required dependency property.
  • Chordal graph: The proof invokes maximal cliques of a chordal graph as a valid sparsity pattern and uses density only for the final clique property.The first two properties hold for arbitrary network architectures.
  • Chordal graph: Adding edges among all non-final-layer neurons produces a chordal graph whose maximal cliques coincide with the proposition’s sparsity sets.This identifies the graph-theoretic structure underlying the construction.

C EXPERIMENTS ON RANDOM NETWORKS

The section compares Lipschitz bounds for random networks with one and two hidden layers.

  • Figure 9 compares Lipschitz bounds for 1-hidden-layer networks.
  • Together, the figures cover Lipschitz-bound comparisons across networks with one and two hidden layers.
  • Figure 10 compares Lipschitz bounds for 2-hidden-layer networks.
Loading 2004.08688v1…